介绍

椭圆曲线密码学（Elliptic curve cryptography），简称 ECC，和RSA、ElGamel 算法等类似，是一种公开秘钥加密的算法，也就是非对称加密。ECC 被公认为在给定秘钥长度下最安全的加密算法。ECC 依赖于解决大椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。

数学基础与算法介绍

群

一个集合 G 以及定义在集合 G 上的二元运算 ∗ 称为群（group），若满足以下条件：

  1. ∗ 运算满足结合律
  2. G 有单位元
  3. 对于任意 a∈G ， a有逆元

若群上的运算满足交换律，则称该群为可交换群或阿贝尔群。

群是一个二元组 (G, ∗)，有时候为了方便就直接用 G 表示群。

域

定义：F 是一个集合， + 和 ⋅ 是定义在 F 上的两个二元运算，分别称作加法和乘法。(F,+,⋅) 称为域（field），若满足：

  1. (F,+,⋅) 构成一个环，且 0 和 1 是不同的元素
  2. (F−{0},⋅) 构成可交换群

显然，一个域至少要包含 0 和 1 两个元素。域是一个三元组 (F,+,⋅) ，有时候直接用 F 表示域。

由定义可以推出，给定域 (F,+,⋅) ，对于任意 a∈F ，0 ⋅ a = 0 。

有限域

有限域也被称为伽罗瓦域（Galois field）。

对于任何一个素数 p ，集合 G = {0,1,…,p−1} 对模 p 加法和模 p 乘法构成有限域，记为 GF(p) 。简单来说，GF(p) 就是 mod p，因为一个数模 p 后，结果在 [0, p - 1] 之间。对于元素a和b，那么 (a + b) mod p 和 (a * b) mod p，其结果都是域中的元素。

通常用 GF(q) 表示一个阶为 q 的有限域，q 必定是某个素数 p 的幂。

射影平面

射影平面的概念是从普通直角坐标系引入的，即笛卡尔积坐标系。

笛卡尔积坐标系是没有设置无穷点的，所以为了表示无穷远点，就产生了一个叫做射影平面坐标系的东西，这个射影平面坐标系可以同时表示无穷远点和平常点。

有限域上的椭圆曲线

有限域上的椭圆曲线是指在椭圆曲线的定义式:

$y^2+axy+by=x^3+cx^2+dx+e$

其中所有的系数都是在某个有限域GF(p)中的元素，其中p为一个大素数。

当然，并不是所有的椭圆曲线都适合于加密，最为常用的方程如下:

$y^2=x^3+ax+b$

其中 $4a^3+27b^2 \bmod p \neq 0$

我们称该方程的所有解$(x,y)，(x\in Fp , y \in Fp)$，以及一个称为“无穷远点”(O)组成的集合为定义在 Fp 上的一个椭圆曲线，记为 E(Fp)。

一般定义椭圆曲线密码需要以下条件：

假设E(Fp)对于点的运算 ⊕ 形成一个able群（交换群，逆元存在，封闭性等），设 $p\in E(Fq)$，且满足下列条件的 t 很大

$p \oplus p \oplus … \oplus p=O$

其中共有 t 个 p 参与运算。这里我们称 t 为 p 的周期。此外，对于$Q\in E(Fq)$ ，定有某个正整数 m 使得下列式子成立，定义$m=log_pq$

$Q=m\cdot p =p \oplus p \oplus … \oplus p$（m 个 p 参与运算）

此外，假设 G 是该 $E_q (a,b)$ 的生成元，即可以生成其中的所有元素，其阶为满足 $nG=O$ 的最小正整数 n。

ECC中的ElGamal

假设用户 B 要把消息加密后传给用户 A。

密钥生成

用户A先选择一条椭圆曲线 $E_q (a,b))$ ，然后选择其上的一个生成元 G，假设其阶为 n，之后再选择一个正整数 $n_a$ 作为密钥，计算$P_a=n_aG$。

其中，$E_q(a,b), q,G$ 都会被公开。

公钥为 $P_a$，私钥为 $n_a $。

