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

Однако два математика доказали, что для взлома понадобится всего 20 млн кубит и восемь часов работы. Они считают, что шифр будет гарантировано взломан в ближайшие 25 лет.

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

Ученые уже пытались подсчитать ресурсы, необходимые такому квантовому компьютеру, и предсказывали, когда такую машину могут построить. И ответ всегда был — несколько десятилетий. Однако исследование квантовых вычислений, проведенное Крейгом Гидни из Google и Мартином Экерой из Королевского института в Стокгольме, открыло более эффективный метод взлома систем шифрования и на порядок сократило требования к ресурсам.

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

Предыстория: алгоритм Шора

В 1994 американский математик Питер Шор открыл квантовый алгоритм, который превзошел классический аналог — ключевой элемент процесса взлома кода с потайным входом. Функции потайных входов основаны на процессе умножения, которое легко осуществить в одном направлении и гораздо сложнее — в обратном. К примеру, не трудно перемножить 593 на 829 и получить 491 597. Но понять, какие два простых числа нужно перемножить, чтобы получить 491 597, намного сложнее. И чем больше число, тем труднее задача. Тот же принцип лежит в основе популярного шифровального алгоритма RSA.

Специалисты полагают, что классическому компьютеру практически невозможно взломать данные, зашифрованные ключом RSA с длиной 2048 бит и более.

В 2012 году физики смогли при помощи квантового компьютера разложить на множители число 143. В 2014-м — 56 153. Казалось бы, продолжая в том же духе, квантовые компьютеры вскоре смогут превзойти классические.

Не тут-то было. Оказывается, задача сложнее, чем предполагалось, потому что чем больше квантовый компьютер — тем больше на процесс его работы влияют помехи. Их нужно нейтрализовать дополнительными кубитами. В 2015 ученые подсчитали, что для того чтобы разложить на множители 2048-битные числа, потребуется миллиард кубитов. А у нас пока есть только 70.

Взлом взлома

Смысл работы Гидни и Экера в том, что они доказали: для этих вычислений квантовому компьютеру понадобится всего 20 млн кубит и восемь часов работы. Количество необходимых ресурсов упало почти на два порядка.

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

Кроме того, они подсчитали, что устройства с 20 млн кубит, невозможные сегодня, могут стать реальностью лет через 25. И тогда нам понадобится новый вид шифрования.

Для обычных пользователей открытие математиков не несет угрозы. Большинство из нас пользуется 2048-битным шифрованием разве что для передачи банковских данных через интернет. Если через 25 лет эти транзакции будут взломаны, вряд ли это причинит нам какой-то ущерб. Но для всех государств, которые хранят военные и дипломатические тайны, появление работающего квантового компьютера станет кошмаром, уверены эксперты.