dxdt.ru: занимательный интернет-журнал

В IETF и вокруг сейчас происходит небольшой технический скандал, непосредственно связанный с внедрением рекомендаций по использванию негибридных криптосистем ML-KEM в TLS.

Если очень кратко, то переход на постквантовую криптосистему ML-KEM, как единственный механизм получения сеансового секрета, может восприниматься как попытка протолкнуть в TLS некий бэкдор, который отсутствует в X25519 (сейчас X25519 используется вместе с ML-KEM, в составе гибридной криптосистемы, поэтому бэкдор в ML-KEM, для гибрида, только лишь снизит стойкость в два раза).

На днях появилась весьма занятная публикация, непосредственно касающаяся технической части этого скандала: ML-KEM Mythbusting (“Разрушение мифов об ML-KEM”, англ.). Самый удивительный аспект этой публикации в том, что автор прямо утверждает: “в ML-KEM нет бэкдора, это можно доказать”. Вообще, доказать отсутствие бэкдора в криптосистеме не просто сложно, а, часто, невозможно. Особенно, если речь идёт об асимметричных схемах инкапсуляции ключа. Видимо поэтому в публикации по ссылке утверждение заметно более размытое: делается попытка доказать, что это в параметрах ML-KEM недостаточно энтропии для того, чтобы встроить качественный бекдор. (“Качественный” тут – это доступный только держателю секретного ключа от бэкдора, как в DUAL EC DRBG.)

Что имеется в виду? Вот что: якобы, если множество вариантов параметров криптосистемы достаточно маленькое, чтобы перебрать его за обозримое время, то бэкдор там негде прятать – его можно будет обнаружить простым перебором. И вот в ML-KEM, как бы, это множество – всего 34 бита. Как бы, утверждение верное, вот только оно сильно слабее, чем предположение о бэкдоре: бэкдор может находиться непосредственно в алгоритмах, поэтому, для его обнаружения прямым перебором, нужно будет мощность множества параметров возвести в некоторую большую степень (это, примерно, как идея моделирования квантовых вычислений, когда у вас все 2^34 варианта участвуют в расчётах на каждом шаге).

Также упомянут заложенный в алгоритм отказ с ошибкой при обработке корректного шифротекста. Малая расчётная вероятность такой ошибки, – которая вероятность, кстати, прямо связана с выбором параметров, но про это ничего в публикации не сказано, – сравнивается с возможностью аппаратного сбоя: вероятность сбоя, – например, перещёлкивания битов под воздействием космического излучения, – оказывается выше, чем расчётная вероятность штатного сбоя ML-KEM. Но, всё же, аппаратный сбой в результате “пролёта нейтрона”, это совсем не то же самое, что и идеальная ошибка, заложенная прямо в алгоритм. Я, кстати, писал об этом моменте, именно в части ML-KEM.

Вообще, конечно, история, в которой ML-KEM почему-то начинают тщательно “обелять”, доказывая, что там нет бэкдора – несколько подозрительная.

Сейчас почти весь TLS-трафик в вебе, защищённый криптосистемами с постквантовой стойкостью, использует для согласования симметричных ключей гибридную криптосистему X25519MLKEM (X25519+ML-KEM). Что здесь означает термин “гибридная”? А означает он, что объединяются секреты, полученные в результате работы двух криптосистем: ML-KEM и X25519. Возможны сочетания ML-KEM с привычными вариантами ECDH – логика их устройства такая же, как и в случае X25519, поэтому дальше, в качестве примера, используется только X25519.

Итак, X25519MLKEM это не какая-то особенная криптосистема, в которой “объединяются X25519 и ML-KEM”, а всего лишь указание на параллельное использование пары криптосистем, где объединяются не криптосистемы, а их вывод – общие секреты сторон. Причём, даже это объединение выполняется самым простым способом: байты, выведенные ML-KEM, дописываются к байтам, выведенным X25519. Желаемую постквантовую стойкость обеспечивает часть ML-KEM. Минимальная практическая взаимосвязь реализаций двух криптосистем тут возможна разве что на уровне генератора (псевдо)случайных чисел и хеш-фунций (но при этом ML-KEM использует SHA-3/SHAKE256).

Таким образом, в сильно гипотетическом случае появления квантового компьютера, пригодного для криптоанализа, стойкость подобных гибридных ключей всего лишь упадёт в два раза, если считать по битовой разрядности: квантово-компьютерный атакующий сможет вычислить секрет X25519.

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

Зачем же тогда нужен гибрид? Базовая причина довольно простая: подстраховать ML-KEM на тот случай, если данная криптосистема окажется очень уязвимой для классических атак. Проще говоря, сломают именно алгоритм ML-KEM. Вообще, идея внедрения постквантовой криптографии довольно старая (это может показаться контринтуитивным, но криптосистемы с постквантовой стойкостью появились даже раньше, чем был предложен квантовый алгоритм Шора для взлома других криптосистем). Эксперименты с практическим внедрением новых криптосистем в TLS тоже проводились раньше, до появления стандарта на ту же криптосистему ML-KEM.

Например, в 2019 году Cloudflare совместно с Google Chrome испытывали сочетание SIKE и X25519 (эксперимент CECPQ2b), где постквантовую стойкость относили на счёт криптосистемы SIKE. Однако использованная версия SIKE оказалась недостаточно стойкой к классическим атакам. Так что, не будь в составе того эксперимента X25519, которая пока сохраняет свою стойкость, все TLS-сессии, установленные в рамках эксперимента с SIKE, были бы сейчас скомпрометированы постфактум (если, конечно, их кто-то записал). Квантовый компьютер для этого не потребовался бы. Такая же ситуация возможна и для ML-KEM (пусть ML-KEM и использует другой, относительно SIKE, математический аппарат).

Однако соответствующий стандарт NIST на ML-KEM никакой гибридизации с “классической” криптосистемой не требует: почему-то считается, что данная криптосистема имеет достаточную “классическую стойкость”. Тут необходимо отметить, что никто, естественно, не гарантирует стойкость ML-KEM. Оценка стойкости криптосистем в целом, и асимметричных криптосистем в частности, представляет собой дисциплину, наполненную эвристикой, предположениями и “допусками” при моделировании. С сугубо теоретической точки зрения не известно, возможны ли в принципе стойкие криптосистемы кроме единственной абсолютно стойкой (шифр Вернама), в которой длина секретного ключа равна длине сообщения. Так что для практических криптосистем лишь предлагаются оценки стойкости, взятые в некоторой модели вычислительных ресурсов. А потом появляются всё новые и новые атаки, понижающие предложенные оценки.

Конечно, именно поэтому никто не может гарантировать, что завтра не будет полностью взломана и X25519 – классическая часть гибрида с ML-KEM. Но, всё же, ML-KEM и более новая, и использует другой математический аппарат. А X25519 уже успешно и массово работает десятилетиями, а эффективных атак пока выявлено не было. Как бы там ни было, но один факт не вызывает сомнений: две независимых криптосистемы, – обычно, – лучше, чем одна.

