椭圆曲线加密算法

Jun 23, 2022

本文为Elliptic Curve Cryptography系列文章的翻译，原文深入浅出，非常值得一读。这篇译文刨去了背景知识，相当于是一篇纯纯的学习笔记了。不过由于我本人完全是一个密码学门外汉，专业水平有限，不足之处多多包涵。

Table of Contents

加密算法分支

  • 基于椭圆曲线

    基于椭圆曲线的加密算法包括ECC（Elliptic Curve Cryptography）、ECDH和ECDSA。ECDH与ECDSA是基于ECC发展而来。

  • 基于模余运算

    基于模余运算的加密算法包括RSA、DSA、DH以及其他衍生算法。

椭圆曲线与群

椭圆曲线

一条椭圆曲线就是一组满足\(y^2 = x^3 + ax + b\)且\(4a^3 + 27b^2 \ne 0\)的二维平面点集。\(4a^3 + 27b^2 \ne 0\)的条件是为了保证曲线不存在奇点（singularity）；\(y^2 = x^3 + ax + b\)又被称作椭圆曲线的Weierstrass normal form。

除了这条曲线上的点，我们还需要一个无穷远处的点，我们用\(0\)这个特殊的符号来表示这个点，所以椭圆曲线更准确的表达式为 \[ \{(x,y) \in \R^2 | y^2 = x^3 + ax + b, 4a^3 + 27b^2 \ne 0\} \cup \{0\} \] 椭圆曲线的一条显而易见的性质是，它是关于\(x\)轴对称的。

群（Group）

一个集合\(G\)加上一个二元运算\(\oplus\)，若满足以下条件，就构成了数学上的一个群：

  • 封闭性（closure）：\(a \in G, b \in G \to a \oplus b \in G\)；
  • 结合律（associativity）：\((a + b) + c = a + (b + c)\)；
  • 存在一个单位元（identity element）\(0\)，使得\(a + 0 = 0 + a = a\)，即单位元与任何元素进行运算，不改变该元素的值；
  • 每个数都存在一个逆元（inverse）。

若该群进一步满足

  • 交换律（commutativity）：\(a + b = b + a\)。

则称该群为阿贝尔群（Abelian group）。

椭圆曲线上的群

对于我们定义的椭圆曲线集合，我们

  • 定义无穷远处的\(0\)为单位元；

  • 定义逆元为该点关于\(x\)轴另一侧的对称点；

  • 定义二元运算\(\oplus\)如下：

    若一条直线与椭圆曲线的三个交点分别为\(P,Q,R\)，则\(P \oplus Q \oplus R = 0\)，我们称这三个点是对齐的（aligned）。在此处我们没有规定三个点之间的顺序，即三个点之间可以任意交换位置，也就是说我们的定义的二元运算是满足交换律的，我们定义的群是一个阿贝尔群。

    给定两个非零、非对称的点\(P = (x_P, y_p), Q = (x_q, y_Q)\)，我们可以很轻松地找到\(R = P \oplus Q\): \[ \begin{align} x_R &= m^2 - x_P - x_Q \\ y_R &= y_P + m(x_R - x_P) \\ &= y_Q + m(x_R - x_Q) \end{align} \] 其中： \[ m = \begin{cases} \frac{y_P - y_Q}{x_P - xQ}, & P \ne Q \\ \frac{3x_P^2 + a}{2y_P}, & P = Q \end{cases} \]

标量积（Scalar Multiplication）

给定之前的二元加法运算，我们可以定义出相应的群中元素与标量之间的乘法运算： \[ n P = \underbrace{P + \dots + P}_{n \text{ times}} \] 这样的乘法运算可以在\(\Omicron(\log n)\)时间内完成。

对数运算（Logarithm）

给定\(n\)和\(P\)，我们可以很高效地完成标量积运算\(Q = nP\)；但如果给定\(Q\)和\(P\)，我们如何计算出对数运算（虽然这里是除法，但是为了和密码学中的标记保持一致，这里使用了对数）\(n = Q \div P\)呢？

椭圆曲线与有限域

有限域（Finite Field）

有限域首先是一系列元素的集合，比如说由整数模余某个质数\(p\)得到的集合（通常表示为\(\Z/p\)或\(\newcommand{F}{\mathbb F} \F_p\)）；有限域还定义了两种二元运算：加法和乘法，且这两种运算应该满足如下条件：

  • 在有限域上都是封闭的、满足结合律以及交换律的；
  • 存在单位元；
  • 每个元素都存在相应的逆元。

除此之外，乘法运算还应该满足分配律（distributive）：\(x \cdot (y + z) = x \cdot y + x \cdot z\)。

