Алгоритмы Шора и Гровера: объяснение

Квантовые компьютеры не просто быстрее выполняют классические алгоритмы — они используют квантовую суперпозицию и интерференцию, чтобы решать определённые задачи экспоненциально быстрее. Два алгоритма угрожают большей части используемой криптографии: алгоритм Шора (взламывает RSA/ECC) и алгоритм Гровера (ослабляет симметричную криптографию и хеш-функции).

Алгоритм Шора (1994) решает задачи разложения целых чисел на множители и дискретного логарифмирования за полиномиальное время на квантовом компьютере. Это напрямую взламывает RSA (основанный на факторизации), Диффи — Хеллмана (дискретный логарифм по модулю p) и ECDH/ECDSA (дискретный логарифм на эллиптической кривой).

Ключевой компонент алгоритма Шора — квантовое преобразование Фурье (QFT), экспоненциально более быстрая квантовая версия DFT. При поиске периода QFT определяет период функции f(x) = a^x mod N, после чего множители N выводятся с помощью GCD.

Чтобы разложить N на множители: (1) выбрать случайное a < N и проверить gcd(a,N)=1; (2) найти период r функции f(x)=a^x mod N с помощью QFT; (3) с высокой вероятностью gcd(a^{r/2}±1, N) даст нетривиальный множитель. Классический этап занимает O(log N), а квантовый поиск периода — O((log N)^3), то есть полиномиальное время.

Лучший классический метод факторизации: GNFS — субэкспоненциальная сложность O(exp((64/9 log N)^{1/3} log log N)^{2/3})). Алгоритм Шора на отказоустойчивом квантовом компьютере имеет полиномиальную сложность O((log N)^3). Для RSA-2048 требуется около 4000 логических кубитов и около 10^9 операций над элементами вентилей. Современные компьютеры NISQ имеют около 1000 зашумлённых кубитов и пока не представляют угрозы.

Алгоритм Гровера (1996) обеспечивает квадратичное ускорение неструктурированного поиска. Для пространства поиска из N элементов классическим алгоритмам требуется O(N) запросов, а алгоритму Гровера — O(√N). В криптографии это позволяет взламывать симметричные ключи длиной n бит за O(2^{n/2}) вместо O(2^n).

AES-128: классическая стойкость 2^128, алгоритм Гровера снижает её до 2^64 — это небезопасно против мощного квантового компьютера. AES-256: 2^256 → 2^128 — по-прежнему безопасно. Решение: вдвое увеличить размеры симметричных ключей. Стойкость SHA-256 к коллизиям: 2^128 → 2^85 (парадокс дней рождения + алгоритм Гровера). Стойкость SHA-256 к нахождению прообраза: 2^256 → 2^128 — OK.

Современные квантовые компьютеры NISQ (IBM Heron: 133 кубита, Google Sycamore: 70 кубитов) слишком малы и слишком зашумлены для вычислений, имеющих криптографическую значимость. Согласно оценкам, RSA-2048 будет взломан в 2035–2050 годах с появлением отказоустойчивых квантовых компьютеров. Атаки типа «собрать сейчас — расшифровать позже» представляют угрозу уже сегодня.

Злоумышленники уже сегодня собирают зашифрованный трафик и сохраняют его. Когда появится квантовый компьютер, они расшифруют эти данные задним числом. Поэтому секреты с длительным сроком действия (секретные правительственные данные, медицинские записи) уязвимы уже сейчас. Для таких данных переход на PQC необходимо начать немедленно.

Решётчатые задачи (LWE, SIS), задачи на кодах (McEliece), хеш-ориентированные схемы подписей (SPHINCS+), многомерные задачи — для них не известен квантовый алгоритм с полиномиальным временем выполнения. Они лежат в основе постквантовых стандартов NIST.

Стандарты NIST для PQC (ML-KEM, ML-DSA, SLH-DSA) были окончательно утверждены в 2024 году. Организациям следует: провести инвентаризацию текущего использования криптографии, выявить данные с длительным сроком хранения и приоритизировать внедрение PQC для обмена ключами (это наиболее срочно из-за атак типа «собрать сейчас — расшифровать позже»). Для подписей времени больше.

Как алгоритм Гровера влияет на AES-128?

Алгоритм Шора (полиномиальное время) взламывает RSA, DH и ECC. Алгоритм Гровера (квадратичное ускорение) вдвое уменьшает стойкость симметричных ключей. Решение: перейти на стандарты NIST для PQC (на основе решёток). Далее: CRYSTALS-Kyber KEM.