Новый алгоритм приближает взлом RSA-шифрования

Квантовые компьютеры имеют потенциал взломать современное шифрование. Новый алгоритм, разработанный ученым из Нью-Йоркского университета, может существенно ускорить этот процесс.

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

Регев модифицировал алгоритм, разработанный в 1994 году Питером Шором из MIT. Шор создал метод раскладывания чисел на простые множители, что стоит в основе популярной криптографической схемы RSA. Регев предлагает эффективный способ поиска простых множителей числа, требующий гораздо меньше логических шагов. Если первоначальный алгоритм Шора требовал n^2 врат для факторизации числа, новый метод Регева требует всего n^1.5 врат.

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

Тем не менее, эти исследования служат напоминанием о том, что угроза квантовых компьютеров для шифрования постоянно меняется, и переход к пост-квантовым схемам является важной задачей на сегодняшний день.