\(\F_p\)包含了从\(0\)到\(p-1\)的所有整数，而加法、乘法操作之后要追加模余（除数为\(p\)）操作。

  • 若\(a + b = 0 \pmod p\)，则\(a\)，\(b\)互为加法逆元（additive inverse），\(a=-b, b=-a\)；
  • 若\(ab = 1 \pmod o\)，则\(a\)，\(b\)互为乘法逆元（multiplicative inverse），\(a=b^{-1},b=a^{-1}\)；\(xy^{-1}\)有时也表示为\(x/y\)；\(n\)的乘法逆元可以通过Extended Euclidean Algorithm，其时间复杂度为\(\Omicron(\log n)\)。

可以证明，\(\F_p\)也是一个阿贝尔群。

有限域上的椭圆曲线

椭圆曲线本身的定义为： \[ \{(x,y) \in \R^2 | y^2 = x^3 + ax + b, 4a^3 + 27b^2 \ne 0\} \cup \{0\} \] 加上有限域的限制之后，变为 \[ \{(x,y) \in \F^2 | y^2 = x^3 + ax + b \pmod p, 4a^3 + 27b^2 \ne 0 \pmod p, a, b \in \F_p \} \cup \{0\} \] 由于有限域的限制，此时所有的点全部出现第一象限。该图像关于\(y = p / 2\)对称，因为若\(y_1 + y_2 = p\)， \[ \begin{aligned} y_1^2 &= (p - y_2)^2 \\ &= p^2 - 2py_2 + y_2^2 \\ &= y_2^2 \pmod p \end{aligned} \]

再看群

  • 对于一个点\(Q = (x_Q, y_Q)\)，其逆元\(-Q\)定义为\(-Q = (x_Q, -y_Q \mod p)\)；

  • 我们这样定义有限域上椭圆曲线上的点之间的二元运算\(\oplus\)，同之前一样，三个对齐的点（aligned points）\(P,Q,R\)满足 \[ P \oplus Q \oplus R = 0 \] 只不过这里“对齐”的含义与之前有所不同，之前的对齐指的是几何上的共线，即三个点满足\(ax + by + c = 0\)；而这里的对齐指的是： \[ ax + by + c = 0 \pmod p \] 有趣的是，计算加法的公式和之前没有发生太大变化（证明）。给定两个非零、非对称的点\(P = (x_P, y_p), Q = (x_q, y_Q)\)，我们可以很轻松地找到\(R = P \oplus Q\)： \[ \begin{align} 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 \end{align} \]

    其中： \[ m = \begin{cases} (y_P - y_R)(x_P - x_R)^{-1} \mod p, & P \ne Q \\ (3x_P^2 + a)(2y_P)^{-1} \mod p, & P = Q \end{cases} \]

群中元素的个数叫做群的秩（order），可以通过Schoof’s algorithm计算求得。

标量积与子群

标量积依旧遵循之前的定义，给定正整数\(n\)和群中的点\(P\)， \[ nP = \underbrace{P + \dots + P}_{n \text{ times}} \] 标量积其实就是对某个点\(P\)不断做加法，其中一个有趣的性质是，\(0P, 1P, 2P, \dots\)的结果会以某个最小正周期周期\(k\)循环（证明）。这也就意味着，群中对加法\(P\)的倍数是关于加法封闭的（closed under addition），它们又构成了一个循环子群（cyclic subgroup），\(P\)又称作这个循环子群的基点（base point/generator），\(k\)是这个循环子群的秩（subgroup order）。

根据Lagrange’s theorem，子群的秩是其父群的秩的约数。

寻找基点

在ECC算法中，我们一般会先计算父群的秩\(N\)，找出它一个比较大的约数\(n\)，让\(n\)作为子群的秩，\(h = N / n\)称作这个子群的余因子（cofactor），再根据这个子群的秩去找这个子群的基点。一般来说，\(n\)会从\(N\)的质因子中选取，基本算法如下：

  • 计算父群的秩\(N\)；

  • 计算\(N\)的质因子\(n\)，从大到小排列进行试验：

    1. 计算余因子\(h = N / n\)；

    2. 随机选择椭圆曲线上的一点\(P\)；

    3. 计算\(G = hP\)；

    4. 如果\(G\)为\(0\)，则重新选择\(P\)进行试验；否则这意味着\(G\)就是秩为\(n\)的子群的基点。

需要注意的是，ECC算法能够运行的前提是，\(n\)必须是\(N\)的质因子。

离散对数运算（Discrete Logarithm）

现在我们解答之前提出的对数运算问题，给定\(Q\)和\(P\)，目前没有算法能够在多项式时间之内求解满足\(Q = kP\)的\(k\)。这个问题有点类似于给定整数\(a\)和\(b\)，如何求解满足\(b = a^k \pmod p\)的\(k\)？这两个问题目前都没有算法能在多项式时间之内求解，这也是ECC算法安全的根本。

椭圆曲线加密算法

