Постквантовые алгоритмы обмена ключами

Все началось с того, что при коннекте по SSH с одного очень нового сервера на один очень старый, SSH-клиент выдал вот такую фразу:

** WARNING: connection is not using a post-quantum key exchange algorithm.
** This session may be vulnerable to "store now, decrypt later" attacks.
** The server may need to be upgraded. See https://openssh.com/pq.html

** ВНИМАНИЕ: соединение не использует постквантовый алгоритм обмена ключами.
** Эта сессия может быть уязвима для атак типа «сохранить сейчас, расшифровать позже».
** Возможно, потребуется обновление сервера.

Что же это за постквантовые алгоритмы и о каких уязвимостях перед квантовыми компьютерами будущего предупреждает нас SSH-клиент?

Этот варнинг появляется потому, что клиентский компьютер использует современный OpenSSH (версии 10.1 или новее), а сервер работает на старой ОС (Ubuntu 16.04 или даже 20.04) со старой версией OpenSSH (ниже 9.0). Постквантовая защита (алгоритмы шифрования sntrup761 или mlkem) появляются только в Ubuntu 24.04+ (OpenSSH 9.6+).

sntrup761 (Streamlined NTRU Prime 761)

Это постквантовый алгоритм обмена ключами (KEX), основанный на математике криптографии на решетках (lattice-based cryptography). Его главная задача — защитить данные от расшифровки в будущем с помощью мощных квантовых компьютеров. В OpenSSH этот алгоритм используется не самостоятельно, а в виде гибрида sntrup761x25519-sha512.

Как это работает и зачем нужно?

• Гибридный подход: Алгоритм объединяет классический протокол x25519 (эллиптические кривые) и постквантовый sntrup761. Если в будущем x25519 будет взломан квантовым компьютером, сессия останется защищенной благодаря sntrup761. Если же в самом sntrup761 найдут уязвимость, надежность соединения будет не хуже, чем у классического проверенного x25519.
• Защита от атаки «Перехвати сейчас, расшифруй потом»: Злоумышленники могут записывать ваш зашифрованный SSH-трафик сегодня, чтобы расшифровать его через 10–15 лет, когда появятся криптографически релевантные квантовые компьютеры. Использование sntrup761 делает такую дешифровку невозможной, потому что он основан на криптографии на решётках (lattice-based cryptography). Этот математический подход неуязвим для известных квантовых алгоритмов, в отличие от классического шифрования.

Принцип защиты строится на фундаментальной разнице в математических задачах:

В чем слабость классического шифрования?

Обычные алгоритмы (RSA, Diffie-Hellman, ECDH) основаны на задачах факторизации больших чисел или дискретного логарифмирования. Обычный компьютер решает такие задачи миллионы лет.

Квантовый компьютер использует алгоритм Шора (Shor’s algorithm). Этот алгоритм позволяет квантовым кубитам находить секретные ключи за считанные минуты. Если трафик был перехвачен и записан, квантовый компьютер легко его вскроет.

Как sntrup761 защищает от квантового компьютера?

Алгоритм sntrup761 (модификация системы NTRU) полностью меняет математическую парадигму:

• Многомерные геометрические решётки: Вместо деления чисел алгоритм работает с геометрическими объектами в пространствах с сотнями измерений (векторами на решётках).
• Задача поиска кратчайшего вектора (SVP): Секретный ключ — это точка в этой многомерной решётке, находящаяся максимально близко к началу координат.
• Бессилие алгоритма Шора: Алгоритм Шора абсолютно бесполезен против геометрии решёток. Для квантового компьютера поиск правильной точки в 761-мерном пространстве (отсюда число 761 в названии) остается задачей экспоненциальной сложности — ему всё так же потребуются миллиарды лет перебора.

Дополнительная защита: гибридный метод

Разработчики OpenSSH учитывают, что sntrup761 — относительно новый алгоритм. Чтобы исключить скрытые уязвимости, его объединили с классическим x25519 в связку sntrup761x25519-sha512.

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

На сколько применение данного алгоритма нагружает процессор

Использование гибридного алгоритма sntrup761x25519-sha512 практически не создает заметной нагрузки на современный процессор. Потребление ресурсов увеличивается незначительно, и обычный пользователь этого не замечает.

Математические вычисления выполняются только в момент установки SSH-соединения (фаза рукопожатия / handshake). Как только связь установлена, алгоритм отключается, а сам трафик шифруется стандартными быстрыми алгоритмами вроде AES или ChaCha20.

Нагрузку можно разделить на две категории в зависимости от устройства:

1. На обычном компьютере или сервере

• Процессорное время: На вычисление ключей уходит мизерная доля секунды. Даже если вы будете открывать десятки SSH-сессий в секунду, загрузка CPU мощного сервера едва ли превысит 0.01%.
• Сетевой оверхед (трафик): Размер постквантовых ключей больше традиционных. Вместо скромных 32 байт для классического x25519, гибридный пакет sntrup761 весит около 1 КБ. Для современных сетей этот лишний килобайт при подключении абсолютно неощутим.

2. Специфика для мини-компьютеров

Для мини-компьютера с относительно слабым процессором ARM Cortex-A53 (1.2 ГГц) разница есть, но она также незначительна:

