Ed25519

摘要

EdDSA算法本身是安全的，但有些EdDSA库的实现是不安全的，有可能会导致私钥泄露。

密码学背景

Edwards曲线数字签名算法 (EdDSA)是一种数字签名方案，使用了Schnorr签名的变种，基于扭曲Edwards曲线。

EdDSA签名算法及其变种Ed25519和Ed448在RFC 8032有完整的技术性描述。

私钥: k

k = RNG生成的随机数

衍生的一个整数: a

计算私钥的摘要：

$$H(k)=(h_0,h_1,...,h_{2b-1})$$

然后计算整数a:

$$a = 2^{b-2} + \sum_{\substack 3⩽i⩽b-3} 2^ih_i \in \lbrace {2^{b-2},2^{b-2}+8,...,2^{b-1}-8} \rbrace$$

后面你会发现，这个a也是一个不能泄露的数，它基本等同于私钥。

公钥: A

$$A = aB$$

B为曲线的基点

签名生成: (R,s)

对于消息M:

$$r=H(h_b,...,h_{2b-1},M) \in 0,1,...2^{2b}-1$$

$$R=rB$$

$$s=(r+H(R,A,M)a)\bmod l$$

l是点B生成的子群的阶。

现在我们得到了签名(R,s). 显然，如果你知道了a则可以计算任意签名, 等同于知道了私钥k。

验证签名

$$if\space 8sB == 8R+8H(R,A,M)A$$

​

不安全的实现

想象一下这种函数实现:

//PSEUDO CODE
func sign(message M, publicKey A){    
    R = rB
    S=(r+H(R,A,M)a) mod l
    return (R,S)    
}

该sign()函数允许调用者输入任意消息和公钥。如果有人使用了相同的M但不同的A，则他可以计算出整数a，私钥k的等价物。

$$a=(S-S')[H(R,A,M)-H(R,A',M)]^{-1} \bmod l$$

有很多库有类似的不安全实现，查看列表.

总结

这是对Ed25519对不安全实现，虽然并不意味着一定会出问题，但还是要尽可能规范。.

开发者应该尽可能熟悉底层的密码学知识以避免类似攻击。

参考

https://twitter.com/kostascrypto/status/1535579208960790528

https://datatracker.ietf.org/doc/html/rfc8032