ECC算法

对TLS1.3中用到的ECC相关算法，比如ECDH, ECDSA, X25519等进行一下基础说明，起码知道group、curve之类的是什么意思。

1. 椭圆曲线(Elliptic Curves)

椭圆曲线的Weierstrass标准形式：
$y^{2} = x^{3} + a x + b$
$4 a^{3} + 27 b^{2}! = 0$

定义0表示椭圆曲线上的无限远点，这样组成的椭圆曲线是这样的：
$Missing or unrecognized delimiter for \left$

2. 群(Group)

$G$ 是一个集合，在集合中定义一个对两个元素的操作，记为"加",用+表示，集合中两个元素a和b,"加"操作表示为 $a + b$ ，如果 $a + b$ 这个操作满足一下4个特性， $G$ 就是一个群(Group):

闭合性closure: a, b是 $G$ 的元素， $a + b$ 也是；
结合性associativity: $(a + b) + c = a + (b + c)$
存在单位元identity element 0, 有 $a + 0 = 0 + a = a$
每个元素都有一个相反数，对每个元素a都存在b使 $a + b = 0$ , b就是a的相反数，可以表示为 $- a$

如果再加一条特性：

交换律： $a + b = b + a$
这样的群就要阿贝尔群(Abelian Group)

这个”加+”操作，也可以用”乘*”来表示，这个操作只是表示集合上两个元素的一个操作，此时

$a \cdot b$ 也是 $G$ 上的一个元素；
$(a \cdot b) \cdot c = a \cdot (b \cdot c)$
单位元1， $a \cdot 1 = 1 \cdot a = a$
$a \cdot b = 1$ ， b可以表示为 $a^{- 1}$

在讨论ECC的时候，一些旧的文献通常用+，新的通常用*，另外，在密码学中讨论加密强度的时候，通常按照指数(幂)、读书来讨论，比如长听到取离散对数问题。本文都用+来表示。

3. 椭圆曲线上的群

可以定义一个在椭圆曲线上的群 $G$ ：

一个椭圆曲线上的点是 $G$ 中的元素;
单位元定义为无穷远处的点0
一个点P的相反数是关于x轴对称的点
加定义为： $P, Q, R$ 是斜率相同的点(一条直线跟椭圆曲线相交的3个点)，有 $P + Q + R = 0$

这样就有 $R = - (P + Q)$ ，如果要用计算机去算，需要转换成代数的方法计算R的x,y坐标
记
$P = (x_{P}, y_{P}), Q = (x_{Q}, y_{Q}), R = (x_{R}, y_{R})$
则:
$m = \frac{y_{P} - y_{Q}}{x_{R} - x_{Q}}$
$x_{R} = m^{2} - x_{P} - x_{Q}$
$y_{R} = y_{P} + m (x_{R} - x_{P})$
这样，就能根据 $P, Q$ 算出 $R$ 了。

4. 标量乘法

$n P = \underset{n times}{\underset{⏟}{P + P + \dots + P}}$
叫做标量乘法.
有个快速算法：double and add，
比如 $n = 151$ ，用2进制表示为 $10010111 b$ ，然后
$\begin{array}{rcl} 151 & = & 1 \cdot 2^{7} + 0 \cdot 2^{6} + 0 \cdot 2^{5} + 1 \cdot 2^{4} + 0 \cdot 2^{3} + 1 \cdot 2^{2} + 1 \cdot 2^{1} + 1 \cdot 2^{0} & = & 2^{7} + 2^{4} + 2^{2} + 2^{1} + 2^{0} \end{array}$
就可以很方便的用计算机去算了。

5. 对数

对 $Q = n P$ ,如果知道 $n$ 和 $P$ ，可以很容易算出 $Q$ (double and add)，但如果知道 $Q$ 和 $P$ ，却很难算出 $n$ ——数学上没有很快的算法。
如果用*来表示，那就是 $Q = P^{n}$ ,知道 $Q$ 和 $P$ ，很难算出指数 $n$ ，这就是取对数难题，也是密码学中的基石。

