Категорический императив кванта

Работа китайских ученых, которые заявили о принципиальном решении проблемы, связанной со взломом компьютерного шифрования — пример преждевременной сенсации

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

В свое время физики придумали квантовые компьютеры, логической единицей которых является не классический объект (бит) с состояниями «0» и «1», но квантовый — так называемый кубит. В настоящее время квантовые компьютеры реализованы экспериментально; самый большой из них содержит 433 кубита.

По идее, квантовые компьютеры обладают рядом преимуществ перед классическими, которые позволяют им более быстро решать задачу разложения числа на простые множители.

Это привело бы к революции в цифровом мире — стандартные способы шифрования перестали бы быть надежными, и человечеству пришлось бы заново решать проблему безопасности переписки и банковских транзакций.

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

Алгоритм Шора. Фото: Wikimedia Commons, CC BY-SA 4.0

В конце прошлого года появилась статья китайских ученых (Бао Ян и другие), в которой предъявлен результат, который претендует на революционность: они продемонстрировали, что совсем маленький квантовый компьютер из 10 кубитов справляется с реализацией алгоритма разложения на простые множители. Речь идет не о стандартном алгоритме Шора, а о так называемом алгоритме Шнорра. Его до сих пор не реализовывали на квантовом компьютере.

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

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