Кроме теоретических аспектов, важны и практические: для той же ML-KEM требуется новая реализация, в которой много других алгоритмов, по сравнению с X25519 (или каким-то ещё вариантом ECDH). Новая реализация – это всегда новые дефекты и уязвимости именно в реализации, без учёта самого математического алгоритма. То есть, если использовать только ML-KEM – практически гарантированы новые критические ошибки, которых уже нет во второй части гибрида – в X25519. Более того, части ошибок реализации в X25519 просто и не может быть, потому что там другая математика.

Считается, что ML-KEM защищает от криптоанализа на гипотетическом квантовом компьютере. Очевидно, если бы подходящий квантовый компьютер появился, то использование гибридной пары с X25519 тут же потеряло бы смысл, так как эта криптосистема оказалась бы взломана. Чем не обоснование для отказа от гибрида? Но ведь этого квантового компьютера ещё нет и на горизонте! Так что обосновывать этим гипотетическим событием отказ от гибридных криптосистем на практике – несколько странно. Особенно, если учитывать, что никто не отменял классических атак на ML-KEM, и они пока что выглядят куда более реальными, чем квантовый компьютер для криптоанализа.

И тем не менее: стандарты – не требуют гибридов, а в IETF уже есть черновики RFC, описывающие “чистое” использование той же ML-KEM в TLS 1.3.

Dual EC DRBG (“Сдвоенный детерминированный генератор случайных битов на эллиптической кривой”) – нашумевшая схема генератора псевдослучайных чисел, в которой встроен (потенциальный) математический бэкдор. Несмотря на сразу же возникшие подозрения о бэкдоре, эта схема была без проблем стандартизована NIST в 2006-2007 годах и достаточно широко использовалась. Соответствующий стандарт позже официально отозван NIST.

В криптографии постоянно требуются случайные числа. Получение действительно случайных чисел сопряжено с большими проблемами, которые начинаются с того момента, что всякая попытка строго определить и гарантировать случайность значений неминуемо сталкивается с философскими трудностями, корни которых находятся в области интерпретации реальности. Поэтому на практике гарантировать случайность невозможно, но есть различные модели и допущения, позволяющие приблизиться к “строгой случайности” с точки зрения вычислительных возможностей. (Да, есть “квантовые” предложения – но они сугубо теоретические, и тоже подразумевают некоторую модель – модель “квантовой механики”.) Естественно, только из этого не следует вывод о том, что все практические случайные значения предсказуемы, но зато следует другой вывод – о допустимости использования алгоритмических генераторов псевдослучайных чисел: алгоритмов, выдающих такие последовательностей значений, которые вычислительно неотличимы от истинно случайных. (Оставим понятие “истинно случайный” – за скобками, отметив, что, – по современным представлениям, – генератор “истинно случайных” значений должен быть исключительно аппаратным.)

Важнейшей особенностью криптографических генераторов (псевдо)случайных чисел является то, что выдача генератора детерминирована – то есть, выдаваемые значения определяются внутренним состоянием. Именно этот аспект служит фундаментом для построения бекдора в Dual EC DRBG. Криптографические генераторы псевдослучайных чисел имеют важнейшее значение не только для теоретической, но и для прикладной криптографии – это краеугольный камень всех практических систем криптографической защиты.

Несмотря на то, что с точки зрения теории криптографии схема, о которой идёт речь, предоставляет потенциальный бэкдор, её свойства можно трактовать и как инструмент “депонирования” ключей – то есть, при реализации конкретного экземпляра генератора выбираются такие параметры, что уполномоченная сторона может его “взламывать”. Однако уже сам факт того, что возможно провести в статус стандарта такую схему генератора, которая содержит механизм построения бэкдора на уровне алгоритма и описание этого бэкдора опубликовано на момент стандартизации, имеет большое историческое значение. Ещё более показательна и интересна сугубо математическая часть данного бэкдора. Настоящая статья посвящена именно математике бэкдора и в деталях объясняет то, почему он работает.

По сути, бэкдор в Dual_EC_DRBG – это реализация протокола Диффи-Хеллмана (DH) на эллиптической кривой: секретный ключ находится у стороны, контролирующей бэкдор через параметры протокола, что позволяет этой стороне получать внутреннее состояние генератора псевдослучайных чисел, наблюдая его выдачу. Знание внутреннего состояния приводит к раскрытию всей последующей выдачи генератора. При этом, математически, пользователь Dual EC DRBG неявно выполняет обмен DH с контролирующей параметры генератора стороной. Это важное свойство штатных схем построения “надёжных бэкдоров”: доступ к бэкдору должен быть только у той сторны, которая знает секретный параметр – секретный ключ. Есть и другое важное свойство: если секретный параметр не был раскрыт, то строго доказать, что бэкдор действительно встроен в конкретную реализацию – нельзя. Это не отменяет возможности тсрогого описания для механизма такого бэкдора.

Итак, в Dual EC DRBG, без знания секретного параметра раскрыть внутреннее состояние генератора вычислительно трудно, потому что базовые функции протокола – односторонние. Поэтому, если оставить за скобками секретный параметр, то протокол полностью соответствует общепринятой схеме.

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

На схеме: S_n – внутренние состояния генератора; φ() – функция, преобразующая состояние S_n в S_n+1; ξ() – функция, преобразующая состояние S_n в выдачу генератора B_n на данном шаге. Биты пошаговой выдачи B_n могут конкатенироваться для получения псевдослучайной последовательности нужной длины (на схеме: RND[…]) – это типовой способ прикладного использования генератора.

Криптографические генераторы псевдослучайных чисел, помимо общих “статистических” требований к неотличимости выдачи от случайной, имеют ряд особенностей. Прежде всего – выдача должна быть необратимой. А именно: состояния S_n являются секретными параметрами, поскольку позволяют раскрыть будущую выдачу генератора. При этом выдача генератора (B_n) на каждом шаге – публична. Из этого нетрудно сделать вывод, что функции φ и ξ должны быть односторонними (однонаправленными – по значению сложно определить аргумент): если это не так, то по публично доступным данным (B_n) легко вычислить состояние генератора. В чём и состоит логический смысл описываемого бэкдора.

Почему односторонней должна быть и функция φ, которая переводит текущее внутреннее состояние в следующее? Это нужно для того, чтобы по утекшей информации о внутреннем состоянии на каком-то шаге было вычислительно сложно восстановить предыдущую выдачу генератора. Одно из базовых требований к криптографически стойким генераторам псевдослучайных чисел состоит в минимизации возможностей по раскрытию данных. Например, если есть бэкдор, позволяющий обратить ξ, то, при условии обратимости φ, взяв любую точку можно раскрыть сколько угодно данных – и предыдущие, и следующие. При этом обратимость ξ может являться следствием не бэкдора, а обычной уязвимости, в том числе, уязвимости реализации алгоритма. Предположим, эта уязвимость ξ срабатывает лишь на каких-от редких данных: соответственно, если подобрать такие данные удалось, но φ осталась необратимой, атакующий сможет вычислить только следующие состояния генератора и все предыдущие секреты останутся защищены.

