Квантовый компьютер убьёт шифрование AES-128? Математика говорит: для этого нужно больше машин, чем атомов во Вселенной

AES-128 - один из базовых механизмов шифрования, который защищает данные в интернете и внутри сервисов. Когда браузер открывает сайт по HTTPS, когда мессенджер шифрует переписку или система хранит пароли и токены, часто в основе лежит именно этот алгоритм. Он берет данные и перемешивает их с помощью ключа длиной 128 бит. Без этого ключа исходный текст восстановить нельзя: остается только перебирать все возможные варианты, а их 2^128, то есть число с 38 нулями. Даже при огромных вычислительных мощностях такой перебор занимает астрономическое время.

На фоне разговоров о квантовых компьютерах вокруг AES-128 закрепилась упрощенная формула: как только появятся достаточно мощные квантовые машины, защита «сожмется» вдвое и станет сопоставима с 64 битами. Из этого делают прямой вывод, что алгоритм почти потеряет смысл. Криптограф Филиппо Валсорда разбирает этот тезис и показывает, где именно ломается логика.

Основанием для такого страха стал алгоритм Гровера. Он ускоряет поиск по неструктурированному набору данных и теоретически снижает число шагов при переборе ключей. В пересказах часто остается только одно: вместо 2^128 операций якобы нужно примерно 2^64. Но такой пересчет игнорирует, как устроена реальная атака и какие ограничения возникают при попытке реализовать ее на практике.

Обычный перебор на классических компьютерах хорошо делится на части. Если задача требует проверить миллиарды вариантов, ее можно раздать тысячам машин, и каждая возьмет свою долю. Чем больше ресурсов, тем быстрее падает общее время. Алгоритм Гровера ведет себя иначе. Он требует длинного последовательного вычисления, где шаги зависят друг от друга. Попытка как бы разрезать задачу и распараллелить ее резко снижает выигрыш от квантового ускорения.

Валсорда объясняет разницу на простом примере с замком на 256 комбинаций. Классическая атака перебирает все 256 вариантов. Если подключить еще троих, каждый проверит по 64, и задача завершится быстрее. С алгоритмом Гровера одиночная атака теоретически уложится в 16 шагов подряд. Но если те же четыре участника попытаются поделить работу, каждому придется делать по восемь шагов, а суммарный объем вычислений вырастет до 32. В итоге помощь увеличивает общую работу вместо того, чтобы ее сократить.

Та же логика проявляется и в более строгих оценках. Популярная цифра 2^64 строится на допущении, что весь алгоритм AES можно выполнить как одну квантовую операцию. В реальности модель гораздо сложнее. Если учитывать ограничения на параллельные вычисления и структуру самой атаки, итоговая стоимость поднимается примерно до 2^104 операций. Такой уровень уже далеко за пределами того, что можно реализовать даже с учетом будущих квантовых машин.

Похожую картину описывает инженер Google Софи Шмиг. При обычном переборе остановка на половине пути уже дает около 50 процентов шанса угадать ключ, поэтому задачу легко делить между машинами. В квантовом варианте при той же остановке вероятность успеха падает примерно до 25 процентов. Чтобы сохранить эффективность, приходится увеличивать число устройств, и общий объем работы снова растет. Если довести параллелизацию до предела, понадобится уже 2^128 квантовых машин, то есть выигрыш исчезает.

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

Главный вывод Валсорды касается приоритетов. Квантовые компьютеры действительно представляют проблему для криптографии, но в первую очередь для асимметричных алгоритмов, которые лежат в основе обмена ключами и цифровых подписей. Алгоритм Шора способен ломать их на порядки быстрее классических методов. Поэтому основной объем работы сейчас связан с заменой именно этих механизмов на постквантовые аналоги. Симметричное шифрование, к которому относится AES, в этом смысле остается устойчивым и не требует срочной перестройки.