ECC¶
概述¶
ECC 全称为椭圆曲线加密，EllipseCurve Cryptography，是一种基于椭圆曲线数学的公钥密码。与传统的基于大质数因子分解困难性的加密方法不同，ECC依赖于解决椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。目前椭圆曲线主要采用的有限域有
- 以素数为模的整数域GF(p)，通常在通用处理器上更为有效。
- 特征为 2 的伽罗华域GF（2^m），可以设计专门的硬件。
基本知识¶
我们首先来了解一下有限域上的椭圆曲线，有限域上的椭圆曲线是指在椭圆曲线的定义式
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)对于点的运算\oplus 形成一个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已经被编码为椭圆曲线上的点，其加密步骤如下
- 查询用户A的公钥E_q(a,b), q, P_a,G 。
- 在(1,q-1) 的区间内选择随机数k 。
- 根据A的公钥计算点(x_1,y_1)=kG 。
- 计算点(x_2,y_2)=kP_a ，如果为O，则从第二步重新开始。
- 计算C=m+(x_2,y_2)
- 将((x_1,y_1),C) 发送给A。
解密¶
解密步骤如下
- 利用私钥计算点n_a(x_1,y_1)=n_akG=kP_a=(x_2,y_2)。
- 计算消息m=C-(x_2,y_2) 。
关键点¶
这里的关键点在于我们即使知道了(x_1,y_1) 也难以知道k，这是由离散对数的问题的难度决定的。
2013 SECCON CTF quals Cryptanalysis¶
这里我们以2013年SECCON CTF quals 中的 Cryptanalysis 为例，题目如下
这里，我们已知椭圆曲线方程以及对应的生成元 base，还知道相应的模数以及公钥以及加密后的结果。
但是可以看出的我们的模数太小，我们暴力枚举获取结果。
这里直接参考 github上的 sage 程序，暴力跑出 secret key。之后便可以解密了。
a = 1234577
b = 3213242
n = 7654319
E = EllipticCurve(GF(n), [0, 0, 0, a, b])
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]
暴力跑出结果
[+] secret: 1584718
[+] x: 2171002
[+] y: 3549912
[+] x+y: 5720914