Математической особенностью описываемого бэкдора является то, что он вовсе и не позволяет обратить функции ξ и φ – они остаются односторонними, но бэкдор открывает возможность простого вычисления следующего внутреннего состояния генератора по известной выдаче ξ. Это возможно потому, что алгоритм содержит дополнительную структуру, связывающую функции ξ и φ.

Псевдослучайная выдача в криптографических протоколах постоянно используется в открытом виде. Например, в открытом виде передаются векторы инициализации для схем зашифрования (GCM и пр.), псевдослучайные векторы в сообщениях TLS (поля ClientRandom и ServerRandom) и др. Поэтому нетрудно извлечь значения из трафика, сопоставить их с выдачей генератора псевдослучайных чисел, раскрыть внутреннее состояние генератора и получить последующие биты выдачи, которые, например, были использованы тем же приложением для получения секретных ключей шифров, защищающих трафик – это позволит восстановить секретные ключи и расшифровать трафик в пассивном режиме.

Dual EC DRBG работает на эллиптической кривой (над конечным полем), а в качестве односторонних функций использует умножение точки эллиптической кривой на скаляр: x∘P. Далее умножение на скаляр обозначается “блобом” (∘). Стойкость к обращению здесь основана на задаче дискретного логарифмирования: то есть, по значению Q = x∘P – вычислительно трудно найти x.

Вспомним, что умножение на скаляр – обычное для эллиптической криптографии последовательное сложение точки кривой с самой собой. Сложение – операция, которая введена на точках кривой. А именно: точкой кривой называется пара (X, Y) значений “координат”, соответствующих уравнению кривой. Здесь X и Y – это элементы подлежащего конечного поля, которое входит в параметры криптосистемы. В данном конкретном случае (например, для кривой P-256) используемое конечное поле – это вычеты, то есть “остатки” по модулю простого числа. Сложение точек P + Q = R позволяет по паре координат точки Q (X_Q, Y_Q) и паре координат точки P (X_P, Y_P) Получить координату точки R (X_R, Y_R). Скаляр – это целое число. Умножение на скаляр 3 означает, что точка складывается сама с сбой в трёх экземплярах: 3∘P = P + P + P (плюс – это сложение точек). По такому сложению точки всякой эллиптической кривой всегда образуют группу (по определению эллиптической кривой).

В алгоритме Dual EC DRBG используется две точки кривой: P и Q. Точка P – задаёт последовательность внутренних состояний. Внутреннее состояние S_n в Dual EC DRBG – целое число, которое соответствует координате X точки кривой, полученной умножением P на значение предыдущего состояния, как на скаляр. Вторая точка, Q – задаёт “ответвления”, то есть, выдачу генератора по каждому из состояний, и используется в качестве основания на каждом шаге. Ниже представлена упрощённая схема Dual EC DRBG.

На этой схеме: S_n – внутреннее состояние; для получения следующего состояния из текущего – точка P умножается на значение состояния (скаляр: S_n∘P), а координата X получившейся точки – выводится в качестве нового состояния генератора; для вывода случайных значений – вторая точка, то есть – точка Q, умножается на состояние (S_n∘Q) и выводится координата X получившейся точки. То есть, используется две одинаковых функции с разным основанием: P и Q. Раз стойкость этих функций основана на дискретном логарифмировании, то они односторонние, как и требуется.

Математический смысл бэкдора не нарушает стойкость конкретных операций с точками P и Q, он несколько хитрее и строится на в соотношении между точками P и Q. Допустим, атакующей стороне известно такое значение δ, что P = δ∘Q. Выдача генератора – это X-координата точки S_n∘Q. Атакующий находит подходящую Y-координату, подставив значение в уравнение кривой (точек с подходящими координатами будет две, алгоритм знак координаты Y не различает, но выбор точки, очевидно, не представляет труда). Таким образом атакующий легко восстанавливает точку кривой, подходящую для выдачи генератора. Далее – умножаем на δ.

δ∘(S_n∘Q) = S_n∘(δ∘Q) = S_n∘P   (1)

Рассмотрим формулу (1) подробнее. Почему она работает? Потому что скаляры – это целые числа. Из-за коммутативности группы точек кривой к скалярам применимы арифметические свойства целых чисел. В алгебре такая конструкция называется ℤ-модулем. Всякая коммутативная группа является ℤ-модулем. (Некоторые алгебраисты из-за этого даже не считают коммутативные группы “настоящими” группами.) Применительно к эллиптической кривой: 3∘P = P + P + P, а 5∘P = P + P + P + P + P. Но тогда (3+2)∘P = 5∘P = P + P + P + P + P, что следует из свойств групповой операции – просто поставим скобки: (P + P) + (P + P + P), получив, таким образом, две точки (P + P) = 2∘P и (P + P + P) = 3∘P. 3∘P + 2∘P = 5∘P. Обратите внимание, что здесь знак “плюс” используется в двух значениях: и для обозначения сложения точек кривой, и для обозначения привычного сложения в целых числах (3+2). А раз схема работает для сложения целых чисел, то она обязательно работает и для умножения целых чисел, потому что умножение в целых числах можно построить через сложение (собственно, при корректном преобразовании 0 и 1, сложение и умножение в целых числах просто могут быть переведены одно в другое, как операции). Но тогда и (3*2)∘P = (P + P) + (P + P) + (P + P) = 3∘(2∘P) = 6∘P. Что и используется в формуле (1), вместе с коммутативностью умножения в целых числах: 2 * 3 = 3 * 2.

Таким образом, атакующая сторона, которая знает секретный скаляр δ, получила значение следующего состояния генератора, вычислив Χ-координату точки S_n∘P (см. схему). Формула (1) вообще очень похожа на реализацию протокола Диффи-Хеллмана (DH) на эллиптической кривой. То есть, пользователь генератора псведослучайных чисел, можно сказать, обменялся с атакующей стороной открытыми параметрами Диффи-Хеллмана. А именно: открытый параметр атакующей стороны, статический ключ, зашит в константы протокола – P = δ∘Q, где секретный ключ – δ; открытый параметр DH пользователя – это динамическая выдача основного алгоритма – S_n∘Q, где секретный ключ S_n. “Открытые параметры DH” пользователя атакующая сторона наблюдает в трафике. Важное отличие от практического DH состоит в том, что “общий секрет” тут не должен становиться “общим” с атакующей стороной.

Итак, для внедрения бэкдора нужно выбрать такие P и Q, что P = δ∘Q. Полученные точки – это параметры конкретной реализации алгоритма, но они могут быть закреплены в стандарте (что и было сделано). Но в спецификации Dual EC DRBG для кривой P-256 в качестве точки P строго указана базовая точка группы кривой, которая используется в спецификации P-256. То есть, произвольно выбрать P нельзя. Оказывается, в том случае, если одна из точек P или Q заранее строго задана, то определить нужное значение δ можно при помощи вычисления мультипликативного обратного по модулю порядка группы точек. Важно, чтобы порядок был простым числом. Но это стандартная практика для прикладной криптографии. Например, для кривой P-256 – соответствующий порядок простой.

