Простой компьютер взломал алгоритм постквантового шифрования: справился за час

Ученые из Левенского католического университета (Нидерланды) взломали алгоритм постквантового шифрования с помощью простого компьютера. На взлом они потратили 1 ч, сообщает arstechnica.com

Национальный институт стандартов и технологий Министерства торговли США (NIST) выбрал четыре алгоритма шифрования постквантовых вычислений для замены алгоритмов, которые не могут выдержать атак квантовых компьютеров, — RSA, алгоритм Диффи-Хеллмана и алгоритм Диффи-Хеллмана на основе эллиптических кривых. Также в NIST выбрали 4 дополнительных алгоритма в качестве потенциальной замены традиционным алгоритмам. Оказалось, что один из алгоритмов "на замену", SIKE, можно взломать. Однако стоит отметить, что взломать четыре алгоритма PQC (PQC — пост-квантовая криптография), выбранных NIST в качестве утвержденных стандартов, не удалось, так как они основаны на совершенно иных математических методах.

Нидерландские исследователи Воутер Кастрик и Томас Декру применили свои математические знания и обычный одноядерный компьютер, что и помогло им одолеть SIKE. Ученые нацелили атаку на ядро алгоритма, а не пошли по пути поиска и атак уязвимостей.

Ядром алгоритма является протокол Supersingular Isogeny Diffie-Hellman (SIDH), который, как выяснилось, и является одной сплошной уязвимостью. Применив теорему "склеить и разделить" (glue-and-split) авторства математика Эрнста Кани и несколько инструментов, разработанных математиками Эвереттом Хоу, Франком Лепрево и Бьорном Пуненом, нидерландские ученые совершили адаптивную атаку GPST (GPST — Galbraith-Petit-Shani-Ti, фамилии исследователей).

Адаптивная атака GPST нацелена на так называемые "вспомогательные точки" протокола SIDH, которые заранее известны. Поэтому взломать SIKE не составило труда, используя даже "слабенький" компьютер.

Ранее Фокус писал о том, что исследователям удалось разработать более мощный квантовый компьютер из всех когда-либо созданных. Устройство работает на основе лазера, управляющего несколькими состояниями квантовых частиц одновременно, что и делает его эффективным.