• Задержка при входе: При подключении, например, к Raspberry Pi по SSH вы можете заметить, что от момента ввода команды до появления строки приветствия (логина) проходит на 20–50 миллисекунд дольше, чем при использовании старого «чистого» x25519.
• Нагрузка на CPU: В момент генерации ключа (микросекундный всплеск) одно ядро процессора нагрузится сильнее обычного, но как только сессия откроется, нагрузка мгновенно упадет до 0%.

Стоит ли его отключать ради экономии ресурсов?

Однозначно нет. Экономия нескольких миллисекунд процессорного времени при авторизации не стоит того, чтобы лишать систему долгосрочной защиты от квантового взлома в будущем. В процессе удержания уже открытой сессии этот алгоритм процессор вообще не использует.

Применяется ли подобные алгоритмы в туннелях ВПН

Эти алгоритмы применяются для защиты VPN-туннелей, но их использование имеет свою специфику и зависит от конкретного провайдера и технологии.

Как и в случае с SSH, в VPN-туннелях sntrup761 отвечает исключительно за фазу обмена ключами (Handshake), защищая сессию от атак класса «перехвати сейчас, расшифруй потом». Сам же интернет-трафик внутри туннеля шифруется быстрыми симметричными алгоритмами (например, AES-256 или ChaCha20).

OpenSSH

Если вы поднимаете свой собственный VPN-туннель средствами самого OpenSSH (например, через команду ssh -w или туннелирование трафика ssh -D), то sntrup761 используется там по умолчанию (начиная с OpenSSH 9.0), защищая весь проходящий трафик.

Хотя sntrup761 очень надежен, он не стал главным мировым стандартом. В 2024 году американский институт NIST официально финализировал стандарты постквантовой криптографии. Победителем стал другой алгоритм на решетках — ML-KEM (ранее известный как Kyber).

Как принудительно заставить SSHFS использовать sntrup761?

Если вы хотите быть на 100% уверены, что соединение пойдет строго через этот алгоритм (или если на сервере изменены дефолтные настройки), вы можете передать SSHFS жесткое требование к шифрованию через флаг -o KexAlgorithms

sshfs user@123.45.67.89:/remote/dir /local/mnt -o KexAlgorithms=sntrup761x25519-sha512@openssh.com

Как проверить, что алгоритм на решётках действительно включился?

Вы можете запустить монтирование в режиме отладки с выводом подробных логов, добавив ключ -o ssh_command=»ssh -v»

sshfs user@123.45.67.89:/remote/dir /local/mnt -o ssh_command="ssh -v"

В терминал посыплется техническая информация. Ищите в первых 30-40 строках блоки, связанные с KEX (Key Exchange)

debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: sntrup761x25519-sha512@openssh.com

StrongSwan

Что касается используемых алгоритмов, strongSwan имеет модульную архитектуру плагинов. Набор алгоритмов зависит от того, какие библиотеки подключены (например, openssl, gcrypt или wolfssl).

В strongSwan v6 реализована поддержка множественного обмена ключами (Multiple Key Exchanges, RFC 9370). Это позволяет строить гибридные туннели, устойчивые к квантовым компьютерам.

В отличие от OpenSSH, выбравшего sntrup761, экосистема strongSwan и стандарты IPsec пошли по пути рекомендаций NIST:

• ML-KEM (бывший Kyber): Главный постквантовый алгоритм обмена ключами в современных сборках strongSwan. Настраивается через дополнительные параметры ke1_ … ke7_ в предложениях swanctl.
• ML-DSA (бывший Dilithium): Используется для квантово-устойчивой аутентификации по сертификатам.
• Другие альтернативы: В зависимости от плагинов могут поддерживаться алгоритмы BIKE или HQC.

Пример настройки гибридного (квантово-защищенного) туннеля в swanctl.conf

# Сначала выполняется классический обмен (curve25519), 
# а следом — постквантовый (mlkem768)
proposals = aes256-sha256-x25519-ke1_mlkem768

Как узнать, что доступно именно у вас?

Поскольку strongSwan собирается из плагинов, вы можете прямо в терминале своего сервера проверить, какие именно алгоритмы шифрования сейчас подгружены и доступны для swanctl:

swanctl --list-algs

Команда выведет весь список: от классического AES до доступных методов генерации ключей и постквантовых модулей.

ML-KEM-768 (ранее известный как Kyber768)

Это официальный глобальный стандарт постквантового обмена ключами, утвержденный американским институтом NIST (стандарт FIPS 203). Хотя и ML-KEM-768, и обсуждаемый ранее sntrup761 относятся к криптографии на многомерных решетках, между ними есть принципиальные различия, определившие их судьбу в ИТ-индустрии.

Основные отличия ML-KEM-768 от конкурентов и, в частности, от sntrup761:

1. Статус официального мирового стандарта

• ML-KEM-768: Победитель многолетнего конкурса NIST. Именно его официально выбрали в качестве обязательного будущего стандарта для всей мировой индустрии. Он внедряется в TLS 1.3 (HTTPS), браузеры (Chrome, Firefox), продукты Google, AWS и Cloudflare.

• sntrup761: Не является стандартом NIST. Это альтернативный «академический» алгоритм, созданный известным криптографом Дэниелом Бернштейном. Его интеграция в OpenSSH была временной подстраховкой разработчиков, пока NIST финализировал свои стандарты.

2. Математическая база и производительность

Оба алгоритма решают задачу на решетках, но используют разные типы модулей, что напрямую влияет на скорость их работы:

• ML-KEM-768 работает значительно быстрее. Он оптимизирован для векторных процессорных инструкций (например, AVX-512). Скорость генерации и проверки ключей у него выше, чем у sntrup761.
• ML-KEM-768 имеет меньший размер данных. При обмене ключами он передает по сети пакеты меньшего объема по сравнению со sntrup761, что критично для загруженных веб-серверов с миллионами запросов в секунду.

Разница между sntrup761 (Streamlined NTRU Prime) и ML-KEM-768 (Kyber) заключается в особенностях математической структуры решёток и в том, как именно они обрабатывают ошибки округления при дешифровании.

Хотя оба алгоритма относятся к криптографии на решётках, они представляют две разные математические философии.

1. Фундаментальная математика (Кольца против Модулей)

• sntrup761 (Семейство NTRU): Работает в одном фиксированном, но очень сложном большом кольце полиномов. Чтобы повысить безопасность, инженеры увеличивают степень самого полинома (в sntrup761 степень равна 761). Математическая структура этого кольца специально сделана «неправильной» и асимметричной, чтобы минимизировать любые скрытые математические зависимости, которые теоретически мог бы использовать злоумышленник.

• ML-KEM-768 (Семейство Kyber): Использует подход модульных решёток. Вместо одного огромного полинома он работает с небольшими матрицами и векторами, элементами которых являются простые полиномы фиксированной степени 256. В версии ML-KEM-768 используется матрица размером всего 3 × 3. Чтобы повысить безопасность, инженеры просто увеличивают размер матрицы (например, до 4 × 4 в ML-KEM-1024), не меняя саму математику полиномов.

2. Вероятность ошибки дешифрования (Decryption Failure)

• ML-KEM (Kyber): Имеет микроскопическую, но теоретически ненулевую вероятность ошибки расшифровки (около 2⁻¹⁶⁴ для версии 768). Из-за случайного шума в редчайших случаях «0» может округлиться в «1». В реальной жизни эта вероятность меньше, чем шанс падения метеорита на сервер во время рукопожатия, но перфекционистам это не нравилось.

• sntrup761 (NTRU Prime): Создавался под девизом «Никаких компромиссов в безопасности». Его математика рассчитана так, что вероятность ошибки равна строго нулю. Корректно зашифрованное сообщение всегда расшифруется идеально, независимо от случайного шума.

3. Оптимизация и NTT-преобразование

• ML-KEM: Специально проектировался под быстрое преобразование NTT (которое рассматривается ниже). Его модуль q = 3329 и степень 256 идеально подходят для этого. Из-за этого Kyber работает феноменально быстро на любых процессорах и требует очень мало строчек кода.

• sntrup761: Из-за своей сложной «защищенной» структуры (где степень полинома равна 761, а модуль q = 4591) алгоритм не поддерживает стандартное NTT-преобразование. Для его ускорения требуются гораздо более сложные и тяжелые математические трюки (например, алгоритм Карацубы или многоступенчатые схемы смешанных оснований).

3. Уровень безопасности (Индекс «768»)

Цифра в названии указывает на уровень квантовой стойкости:

• ML-KEM-768 обеспечивает Уровень 3 (NIST Security Level 3), что эквивалентно по стойкости симметричному шифрованию AES-192. Это оптимальный баланс между скоростью работы и криптостойкостью для большинства коммерческих систем.

• sntrup761 имеет промежуточную стойкость. Однако сторонники sntrup761 утверждают, что его математическая модель имеет более «консервативные» и безопасные предположения, снижающие риск скрытых уязвимостей в самой теории алгоритма.

Сводное сравнение алгоритмов

Итог

ML-KEM (Kyber) победил в конкурсе NIST благодаря своей модульной структуре, простоте реализации и колоссальной скорости работы через NTT. Именно поэтому его добавили в strongSwan, WireGuard и браузеры.

sntrup761 остался нишевым, но очень уважаемым алгоритмом. Его авторы пожертвовали скоростью ради математической «чистоты» и нулевой вероятности ошибок, поэтому разработчики OpenSSH выбрали его в качестве надежного защитника для удаленного доступа к серверам.

Пример настройки mlkem768 в strongswan

Настройка ML-KEM-768 (ранее Kyber768) в strongSwan стала официально доступна начиная с версии strongSwan 6.0.0 (декабрь 2024 года). Для реализации постквантовой защиты используется современный синтаксис управления через утилиту swanctl и конфигурационный файл swanctl.conf.

Поскольку использовать «чистый» постквантовый алгоритм в продакшене рискованно из-за его новизны, индустриальным стандартом является гибридный метод (RFC 9370 + RFC 9242). В рамках одной сессии strongSwan сначала выполняет классический обмен ключами (например, эллиптические кривые x25519), а затем, на промежуточном этапе, подмешивает секрет от ML-KEM-768.

Ниже приведен готовый рабочий пример конфигурации защищенного гибридного туннеля между двумя офисами (Site-to-Site).

Шаг 1. Конфигурация swanctl.conf на стороне Сервера А (Инициатор)

Файл конфигурации обычно располагается по пути /etc/swanctl/swanctl.conf.