Чтобы получить бэкдор, нужно определить δ из P = δ∘Q. Может показаться, что если точка P зафиксирована, – соответственно, выбрать эту точку умножением какой-то точки Q на произвольный скаляр нельзя, – то требуется решить сложную задачу отыскания дискретного логарифма. Но это не так, поскольку мы всё равно можем выбрать произвольную точку Q. Чтобы согласовать точки, возьмём произвольное значение ε в интервале от 2 до порядка группы, генерируемой P, а потом возьмём δ = ε^(-1) по модулю порядка. Пусть порядок P – то есть, количество точек в используемой группе, – это простое число n. Тогда нужно найти ε * δ = 1 (mod n). (Например, 2 – обратный по умножению элемент к 4 по модулю 7, так как 2 * 4 = 1 (mod 7).) Задача нахождения мультипликативного обратного по модулю простого числа здесь вычислительно несложная. Определив δ = ε^(-1), в качестве точки Q выберем ε∘P. Тогда: δ∘Q = δ∘(ε∘P) = (ε^(-1)*ε)∘P = P. Следовательно, мы нашли такое δ, что P = δ∘Q.

То есть, если можно выбрать оба параметра – точки P и Q, – то выбираем так, что P = δ∘Q, а если одна из точек зафиксирована – выбираем δ = ε^(-1) по модулю (простого) порядка группы точек, это всегда можно сделать из-за особенностей спецификации: подлежащие группы имеют простой порядок. (Не забывайте, что в формулах выше используется два умножения – умножение точки на скаляр и умножение целых чисел (δ = ε^(-1); 1 = ε^(-1)*ε). Это работает потому, что скаляры – целые числа, но по модулю порядка группы.)

В Dual EC DRBG битовый вывод генератора, – то есть, X-координата S_n∘Q, – урезается: из него удаляются 16 старших битов. Это означает, что прямо использовать результат для вычисления координат исходной точки нельзя. Но 16 бит можно быстро перебрать, проверяя, для всех значений подряд, лежит ли на кривой точка с соответствующей X-координатой. Вычисление значений по уравнению кривой тоже не составляет проблемы – уравнение известно, а используемые там операции обязательно быстрые.

Естественно, полученная перебором точка может оказаться неверной. То есть, точка не будет являться S_n∘Q. На этом шаге “через бэкдор” у атакующего нет никакого способа проверить, что точки совпали. Но это не сильно затрудняет атаку. Значения секретного состояния нужно вычислить для всех возможных точек, которые соответствуют сокращённому битовому значению, а результат по каждой точке – сопоставить с дальнейшим анализом трафика. Например, если выдача генератора используется для получения секретного ключа, то выбрать его верное значение можно при помощи пробного расшифрования. В любом случае, анализ 2^16 числовых значений при помощи перебора не представляет здесь вычислительной проблемы.

В ранней версии стандарта NIST на Dual EC DRBG реализация использовала подмешивание дополнительной маски на каждом шаге вычисления псевдослучайных чисел. Это делало описанный бэкдор нерабочим. Однако стандарт был быстро обновлён, точка подмешивания дополнительной маски перенесена, и использование бэкдора стало снова возможным. Поэтому данная особенность здесь не рассматривается.

Проблема алгоритма Dual EC DRBG, как криптографического генератора псевдослучайных чисел, помимо низкой производительности, в том, что внутри его конструкции есть жесткая структура, зависящая от внешних параметров. Из-за алгебраических свойств эллиптических кривых, в практической реализации – точки P и Q всегда связаны. Да, иногда, если специально постараться, они могут быть получены способом, дающим некоторую гарантию того, что связующий скаляр никому не известен. Либо, P и Q может генерировать конкретный пользователь, в качестве параметра для своей локальной версии генератора. Стандарт NIST разрешал такой вариант, но не рекомендовал его, а для соответствия строгим требованиям FIPS допускались только параметры из спецификации.

(Это расширенная версия статьи, которую я недавно опубликовал на “Хабре”.)

Часто попадается популярная иллюстрация к протоколу Диффи-Хеллмана, использующая аналогию “смешивания красок”: то есть, стороны, пытающиеся получить общий секрет, смешивают исходную краску, которая известна всем, каждая со своей секретной краской, а потом обмениваются результатами по открытому каналу и смешивают со своим секретом уже результат второй стороны (см. ниже), получая, таким образом, одинаковый “цвет”. Например, в английской “Википедии” сейчас дана именно такая иллюстрация.

(Source: Wikimedia)

Оказывается, такая картинка – не самый плохой способ объяснить что-то содержательное про протокол DH “на пальцах”, пусть некоторые требования и остаются за кадром. Например, эта схема не позволяет показать, почему атакующая сторона не может “перебрать все краски” (естественно, в практическом случае с числами).

Посмотрим на основные моменты, которые подразумевает имеющаяся картинка. Во-первых, результат смешивания красок должно быть трудно обратить – важнейшее свойство для DH, который строится на “однонаправленных” функциях (об этом написано на исходной картинке). То есть, сторона, наблюдающая обмен, не может простым способом разделить краски. Вспомните, что исходная краска, – которая соответствует генератору в “настоящем” DH, – известна всем, в том числе, стороне, пытающейся взломать обмен. По условию – выделить эту краску из смешанных “цветов” оказывается вычислительно невозможно. Во-вторых, операция смешивания красок должна быть “коммутативной” (условно!) – то есть, результат не отличается от порядка подмешивания ингредиентов сторонами. Это не менее важный математический момент “настоящего” протокола, который позволяет обобщить его и перенести с классических вычетов на совсем другие структуры.

Вообще, “коммутативность” тут именно в кавычках, поскольку математическая структура несколько сложнее. Запишем операцию в виде формулы, где “*” соответствует смешиванию красок и действует слева: α * G – означает, что секретная краска α смешана с краской G (чтобы как-то обосновать “левое и правое” действие – считаем, что колер α добавлен в банку к краске G). Тогда: β * (α * G) == α * (β * G) – это то, что происходит в протоколе с красками. То есть, сторона A получает результат смешивания (β * G) и замешивает свою краску α: α * (β * G). Сторона B – наоборот. Казалось бы, должно выполняться (α * β) == (β * α), тогда работает схема. Именно так устроено в классическом DH, но с показателями степенй: (G^β)^α == (G^α)^β. Однако для протокола на красках, вообще говоря, (α * β) == (β * α) хоть и очевидно работает в “локальном” случае, но не применимо в иллюстрируемой схеме – ведь ни у стороны A, ни у стороны B нет готового состава (α * β) – они не могут его приготовить по условию “неразделимости” красок. Вариант (α * β) * G провернуть не получится, по условиям задачи: краски – это не натуральные числа. Поэтому-то “коммутативность” тут – это не настоящая коммутативность (без кавычек). Требуется именно “одинаковость” действия и краски α, и краски β на уже смешанные и подходящие краски. Это можно переписать в других обозначениях: A := α * G (подмешали α в G); B := β * G (подмешали β в G); α * B == β * A – потребовали выполнения базового свойства, необходимого для работы протокола DH на красках: β переводит A в тот же цвет, в который α переводит B.

