详解椭圆曲线加密

September 13th, 2024

为什么需要椭圆曲线加密？

理解非对称加密

在加密货币中，如果 Alice 向 Bob 转账，需要满足两个基本条件：

证明这笔转账是 Alice 触发的 → 签名；
Bob 收到了这笔转账，且 Bob 可以消费 Alice 转给他的钱 → 验证。

这其中的签名就是 Alice 的私钥生成公钥的过程，而验证则是验证 Alice 的公钥，且保证 Alice 的公钥无法推导出 Alice 的私钥，因为如果大家都可以推导出私钥，那人人都可以代替 Alice 签名，从而转走 Alice 的资产。

这种加密方式我们称为非对称加密，即可以从 A→B，但很难从 B→A。有几种比较合适的数学函数可以满足这种加密理念，比如素数指数和椭圆曲线。他们的理念都是一样的，为了更好的理解后者，我们可以先用素数指数做一个「热身」。

素数在加密中的作用

在很多加密系统中，素数起着至关重要的作用。什么是素数？就是大于 1 的自然数，只能被 1 和它本身整除。比如 2，3，5，7 为素数，而 4，6，8，9 则不是素数。

2 = 1 * 2 ✅
3 = 1 * 3 ✅
5 = 1 * 5 ✅
7 = 1 * 7 ✅

4 = 1 * 4 = 2 * 2 ❎
6 = 1 * 6 = 2 * 3 ❎
8 = 1 * 8 = 2 * 2 * 2 ❎
9 = 1 * 9 = 3 * 3 ❎

为什么素数重要呢？因为它们是所有其他数的“基本构建块”。比如：

6 可以分解为 2 * 3（两个素数相乘）
15 可以分解为 3 * 5

这个分解过程称为“质因数分解”，在密码学中非常重要。这里有一个很有趣的现象，如果一个数字很小，比如 15，你快速拆解为 3 * 5 两个素数因子相乘。但如果我给你 19604323 这种很大的数，你是很难在短时间找到两个素数因子的。所以，大数的质因数分解，就是很多非对称加密算法的核心逻辑，比如知名的 RSA 加密。

为什么选择椭圆曲线加密？

所以基于上述讨论，我们想象一下，如果这个数足够大，比如达到 2^256 或者 10^77，那么计算机去计算质因子也是极其困难的。而相较于 RSA 算法，椭圆曲线加密使用更短的秘钥，就可以达到相同的安全强度，一般认为 160 bit 的椭圆曲线秘钥强度和 1024 bit 的 RSA 秘钥安全相当。所以比特币选择使用椭圆曲线加密作为公私钥的核心加密算法。

什么是椭圆曲线加密？

先说个冷知识，椭圆曲线加密和椭圆形一点关系都没有，它呈现的图像也不是椭圆形，之所以叫椭圆曲线加密，是因为计算某些属性的时候和计算椭圆弧长相关属性有一些相似之处。下图是一些椭圆曲线样式。

数学公式与曲线样式

椭圆曲线的公式为

y^2 = x^3 + ax + b, 4a^3 + 27b^2 ≠ 0

因为比特币采用的是 Secp256k1 加密算法，规定 a = 0，b = 7，所以公式为

y^3=x^3+7

这让比特币的椭圆曲线看起来如下图所示：

椭圆曲线上的点有一种特殊的「加法运算」规则，我们可以用这种规则将两个点「相加」得到一个新的点。通过反复执行这种运算，可以在椭圆曲线上实现类似于指数的概念。指数是一个非常常见的数学概念，它表示一个数（底数）自我相乘的次数。例如：

• 2^3 = 2 * 2 * 2 = 8
• 5^4 = 5 * 5 * 5 * 5 = 625

在椭圆曲线上，计算 P = kG 是一种类似于指数运算的过程。就像在普通数学中，计算 2^5 = 32 是很容易的，但如果只知道结果是 32，想反过来推算出 2^k = 32 需要一些试探性的计算。

超出宇宙寿命的破解时间