connections {
    net-to-net-pqc {
        version = 2
        local_addrs = 192.168.1.10
        remote_addrs = 192.168.2.10

        # Гибридный обмен: классический (Curve25519) + PQC (ML-KEM-768)
        proposals = aes256-sha256-x25519-ke1_mlkem768

        local { auth = psk; id = office-a@company.com }
        remote { auth = psk; id = office-b@company.com }

        children {
            tunnel-pqc {
                local_ts = 10.10.1.0/24
                remote_ts = 10.10.2.0/24
                esp_proposals = chacha20poly1305
                updown = _updown iptables
            }
        }
    }
}

Шаг 2. Конфигурация swanctl.conf на стороне Сервера Б (Респондент)

Настройки зеркальны, параметры proposals и ke1_proposals должны совпадать.

connections {
    net-to-net-pqc {
        version = 2
        local_addrs = 192.168.2.10
        remote_addrs = 192.168.1.10
        proposals = aes256-sha256-x25519-ke1_mlkem768
        local { auth = psk; id = office-b@company.com }
        remote { auth = psk; id = office-a@company.com }
        children {
            tunnel-pqc {
                local_ts = 10.10.2.0/24
                remote_ts = 10.10.1.0/24
                esp_proposals = chacha20poly1305
                updown = _updown iptables
            }
        }
    }
}
# Секреты аналогичны инициатору

Имеет ли постквантовую защиту шифрование по ГОСТ

Текущие государственные стандарты шифрования (ГОСТ) защищены от квантовых угроз лишь наполовину, а полноценные отечественные постквантовые стандарты находятся в процессе разработки и ожидаются в 2026–2027 годах. Ситуация кардинально различается для двух типов алгоритмов: симметричных и асимметричных.

Влияние квантовых компьютеров на российские ГОСТ-алгоритмы делится на две категории:

1. Симметричные шифры и хэш-функции — ИМЕЮТ защиту

Алгоритмы ГОСТ Р 34.12-2015 («Кузнечик» и «Магма»), а также хэш-функция ГОСТ Р 34.11-2012 («Стрибог») изначально обладают высокой устойчивостью к квантовым атакам.

• Почему они защищены: Против симметричных шифров квантовый компьютер может применить только алгоритм Гровера. Этот алгоритм не взламывает шифр полностью, а лишь уменьшает эффективную длину ключа вдвое.
• Поскольку длина ключа в «Кузнечике» и «Магме» составляет 256 бит, их квантовая стойкость снижается до 128 бит. Этого запаса прочности с избытком хватает, чтобы сделать полный перебор ключей невозможным для любого компьютера будущего.

2. Асимметричные шифры и ЭЦП — НЕ ИМЕЮТ защиты

Алгоритм электронной цифровой подписи ГОСТ Р 34.10-2012 (основанный на эллиптических кривых) полностью уязвим для квантового алгоритма Шора.

• В чем опасность: Мощный квантовый компьютер сможет за несколько минут вычислить закрытый ключ подписи на основе открытого ключа или взломать процедуру выработки общего секретного ключа (VKO ГОСТ). Соответственно, трафик, защищенный классическим ГОСТ-TLS, подвержен атакам типа «перехвати сейчас, расшифруй потом».

Текущие разработки в России (2026 год)

Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26) активно готовит замену уязвимым асимметричным алгоритмам:

• Гибридный подход: Прямо сейчас в российских СКЗИ (средствах криптографической защиты информации) тестируется интеграция гибридных протоколов, где классический ГОСТ Р 34.10-2012 объединяется с новыми постквантовыми решёточными алгоритмами (похоже на то, как OpenSSH объединил x25519 и sntrup761).
• Первые официальные шаги: В марте 2026 года Минцифры России впервые официально одобрило программные комплекты (SDK), такие как «Сириус-Q. КНАА-2-ЭЦП», реализующие отечественную квантово-устойчивую электронную подпись для блокчейн-платформ.
• Официальные стандарты ГОСТ: Окончательное принятие новых, полностью независимых постквантовых стандартов ГОСТ для общих каналов связи запланировано регуляторами на период 2026–2027 годов.

Пора закладывать в архитектуру гибридные методы защиты, т. к. квантовое будущее уже не за горами.

Используется ли на мобильных устройствах

Алгоритмы постквантового шифрования можно и уже активно используют на обычных современных смартфонах.

Для этого не требуется специальное «квантовое» или специфическое железо. Постквантовая криптография (PQC) — это обычные математические алгоритмы (просто с матрицами и полиномами вместо факторизации чисел), которые выполняются на стандартных ARM-процессорах телефонов.

Ниже подробно разобрано, где именно они уже работают и какие устройства их поддерживают.

Математика процесса

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

В основе большинства современных алгоритмов (например, Kyber/ML-KEM, принятого стандартом NIST) лежит задача LWE (Learning With Errors — Обучение с ошибками) или ее кольцевой вариант Ring-LWE.

Математический базис

Решётка — это бесконечное множество точек в n-мерном пространстве, образованных целыми линейными комбинациями базисных векторов.

Численный пример

Чтобы наглядно понять математику LWE (Learning With Errors), давайте разберем упрощенный численный пример шифрования одного бита информации.

В реальных системах размерность матриц составляет (512 х 512) и более, но для примера мы возьмем размерность (n = 2) и будем проводить все вычисления по модулю числа (q = 17).

Шифрование строки

Чтобы зашифровать целую строку текста, а не один бит, в криптографии на решётках используют два основных подхода.

Первый — это простое повторение алгоритма LWE для каждого бита (очень медленно). Второй — современный и эффективный подход, используемый в стандарте Kyber (ML-KEM). Он называется Ring-LWE (LWE в кольцах полиномов).

