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