寻找到之前秩为\(n\)、基点为\(G\)的子群后，我们就可以生成私钥和公钥了：

  • 私钥是从\(\{1,\dots,n-1\}\)中随机抽取的数字\(d\)；
  • 公钥是点\(H = dG\)。

下面介绍两个基于ECC的公钥加密算法。

Elliptic Curve Diffie-Hellman

ECDH是DH算法在椭圆曲线中的变体，它实际上是一种密钥交换算法，而不是加密算法。它的大致流程如下：

  • Alice和Bob各自随机生成私钥和公钥：\(H_A = d_A G, H_B = d_B G\)，注意，Alice和Bob使用了相同的基点；
  • Alice和Bob在非安全信道上交换各自的公钥，即使中间人拦截到了\(H_A\)和\(H_B\)，如果他不能求解出对数运算问题，他也不会知道Alice和Bob的私钥；
  • Alice计算\(S = d_A H_B\)，Bob计算\(S = d_B H_A\)，根据子群对加法的封闭性，二者应该得到相同的结果；
  • 中间人即使知道\(H_A\)、\(H_B\)，也无法得到密钥\(S\)，Alice和Bob便可以通过密钥\(S\)加密内容。

Elliptic Curve Digital Signature Algorithm

ECDSA是一种公钥加密算法，可以用于数字签名。ECDSA的作用对象是消息的哈希值，而不是消息本身，所以在使用ECDSA时，也要选取一个安全的哈希函数。消息的哈希值在签名过程中会被截断，使得该剩余哈希值的比特位数等于\(n\)的比特位数，我们用\(z\)来表示剩余哈希值所代表的整数。ECDSA的大致流程如下：

  • Alice从\(\{1, \dots, n\}\)中随机抽取数字\(k\)；
  • Alice计算\(P = kG\)；
  • Alice计算\(r = x_P \mod n\)，如果\(r=0\)，则重新选取\(k\)；
  • Alice计算\(s = k^{-1} (z + rd_A) \mod n\)，其中\(d_A\)是Alice的私钥，\(k^{-1}\)是\(k\)关于\(n\)的乘法逆元（我们前面选取\(n\)为质因子的目的就在于，保证这里的\(k^{-1}\)一定存在），如果\(s=0\)，则重新选取\(k\)。

元组\((r,s)\)就是Alice对应的签名。Bob拿到这样的签名之后，作以下验证：

  • 计算\(u_1 = s^{-1}z \mod n\)；
  • 计算\(u_2 = s^{-1}r \mod n\)；
  • 计算点\(P = u_1G + u_2H_A\)；
  • 仅当\(r = x_P \mod n\)时，Bob可以验证这确实是Alice的签名。

验证过程的正确性证明如下， \[ \label{P} \begin{aligned} P &= u_1 G + u_2 H_A \\ &= u_1 G + u_2 d_A G \\ &= (s^{-1} z + s^{-1} r d_A) G \\ &= s^{-1}(z + r d_A) G \end{aligned} \] 之前我们定义\(s = k^{-1} (z + r d_A) \mod n\)，将两边同乘\(ks^{-1}\)，我们可以得到\(k = s^{-1}(z + r d_A) \mod n\)，将此式代入\(\eqref{P}\)可以得到 \[ P = kG \] 这也就是Alice签名过程中得到的\(P\)，证毕。

\(k\)的选取

在使用ECDSA时，我们必须注意不能使用相同的\(k\)加密多份消息，也不能暴露我们选取\(k\)的方式（比如说随机数生成方式），否则就会有很大的私钥泄露风险。比如说我们用同一个\(k\)加密两份消息，Bob就可以通过这两次签名过程得到\((r, s_1), (r, s_2)\)，如果Bob还有额外途径获取两次消息的哈希\(z_1, z_2\)，那么： \[ \begin{gather} s_1 = k^{-1}(z_1 + r d_A), s_2 = k^{-1}(z_2 + r d_A) \to \\ (s_1 - s_2) = k^{-1}(z_1 - z_2) \mod n \to \\ k = (z_1 - z_2)(s_1 - s_2)^{-1} \end{gather} \] 再根据\(s_1 = k^{-1}(z_1 + r d_A) \mod n\)， \[ \begin{aligned} d_A &= r^{-1}(s_1k - z_1) \mod n \\ &= r^{-1}(s_1(z_1 - z_2)(s_1 - s_2)^{-1} - z_1) \mod n \end{aligned} \]

再看离散对数运算

给定秩为\(n\)、基点为\(G\)的椭圆曲线子群，以及该子群上的两点\(P,Q\)，离散对数运算求解的是满足\(Q = xP\)的整数\(x\)。我们接下来了解两个求解离散对数运算的算法。

Baby-step-giant-step

