Приветствую, Хабр! В своей предыдущей статье (посвященной оценке необходимости срочного перехода на постквантовые криптоалгоритмы) я упомянул о принятых в США стандартах на постквантовые алгоритмы электронной подписи и обмена ключами. Данные стандарты были приняты в августе прошлого года (а перед этим они в течение года проходили оценку криптологическим сообществом в виде драфтов), при этом Институт стандартов и технологий США NIST анонсировал принятие дополнительных (альтернативных) постквантовых криптостандартов в будущем.

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

Кратко о конкурсе NIST по выбору постквантовых криптостандартов

Выбор постквантовых криптоалгоритмов осуществлялся NIST в рамках открытого конкурса, в процессе которого производился тщательный сравнительный анализ заявленных на конкурс постквантовых алгоритмов электронной подписи (ЭП) и асимметричного шифрования / инкапсуляции ключей (PKE/KEM; не могу сказать, в какой именно момент, но в процессе конкурса NIST отказался от рассмотрения постквантовых алгоритмов, которые можно было бы использовать именно для асимметричного шифрования, а не для инкапсуляции ключей, поэтому далее будем в этой части говорить только о KEM).

Проведение подобных конкурсов можно считать уже устоявшейся традицией – вспомним, как минимум, открытые конкурсы NIST по выбору алгоритмов для последующей стандартизации в виде стандартов блочного симметричного шифрования (AES), хеширования (SHA-3) и низкоресурсного аутентифицированного шифрования с присоединенными данными – AEAD. Каждый раз проведение подобного конкурса привлекает внимание значительного числа коллективов криптологов как к разработке заявляемых на конкурс криптоалгоритмов, так и к их криптоанализу, что в итоге дает значительный импульс развитию конкретного направления криптографии в мире. Не стал в этом смысле исключением и конкурс по постквантовым криптоалгоритмам; причем, несмотря на выпуск по результатам конкурса нескольких стандартов, данный конкурс еще не завершен – об этом будет сказано далее.

Конкурс по выбору постквантовых криптоалгоритмов был объявлен в 2016 г., в декабре которого были опубликованы требования к подаваемым на конкурс алгоритмам [1] (перечень источников приведен в конце статьи). На текущий момент проведены 3 раунда конкурса; в каждом из них выполнялся анализ поданных на конкурс алгоритмов (всего было принято 48 алгоритмов PKE/KEM и 20 алгоритмов ЭП), по результатам которого количество алгоритмов сужалось: в третьем раунде осталось 4 алгоритма KEM и 3 алгоритма ЭП плюс в качестве резервных еще 5 алгоритмов KEM и 3 алгоритма ЭП [2].

По результатам проведенных исследований (сводная информация была опубликована в отчете по 3 раунду конкурса [3]), подготовки документов по стандартизации и общественного обсуждения (начатого в августе 2023 г.) предполагаемых к публикации стандартов в августе 2024 г. NIST издал три стандарта уровня FIPS (Federal Information Processing Standard – Федеральный стандарт обработки информации), основная информация о которых приведена в таблице [4, 5]:

Рассмотрим алгоритмы, описанные в данных стандартах FIPS. 

Алгоритм инкапсуляции ключей ML-KEM (FIPS 203)

Стандарт FIPS 203 [6] описывает алгоритм инкапсуляции ключей ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism – алгоритм инкапсуляции ключей на основе модульных решеток). Данный алгоритм основан на сложности решения одной из известных проблем теории решеток – проблемы «модульного обучения с ошибками» MLWE (Module Learning with Errors). Кратко описать суть ее применения в алгоритме ML-KEM можно так: ошибка вносится в вычисления на этапе инкапсуляции, после чего она удаляется в процессе декапсуляции, что невозможно сделать без знания ключа декапсуляции.

Как было сказано в предыдущей статье, алгоритмы KEM подразумевают генерацию и передачу общего симметричного ключа для двух сторон обмена информацией с использованием следующих процедур:

• KeyGen – генерация долговременной асимметричной ключевой пары для последующей инкапсуляции/декапсуляции ключей;

• Encaps – генерация и инкапсуляция симметричного ключа;

• Decaps – декапсуляция (извлечение) симметричного ключа.

Рассмотрим, как реализованы данные процедуры в алгоритме ML-KEM. 

Дисклеймер: приведенные далее описания процедур рассматриваемых алгоритмов значительно упрощены по сравнению с оригинальными описаниями, которые несравнимо более масштабны и не могут быть переданы в формате статьи на Хабре; их можно найти в соответствующих стандартах [6-8]. При этом упрощенные описания позволяют, на мой взгляд, передать основную суть преобразований; сокращения коснулись, в основном, конвертаций между различными представлениями данных и избыточных для цели данной статьи математических подробностей. 