6. 有限域(Finite Field)

有限域，就是域中元素是有限个数的域，整个实数域是无限的，如果对实数取 $mod p$ ，就可以得到元素个数为p的有限域了，
域中多一个操作乘，符合结合律： $x \cdot (y + z) = x \cdot y + x \cdot z$

先了解mod运算
$(18 + 9) mod 23 = 4$
$- 5 mod 23 = 18$
$9^{- 1} mod 23 = 18$
因为在域23上， $9^{- 1} = 18$ (因为 $9 \cdot 18 mod 23 = 1, 9 \cdot 9^{-} 1 m o d 23 = 1$ , 域上1个元素有且只有1个倒数，所以 $9^{- 1} = 18$ ，9的倒数是18)

7. mod p 除法

要计算 $\frac{x}{y}$ ，需要计算 $x \cdot y^{^{-} 1}$ ,也是就是我们要先找到y的倒数，然后再乘上x
取一个数的倒数用扩展欧几里得算法可以很简单算出来。

8. 有限域 $G F (p)$ 中的椭圆曲线

先前的椭圆曲线是实数域上的，现在挑选其中在有限域 $G F (p)$ 上的点，就组成了椭圆曲线上的有限域——或者有限域上的椭圆曲线。

9. 有限域上的椭圆曲线的加法

还是 $P + Q + R = 0$ ，但 $P ， Q, R$ 在有限域上怎么斜率相同呢？——在一条直线上即可。但有限域上的直线跟是实数域上有些不同，只要有限域中的点 $(x, y)$ 符合 $a x + b y + c (mod p) = 0 (mod p)$ ，就说这些点在同一条直线上——这样的直线画出来可能有很多并行的条，都算同一条直线。

这样，有限域上的加法用计算机计算，公式是这样的
$x_{R} = (m^{2} - x_{P} - x_{Q}) mod p$
$y_{R} = [y_{P} + m (x_{R} - x_{P})] mod p = [y_{Q} + m (x_{R} - x_{Q})] mod p$

这样就可以用计算机计算 $P + Q = R$ 了

10. 一个椭圆曲线群的阶`order`

首先，一个群上的点的元素个数，叫做这个群的阶。
定义在一个有限域上的一个椭圆曲线的元素个数是多少呢？有个快速的算法可以计算: Schoof’s algorithm。可以方便计算椭圆曲线在有限域上的元素个数。

11. 标量乘法和曲线子群

标量乘法是这样的
$n P = \underset{n times}{\underset{⏟}{P + P + \dots + P}}$
但在有限域上，我们可以想象出
$1 P$
$2 P$
$3 P$
$\dots$
得出的结果最终会形成一个循环，而且循环中的所有结果都在有限域上，这样，我们根据 $P$ 生成了一个曲线子群， $P$ 就叫做这个子群的生成因子后者基准点。曲线子群就是ECC和其他加密系统的基础。

现在我们梳理一下：

一开始我们有实数群 $G$ ,
我们取椭圆曲线，得出椭圆曲线上的点，形成一个小一点的群
接着定义有限域，然后将椭圆曲线限制到有限域上，这样框出来的椭圆曲线上的点，形成一个更小一点的群
最后，我们取其中一个点作为基准点，取基准点的向量倍数，生成一个再小一点的子群，这个群，就是我们的ECC要用的群了。

12. 子群的阶

我们想知道，由基准点 $P$ 生成的子群的阶是多少。现在不能用Schoof’s算法，它是工作在整个椭圆曲线上，而不是其中的一个子群。
要算子群的阶，需要知道：

子群的阶就是子群中的元素个数，等价于 $n P = 0$ ，其 $n$ 是正整数，且 $n$ 是其中最小的1个，这个 $n$ 就是子群的阶。
根据拉格朗日定理，子群 $P$ 的阶，是父群阶的一个因子，比如一个椭圆曲线有 $N$ 个元素，它的一个子群有 $n$ 个元素， $n$ 能整除 $N$

接着我们开始算子群P的阶：

