СТБ 34.101.60

СТБ 34.101.60 — государственный стандарт алгоритмов разделения секрета в Республике Беларусь Полное название стандарта — СТБ 34.101.60-2014 «Информационные технологии и безопасность. Алгоритмы разделения секрета». Введен в действие 28 января 2014 года.

Описание

Настоящий стандарт определяет криптографические алгоритмы разделения и восстановления секрета (ключа) между пользователями, а также алгоритмы генерации параметров, необходимых при разделении / восстановлении секрета. Секрет разделяется между пользователями таким образом, что лишь заранее определенные подмножества пользователей могут восстановить его.

Настоящий стандарт применяется при разработке средств криптографической защиты информации. Стандарт определяет криптографические алгоритмы разделения секрета между 𝑛 пользователями. Разделение секрета выполняется так, что для выбранного порогового числа 𝑡 ∈ {1, 2, . . . , 𝑛} только подмножества из 𝑟 > 𝑡 пользователей могут восстановить секрет.

Перед разделением секрета пользователи договариваются об использовании общего открытого ключа М₀. После выбора М₀ пользователи строят свои открытые ключи М₁, М₂, . . . , М_n и сообщают их друг другу. В качестве идентификатора может выступать кодовое представление имени пользователя, адреса его электронной почты, личного номера и т. д. Одни и те же открытые ключи могут использоваться для разделения нескольких секретов. Секрет представляет собой двоичное слово длины 𝑙 ∈ {128, 192, 256}.

Для алгоритмов, определенных в настоящем стандарте, выполняются следующие свойства:

• частичные секреты S_I являются двоичными словами такой же длины, как и 𝑆;
• совокупность из 𝑟 < 𝑡 частичных секретов не содержит никакой информации об 𝑆.

Разделение секрета между пользователями выполняет дилер. Обычно, он же генерирует открытые ключи, если они не заданы. В качестве дилера может выступать лицо, программа, программно-аппаратное устройство. В настоящем стандарте полагается, что дилер строго следует алгоритму разделения секрета, не меняет параметры и ключи, то есть является доверенной стороной.

Для разделения секретных данных большого объема рекомендуется выбрать секретный ключ случайно равновероятно из {0, 1}^𝑙, зашифровать данные на этом ключе, а затем разделить ключ на частичные секреты. Другой способ обработки данных большого объема заключается в их разбиении на фрагменты — двоичные слова длины 𝑙 — и разделении каждого фрагмента по отдельности. При таком подходе следует предусмотреть контроль длины и целостности исходных данных, контроль порядка следования фрагментов и порядок обработки последнего, возможно неполного, фрагмента.

Открытые ключи М₀, М₁, . . . , М_n представляют собой двоичные слова длины 𝑙. При распространении и хранении открытых ключей должен обеспечиваться контроль их целостности.

Открытым ключам соответствуют многочлены f_i(𝑥) = 𝑥^𝑙 + М_i(𝑥), 𝑖 = 0, 1, . . . , 𝑛. Для корректного восстановления секрета многочлены f_i(𝑥) должны быть попарно взаимно простыми.

При разделении секрета используется одноразовый ключ 𝑘. Одноразовый ключ должен вырабатываться без возможности предсказания и уничтожаться после использования. Для создания одноразовых ключей может быть использован физический генератор случайных чисел, удовлетворяющий техническим нормативным правовым актам, или алгоритм генерации псевдослучайных чисел. Входные данные алгоритма должны включать секретный ключ и уникальную синхропосылку. Длина ключа алгоритма генерации должна быть не меньше 𝑙.

Частичные секреты являются двоичными словами длины 𝑙. Они должны храниться и распространяться с соблюдением мер конфиденциальности и контроля целостности. Утрата частичных секретов в количестве, меньшем порогового числа 𝑡, не влияет на безопасность исходного секрета и не влечет необходимость его замены.

Поскольку одни и те же открытые ключи могут использоваться при разделении различных секретов, рекомендуется выбирать уникальный номер секрета и распространять его вместе с частичными секретами. При восстановлении секрета по этому номеру можно судить о соответствии частичных секретов друг другу.

Алгоритмы генерации параметров

Входные и выходные данные

Входными данными алгоритма генерации общего открытого ключа является длина секрета 𝑙 ∈ {128, 192, 256}. Выходными данными является общий открытый ключ 𝑀₀ ∈ {0, 1}^𝑙.

Входными данными алгоритма генерации открытых ключей пользователей являются число пользователей 𝑛, длина секрета 𝑙 ∈ {128, 192, 256} и общий открытый ключ 𝑀₀ ∈ {0, 1}^𝑙. Выходными данными являются слова 𝑀₀, . . . , 𝑀_n ∈ {0, 1}^𝑙. — открытые ключи пользователей.

