椭圆曲线普通方程： \({y^2} + {a_1}xy + {a_3}y = {x^3} + {a_2}{x^2} + {a_4}x + {a_6}\) 椭圆曲线P+Q加法定义：连接P、Q两点作直线，交椭圆曲线于第三点G，过G作垂直于x轴直线，交椭圆曲线于R，则R被定义为P+Q的结果：P+Q=R。 \(P!=Q,斜率m=\frac{y_P-y_Q}{x_P-x_Q}\\ P==Q,斜率m=\frac{3x_P^2+a}{2y_P}\\ x_R=m^2-x_P-x_Q\mod p\\ y_R=y_P+m(x_R-x_P)\mod p\) 点乘kG，根据k的二进制表达的长度来做迭代计算。每次迭代中，根据k相应的二进制位 (例如k = 0d11 = 0b1011)的取值，决定是只做Point_Double(当该bit为0)，还是在Point_Double之后再多做一次Point_Add。这个算法被称为 Double_and_Add。
椭圆曲线是连续的，不适合加密。所以，需要把椭圆曲线变成离散的点，也就是把椭圆曲线定义在有限域上。有限域椭圆曲线方程Ep(a,b)，p为质数： \({y^2} = {x^3} + ax + b\left( {\bmod p} \right)\\4{a^3} + 27{b^2} \ne 0\left( {\bmod p} \right)\) 相应地，椭圆曲线有限域加法需要对p取模，通过加法进而定义乘法。
椭圆曲线上一点P，存在最小的正整数n使得数乘nP=O∞，则将n称为P的阶(order)，这n个点形成一个循环阿贝尔群。
ECC
利用有限域椭圆曲线进行加密的方法即为ECC(Elliptic Curve Cryptography)：考虑K=kG ，其中K、G为椭圆曲线Ep(a,b)上的点，n为G的阶order（nG=O∞），k为小于n的整数。则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难。点G称为基点（base point），k（k<n）为私有密钥（privte key），K为公开密钥（public key）。
加密：明文编码到点M，选择任意随机数r（r<n），计算C1=M+rK，C2=rG
解密：计算C1-kC2=M+rK-krG=M+rK-rK=M（K=kG）
阶可分解为若干小素数，Pohlig-Hellman攻击（sample：ECC2，picoCTF_2017）
\[对于给定Q=l*P，求得P的阶n，即n*P=O\infty\\分解n=p_1^{e_1}*p_2^{e_2}...*p_r^{e_r}\\对于目标l，假设求得以下l_i：\\l\equiv l_1\mod p_1^{e_1}\\l\equiv l_2\mod p_2^{e_2}\\l\equiv l_r\mod p_r^{e_r}\\即可以通过中国剩余定理求得l\\对于任意i，有：l=k*p_i^{e_i}+l_i\\定义点P_i=\frac{n}{p_i^{e_i}}P，Q_i=\frac{n}{p_i^{e_i}}Q，由于P_i * p_i^{e_i}=n*P=O\infty，因此P_i的阶为p_i^{e_i}\\对Q=l*P两边同时乘\frac{n}{p_i^{e_i}}，得：Q_i=l*P_i\\将l代入，得：Q_i=(k*p_i^{e_i}+l_i)*P_i=k*p_i^{e_i}*P_i+l_i*P_i=l_i*P_i\\由于P_i的阶为p_i^{e_i}，比n小，直接对所有的Q_i，P_i求离散对数，求得相应的l_i，再通过中国剩余定理求得l\]E(Fp)=p，曲线的阶等于模数p，SmartAttack
sample：two_DLP，gdqwb-2021
超奇异椭圆曲线（阶整除p^k-1，2<=k<=6），MOV攻击
sample：Trick，cmcc-200421；keygreed，VolgaCTF 2020；two_DLP，gdqwb-2021 \(嵌入度k是满足k>=2，且阶n整除p^k-1的最小k。\)
| 常见：E(Fp)=p+1 | p^2 - 1 |
多组不同的(c,a,b,n)的四元组，对同一明文加密，低指数广播攻击
已知两个明文的差，相关密文攻击（sample：relatedmessage，dasctf-2020-12）
ECDSA
用于数字签名，ECC与DSA的结合，签名过程与DSA类似。选择椭圆曲线Ep(a,b)和基点G，选择私钥d（d<n，n为G的阶），计算公钥P=dG。
签名：（r，s）为明文m的签名 \(1.产生随机整数k（k<n），计算kG=(x_1,y_1)\\ 2.X(R)运算为取R的x坐标，计算r=X(kG)=x_1 \mod n\\ 3.对于明文m计算哈希值e=H(m)，如SHA256\\ 4.计算s=k^{-1}(e+dr) \mod n\) 验证： \(1.计算e=H(m)\\ 2.计算X(s^{-1}*(eG+rP))如果等于r，则验证通过\\ 原理：对s=k^{-1}(e+dr) \mod n两边乘以(s^{-1}kG)，得：\\ kG=s^{-1}(eG+rdG)=s^{-1}*(eG+rP)\\ r=X(kG)=X(s^{-1}*(eG+rP))\)
python实现
1 | |
随机整数k相同或可预测
通过两个签名值(r1 , s1)、(r2, s2)，由于k值一样，故r值也一样 \(s_1 = k^{-1}(e_1 + d*r) \mod n\\ s_2 = k^{-1}(e_2 + d*r) \mod n\\ 两式相减：s_1-s_2 = k^{-1}(e1 - e2) \mod n\\ 因此：k=(s_1-s_2)^{-1}*(e1 - e2) \mod n\\ 再把k代入原式求得d=(sk-e)*r^{-1} \mod n\) 对于已知随机整数k线性关系：k2=a*k1+b的情况可同理求d。