在公钥密码学,爱德华兹曲线数字签名算法(EdDSA)是一种数字签名方式,使用一种基于扭曲的爱德华兹曲线的施诺尔签名变种。[1]
其被设计为比现有的数字签名方式更快同时不牺牲安全性。Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe 和 Bo-Yin Yang等人的团队研发了这一算法[2],并将其参考实现发布为了公有领域软件。[3]
概要
以下是 EdDSA 的简化描述,忽略将整数和曲线点编码为位串的细节。关于完整的细节,请参见论文和RFC。[4][2][1]
一种EdDSA 签名方案是一种下列内容的组合:[4]:1–2[2]:5–6[1]:5–7
- 奇素数幂
上的有限域![{\displaystyle \mathbb {F} _{q))](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbb96e056c071d13fc7702013f9273e7f5cd88a7)
上的椭圆曲线
,其
关系点群
的阶数为
,其中
是一个大素数且
被称为辅因子
- 阶数为
的基点![{\displaystyle B\in E(\mathbb {F} _{q})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65507bc64c16669baeb8dcb78b49190a87a0220d)
- 有
位输出的密码学散列函数
,其中
,使得
的元素和
中的曲线点可以被以
位的字符串表示。
这些参数对于使用同一EdDSA签名方案的所有用户都是通用的。EdDSA签名方案的安全性关键取决于参数的选择,除了基点的任意选择之外,例如,Pollard Rho算法预计需要大约
次曲线相加才能计算离散对数,[5] 所以
必须足够大才能使其不可行,并且通常取值超过2200。[6]
的选择受限于
的选择,因为根据哈斯定理,
不能与
相差超过
。散列函数
在EdDSA安全性的正式分析中通常被建模为随机预言。
在 EdDSA 签名方案中,
- 公钥
- EdDSA公钥是一个曲线点
,编码为
位。
- 签名验证
- 公钥
对消息
的EdDSA签名是元组
,编码为
位,由满足下面的验证方程的曲线点
和整数
组成。
表示串接。
- 私钥
- EdDSA私钥是一个
位字符串
,其应该被均匀地随机选择。对应的公钥为
,其中
为通过将
的最低有效
位解释为小端字节序的整数得到。
- 签名
- 消息
的签名被确定地计算为
,其中
,
,且
这满足验证方程:
Ed25519
Ed25519是使用SHA-512(SHA-2)和Curve25519的EdDSA签名方式[2],其中:
![{\displaystyle q=2^{255}-19,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efb5112630883ccb8eddbdc762c54696bc78abc3)
是扭曲的爱德华兹曲线
,且![{\displaystyle c=3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da6c3ad0b12414cdd2dad18f1ebd555f89ae5ece)
为
中独特的一点,其
坐标为
,且
坐标为正数
“正数”根据位编码定义:
- “正”坐标是偶数坐标(最低有效位被清除)
- “负数”坐标是奇数坐标(最低有效位被设置)
为SHA-512,其
。
曲线
与被称为Curve25519的蒙哥马利曲线双有理等价。等价的是:[2][7]
性能
原作团队将Ed25519针对x86-64 Nehalem、Westmere处理器家族进行了优化x86-64。可以批量执行64个签名的验证,以获得更大的吞吐量。Ed25519 旨在提供与128位对称密码质量相当的抗攻击能力。[8]
公钥的长度为256位,签名的长度为512位。[9]
安全编码
Ed25519旨在避免使用依赖于秘密数据的分支条件或数组索引的实现,[2]:2[1]:40以缓解侧信道攻击。
与其他基于离散对数的签名方案一样,EdDSA 为每个签名使用一个唯一的、被称为“nonce”的秘密值。在DSA和ECDSA签名方案中,传统上,这个随机数是为每个签名随机生成的,如果随机数生成器在签名时被破坏并且是可预测的,则签名可能会泄漏私钥,就像Sony PlayStation 3固件更新签名密钥所发生的那样。[10][11][12][13]
相比之下,EdDSA 确定性地选择 nonce 作为私钥和消息的哈希值的一部分。因此,一旦生成私钥,EdDSA 就不再需要随机数生成器来进行签名,并且不存在用于生成签名的受损随机数生成器泄露私钥的风险。[2]:8
标准化与实施不一致
值得注意的是,EdDSA 有两项标准化工作,一项来自IETF,即信息性RFC 8032,另一项来自NIST,作为FIPS 186-5的一部分。[14]两个标准之间的差异已经被分析了,[15][16]并且有测试向量。[17]
软件
Ed25519 的显着用途包括OpenSSH、[18]GnuPG[19]及各种替代方案和OpenBSD的signify工具[20]。SSH协议中的Ed25519和Ed448使用已经得到标准化。[21]在2023年,FIPS 186-5 标准的最终版确定将Ed25519包含为一种批准的签名方案。[14]
Ed448
Ed448是使用SHAKE256和Curve448的EdDSA签名方式,定义于RFC 8032。其也已被FIPE 186-5标准的最终版本批准。[14]