Вместо чисел и матриц здесь используются полиномы (многочлены), а одна математическая операция шифрует сразу целый блок данных.

Главный секрет: Текст → Биты → Коэффициенты полинома

В Ring-LWE сообщение представляется в виде полинома, где каждый бит текста становится коэффициентом перед переменной x.

Максимальная степень полинома обычно равна n = 256. Это значит, что один полином может содержать ровно 256 коэффициентов.

• Каждый коэффициент — это либо 0, либо 1 (один бит).
• В 256 бит отлично помещается 32 байта данных (например, 256-битный секретный ключ для AES или короткая строка текста).

Пример кодирования строки «Hi»:

1. Переводим буквы в бинарный код (ASCII/UTF-8):
   1. «H» = 01001000
   2. «i» = 01101001
   3. Итоговая строка бит: 0100100001101001 … (остальные из 256 позиций забиваем нулями).
2. Превращаем эти биты в коэффициенты полинома m(x):
   
   $m\left(x\right)=\mathbf{0}+\mathbf{1}x+\mathbf{0}{x}^2+\mathbf{0}{x}^3+\mathbf{1}{x}^4+\mathbf{0}{x}^5+\mathbf{0}{x}^6+\mathbf{0}{x}^7+\mathbf{0}{x}^8+\mathbf{1}{x}^9+\mathbf{1}{x}^{10}\dots$

Как устроена математика для строк

Вместо умножения огромных матриц компьютеры умножают полиномы в специальном кольце по модулю X²⁵⁶ + 1 и по модулю простого числа q (например, q = 3329).

1. Генерация ключей

• Секретный ключ (s): случайный полином с маленькими коэффициентами.
• Открытый ключ (A, b): случайный полином A (общеизвестный) и вычисляемый полином b:
  
  $b=A\cdot s+e(mod{X}^{256}+1,q)$
  
  (где e — полином-шум с микроскопическими коэффициентами).

2. Шифрование всей строки за один раз

Отправитель берет полином сообщения m(x), где зашиты наши буквы «Hi», и масштабирует его коэффициенты, умножая на $\lfloor q/2\rfloor$ (например, на 1664). То есть вместо 0 и 1 коэффициенты становятся равны 0 и 1664.

Затем создаются три случайных маленьких полинома-переключателя (r, e₁, e₂) и вычисляется шифротекст из двух полиномов (u, v):

3. Расшифровка и чтение текста

Получатель выполняет уже знакомую нам поштучную очистку от шума, но сразу для всего многочлена:

4.Финальный шаг алгоритма:

1. Компьютер пробегается по всем 256 коэффициентам полученного полинома.
2. Если коэффициент ближе к 1664, он превращает его в 1. Если ближе к 0 — в 0.
3. Полученная цепочка бит 0100100001101001… декодируется обратно в символы.
4. Перед получателем снова появляется строка «Hi».

Почему на практике так не шифруют длинные файлы?

Шифрование на решётках (как и RSA) — это асимметричное шифрование. Оно требует много памяти: чтобы передать строку из 32 байт, размер шифротекста (u, v) составит около 1-2 килобайт. Шифровать так гигабайты видео или документов слишком накладно.

Поэтому в реальности строки шифруют только в рамках механизма KEM (Key Encapsulation Mechanism):

1. Алиса шифрует на решётках случайную короткую строку (256-битный ключ).
2. Пересылает её Бобу.
3. Боб расшифровывает её с помощью своего секретного ключа.
4. Теперь у Алисы и Боба есть общий секретный ключ, и всю дальнейшую переписку или файлы они шифруют моментальным и легким симметричным алгоритмом (например, AES или Кузнечик).

Простая реализация Ring-LWE на Python

Код шифрует строку текста, превращает её в полином, добавляет случайный шум, а затем успешно расшифровывает обратно. Для работы кода нужен только чистый Python без сторонних библиотек.

import random

# Параметры кольца полиномов (упрощенные для наглядности)
# На практике N = 256, Q = 3329 (как в Kyber / ML-KEM)
N = 64        # Максимальная степень полинома (х^64)
Q = 257       # Модуль вычислений (простое число)
HALF_Q = Q // 2

# === ВСПОМОГАТЕЛЬНЫЕ ФУНКЦИИ ДЛЯ РАБОТЫ С ПОЛИНОМАМИ ===

def poly_add(poly1, poly2):
    """Сложение двух полиномов по модулю Q"""
    res = [(poly1[i] + poly2[i]) % Q for i in range(N)]
    return res

def poly_sub(poly1, poly2):
    """Вычитание двух полиномов по модулю Q"""
    res = [(poly1[i] - poly2[i]) % Q for i in range(N)]
    return res

def poly_mul(poly1, poly2):
    """Умножение полиномов в кольце по модулю (X^N + 1) и по модулю Q"""
    res = [0] * (2 * N)
    # Обычное умножение в лоб
    for i in range(N):
        for j in range(N):
            res[i + j] += poly1[i] * poly2[j]
    
    # Редукция по модулю X^N + 1 (срезаем хвост полинома и вычитаем его из начала)
    final_res = [0] * N
    for i in range(N):
        final_res[i] = (res[i] - res[i + N]) % Q
    return final_res

def gen_noise_poly():
    """Генерация полинома-шума (маленькие коэффициенты: -1, 0, 1)"""
    return [random.choice([-1, 0, 1]) % Q for _ in range(N)]