Процедура генерации ключей инкапсуляции и декапсуляции KeyGen выполняет следующие действия (попытка схематически изобразить процедуру KeyGen с комментариями приведена на рисунке далее):

1. Получает с помощью генератора случайных чисел (ГСЧ) два случайных числа и размером 32 байта каждое.

2. Вычисляет два 32-байтных значения ρ и σ путем хеширования с помощью стандартного алгоритма SHA3-512 (с 64-байтным выходным значением) [9] результата конкатенации случайного числа и 1-байтного параметра алгоритма k; данный параметр определяет размерности ряда данных, используемых алгоритмом ML-KEM:

   · ключей инкапсуляции и декапсуляции (перечень параметров и размеры ключей для стандартизованных вариантов алгоритма ML-KEM будут приведены далее);

   · ряда внутренних параметров алгоритма.

3. Формируется матрица A размерности k × k, элементы которой вычисляются псевдослучайным образом на основе значения ρ и их индексов и ; матрица состоит из элементов a_ij ∈ ℤ_q²⁵⁶, где q = 3329 – одна из основных констант алгоритма.

4. Генерируется вектор ключа декапсуляции s (состоящий из k элементов кольца R_q = ℤ_q[X]/(Xⁿ + 1), где n = 256 – еще одна из основных констант алгоритма) путем псевдослучайной выборки из байтового массива размером 64_η1 (η₁ – параметр алгоритма), при этом для каждого из k элементов байтовый массив создается путем хеширования входных данных на основе значения σ и индекса элемента с помощью стандартной хеш-функции с переменным размером выходного значения (XOF – Extendable Output Function) SHAKE256, также описанной в [9].

5. Аналогичным образом генерируется вектор ошибки e той же размерности.

6. Вычисляется вектор t размерности k путем умножения матрицы A на вектор s и сложения результата умножения с вектором e.

7. Ключ инкапсуляции EK получается путем преобразования вектора t в байтовый массив и конкатенации результата со значением ρ.

8. Ключ декапсуляции DK представляет собой результат конкатенации следующих элементов:
   ·     результата преобразования вектора s в байтовый массив;
   ·     ключа EK;
   ·     хеш-кода ключа EK, вычисленного с помощью алгоритма SHA3-256 (еще одна определенная в стандарте [9] хеш-функция с 256-битным выходным значением);
   ·     случайного числа .

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

Вектор ошибки не дает возможности вычислить ключ декапсуляции на основе ключа инкапсуляции, но при этом, как будет показано далее, не препятствует корректным вычислениям в процессе инкапсуляции и декапсуляции.

Процедура генерации и инкапсуляции общего ключа Encaps состоит из следующей последовательности операций:

1. С помощью ГСЧ генерируется 32-байтное случайное число m.

2. Вычисляется 256-битный (32-байтный) ключ симметричного шифрования K:

   {K, r} = SHA3-512(m || SHA3-256(EK)),

   где r – 32-байтное псевдослучайное значение, которое будет использовано в дальнейших вычислениях.

3. Из левой части ключа EK извлекается вектор t (см. описание процедуры KeyGen).

4. Из правой части ключа EK извлекается значение ρ.

5. На основе значения ρ восстанавливается матрица A. Данная матрица может быть предвычислена и сохранена для неоднократного использования или может даже передаваться (публиковаться) вместе с ключом EK (но, если рассматривать данную матрицу как часть ключа, размер ключа значительно возрастет; приведенные ниже размеры ключей показаны без учета матрицы A).

6. Аналогично описанному в рамках процедуры KeyGen процессу генерации векторов s и e на основе значения r и параметра η₁ генерируется вектор y размерности k, используемый впоследствии для генерации шифртекста.

7. Аналогичным образом (но со значением η₂, которое также является одним из параметров алгоритма) вычисляются вектор ошибки e₁ и элемент e₂∈ℤ_q²⁵⁶ .

8. Вычисляется вектор u следующим образом:

   u = A^T × y + e₁.

    

9. Число m преобразуется в элемент ∈ℤ_q ²⁵⁶ .

10. Вычисляется элемент v ∈ ℤ_q²⁵⁶ следующим образом (где Conv– операция конвертации результата произведения векторов в ℤ_q ²⁵⁶):

    v = Conv(t^T × y) + e₂ + 

11. Вектор u и элемент v преобразуются в байтовые строки c₁ и c₂ соответственно.

12. Шифртекст C представляет собой результат конкатенации строк c₁ и c₂.

Таким образом, ключ симметричного шифрования K генерируется на основе случайного числа m, но преобразования из m в K с участием других элементов выполняются детерминированно. Следовательно, знания m (в совокупности с (открытым) ключом инкапсуляции EK) достаточно для восстановления ключа K.