И это вовсе не беспричинно въедливое разбирательство. Любой химик вам подтвердит, что в химии – далеко не всегда порядок подмешивания ингредиентов не влияет на результат. Формулы веществ это хорошо, но иногда нарушение порядка смешивания может так повлиять, что лабораторию придётся ремонтировать или даже строить новую.

Дело не только в химии: именно обобщение структурной особенности, которая переводит две разных “краски” строго в одну при действии разными элементами (другими “красками”) как раз и позволяет максимально обобщить и сам протокол DH, переписав его в терминах того, что в математике называется “действием группы”. Это, впрочем, отдельная история.

С “красочной” иллюстрацией к DH связан и ещё один занимательный момент. Хорошо, разобрать смешанный “цвет” на составляющие краски трудно – это по условию задачи. Но что мешает атакующему перебрать все доступные краски, подмешивая их к исходной? Результаты смешивания сравниваются с переданными в открытом виде “цветами” (они соответствуют открытым ключам DH) – если цвет совпал, то угадана секретная краска. Естественный вариант защиты: красок слишком много – перебор окажется неприемлемо долгим, а вот сторонам протокола легко выбрать одну секретную краску. Это, опять же, важный математический момент протокола: краски выбрать может быть легко, – вот тысячи, допустим, банок стоят на складских полках, – но реальный DH работает не на красках и там тоже требуется, чтобы был вычислительно простой метод равновероятного случайного выбора нужного числа (секретной “краски”). Да, в классическом варианте с целыми числами – выбрать число случайно и равновероятно не трудно. Вот только тут возникает другая проблема.

Классический вариант DH требует возведения в степень. Показатель степени является секретным ключом. Чтобы атакующая сторона не могла перебрать все показатели за обозримое время, значение должно быть большим. Но как быть стороне протокола, вычисляющей открытый параметр при помощи того же возведения в степень? Последовательно умножать генератор столько же раз, сколько и атакующий – выглядит несколько абсурдно. Хорошо, что знание показателя степени позволяет использовать быстрые методы, построенные на возведении генератора в квадрат и домножении на генератор в “нечётных” случаях: например, чтобы возвести 2 в пятую степень нужно дважды возвести 2 в квадрат и домножить на 2 – (2^2)^2 * 2, это три умножения, а не четыре, как для 2*2*2*2*2. В красках этого нет, но для любого практического воплощения протокола DH данное свойство “удвоения со сложением” необходимо – иначе легитимные стороны протокола оказываются в том же положении, что и атакующая сторона.

Недавно публиковал заметку о том, как перейти с ECDH на ML-KEM в проекте на Go: там на схемах показано, что DH можно уложить в схему KEM, что делает переход почти прозрачным. С этим связан интересный момент, касающийся свойств криптографической схемы, который в англоязычной традиции называется interactive и non-interactive (“интерактивная” и “не интерактивная”).

В ECDH (и в DH вообще) каждая из сторон может в любой момент вычислить общий секрет, если только знает открытый ключ другой стороны. То есть, это “не интерактивная” схема. Буквально: в DH, если сторона A знает открытый ключ стороны B, то A домножает этот открытый ключ на собственный секрет, который тут же выбирает независимо (но в соответствии со свои открытым ключом), и получает на своей стороне общий секрет. Никакого взаимодействия с B для этого не потребовалось. Поэтому, например, статичный открытый ключ DH может быть встроен в сертификат или ещё где-то опубликован, вне зависимости от того, в каком порядке вычисляется общий секрет сторонами. То же самое – для стороны B: этой стороне не требуется участие A для получения общего секрета (но нужен открытый ключ).

В ML-KEM ситуация другая. Прежде всего, здесь у сторон разные роли: одна сторона, – принимающая, A, – передаёт открытый ключ для инкапсуляции секрета, а другая сторона, – отправляющая, B, – инкапсулирует некий секрет в шифротекст строго при помощи этого открытого ключа. То есть, отправляющей стороне нужно получить открытый ключ принимающей стороны (как и в DH, да), потом вычислить общий секрет и шифротекст, отправить шифротекст принимающей стороне – и только тогда принимающая сторона сможет вычислить общий секрет. И сторона A никак не может вычислить общий секрет, пока B не пришлёт шифротекст (не открытый ключ – важно). Это уже существенное отличие от схемы DH: на принимающей стороне необходимо дождаться ответного сообщения от отправляющей стороны, – а это сообщение строго привязано к открытому ключу A, – и только потом можно вычислить общий секрет. Передача открытого ключа стороной B не предусмотрена. Шифротекст B тоже не может получить, пока нет открытого ключа A (в DH – может каждая сторона независимо сгенерировать открытый ключ). В ML-KEM получается, что на принимающей стороне требуется шаг, зависящий от действий отправляющей стороны. Это “интерактивная” схема.

Но главное отличие – DH можно переписать в KEM (не конкретно ML-KEM, а именно в схему), а вот произвольную схему KEM в DH – не выйдет.

ML-KEM/Kyber – быстрая криптосистема. На типовой современной аппаратуре она быстрее и чем X25519, и чем ECDH, и чем RSA. К тому же – с заявленной постквантовой стойкостью. Почему подобную криптосистему не внедрили для Интернета раньше, и в качестве основной? Можно же предположить, что вместо RSA и классического протокола Диффи-Хеллмана разработали бы что-то сразу с постквантовой стойкостью?

Публикация алгоритма Шора тут, очевидно, играет важную роль. Но криптосистемы с постквантовой стойкостью предлагались и раньше, до публикации Шора. Да, современного понятия о “постквантовой стойкости” тогда не было, но неверно и считать, что алгоритм Шора взламывает всё, что было предложено раньше этого алгоритма. Например, криптосистема McEliece, в исходном варианте, предложена в 1978 году, за 16 лет до алгоритма Шора. Но алгоритм Шора не позволяет взломать McEliece, а постквантовая стойкость может идти в качестве автоматического бонуса. Однако современные варианты McEliece стали внедрять на практике недавно, уже после того, как “постквантовый шум” набрал обороты, и как раз по причине стойкости к алгоритму Шора. Так что, пусть постквантовая стойкость и возможна без алгоритма Шора, но само по себе это ничего не гарантирует в плане внедрения криптосистем.

Кстати, что касается алгоритмов ML-KEM/Kyber, то соответствующая сложная задача (LWE) была сформулирована в 2005 году, но исходные вычислительные проблемы на решётках (SVP и др.) – тоже изучались заметно раньше, с начала 80-х годов прошлого века.

Базовые причины массового внедрения именно криптосистем, не стойких к взлому алгоритмом Шора, те же, по которым не было никаких инструментов криптографической защиты в такой важной технологии, как DNS, где криптографии не могло появиться изначально из-за стремления к строгой оптимизации ресурсов и по причине общего “экзотического статуса” алгоритмов.