# === ОСНОВНОЙ АЛГОРИТМ ШИФРОВАНИЯ ===

# 1. Генерация ключей
def generate_keys():
    # Открытый случайный полином A
    poly_A = [random.randint(0, Q - 1) for _ in range(N)]
    # Секретный ключ S (маленькие коэффициенты)
    secret_S = gen_noise_poly()
    # Шум E
    noise_E = gen_noise_poly()
    
    # b = A * s + e
    poly_b = poly_add(poly_mul(poly_A, secret_S), noise_E)
    
    # Открытый ключ: (A, b), Секретный ключ: S
    return (poly_A, poly_b), secret_S

# 2. Шифрование строки
def encrypt_string(text, public_key):
    poly_A, poly_b = public_key
    
    # Переводим текст в биты
    bits = []
    for char in text:
        bits.extend([int(b) for b in f"{ord(char):08b}"])
    
    if len(bits) > N:
        raise ValueError(f"Текст слишком длинный! Максимум {N // 8} символов для N={N}")
    
    # Добиваем нулями до длины N
    bits += [0] * (N - len(bits))
    
    # Масштабируем биты в полином сообщения m(x): умножаем каждый бит на HALF_Q
    poly_m = [(bit * HALF_Q) % Q for bit in bits]
    
    # Генерируем случайные параметры шифрования (маленькие шумы)
    r = gen_noise_poly()
    e1 = gen_noise_poly()
    e2 = gen_noise_poly()
    
    # u = A * r + e1
    poly_u = poly_add(poly_mul(poly_A, r), e1)
    # v = b * r + e2 + m
    poly_v = poly_add(poly_add(poly_mul(poly_b, r), e2), poly_m)
    
    return (poly_u, poly_v)

# 3. Расшифровка строки
def decrypt_string(ciphertext, secret_key):
    poly_u, poly_v = ciphertext
    
    # Очистка от шума: у = v - u * s
    poly_decrypted = poly_sub(poly_v, poly_mul(poly_u, secret_key))
    
    # Округление коэффициентов обратно в биты (0 или 1)
    decoded_bits = []
    for coeff in poly_decrypted:
        # Находим расстояние до HALF_Q и до 0 (с учетом циклического модуля Q)
        dist_to_half = min(abs(coeff - HALF_Q), Q - abs(coeff - HALF_Q))
        dist_to_zero = min(coeff, Q - coeff)
        
        if dist_to_half < dist_to_zero:
            decoded_bits.append(1)
        else:
            decoded_bits.append(0)
            
    # Собираем биты обратно в строку текста
    chars = []
    for i in range(0, len(decoded_bits), 8):
        byte = decoded_bits[i:i+8]
        if len(byte) < 8 or sum(byte) == 0: # Прерываемся на пустых байтах
            break
        char_code = int("".join(map(str, byte)), 2)
        chars.append(chr(char_code))
        
    return "".join(chars)

# === ТЕСТИРОВАНИЕ СИСТЕМЫ ===
if __name__ == "__main__":
    message = "Secret!" # Длина должна быть не более N // 8 = 8 символов
    print(f"Исходное сообщение: '{message}'")
    
    # Генерация пары ключей
    pub_key, sec_key = generate_keys()
    
    # Шифрование
    cipher = encrypt_string(message, pub_key)
    print("\nСтрока успешно зашифрована в пару полиномов (u, v).")
    print(f"Пример полиномы U (первые 5 коэф.): {cipher[0][:5]}...")
    
    # Расшифровка
    decrypted_message = decrypt_string(cipher, sec_key)
    print(f"\nРезультат расшифровки: '{decrypted_message}'")

Как работает редукция

Чтобы понять, почему криптография на решётках работает так быстро, нужно разобрать два её главных математических движка: умножение в кольце (модуль $X^N+1$) и преобразование NTT.

В коде была строка умножения полиномов, где «хвост» массива отсекался и вычитался из начала: final_res[i] = (res[i] — res[i + N]) % Q. Зачем это нужно?

Когда мы перемножаем два полинома степени N-1, в результате получается огромный полином степени 2N-2. Нам нельзя позволять полиномам бесконечно расти, иначе шифрование превратится в неподъемную задачу. Поэтому математики договорились: все вычисления ведутся в кольце полиномов по модулю $X^N+1=0$.

Из этого уравнения следует важнейшее правило:

Что это значит на практике?

• Пример при N=4: Мы умножили полиномы и получили член 5X⁶.
• Раскладываем его: 5 ⋅ X⁴ ⋅ X².
• Заменяем X⁴ на -1: получаем -5X².

Таким образом, любой длинный «хвост» полинома (от степени N до 2N-2) просто загибается обратно, меняет свой знак на минус и складывается со стартовыми коэффициентами. Это гарантирует, что размер зашифрованного сообщения всегда строго ограничен и никогда не превысит длину N.

Почему в реальности используют NTT (Теоретико-числовое преобразование)

В коде выше использовалось обычное умножение полиномов «в лоб» через двойной цикл. Если N = 256, процессору нужно сделать 256 × 256 = 65 536 умножений. Это долго. А теперь представьте, что серверу нужно обрабатывать миллионы запросов в секунду. Архитектура «в лоб» (её сложность обозначается как O(N²)) создаст огромную нагрузку.

