Подписи CRYSTALS-Dilithium и Falcon

Подписи RSA и ECDSA взламываются алгоритмом Шора. Постквантовые подписи должны заменить их для сертификатов TLS, подписывания кода, подписывания электронной почты (S/MIME, PGP) и проверки подлинности обновлений программного обеспечения. NIST стандартизовал две схемы на основе решёток: ML-DSA и FN-DSA.

Dilithium основан на сложности задач Module-LWE и Module-SIS (задача короткого целочисленного решения). Доказательство стойкости построено в модели QROM (квантовая модель случайного оракула). Существуют три варианта: Dilithium2 (около 128 бит), Dilithium3 (около 192 бит) и Dilithium5 (около 256 бит). Путь формирования подписи прост и не требует выборки с отклонением.

Закрытый ключ: секретные матрицы s1, s2. Открытый ключ: t = As1 + s2. Для формирования подписи выберите случайное y; вычислите w = Ay; вычислите вызов c = H(mu || w1), где w1 = HighBits(w); вычислите z = y + cs1; если ||z|| или ||r0|| слишком велико, отклоните результат и повторите попытку. Результат: (z, c, hint).

Для проверки (z, c, hint) убедитесь, что ||z|| мало; вычислите w' = Az - ct; с помощью hint восстановите w1; проверьте c == H(mu || w1). Подсказка — это небольшое число битов из MakeHint(). Отклонение результатов не позволяет z раскрыть s1 — обоснование стойкости строится на аргументе «сначала прерывание, затем равномерное распределение».

ML-DSA-65 (Dilithium3, стойкость 192 бита): открытый ключ — 1952 байта, закрытый ключ — 4000 байт, подпись — 3293 байта. Для сравнения, ECDSA-P256 использует открытый ключ размером 64 байта и подпись размером 64 байта. Подписи Dilithium примерно в 40–50 раз больше, но устойчивы к квантовым атакам.

Falcon основан на решётках NTRU и использует гауссовский генератор над решёткой NTRU. Подписи значительно меньше, чем у Dilithium, но для формирования подписи требуется гауссовский генератор с плавающей точкой — его сложнее реализовать за постоянное время и безопасно запрограммировать.

Falcon-512 (стойкость 128 бит): открытый ключ — 897 байт, подпись — 666 байт, что значительно меньше, чем у Dilithium. Компромисс: Falcon сложнее безопасно реализовать (выборка по гауссовскому распределению уязвима для атак по времени выполнения). Он подходит для сред с ограниченной пропускной способностью, но требует тщательной реализации.

SPHINCS+ — схема подписей на основе хеш-функций и консервативный выбор, не опирающийся на структурные алгебраические предположения. Стойкость зависит только от стойкости хеш-функции. Размер подписи составляет около 8–50 KB, то есть она большая. Формирование подписи выполняется медленно. Схема используется там, где критична долгосрочная надёжность, а производительность вторична.

ML-DSA (Dilithium): общего назначения, простая реализация, подходит для сертификатов TLS и подписывания кода. FN-DSA (Falcon): среды с ограниченной пропускной способностью (Интернет вещей, LPWAN). SLH-DSA (SPHINCS+): крайне консервативный выбор для долгоживущих корней (автономные ключи CA, программный корень доверия).

Dilithium: выборка с отклонением может раскрывать информацию по времени выполнения ветвлений — используйте сравнение за постоянное время. Falcon: гауссовский генератор использует арифметику с плавающей точкой — обеспечьте детерминизм FP. Для обоих алгоритмов избегайте побочных каналов в арифметике многочленов. Используйте эталонные реализации из пакетов заявок NIST.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Все они опубликованы в августе 2024 года. Библиотеки OpenSSL 3.x, BoringSSL и liboqs (проект Open Quantum Safe) реализуют все три схемы.

В чём главное преимущество Falcon перед Dilithium?

ML-DSA (Dilithium): на основе решёток, простая реализация, подписи размером около 3 KB. FN-DSA (Falcon): на основе NTRU, подписи размером около 700 байт, сложная реализация. SLH-DSA (SPHINCS+): на основе хеш-функций, консервативная схема, большие подписи. Все стандартизованы в документах FIPS 204/205/206. Далее: переход на PQC с использованием гибридных подходов.