椭圆曲线加密算法原理
阿牛哥 Lv4

和RSA算法类似,椭圆曲线加密(ECC,Elliptic Curve Cryptography)也是一种非对称加密算法。我们常见的ed25519就是基于该算法。

RSA利用了大数分解问题在计算机上求解困难,破解需要耗费大量的时间,从而保证其安全性。ECC也借鉴了相同的思路,通过椭圆曲线上的求解难题来保证安全性。

椭圆曲线加密算法

为什么叫椭圆曲线

椭圆曲线(Elliptic Curve)是一类平面曲线,虽然名称中包含“椭圆”,但画在图形上并不是椭圆形,之所以叫这个名字,是因为这类曲线的公式很像椭圆的周长公式:

y2=x3+ax+by^2 = x^3 + ax + b

椭圆曲线加密的基本原理

用椭圆曲线计算出来的私钥和公钥有如下关系:

Q=kPQ = kP

其中 kk 是私钥, QQ 是公钥, PP 为基点。

给定私钥 kk 和参数 PP 的情况下计算出 QQ 是很容易的;反之,在知道公钥 QQ PP 的情况下要反推出私钥kk 是很困难的。

看到这里你可能会有疑问,Q=kPQ = kP 不就一个乘法式子嘛,为什么在已知 QQ PP 的情况下计算 kk 会很难呢?

实际上,上式不是普通的乘法,它的计算规则和算术乘法是不一样的。

椭圆曲线的定义

平面上的椭圆曲线符合如下公式:

y2=x3+ax+b且 4a3+27b20y^2 = x^3 + ax + b \\ 且 \ 4a^3 + 27b^2 \neq 0

xx yy 是平面上的点的横坐标和纵坐标, aa bb 是系数。

举个例子,当 a=2, b=4a = -2, \ b = 4 时,椭圆曲线的图形是这个样子:

y^2 = x^3 - 2x + 4

y2=x32x+4y^2 = x^3 -2x + 4

椭圆曲线的运算

加法

假设椭圆曲线上有 AA BB 两个点,那么计算椭圆曲线上的加法 A+BA + B 的过程是这样的:

  1. AA BB 画直线。一般情况下,直线会和椭圆曲线相较于 CC 点。

  2. 画一条过 CC 点且与 YY轴 平行的直线,它和椭圆曲线的另一个交点 DD 的坐标就是 A+BA + B 的结果。

如图所示:

椭圆曲线上的加法

某些特殊情况下, AA BB 点的连线和椭圆曲线可能不存在交点,此处不做讨论。

乘法

想象一下,当 AA BB 相互靠近,它们的连线会越来越接近于椭圆曲线的切线。

而当AA BB 完全重合,即 A=BA = B 时,它们的连线就是一条切线。此时, A+BA + B 是这个样子:

A = B时的椭圆曲线加法

因为 A=BA = B ,所以椭圆曲线上的乘法 2A=2B=D2A = 2B = D

再进一步 3A=2A+A=D+A=F3A = 2A + A = D + A = F

椭圆曲线乘法F = 3A

依此类推,以 kk 为系数的乘法就很清楚了。

离散的情况

在计算机中,用整数计算显然更合适,所以在算法设计上,要对连续的椭圆曲线做修改,所有的取值都只能是平面上离散的点。这样 kPkP 的每一步都会取模落在“有限域”内。

也就是说,在每一步运算之后都要取余数,一旦超过某个素数 pp ,就对其取余数,这样的域记作GF(pnp^n ) , pnp^n 等于域内元素的个数。比如 p=53, n=1p = 53, \ n = 1 即GF(53),如果此时 a=1, b=1a = 1, \ b = 1 ,那么改造后的椭圆曲线公式为:

y2x3+x+1 (mod 53)y^2 \equiv x^3 + x + 1 \ (mod \ 53)

有限域的定义和运算规则

数学上,对于一个有限个数字的集合,集合内的数字间进行加、减、乘、除运算,其运算结果依然在集合内,那么这样的集合就是一个有限域

比如 {0,1,2,3,4,5,6,7,8,9,10,11}\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \} ,想要让它成为有限域,还要对运算规则做一些修改,因为11如果和1相加的结果12不在域内了。

在有限域内,加法和乘法的结果都要取模,即 a+ba + b 的结果是 (a+b) mod p(a + b) \ mod \ p a×ba \times b 的结果是 (a×b) mod p(a \times b)\ mod \ p

在这样的运算规则下,对于 Q=kPQ = kP ,在已知 QQ PP 的情况下,要i计算出私钥 kk 是相当困难的。

椭圆曲线的加解密过程

私钥和公钥

私钥和公钥的生成过程:

  1. 选一条椭圆曲线

  2. 在曲线上选一个基点 PP

  3. 选一个大数 kk 作为私钥

  4. 生成公钥 Q=kPQ = kP

这里除了私钥 kk 保密之外,基点 PP 和公钥 QQ 是公开的。

加密

有了私钥和公钥后,对消息 MM 的加密过程是这样的:

  1. 选取一个随机数 rr

  2. 密文 C=(rP,M+rQ)C = (rP, M + rQ)

这里用到了 PP QQ

解密

解密使用密文 CC 和私钥 kk

因为 CC 分两部分 M+rQM + rQ rPrP ,通过如下计算能得到明文:

M+rQk(rP)=M+r(kP)k(rP)=M+rkPrkP=M\quad M + rQ - k(rP) \\ = M + r(kP) - k(rP) \\ = M + rkP - rkP \\ = M

证明完毕!