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

Появилась новая публикация (Daniel R. Simon), предлагающая квантовый алгоритм, взламывающий – теоретически! – криптосистемы типа ML-KEM/ML-DSA за полиномиальное время (то есть, атака предложена на задачу, лежащую в основе предположения о стойкости, в том числе, ML-KEM/ML-DSA, но подходит не только для них). Для работы алгоритма потребуется подходящий квантовый компьютер – уже этим многое сказано. Однако пока что и сама работа опубликована в статусе черновика, о чём там прямо сказано. То есть, скорее всего, – найдутся ошибки.

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

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

Что будет означать появление описания квантового алгоритма, эффективно взламывающего ML-KEM/ML-DSA и другие криптосистемы под собирательным обозначением “на решётках”? Это точно не приблизит к реальности сами универсальные квантовые компьютеры, но зато создаст вполне себе хорошее обоснование для того, чтобы либо улучшать стойкость ML-KEM/ML-DSA и прочих “решёточных” криптосистем, либо переходить на другие криптосистемы. И это будет весьма забавно: для атаки на постквантовые криптосистемы предложены новые теоретические квантовые алгоритмы, поэтому нужны суперпостквантовые криптосистемы, устойчивые и к алгоритму Шора, и к новому алгоритму “Имярек”.

Посмотрим, в общем, что там предложат. Так или иначе, но считать ML-KEM/ML-DSA неприступными – точно ещё рано.

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

Более или менее строгое определение: “ML-KEM, теоретически, обладает стойкостью к взлому при помощи алгоритма Шора”.

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

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

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

Во-вторых, никто не доказал, что невозможны другие “квантовые алгоритмы”, которые, – на подходящем, но гипотетически реализуемом, квантовом компьютере, – будут успешно и быстро взламывать ML-KEM. А если учитывать, что модели квантовых вычислений легко оперируют континуумом (синусы/косинусы и действительные числа), то, вообще говоря, не стоит делать ставку на то, что теоретический “квантовый алгоритм подбора ML-KEM” не придумают в обозримом будущем. Более того, сейчас распространено мнение, что в том самом обозримом будущем гораздо более вероятно появление практической классической атаки на ML-KEM, чем появление квантовых компьютеров, способных сломать ту же X25519 (разновидность ECDH) алгоритмом Шора. То есть, криптосистема ML-KEM может оказаться уязвима для обычных компьютеров, а X25519 и другие современные варианты ECDH – сохранят классическую стойкость.

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

Нередко приходится слышать, в качестве ответа на критику очередного “опуса”, сгенерированного ИИ, что, мол, люди тоже публикуют всякие “бесполезные наборы слов”. Поэтому процитирую весьма занятный фрагмент из недавней публикации известного британского физика Джонотана Оппенгейма (Jonathan Oppenheim). Прямо по этой же теме. Контекст – рассуждения (англ.) о научной публикации в Physics Letters B, которая, как заявлено, основана на “идее, сформулированной ИИ Chat GPT-5”. (Сама работа, при ближайшем рассмотрении экспертом, оказывается и бесполезной по основной идее, и ошибочной по содержанию; однако выяснить это непросто, откуда и популярный нынче термин AI slop – “ИИ-помои”.)

Конечно, исследователи-люди тоже выпускают “помои” (slop): лишь небольшая доля публикаций интересна. Да, нам точно нужны более высокие стандарты публикации, и мы должны писать меньше работ. Однако разница между “помоями”, созданными человеком, и “помоями” ИИ состоит в том, что “помои” от людей помогают поддерживать исследовательское сообщество. И это сообщество исследователей нужно нам: оно позволяет обучать студентов, служит “институциональной памятью”, действует как распределённая сеть знаний и коллективного чувства стиля. Это то самое большее исследовательское сообщество, что создаёт и поддерживает (sustain) великих учёных. А у “помоев”, которые производит ИИ, нет никакой выгоды, насколько я вижу.

