Решёточная криптография

На каких математических задачах строят защиту, которую не ломает алгоритм Шора.

Решёточная криптография — это семейство постквантовых схем, стойкость которых опирается на сложность геометрических задач в решётках (например, найти ближайший узел или короткий вектор), для которых не известно эффективного квантового алгоритма.

Если RSA и ECC рушатся под Шором, нужна другая «тяжёлая» задача — такая, для которой ни классический, ни квантовый компьютер не знают быстрого решения. Самым перспективным фундаментом оказались решётки. На них построены два из главных утверждённых стандартов: механизм обмена ключами Kyber и схема подписи Dilithium. Разберёмся без формул, в чём идея.

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

Чтобы осознанно выбирать и настраивать постквантовые алгоритмы, полезно понимать, откуда берётся их стойкость и какие у них особенности (например, большие ключи). Тогда решения про размеры, производительность и совместимость принимаются не вслепую. Это не про реализацию криптографии своими руками — её писать не нужно, — а про грамотное применение готовых библиотек.

Что такое решётка

Представьте бесконечную регулярную сетку точек в пространстве. На плоскости это похоже на узлы клетчатой бумаги, но в криптографии измерений много — сотни и больше. Решётка задаётся набором базисных векторов: складывая их с целыми коэффициентами, получаем все узлы. Один и тот же набор узлов можно описать хорошим базисом (короткие, почти перпендикулярные векторы) или плохим (длинные, скошенные). Узлы те же, но работать с ними по-разному легко.

Две классические «тяжёлые» задачи: SVP — найти кратчайший ненулевой вектор решётки, и CVP — для произвольной точки пространства найти ближайший к ней узел. В малых размерностях это просто, а в высоких — вычислительно неподъёмно, особенно если у вас «плохой» базис. Секрет владельца ключа как раз и есть «хороший» базис, который позволяет легко решать то, что для остальных невозможно.

LWE: обучение с ошибками

На практике чаще используют не сами SVP/CVP напрямую, а связанную задачу LWE — Learning With Errors («обучение с ошибками»). Идея неожиданно наглядна. Возьмём секретный вектор s. Будем брать случайные строки чисел a и считать скалярное произведение со s, но к каждому результату добавлять небольшую случайную ошибку. На выходе — пары «строка a и почти правильное значение b».

Без ошибки это была бы школьная система линейных уравнений: набрал достаточно строк — и решил относительно s методом исключения. Но даже крошечный шум всё ломает: накапливаясь, ошибки делают систему практически нерешаемой. Восстановить s из зашумлённых уравнений — и есть задача LWE, и она считается тяжёлой даже для квантового компьютера. При этом создавать такие пары и проверять их, зная секрет, очень легко — это и нужно для криптографии.

# Игрушечная иллюстрация LWE по модулю q (НЕ реальная криптография!)
q = 97
secret = [4, 11, 7]                 # секрет s (его «надо угадать»)

# Заранее зафиксированные строки a и маленький шум для каждой
rows   = [[17, 72, 8], [40, 24, 26], [10, 80, 5]]
errors = [1, -1, 0]                  # шум из множества {-1, 0, 1}

for a, e in zip(rows, errors):
    dot = sum(x * y for x, y in zip(a, secret))
    b = (dot + e) % q               # почти правильное значение
    print("a =", a, " b =", b)
print("Секрет:", secret)

Вывод:

a = [17, 72, 8]  b = 44
a = [40, 24, 26]  b = 23
a = [10, 80, 5]  b = 82
Секрет: [4, 11, 7]

Глядя только на пары a и b, восстановить секрет тяжело именно из-за шума. В настоящих схемах размерность — сотни, числа большие, а шум подобран строго: достаточно, чтобы запутать атакующего, но не настолько, чтобы помешать легальной расшифровке.

От LWE к Kyber и Dilithium

Чтобы ключи и операции были компактнее и быстрее, на практике берут структурированный вариант — Module-LWE, где вместо «плоских» чисел работают с многочленами в кольце. Это резко сокращает размеры и ускоряет арифметику, сохраняя ту же лежащую в основе сложность.

Kyber (стандартизован как ML-KEM) — это механизм инкапсуляции ключа (KEM). Грубо: отправитель «прячет» случайный сеансовый ключ в зашумлённое LWE-уравнение, построенное на открытом ключе получателя. Получатель своим секретом снимает шум и достаёт тот же ключ. Дальше им шифруют данные обычным быстрым AES. Так решают задачу безопасного обмена ключом без RSA/ECDH.
Dilithium (стандартизован как ML-DSA) — схема цифровой подписи. Подписант доказывает знание секрета через короткий вектор/значение, связанное с решёткой, но так, что подпись не выдаёт сам секрет. Любой с открытым ключом проверяет подпись; подделать её без секрета не выходит. Это замена RSA/ECDSA-подписям.

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

Полезно понимать, чем эти схемы отличаются от привычных в эксплуатации. Во-первых, размеры: открытые ключи, шифртексты и подписи у решёточных схем заметно больше, чем у ECC. Если у эллиптической кривой ключ — десятки байт, то у Kyber/Dilithium это уже сотни и тысячи байт. Для TLS-рукопожатия это означает чуть больше трафика; для встроенных систем с жёсткой памятью — фактор, который надо учитывать.

Во-вторых, скорость: ирония в том, что решёточные операции (в основном умножение многочленов) часто работают очень быстро — иногда быстрее, чем RSA с длинным ключом. Так что бутылочное горлышко — обычно объём данных, а не вычисления.

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

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

Используйте стандартизованные параметры Kyber/Dilithium (ML-KEM/ML-DSA), а не самодельные «решёточные» конструкции — стойкость зависит от точно выверенных чисел.
Закладывайте увеличенные размеры ключей и подписей в протоколы, буферы и форматы заранее: постквантовые артефакты крупнее привычных.
Берите аудированные библиотеки (например, реализации из liboqs / OpenSSL-провайдеров), следите за обновлениями: атаки на параметры со временем уточняются.
Не отключайте проверку шумовых/корректностных условий в библиотеке ради скорости — это часть безопасности схемы.

Итоги

Решётка — регулярная сетка точек в многомерном пространстве; задачи «найти ближайший узел/короткий вектор» тяжелы и для квантового компьютера.
LWE («обучение с ошибками») добавляет к линейным уравнениям небольшой шум, превращая лёгкую систему в практически нерешаемую без секрета.
Kyber (ML-KEM) решает обмен ключом, Dilithium (ML-DSA) — цифровую подпись; оба используют структурированный Module-LWE для компактности.
Особенности эксплуатации: большие ключи и подписи, но обычно быстрая арифметика; узкое место — размер данных, а не скорость.
Главное правило защитника: применять готовые стандартные реализации с проверенными параметрами, а не изобретать криптографию самому.