Чтобы решить эту проблему, применяют NTT (Number Theoretic Transform) — аналог Быстрого преобразования Фурье (FFT), но адаптированный для целых чисел по модулю Q.

Интеграция NTT

Для интеграции NTT нам необходимо использовать параметры, которые математически поддерживают это преобразование. В NTT используется так называемый первообразный корень из единицы степени 2N по модулю Q.

Чтобы код оставался простым и не требовал сотен строк высшей математики, мы перейдем на реальные параметры стандарта Kyber/ML-KEM:

• N = 256 (степень полинома)
• Q = 3329 (модуль)
• ζ = 17 (первообразный корень степени 256 по модулю 3329)

Ниже представлена обновленная и полностью рабочая программа на Python, где «тяжелое» умножение полиномов из прошлых шагов заменено на моментальное покоэффициентное умножение в NTT-домене.

Главные изменения в архитектуре:

1. Масштабируемость: Теперь размер полинома равен 256 (как в боевых стандартах), что позволяет за один раз зашифровать строку длиной до 32 символов.

2. Скорость: Функция poly_mul_ntt выполняет умножение за фиксированные N шагов в домене NTT, убирая ресурсоемкую вложенность циклов.

3. Авто-редукция: Математика NTT построена так, что при обратном преобразовании inv_ntt полином автоматически оказывается сокращенным по модулю X²⁵⁶ + 1. Дополнительно «срезать хвосты» руками больше не нужно.

import random

# Параметры Kyber (ML-KEM), поддерживающие NTT
N = 256       # Число коэффициентов
Q = 3329      # Модуль вычислений
HALF_Q = Q // 2
ZETA = 17     # Первообразный корень 256-й степени из единицы по модулю Q

# === ГЕНЕРАЦИЯ ТАБЛИЦЫ КОРНЕЙ ДЛЯ NTT (Алгоритм Кули-Тьюки) ===
def get_ntt_tables():
    """Генерирует степени корней для быстрого бабочкового преобразования"""
    powers = []
    # Нам нужны корни в правильном бинарно-инвертированном порядке
    for i in range(N):
        # Бинарная инверсия индекса (bit-reversal)
        rev_i = int(f"{i:08b}"[::-1], 2)
        powers.append(pow(ZETA, rev_i, Q))
    return powers

NTT_POWERS = get_ntt_tables()
INV_N = pow(N, Q - 2, Q) # Модульное обратное от N (для обратного NTT)

# === ФУНКЦИИ NTT И ОБРАТНОГО NTT ===

def ntt(poly):
    """Прямое NTT (Перевод полинома в область частот). Сложность: O(N log N)"""
    a = list(poly)
    t = N // 2
    k = 1
    while t > 0:
        for start in range(0, N, 2 * t):
            zeta = NTT_POWERS[k]
            k += 1
            for j in range(start, start + t):
                u = a[j]
                v = (a[j + t] * zeta) % Q
                a[j] = (u + v) % Q
                a[j + t] = (u - v) % Q
        t //= 2
    return a

def inv_ntt(poly):
    """Обратное NTT (Возврат из области частот в полином). Сложность: O(N log N)"""
    a = list(poly)
    t = 1
    k = N - 1
    while t < N:
        for start in range(0, N, 2 * t):
            zeta = NTT_POWERS[k]
            k -= 1
            for j in range(start, start + t):
                u = a[j]
                v = a[j + t]
                a[j] = (u + v) % Q
                # В обратном NTT вычитание умножается на инвертированную зету
                a[j + t] = ((u - v) * zeta) % Q
        t *= 2
    
    # Финальное масштабирование на 1/N
    for i in range(N):
        a[i] = (a[i] * INV_N) % Q
    return a

# === ОПЕРАЦИИ НАД ПОЛИНОМАМИ ===

def poly_add(p1, p2):
    return [(p1[i] + p2[i]) % Q for i in range(N)]

def poly_sub(p1, p2):
    return [(p1[i] - p2[i]) % Q for i in range(N)]

def poly_mul_ntt(p1, p2):
    """
    УМНОЖЕНИЕ С NTT:
    Вместо двойного цикла за O(N^2) мы переводим оба полинома в NTT,
    перемножаем их попарно за один цикл и возвращаем обратно.
    """
    # 1. Перевод в NTT-домен
    p1_ntt = ntt(p1)
    p2_ntt = ntt(p2)
    
    # 2. Покоэффициентное умножение (всего 256 итераций вместо 65536!)
    res_ntt = [(p1_ntt[i] * p2_ntt[i]) % Q for i in range(N)]
    
    # 3. Возврат в обычный вид (редукция по X^N + 1 происходит автоматически)
    return inv_ntt(res_ntt)

