椭圆曲线定义
设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：
其中不妨令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
Original: https://blog.csdn.net/weixin_40986490/article/details/126255092
Author: 白速龙王的回眸
Title: 椭圆曲线离散对数问题以及求解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/720655/
转载文章受原作者版权保护。转载请注明原作者出处！