当前位置:   article > 正文

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

椭圆曲线离散对数问题

椭圆曲线定义

设Fp 表示具有p个元素的有限域,p > 3为一个素数。椭圆曲线上的有理点集合E(Fp)定义为
在这里插入图片描述在这里插入图片描述
在这里插入图片描述

判别式 = 4a3 + 27b2 != 0(平滑无奇点)

点的加法

设E(Fp)上两点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代入y2= x3+ Ax + B, 整理:

x3 - c2 x2 + (A - 2cd)x + (B - d2) = 0 = (x - x1)(x - x2)(x - x3)

=> x3 = c2 - x1 - x2

在这里插入图片描述

P = Q时,2y * y’ = 3 x2 + a => k = y’ = (3 x2 + a) / 2y

在这里插入图片描述

点的数乘和阶

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

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

在这里插入图片描述

{O, P, 2P, … , (r - 1)P}是E(Fp)的一个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:

img

其中不妨令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 = ∑ i = 1 n \sum_{i=1}^n i=1n ai ti Mi + KM

x = aj tj Mj (mod mj) 因为 mj | M, mj | Mk (k != j)

x = aj (mod mj)

算法步骤:

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可以表示为z0 + z1 * p + z2 * p2 +…+ze-1 pe-1 , 其中zi 在[0, p - 1]取值

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

在这里插入图片描述

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

由于l * P = Q => (li + k * piei) * P = Q => (li + k * piei) * P0 = Q0

=> li * P0 = Q0

=>(z0 + z1 * pi + z2 * pi2 +…+ze-1 piei-1 ) P0 = Q0

=>z0 * P0 = Q0 (把原本的阶从n变成现在的pi, 结合Pollard Rho求解)

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

其中:

在这里插入图片描述

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

Q1 = (n / pi2) * (Q - z0 * P)

​ = (n / pi2) * ((li + k * piei) * P - z0 * P)

​ = (n / pi2) * P * (li - z0 + k * piei)

​ = P0 * (1 / pi ) * (z1 * pi + z2 * pi2 +…+ze-1 piei-1 + k * piei)

​ = P0 * Z1

因此,我们易知Zi+1 = f(Z0, Z1, … , Zi)

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

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

MOV攻击

  • MOV攻击利用一个双线性配对。双线性配对(大致上)是一个函数e,它将椭圆曲线E(Fq)中的两个点映射到有限域Fq^k中的一个元素,其中k是与该曲线相关的嵌入度
  • 嵌入度是满足k≥2且椭圆曲线的阶n∣qk−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=ur
  • 所以我们可以解Fq^k中的离散对数(给定ur和u,解出r),以解决椭圆曲线中的离散对数!
  • 通常情况下,嵌入度k非常大(与q相同大小),因此将离散对数转到Fq^k中没用。
  • 但是对于某些曲线来说,嵌入度足够小(特别是超奇异曲线,其中k≤6),这使得MOV攻击成为可能。
  • 例如,一条256位q的曲线通常提供128位的安全性(即可以用2128步进行攻击);但如果它的嵌入度为2,那么我们可以将离散对数映射到有限域Fq^2中求解,这只提供60位的安全性。

小结

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

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

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

更多细节可以参考:

SM2椭圆曲线公钥密码算法

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/612174
推荐阅读
相关标签
  

闽ICP备14008679号