椭圆曲线离散对数问题以及求解

椭圆曲线定义

设F_p 表示具有p个元素的有限域，p > 3为一个素数。椭圆曲线上的有理点集合E(F_p)定义为

判别式 = 4a³ + 27b² != 0(平滑无奇点)

点的加法

设E(F_p)上两点P = (x1, y1), Q = (x2, y2)

P + Q = R是指过P和Q的直线与曲线的另一交点关于x轴的对称点（P=Q时是切线）

PQ：y = cx + d

设R的关于x轴对称点：(x3, c * x3 + d), 那么R(x3, - c * x3 - d)

c = (y2 - y1) / (x2 - x1)

d = y1 - c * x1

将y = cx + d代入y²= x³+ Ax + B, 整理：

x³ - c² x² + (A - 2cd)x + (B - d²) = 0 = (x - x1)(x - x2)(x - x3)

=> x3 = c² - x1 - x2

P = Q时，2y * y’ = 3 x² + a => k = y’ = (3 x² + a) / 2y

点的数乘和阶

[k] P = P + P + … + P(k个)

若r是最小的正整数s.t.[r]P = O（两个对称点相加的结果）

{O, P, 2P, … , (r - 1)P}是E(F_p)的一个r阶子群（加法数乘封闭）

ECDLP

给定素数p和椭圆曲线E，对Q=kP，在已知P，Q 的情况下求出小于p的正整数k。可以证明由k和P计算Q比较容易，而由Q和P计算k则比较困难, 一般情况下只能暴力遍历所有kP

Pollard Rho攻击方法

一种随机性的概率型算法，基于PR算法我们可以加速大整数的因子分解

**原理：**生日悖论，k个学生时这些学生里至少有两个人的生日在同一天的概率会是多大，大约为23时就可以使概率提高到50%，当取到58人时概率就已经达到了99%

首先设定一个ECDLP问题，对于椭圆曲线E(Fp)，我们取基点P，且P的阶为N，然后对于曲线上另一点Q，我们需要求k，使得P*k=Q

算法步骤

1.我们令G=E(Fp)，然后我们将G分成三个大小相近的部分S1,S2,S3

2.设定一个用于生成随机的步数的迭代函数f：

其中不妨令R0 = P（Q也可以）

3.由上式可知Ri是P和Q的线性组合，即Ri = ai P + bi Q

也可以把ai和bi的递推关系写出来

4.我们不断生成配对(Ri, R2i)直到找到某个m使得Rm = R2m

限制1：gcd(bm - b2m, N) = 1，否则逆元不存在

假设gcd(a, p) = d 且 ax = 1(mod p)

gcd(a, p) = d =>

ax + py = d =>

1 = d(mod p) =>

d = 1(d <= p)

限制2：对与不同的椭圆曲线能命中的概率与效率也是不同的，这取决于我们设定的迭代函数以及我们初始化的点位，有时候没取好可能无法相等

例子：

Z3 = (50, 35) = 1 P + 2 Q

Z6 = (50, 35) = 8 P + 8 Q

211 P = O(求阶是容易的)

1 P + 2 Q = 8 P + 8 Q =>

-7 P = 6 Q =>

204 P = 6 Q =>

Q = 34 P

Pohlig-Hellman攻击方法

**原理：**中国剩余定理

假设整数m1,m2, … ,mn两两互质，则对任意的整数：a1,a2, … ,an，方程组（S）有解，设M = m1 * m2 * … * mn

这里Mi = M / mi， ti * Mi = 1(mod mi)

证明也比较明显：

x = ${\sum }_{i=1}^n$ a_i t_i M_i + KM

x = a_j t_j M_j (mod m_j) 因为 m_j | M, m_j | M_k (k != j)

x = a_j (mod m_j)

算法步骤：

1.我们不妨假设需要求解Q = l * P中的l，同时我们知道P的阶为n（np = O）

同时，n = p1^e1 * p2^e2 * … * pr^er

我们希望得到r个 l = li(mod pi^ei)的式子

这样的话就可以通过中国剩余定理求解出l

这里的难点就是如何求出每个li

2.li的表示：由于是在mod pi^ei 的意义下

li可以表示为z₀ + z₁ * p + z₂ * p² +…+z_e-1 p^e-1 , 其中z_i 在[0, p - 1]取值

3.zi的计算：引入P0和Q0

则pi * P₀ = nP = O => P₀ 的阶是pi(大大降阶)

由于l * P = Q => (li + k * pi^ei) * P = Q => (li + k * pi^ei) * P₀ = Q₀

=> li * P₀ = Q₀

=>(z₀ + z₁ * pi + z₂ * pi² +…+z_e-1 pi^ei-1 ) P₀ = Q₀

=>z₀ * P₀ = Q₀ （把原本的阶从n变成现在的pi, 结合Pollard Rho求解)

对于剩余的z_j 我们同样可以通过求解Qj = zj * P₀的方式求解

其中：

不妨验证一下Q1 = z1 * P0 的正确性

Q1 = (n / pi²) * (Q - z0 * P)

​ = (n / pi²) * ((li + k * pi^ei) * P - z0 * P)

​ = (n / pi²) * P * (li - z0 + k * pi^ei)

​ = P0 * (1 / pi ) * (z₁ * pi + z₂ * pi² +…+z_e-1 pi^ei-1 + k * pi^ei)

​ = P0 * Z1

因此，我们易知Z_i+1 = f(Z₀, Z₁, … , Z_i)

参考https://wstein.org/edu/2010/414/projects/novotney.pdf

4.求出了每个zi就可以还原li，从而有r组同余方程，通过中国剩余定理求出l

MOV攻击

• MOV攻击利用一个双线性配对。双线性配对（大致上）是一个函数e，它将椭圆曲线E(F_q)中的两个点映射到有限域F_q^k中的一个元素，其中k是与该曲线相关的嵌入度。
• 嵌入度是满足k≥2且椭圆曲线的阶n∣q^k−1之最小的k。
• 双线性意味着对于点对(P,Q)，我们有e(rP,sQ)=e(P,Q)^rs。 因此，如果要计算P的离散对数r，对于椭圆曲线上另外一个点Q（这个Q点的选取任意），我们可以计算u=e(P,Q)和v=e(rP,Q)。
• 由于e是双线性的，我们有v=e(P,Q)^r=u^r。
• 所以我们可以解F_q^k中的离散对数（给定u^r和u，解出r），以解决椭圆曲线中的离散对数！
• 通常情况下，嵌入度k非常大（与q相同大小），因此将离散对数转到F_q^k中没用。
• 但是对于某些曲线来说，嵌入度足够小（特别是超奇异曲线，其中k≤6），这使得MOV攻击成为可能。
• 例如，一条256位q的曲线通常提供128位的安全性（即可以用2¹²⁸步进行攻击）；但如果它的嵌入度为2，那么我们可以将离散对数映射到有限域F_q^2中求解，这只提供60位的安全性。

小结

Pollard Rho构造碰撞，形成比例关系

Pohlig-Hellman分解质因数，降阶，约化成简单ECDLP

MOV通过双线性配对，对嵌入度较小的曲线，约化成更简单的DLP（存在亚指数解法）

更多细节可以参考：

SM2椭圆曲线公钥密码算法