准备好迎接FN-DSA：比Dilithium慢，但密钥/密文更小
- billatnapier
- 发布于 2025-03-29 16:42
- 阅读 22
本文介绍了NIST即将定义的第三个后量子密码数字签名标准FN-DSA，它基于FALCON方法。FALCON的性能比Dilithium慢，但密钥大小和密文更小。文章对比了Falcon与Dilithium、RSA等算法在密钥大小、签名大小和性能上的差异，并提供了NTRU算法的简单示例和C代码实现。
准备好迎接 FN-DSA：比 Dilithium 慢，但密钥/密文更小
目前，我们有两个主要的 PQC 数字签名标准。它们是 FIPS 204（Dilithium — ML-DSA）和 FIPS 205（SPHINCS+ — SLH-DSA）。现在，NIST 正在定义第三个标准：FIPS 206，它基于 FALCON 方法。它将被命名为 FN-DSA — 基于 NTRU 格的数字签名算法的 FFT（快速傅里叶变换）。基线是 FALCON 在性能上比 Dilithium 慢，但密钥大小和密文要小得多。
你可能知道，我们大多数公钥方法都受到量子计算机的威胁。这包括 ECC、RSA 和离散对数方法。因此，在未来十年里，我们可能会看到这些方法迁移到量子稳健的方法上——并见证 PQC（后量子密码学）的兴起。
性能和密钥长度
对于 Falcon-512（它具有与 RSA-2048 等效的安全性），我们生成一个 897 字节的公钥，一个 1,281 字节的私钥和一个 690 字节的签名大小，而 FALCON-1024 提供一个 1,793 字节的公钥，一个 2,305 字节的私钥和一个 1,313 字节的签名大小 [ here]：
Falcon 使用 NTRU 作为非对称加密方法，并且经过基准测试，加密速度是 RSA 的两倍，解密速度是 RSA 的三倍。NTRU 是一种不基于因子分解（RSA）、离散对数或椭圆曲线方法的公钥方法。总的来说，与 Dilithium 相比，它在密钥生成方面相对较慢，但在密钥签名和验证方面性能更接近：
对于 ECDSA、RSA、Ed25519 和 Ed448，我们有：
Method Public key size (B) Private key size (B) Signature size (B) Security level
------------------------------------------------------------------------------------------------------
Ed25519 32 32 64 1 (128-bit) EdDSA
Ed448 57 57 112 3 (192-bit) EdDSA
ECDSA 64 32 48 1 (128-bit) ECDSA
RSA-2048 256 256 256 1 (128-bit) RSA以下是对数字签名 PCQ 方法的分析：
Method Public key size Private key size Signature size Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) Lattice
Crystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) Lattice
Crystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) Lattice
Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) Lattice
Falcon 1024 1,793 2,305 1,330 5 (256-bit) Lattice
Rainbow Level Ia (Oil-and-Vineger) 161,600 103,648 66 1 (128-bit) Multivariate (UOV)
Rainbow Level IIIa 861,400 611,300 164 3 (192-bit) Multivariate (UOV)
Rainbow Level Vc 1,885,400 1,375,700 204 5 (256-bit) Multivariate (UOV)
Sphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-based
Sphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-based
Sphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-based
Picnic 3 Full 49 73 71,179 3 (192-bit) Symmetric
GeMSS 128 352,188 16 33 1 (128-bit) Multivariate (HFEv-)
GeMSS 192 1,237,964 24 53 1 (128-bit) Multivariate (HFEv-)对于 M4（ARM Cortex-M4 开发）[1] 上的性能，以每秒 CPU 操作次数衡量。请注意，[1] 中未执行 Rainbow 评估，因此已使用 LUOV（一种油和醋方法）来指示性能水平：
Method Key generation Sign Verify
----------------------------------------------------------------
Crystals Dilithium 2 (Lattice) 36,424 61,312 40,664
Crystals Dilithium 3 50,752 81,792 55,000
Crystals Dilithium 5 67,136 104,408 71,472
Falcon 512 (Lattice) 1,680 2,484 512
Falcon 1024 1,680 2,452 512
Rainbow Level Ia (Oil-and-Vineger) 2,969 4,720 2,732
Rainbow Level IIIa 3,216 3,224 1,440
Rainbow Level Vc 3,736 6,896 4,928
Sphincs SHA256-128f Simple 2,192 2,248 2,544
Sphincs SHA256-192f Simple 3,512 3,640 3,872
Sphincs SHA256-256f Simple 5,600 5,560 5,184对于 ARM Cortex-M4 设备上的堆栈内存大小 [1]，以字节为单位衡量。请注意，[1] 中未执行 Rainbow 评估，因此已使用 LUOV（一种油和醋方法）来指示性能水平：
Method Memory (Bytes)
-------------------------------------------------
Crystals Dilithium 2 (Lattice) 13,948
Crystals Dilithium 3 13,756
Crystals Dilithium 5 13,852
Falcon 512 (Lattice) 117,271
Falcon 1024 157,207
Rainbow Level Ia (Oil-and-Vineger) 404,920
Rainbow Level IIIa 405,412
Rainbow Level Vc 405,730
Sphincs SHA256-128f Simple 4,668
Sphincs SHA256-192f Simple 4,676
Sphincs SHA256-256f Simple 5,084方法
因此，让我们举一个简单的例子来说明 NTRU 的工作原理。总的来说，Falcon 基于 Gentry、Peikert 和 Vaikuntanathan 方法来生成基于格的签名方案，以及一个 trapdoor sampler — 快速傅里叶采样。最初，我们选择三个参数：N、p 和 q。为了生成密钥对，我们选择两个多项式：f 和 g。由此我们计算得出：
并且其中 f 和 f q 是私钥。公钥是：
Bob 和 Alice 同意共享 N（它限制了最大的多项式幂）、p 和 q，然后 Bob 生成两个短多项式（f 和 g），并由此生成他的密钥对。这些多项式的系数为 -1、0 和 1。例如，当 N =11，p =3 且 q =32 时。如果 Bob 选择以下值：
f =[−1,1,1,0,−1,0,1,0,0,1,−1]
那么作为多项式表示：
f =−1+ x + x² − x ⁴+ x ⁶+ x⁹ − x ¹⁰
然后选择 g：
g =−1+ x ²+ x ³+ x ⁵− x ⁸− x ¹⁰
然后我们应该能够计算 f 对于 (mod p) 和 (mod q) 的逆。因此：
f ⋅ f p(mod p)=1
f ⋅ f q(mod q)=1
使用逆函数，我们得到 [ here]：
f p =[9,5,16,3,15,15,22,19,18,29,5]
f p =9 x¹⁰ +5 x ⁹+16 x ⁸+3 x ⁷+15 x ⁶+15 x ⁵+22 x ⁴+19 x ³+18 x ²+29 x +5
然后公钥变为：
h = p ⋅ f q. f(mod q)
在这种情况下，我们得到：
f q ⋅ g =[−5,−9,−1,−2,11,12,13,3,22,15,16,29,60,19,−2,−7,−36,−40,−50,−18,−30]
为了创建一个环，我们然后除以 x^{N}−1 并得到：
H (Bob's Public Key): [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]私钥是 f 和 f q。
要加密，我们取 Bob 的公钥 (h)、一个随机多项式 (r) 和一条消息 (M)，然后计算：
Enc = r ⋅ h + M
要解密，首先我们将 Bob 的私钥 f q 乘以并取 (mod q)：
Dec =( r ⋅ h + M). f(mod q)
这会给出：
Dec =( p ⋅ r ⋅ f q ⋅ g + M). f(mod q)
并且由于 (f q. f)(mod q) 为 1，我们得到：
Dec =( p ⋅ r ⋅ g + M ⋅ f)
最后，我们将 f p(mod p) 乘以：
Dec =( p ⋅ r ⋅ g + M ⋅ f). f p(mod p)
这将是：
Dec = p ⋅ r ⋅ f ⋅ f p + M ⋅ f ⋅ f p(mod p)
并且由于我们有一个 p 的乘数，我们将得到第一个项的零值，因为我们有 (mod p) 操作：
Dec =0+ M ⋅ f ⋅ f p(mod p)
并且由于 f ⋅ f p(mod p) 将为 1，我们得到：
Dec = M
参数的示例值为：
- 最小安全性：N =167，p =3，q =128。
- 良好安全性：N =251，p =3，q =128。
- 强安全性：N =347，p =3，q =128。
- 卓越安全性：N =503，p =3，q =256。
编码
编码是 [ here]：
namespace Falcon
{
using Org.BouncyCastle.Pqc.Crypto.Falcon;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var msg="Hello";
var method="Falcon2";
if (args.Length >0) msg=args[0];
if (args.Length >1) method=args[1];
var random = new SecureRandom();
var keyGenParameters = new FalconKeyGenerationParameters(random, FalconParameters.falcon_512);
if (method=="Falcon1024") keyGenParameters = new FalconKeyGenerationParameters(random, FalconParameters.falcon_1024);
var keyPairGen = new FalconKeyPairGenerator();
keyPairGen.Init(keyGenParameters);
var keyPair = keyPairGen.GenerateKeyPair();
var pubKey = (FalconPublicKeyParameters)keyPair.Public;
var privKey = (FalconPrivateKeyParameters)keyPair.Private;
// Signing // 签名
var aliceSign = new FalconSigner();
aliceSign.Init(true, privKey);
var signature = aliceSign.GenerateSignature(System.Text.Encoding.UTF8.GetBytes(msg));
// verify signature // 验证签名
var bobVerify = new FalconSigner();
bobVerify.Init(false, pubKey);
var rtn = bobVerify.VerifySignature(System.Text.Encoding.UTF8.GetBytes(msg), signature);
Console.WriteLine("Message:\t{0}",msg);
Console.WriteLine("Method:\t\t{0}",method);
Console.WriteLine("\nPublic key (length):\t{0} bytes",pubKey.GetEncoded().Length);
Console.WriteLine("Alice Public key (first 50 bytes)):\t{0}",Convert.ToHexString(pubKey.GetEncoded())[..100]);
Console.WriteLine("\nPrivate key (length):\t{0} bytes",privKey.GetEncoded().Length);
Console.WriteLine("Alice Private key (first 50 bytes)):\t{0}",Convert.ToHexString(privKey.GetEncoded())[..100]);
Console.WriteLine("\nSignature (length):\t{0} bytes",signature.Length);
Console.WriteLine("Signature (first 50 bytes):\t\t{0}",Convert.ToHexString(signature)[..100]);
Console.WriteLine("\nVerified:\t{0}",rtn);
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}一个示例运行 [ here]：
Message: Post Quantum Crypto
Method: Falcon512
Public key (length): 896 bytes
Alice Public key (first 50 bytes)): 33AE8162CE525CAB957E55B247E155844595285D1D48593FA4242BD4193CFADAF1E988737026D133DF875FB63EC652AE325E
Private key (length): 1280 bytes
Alice Private key (first 50 bytes)): FBFFC1E3FF02F811840B9141FFE0C3043079EBCEFBEC10040402BDFC0FC30FEF0310210307B27E17F03C009EC1F821C007D1
Signature (length): 654 bytes
Signature (first 50 bytes): 3924784F35D2A8ACF72AF51448B40ACE2E8B32AFC162DAB81AE34466C74501E0BCA0A101587310FED69BEE910E072F2F40A1
Verified: True结论
Falcon 在性能上比 Dilithium 慢，但密钥长度和密文要小得多：
Method Public key size Private key size Signature size Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) Lattice
Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) Lattice参考文献
[1] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: 在 ARM Cortex-M4 上测试 NIST PQC
- 原文链接： billatnapier.medium.com/...
- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
