Взлом шифрования с помощью квантового компьютера оказался в 20 раз проще

Квантовые компьютеры смогут взломать распространенную технологию шифрования данных, как только их мощность достигнет миллиона кубитов (квантовых битов). Хотя современные квантовые компьютеры пока далеки от таких возможностей, новая оценка в 20 раз ниже предыдущей, что говорит о том, что день взлома шифрования ближе, чем мы думали.

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

В 2019 году инженер Крейг Гидни из Google Quantum AI с соавторами показал, что алгоритм Шора может взломать ключи RSA стандартного размера (2048 бит) всего за восемь часов с помощью квантового компьютера с 20 миллионами кубитов. Владелец такого пока что гипотетического компьютера сможет проникать в почту или банковские счета, защищенные этой технологией, и потенциально получать доступ к государственным секретам.

С тех пор Гидни усовершенствовал свой метод, результатами чего поделился в статье на сервере препринтов arXiv. По новым расчетам, у квантового компьютера с менее чем миллионом шумных кубитов на взлом RSA уйдет меньше недели.

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

Это исследование стало очередным напоминанием о необходимости перехода на постквантовую криптографию, добавил математик Дастин Муди из Национального института стандартов и технологий (NIST). По его словам, NIST уже выбрал новое поколение алгоритмов шифрования, устойчивых к квантовым компьютерам: «Правительство и бизнес уже работают над переходом».

Улучшения Гидни основаны не на новой теории, а на интеграции последних достижений в компиляции квантовых алгоритмов в физические квантовые схемы, заметил Александр Киссинджер, также из Оксфорда. Число необходимых кубитов удалось сократить за счет увеличения времени вычислений — с восьми часов (в статье 2019 года) до «менее недели».

На практике за надежность RSA можно пока не переживать: квантовые компьютеры пока очень далеки от требований Гидни: текущий рекорд — чуть более 1000 кубитов. Однако Лик считает, что улучшение уровня ошибок квантовых вычислений может еще снизить необходимое число кубитов.