/Of course, human researchers also produce slop – only a small percentage of papers are interesting. And yes, we should definitely have higher standards for publication, and write fewer papers. But the difference between human slop and AI slop, is that human slop helps sustain a community of researchers. And we need this community of researchers, to train students, serve as institutional memory, and act as a distributed network of knowledge and collective taste. It is this wider community of researchers which sustain the great scientists. While the slop that AIs produce have no benefit as far as I can see./

В 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 почему-то начинают тщательно “обелять”, доказывая, что там нет бэкдора – несколько подозрительная.

Кстати, в продолжение недавней заметки про то, что тип float – это не про числа, тем более, не про действительные числа. С точки зрения рекомендаций разработчику ПО.

Вообще, если получается, то никаких float и тому подобных инструментов лучше не использовать. Совсем. Тем более, в воплощении различных sin, cos и прочих. Заменять нужно таблицами целых (в смыcле int) значений и целочисленными, со строго фиксированной справа точкой, арифметическими операциями. Особенно, если речь о программировании систем управления и микроконтроллеров.

Если же не получается совсем отказаться, то есть эффективный способ правильно думать про float. Нужно переменные с типом данных float понимать как алгоритмы, и сравнение таких переменных интерпретировать как сравнение алгоритмов. Это помогает избежать многих ошибок (см. ниже).

Например, во float нет дистрибутивности. В алгоритмической интерпретации это означает, что выражения L := b*(c + d) и L := b*c + b*d – присваивают переменной L разные алгоритмы. И действительно, запись, в которой сперва вычисляется сумма (c + d), а потом результат умножается на b, это другой алгоритм, нежели вариант, когда сперва b умножается на d и b умножается на с, а потом вычисляется сумма результатов (обратите, кстати, внимание, что тут ещё и порядок играет важную роль: сначала b*c или сначала b*d? если с точки зерния параллельных вычислений эти операции могут быть выполнены “независимо” разными потоками, то с точки зрения компилятора, имеющего дело с вполне себе последовательной записью, всё может выглядеть сильно иначе – но это явно тема для другой записки).

Если не упускать этот алгоритмический момент из виду, то оступиться становится сложнее. Так, алгоритмическое восприятие float позволяет отбросить сомнения, что в двух описанных выше случаях из L можно достать разное битовое значение при одних и тех же входных переменных – алгоритмы-то там разные. Естественно, сравнивать алгоритмы сложно, но тут понятие об алгоритме – это лишь средство обобщения, мыслительный гаджет, но такой гаджет, который верно работает.

Лирическое отступление. Это раньше к компьютерными вычислениями подходили с нужной тщательностью и пониманием того, что такое преобразование погрешностей. Сейчас, оказывается, времена ИИ и LLM. Поэтому сказку сильно сократили. К сожалению, уже на практике полагают, что во float – действительные числа, “просто с погрешностью” (“просто”, да). Соответственно, получается, что конкретный математический аппарат, служащий основой проектирования алгоритмов ПО, оперирует действительными числами, синусами и косинусами – здесь всё со всем пересекается, всё максимально гладкое, а поэтому выполняются нужные равенства и теоремы существования. Потом математический аппарат прямо переносят в программный код. После чего, в один не самый ожидаемый момент, вычисления ломаются и предположим, аппарат космический улетает совсем не туда, куда предписывала гладкая и непрерывная модель с синусами и дистрибутивностью.

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

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

Важнейшей особенностью криптографических генераторов (псевдо)случайных чисел является то, что выдача генератора детерминирована внутри – то есть, выдаваемые значения определяются внутренним состоянием (пояснение от 28/01/26: это только для внешнего наблюдателя генерируемая последовательность выглядит как случайная). Именно этот аспект служит фундаментом для построения бекдора в 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 допускались только параметры из спецификации.

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

