type
status
date
summary
password
category
slug
icon
🥂ECC
基本概念
椭圆曲线不是椭圆而是椭圆积分方程
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合
- 椭圆曲线的定义式：
一般方程：
- 1椭圆曲线方程是一个齐次方程
- 椭圆曲线都是关于X轴对称的曲线。
- 2曲线上的每个点都必须是非奇异的（光滑的），偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0
- 3圆曲线的形状，并不是椭圆的。只是因为椭圆曲线的描述方程，类似于计算一个椭圆周长的方程故得名
- 椭圆曲线表达式
加法运算规则
P,Q,R如果在一条直线上，并且在椭圆曲线上，那么P+Q+R=0(椭圆曲线阿尔贝群)
为了避免p点没有切线，因此要满足
代数加法
几何加法
加法
A+B
二倍运算
2A
普通相交三点：P+Q+R=0
普通相交两点：P+P+Q=0，P+Q+Q=0 （一点相切）
垂直相交两点：P+Q+0=0 （垂直X轴）
垂直相交一点：P+P+0=0 （垂直X轴+一点相切）
减法
P-Q=P+(-Q),其中-Q=(X,-Y)=(X,P-Y),其中P为椭圆曲线的素域。
离散化
椭圆曲线密码体制使用的是有限域上的椭圆曲线，即变量和代数为有限域中的元素。有限域GF（p）上的椭圆曲线是指满足方程
/eq
的所有点再加上一个无穷远点O构成的集合，其中a，b,x,y均在有限域上取值，p是素数。记为Ep(a,b)
椭圆曲线上的阶：椭圆曲线中元素的个数，表示|Ep(a,b)|
椭圆曲线上元素的阶： 记为ord(P)，令nP=O（无穷远点）的最小整数。
生成元： ord(G)=|Ep(a,b)|,则称G为Ep(a,b)的生成元,
椭圆曲线上的离散对数问题
ECC算法
加解密
参数选取：选定一条椭圆曲线 Ep(a,b)，并取椭圆曲线上一点作为基点 G；(G是Ep(a,b)的生成元)
产生公钥和私钥：选择一个私有密钥 Sk (k<n)，并生成公开密钥 Pk=SkG；
加密：将明文编码到 Ep(a,b)上的一点 M，并产生一个随机整数 r（0<r<n，n为 G 的阶数）；C1=(C1,C2),C1=M+rPk和 C2=rG
解密：
M=C1-SkC2
C1-SkC2=M+rPk-SkrG=M+rSkG-SkrG=M
常见攻击(求解私钥k)
Smart’s attack
适用于：E.order()=p
即一个椭圆曲线的阶等于 p，意味着曲线上的点的数量与有限域的元素数量相同
p=h*n的椭圆曲线
attack：求解 Q=k*P中的k值
Pohlig-Hellman算法
主要解决：整数域中
里的 x以及椭圆曲线离散对数问题中 Gk=Q的 G的阶 n
P的阶n: nP=O
Q mod nP =l
Q mod n=l
Q 模上n的因数等于l
寻找在不同因子下的l的对应同余数li
脚本
if i > 10**9:
print(i)
break 注意！！！有限制条件，可能求出的结果不准确，需进行调整
ECDLP
ECDLP即椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem）
- 将椭圆曲线中的加法运算与离散对数中的模乘运算相对应
- 将椭圆曲线中的乘法运算与离散对数中的模幂运算相对应
ECDSA
ECDSA（Elliptic Curve Digital Signature Algorithm）基于椭圆曲线密码学的数字签名算法,用于生成和验证数字签名
📎 参考
🤔总结
- smart's attack E.order()=p
- ECDLP 转化成 离散对数问题
- PH算法 G的n的可分解