我们再聊回椭圆曲线加密，如图：

在椭圆曲线上我们取一个基点 G(x,y)，将其和整数 k 相乘，得到曲线上另外一点 P(x,y)，即

P = k*G

其中 k 是私钥，而 P 是公钥，计算 P = k * G 的速度很快，而计算 k = P/G 则是不可能的，只能通过无限尝试，暴力破解来获得，如果 k 为一个极大的数，如我们上文提到的 2^256 或者 10^77，按照计算机每秒计算 1 万亿次，则计算 k 值将花费

2^{256}÷10^{12}÷(60*60*24*365)

这大约等于数十亿年。这种难度使得破解椭圆曲线加密在实际中不可行，甚至有可能超过宇宙的寿命。

为什么椭圆曲线加密是不可逆的（非对称加密）？

这里我们要再继续深度讨论一个问题，既然从 k *G 得到 P 是速度极快的，那么为什么不能用 P/G = k 得到私钥呢？

了解点加法

我们谈到 P = kG，其中 k 是私钥，P 和 G 是曲线上的两个点。在椭圆曲线加密中，点乘法（点乘法是基于点加法的一种重复运算） kG 和普通的乘法不一样。虽然我们用类似于「乘法」的记号来表示，但是它背后的计算原理是完全不同的。椭圆曲线加密中的点乘法不是直接的数值相乘，而是通过重复加法实现的。具体做法的是将两个点在曲线上的位置通过几何规则相加，得到一个新的点。这与我们平时理解的数字加法不同，它不涉及直接加两个数，而是利用曲线上的几何关系来进行操作。我们从一个简单的例子开始，看看两个点的点加法是怎么运算的：

1. 两个不同的点加法

a. 选择两个点 P 和 Q ：假设你有两个不同的点 P 和 Q ，都在椭圆曲线上；

b. 画一条直线连接这两个点：你从点 P 画一条直线，穿过点 Q ，这条直线会与椭圆曲线的另一个地方相交；

c. 取相交点：你找到直线与曲线的第三个相交点，称它为 R ；

d. 取对称点：然后你取点 R 的垂直镜像点 R’（即以 x 轴为对称轴的另一个点），这个镜像点就是 P + Q 的结果。

2. 同一个点的加法

如果你想要将一个点 P 自己加自己（类似于 2P）：

a. 从点 P 向曲线画切线：你画一条经过点 P 的切线，这条切线会与曲线的另一个地方相交；

b. 找到相交点：这条切线会与曲线相交于另一个点 R ；

c. 取对称点：同样，你取点 R 的垂直镜像点 R’，这个镜像点就是 P + P （或 2P）的结果。

为什么点加法很难反向操作？

现在你已经了解了椭圆曲线上的点加法是通过几何上的规则（画直线、找相交点、取镜像点）来完成的。我们可以不断加点，比如：

• P + P = 2P
• 2P + P = 3P
• 3P + P = 4P

每次得到的点分布在曲线的不同位置，并且这个过程并不像数字乘法那样有一个可预见的规律，虽然我们可以反复用点加法从 P 得到 Q，但是这些点的分布是不规则的，不像我们平时的乘法那样有固定的规律。例如：

P 和 2P 可能相隔很远， 3P 又跳到了另外一个完全不同的位置；
因为每次点加法都依赖于几何上的规则，它不像我们平时的“乘法”，每次都在某个固定的倍数范围内跳跃。

这意味着，即使你知道 P 和最后的结果 Q ，你很难推测出中间加了几次点，也就是找出这个 k 值（即 kG = Q 中的 k）。

具体的困难：离散点和非线性

椭圆曲线的点加法具有离散性和非线性特征，这使得反向求解变得非常复杂：

离散性：点加法后的点分布在曲线的各个位置，之间没有简单的线性关系，无法通过观察点的相对位置推测出具体的加法次数；
非线性：我们平时的加法是线性的，比如 2 + 2 = 4，4 + 2 = 6。但在椭圆曲线上的点加法并没有这样简单的规律。例如：
- P + P 不等于 P * 2 的数字乘法，它是通过几何图形操作得到的一个新点；
- 2P 和 3P 之间的关系不直观，反向操作时（即从 P 和 Q 找 k ）没有捷径，只能逐一尝试。