Значение m подвергается последовательности преобразований (m →  →  → c₂), в результате которой оно в зашифрованном виде помещается в шифртекст C (таким образом, получить m для восстановления K может только обладатель (секретного) ключа декапсуляции). На этапах преобразования  →  и вычисления вектора u в шифртекст подмешивается ошибка в виде, соответственно, элемента e₂ и вектора e₁.

Копия ключа K также является выходным значением процедуры Encaps (помимо шифртекста); она остается у выполнившего ее пользователя.

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

1. Извлекает из ключа декапсуляции DK его компоненты (перечислены ранее в описании процедуры KeyGen).

2. Извлекает из шифртекста C его компоненты (c₁ и c₂).

3. Восстанавливает вектор u’ и элемент v’ из их байтовых представлений c₁ и c₂ соответственно.

4. Вычисляет элемент w∈ℤ_q ²⁵⁶ : w = v’ - Conv(s^T × u’),

   где вектор s восстановлен из байтового представления соответствующей (левой) части ключа DK.

5. Преобразует элемент w в 32-байтное число m’.

6. Вычисляет пару значений K’ и r’:

   {K’, r’} = SHA3-512(m’ || h),

   где h – хеш-код ключа EK, извлеченный из ключа декапсуляции.

7. Выполняет проверочное вычисление шифртекста С’ (аналогично процедуре Encaps, начиная с шага 3) с использованием значений m’ и r’ вместо, соответственно, значений m и r.

