3. EdDSA Algorithm (EdDSA 算法)

EdDSA 是一个具有 11 个参数的数字签名系统。

具有 11 个输入参数的通用 EdDSA 数字签名系统不打算直接实现。选择参数对于安全和高效的操作至关重要。相反, 您应该实现 EdDSA 的特定参数选择 (例如 Ed25519 或 Ed448), 有时会稍微泛化以实现代码重用来覆盖 Ed25519 和 Ed448。

因此, 通用 EdDSA 的精确解释对实现者并不特别有用。为了背景和完整性, 这里给出了通用 EdDSA 算法的简洁描述。

某些参数的定义 (如 n 和 c) 可能有助于解释算法中一些不直观的步骤。

此描述紧密遵循 [EDDSA2]。

EdDSA 有 11 个参数:

一个奇素数幂 p。EdDSA 使用有限域 GF(p) 上的椭圆曲线。
一个整数 b, 满足 2^(b-1) > p。EdDSA 公钥恰好有 b 位, EdDSA 签名恰好有 2*b 位。建议 b 是 8 的倍数, 因此公钥和签名长度是整数个八位字节。
有限域 GF(p) 元素的 (b-1) 位编码。
一个密码学哈希函数 H, 产生 2*b 位输出。推荐使用保守的哈希函数 (即创建碰撞是不可行的哈希函数), 并且对 EdDSA 的总成本没有太大影响。
一个整数 c, 为 2 或 3。秘密 EdDSA 标量是 2^c 的倍数。整数 c 是所谓的辅因子 (cofactor) 的以 2 为底的对数。
一个整数 n, 满足 c <= n < b。秘密 EdDSA 标量恰好有 n + 1 位, 最高位 (2^n 位置) 总是设置的, 最低 c 位总是清除的。
GF(p) 的一个非平方元素 d。通常的建议是取最接近零的值, 使得产生可接受的曲线。
GF(p) 的一个非零平方元素 a。为了获得最佳性能, 通常的建议是: 如果 p mod 4 = 1, 则 a = -1; 如果 p mod 4 = 3, 则 a = 1。
集合 E 的一个元素 B != (0,1), 其中 E = { (x,y) 是 GF(p) x GF(p) 的成员, 满足 a * x^2 + y^2 = 1 + d * x^2 * y^2 }。
一个奇素数 L, 满足 [L]B = 0 和 2^c * L = #E。数字 #E (曲线上的点数) 是为椭圆曲线 E 提供的标准数据的一部分, 或者可以计算为 cofactor * order。
一个"预哈希" (prehash) 函数 PH。PureEdDSA 意味着 EdDSA 中 PH 是恒等函数, 即 PH(M) = M。HashEdDSA 意味着 EdDSA 中 PH 生成短输出, 无论消息多长; 例如, PH(M) = SHA-512(M)。

曲线上的点在加法下形成一个群, (x3, y3) = (x1, y1) + (x2, y2), 公式为

         x1 * y2 + x2 * y1                y1 * y2 - a * x1 * x2
x3 = --------------------------,   y3 = ---------------------------
     1 + d * x1 * x2 * y1 * y2          1 - d * x1 * x2 * y1 * y2

群中的中性元素是 (0,1)。

与许多其他用于密码学应用的曲线不同, 这些公式是"完备的"; 它们对曲线上的所有点都有效, 没有例外。特别是, 对于所有输入点, 分母都是非零的。

存在更高效的公式, 仍然是完备的, 使用齐次坐标来避免昂贵的模 p 求逆。参见 [Faster-ECC] 和 [Edwards-revisited]。

3. EdDSA Algorithm (EdDSA 算法)​

3. EdDSA Algorithm (EdDSA 算法)