再从离散对数解释椭圆曲线加密的不可逆

离散对数（Discrete Logarithm）是数学中的一个重要概念，尤其在密码学中，它是许多加密算法（如椭圆曲线加密和 Diffie-Hellman 密钥交换）的核心难题。离散对数问题在数学上非常困难，正是这种困难性保证了这些加密系统的安全性。其中 P = k*G，找到 k 就是离散对数问题。

什么是普通对数？

为了理解离散对数，我们先温习一下中学知识，即普通对数。在普通的指数中，比如：

a^x = b

我们可以通过“对数”来反过来求解 x 。这就是普通对数的作用。比如：

2^3 = 8

如果你知道 2 和 8，并且想求 x ，可以通过对数：

\log_2(8) = 3

这里， log2(8) 表示的是以 2 为底，得到 8 需要 2 自己乘几次。这个对数运算是普通数学中常见的反向操作。

什么是离散对数？

离散对数与普通对数类似，但它应用在模运算的场景中，也就是数论中的指数运算。它的计算和理解要比普通对数复杂一些。在离散对数中，我们通常不直接处理实数，而是处理整数模运算，即我们只关心除法的余数。

假设公式：

g^x \equiv h\pmod{p}

这里 g 是一个已知的数，称为底数，h 是已知的结果，p 是一个素数，用来做模运算，我们的目标是找到 x ，使得 g^x mod p = h。这个 x 就是离散对数。假设我们想找到一个 x ，使得 2^x 对 5 取余等于 3。

2^x \equiv 3 \pmod{5}

通过尝试不同的 x 值：

• 2^1 = 2 ，对 5 取余是 2；
• 2^2 = 4 ，对 5 取余是 4；
• 2^3 = 8 ，对 5 取余是 3。

因此，当 x = 3 时，满足方程解。

离散对数为什么难解？

与普通对数不同，离散对数的计算非常困难，因为它是在模运算下进行的，而且没有简单的反向操作。在普通对数中，我们可以直接使用对数公式反推出 x ，但在离散对数中，由于模运算的非线性特性，没有有效的办法反向计算。模运算导致指数函数呈现出周期性和复杂性，这使得我们不能像普通对数那样直接反向求解。还是这个假设：

g^x \equiv h \pmod{p}

在模运算中， g^x 的结果是对 p 取余数的结果，这意味着指数增长后的结果会被限制在一个循环范围内。这种循环使得反向求解 x 非常复杂。

为什么有循环性？

假设我们进行上述指数模运算，不管 x 多大，最终结果总是会被限制在 p 的范围内。

举个简单的例子，假设 g = 2，p = 5 （这是一个很小的素数），我们计算不同的 x 值下的 2^x mod 5

2^1 mod 5 &= 2
2^2 mod 5 &= 4 
2^3 mod 5 &= 8 mod 5 = 3 
2^4 mod 5 &= 16 mod 5 = 1 
2^5 mod 5 &= 32 mod 5 = 2

你可以看到，当 x = 5 时，结果再次回到 2，这意味着计算进入了一个循环。这种周期性是模运算的一个特性，因为取模将所有结果限制在 [0, p-1] 之间。

所以当 p 很大时，可能性很多。当 p 是一个非常大的素数，比如 256 位的素数，模运算的结果也会被限制在 0 到 p-1 的范围内。但由于 p 很大，可能的结果范围也非常广。假设 p 是一个 256 位的素数，那么大约有 2^256 中可能性，因此 g^x mod p 的结果会在 0 到 p-1 之间随机分布，而 p 有接近 2^{256} 个可能的值。这意味着，对于每个 x 值，我们有接近 2^{256} 种可能的模运算结果，你要找到合适的 x 值，只能暴力破解。