FN-DSA и ML-DSA — две схемы подписи на решётках, которые NIST выбрал в 2022 году. ML-DSA (на основе CRYSTALS-Dilithium) стала стандартом FIPS 204 в августе 2024 года. FN-DSA, как NIST называет Falcon, стандартизируется в виде FIPS 206; в октябре 2026 года этот стандарт всё ещё оставался проектом. Falcon гораздо компактнее, а ML-DSA гораздо проще правильно реализовать.
Коротко о главном
| FN-DSA-512 (Falcon-512) | ML-DSA-44 | FN-DSA-1024 (Falcon-1024) | ML-DSA-87 | |
|---|---|---|---|---|
| Категория стойкости | 1 | 2 | 5 | 5 |
| Открытый ключ | 897 байт | 1 312 байт | 1 793 байта | 2 592 байта |
| Подпись | 666 байт (с дополнением) | 2 420 байт | 1 280 байт (с дополнением) | 4 627 байт |
| Открытый ключ + подпись | 1 563 байта | 3 732 байта | 3 073 байта | 7 219 байт |
| Семейство решёток | NTRU | Module-LWE / Module-SIS | NTRU | Module-LWE / Module-SIS |
| Арифметика при подписании | С плавающей точкой (выборка из дискретного гауссова распределения) | Только целые числа | С плавающей точкой | Только целые числа |
| Стандарт | Проект FIPS 206 | FIPS 204 (окончательный, 2024) | Проект FIPS 206 | FIPS 204 |
| X.509 | Ещё не стандартизировано | RFC 9881 | Ещё не стандартизировано | RFC 9881 |
Размеры Falcon взяты из спецификации Falcon (подписи можно также записывать в сжатой кодировке переменной длины, не более 752 и 1 462 байт); размеры ML-DSA — из таблицы 2 FIPS 204. У ML-DSA-65 (категория 3) нет аналога среди вариантов Falcon.
Почему важен размер
Falcon строит короткий вектор в решётке NTRU с помощью лазейки (trapdoor) и быстрой фурье-выборки (fast Fourier sampling), и это даёт наименьший суммарный размер открытого ключа и подписи среди всех постквантовых подписей NIST: около 1,6 КБ для категории 1 против 3,7 КБ у ML-DSA-44. В цепочке сертификатов TLS, где каждый сертификат содержит открытый ключ и подпись, а рукопожатие добавляет ещё подписи и SCT, эта разница отделяет цепочку, которая вырастает примерно вдвое, от цепочки, которая вырастает вчетверо. DNSSEC, где подписи должны помещаться в UDP-ответы, и блокчейны, где за каждый байт платят комиссию, ощущают это ещё сильнее.
Почему главная трудность — реализация
Алгоритм подписи Falcon делает выборку из дискретного гауссова распределения на решётке с помощью арифметики с плавающей точкой. Из-за этого возникают три проблемы, которых нет у ML-DSA:
- Постоянное время выполнения. На некоторых процессорах время операций с плавающей точкой зависит от данных, а эмулировать их в целых числах медленно; исследовательские атаки показали, что утечки по времени в процедуре выборки раскрывают ключи.
- Тестируемость. Из-за округления две правильные реализации могут выдавать разные подписи для одних и тех же входных данных, поэтому тесты с известными ответами (known-answer tests) не выявят слегка смещённую процедуру выборки, а смещённая процедура по-прежнему выдаёт верные подписи, хотя и раскрывает сведения о ключе. В сентябре 2026 года команда NIST, которая работает над FIPS 206, предложила процедуру подписи с фиксированной точкой именно для того, чтобы реализации стали детерминированными и тестируемыми.
- Переносимость. Встраиваемым процессорам без блока операций с плавающей точкой нужна программная эмуляция, которая снижает скорость и увеличивает размер кода.
ML-DSA использует только целочисленную арифметику по модулю 8380417 и выборку с отклонением (rejection sampling); её легко реализовать с постоянным временем выполнения, а её результаты полностью определены в FIPS 204. Проверка проста для обеих схем, а у Falcon она особенно быстрая: эталонная реализация команды Falcon показывает около 27 900 проверок и 5 900 подписей Falcon-512 в секунду на Intel Core i5-8259U с частотой 2,3 ГГц. На одном ядре Apple M4 Max переносимый код ML-DSA-44 из OpenSSL 3.6.5 показал около 20 800 проверок и 3 900 подписей в секунду. Машины разные, поэтому воспринимайте эти цифры как порядок величин, а не как прямое сравнение.
Статус стандартов
- ML-DSA: окончательный стандарт с 13 августа 2024 года (FIPS 204); есть идентификаторы для X.509 (RFC 9881), профили для CMS и OpenPGP, включение в CNSA 2.0 (ML-DSA-87) и прошедшие валидацию модули.
- FN-DSA: в июле 2022 года NIST объявил, что стандартизирует Falcon, и запланировал FIPS 206 после FIPS 204 и 205. В 2025 году сотрудники NIST сообщили, что первый публичный проект по сути написан и ожидает одобрения; на октябрь 2026 года окончательного стандарта нет, а предложение о фиксированной точке, сделанное в сентябре 2026 года, показывает, что спецификация всё ещё меняется. Черновики IETF для FN-DSA в JOSE, COSE и X.509 следуют за изменениями FIPS.
Поскольку FIPS 206 может отличаться от спецификации Falcon третьего раунда, реализации, написанные сегодня, возможно, придётся изменить, чтобы они соответствовали окончательному стандарту.
Что когда выбирать
- Постквантовые подписи общего назначения сегодня: ML-DSA (44 или 65).
- Внедрения, где главное — соответствие требованиям (FIPS 140-3, CNSA 2.0): ML-DSA; реализации FN-DSA не могут пройти валидацию, пока FIPS 206 не станет окончательным.
- Протоколы с большим числом сертификатов в будущем (цепочки TLS, DNSSEC, обновления IoT-устройств с ограниченными ресурсами): следите за FN-DSA; скорее всего, именно она позволит удержать накладные расходы на подписи в разумных пределах, не меняя структуру протокола.
- Оборудование без поддержки плавающей точки или со строгими требованиями к защите от атак по побочным каналам: ML-DSA или Falcon, но только с проверенной целочисленной реализацией с постоянным временем выполнения.
- Долгоживущие корневые сертификаты, где размер не важен: SLH-DSA, стойкость которой опирается только на хеш-функции, или ML-DSA; небольшой размер подписей FN-DSA там ничего не даёт.
Заметки о миграции
- Проектируйте с расчётом на криптографическую гибкость: передавайте идентификаторы алгоритмов, не закладывайтесь на фиксированный размер подписи и будьте готовы добавить FN-DSA как второй постквантовый вариант рядом с ML-DSA.
- Прототипируйте осторожно: используйте библиотеки, которые реализуют процедуру выборки Falcon с постоянным временем выполнения, и помечайте их результаты как созданные до выхода стандарта; не поставляйте их в продуктах, где требуется стандарт.
- Измерьте бюджет размера своего протокола с ML-DSA уже сейчас: если она в него укладывается, FN-DSA там может так и не понадобиться.
- Следите за окончательной версией FIPS 206: названия параметров, кодировки и процедура подписи могут отличаться от Falcon третьего раунда, и тестовые векторы соответственно изменятся.
- Помните о гибридах: на переходный период составные подписи объединяют постквантовую схему с ECDSA или EdDSA, какую бы схему на решётках вы ни выбрали.