EdDSA 与 Ed25519
EdDSA（Edwards 曲线数字签名算法）是一种现代、安全的数字签名算法，基于为性能优化的椭圆曲线，例如 255 位曲线 Curve25519 和 448 位曲线 Curve448-Goldilocks。出于性能考虑，EdDSA 签名分别使用椭圆曲线的 Edwards 形式 edwards25519 和 edwards448。EdDSA 算法基于 Schnorr 签名算法，其安全性依赖 ECDLP 问题的困难性。
RFC 8032 从技术上描述了 EdDSA 签名算法及其变体 Ed25519 和 Ed448。
EdDSA 密钥生成
Ed25519 和 Ed448 使用较短的私钥（分别为 32 或 57 字节）、较短的公钥（32 或 57 字节）和较短的签名（64 或 114 字节），同时具有较高的安全级别（分别为 128 位或 224 位）。
假设 EdDSA 算法所用的椭圆曲线带有生成元点 G，以及由 G 生成的 EC 点子群的阶 q。
EdDSA 密钥对由以下部分组成：
- 私钥（整数）：privKey
- 公钥（EC 点）：pubKey = privKey * G
私钥由称为 seed 的随机整数生成（其位长度应与曲线阶相近）。首先对 seed 进行哈希，然后清除与曲线余因子相对应的最低若干位（Ed25519 为 8，X448 为 4），再清除最高位并设置次高位。这些变换保证私钥始终属于曲线上同一个 EC 点子群，并且私钥始终具有相近的位长度（以防御基于时序的侧信道攻击）。Ed25519 的私钥为 32 字节，Ed448 的私钥为 57 字节。
公钥 pubKey 是椭圆曲线上的一个点，通过 EC 点乘法计算：pubKey = privKey * G（私钥乘以曲线的生成元点 G）。公钥编码为压缩 EC 点：将 y 坐标与 x 坐标的最低位（奇偶性）组合起来。Ed25519 的公钥为 32 字节，Ed448 的公钥为 57 字节。
EdDSA 签名
EdDSA 签名算法（RFC 8032）以文本消息 msg 和签名者的 EdDSA 私钥 privKey 为输入，输出一对整数 {R, s}。EdDSA 签名的工作方式如下（略有简化）：
EdDSA_sign(msg, privKey) --> { R, s }
- 计算 pubKey = privKey * G
- 以确定性方式生成秘密整数 r = hash(hash(privKey) + msg) mod q（此处略有简化）
- 将 r 乘以曲线生成元，计算其对应的公钥点：R = r * G
- 计算 h = hash(R + pubKey + msg) mod q
- 计算 s = (r + h * privKey) mod q
- 返回签名 { R, s }
生成的数字签名对于 Ed25519 为 64 字节（32 + 32 字节），对于 Ed448 为 114 字节（57 + 57 字节）。它包含压缩点 R 和整数 s，用于确认签名者知道 msg 和 privKey。
EdDSA 签名验证
EdDSA 签名验证算法（RFC 8032）以文本消息 msg、签名者的 EdDSA 公钥 pubKey 和 EdDSA 签名 {R, s} 为输入，输出一个布尔值（签名有效或无效）。EdDSA 验证的工作方式如下（略有简化）：
EdDSA_signature_verify(msg, pubKey, signature { R, s } ) --> valid / invalid
- 计算 h = hash(R + pubKey + msg) mod q
- 计算 P1 = s * G
- 计算 P2 = R + h * pubKey
- 返回 P1 == P2
工作原理
验证期间按如下方式计算点 P1：P1 = s * G。
签名期间，s = (r + h * privKey) mod q。现在替换上述方程中的 s：
- P1 = s * G = (r + h * privKey) mod q * G = r * G + h * privKey * G = R + h * pubKey
上述结果恰好就是另一个点 P2。如果点 P1 和 P2 是同一个 EC 点，就证明由私钥计算出的点 P1 与其相应公钥创建的点 P2 相匹配。
ECDSA 与 EdDSA 对比
比较 EdDSA 的签名与验证过程可以发现，EdDSA 比 ECDSA 更简单，也更容易理解和实现。对于密钥长度相近的曲线，两种签名算法具有相近的安全强度。对于最流行的曲线（如 edwards25519 和 edwards448），EdDSA 算法比 ECDSA 略快，但这在很大程度上取决于所用曲线和具体实现。与 ECDSA 不同，EdDSA 签名无法从签名和消息中恢复签名者的公钥。一般认为，大多数现代应用都适合采用 EdDSA。