Входными данными алгоритма генерации открытого ключа пользователя по идентификатору являются длина секрета 𝑙 ∈ {128, 192, 256}, общий открытый ключ 𝑀₀ ∈ {0, 1}^𝑙 и идентификатор пользователя 𝐼𝑑 ∈ {0, 1}. Выходными данными является слово 𝑀 ∈ {0, 1}^𝑙— открытый ключ пользователя с идентификатором 𝐼𝑑.

Вспомогательные алгоритмы и переменные

Алгоритм belt-hash. Используется алгоритм хэширования belt-hash. Входными данными алгоритма является слово 𝑋 ∈ {0, 1}, выходными — хэш-значение 𝑌 ∈ {0, 1}²⁵⁶.

Алгоритм BuildIrred. Входными данными алгоритма являются слово 𝑢 ∈ {0, 1}^𝑙 и общий открытый ключ 𝑀₀ ∈ {0, 1}^𝑙. Выходными данными является многочлен 𝑓(𝑥) ∈ F2[𝑥], степень которого не превосходит 𝑙 и который является либо неприводимым, либо постоянным.

Переменные. Используются переменная 𝑢 со значениями в {0, 1}^𝑙 и переменные 𝑎(𝑥), 𝑏(𝑥), 𝑔(𝑥), 𝑞(𝑥), 𝑟(𝑥) со значениями в F₂[𝑥].

Алгоритм BuildIrred

Для генерации многочлена 𝑓(𝑥) выполняются следующие шаги: 1. Установить 𝑎(𝑥) ← 𝑢(𝑥), 𝑏(𝑥) ← 𝑎(0).

2. Для 𝑖 = 1, 2, . . . , 2𝑙 − 1:

1) 𝑎(𝑥) ← 𝑎(𝑥)𝑢(𝑥) mod (︀𝑥𝑙 + 𝑀0(𝑥))︀;
2) 𝑏(𝑥) ← 𝑥𝑏(𝑥) + 𝑎(0).

3. Установить 𝑎(𝑥) ← 𝑥2𝑙.

4. Установить 𝑔(𝑥) ← 0, 𝑓(𝑥) ← 1.

5. Пока 𝑏(𝑥) ̸= 0 и deg 𝑏(𝑥) ≥ 𝑙 выполнить:

1) 𝑞(𝑥) ← 𝑎(𝑥) div 𝑏(𝑥);
2) 𝑎(𝑥) ← 𝑎(𝑥) mod 𝑏(𝑥);
3) 𝑎(𝑥) ↔ 𝑏(𝑥);
4) 𝑔(𝑥) ← 𝑔(𝑥) + 𝑓(𝑥)𝑞(𝑥);
5) 𝑔(𝑥) ↔ 𝑓(𝑥).

6. Возвратить 𝑓(𝑥).

Алгоритм генерации общего открытого ключа

Для генерации общего открытого ключа выполняются следующие шаги:

1. Выбрать произвольным образом 𝑀₀ ∈ {0, 1}^𝑙.

2. Если многочлен 𝑥^𝑙 + 𝑀₀(𝑥) не является неприводимым, то вернуться к шагу 1.

3. Возвратить 𝑀₀.

Алгоритм генерации открытых ключей пользователей

Для генерации открытых ключей пользователей выполняются следующие шаги:

1. Установить 𝑖 ← 1.

2. Пока 𝑖 ≤ 𝑛 выполнить:

1) выбрать произвольным образом 𝑢 ∈ {0, 1}𝑙;
2) 𝑓(𝑥) ← BuildIrred(𝑢, 𝑀0);
3) если deg 𝑓(𝑥) ̸= 𝑙, то вернуться к шагу 2.1;
4) определить 𝑀𝑖 ∈ {0, 1}𝑙, исходя из условия 𝑓(𝑥) = 𝑥𝑙 + 𝑀0(𝑥);
5) если Mi совпадает с некоторым из слов 𝑀0, . . . , 𝑀i-1, то вернуться к шагу 2.1;
6) 𝑖 ← 𝑖 + 1.

3. Возвратить 𝑀₁, . . . , 𝑀_n.

Алгоритм генерации открытого ключа пользователя по идентификатору

Для генерации открытого ключа пользователя по его идентификатору выполняются следующие шаги: 1. Установить 𝑢 ← ⟨belt-hash(𝐼𝑑)⟩_n.

2. Установить 𝑓(𝑥) ← BuildIrred(𝑢, 𝑀₀).

3. Если deg 𝑓(𝑥) ̸= 𝑙 или 𝑓(𝑥) = 𝑥^𝑙 + 𝑀₀(𝑥), то

1) 𝑢 ← ⟨ū + 1⟩l;
2) вернуться к шагу 2.