Во-первых, в конце 70-х и начале 80-х годов прошлого века криптография, как ни крути, являлась даже более эзотерической областью, чем она есть сейчас. Тут, несомненно, важен вопрос регулирования и “криптовойн”. То есть, вот мы разбираем достаточно узкий вопрос: почему придумали, разработали и внедрили именно RSA с FFDH (классический вариант Диффи-Хеллмана, в конечном поле), а не что-то вроде McEliece/Kyber – но предположим, на минуточку, что регулирование в отношении “понижения стойкости” тут сыграло важную роль: в каких-то криптосистемах стойкость снижать проще, чем в других. Естественно, этот процесс напрямую связан с алгоритмическими особенностями криптосистем. В той же ML-KEM контролируемо снизить стойкость, оставаясь на уровне компьютерных систем начала 80-х годов прошлого века, несколько сложнее, чем реализовать то же самое для RSA, которая тут более “гладкая”. Речь, конечно, не идёт о планах грубо сломать криптосистему, выбрав нестойкие параметры – это не сложно сделать и для ML-KEM/Kyber. Под “контролируемым снижением” тут надо понимать такое снижение стойкости, которое выполняется из предположения, что реализация не обваливается совсем, становясь игрушечной. Конечно, это больше похоже на попытку выдать желаемое за действительное. Для процесса запрета стойкой криптографии сохранение стойкости просто не могло рассматриваться в качестве первостепенного критерия. Более того, та же исходная версия McEliece предоставляла лишь что-то около 64-битов стойкости. С другой стороны, как теперь понятно, странное и строгое регулирование внедрению конкретно RSA не помешало, но даже поспособствовало, выделив эту криптосистему при помощи административных и социальных рычагов. В момент резкого роста масштабов практического применения RSA, другие криптосистемы, ещё и не реализованные на практике, тут же оказались заведомо надолго заперты на периферии технологии, в области теоретической криптографии.

Во-вторых, использование “криптографических преобразований” для передачи данных в вычислительной сети 80-х годов не просто выглядело излишним, но и вызвало обоснованные опасения относительно неоптимального расхода драгоценной пропускной способности: тут каждый байт на счету, а предлагается нарастить данные ключами на много килобит. И когда RSA оказалась вне конкуренции, те же эллиптические криптосистемы довольно долго пробирались на уровень практики, опираясь именно на короткие, если сравнивать с RSA, ключи. Короткие ключи очень удобны. В криптосистемах типа ML-KEM – и, тем более, McElice, – ключи очень длинные. Даже если предположить, что вместо ECDSA/ECDH развивалось бы что-то подобное Kyber, то килобитные ключи однозначно бы закрыли путь к внедрению: потому что – какой смысл жертвовать так много байтов? Сейчас этот смысл полностью сводится к желаемой постквантовой стойкости.

Но если бы в качестве массовых криптосистем с 70-х годов прошлого века использовались криптосистемы, стойкие к алгоритму Шора, то этот алгоритм вряд ли стал бы настолько популярным и известным. А ведь сейчас универсальная слава алгоритма Шора является единственным локомотивом, тянущим за собой в массы популярность “квантовых компьютеров”. Сама концепция квантовых вычислений – всё равно развивалась бы, поскольку она не привязана к криптографии. Не отменяет это и интереса к задаче быстрой факторизации, которая тоже важна и без криптографии. Но если не стала бы RSA популярной, если бы использовалась вместо неё стойкая к алгоритму Шора криптосистема, то не сложилось бы и “хайпа” вокруг “квантовых компьютеров”. Получается, тут есть и некоторая “обратная причинность”: постквантовые криптосистемы не внедрили потому, что спустя три десятка лет возник “квантовый хайп”.

Странная история.

В Go 1.24 появилась типовая библиотека, реализующая ML-KEM – crypto/mlkem. На ML-KEM, если нужно задекларировать постквантовую стойкость, нетрудно перейти, например, с ECDH – “эллиптического” протокола Диффи-Хеллмана. Предположим, что у нас ECDH используется для получения общего секрета при обмене данными между микросервисами по HTTP: один из сервисов выступает HTTP-клиентом и сначала запрашивает у сервера сеансовый открытый ключ ECDH (далее – просто DH), а потом в ответном сообщении передаёт свой открытый ключ, вместе с зашифрованными данными. Данные зашифровываются симметричным шифром, а симметричный ключ вычисляется на основе общего секрета DH.

ECDH – протокол симметричный, если смотреть на уровне привычных операций: и на клиенте, и на сервере требуется две одинаковых операции – умножение на скаляр (M). Ниже приведена схема.

Здесь A, B – открытые параметры (ключи) DH. Блоком с буквой M обозначена основная операция протокола (умножение на скаляр).

А вот ML-KEM, на таком же уровне, симметрии не демонстрирует – здесь на сервере используются две операции: первая (K) – получение секрета для декапсуляции, этот секрет выводится вместе с открытым ключом (ключ инкапсуляции); вторая (D) – декапсуляция секрета из полученного от клиента шифротекста. На клиенте – работает одна операция (E), вычисление общего секрета с инкапсуляцией его в виде шифротекста. Посмотрим на схему.

(Здесь EK – открытый ключ, CT – шифротекст.)
Хорошо видно, что схема перестала быть симметричной. Однако, если немного подрегулировать “абстракцию”, то можно убрать преобразования DH на стороне клиента в блок E (инкапсуляция). Вот так:

Если A и B справа поменяются местами, то получится в точности схема ML-KEM. Собственно, часто так и делают: алгоритм Диффи-Хеллмана можно строго переписать в терминах KEM, это известно. Следовательно, нетрудно заменить в проекте, реализованном на Go, ECDH на ML-KEM: доработки оказываются минимальными. Посмотрим чуть детальнее.

Во-первых, речь вот про что. В начале сессии клиент отправляет HTTP-запрос GET на адрес API “коннектора”, где получает, кроме прочего, сессионный ключ. Ответ приходит в JSON. Ключ сервера находится в “блобе” SessionKey (Base64). Выглядит это примерно так, как в распечатке ниже. Кроме ключа в ответе есть токен, таймстемп и подпись ECDSA (на все поля), но это здесь “для антуража”, так что в данной записке не рассматривается.

type serverMessage struct {
	Id		uint64	`json:"Id"`
	Timestamp	uint64	`json:"Timestamp"`
	SessionKey	[]byte	`json:"SessionKey"`
	ECDSASig	[]byte	`json:"Sig"`
}

Во-вторых, мы всего лишь хотим получать вместо DH – ключ ML-KEM. Передавать “блоб” ключа можно в том же поле – в SessionKey.

Чтобы сгенерировать на сервере ключ, нужно сделать пару вызовов crypto/mlkem:

	var sMsg serverMessage
	var err error
[...] // В sMsg записывается принятый JSON-объект.
	dk, err := mlkem.GenerateKey768()
	if err != nil {
		fmt.Fprintf(os.Stderr, "ML-KEM error: %s\n", err)
		return
	}
	sMsg.SessionKey = append(sMsg.SessionKey, dk.EncapsulationKey().Bytes()[0:]...)