def gen_noise_poly():
    return [random.choice(&#91;-1, 0, 1]) % Q for _ in range(N)]

# === КРИПТОГРАФИЧЕСКИЕ ФУНКЦИИ (Ring-LWE) ===

def generate_keys():
    poly_A = [random.randint(0, Q - 1) for _ in range(N)]
    secret_S = gen_noise_poly()
    noise_E = gen_noise_poly()
    
    # b = A * s + e (используем NTT-умножение)
    poly_b = poly_add(poly_mul_ntt(poly_A, secret_S), noise_E)
    return (poly_A, poly_b), secret_S

def encrypt_string(text, public_key):
    poly_A, poly_b = public_key
    
    # Перевод строки в биты
    bits = []
    for char in text:
        bits.extend([int(b) for b in f"{ord(char):08b}"])
    
    if len(bits) > N:
        raise ValueError(f"Текст слишком длинный! Максимум {N // 8} байт (32 символа).")
    
    bits += [0] * (N - len(bits))
    
    # Сообщение m(x)
    poly_m = [(bit * HALF_Q) % Q for bit in bits]
    
    r = gen_noise_poly()
    e1 = gen_noise_poly()
    e2 = gen_noise_poly()
    
    # u = A * r + e1
    poly_u = poly_add(poly_mul_ntt(poly_A, r), e1)
    # v = b * r + e2 + m
    poly_v = poly_add(poly_add(poly_mul_ntt(poly_b, r), e2), poly_m)
    
    return (poly_u, poly_v)

def decrypt_string(ciphertext, secret_key):
    poly_u, poly_v = ciphertext
    
    # Очистка от шума: v - u * s
    poly_decrypted = poly_sub(poly_v, poly_mul_ntt(poly_u, secret_key))
    
    # Округление
    decoded_bits = []
    for coeff in poly_decrypted:
        dist_to_half = min(abs(coeff - HALF_Q), Q - abs(coeff - HALF_Q))
        dist_to_zero = min(coeff, Q - coeff)
        decoded_bits.append(1 if dist_to_half < dist_to_zero else 0)
            
    # Сборка байт в текст
    chars = []
    for i in range(0, len(decoded_bits), 8):
        byte = decoded_bits[i:i+8]
        if len(byte) < 8 or sum(byte) == 0:
            break
        char_code = int("".join(map(str, byte)), 2)
        chars.append(chr(char_code))
        
    return "".join(chars)

# === ТЕСТ ОПТИМИЗИРОВАННОЙ ПРОГРАММЫ ===
if __name__ == "__main__":
    # Благодаря N=256 мы можем шифровать строки до 32 символов
    message = "Lattice+NTT!" 
    print(f"Исходный текст: '{message}'")
    
    # Ключи
    pub_key, sec_key = generate_keys()
    
    # Шифрование через NTT
    cipher = encrypt_string(message, pub_key)
    print("\n[Успешно] Строка зашифрована с применением NTT.")
    
    # Расшифровка через NTT
    decrypted = decrypt_string(cipher, sec_key)
    print(f"Результат расшифровки: '{decrypted}'")

Число q = 3329 в криптографии на решётках (конкретно в стандарте Kyber / ML-KEM) — это не просто случайный модуль. Это ювелирно подобранная константа, которая одновременно обеспечивает криптографическую безопасность и техническую возможность запуска NTT.

Изменить это число можно, но любой другой модуль должен строго подчиняться жестким законам математики, иначе алгоритм либо станет уязвимым, либо перестанет работать.

Почему выбрано именно 3329?

Выбор этого числа обусловлен тремя фундаментальными причинами:

1. Условие для работы NTT (Теория чисел)

Чтобы для полинома степени N = 256 существовало быстрое преобразование NTT, модуль q обязательно должен быть простым числом, и должно выполняться математическое условие:

Удваиваем N (2 * 256 = 512). Проверяем число 3329:

Число 3328 идеально делится на 512 (3328 / 512 = 6.5 — стоп, нет, Kyber использует особую усеченную схему, где q — 1 делится на 256).

Давайте пересчитаем: 3329 — 1 = 3328, а 3328 = 256 * 13.

Это значит, что q ≡ 1 (mod 256). Благодаря этому в поле чисел по модулю 3329 гарантированно существует первообразный корень 256-й степени (им как раз является число ζ = 17). Без этого свойства «бабочка» NTT в коде просто выдавала бы хаотичные ошибочные данные.

2. Оптимизация под компьютерное железо

Число 3329 в двоичной системе требует для записи всего 12 бит (2¹¹ < 3329 < 2¹²).

• Любой коэффициент полинома гарантированно помещается в стандартный минимальный тип данных uint16 (16 бит).

• При перемножении двух коэффициентов (3329 X 3329) результат занимает не более 24 бит, что идеально вшивается в стандартный 32-битный регистр процессора (uint32) без риска переполнения. Это делает вычисления колоссально быстрыми.

3. Баланс безопасности и шума

Если сделать q слишком маленьким, то случайный шум при шифровании начнет накладываться друг на друга, и получатель не сможет отличить «0» от «1» (ошибка округления разрушит данные). Если сделать q слишком большим, шифротекст начнет весить слишком много, а сама задача LWE станет проще для взламывания суперкомпьютерами. Число 3329 — это идеальная «золотая середина» для решёток размерности 256.

Можно ли изменить этот модуль?

Да, можно, но придется полностью перестроить все параметры системы.

1. Если оставить NTT и размер полинома N = 256:
   Придется искать другие простые числа, удовлетворяющие условию q ≡ 1 (mod 256).

   • Например, в первых версиях Kyber использовалось число q = 7681 (7681 — 1 = 7680 = 256 * 30). Но разработчики отказались от него в пользу 3329, так как 3329 меньше, экономит память и работает быстрее.

2. Если взять случайное число (например, 3000):
   Программа выдаст ошибку или мусор при расшифровке. У числа 3000 нет первообразного корня нужной степени, функции ntt() и inv_ntt() математически разрушатся, а код потеряет свой главный козырь — скорость O(N log N).