用Schoof's算法计算椭圆曲线的阶 $N$
找出 $N$ 的所有因子
对 $N$ 的每一个因子 $n$ ，计算 $n P$
找出使 $n P = 0$ 的最小的 $n$ ，这个 $n$ 就是子群的阶.

比如对 $G P (37)$ 有限域上的椭圆曲线 $y^{2} = x^{3} - x + 3$ , 它的阶 $N = 42$ ，子群可能有的阶 $n = 1, 2, 3, 6, 7, 14, 21, 42$ , 如果我们取基准点 $P = (2, 3)$ ，那么
$P! = 0, 2 P! = 0, 3 P! = 0, 6 P! = 0, 7 P = 0$
那么就说， $P$ 的阶是 $n = 7$

13. 找一个基准点

对ECC算法来说，我们希望子群拥有更高的阶。
我们先计算椭圆曲线的阶 $N$ ，找一个比较大的因子 $n$ ，然后根据 $n$ 找出一个合适的基准点。
也就是说，我们先找子群的阶，再根据子群的阶找其中的基准点。而不是先找基准点，再算子群的阶。

再加一个信息：根据拉格朗日定理， $h = N / n$ 肯定是个整数（因为 $n$ 是 $N$ 的一个因子）。这个 $h$ 叫做子群的协因子(cofactor).

对一个椭圆曲线上的任意一点来说， $N P = 0$ ,因为 $N$ 总是任何一个 $n$ 的倍数；
也就是 $n (h P) = 0$
取 $n$ 是素数，点 $G = h P$ 生成一个阶为 $n$ 的子群。
这样，我们就根据选择的阶 $n$ ，算出了一个基准点。

14. 离散对数

在连续的椭圆曲线上，我们如果知道 $P$ 和 $Q$ 很难算出 $k$ ，使得 $Q = k P$ ，
那么，
在有限域上的椭圆曲线，这个也是很多难的，叫做椭圆曲线的离散对数问题。

ECC有意思的一点是，这个离散对数问题“更难”，也就是要达到相同的加密强度， $k$ 的位数可以更少。这也是有RSA，还有开发ECC的原因。

15. 定义一个ECC的域需要的参数

有限域的大小是个素数 $p$
椭圆曲线中的系数 $a, b$
子群基准点 $G$
子群的阶 $n$
子群的协因子 $h$

所以，定义一个我们ECC需要的问题域需要6个因子 $（ p, a, b, G, n, h ）$

16. 随机曲线

并不是所有的椭圆曲线上的离散对数都那么难，比如 $p = h n$ 的椭圆曲线就可以用Smart方法攻击。而且我们也不知道还有没有哪些椭圆曲线的攻击方法我们没发现。
一个更具密码学强度的方法是，我们选一个随机因子 $S$ ，对 $S$ 取hash，然后衍生出 $a 、 b$ 或者 $G$ ，或者两者都用 $S$ 生成，那么攻击者就不知道我们用的是什么参数，会更安全些。
但是，NIST规定了一些 $S$ ，我们也不知道 $S$ 是不是精心挑选的。。。。。。

17. ECC算法

私钥就是从 $[1, n - 1]$ ( $n$ 是子群的阶)中随机挑选的一个整数 $d$
公钥就是点 $H = d G$ ( $G$ 是子群的基准点)

知道 $d$ 和 $G$ ，算出 $H$ 很简单，但反过来就很难。
这是个非对称加密算法，基于此，衍生出两个算法ECDH（用于密钥交换），ECDSA（用于签名）

18. ECDH

Alice和Bob各自生成自己的公私钥，Alice的私钥是 $d_{A}$ , 公钥是 $H_{A} = d_{A} \cdot G$ ，Bob的是 $d_{B}$ 和 $H_{B} = d_{B} \cdot G$ 。注意Alice和Bob用的是同一个有限域上的同一个椭圆曲线的同一个基准点 $G$
Alice和bob在一个未加密的通道上交换公钥 $H_{A}$ 和 $H_{B}$ ,
Alice计算 $S = d_{A} \cdot H_{B}$ , Bob计算 $S = d_{B} \cdot H_{A}$ , 两个计算出来的 $S$ 是一样的