[...]

dk – это секретный ключ, он временно сохраняется на сервере в привязке к сессии.
Клиент получает общий секрет и шифротекст, записывает шифротекст в запрос, который отправляет по адресу API для обработки сессии. Формат данных клиента, предположим, такой:

type clientMessage struct {
	Id		uint64	`json:"Id"`
	Timestamp	uint64	`json:"Timestamp"`
	MLKEMCT		[]byte	`json:"MLKEMCT"`
	ECDSASig	[]byte	`json:"Sig"`
}

Здесь уже придётся поменять имя поля на MLKEMCT – раньше тут был бы открытый параметр DH клиента (SessionKey).
В коде, обработка на стороне клиента выглядит так:

	ek, err := mlkem.NewEncapsulationKey768(sMsg.MLKEMKey)
	if err != nil {
		fmt.Fprintf(os.Stderr, "ML-KEM error: %s\n", err)
		return
	}
	sharedSecret, ct := ek.Encapsulate()
	var cMsg clientMessage
	cMsg.MLKEMCT = append(cMsg.MLKEMCT, ct[0:]...)
[...]

Когда клиент пришлёт шифротекст, серверу нужно извлечь из него общий секрет, это делается так (используется сохранённый в обработчике “коннектора” dk):

	var cMsg clientMessage
	sharedSecret, err := dk.Decapsulate(cMsg.MLKEMCiphertext)
	if err != nil {
		fmt.Fprintf(os.Stderr, "ML-KEM error: %s\n", err)
		return
	}
[...]

Алгоритмически, от ECDH, реализуемого типовой библиотекой crypto/ecdh, отличается мало. Но замена даёт постквантовую стойкость и ML-KEM работает даже несколько быстрее, чем ECDH.

Может показаться, что в новой схеме сервер генерирует какой-то ключ, а клиент этот ключ использует, а в варианте с ECDH – ключи генерировали обе стороны. Однако, во-первых, секрет здесь генерируется и на стороне клиента; во-вторых, при использовании DH, секрет каждой из сторон раскрывает общий сессионный секрет – то есть, в DH достаточно знать секретный параметр сервера или клиента, чтобы из открытого параметра вычислить общий секрет, использованный для защиты трафика. Так что схема ML-KEM в этой части, на практике, не отличается (хоть и устроена иначе). При желании, можно сделать “гибрид”, как в TLS, но тогда придётся и передавать параметры DH в дополнение к ML-KEM, и хранить дополнительные ключи, пока не установлена сессия. Формально, спецификация ML-KEM не требует “гибридизации” – эта криптосистема заявлена как стойкая, поэтому, если соответствия спецификации достаточно, то – достаточно.

Реализации ML-KEM могут быть очень быстрыми, быстрее, чем X25519 – это относится к гибридам в браузерах. Например, реализация ML-KEM-768 для OpenSSL из проекта OpenQuantumSafe для инкапсуляции ключа работает в пять раз быстрее, чем X25519 в том же OpenSSL “при прочих равных” (декапсуляция – в три раза быстрее):

(openssl speed X25519 mlkem768)

           keygens/s  encaps/s  decaps/s
X25519     26646.1    12213.9   24366.2
mlkem768   53101.6    62756.0   63933.0

То есть, в гибридной схеме, где ML-KEM присоединяется к X25519, будет весьма небольшой рост вычислительных затрат по сравнению с X25519. При этом браузер Firefox, скажем, ещё и экономит время на генерирование ключей, поскольку использует один и тот же открытый параметр X25519 и в гибриде, и в отдельном варианте. Понятно, что на серверной стороне разницы тут нет – серверу так или иначе придётся для гибрида выполнить и X25519, и ML-KEM. Но всё равно это лишь небольшой дополнительный расход вычислительных мощностей.

Конечно, ML-KEM, согласно стандарту, может использоваться отдельно, тогда схема будет и работать быстрее, и постквантовую стойкость обеспечивать; гибрид используется для подстраховки – и совсем не лишней подстраховки, надо заметить. А работает ML-KEM быстро потому, что там используется NTT (“теоретико-числовое преобразование”) и, соответственно, быстрые операции с полиномами.

В продолжение недавней записки про числа в ML-KEM. Один из ключевых параметров ML-KEM, одинаковый для всех наборов, это число (модуль) 3329. Почему выбрано именно 3329? Был ли выбор “случайным” (а иногда используют проверяемые методы для выбора параметров) или это число подобрано специально?

Число 3329, обозначаемое q, в ML-KEM выбрано строго специально. И вот из каких соображений. Весь практический вычислительный смысл ML-KEM (Kyber) в преобразовании (NTT), позволяющем быстро производить арифметические операции с полиномами. Чтобы быстрые операции NTT стали возможны в ML-KEM, число q должно быть простым, а (q-1) должно делиться на 256. (Более “общо” – делиться должно на степень двойки.) 256 – это другой параметр ML-KEM, его значение продиктовано разрядностью операций (256 бит).

То есть, 3329 – простое, (3329 – 1)/256 == 13. Если эти требования не выполняются, быстрый NTT работать должным образом не будет, поскольку это не настолько универсальный алгоритм, умножать полиномы “в лоб” – очень медленно, и другие быстрые алгоритмы – тоже оказываются медленными по сравнению с NTT. Неподалёку от 3329 не так много чисел, обладающих описанными свойствами: 257, 769, 3329, 7681, 7937. При этом, нужно выбрать число поменьше (важна экономия каждого бита), но чтобы не слишком выросла вероятность получения неверного результата при работе криптосистемы. Для 257 и 769 вероятность ошибки заметно больше. Поэтому авторы алгоритма выбрали 3329.

Аккаунт на “Хабре” у меня уже больше пятнадцати лет, однако за эти годы я там написал только два комментария (сейчас уже четыре!). Подумал, что, наверное, пора и статью попробовать опубликовать – подготовил, да и опубликовал технический текст про ключи и шифротексты ML-KEM в TLS, с числами и байтами.

Нестрогое, краткое описание чисел и ключей, возникающих в ML-KEM (но без алгоритмов самой криптосистемы). Это описание, к тому же, не использует технических математических терминов, хоть и требует некоторых знаний из школьного курса алгебры (про такое описание нередко спрашивают).

ML-KEM – модуль-решёточная криптосистема с постквантовой стойкостью, носившая название Kyber до своей стандартизации. “Постквантовая стойкость” означает, что криптосистема не взламывается алгоритмом Шора на достаточно мощном универсальном квантовом компьютере (теоретическом). ML-KEM позволяет одной стороне передать другой стороне через открытый канал секрет, который становится для этих сторон общим секретом.

Схема называется KEM – Key Encapsulation Mechanism. KEM является обобщением, которое делает возможным формальный анализ стойкости криптосистем в криптологии. KEM – это не система “шифрования” и не система “цифровой подписи”. Логически, в случае ML-KEM, используется преобразование исходного значения секрета при помощи открытого ключа в шифротекст. Необходимые алгоритмические дополнения, превращающие асимметричную криптосистему в KEM, как говорится, снаружи всё равно не видны. Вполне можно упрощённо считать, что секрет здесь передаётся в зашифрованном асимметричной криптосистемой виде.