加密

用户 B 在向用户 A 发送消息 m，这里假设消息 m 已经被编码为椭圆曲线上的点，其加密步骤如下

  1. 查询用户 A 的公钥 $E_q(a,b), q, P_a,G$ 。
  2. 在 (1,q - 1) 的区间内选择随机数 k 。
  3. 根据 A 的公钥计算点 $(x_1,y_1)=kG$。
  4. 计算点 $(x_2,y_2)=kP_a$，如果为 0，则从第二步重新开始。
  5. 计算 $C=m+(x_2,y_2)$
  6. 将 $((x_1,y_1),C)$ 发送给 A。

解密

解密步骤如下

  1. 利用私钥计算点 $n_a(x_1,y_1)=n_akG=kP_a=(x_2,y_2)$。
  2. 计算消息 $m=C-(x_2,y_2)$ 。

关键点

这里的关键点在于我们即使知道了 $(x_1,y_1) $ 也难以知道 k，这是由离散对数的问题的难度决定的。

例子

以 2013 SECCON CTF quals Cryptanalysis 为例

20140127213558

我们已知椭圆曲线方程以及对应的生成元 base，还知道相应的模数以及公钥以及加密后的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
a = 1234577
b = 3213242
n = 7654319

E = EllipticCurve(GF(n), [0, 0, 0, a, b])
#EllipticCurve([a1,a2,a3,a4,a6])
#构造椭圆曲线#y**2+a1*xy+a3*y=x**3+a2*x**2+a4*x+a6
base = E([5234568, 2287747])
pub = E([2366653, 1424308])

c1 = E([5081741, 6744615])
c2 = E([610619, 6218])

X = base

for i in range(1, n):
    if X == pub:
        secret = i
        print "[+] secret:", i
        break
    else:
        X = X + base
        print i

m = c2 - (c1 * secret)

print "[+] x:", m[0]
print "[+] y:", m[1]
print "[+] x+y:", m[0] + m[1]

ECC中的Pohlig-Hellman

加解密

首先我们不妨假设需要求解的式子为：

$Q = l * P$

其中 P 为我们选取的一个基点，l 就是我们选定的随机数，相当于要求解的私钥。

首先求得 P 的阶 n，也就是可使得 n * P 不存在的最小正整数

然后我们将 n 进行分解，我们设

$n = p_1^{e_1} * p_2^{e_2} ……p_r^{e_r}$

然后我们将这些因子拿出来，对于 i 属于 [1, r],计算

$li = l \space mod \space p_i^{e_i}$

于是我们便得到了下面的这一系列等式
$l ≡ (l_1 \space mod \space p_1^{e_1})$
$l ≡ (l_2 \space mod \space p_2^{e_2})$
……
$l ≡ (l_r \space mod \space p_r^{e_r})$

看上去是不是有点眼熟，如果得到了这些 $l_i$ 的值我们就能使用中国剩余定理进行求解得到 l 了，现在的问题就是求解这些 $l_i$

首先我们将 $l_i$ 设为成 $p_i$ 表示的多项式，如下：

$l_i = z_0 +z_1p_i+z_2p_i^2+…+z_{e-1}p_i$

接下来我们的任务就是求解这些 z，注意这里的z应该是属于 $[0,p_i-1]$

下面就很有意思了，为了计算 $z_i$，我们分别取 $P_0$ 和 $Q_0$，并取值：

$P_0 = \frac{n}{p_i}P$

$Q_0=\frac{n}{p_i}Q$

这样我们就有了 $p_i*P_0 = nP$，接下来我们可以得到 $Q_0$ 的表达式：

$Q_0=\frac{n}{p_i}Q=\frac{n}{p_i}(lP)=l(\frac{n}{p_i}P)=lP_0$

其实就是在我们原表达式的两边乘上了 $n/p_i$

这样的话我们再转回 $l_i$，先求解 $z_0$

$l_i*P=Q$

$=>l_i*P_0=Q_0$

$=>(z_0+z_1P_i+…+z_{e-1}P_i^{e-1})P_0=Q_0$

