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

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 заложена очень небольшая вероятность ошибки, поэтому секреты могут не совпасть даже тогда, когда все операции выполнены верно. На практике, ошибка проявляться не должна.

Даниэль Бернштейн (Daniel J. Bernstein) опубликовал большую статью (англ.) с критикой некоторых возражений, относящихся к возможности создания универсальных квантовых компьютеров. Вообще, основной посыл статьи такой: нужно немедленно повсеместно внедрять постквантовую криптографию, потому что, исходя из анализа ситуации, не удаётся найти веских причин для уверенности в том, что АНБ уже не строит активно (или построило) квантовый компьютер, пригодный для практического криптоанализа.

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

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

I’m not saying that computation on qubits is the same as computation on random bits. When you look at the details, you see that quantum computation allows a useful extra trick, setting up interference patterns between positive and negative variables. But an argument saying “quantum computing is impossible because there are so many variables” can’t be right: it also says that your laptop is impossible.
(“Я не утверждаю, что вычисление на кубитах это то же самое, что и вычисление на случайных битах. Если посмотреть детально, то можно увидеть, что квантовое вычисление позволяет провести дополнительный полезный трюк, задав схемы интерференции между положительными и отрицательными переменными. Однако аргумент, говорящий, что “квантовые вычисления невозможны, так как там настолько много переменных”, не может быть верным, поскольку этот же аргумент говорит, что ваш ноутбук невозможен.”)

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

А тип криптосистемы ML-KEM (она же – Kyber) на русском лучше писать так: “модуль-решёточная криптография”.

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

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

“Модулярная решётка” – явно не подходит, поэтому пусть будет “модуль-решёточная”. Ведь главное тут – чтобы криптосистема не оказалась решетчатой, но от слова “решето”.

В ML-KEM (ранее – Kyber) возможен вариант, когда корректно полученные сторонами секреты не совпадут. В стандарте NIST это называется Decapsulation failure. То есть, сами криптографические примитивы, составляющие ML-KEM, срабатывают всегда – выводят 256-битное значение. Но с некоторой (чрезвычайно малой) вероятностью принимающая сторона, расшифровывающая секрет, может получить значение, не совпадающее с тем, которое отправлено. “Чрезвычайно малая вероятность” тут означает 2^(-164.8). Выглядит более чем несущественным параметром. Но рассматривать сам факт наличия такой “погрешности” можно с разных сторон.

Многие криптографические алгоритмы хороши тем, что, математически, там никакой ошибки быть не может: если шаги выполнены верно, то и результат всегда строго совпадает. Это один из фундаментальных принципов использования алгебры в криптографии: нельзя проверить все 2^256 элементов и записать их в один массив, но можно использовать обозримые свойства структуры группы, чтобы гарантировать, что результаты операций с любыми сочетаниями этих 2^256 элементов не разойдутся.

Строго говоря, и в ML-KEM упомянутая “погрешность” оказывается в ряду заданных результатов алгоритма, просто, определяется она на другом уровне. Более того, при практической реализации алгоритмов, не имеющих встроенных “погрешностей”, эти самые погрешности постоянно возникают и из-за ошибок в программах, и даже из-за ошибок в работе оборудования. Особенно, если говорить о вероятностях порядка 2^(-165) – казалось бы, тут и без всяких Rowhammer какой-нибудь залётный нейтрон может вызвать реакцию, которая переключит пару битов в модуле памяти. Нейтрон, конечно, может помешать, но это будет не то же самое, что и внесение обязательного сбоя непосредственно в логику алгоритма.

Пишут, что свежие рекомендации профильного агентства правительства Австралии требуют отказаться от современных распространённых криптосистем (ECDH, ECDSA и др.) и перейти на постквантовые криптосистемы совсем скоро – к 2030 году. Занятно, что в этих рекомендациях запрещают SHA-256 в HMAC, но оставляют AES. Это тем более странно, что отказ от SHA-256 мотивируют традиционным развитием квантовых компьютеров. При этом, конечно, ничего не сказано про алгоритмы, используемые для защиты по высшим категориям (TOP SECRET).

Нетрудно посчитать, что знаменитый 2030 год планируется уже через пять лет. С одной стороны, пять лет это очень мало. С другой стороны – пяти лет может оказаться достаточно для того, чтобы появились квантовые алгоритмы для взлома, скажем, криптосистем на кодах и решётках. (Но и квантовые алгоритмы для AES – тоже нельзя исключать.) Естественно, алгоритмы будут не менее теоретическими, чем алгоритм Шора, и смогут сработать только на “гипотетических квантовых компьютерах”, но это всё равно потребует, как минимум, пересмотра рекомендаций, а как максимум – разработки новых криптосистем. Впрочем, всегда можно просто увеличить длину ключей (как долгие годы и делается с RSA).

Поскольку браузеры, – в том числе, самый свежий Firefox, – перешли с Kyber768 на ML-KEM, я добавил на свой тестовый сервер TLS поддержку X25519MLKEM768 (не удаляя “гибриды” с Kyber768). Проверить можно при помощи новых версий браузеров Chrome и Firefox.

Кстати, немного занимательных элементов. В процессе развития постквантовой криптографии в TLS уже успели поменять “порядок байтов”. Так, в новых версиях представлений гибридных ключей – разная конкатенация массивов: в “старом” X25519Kyber768, если смотреть в сетевом порядке (так сказать, слева направо, что, конечно, математически неверно), сначала идёт ключ X25519, а потом – Kyber768; в “новом” X25519MLKEM – наоборот, сначала данные ML-KEM, а потом – X25519.

Почему это занимательно? А вот почему. Те немногие читатели dxdt.ru, которые непосредственно связаны с разработкой и реализацией ГОСТ-криптографии, совершенно точно наслышаны о технической шутке про “вращение байтов”, всплывающей в данной области постоянно и много лет. Суть вот в чём: при записи криптографических представлений, понятно, очень важен порядок байтов; так вот, в реализациях ГОСТ-криптографии, порядок байтов местами “сетевой”, а местами – в другую сторону. “Тупоконечное” и “остроконечное” представление. Так сложилось исторически. И смена направления, хоть и строго определена, но всегда происходит неожиданно. И она вовсе не так тривиальна, как можно подумать: байтовые последовательности попадают в хеш-функции; координаты точек – записываются в файлы; и так далее, и тому подобное. Понятно, что на стойкость и свойства математических операций, как и на описание алгоритмов в спецификациях, это не влияет. Однако если две реализации “байты вертят в разные стороны”, то они между собой несовместимы. На этом направлении даже есть тесты, которые, впрочем, не всегда помогают (как и в других областях, конечно). А самый забавный вариант – это когда значение оказалось “палиндромом”.