签名与EdDSA碰撞的可能性

Question

以EdDSA为例，给定数据有效载荷的签名长度为512位，如果另有一个512位值也是有效签名，那么碰撞的概率是多少？

使用对称密码，我们知道在整个空间中只有一个密钥可以有效地解密使用相同密钥加密的数据。

Can我们可以证明，对于给定的有效负载和给定的私钥，在512位签名空间？中只有一个有效签名，即不存在其他可以与创建签名的私钥相对应的公钥验证的签名。

Answer 1

我们是否可以证明，对于给定的有效载荷和私钥，512位签名空间中只有一个有效签名？

不是的。如果您认为EdDSA验证是一个合法的签名者可以生成一个给定消息的多个签名，那么所有签名都将通过EdDSA验证。但是，只有使用EdDSA签名过程生成的签名才能通过无因素验证。

有关如何生成其他有效签名的更多详细信息，请参见在这个答案中。

关于更广泛的问题：

以EdDSA为例，给定数据有效载荷的签名长度为512位，如果另有一个512位值也是有效签名，那么碰撞的概率是多少？

专门要求只通过无代码验证(为了避免由上述技术生成的其他有效签名)，应该为r的每个可能值提供一个有效的D6。由于R完全依赖于r和0 \le r < L，因此至少存在L可能的有效签名，其中L是大素数子群的阶。对于ed25519，L = 2^{252}+27742317777372353535851937790883648493