8. Если вычисленный шифртекст С’ совпадает с полученным шифртекстом c, то K’ представляет собой общий ключ симметричного шифрования K. В противном случае считается, что процесс в целом завершился неудачно (в этом случае неверно извлеченный ключ K’ замещается результатом применения функции SHAKE128 к конкатенации значения z (извлекается из ключа декапсуляции) и шифртекста C.  

Вероятность ошибочной декапсуляции симметричного ключа крайне мала и составляет
от 2^-174,8 до 2^-138,8 в зависимости от варианта алгоритма.
Стандартом [6] предусмотрено три варианта алгоритма ML-KEM с фиксированными наборами параметров, которые приведены в таблице:

Назначение параметра k было описано ранее; кратко опишу остальные параметры алгоритма:

• η₁ и η₂ определяют размеры выходного значения функции SHAKE256 и индексы выбираемых элементов массивов при формировании, соответственно, значащих векторов и векторов ошибок;

• d_u и d_v являются внутренними параметрами преобразований при формировании байтовых строк c₁ и c₂ при инкапсуляции и, соответственно, извлечении данных из этих строк при декапсуляции; данные параметры напрямую влияют на размеры шифртекста.

Размеры ключей и шифртекста вариантов алгоритма ML-KEM приведены в следующей таблице:

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

Стандарт FIPS 203 рекомендует применять вариант ML-KEM-768 данного алгоритма, а остальные варианты использовать только в следующих случаях:

• когда требуется более быстродействующий алгоритм при умеренных требованиях к криптостойкости – использовать ML-KEM-512;

• когда требуется еще более высокий уровень криптостойкости – использовать ML-KEM-1024.

Алгоритм электронной подписи ML-DSA (FIPS 204)

Стандарт FIPS 204 [7] описывает алгоритм ML-DSA (Module-Lattice-Based Digital Signature Algorithm) – алгоритм электронной подписи на основе модульных решеток.
В основе данного алгоритма ЭП лежит та же проблема MLWE, на которой базируется рассмотренный выше алгоритм инкапсуляции ключа ML-KEM, а также проблема MSIS (Module Short Integer Solution) – проблема поиска близких к минимальным целочисленных значений, удовлетворяющих определенной системе линейных уравнений.
Как и описанный ранее ML-KEM, алгоритм ML-DSA имеет три варианта, каждому из которых соответствует определенный набор фиксированных параметров, обеспечивающих различные уровни безопасности (значения параметров будут приведены далее):

• ML-DSA-44;

• ML-DSA-65;

• ML-DSA-87.

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

• используется ли ГСЧ при вычислении ЭП (отсутствие ГСЧ не рекомендуется, но возможно);

• используется ли внешний алгоритм хеширования сообщений (такой вариант называется HashML-DSA, он также не рекомендуется, но допускается).

Опишем процедуры алгоритма ML-DSA (со значительными упрощениями) согласно их спецификации в стандарте [7].
Процедура KeyGen выполняет следующие операции:

1. Получает с помощью ГСЧ 32-байтное случайное число ξ.

2. С помощью XOF-алгоритма хеширования SHAKE256 вычисляет значения переменных ρ (32 байта), ρ’ (64 байта) и K (32 байта) на основе следующей последовательности входных данных:
   ·  случайного числа ξ;
   ·  параметров алгоритма k и l размером по 1 байту (эти значения являются основными параметрами алгоритма, определяющими размерности ряда данных, используемых алгоритмом, включая размеры секретного и открытого ключей и ЭП; важность данных параметров подчеркивает тот факт, что их значения вынесены в наименования вариантов алгоритма: ML-DSA-kl).

3. Формируется матрица A размерности k × l, элементы которой вычисляются на основе значения ρ и их индексов; каждый элемент матрицы a_ij принадлежит кольцу T_q, каждый из элементов которого представляет собой массив из 256 элементов кольца ℤ_q, где q – простое число, равное 8380417.

4. На основе значения ρ’ вычисляются элементы секретного ключа – векторы s₁ (размера l) и s₂ (размера k), каждый из которых содержит значения, лежащие в небольшом интервале [-η, η], где η – параметр алгоритма.

5. Вычисляется вектор t путем умножения матрицы A на вектор s₁ и прибавления к результату вектора s₂.

6. Вектор t поэлементно разбивается на старшую (t₁) и младшую (t₀) части, связанные соотношением t[i] ≡ t₁[i] * 2^d + t₀[i], где d = 13 – константа, обозначающая количество отбрасываемых младших бит элементов вектора t при их округлении.

7. Открытый ключ pk представляет собой конкатенацию значения ρ и элементов вектора t₁, преобразованных в байтовую последовательность.

8. Вычисляется 64-байтный хеш-код tr от значения открытого ключа pk с помощью алгоритма SHAKE256.

9. Секретный ключ sk представляет собой конкатенацию значений и векторов ρ, K, tr, s₁, s₂, t₀, преобразованных в байтовую последовательность.

Таким образом, секретный ключ алгоритма ML-DSA состоит из следующего набора компонентов:

• открытого псевдослучайного значения ρ;

• секретных компонентов: псевдослучайного числа K и векторов s₁ и s₂;

• хеш-кода открытого ключа tr;

• вектора t₀, содержащего младшие биты элементов вектора t.

Открытый ключ в своем составе содержит значение ρ и округленные элементы вектора t – вектор t₁.
Процедура вычисления ЭП (Sign) в алгоритме ML-DSA выполняется следующим образом:

1. С ГСЧ запрашивается случайное число rnd размером 32 байта. Если применяется вариант без использования случайных чисел в процессе вычисления подписи (см. выше), то в качестве rnd используется строка из 32 нулевых байт.

2. Формируется подписываемая байтовая последовательность M’, состоящая из конкатенации следующих данных:
   ·  нулевого байта;
   ·  байта, содержащего размер контекста |ctx| в байтах; в качестве контекста ctx может использоваться произвольная (зависящая от приложения) информация размером от 0 до 255 байт включительно; если контекст не используется, то в качестве ctx берется пустая строка;
   ·  контекста при его наличии;
   ·  подписываемого сообщения произвольного размера M.

3. Из значения секретного ключа sk извлекаются векторы s₁, s₂ и t₀.

4. Из извлеченного из секретного ключа значения ρ аналогичным процедуре KeyGen образом вычисляется матрица A (как и в алгоритме ML-KEM, данная матрица может считаться частью секретного и открытого ключей, но в этом случае их размер значительно увеличится).

5. С помощью алгоритма хеширования SHAKE256 вычисляется 64-байтное хеш-значение μ от результата конкатенации следующих данных:
   ·  извлеченного из секретного ключа значения tr;
   ·  последовательности M’.

6. Вычисляется псевдослучайная 64-байтная величина ρ’’ путем хеширования функцией SHAKE256 конкатенации значений K (извлечено из секретного ключа), rnd и μ.

7. Далее в цикле выполняется попытка вычисления ЭП (основным критерием корректности вычисления ЭП является отсутствие в значении ЭП криптографически значимой утечки информации о значении секретного ключа – как это проверяется, описано далее) с помощью следующей последовательности действий:
   ·  на основе значения ρ’’ и счетчика цикла κ (изначально счетчик обнулен) вычисляется вектор y, состоящий из l элементов кольца R_q = ℤ_q[X]/(X²⁵⁶ + 1);
   ·  вычисляется вектор w путем умножения матрицы A на вектор y;
   ·  поэлементно формируется вектор w₁, каждый элемент которого содержит старшие биты вектора w: w_[i] ≡ w_1[i] * 2_γ2 + w_0[i] mod q, где γ₂ – параметр алгоритма; младшая часть отбрасывается;
   ·  вычисляется хеш-значение ç размером λ/4 байт (λ – параметр алгоритма, определяющий стойкость к коллизиям) путем применения алгоритма SHAKE256 к результату конкатенации значения μ и вектора w₁, преобразованного в байтовую строку;
   ·  на основе значения ç с использованием преобразований алгоритма SHAKE256 формируется значение c ∈ R_q, содержащее коэффициенты 0 или ±1 с весом Хемминга (определяется количеством ненулевых коэффициентов) (параметр алгоритма) не более 64;
   ·  вычисляются векторы cs₁ и cs₂ в результате умножения, соответственно, векторов s₁ и s₂ на значение c;
   ·  вычисляется вектор z путем сложения векторов y и cs₁;
   ·  вычисляется вектор r₀, элементы которого состоят из младших бит элементов разности векторов w и cs₂ (используется то же соотношение, что было приведено ранее для векторов w и w₁, только для выделения младших бит, а не старших);
   ·  полученные векторы z и r₀ проверяются на соответствие критерию минимальности (для предотвращения утечки информации о значении секретного ключа): если норма вектора z не меньше разности γ₁ - β или норма вектора r₀ не меньше разности γ₂ - β (γ₁ и β также являются параметрами алгоритма), то счетчик цикла κ увеличивается на значение l и выполняется следующая попытка генерации ЭП;
   ·  в случае прохождения указанного критерия попытка генерации ЭП продолжается, вычисляется вектор ct₀ путем умножения вектора t₀ на значение c;
   ·  вычисляется вектор «подсказки» h, каждый элемент которого показывает, меняет ли прибавление элемента первого вектора старшие биты элемента второго вектора; в качестве первого вектора в данной операции используется вектор -ct₀, в качестве второго – вектор w - cs₂ + ct₀;
   ·  выполняется еще одна проверка соответствия критерию минимальности: если норма вектора ct₀ превышает γ2 или количество ненулевых элементов в векторе h превышает значение ω (параметр алгоритма), то счетчик цикла κ увеличивается на значение l и выполняется следующая попытка генерации ЭП;
   ·  если данный критерий пройден, то цикл завершается успешно (стоит отметить, что максимальное значение счетчика κ может быть ограничено, при превышении ограничения ЭП не считается сгенерированной, процедура завершается с признаком ошибки).

8. Результирующей ЭП σ является байтовая последовательность, в которой закодировано следующее:

   ·  значение ç;
   ·  вектор z mod^± q, где mod^± q означает приведение к диапазону от -q/2 до q/2;
   ·  вектор подсказки h.

Поскольку при вычислении значения подписи использовался вектор w1, представляющий собой результат округления элементов вектора w, вектор подсказки h необходим для ее проверки. Он позволяет восстановить исходный вектор из округленного, как будет показано далее.
При использовании внешнего алгоритма хеширования процесс вычисления ЭП несколько меняется – на шаге 2 описанной выше последовательности действий изменяется порядок вычисления последовательности M’, которая в этом случае будет являться результатом конкатенации следующих данных:
·  байта со значением 1;
·  байта, содержащего размер контекста |ctx| в байтах;
·  контекста при его наличии;
·  11-байтного идентификатора (OID) используемого алгоритма хеширования; алгоритм должен быть стандартизован (в США);
·  хеш-кода H подписываемого сообщения M, вычисленного данным алгоритмом хеширования.

Остальные этапы процедуры вычисления ЭП не меняются. Процедура проверки ЭП (Verify) состоит в выполнении следующих действий:

1. Таким же образом, как и при вычислении ЭП, выполняется формирование байтовой последовательности M’ из подписываемого сообщения M и контекста ctx (и его размера) при его наличии. Это справедливо как для основной версии алгоритма, так и для версии с использованием внешнего алгоритма хеширования.

2. Из значения открытого ключа pk извлекаются значение ρ и вектор t₁.

3. Из значения ЭП σ извлекаются значение ç и векторы z и h.

4. Из значения ρ аналогичным процедуре KeyGen образом вычисляется матрица A.

5. Вычисляется хеш-код открытого ключа tr с помощью функции SHAKE256.

6. Аналогично процедуре Sign вычисляется хеш-код μ от результата конкатенации хеш-кода tr и последовательности M’.

7. Аналогично процедуре Sign на основе значения ç формируется значение c.

8. Вычисляется приблизительное проверочное значение w’_approx = Az - ct₁ * 2^d (напомню, что умножение элементов вектора t₁ на 2^d дает в результате округленные значения элементов вектора t, поскольку t₁ содержит их старшие биты).

9. С помощью элементов вектора h (который содержит информацию о требуемой коррекции (модификации значений старших битов) элементов вектора w’_approx) из вектора w’_approx вычисляется вектор w₁’.

10. Вычисляется λ/4-байтное проверочное значение ç’ как результат хеширования функцией SHAKE256 конкатенации значения μ и вектора w₁’, преобразованного в байтовую строку.

11. Если значения ç и ç’ являются идентичными и норма вектора z меньше γ₁ - β, то ЭП признается верной. В противном случае ЭП неверна.

Как было сказано выше, существует три основных варианта алгоритма ML-DSA с фиксированным набором параметров. Значения параметров для вариантов алгоритма приведены в таблице:

Назначение параметров алгоритма было описано ранее при описании его процедур. Размеры секретного и открытого ключей и ЭП алгоритма ML-DSA в байтах: 

Стандарт FIPS 204 не содержит рекомендаций, какой из данных вариантов является приоритетным для применения: варианты ML-DSA должны применяться в зависимости от требуемого уровня стойкости.

Алгоритм электронной подписи SLH-DSA (FIPS 205)

Алгоритм ЭП SLH-DSA (Stateless Hash-Based Digital Signature Algorithm – алгоритм электронной подписи на основе хеширования без сохранения состояния) описан в стандарте FIPS 205 [8].

SLH-DSA основывается на концепции применения одноразовых электронных подписей, в качестве которых используется модифицированная одноразовая электронная подпись Винтерница WOTS⁺ (Winternitz One Time Signature) и схема электронной подписи с ограниченным количеством применений FORS (Forest of Random Subsets) совместно с многоуровневой древовидной структурой расширенной одноразовой подписи Меркля XMSS (Extended Merkle Signature Scheme). Общая структура алгоритма приведена на рисунке:

Аналогично алгоритму ML-DSA, SLH-DSA является параметризуемым и имеет несколько вариантов с фиксированными параметрами (см. далее), а также подварианты с детерминированным вычислением ЭП и с внешним хешированием.

Рассмотрим основные операции (со значительными упрощениями) данного алгоритма согласно его описанию в стандарте [8].

Процедура генерации пары ключей KeyGen состоит в выполнении следующей последовательности действий:

1. С помощью ГСЧ генерируются случайные числа – компоненты ключей SK.seed, SK.prf и PK.seed, каждое из которых имеет размер n байт, где n – основной параметр алгоритма, определяющий уровень безопасности.

2. Рекурсивно (снизу вверх) строится дерево XMSS:
   
   ·  на нижнем уровне формируются листья дерева, содержащие открытые ключи одноразовой ЭП WOTS⁺ : секретные ключи ЭП WOTS⁺ формируются в виде цепочки хеш-значений, полученных в результате хеширования значений PK.seed, SK.seed и уникального адреса узла, после чего из секретных ключей вычисляются открытые ключи, тогда как сами секретные ключи отбрасываются;
   
   ·  на каждом из последующих уровней формируется узел дерева, содержащий n-байтное хеш-значение, вычисленное с помощью хеш-функции H (в качестве данной хеш-функции могут использоваться алгоритмы SHA-256, SHA-512 или SHAKE256 в зависимости от конкретного варианта алгоритма; SHA-256 и SHA-512 представляют собой функции семейства SHA-2, описанного в стандарте FIPS 180 [10], результат хеширования при их использовании при необходимости усекается до n байт), в качестве входных данных которой используется результат конкатенации значения PK.seed, адреса узла и содержимого левого и правого дочерних узлов (или листьев) данного узла;
   
   ·  высота каждого дерева определяется параметром алгоритма h’.

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

4. Секретным ключом SK является результат конкатенации следующих значений, каждое из которых имеет размер n байт: SK.seed, SK.prf, PK.seed и PK.root.

5. Открытый ключ PK представляет собой результат конкатенации значений PK.seed и PK.root.

Таким образом, процедура генерации пары ключей получает ряд случайных значений, на их основе вычисляет пары ключей одноразовой ЭП WOTS^₊, заполняет листья дерева значениями открытых ключей WOTS⁺, формирует структуру дерева XMSS, корневой элемент которого становится компонентом открытого ключа алгоритма SLH-DSA, после чего из полученных значений формирует пару ключей данного алгоритма: секретный ключ размером 2n байт и открытый ключ размером 4n байт. Процедура вычисления ЭП выполняет следующую последовательность операций:

1. Генерируется с помощью ГСЧ случайное n-байтное значение addrnd; для детерминированного варианта вычисления ЭП данное значение с ГСЧ не запрашивается, а принимается равным значению PK.seed.

2. Формируется подписываемая байтовая последовательность M’, состоящая из конкатенации следующих данных:
   
   ·  нулевого байта;
   ·  байта, содержащего размер контекста |ctx| в байтах;
   ·  контекста при его наличии;
   ·  подписываемого сообщения произвольного размера M.

3. Вычисляется n-байтный случайный компонент подписи R как результат применения хеш-функции SHAKE256 или надстройки над алгоритмами хеширования HMAC (Hash-Based Message Authentication Code) [11] при использовании хеш-функций SHA-256 или SHA-512; хешируемым сообщением в данном случае является конкатенация значений SK.prf, addrnd и M’.

4. Вычисляется m-байтовое (m – параметр алгоритма) хеш-значение digest путем применения хеш-функции SHAKE256 или надстройки над алгоритмами хеширования MGF (Mask Generation Function) в случае использования хеш-функции SHA-256 или SHA-512; хешируемым сообщением в данном случае является конкатенация значений R, PK.seed, PK.root и M’.

5. Из значения digest производится формирование трех следующих компонентов:
   
   ·  значения md, используемого в дальнейшем в качестве хеш-кода подписываемого сообщения;
   ·  значения idx_tree, по которому выбирается конкретное дерево;
   ·  значения idx_leaf, по которому выбирается конкретный лист дерева.

6. Вычисляется FORS-компонент ЭП SIG_FORS на основе значений md, SK.seed и PK.seed:
   
   ·   значение md разбивается на k индексов по a бит, где k и a – параметры алгоритма, из них k определяет количество деревьев леса FORS;
   ·   на основе каждого из этих значений формируется фрагмент SIG_FORS, который также дополняется «аутентифицирующим путем» данного фрагмента - совокупностью данных, необходимых для достраивания дерева FORS, которому принадлежит фрагмент (см. рисунок далее).

7. Вычисляется открытый ключ PK_FORS путем построения подмножества из k деревьев леса FORS, ссылки на которые содержатся в SIG_FORS с использованием также содержащихся в SIG_FORS путей аутентификации; PK_FORS представляет собой результат хеширования корневых элементов сформированных деревьев FORS.

8. На основе значений PK_FORS, SK.seed, PK.seed, idx_tree и idx_leaf вычисляется HT-компонент ЭП SIG_HT:
   
   ·   данный компонент содержит в себе последовательность из d (параметр алгоритма) компонентов SIG_XMSS – по числу уровней гипердерева;
   ·   на нижнем уровне подписывается открытый ключ FORS, после чего конкретное из деревьев XMSS достраивается с получением корневого ключа PK данного дерева;
   ·   на последующих уровнях подписывается корневой ключ PK нижележащего дерева, после чего строится дерево верхнего уровня и процесс повторяется.

9. Вычисленная с помощью данной процедуры ЭП представляет собой результат конкатенации значений R, SIG_FORS и SIG_HT. Размер ЭП определяется значениями параметров алгоритма n, k, a, h, d, где параметр h = d * h’ определяет общую высоту гипердерева.

При использовании для вычисления ЭП внешнего алгоритма хеширования меняется порядок формирования значения M’ из M, что выполняется аналогично описанному ранее порядку формирования M’ при использовании внешнего алгоритма хеширования для алгоритма ЭП ML-DSA. Стоит отметить, что стандарт FIPS 205 не рекомендует использовать один и тот же секретный ключ в различных подвариантах алгоритма (т. е. для случайного и детерминированного вычисления ЭП, а также с внутренним и внешним хешированием).

Процесс проверки ЭП алгоритмом SLH-DSA выглядит следующим образом:

1. Из сообщения и контекста (при его наличии) формируется байтовая строка M’ аналогично ее формированию при вычислении ЭП.

2. Из ЭП извлекаются ее компоненты: R, SIG_FORS и SIG_HT.

3. Аналогично процессу генерации ЭП вычисляется хеш-значение digest путем хеширования результата конкатенации значений R, PK.seed, PK.root и M’ (PK.seed и PK.root извлекаются из открытого ключа).

4. Аналогично процессу генерации ЭП из значения digest извлекаются хеш-код md и индексы дерева и листа idx_tree и idx_leaf соответственно.

5. С использованием разложения значения md на индексы (аналогично процессу генерации ЭП), значения PK.seed, а также извлеченной из SIG_FORS информации, соответствующей определенным листьям деревьев FORS и путям их аутентификации, формируется необходимое подмножество деревьев FORS и вычисляется значение PK’_FORS как результат хеширования корневых элементов сформированных деревьев FORS.

6. На основе компонента ЭП SIG_HT вычисляется значение PK’.root:
   ·  из SIG_HT извлекаются d значений SIG_XMSS;
   ·  как и в процессе подписания, создается гипердерево, каждое из деревьев которого строится на основе соответствующего значения SIG_XMSS, в результате построения для каждого дерева формируется корневое значение;
   ·  в результате итеративного процесса вычисляется корневое значение дерева, находящегося на верхнем уровне, которое соответствует значению PK’.root.

7. Если вычисленное таким образом значение PK’.root совпадает со значением PK.root из открытого ключа, то подпись признается верной, в противном случае ЭП неверна.

Как и при вычислении ЭП, при ее проверке можно использовать внешний алгоритм хеширования. Процедура проверки в этом случае отличается тем же, что и процедура вычисления ЭП – иначе формируется байтовая последовательность M’ – см. описание процедуры генерации подписи с внешним алгоритмом хеширования для алгоритма ML-DSA.

Стандарт [8] описывает 12 вариантов алгоритма SLH-DSA: по 6 различных наборов параметров для вариантов данного алгоритма, основанных на XOF-хеш-функциях SHAKE или хеш-функциях семейства SHA-2. Стандартные наборы параметров для вариантов алгоритма SLH-DSA сведены в таблице далее; в наименовании варианта указано, какая хеш-функция в нем применяется.

Назначение параметров алгоритма было приведено ранее в описании его процедур.
Дополнительные индексы в названии каждого из вариантов (“s” или “f”) обозначают направление оптимизации конкретного варианта: с целью ускорения вычисления ЭП (“f” от “fast”) или с целью уменьшения ее размера (“s” от “small”).
Размеры ключей и ЭП стандартных вариантов алгоритма SLH-DSA:

Как видно, по сравнению с описанными ранее алгоритмами, алгоритм SLH-DSA имеет небольшие размеры ключей, но значительно больший размер ЭП.
Стандарт FIPS 205 не содержит рекомендаций, какой из данных вариантов является приоритетным для применения: варианты алгоритма SLH-DSA должны применяться в зависимости от требуемого уровня стойкости. 

Конкурс NIST по выбору постквантовых криптостандартов продолжается – что же происходит сейчас?

Помимо трех перечисленных стандартов, в настоящий момент готовится к выходу FIPS 206 (изначально выход данного стандарта ожидался в конце 2024 г. [5], но стандарт до сих пор не опубликован) – это еще один резервный стандарт на постквантовую ЭП на основе алгоритма FALCON.
При этом связанный с конкурсом проект по анализу поданных на конкурс постквантовых алгоритмов не завершен – параллельно описанному выше процессу стандартизации на основе ряда выбранных алгоритмов NIST проводит дополнительный (четвертый) раунд, в процессе которого выполняется анализ некоторых альтернативных алгоритмов-кандидатов. Это объясняется желанием создать пул из ряда резервных постквантовых криптоалгоритмов для быстрой замены ими опубликованных стандартных алгоритмов на случай, если против последних будут найдены успешные криптоаналитические атаки (подобное резервирование не производится в части традиционных криптоалгоритмов, но считается уместным для постквантовых, поскольку в большинстве случаев в их основе лежат относительно новые и недостаточно хорошо изученные преобразования, что может способствовать их неожиданному взлому) [2].
Кроме того, поскольку два из трех стандартов на постквантовые алгоритмы ЭП (FIPS 204 и будущий FIPS 206) базируются на схожих преобразованиях (а именно, на задачах, относящихся к структурированным алгебраическим решеткам), т. е. нет достаточной диверсификации подходов на случай успешных криптоаналитических атак против данных задач, а также из-за относительно больших размеров ключей и ЭП в выбранных алгоритмах, NIST посчитал, что в части ЭП цель проведенного конкурса не достигнута и в 2022 г. (уже после выбора четырех перечисленных выше алгоритмов для их стандартизации) объявил о дополнительном наборе алгоритмов ЭП для дальнейшего анализа. В 2023 г. на данный дополнительный конкурс было принято 40 алгоритмов ЭП; в октябре 2024 г. завершился первый раунд конкурса, по результатам которого было выбрано 14 алгоритмов; в настоящее время выполняется их анализ в рамках второго раунда [12].
Таким образом, по результатам четвертого раунда конкурса NIST по выбору постквантовых криптоалгоритмов и дополнительного конкурса в части алгоритмов электронной подписи можно ожидать выхода новых стандартов, описывающих альтернативные постквантовые криптоалгоритмы – в дополнение к существующим с целью резервирования против возможных успешных криптоаналитических атак в будущем.

Все три опубликованных стандарта вступили в силу 13 августа 2024 г. и «готовы к немедленному применению»; как обсуждалось в предыдущей статье, их реализацию эксперты NIST также призывают «начать немедленно, поскольку полная интеграция [новых стандартов с существующими системами] займет много времени» [5].

В августе прошлого года в документе [4] NIST анонсировал выход рекомендаций по переходу с классических стандартных криптографических алгоритмов электронной подписи и вычисления общего ключа (описанных в текущих стандартах и рекомендациях на классические криптографические алгоритмы: [13, 14] в части ЭП и [15, 16] в части вычисления общего ключа), потенциально атакуемых с помощью квантовых компьютеров с достаточными ресурсами, на постквантовые алгоритмы ЭП и KEM, описанные в перечисленных выше и ожидающихся стандартах FIPS. Драфты общих рекомендаций по переходу на постквантовые криптоалгоритмы [17] и рекомендаций в части применения алгоритмов KEM [18] уже опубликованы, в ближайшей перспективе ожидается выход их финальных версий и аналогичных рекомендаций по переходу на постквантовые алгоритмы ЭП.