ML-KEM стандартизована для нескольких сочетаний параметров. Используемое сочетание отражается цифрами, которые приписывают к названию: ML-KEM-512, ML-KEM-768, ML-KEM-1024.

Эти числа из названия следует воспринимать как “длину секретного ключа”, выраженную в “базовых элементах” – но не в битах! Ключи в ML-KEM строятся из многочленов (полиномов), имеющих 256 коэффициентов. Многочлены образуют векторы и матрицы. То есть, элементами векторов и матриц являются многочлены, а не “отдельные числа”.

Так, ML-KEM-768 использует размерность 3 (параметр называется k), что соответствует трём многочленам или 3*256 == 768 коэффициентам. Если бы размерность ключей была бы ровно три, то взлом не составил бы труда и без всяких квантовых компьютеров. Для 768 коэффициентов – вычислительная сложность существенно выше (а квадратная матрица 3×3, являющаяся частью открытого ключа ML-KEM-768, будет, в итоге, содержать 256×9 коэффициентов: девять полиномов, каждый – по 256 коэффициентов). 256 – один из фиксированных параметров ML-KEM. Коэффициенты многочленов берутся по модулю 3329, то есть, берутся остатки от деления на 3329, поэтому коэффициенты лежат в интервале от 0 до 3328. Внутри ML-KEM используются представления, вводящие отрицательные значения, это нужно для процедур округления рациональных чисел, но на верхнеуровневую картину данный аспект не влияет. Заметьте, впрочем, что особенности округления используются при упаковке шифротекста (см. ниже). 3329 – простое число, второй фиксированный параметр ML-KEM.

Открытый ключ ML-KEM состоит из матрицы (обозначается A) и вектора (обозначается t). Однако ни матрица открытого ключа (обозначается A), ни многочлены, составляющие вектор, – не передаются в формате “как есть”: чтобы сократить количество используемых байтов в ML-KEM применяется ряд оптимизаций. Вместо матрицы – передаётся 256-битное инициализирующее значение, из которого матрица вычисляется при помощи хеш-функции и специального алгоритма. Многочлены передаются как кортежи битовых представлений коэффициентов, но биты упаковываются в байты особым образом. Так, для многочленов, входящих в открытый ключ (помимо матрицы), запись одного коэффициента (значение в интервале [0,3328]) требует не более 12 битов, биты можно объединить как биты и записать, например, два значения в три байта (если бы два значения передавались без “упаковывания”, то потребовалось бы четыре байта). При передаче коэффициентов многочленов, формирующих шифротекст, используются другие методы оптимизации, существенно сокращающие количество байтов, нужное для записи шифротекста.

Запись открытого ключа ML-KEM-768 имеет длину 1184 байта. ML-KEM-512 – 800 байтов, а ML-KEM-1024 – 1568 байтов. Шифротексты – ML-KEM-768 – 1088 байтов, ML-KEM-512 – 768 байтов, ML-KEM-1024 – 1568 байтов.

Попробуем понять, почему длина открытого ключа и широтекста совпали в ML-KEM-1024. Открытый ключ в ML-KEM это квадратная матрица и вектор. В ML-KEM-1024 параметр k, задающий размерность матрицы и вектора, равен четырём, но матрица всё равно передаётся в виде инициализирующего 256-битного значения, то есть, 32 байта, а вот вектор – состоит из 4×256 элементов (напомню, что 256 – количество коэффициентов каждого многочлена, в векторе их четыре). Получаем, для вектора, 1024 коэффициента, пара которых занимает три байта. Делим и умножаем: 1024/2×3 == 1536 байтов, плюс 32 байта, задающих матрицу, итого 1568 байтов занимает открытый ключ.

Шифротекст (то есть, “инкапсулированный” ключ) в ML-KEM состоит из вектора (обозначается u) и одного многочлена (обозначается v). В варианте параметров ML-KEM-1024, вектор – это четыре многочлена (k==4). То есть, тут всего пять многочленов, 256 коэффициентов в каждом. Однако для многочленов, составляющих шифротекст ML-KEM, применяются другие способы “сжатия”, использующие свойства округления значений коэффициентов. Это позволяет уменьшить количество битов. Поэтому запись каждого коэффициента в ML-KEM-1024 для вектора u использует 11 битов, а для многочлена v – всего 5 битов. Считаем в битах: 4×256×11 == 11264 бита или 1408 байтов; это вектор; дополнительный многочлен – 256×5 == 1280 битов или 160 байтов; итого: 1408 + 160 == 1568 байтов. Параметры сжатия для шифротекста отличаются от набора к набору: для ML-KEM-1024 это 11 и 5 битов, для ML-KEM-768/512 – 10 и 4 бита.

В спецификации ML-KEM есть ещё параметры, обозначаемые буквой η (их два). Эти параметры задают интервалы значений при случайной выборке (семплировании) коэффициентов многочленов, служащих в качестве секретного ключа и маскирующих элементов (то есть, многочлена, задающего “ошибку”, которая скрывает передаваемые данные от стороны, не знающей секретного ключа).

Общий секрет в схеме ML-KEM имеет длину 256 бит строго. Это не секретный ключ, а секрет, который согласуют стороны. При получении секрета используеются хеш-функции и значение, передаваемое внутри схемы инкапсуляции. То есть, передаётся не сам секрет, а начальное значение, из которого принимающая сторона вычисляет верный екрет только в том случае, когда прочие параметры совпали. Это позволяет сделать схему стойкой в соответствии с формальными критериями. Логика же передачи секрета такова, что каждый бит отображается в коэффициент полинома, соответствующего, таким образом, этому секрету (с точностью до функции вычисления конкретного значения). Здесь используется основной трюк ML-KEM: математическая схема позволяет передать только один элемент за одну “транзакцию”, это часто и описано в элементарных примерах, но в ML-KEM этот элемент – многочлен с 256 коэффициентами, поэтому, приняв коэффициенты за ноль и единицу, передать можно 256 бит. Для отображения в ноль и единицу криптосистема использует округление по заданному правилу: грубо говоря, если значение коэффициента меньше половины максимального, то это ноль, иначе – единица (но может быть и ошибка – см. ниже). Таким образом, длина получаемого секрета – 256 бит.

В TLS клиент передаёт свой открытый ключ серверу, сервер вычисляет общий секрет на своей стороне и передаёт параметр, нужный для вычисления общего секрета, клиенту в виде шифротекста, который вычисляет, используя открытый ключ. Клиенту известен секретный ключ, парный открытому, поэтому, получив шифротекст, клиент вычисляет общий секрет, который в большинстве случаев совпадёт с секретом, полученным сервером. В ML-KEM заложена очень небольшая вероятность ошибки, поэтому секреты могут не совпасть даже тогда, когда все операции выполнены верно. На практике, ошибка проявляться не должна.