Квантовая угроза: алгоритмы Шора и Гровера

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

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

Сегодняшняя защита данных стоит на простой идее: есть математические задачи, которые легко решить в одну сторону и практически невозможно — в обратную. Перемножить два больших простых числа просто, а разложить результат обратно на множители — чудовищно долго для обычного компьютера. На этом «обратном» неравенстве держатся RSA, обмен ключами Диффи-Хеллмана и эллиптическая криптография (ECC), а значит — почти весь защищённый трафик в интернете: HTTPS, мессенджеры, банковские операции, подпись обновлений.

Зачем это знать защитнику

Инженеру по безопасности важно понимать угрозу не для того, чтобы что-то ломать, а чтобы вовремя планировать миграцию. Криптография — это «долгий» элемент инфраструктуры: сертификаты, протоколы и встроенные в железо алгоритмы живут годами и десятилетиями. Если мы узнаём о слабости только в день, когда она реализовалась, — уже поздно. Поэтому квантовую угрозу принято оценивать заранее, как стихийный риск: не «случится ли», а «к какому сроку нужно быть готовым».

Алгоритм Шора: удар по асимметрике

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

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

Вывод простой: RSA, классический Диффи-Хеллман и ECC при достаточно мощном квантовом компьютере перестают быть защитой полностью. Увеличение длины ключа здесь почти не помогает: алгоритм Шора масштабируется слишком хорошо.

Алгоритм Гровера: удар по симметрике

Для симметричного шифрования (AES) и хеш-функций (SHA-2, SHA-3) угроза мягче. Здесь работает другой квантовый алгоритм — Гровера (1996). Он ускоряет перебор: классический полный перебор по пространству из N вариантов требует порядка N операций, а Гровер находит нужный за порядка корня из N. Это «квадратичное» ускорение, а не экспоненциальное, как у Шора.

На практике это означает, что Гровер как бы уполовинивает эффективную длину ключа. AES-128 против квантового перебора ведёт себя примерно как 64-битный против классического — это уже слабовато. А вот AES-256 даже после «уполовинивания» сохраняет около 128 бит стойкости, чего достаточно. Поэтому защита проста и понятна: переходить на AES-256 и хеши с длинным выходом (например, SHA-384/SHA-512). Симметрику не нужно выбрасывать — её достаточно «утолстить».

Harvest now, decrypt later

Самое коварное в квантовой угрозе — что она опасна уже сегодня, хотя большого квантового компьютера ещё нет. Стратегия называется «harvest now, decrypt later» («собери сейчас, расшифруй потом»). Противник перехватывает и сохраняет зашифрованный трафик прямо сейчас, складывает его в архив и ждёт. Как только появится квантовый компьютер, способный запустить Шора на нужном размере ключа, весь накопленный архив будет расшифрован задним числом.

Это смещает дедлайн миграции в прошлое. Для данных, которые должны оставаться секретными 10–20 лет (медицинские записи, гостайна, долгосрочные коммерческие тайны, корневые ключи), «потом» уже наступило: если их перехватят сегодня, они окажутся уязвимы, как только техника дозреет. Поэтому организации с длинным горизонтом конфиденциальности начинают переход на постквантовые алгоритмы, не дожидаясь готового квантового компьютера.

Как это работает под капотом

Стоит развеять частое заблуждение: квантовый компьютер — это не «обычный, но в миллион раз быстрее». Он работает иначе. Вместо битов (0 или 1) у него кубиты, которые могут находиться в суперпозиции состояний. Несколько кубитов вместе кодируют сразу множество комбинаций, и квантовый алгоритм организует интерференцию так, чтобы нужный ответ «усилился», а ненужные «погасились». Именно поэтому ускорение получается только для особых задач со скрытой структурой (период, как у Шора), а не для всего подряд.

Главная сложность — кубиты крайне хрупкие: шум и взаимодействие со средой разрушают квантовое состояние (декогеренция). Чтобы запустить Шора на «боевом» размере ключа RSA, нужны не сотни шумных физических кубитов, а тысячи стабильных логических кубитов, каждый из которых собирается из множества физических с коррекцией ошибок. Поэтому сегодняшние процессоры пока не угрожают реальным ключам — но прогресс идёт, и оценки «когда» постоянно сдвигаются. Защитник планирует, исходя из риска, а не из точной даты.

Ниже — крошечная классическая иллюстрация того, почему факторизация «тяжела»: даже наивный перебор делителей быстро упирается в размер числа.

def factor_trial(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d, n // d
        d += 1
    return None  # простое

# Маленькое число факторизуется мгновенно
print(factor_trial(91))        # 7 * 13
# А число побольше уже требует заметного перебора
print(factor_trial(1000003))   # это простое число
print("Шагов для 1000003 примерно:", int(1000003 ** 0.5))

Вывод:

(7, 13)
None
Шагов для 1000003 примерно: 1000

Для настоящего RSA число имеет сотни десятичных цифр, и даже «умные» классические методы (не наивный перебор) бессильны за обозримое время — а Шор справился бы. В этом и суть угрозы.

Как защититься

Главное — действовать заранее и системно, а не паниковать.

• Сделайте инвентаризацию криптографии: где используются RSA/ECC/DH, какие сертификаты, какие сроки жизни ключей и данных. Нельзя защитить то, о чём не знаешь.
• Поднимите симметрику до квантово-стойких параметров: AES-256 вместо AES-128, хеши с длинным выходом. Это дёшево и снимает угрозу Гровера.
• Введите криптографическую гибкость (crypto-agility): проектируйте системы так, чтобы алгоритм можно было заменить без переписывания всего. Тогда переход на постквантовые схемы будет управляемым.
• Приоритизируйте по горизонту секретности: данные, которые должны жить десятилетиями, мигрируйте на постквантовые алгоритмы в первую очередь — из-за «harvest now, decrypt later».
• Следите за стандартами: ориентир — утверждённые NIST постквантовые алгоритмы, о которых речь в следующих уроках. Не изобретайте свою «квантово-стойкую» криптографию.

Итоги

• Алгоритм Шора полиномиально решает факторизацию и дискретный логарифм — это рушит RSA, классический Диффи-Хеллман и ECC; длиннее ключ почти не спасает.
• Алгоритм Гровера даёт лишь квадратичное ускорение перебора, поэтому симметрику (AES) и хеши достаточно «утолстить»: AES-256, длинные хеши.
• Угроза «harvest now, decrypt later» делает миграцию актуальной уже сегодня для долгоживущих секретов, даже до появления большого квантового компьютера.
• Квантовое ускорение работает только для задач со скрытой структурой; помеха — хрупкость кубитов и потребность в коррекции ошибок.
• Защита защитника: инвентаризация, AES-256, crypto-agility и плановый переход на стандартизованные постквантовые алгоритмы.