Код
#новости

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

Ему понадобился всего час, чтобы сделать это.

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

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

Принцип работы алгоритма SIKE. Источник: блог Microsoft

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

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

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

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

«Решение алгоритма SIKEp434 заняло всего 62 минуты на одном ядре, а алгоритм же, по мнению NIST, должен был иметь квантовую защиту первого уровня», — рассказали исследователи из KU Leuven в своей научной статье.

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

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


Учись бесплатно:
вебинары по программированию, маркетингу и дизайну.

Участвовать
Понравилась статья?
Да

Пользуясь нашим сайтом, вы соглашаетесь с тем, что мы используем cookies 🍪

Ссылка скопирована