首先任意一个整数\(x\)，都可以写成\(x = am + b\)，由\(a,m,b\)这三个满足关系的任意整数表示，那么，我们就可以考虑这样解决离散对数运算问题： \[ \begin{aligned} Q &= xP \\ Q &= (am + b)P \\ Q - amP &= bP \end{aligned} \] Baby-step-giant-step算法采取了从两边夹逼的方式解决问题，过程如下：

  • 计算\(m = \lceil \sqrt n \rceil\)；
  • 对所有\(\{0, \dots, m\}\)中的数字\(b\)，计算\(bP\)，并将\(bP\)存储到哈希表中；
  • 对所有\(\{0, \dots, m\}\)中的数字\(a\)，
    1. 计算\(amP\)；
    2. 计算\(Q - amP\)；
    3. 检查哈希表中是否存在某个\(bP\)，使得\(Q - amP = bP\)，如果存在，就意味着我们找到了一个解。

\(bP\)的计算对应着baby-step，\(amP\)的计算对应着giant-step，该算法的合理性在于：

  • \(a=0\)时，我们检查\(Q\)是否和\(0, P, \dots, mP\)相等；
  • \(a=1\)时，我们检查\(Q\)是否和\(mP, P + mp, \dots, mP + mP\)相等；
  • \(a=2\)时，我们检查\(Q\)是否和\(2mP, P + 2mp, \dots, mP + 2mP\)相等；
  • \(\dots\)
  • \(a=m-1\)时，我们检查\(Q\)是否和\((m-1)mP, P + (m-1)mp, \dots, mP + (m-1)mP\)相等；

总之，我们检查了\(0\)到\(m^2P=nP\)之间的所有点，也就是所有可能的点。而检查的过程我们并不需要做实际的加法运算，只需要检查哈希表中有没有对应的差值。在baby-step中，我们需要做\(m\)次加法，在giant-step中，由于哈希表查询速度为\(\Omicron(1)\)，并且至多需要做\(m\)次加减法，所以整体上该算法的时间复杂度为\(\Omicron(\sqrt n)\)，而哈希表带来的空间复杂度也是\(\Omicron(\sqrt n)\)。尽管看上去这个多项式时间的算法还不错，但是由于一般\(n\)非常大，这个算法实际需要的时间成本以及存储成本远远超出当前计算机的水平。

Pollard’s \(\rho\)

Pollard’s \(\rho\)算法的时间复杂度也是\(\Omicron(\sqrt n)\)，但是它的空间复杂度为\(\Omicron(1)\)。和Baby-step-giant-step算法一样，我们实际解决的问题与原问题稍微有所不同，在Pollard’s \(\rho\)算法中，给定\(P,Q\)，我们想要找到整数\(a,b,A,B\)，使得 \[ aP + bQ = AP + BQ \] 找到这四个整数之后，我们代入\(Q = xP\)来求解\(x\)： \[ \begin{aligned} aP + bxP &= AP + BxP \\ (a-A)P &= (b-B)xP \\ &\Downarrow \\ (a-A) &= (b-B)x \pmod n \\ x &= (a-A)(b-B)^{-1} \mod n \end{aligned} \] Pollard’s \(\rho\)算法思路是这样的：我们生成一系列伪随机点\(X_1, X_2, \dots\)，其中\(X_i = a_iP + b_iQ\)。这样的序列可以由一个伪随机函数\(f(X_i) = (a_{i+1}, b_{i+1})\)生成，也就是说下一点是由当前点决定的，而\(f\)内部如何工作并不重要。通过这样的\(f\)产生序列，我们的序列迟早会出现一个回环，也就是说\(X_j = X_i\)，而这时我们也就能够找到相应的\(x\)。出现回环的原因也很好理解：我们点的个数是有限的，问题其实在于如何找到回环入口。

龟兔赛跑

Pollard’s \(\rho\)算法中的回环入口查找，其实类似单向链表中的回环入口查找：在链表开头设置一快一慢两个指针，我们让快指针每次前进两步，慢指针每次前进一步；二者相遇时，从相遇点和起点再设置两个新的慢指针，这两个新的慢指针相遇之处即为环的入口。

量子计算：Shor’s Algorithm

理论上，Shor’s Algorithm的时间复杂度为\(\Omicron((\log n)^3)\)，空间复杂度为\(\Omicron(\log n)\)，但是目前的量子计算机还不能进行像Shor’s Algorithm这样复杂的运算。

ECC与RSA

RSA的密钥长度在数量级上大于ECC的密钥长度，这不仅意味着更多的内存占用，还意味着更慢的计算速度。这其中的原因在于，RSA算法的离散对数运算是快于ECC算法的离散对数运算（参考General number field sieve），这也就意味着RSA算法不得不采用更长的密钥来加大破解难度。更少的内存占用，更快的计算速度，这就是在已经有了成熟的RSA算法的情况下，ECC仍被提出的原因。