这样Alice和Bob就得出了同一个 $S$ ，就可用于对称加密了。

一个例子

$p$ = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
$a$ = 0
$b$ = 7
$x_{G}$ = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
$y_{G}$ = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
$n$ = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141

h

= 1

Curve: secp256k1
Alice's private key: 0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb
Alice's public key: (0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677, 0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)
Bob's private key: 0xcef147652aa90162e1fff9cf07f2605ea05529ca215a04350a98ecc24aa34342
Bob's public key: (0x4034127647bb7fdab7f1526c7d10be8b28174e2bba35b06ffd8a26fc2c20134a, 0x9e773199edc1ea792b150270ea3317689286c9fe239dd5b9c5cfd9e81b4b632)
Shared secret: (0x3e2ffbc3aa8a2836c1689e55cd169ba638b58a3a18803fcf7de153525b28c3cd, 0x43ca148c92af58ebdb525542488a4fe6397809200fe8c61b41a105449507083)

PS：每次都生成新的公私钥，就叫ECDHE，E表示Ephermeral，瞬时的，短暂的

19. ECDSA

Alice使用私钥 $d_{A}$ 签名消息，Bob使用Alice的公钥 $H_{A}$ 验签。
ECDSA需要对消息的摘要进行签名，而不是对任意长度的消息签名。消息摘要需要截断到跟子群的阶 $n$ 一样长度的位数，截断的摘要用作为一个整数 $z$

签名:

从 $[1, n - 1]$ ( $n$ 是子群的阶)中随机选择一个整数 $k$
计算 $P = k G$ （ $G$ 是子群的基准点）
计算 $r = x_{P} mod n$ ( $x_{P}$ 是 $P$ 的x坐标)
如果 $r = 0$ ，重新选择 $k$
计算 $s = k^{- 1} (z + r \cdot d_{A}) mod n$ （ $d_{A}$ 是Alice的私钥， $k^{- 1}$ 是 $k$ 的乘法倒数 mod n）
如果 $s = 0$ ，重新选择 $k$

$(r, s)$ 组成的对儿就是签名

验签：

计算 $u_{1} = s^{- 1} \cdot z mod n$
计算 $u_{2} = s^{- 1} \cdot r mod n$
计算点 $P = u_{1} G + u_{2} H_{A}$
如果 $r = x_{P} mod n$ ，就说明签名正确

例子

Curve: secp256k1
Private key: 0x9f4c9eb899bd86e0e83ecca659602a15b2edb648e2ae4ee4a256b17bb29a1a1e
Public key: (0xabd9791437093d377ca25ea974ddc099eafa3d97c7250d2ea32af6a1556f92a, 0x3fe60f6150b6d87ae8d64b78199b13f26977407c801f233288c97ddc4acca326)

Message: b'Hello!'
Signature: (0xddcb8b5abfe46902f2ac54ab9cd5cf205e359c03fdf66ead1130826f79d45478, 0x551a5b2cd8465db43254df998ba577cb28e1ee73c5530430395e4fba96610151)
Verification: signature matches

Message: b'Hi there!'
Verification: invalid signature

Message: b'Hello!'
Public key: (0xc40572bb38dec72b82b3efb1efc8552588b8774149a32e546fb703021cf3b78a, 0x8c6e5c5a9c1ea4cad778072fe955ed1c6a2a92f516f02cab57e0ba7d0765f8bb)
Verification: invalid signature

参考：

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ : 这个系列非常好，基本是翻译了这篇原文.
RFC8442-Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS) Versions 1.2 and Earlier: 定义了TLS1.2及以前的协议使用的ECC曲线都有哪些，比如X25591,secp256r1等.
RFC7748-Elliptic Curves for Security: 具体定义了X25519,X448曲线算法.
RFC6090-Fundamental Elliptic Curve Cryptography Algorithms: ECC基本定义.
Elliptic Curve Cryptography: openssl对ECC的解释，简单明了，值得一看