4. Определить 𝑀 ∈ {0, 1}^𝑙, исходя из условия 𝑓(𝑥) = 𝑥^𝑙 + 𝑀₀(𝑥).

5. Возвратить 𝑀.

Основные алгоритмы

Входные и выходные данные

Входными данными алгоритма разделения секрета являются число пользователей 𝑛, пороговое число 𝑡, длина секрета 𝑙 ∈ {128, 192, 256}, секрет 𝑆 ∈ {0, 1}^𝑙 и открытые ключи M₀, M₁, . . . , 𝑀_n∈{0, 1}^𝑙.

Выходными данными алгоритма разделения секрета являются слова 𝑆₁, 𝑆₂, . . . , 𝑆_n ∈{0, 1}^𝑙 — частичные секреты пользователей.

При восстановлении секрета используются данные пользователей с номерами 𝑖₁, 𝑖₂, . . . , 𝑖_r ∈ {1, 2, . . . , 𝑛}. Входными данными алгоритма восстановления секрета являются длина секрета 𝑙 ∈ {128, 192, 256}, частичные секреты 𝑆_i1, 𝑆_i2, . . . , 𝑆_ir ∈ {0, 1}^𝑙, общийоткрытый ключ 𝑀₀ ∈ {0, 1}^𝑙 и открытые ключи 𝑀_i1, 𝑀_i2, . . . , 𝑀_ir ∈ {0, 1}^𝑙.

Выходными данными алгоритма восстановления секрета является либо секрет 𝑆 ∈{0, 1}^𝑙, либо признак ОШИБКА. Возврат признака ОШИБКА означает, что открытые ключи некорректны.

Примечание — Восстановленный секрет не обязательно будет совпадать с первоначально разделенным. Для гарантированного совпадения требуется сохранение целостности открытых ключей и частичных секретов, а также выполнение условия 𝑟 > 𝑡.

Вспомогательные алгоритмы и переменные

Расширенный алгоритм Евклида. Для определения многочленов 𝑑(𝑥), 𝑢(𝑥), 𝑣(𝑥) может использоваться расширенный алгоритм Евклида.

Одноразовый ключ 𝑘. При разделении секрета используется одноразовый ключ 𝑘 ∈{0, 1}^(t-1)𝑙.

Переменные. Используется переменная 𝐶(𝑥) со значениями в F₂[𝑥]. Значение 𝐶(𝑥) должно быть уничтожено после использования. При восстановлении секрета дополнительно используются переменные 𝑑(𝑥), 𝑢(𝑥), 𝑣(𝑥), 𝑔(𝑥) со значениями в F₂[𝑥].

Алгоритм разделения секрета

Для разделения секрета выполняются следующие шаги:

1. Выработать k ←^R {0, 1}^(t-1)𝑙.

2. Установить 𝐶(𝑥) ← (𝑥^𝑙 + 𝑀₀(𝑥))𝑘(𝑥) + 𝑆(𝑥).

3. Для 𝑖 = 1, 2, . . . , 𝑛 выполнить:

1) 𝑆i(𝑥) ← 𝐶(𝑥) mod (𝑥𝑙 + 𝑀i(𝑥)).

4. Возвратить 𝑆₁, 𝑆₂, . . . , 𝑆_n.

Алгоритм восстановления секрета

Для восстановления секрета выполняются следующие шаги:

1. Установить 𝐶(𝑥) ← 𝑆_i1(𝑥), 𝑔(𝑥) ← 𝑥^𝑙 + 𝑀_i1(𝑥).

2. Для 𝑗 = 2, 3, . . . , 𝑟 выполнить:

1) найти 𝑑(𝑥), 𝑢(𝑥), 𝑣(𝑥) такие, что 𝑑(𝑥) = НОД(𝑥𝑙 + 𝑀ij, 𝑔(𝑥)) и 𝑢(𝑥)(𝑥𝑙 + 𝑀ij) + 𝑣(𝑥)𝑔(𝑥) = 𝑑(𝑥);
2) если 𝑑(𝑥) ̸= 1, то возвратить ОШИБКА;
3) 𝐶(𝑥) ← 𝑢(𝑥)(𝑥𝑙 + 𝑀ij(𝑥))𝐶(𝑥) + 𝑣(𝑥)𝑔(𝑥)𝑆ij(𝑥);
4) 𝑔(𝑥) ← (𝑥𝑙 + 𝑀ij(𝑥))𝑔(𝑥);
5) 𝐶(𝑥) ← 𝐶(𝑥) mod 𝑔(𝑥).

3. 𝑆(𝑥) ← 𝐶(𝑥) mod (𝑥^𝑙 + 𝑀₀).

4 Возвратить 𝑆.

Ссылки

• http://apmi.bsu.by/assets/files/std/bels-spec29.pdf