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

image-loader.svg

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

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

1f037357d1a7f8a7f22c97bf498dcf58.jpg

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

Проблема Y2Q

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

2b93dc38195de2a4c9a70b71e8f403c9.jpg

Математик Питер Шор, ответственный за один из алгоритмов, в конце 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.

  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) = r^p -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.

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

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

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

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

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

Заключение

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

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

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

© Habrahabr.ru