EdDSA and Ed25519

Table of Contents

1 EdDSA 简介

EdDSABernstein 等人于 2011 年设计,它可以看作是 Schnorr 签名方案采用 Twisted Edwards Curve 时的变种。EdDSA 在 RFC8032 中被标准化。

目前 EdDSA 有两个方案:Ed25519 和 Ed448。Ed25519 采用的哈希函数为 SHA-512(SHA-2),曲线为 Curve25519;而 Ed448 采用的哈希函数为 SHAKE256(SHA-3),曲线为 Curve448

1.1 Twisted Edwards Curve, Curve25519

Twisted Edwards Curve 由下式定义: \[ax^{2}+y^{2}=1+dx^{2}y^{2}\]

对于 Curve25519, \(a=-1, d=-\frac{121665}{121666}\) ,也就是 Curve25519 曲线为: \[-x^2 + y^2 = 1 -\frac{121665}{121666} x^2 y^2\]

如果采用 Montgomery Curve 表示,则 Curve25519 还可以表示为: \[y^2 = x^3 + 486662 x^2 + x\]

关于作者是如何选择数字 486662 的?可以参考论文 Curve25519: new Diffie-Hellman speed records

The smallest positive choices for A are 358990, 464586, and 486662. I rejected A = 358990 because one of its primes is slightly smaller than 2^{252}, raising the question of how standards and implementations should handle the theoretical possibility of a user's secret key matching the prime; discussing this question is more difficult than switching to another A. I rejected 464586 for the same reason. So I ended up with A = 486662.

2 EdDSA, Ed25519

2.1 11 个参数

EdDSA 一共定义了 11 个参数。对于 Ed25519,这 11 个参数分别为:

+-----------+-------------------------------------------------------+
| Parameter | Value                                                 |
+-----------+-------------------------------------------------------+
|     p     | p of edwards25519 in [RFC7748] (i.e., 2^255 - 19)     |
+-----------+-------------------------------------------------------+
|     b     | 256                                                   |
+-----------+-------------------------------------------------------+
|  encoding | 255-bit little-endian encoding of {0, 1, ..., p-1}    |
|  of GF(p) |                                                       |
+-----------+-------------------------------------------------------+
|    H(x)   | SHA-512(x) [RFC6234]                                  |
+-----------+-------------------------------------------------------+
|     c     | base 2 logarithm of cofactor of edwards25519 in       |
|           | [RFC7748] (i.e., 3)                                   |
+-----------+-------------------------------------------------------+
|     n     | 254                                                   |
+-----------+-------------------------------------------------------+
|     d     | d of edwards25519 in [RFC7748] (i.e., -121665/121666  |
|           | = 370957059346694393431380835087545651895421138798432 |
|           | 19016388785533085940283555)                           |
+-----------+-------------------------------------------------------+
|     a     | -1                                                    |
+-----------+-------------------------------------------------------+
|     B     | (X(P),Y(P)) of edwards25519 in [RFC7748] (i.e., (1511 |
|           | 22213495354007725011514095885315114540126930418572060 |
|           | 46113283949847762202, 4631683569492647816942839400347 |
|           | 5163141307993866256225615783033603165251855960))      |
+-----------+-------------------------------------------------------+
|     L     | order of edwards25519 in [RFC7748] (i.e.,             |
|           | 2^252+27742317777372353535851937790883648493).        |
+-----------+-------------------------------------------------------+
|   PH(x)   | x (i.e., the identity function)                       |
+-----------+-------------------------------------------------------+

2.2 生成私钥和公钥

EdDSA 的私钥是 \(b\) 个比特位的随机串,一般记为 \(k\) 。

为了计算公钥,我们对私钥进行哈希运算,确保结果占 \(2b\) 比特位,得结果 \(H(k) = (h_0, h_1, ..., h_{2b-1})\) 。记: \[s \triangleq 2^n + \sum_{c \le i \lt n} 2^i \cdot h_i\] EdDSA 的公钥记为 \(A\) ,由下式得到: \[A \triangleq s \cdot B\]

特别地,对于 Ed25519( \(b=256,n=254,c=3\) ),哈希运算为 SHA-512,其公钥可以用下式计算: \[A = \left(2^{254} + \sum_{i=3}^{253} 2^i \cdot h_i \right) \cdot B\] 式中 \(B\) 是曲线的 Base Point(Generator)。

注: Ed25519 公钥从私钥哈希 \(\text{SHA-512}(k)\) 的“左半部分”计算而来, 因为 \(\text{SHA-512}(k)\) 的输出是 512 个比特位,而上式中 \(h_i\) 中 \(i\) 最大值为 253。后文我们可以看到私钥哈希 \(\text{SHA-512}(k)\) 的“右半部分”用于签名。

2.3 生成签名

记: \[r \triangleq H(h_b || ... || h_{2b-1} || M)\] 其中 \(||\) 表示的是 concatenation。显然计算 \(r\) 时只使用了私钥哈希 \(H(k)\) 的“右半部分”,因为只取了 \(H(k)\) 的 \(b\) 到 \(2b-1\) 位。

定义: \[R \triangleq r \cdot B\] 定义: \[S \triangleq (r + s \cdot H(R||A||M)) \pmod L\] 式中的 \(s\) 在前一节中有定义,是利用私钥哈希 \(H(k)\) 的“左半部分”计算而来。

得到的 \((R,S)\) 就是 EdDSA 签名。 \(R\) 是曲线上的点,而 \(S\) 是大整数。

对于 Ed25519,则取哈希函数为 \(\text{SHA-512}\) ,取 \[b=256, L = 2^{252} + 27742317777372353535851937790883648493\] 即可。

注:和其它签名算法(如 DSA,ECDSA)不同, EdDSA 签名算法并没有引入一次一用的随机数。

2.4 验证签名

有了签名数据 \((R,S)\) 和公钥 \(A\) ,如果下面成立: \[(2^c \cdot S) \cdot B = 2^c \cdot R + (2^c \cdot H(R||A||M)) \cdot A\] 则通过签名验证。对于 Ed25519,则取哈希函数为 \(\text{SHA-512}\) ,取参数 \(c=3\) 即可。

2.4.1 证明

EdDSA 的证明:

\begin{aligned}2^{c}SB &=2^{c}(r+H(R||A||M)s)B \\ &=2^{c}rB+2^{c}H(R||A||M)sB \\ &=2^{c}R+2^{c}H(R||A||M)A \end{aligned}

3 Ed25519 实现

https://ed25519.cr.yp.to/software.html 中可以找到 Ed25519 的实现,其中包含了 Python 的一个参考性实现。

4 参考

Author: cig01

Created: <2020-07-25 Sat>

Last updated: <2020-12-01 Tue>

Creator: Emacs 27.1 (Org mode 9.4)