Группа китайских математиков модифицировала алгоритм Шора таким образом, чтобы даже не самые мощные квантовые компьютеры могли его успешно выполнить. Ученые приблизили возможность взламывать любые существующие сегодня криптосистемы. Команда описала модификации алгоритма и результаты его тестирования с использованием реальных уже существующих квантовых компьютеров.
Скажем несколько слов о том, как сегодня происходит шифрование (этот метод используется в подавляющем большинстве криптосистем). Возьмем два 100-значных (то есть довольно больших) простых числа (простое число не имеет других делителей, кроме самого числа и единицы) и эти числа перемножим. Сделать это можно довольно быстро (естественно не в столбик, а на компьютере). В результате получится 200-значное число, которое уже простым не является — кроме самого числа и единицы у него есть еще ровно два делителя: те самые 100-значные числа, которые мы только что перемножили.
Мы-то знаем эти два числа, поскольку их перемножали, а вот теперь мы даем кому-то это наше 200-значное число и говорим ему: найди делители этого числа. Оказывается, на решение этой обратной задачи не хватит миллионов лет, даже если использовать самый быстрый из известных на сегодня алгоритмов решето числового поля и самые быстрые компьютеры. Разница огромная: минуты для прямой задачи и миллионы лет для обратной. На этой разнице основаны алгоритмы шифрования с открытым ключом (например, RSA), которыми и шифруются банковские операции, и тот, кто научится искать делители, иначе говоря, факторизовать большие числа, сможет взломать любой шифр.
Но сегодня никто взломать такой шифр не может. Банки живут спокойно. Точнее, жили до сих пор.
Алгоритм Шора
В середине 90-х математик Питер Шор придумал алгоритм, который можно использовать для взлома таких криптосистем с помощью квантового компьютера. Но поскольку квантовые компьютеры не достигли такого уровня развития, когда они могут за обозримое время выполнить алгоритм Шора, криптосистемам ничего не угрожает. Хотя алгоритм Шора сделал сами квантовые компьютеры невероятно популярными. Все занялись квантовыми вычислениями, поскольку тот, кто научится делать это первым, окажется в серьезном выигрыше.
Кто получит все деньги мира
В новой работе команда китайских математиков так модифицировала алгоритм Шора, что для его выполнения теперь нужны гораздо менее мощные квантовые компьютеры. Математики доказали, что это работает, разложив на множители 48-битное число на квантовом компьютере с 10 кубитами.
Ученые предполагают, что вскоре они смогут факторизовать гораздо более длинные числа, а это уже несет определенные риски для реальных криптосистем. По оценкам ученых, квантовый компьютер, использующий 372 кубита и работающий по их алгоритму, может взломать любую из используемых сегодня криптосистем.
Необходимо заметить, что пока даже таких квантовых компьютеров не существует. Но возможность взлома криптосистем неожиданно сильно приблизилась.
Если в ближайшем будущем появятся квантовые компьютеры с достаточно низким коэффициентом ошибок и нужным числом кубитов, производители криптосистем поначалу смогут увеличить размер простых чисел, используемых для генерации их ключей, но это тупиковый путь: квантовый компьютер все равно их догонит. Более вероятной перспективой для защиты компьютерных систем в будущем становится использование квантово-защищенной связи, в частности, квантового распределения ключей.
Наверно, все деньги мира, так никто и не получит, но мы как-то неожиданно говорим о такой возможности уже не как об некоторой абстракции, а как о вполне реальной возможности.