Как стать автором
Обновить

Шор как угроза современной криптографии

Время на прочтение 5 мин
Количество просмотров 21K

Привет, Хабр!

В настоящее время, как в известной басне, ведется опасное соревнование «черепахи и зайца» между квантовыми вычислениями и классической криптографией. Последняя же защищает Интернет, регистры блокчейнов, средства коммуникации и многое другое. Не похоже, что медленно развивающиеся сегодня квантовые вычисления скоро поймают классическую криптографию, но предупреждение в басне всё равно уместно.

Квантовые компьютеры обладают неограниченным потенциалом и особыми талантами — векторами атаки, такими как алгоритмы Шора и Гровера, которые могут взломать криптографию. Причина, по которой эти двое еще не закончили гонку, заключается в том, что все необходимые вычисления на обычных компьютерах могут занять годы. Но многие ожидают, что это изменится по мере роста масштабов и скорости квантовых компьютеров.

Проблема Y2Q

Исследователи придумали термин, обозначающий момент, когда "черепаха" будет проходить мимо "зайца". Это год Y2Q, когда возможности квантового взлома кода станут угрозой существованию классической криптографии. Когда это произойдет, остается только догадываться, но вопрос о том, произойдет ли это, для многих уже решен. В 2018 году в отчете Национальной академии наук, инженерии и медицины США (NASEM) было предсказано, что мощный квантовый компьютер, использующий алгоритм Шора, сможет взломать 1024-битную реализацию шифрования RSA менее чем за 24 часа.

Математик Питер Шор, ответственный за один из алгоритмов, в конце 2020 года добавил свое собственное предупреждение: «Я думаю, что единственным препятствием для замены RSA [криптосистемы с открытым ключом] на безопасную постквантовую криптосистему будет сила воли и время программирования... Если мы будем ждать слишком долго, будет слишком поздно».

В конце 2018 года редакторы журнала Nature объяснили риск, связанный с продуктами блокчейн. Так, безопасность блокчейна основана на односторонних математических функциях. Их легко запустить на обычном компьютере и трудно рассчитать в обратном порядке. Например, умножить два больших простых числа легко, но найти простые множители данного произведения сложно — обычному компьютеру может потребоваться много лет, чтобы решить.

Но алгоритм Шора разработан для работы на квантовом компьютере, который может принимать число и выводить его множители за короткий промежуток времени. С математической точки зрения, это потребует логарифмического (log(N)),а не экспоненциального (exp(N))количества времени. Алгоритм Гровера также является квантовым алгоритмом, предназначенным для ускорения поиска в несортированных базах данных.

Сегодня RSA зависит от сложности, связанной с большими простыми числами. Учёные предсказывают, что в течение десяти лет квантовые компьютеры смогут вычислять односторонние функции, включая блокчейны, которые используются для защиты Интернета и финансовых транзакций. Широко распространенное одностороннее шифрование мгновенно устареет.

Алгоритм Шора

Питер Шор
Питер Шор

В этом параграфе кратко рассмотрим сам алгоритм Шора. Цель алгоритма: для нечетного составного числаNнужно найти целое числоd(строго от 1 доN),на которое делитсяN.

Алгоритм Шора состоит из следующих частей:

  • Преобразование проблемы факторизации в задачу нахождения периода. Эта часть может быть реализована классическими средствами.

  • Нахождение квантового периода с помощью квантового преобразования Фурье, которое отвечает за квантовое ускорение и использует квантовый параллелизм.

Факторизация числа
Факторизация числа

Общая последовательность действий:

INPUT (N) \rightarrow \text{Алгоритм Шора} \rightarrow OUTPUT(\text{Нетривиальный множитель } N)

Алгоритм Шора содержит несколько шагов, причём только на втором шаге требуется использование квантовых компьютеров.

  1. Выбираем любое случайное число r < Nтакое, что rи N— взаимно простые числа.

  2. Квантовый компьютер используется для определения неизвестного периода pфункции f_{r, N} (x) = r^x \text{ mod }N.

  3. Если p— нечетное целое число, возвращаемся к шагу 1. В противном случае переходим к следующему шагу.

  4. Поскольку p— четное целое число, то (r^{p/2}-1)(r^{p/2} +1) = 0 \text{ mod } N.

  5. Теперь, если значение r^{p/2} + 1 = 0 \text{ mod } N,то возвращаемся к шагу 1.

  6. Если значение r^{p/2} +1 \neq 0 \text{ mod }N,переходим к следующему шагу.

  7. Вычисляем d= gcd(r^{p/2} - 1, N).

  8. Получаем требуемое значение d.

Существующие атаки

Для примера, рассмотрим атаку, которая нацелена именно на алгоритм RSA. Суть этой атаки заключается в поиске ключа путем факторизации большого числа (алгоритм Шора для этого как раз заточен!). Если мы сможем вычислить простые числа, которые использовались для генерации конкретного ключа, то фактически получим значение этого ключа.

Итак, мы должны перебрать большой набор чисел. Это очень сложно сделать, но теперь в наших руках грозное оружие — алгоритм Шора. Если наш процесс пройдёт успешно, у нас будет возможность атаковать систему RSA. Фактически, вся сложность состоит во времени, которое нужно для перебора чисел.

По существующим оценкам учёных, при наличии квантовых компьютеров нам потребуется около 20 миллионов физических кубитов для ключа размером 2048 бит. Вы удивитесь, но даже и при таком огромном количестве кубитов нам нужно будет ждать 8 часов.

Если у нас в распоряжении не такие мощные квантовые компьютеры, то оценки показывают, что с 13436 квантовыми единицами информации мы должны будем потратить 177 дней. Сегодня мы не располагаем такой возможностью. Хорошо это или плохо? Поговорим в следующем разделе.

Перспективы развития

Адаптируя стратегию "если ты не можешь кого-то победить, присоединяйся к ним", сейчас начинается гонка за право использования тех же квантовых вычислений. Возможно, эта гонка ведётся даже за мощь "квантового Интернета", который приведёт к созданию новых, более сложных процедур шифрования. Конечная цель — постквантовая криптография.

Можно выделить несколько перспективных методов, на которых основана постквантовая криптография:

Эти подходы не являются решением на века, но способны составить большую конкуренцию квантовым протоколам взлома. Заинтересовавшиеся могут ознакомиться подробнее по ссылкам выше.


Стоит отметить, что проблема массового исчезновения информационной безопасности не нова. Шифрование, созданное немецкими военными машинами Enigma во время Второй мировой войны, в конечном итоге было взломано союзниками, но на этом криптография не закончилась. А в 1977 году в ходе публичного конкурса был нарушен современный стандарт шифрования данных (DES).

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

Не все предсказывают, что гонка завершится через несколько лет. Например, Роджер Граймс, специалист по обеспечению безопасности KnowBe4, объявил, что 2021, вероятно, станет первым публичным признанием квантового криптографического взлома, когда квантовые компьютеры будут способны взламывать традиционные криптографические ключи с открытым ключом. Как мы можем наблюдать, этого пока не случилось.

Заключение

Итак, в нашей статье мы рассмотрели опасность квантового вычисления для классического шифрования Y2Q, представили краткое описание алгоритма Шора и поговорили о перспективах развития криптографии.

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

Спасибо за внимание!

Теги:
Хабы:
+23
Комментарии 59
Комментарии Комментарии 59

Публикации

Истории

Работа

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн