Одноядерный процессор взломал криптошифр, который защищал квантовые компьютеры

Что случилось

Независимые разработчики взломали криптографический алгоритм, который должен противостоять дешифровке от самых мощных квантовых компьютеров. Они сделали это на процессоре Intel Xeon и использовали всего одно ядро.

Что за алгоритм

Алгоритм называется SIKE (Supersingular Isogeny Key Encapsulation). Он прошёл до четвёртого этапа процесса стандартизации Post-Quantum Cryptography. Все эти алгоритмы должны быть устойчивыми к криптоаналитическим атакам от квантовых компьютеров. А сама стандартизация основана институтом стандартов и технологий (NIST) Министерства торговли США.

SIKE создали исследователи и инженеры из Amazon, Florida Atlantic University, Infosec Global, Microsoft Research, университета Radboud, Texas Instruments, Версальского университета и университета Ватерлоо.

Алгоритм работает по инкапсулиционному механизму, основанному на протоколах SIDH — Supersingular Isogeny Diffie-Hellman. SIKE использует арифметические операции для эллиптических кривых, которые определены на конечном поле, чтобы строить специальные карты (изогении) между такими кривыми. Или это ещё можно представить в виде графа.

Сложность алгоритмов SIDH и SIKE в том, что найти конкретные изогении между двумя эллиптическими кривыми непросто. И это становится ещё труднее из-за того, что нужно вычислять дискретные логарифмы на единичных эллиптических кривых. А это, по мнению Microsoft, должно быть сложно для классических и квантовых компьютеров.

Microsoft даже объявила награду для разработчиков за решение этой задачи. Для несложного алгоритма с меньшим количеством точек на графе компания назначила награду в 5 тысяч долларов — задачу даже решили в августе 2021 года. А за усложнённую версию алгоритма — 50 тысяч долларов, но эту задачу до недавнего времени не смогли решить.

Как взломали алгоритм

Разработчики написали код для взлома алгоритма и запустили его на процессоре Intel Xeon E5-2630v2 с частотой 2,6 ГГц. Этот процессор выпустили ещё в 2013 году на микроархитектуре Ivy Bridge.

Для двух более простых задач понадобилось всего четыре и шесть минут соответственно. Об этом исследователи тоже рассказывают в своей работе.

Ещё учёные отметили, что алгоритм SIDH можно улучшить, но для этого понадобится долго анализировать все возможные пути решения этой задачи.