有限域上的椭圆曲线
椭圆曲线是什么:
满足 Weierstrass 方程
$$
Y^2 = X^3 + AX + B
$$
的点集，称为椭圆曲线(elliptic curve)。下面给出两个椭圆曲线的例子：
可见它的长相与椭圆并没有什么联系。我们可以在椭圆曲线E上定义“加”运算：假设有P,Q两点，则P⊕Q的步骤如下：
- 连接PQ引出一条直线，该直线交E于R点
- R相对于x轴的对称点就是P+Q的结果R’
无穷远点：
当P,Q(P’)关于x轴对称时，P与P‘的连线交E于某个无穷远点，记为O
需要注意的是，我们只引入了一个无穷远点，假想它在每一条铅直线上。
如果把某个点加上无穷远点，会发生什么情况呢？P 与 O 的连线交 E 于三个点—— O,P,P′，于是把 **P′ **作为直线与 E 相交得到的点；再关于 x 轴对称一次，又回到了 P. 这也就是说：P+O=P
我们意识到，O 是加法运算的单位元。
椭圆曲线加法群：
由于 O 的存在，任意两个点都是可加的。那么带着刚刚引进的无穷远点 O ，我们重新定义椭圆曲线。
一个椭圆曲线(elliptic curve) E 是满足 Weierstrass 方程
$$
E:Y^2 = x^3 + AX + B
$$
的解集，以及无穷远点 O. 其中 A,B 满足
$$
4A^3 + 27B^2 ≠ 0
$$
解释为什么要 4A^3^ + 27B^2^ ≠ 0.
我们知道x^3^ + Ax + B 可以表达为 (x−p~1~)(x−p~2~)(x−p~3~)，此时当且仅当**p~1~,p~2~,p~3~**互不相同，才会有 4A^3^+27B^2^ ≠ 0.
至于如果 4A^3^ + 27B^2^ = 0，会出现什么情况？
这与我们平常见到的两类椭圆曲线，长相差异有点大。它们存在奇点，这会导致我们一些算法失效。
在椭圆曲线上，⊕ 满足加法的性质，以下简写为 “+”。我们有：
有单位元：P + O = O + P = P有逆元：P + (−P) = O，其中 −P 是 P 关于 x 轴的对称点。结合律：(P + Q) + R = P + (Q + R)交换律：P + Q = Q + P
以上每一条性质都可以手工验证。从而 **(E,+)**是一个阿贝尔群。于是立刻可以定义数乘运算：
对于正整数 n 和椭圆曲线上的点 P，定义
$$
nP = P + P + P + ⋯ + P
$$
显然，nP 可以通过类似于快速幂的算法，以 O(log n) 次加法的代价求出来。
给定 P 和 Q=nP，求解 n，就是椭圆曲线上的离散对数问题。
Sage演示：
下面创建一个有理数域上的椭圆曲线：
1 | E = EllipticCurve([-4,4]) |
y^2^ = x^3^ - 4x + 4
可以获取x = 1 时 y 的坐标：
1 | P = E.lift_x(1) |
可以进行加法和数乘：
1 | P = E(1, 1) |
单位元（无穷远点）用 E(0) 来得到。可以进行运算：
1 | O = E(0) |
现在我们造一个实数域上的椭圆曲线：
1 | E = EllipticCurve(RealField(), [-15,8]) |
y^2^ = x^3^ - 15.0000000000000 * x + 8.00000000000000
运算：
1 | P = E.lift_x(666) |
有限域上的椭圆曲线:
密码学需要的是离散的数学，而以上介绍的都是连续的。我们如果想把椭圆曲线应用于密码学，就需要在它上面定义一个有限群。
设 p 为质数，有限域 Fp 上的椭圆曲线是下面的方程：
$$
E:Y2=X3+AX+B\ \ with\ \ A,B∈Fp,4A^3+27B^2≠0
$$
其点集为：
$$
E(F_p)={(x,y) : x,y∈Fp, y2=x3+Ax+B}∪{O}
$$
其中所有的运算在模 p 意义下进行。
举个🌰，考虑F~13~上的椭圆曲线：
$$
E:\ Y^2\ =\ X^3 +3X +8
$$
想找出这个椭圆曲线上的点集，只需要枚举 x，然后看是不是有 y 使得y^2^ 等于 x^3^+3x+8. 这是一个二次剩余问题，我们已经解决得比较好了。在 x=0 的时候，没有 y 与之对应；在 x=1 的时候，√12=5,8，从而 **(1,5) **和 (1,8) 是椭圆曲线上的点。
Sage 可以在有限域上建立椭圆曲线，并枚举所有点：
1 | E = EllipticCurve(GF(13),[3,8]) |
在有限域椭圆曲线上进行加法：
1 | E = EllipticCurve(GF(13), [3, 8]) |
来观察有限域 F~13~ 上的椭圆曲线的加法表：
▲ F~13~ 上的椭圆曲线 E:Y^2^=X^3^+3X+8 的加法表
有限域上的椭圆曲线以及加法，构成了一个有限群。现在来研究这个群里的元素个数。
我们知道，一个整数在有限域内，大概有一半的概率是二次剩余，一半的概率不是。所以我们猜测
$$
card\ E(Fp)≈50 %\ ⋅p⋅2+1=p+1
$$
这个猜测挺准确。事实上
$$
card\ E(Fp)=p+1−t_p\ \ where\ |t_p|≤2\sqrt{p}
$$
有限域上的椭圆曲线，点的分布与实数域上的椭圆曲线非常不同。来看两个例子。
▲ 有限域上椭圆曲线的点分布。它们 A=3,B=8，左：F~13~，右：F~101~
椭圆曲线离散对数问题:
经典的椭圆曲线上的离散对数问题，是给定点 P和 nP，要推出 n 的值。有限域椭圆曲线上的离散对数问题亦然。
设 E 是有限域 F~p~ 上的椭圆曲线，P,Q∈E(F~p~). 椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem) 是指：找到一个整数 n 使得 Q=nP. 我们记
$$
n=log_P(Q)
$$
并称 n 是以 P 为底 Q 的椭圆曲线离散对数。
举一个离散对数的例子。考虑 F~73~ 上的椭圆曲线
$$
E:Y^2=X^3+8X+7
$$
其上有点 P=(32,53) 和点 Q=(39,17). 计算得知 Q=11P，于是log~P~(Q)=11.
1 | E = EllipticCurve(GF(73), [8, 7]) |
很明显，符合条件的 n 会有很多很多个，就像有限域上的离散对数也有无限多个一样。为了简化问题，我们定义 P 的阶是使得 xP=yP,x>y 的最小的 s:=x−y，于是 sP 显然就是无穷远点。顺带一提，由于拉格朗日定理，s 是 card E(F~p~) 的因数。离散对数是一个解系，每个解可以表示成 n~0~+k⋅s,k∈Z.
所以现在，离散对数的全体解，是集族Z/sZ中的一个元素。以后可以直接取 [0,p) 之间的一个代表元 n~0~，来代表离散对数的解了。另外，我们发现
$$
log_P(Q_1+Q_2)\ =\ log_P(Q_1)+log_P(Q_2)
$$
从而 log~P~:E(F~p~)→Z/sZ 是群 E(F~p~) 到群 Z/sZ 的一个同态映射！
最后，需要注意的一点是，并不是全体 log~P~(Q) 都可以求出解。举个例子：在我们刚刚讨论的那条曲线上，存在 (20,65) 这个点，但它不是 P 的倍数。群论上这是很好理解的，因为这一个 P 的阶不等于 E 的阶，它无法生成整个 E：
1 | E = EllipticCurve(GF(73), [8, 7]) |
目前已知的最快的 ECDLP 算法，需要 √p 次运算来求解 E(F~p~) 上的离散对数问题。因此 ECDLP 是一个相当困难的问题。
例题：
Jarvis OJ: 简单ECC概念
已知椭圆曲线加密 Ep(a,b)参数为 p = 15424654874903,
a = 16546484, b = 4548674875, G(6478678675,5636379357093)私钥为 k = 546768，求公钥 K(x,y)
提示：K=kG注：题目来源XUSTCTF2016
直接用Sage算出kG就行
1 | E = EllipticCurve(GF(15424654874903), [16546484, 4548674875]) |
ElGamal:
假设用户 B 要把消息加密后传给用户 A。
密钥生成
用户A先选择一条椭圆曲线 E~q~(a,b) ，然后选择其上的一个生成元 G，假设其阶为 n，之后再选择一个正整数 na 作为密钥，计算P~a~ = n~a~G。
其中，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~，如果为 0，则从第二步重新开始。
- 计算 C = m + (x~2~,y~2~)
- 将 ((x~1~,y~1~),C) 发送给 A。
解密
解密步骤如下
- 利用私钥计算点 n~a~(x1,y1) = n~a~kG = kP~a~ = (x2,y2)。
- 计算消息 m = C − (x2,y2) 。
关键点
这里的关键点在于我们即使知道了 (x1,y1) 也难以知道 k，这是由离散对数的问题的难度决定的。
例子
以 2013 SECCON CTF quals Cryptanalysis 为例
exp:
1 | #Sage |
ECC中的Pohlig-Hellman
加解密
首先我们不妨假设需要求解的式子为：
Q=l ∗ P
其中 P 为我们选取的一个基点，l就是我们选定的随机数，相当于要求解的私钥。
首先求得 P 的阶 n，也就是可使得 n * P 不存在的最小正整数
然后我们将 n 进行分解，我们设
n=p~1~^e1^∗p~2~^e2^……p~r~^er^
然后我们将这些因子拿出来，对于 i 属于 [1, r],计算
l~i~ = l mod p~i~^ei^
于是我们便得到了下面的这一系列等式
l ≡ (l~1~ mod p~1~^e1^)
l ≡ (l~2~ mod p~2~^e2^)
……
l ≡ (l~r~ mod p~r~^er^)
看上去是不是有点眼熟，如果得到了这些 li 的值我们就能使用中国剩余定理进行求解得到 l 了，现在的问题就是求解这些 l~i~
首先我们将 l~i~ 设为成 pi 表示的多项式，如下：
l~i~=z~0~+z~1~p~i~+z~2~p~i~^2^+…+z~e−1~p~i~
接下来我们的任务就是求解这些 z，注意这里的z应该是属于 [0,pi−1]
下面就很有意思了，为了计算 zi，我们分别取 P0 和 Q0，并取值：
P~0~=(n/p~i~)P
Q~0~=(n/p~i~)Q
这样我们就有了 pi∗P0=nP，接下来我们可以得到 Q0 的表达式：
Q~0~ = (n/p~i~)Q=(n/p~i~)(l P)=l (n/p~i~)P=l * P~0~
其实就是在我们原表达式的两边乘上了 n/p~i~
这样的话我们再转回 l~i~，先求解 z~0~
l~i~∗P=Q
=>l~i~ ∗ P~0~ = Q~0~
=>(z~0~+z~1~P~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~1~p~i~+…+z~e−1~p~i~^e−1^P~0~=Q~0~)
=>z~0~P~0~+(z~1~p~i~+…+z~e−1~p~i~^e−1^P~0~=Q~0~)
=>(z~1~p~i~+…+z~e−1~p~i~^e−1^P~0~=Q~0~−z~0~P~0~)
=>z~1~p~i~=Q~0~−z~0~P~0~
此时就可以求解 z~1~，然后依次将 z~i~ 全部算出来，这样我们就得到了 l~1~，然后便可以代入前面的等式，将 l~1~ 都求出后即可利用中国剩余定理求出 l
例子
picoCTF 2017的 ECC 2-200 题目：
1 | Elliptic Curve: y^2 = x^3 + A*x + B mod M |
由于不知道B，第一步就是解决B，通过重新排列椭圆曲线方程：
y^2^ = x^3^ + ax +b mod n
b = y^2^ − x^3^ − ax mod n
在Sage中，可以通过替换 x 和 y 值求出 b，如下所示：
1 | M = 93556643250795678718734474880013829509320385402690660619699653921022012489089 |
再求P的阶，然后将其分解，Sage如下:
1 | M = 93556643250795678718734474880013829509320385402690660619699653921022012489089 |
之后就是求分解后对应的阶下也就是P~0~对应的l~i~了，这个我们也可以用sage里的discrete_log()函数来直接完成
1 | primes = [4, 3 , 5 , 7 , 137 , 593 , 24337 , 25589 , 3637793 , 5733569 ,106831998530025000830453 , 1975901744727669147699767] |
我们发现有两个阶的l~i~没有算出来，不过这并不影响我们得到结果，得到了这些以后我们就可以利用中国剩余定理来求解了，可以直接在sage里调用crt函数：
1 | primes = [4, 3, 5, 7, 137, 593, 24337, 25589, 3637793, 5733569] |
完整代码：
1 | M = 93556643250795678718734474880013829509320385402690660619699653921022012489089 |