Алгоритм Шора: почему его создатель не боится, что он взломает интернет

Алгоритм Шора, разработанный в 1994 году, теоретически способен взломать большинство современных систем шифрования, лежащих в основе безопасности интернета. Однако сам математик, удостоенный премии Тьюринга, не испытывает беспокойства по этому поводу. В интервью New Scientist он объяснил, почему считает угрозу преувеличенной, и рассказал о реальных сроках появления квантовых компьютеров, способных реализовать его алгоритм на практике. Эта статья разбирает суть алгоритма, причины его опасности и перспективы практической реализации.

Что такое алгоритм Шора и почему его считают опасным

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

Опасность алгоритма осознают не только специалисты. Ещё в 2016 году Агентство национальной безопасности США (NSA) начало подготовку к переходу на постквантовую криптографию. Однако сам Шор, которому сейчас 64 года, утверждает, что для практической реализации его алгоритма потребуется квантовый компьютер с миллионами кубитов, тогда как современные системы имеют лишь несколько сотен. Даже самые мощные из существующих, такие как процессор Google Sycamore, содержат всего 53 кубита, и они подвержены ошибкам.

Предыстория и контекст: от теории к практике

Идея квантовых вычислений возникла ещё в 1980-х годах, но именно алгоритм Шора стал поворотным моментом. Он показал, что квантовые компьютеры способны решать задачи, недоступные классическим. За прошедшие 30 лет прогресс в этой области был значительным: от единичных кубитов до систем с сотнями. Однако путь к созданию машины, способной взломать RSA-2048, остаётся долгим.

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

Почему алгоритм Шора не работает на современных квантовых компьютерах?

Современные квантовые процессоры, такие как IBM Osprey с 433 кубитами, всё ещё далеки от необходимого уровня. Для взлома RSA-2048, по оценкам экспертов, потребуется около 20 миллионов кубитов, причём с низким уровнем ошибок. Даже если учесть прогресс в исправлении ошибок, который позволяет использовать меньшее количество физических кубитов, речь идёт о миллионах. Кроме того, алгоритм Шора требует длительного времени когерентности — состояния, при котором кубиты сохраняют свои квантовые свойства. Современные системы могут удерживать когерентность лишь доли секунды, тогда как для выполнения алгоритма нужны минуты.

Технические подробности: как устроен алгоритм Шора

Алгоритм Шора использует два ключевых свойства квантовой механики: суперпозицию и интерференцию. Вместо перебора всех возможных множителей, как это делают классические алгоритмы, квантовый компьютер может рассматривать их одновременно. Затем с помощью квантового преобразования Фурье он находит период функции, связанной с разложением числа. Этот период даёт информацию о простых множителях. Вся сложность заключается в том, чтобы выполнить эти операции с достаточной точностью и без потери квантового состояния.

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

Кого затронет и как: разработчики, бизнес и пользователи

Для разработчиков и IT-специалистов угроза алгоритма Шора означает необходимость перехода на постквантовую криптографию. Уже сейчас NIST (Национальный институт стандартов и технологий США) проводит конкурс на стандарты шифрования, устойчивые к квантовым атакам. Ожидается, что первые стандарты будут утверждены в 2024 году.

Бизнес, особенно в финансовом и государственном секторах, должен заранее обновить системы безопасности. Для обычных пользователей последствия могут быть серьёзными: взлом банковских транзакций, переписки, паролей. Однако Шор подчёркивает, что до этого ещё далеко, и паниковать не стоит.

В России и странах СНГ также ведётся работа в этом направлении. Центр квантовых технологий МГУ и другие организации разрабатывают отечественные квантовые компьютеры и алгоритмы. Пока что они не достигли уровня, необходимого для взлома шифрования, но прогресс есть.

Что будет дальше: прогнозы и сроки

По оценкам Шора, практическая реализация его алгоритма может произойти через 20–30 лет. Многие эксперты согласны, что ранее 2040 года квантовый компьютер с миллионами кубитов вряд ли появится. Однако прогресс в области исправления ошибок и новых материалов (например, сверхпроводников) может ускорить процесс.

Главный вызов — масштабирование. Компании, такие как Google, IBM и IonQ, работают над увеличением числа кубитов и улучшением их качества. Параллельно развиваются квантовые алгоритмы для других задач, не связанных со взломом шифрования, например, для моделирования молекул в химии и материаловедении.

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

Итог

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