Даниэль Бернштейн (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 (английский) – различаются в трактовках, даже если смотреть узкую интерпретацию, поэтому для строгих определений всё равно потребуются уточнения.

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

В продолжение предыдущей заметки, про определение “самых жарких лет” с точностью в десятые доли градуса с целью создания вала публикаций в СМИ: понятно, что детальное описание методики в любых подобных статистических результатах имеет первоочередное значение, даже если речь о публикациях в СМИ (это, видимо, сейчас целевой показатель), однако с измерением в СМИ некоторой обобщённой “температуры на Земле” ситуация особенно занимательная.

Так, игнорируя очевидную сложность климатических изменений, следят за одним “скалярным” показателем: на гистограммах и картах в источниках (то есть, это не журналисты СМИ нарисовали) – именно некоторая “температура”, взятая даже не как интервал, с указанием градиентов и погрешностей, а в качестве одного показателя. При этом, базовый период – 1850-1900 годы. То есть, если смотреть из 2024 года, то сравниваются показатели с разницей, примерно, в 150 (!) лет. Почему вообще полтора градуса “обобщённой” “климатической” температуры в 2024 году соответствуют полутора градусам такой же “обобщённой” температуры 150 лет назад? На климатические ощущения должны влиять, хотя бы, давление, влажность и тому подобные характеристики. Непонятно. Должно бы быть объяснено в методике.

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

Конкретный термометр, как прибор, точен только в той точке, в которой только что откалиброван. Дальше уже начинаются расхождения, на которые влияют совсем “нелинейные” эффекты, в том числе, внешние, типа материала ведра, в которое набрали забортную океанскую воду для измерения (версия упоминается даже в “Википедии”). Ну или лаборант термометр уронил. А тут в одном показателе на гистограммах для СМИ балансируются и данные разных термометров для разных способов контакта с водой (и/или воздухом) за сотню лет, и данные измерений космических спутников. Между прочим, если момент про ведро кажется несколько притянутым, – на фоне-то аппаратов, “бороздящих космические просторы”, – то вспомните, что базовый период начинается в 1850 году, данные для него заведомо аппроксимированы, а вёдра в исследованиях используют и сейчас.

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

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

Провокационные заголовки “про науку” принято относить на счёт журналистов научпоп-изданий, ещё и называя “кликбейтом”. Однако вот в свежей истории про “экспериментально зафиксированное отрицательное время” оригинальный заголовок исходной работы (препринта) даже веселее, чем варианты СМИ. Заголовок гласит: “Experimental evidence that a photon can spend a negative amount of time in an atom cloud” (“Экспериментальное подтверждение того, что фотон может (can) находиться в “атомном облаке” в течение отрицательного промежутка времени”).

То есть, прямо так и сказано, если дословно: “отрицательное количество времени”. А это сильнее, чем “отрицательное время” СМИ. Как говорится: “в аудитории присутствует минус три студента; сейчас ещё трое придут – вообще никого не останется!”. Скаляр – не скаляр, но журналисту тут и придумывать не нужно ничего. Для полноты картины: конечно, тут же, прямо в аннотации работы, уточняется, что речь идёт о значениях, принимаемых переменными (параметрами времени в уравнениях, вообще говоря) в рамках некоторой интерпретации модели, стоящей за экспериментом.

Phys.Org сообщает, что авторы в курсе “споров вокруг провокационного названия работы”, но авторы также указывают, что пока ни один “серьёзный учёный” экспериментальные результаты (видимо, про “отрицательный интервал времени”) не оспаривает.

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

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

Понятно, что стандартизованная постквантовая криптосистема может оказаться уязвимой для классического криптоанализа (и, скорее всего, так и выйдет). При этом, несмотря на прижившиеся штампы в СМИ, пока никто не продемонстрировал, как именно можно было бы реализовать алгоритм Шора с полиномиальной сложностью, что называется, в железе. Потому что те немногие эксперименты с числом 15 или чуть большим числом, на которые ссылаются много лет, в принципе не позволяют проверить ключевую часть реализации алгоритма – квантовое преобразование Фурье.

Тем не менее, пробовать построить квантовый компьютер хотя бы на 2^1024 состояний – это полезно.