Угроза шифрованию выросла в 20 раз: Квантовые компьютеры снижают планку взлома – что дальше?

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

Так что это за RSA такой и почему все всполошились?

Представьте, что у вас есть два очень больших простых числа (это те, что делятся только на себя и на единицу, помните из школы?). Перемножить их — задачка для калькулятора, даже если числа гигантские. А вот если я вам дам результат умножения и попрошу найти исходные два числа — тут-то и начнется самое интересное. Для обычного компьютера это задача из разряда «почти нерешаемых», если числа достаточно велики. Именно на этой «односторонней» сложности и построен RSA: легко зашифровать, невероятно трудно расшифровать без специального ключа.

Этот принцип лег в основу защиты банковских транзакций, электронной переписки, государственных секретов — да чего уж там, почти всего цифрового мира! Звучит надежно, не правда ли? До тех пор, пока на сцену не выходят…

Квантовые взломщики: знакомьтесь, алгоритм Шора!

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

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

От миллионов к одному: как кубиты «похудели» в 20 раз

Долгое время считалось, что для взлома стандартного 2048-битного ключа RSA с помощью алгоритма Шора потребуется квантовый компьютер с десятками миллионов кубитов. Цифра, прямо скажем, из области научной фантастики на ближайшие годы. Однако Крейг Гидни из Google Quantum AI, который уже прикладывал руку к этим расчетам в 2019 году (тогда речь шла о 20 миллионах кубитов и 8 часах работы), недавно представил обновленную оценку. И она, мягко говоря, впечатляет: для взлома того же ключа может хватить машины с менее чем миллионом кубитов!

Как это удалось? Неужели открыли какой-то новый революционный принцип? Алекс Киссинджер из Оксфорда поясняет: Гидни, скорее, собрал воедино различные наработки последних лет в области «упаковки» квантовых алгоритмов в физические схемы. Это как если бы вы долго оптимизировали программу, находя все новые и новые способы сделать ее компактнее и эффективнее.

Правда, есть нюанс. За уменьшение числа кубитов пришлось заплатить временем: если раньше говорили о 8 часах, то теперь — «менее недели». Знаете, это как с памятью на компьютере: если ее много, можно развернуться и делать много дел параллельно. А если мало — приходится изворачиваться, и процесс затягивается. Гидни, похоже, нашел очень интересный компромисс между «железом» и временем.

Так что, всё пропало, шеф?

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

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

План «Б» уже в действии?

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

Так что, паниковать пока рано. Да, нынешние квантовые «монстры» насчитывают чуть больше тысячи кубитов, что несоизмеримо далеко от миллиона, необходимого по расчетам Гидни. Но прогресс в этой области идет семимильными шагами.

Что в итоге?

Новость о том, что для взлома RSA может хватить миллиона кубитов — это не просто очередная научная статья. Это мощный сигнал всему миру: эпоха квантового превосходства (по крайней мере, в некоторых задачах) становится все реальнее. Гонка между теми, кто строит квантовые компьютеры, и теми, кто разрабатывает защиту от них, набирает обороты.

И хотя день, когда ваш банковский счет окажется под угрозой из-за квантового взломщика, еще не наступил (и, будем надеяться, благодаря постквантовой криптографии и не наступит в таком виде), одно ясно точно: скучно в мире кибербезопасности в ближайшие годы точно не будет. А это значит, нас ждет еще много удивительных открытий и, возможно, неожиданных поворотов. Держим руку на пульсе!