$=> z_0*P_0=Q_0$

这时我们便将在 P 域上的离散对数分解到了 $P_0$ 域上，因为 $P_0$ 的阶是 $n/p_i$，已经较原本的阶 n 运算的复杂度小了很多，当然，除非 n 本身就是个大素数

在这里我们可以求得 $z_0$，然后我们再代回原式

$(z_0+z_1p_i+…+z_{e-1}p_i^{e-1}P_0=Q_0)$

$=>z_0P_0+(z_1p_i+…+z_{e-1}p_i^{e-1}P_0=Q_0)$

$=>(z_1p_i+…+z_{e-1}p_i^{e-1}P_0=Q_0-z_0P_0)$

$=>z_1p_i=Q_0-z_0P_0$

此时就可以求解 $z_1$，然后依次将 $z_i$ 全部算出来，这样我们就得到了 $l_1$，然后便可以代入前面的等式，将 $l_1$ 都求出后即可利用中国剩余定理求出 $l$

例子

picoCTF 2017的 ECC 2-200 题目

1
2
3
4
5
6
7
8
9
10
11
12
Elliptic Curve: y^2 = x^3 + A*x + B mod M
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = *You can figure this out with the point below :)*

P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
n = *SECRET*
n*P = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440)

n < 400000000000000000000000000000

Find n.

第一步解决 b 通过重新排列椭圆曲线方程：

$y^2 = x^3 + ax + b\bmod n$

$b = y^2 - x^3 - ax\bmod n$

在Sage中，可以通过替换 x 和 y 值求出 b，如下所示：

1
2
3
4
5
6
7
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
x, y = P[0], P[1]
b = (y^2 - x^3 - A*x) % M
print(b)
#25255205054024371783896605039267101837972419055969636393425590261926131199030

再求得P的阶，然后将其分解，sage 如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = 25255205054024371783896605039267101837972419055969636393425590261926131199030
P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
Q = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440)

F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)
P.order()
#93556643250795678718734474880013829509196181230338248789325711173791286325820
factor(P.order())
#2^2 * 3 * 5 * 7 * 137 * 593 * 24337 * 25589 * 3637793 * 5733569 * 106831998530025000830453 * 1975901744727669147699767

之后就是求分解后对应的阶下也就是 $P_0$ 对应的 $l_i$ 了，这个我们也可以用 sage 里的 discrete_log 函数来直接完成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
primes = [4, 3, 5, 7, 137, 593, 24337, 25589, 3637793, 5733569, 106831998530025000830453, 1975901744727669147699767]
dlogs = []
for fac in primes:
    t = int(P.order()) / int(fac)
    dlog = discrete_log(t * Q, t * P,operation = "+")
    dlogs += [dlog]
    print("factor:" + str(fac) + ",Discrete Log:" + str(dlog))
'''
factor:4,Discrete Log:2
factor:3,Discrete Log:1
factor:5,Discrete Log:4
factor:7,Discrete Log:1
factor:137,Discrete Log:129
factor:593,Discrete Log:224
factor:24337,Discrete Log:5729
factor:25589,Discrete Log:13993
factor:3637793,Discrete Log:1730599
factor:5733569,Discrete Log:4590572
'''

可以看到有两个阶的 $l_i$ 没有算出来，不过这并不影响我们得到结果，得到了这些以后我们就可以利用中国剩余定理来求解了，而这也可以直接在 sage 里使用 crt 函数来调用：

1
2
3
4
primes = [4, 3, 5, 7, 137, 593, 24337, 25589, 3637793, 5733569]
dlogs = [2, 1, 4, 1, 129, 224, 5729, 13993, 1730599, 4590572]
crt(dlogs,primes)
#152977126447386808276536247114

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = 25255205054024371783896605039267101837972419055969636393425590261926131199030
P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
Q = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440)
F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-2]
dlogs = []
for fac in primes:
    t = int(P.order()) / int(fac)
    dlog = discrete_log(t*Q,t*P,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order

l = crt(dlogs,primes)
print(l)