Мир криптографии постепенно готовится к#nbsp;приходу квантовых вычислений, где вместо двоичной логики используются кубиты. Предполагается, что именно криптография станет одним из#nbsp;первых применений квантовых компьютеров.
Проблема в#nbsp;том, что современные алгоритмы вроде RSA и#nbsp;Диффи-Хеллмана (в#nbsp;том числе на#nbsp;эллиптических кривых) не#nbsp;способны противостоять квантовым атакам. Поэтому в#nbsp;июле 2022 года Национальный институт стандартов и#nbsp;технологий США (NIST) опубликовал набор алгоритмов шифрования, потенциально способных противостоять взлому на#nbsp;квантовых компьютерах#nbsp;— так называемые «постквантовые шифры».
Один из#nbsp;«постквантовых» шифров сразу взломали. Но#nbsp;самое интересное#nbsp;— метод, который применили исследователи.
Алгоритм SIKE
В#nbsp;июле 2022 года после многоступенчатого отбора NIST определил оптимальный универсальный алгоритм CRYSTALS-Kyber и#nbsp;ещё четыре алгоритма общего назначения BIKE, Classic McEliece, HQC и SIKE, которые требуют доработки.
NIST предложил исследователям проверить опубликованные алгоритмы на#nbsp;наличие уязвимостей с вознаграждением $#nbsp;50 тыс. за#nbsp;удачный взлом.
Алгоритм SIKE базируется на#nbsp;суперсингулярной изогении, то#nbsp;есть кружении в суперсингулярном изогенном графе. Основу SIKE составляет протокол под названием SIDH (Supersingular Isogeny Diffie-Hellman).
Исследователи из#nbsp;Католического университета в#nbsp;Лёвене (Бельгия) довольно быстро взломали алгоритм SIKE, за#nbsp;что получили заслуженную награду (об#nbsp;этом упоминали на#nbsp;Хабре в#nbsp;августе 2022 года).
Для#nbsp;нахождения секретного ключа понадобилось задействовать всего одно ядро старенького процессора Xeon E5−2630v2 на#nbsp;тактовой частоте 2,60 ГГц. Вычисление заняло менее часа.
Но#nbsp;более интересны подробности этого взлома, которые можно почитать в#nbsp;кратком комментарии профессора математики Стивена Гэлбрейта, пресс-релизе Королевского университета Канады и научной статье самих криптографов Воутера Кастрика (Wouter Castryck) и#nbsp;Томаса Декру (Thomas Decru).
Теорема 1997 года
Уязвимым местом шифра SIKE оказалась математическая теорема, вероятно, не#nbsp;знакомая авторам шифра и#nbsp;составителям конкурса NIST. Это научная статья д-ра Эрнста Кани от#nbsp;1997 года. Данная теорема связана с#nbsp;абстрактным манипулированием математическими объектами для#nbsp;исследования их#nbsp;различных свойств.
В#nbsp;теореме Кани обсуждается процесс «склеивания» двух эллиптических кривых#nbsp;— и#nbsp;при каких условиях эта процедура может дать сбой. Собственно, один из#nbsp;описанных в#nbsp;статье вариантов сбоя использовался в#nbsp;реализации SIKE, что дало естественный путь к#nbsp;взлому этого алгоритма с#nbsp;помощью «адаптивной атаки GPST», описанной в#nbsp;статье «О#nbsp;безопасности криптосистем с#nbsp;суперсингулярной изогенией» (2016), которая разработана на#nbsp;основе вышеупомянутой работы 1997 года.
В#nbsp;августе 2022 года соавтор статьи о#nbsp;GPST профессор Гэлбрейт пояснил: ключевая уязвимость SIKE состоит в#nbsp;том, что SIDH вычисляет изогению не#nbsp;напрямую, а#nbsp;через вспомогательные точки, причём степень изогении известна. Таким образом, для#nbsp;атаки можно применять готовый математический аппарат, разработанный в#nbsp;1997 году.
Как и#nbsp;GPST, атака на#nbsp;SIKE просто определяет промежуточные кривые между базовой кривой и#nbsp;конечным результатом шифрования, то#nbsp;есть в#nbsp;конечном итоге определяет закрытый ключ. «Один из#nbsp;соавторов алгоритма SIKE выразил удивление по#nbsp;поводу того, что кривые второго порядка можно использовать для#nbsp;получения информации об#nbsp;эллиптических кривых. Но#nbsp;именно такой была наша первоначальная стратегия в#nbsp;1980-х и#nbsp;1990-х годах (и#nbsp;после)»,#nbsp;— сказал доктор Кани в комментарии для#nbsp;пресс-службы университета.
Успешный взлом SIKE доказывает, что он#nbsp;не#nbsp;может быть надёжным средством шифрования, сужая поле возможных кандидатов для#nbsp;технологий постквантового шифрования. Эта история ещё раз демонстрирует силу и#nbsp;мощь глобального научного сообщества, которое действует как единое целое и#nbsp;движет вперёд технический прогресс с#nbsp;неизбежным постоянством.
Важность теоретической науки
Математическая теорема Кани 1997 года#nbsp;— чисто теоретическая работа, при написании которой автор вряд#nbsp;ли предвидел возможные практические применения. В#nbsp;этом нет ничего удивительного. И#nbsp;сейчас учёные в#nbsp;области теоретической, фундаментальной физики и#nbsp;математики не#nbsp;могут представить, для#nbsp;каких реальных приборов будут использоваться их#nbsp;формулы через 100, 1000 или 10 000 лет.
Например, французский математик Пьер Ферма в#nbsp;1637 году во#nbsp;время факторизации больших чисел сформулировал некоторую любопытную теорему. И#nbsp;только в#nbsp;1978 было найдено её#nbsp;применение в#nbsp;криптографии.
Все методы шифрования данных#nbsp;— это математика. Поэтому и#nbsp;новейшие системы постквантового шифрования тоже основаны на#nbsp;научных достижениях прошлых веков.