ECC 笔记
ECC 简介
椭圆曲线密码学(Elliptic Curve Cryptography， ECC)，又称椭圆曲线密码体制、椭圆曲线加密算法等。椭圆曲线加密算法在比特币、目前的二代居民身份证和区块链领域有着广泛的应用。
在很多情况中，ECC在性能(更少的计算量)和带宽(更短的签名和密钥)上都比RSA和离散对数(DL)方案更具有优势。
ECC椭圆曲线加密，它的安全性基于椭圆曲线上的离散对数问题。
ECC 原理
ECC 常用椭圆曲线定义
\(\Z_p\ (p\geq3)\) 上的椭圆曲线指满足以下条件的所有对 \((x, y)\in \Z_p\) 的集合 \[ y^2\equiv x^3+ax+b\pmod{p} \] 以及一个无穷大的虚数点\(\partial\)，其中 \[ a,b\in\Z_p \] 并且满足条件：\(p\) 是素数，\(\Delta_E=4a^3+27b^2\neq 0\pmod{p}\)。
密码学应用感兴趣的时定义中给出的基于素数域的曲线。如果在 \(\Z_p\) 上画出这个椭圆曲线，则得到的从远处看不像是一条曲线。
求解 \(E_p(a,b)\)
设 \(E_p(a,b)\) 表示椭圆曲线上的点集： \[ \{(x,y)|0\leq x\leq p,0\leq y\leq p, 且x,y均为整数 \} \] 求 \(E_p(a,b)\) 点集步骤：
- 对每一个 \(x(0\leq x<p,x\in\Z)\)，计算 \(x^3+ax+b\pmod{p}\)
- 决定以上求得的值在模 \(p\)
下是否有平方根，计算 \(y^2\pmod{p}\)
- 如果没有，则求曲线上没有与这一相对应的点
- 如果有，则求出两个平方根
以下是求解的 python 实现
1 | def get_points(p, a, b): |
椭圆曲线上的群操作
设点 \(P=(x_1,y_1)\) 和 \(Q=(x_2,y_2)\)，我们需要计算第三个点\(R\)的坐标，使得 \[ P+Q=R\\ (x_1,y_1)+(x_2,y_2)=(x_3,y_3) \] 在这里我们只关注素数域上的加法法则，得到以下表达式 \[ x_3=s^2-x_1-x_2\pmod{p}\\ y_3=s(x_1-x_3)-y_1\pmod{p} \] 其中 \[ s=\begin{cases} \displaystyle\frac{y_2-y_1}{x_2-x_1}\pmod{p};\ 当P\neq Q(相异点相加)\\ \displaystyle\frac{3x_1^2+a}{2y_1}\pmod{p};\ 当P=Q(相同点相加) \end{cases} \] 在相异点加法中，参数\(s\)指的是经过\(P\)和\(Q\)的直线的斜率；而在相同点加法中，参数\(s\)指的是经过点\(P\)的切线的斜率。
从几何角度上定义，即作过 \(P,Q\) 两点的直线，与椭圆曲线交于第三点 \(R\)，取 \(R\) 的与 \(x\) 轴对称的点（即将 \(R\) 的 Y 坐标乘以 -1），得到二点相加的结果 \(R'\) 点。
当 \(P=Q\) 时，需要采用极限的思想，此时应该是在椭圆曲线上过 \(P\) 点的切线与椭圆曲线的交点为二倍点。
定义点 \(O\) 为无穷远点，椭圆曲线上一点的运算满足以下规则（\(P,Q,R\in E\)）： \[ P+O=O+P=P\\ P+(-P)=O\\ (P+Q)+R=P+(Q+R)\\ P+Q+Q+P \] 同时定义倍乘为 \[ n P=\underbrace{P+P+P+\cdots+P}_{n \text { copies }} \]
而椭圆曲线的阶（order）定义为，找到一个最小的 \(s\) 满足 \(s=|k-j|\)，其中 \(kP=jP\)。
ECDLP 椭圆曲线离散对数问题
首先已知存在定理：
曲线上的点 \(\partial\) 一起构成了循环子群。在某些条件下，椭圆曲线上的所有点可以形成一个循环群。
在建立 \(DL\) 密码体制时，知道群的阶至关重要，我们可以根据 Hasse's 定理了解它的大概数量：
给定一个椭圆曲线\(Ep\)，曲线上点的个数表示为\(\#E\)，并且在以下范围内： \[ p+1-2\sqrt{p}\leq \#E\leq p+1+2\sqrt{p} \]
Hasse's 定理也称为Hasse's 边界，它说明了点的个数大概在素数 \(p\) 的范围内。这个结论具有非常大的实用性。例如，如果需要一个拥有 \(2^{160}\) 个元素的椭圆曲线，我们必须使用一个长度大约为 160 位的素数。
以下给出椭圆曲线离散对数问题（ECDLP）的定义：
给定一个椭圆曲线 \(E\)，考虑本原 \(P\) 和另一个元素 \(Q\)。则 \(DL\) 问题是找到整数\(k(1\leq k\leq \#E)\)，满足： \[ kP=Q \] 记为 \[ k=\log_P{(Q)} \]
其中，椭圆曲线加密的数学原理：
点\(P\)称为基点（base point）；\(k\)为私有密钥（private key）；\(Q\)为公开密钥（public key）
- 若给定\(k\)和\(P\)，根据加法法则，计算\(Q\)很容易。
- 但给定\(P\)和\(Q\)，求\(k\)非常困难 (实际应用 ECC 时，素数\(p\)会取得非常大，穷举出\(k\)将十分困难)
其中椭圆离散对数满足以下运算： \[ \log_P{(Q_1+Q_2)}=\log_P(Q_1)+\log_P(Q_2);Q_1,Q_2\in E \] 目前已知最快的解决椭圆离散对数问题的算法大约需要在 \(\sqrt{p}\) 步，所以当 \(p\) 足够大时，椭圆曲线加密具有安全性。
基于椭圆曲线的 Diffie-Hellman 密钥交换
首先我们必须统一域参数，即实现所需要的合适的椭圆曲线以及曲线上的一个本原元：
ECDH 域参数
- 选择一个素数\(p\)和椭圆曲线
\[ E:y^2\equiv x^3+ax+b\pmod{p} \]
- 选择一个本原元\(P=(x_p,y_p)\)
素数\(p\)、由系数\(a\)和\(b\)给出的曲线以及本原元\(P\)都是域参数。
请注意：实际上找到一个合适的椭圆曲线是一项比较困难的任务。
椭圆曲线 Diffie-Hellman 密钥交换 (ECDH)
对于 Alice：
选择 \(k_{prA}=a\in \{2,3,...,\#E-1\}\)
计算 \(k_{pubA}=aP=A=(x_A,y_A)\)
对于 Bob：
选择 \(k_{prB}=b\in \{2,3,...,\#E-1\}\)
计算 \(k_{pubB}=bP=B=(x_B,y_B)\)
交换 Alice 和 Bob 的密钥 \(A,B\)
对于 Alice 来说：
计算 \(aB=T_{AB}\)
对于 Bob 来说：
计算 \(bA=T_{AB}\)
故 Alice 和 Bob 之间的联合密钥：\(T_{AB}=(x_{AB}, y_{AB})\)
ElGamal 加密算法
密钥生成
选择一个素数 \(p\) 以及两个小于 \(p\) 的随机数 \(g\) 和 \(x\)，计算 \[ y=g^x\pmod{p} \] 以 \((y,g,p)\) 作为公开密钥 (public key)，\(x\) 作为私有密钥 (private key)
加密
明文消息为\(m\)，随机选取一个与\(p-1\)互素的整数\(k\)，计算 \[ c_1=g^k\pmod{p}\\ c_2=my^k\pmod{p} \] 密文为\(C=(c_1,c_2)\)
解密
\[ m=\frac{c_2}{c_1}\pmod{p} \]
因为 \[ \frac{c_2}{c_1}mod\ p=\frac{my^k}{g^{kx}}mod\ p=\frac{my^k}{y^k}mod\ p=m\pmod{p} \]
EC ElGamal
密钥生成
选一条素数域椭圆曲线，得 \(E_p(a,b)\)，将明文信息\(m\)嵌入到曲线上的点\(P_m\)，再对点\(P_m\)做加密变换。
取 \(E_p(a,b)\) 的一个生成元 \(G\)，\(E_p(a,b)\) 和 \(G\) 作为公开参数。用户 A 选则随机整数
\(n_A\) 作为密钥 (private key)，以 \(P_A=n_AG\) 作为公钥 (public key)
加密
用户B向用户A发送消息 \(P_m\)，选取一个随机正整数 \(k\)，产生以下点对作为密文： \[ C_m=\{kG,P_m+kP_A\} \]
解密
以密文对中的第二个点减去自己的密钥与第一个点的点乘，即 \[ P_m+kP_A-n_AkG=P_m+k(n_AG)-n_AkG=P_m \]
ECC&sagemath 实现
加密
1 | # 获取素数 p, a, b |
Output
1 | p = 128793297744506472538564656403224353239237790297856868063135293480657949718107 |
解密
1 | # 构造在素数p域上的椭圆曲线 |
Output
1 | m = (52087445795594278491856078932932443344636991761169005384048985847142638285440 : 15902591507684804608199095029425478914739638495574120728111164694188566421928 : 1) |
ECC&Python 实现
生成 ECC 密钥
1 | from Crypto.PublicKey import ECC |
查询公开椭圆曲线参数
1 | import fastecdsa.curve as curve |
椭圆曲线
坐标系转换
雅可比射影坐标将仿射坐标系（笛卡尔坐标系）进行一定转换，使得椭圆曲线上两点相加避免求逆运算，转换关系为：
仿射坐标转换为雅可比坐标 \[ (X,Y)\to (X,Y,1) \] 雅可比坐标转换为仿射坐标 \[ (X,Y,Z)\to (X/Z^2,Y/Z^3) \]
爱德华曲线
2007 年，Harold Edwards 在论文 A NORMAL FORM FOR ELLIPTIC CURVES 中提出椭圆曲线的新形式 \[ x^2+y^2=1+dx^2y^2 \] > 有时可能会简单另一种形式下的爱德华曲线 > \[ > x^2+y^2=c^2(1+dx^2y^2) > \] > 二者是等价的，对其进行仿射变换，令 > \[ > \begin{cases} > x'=\frac{x}{c}\\ > y'=\frac{y}{c}\\ > \end{cases} > \] > 那么得到 > \[ > \Big(\cfrac{x}{c}\Big)^2+\Big(\cfrac{y}{c}\Big)^2=1+dc^4\Big(\cfrac{x}{c}\Big)^2\Big(\cfrac{y}{c}\Big)^2 > \] > 即一个新方程 > \[ > x'^2+y'^2=1+Dc^4x'^2y'^2 > \]
与上文之前的椭圆曲线不同，爱德华曲线上的点相加公式为 \[ (x_1,y_1)+(x_2,y_2)=\left(\frac{x_1y_2+x_2y_1}{1+dx_1x_2y_1y_2},\frac{y_1y_2-x_1x_2}{1-dx_1x_2y_1y_2}\right) \] 倍乘公式为 \[ 2(x_1,y_1)=\left(\frac{2x_1y_1}{1+dx_1^2y_1^2},\frac{y_1^2-x_1^2}{1-dx_1^2y_1^2}\right) \]
点 \((x_1,y_1)\) 的逆是 \((-x_1,y_1)\)，零元为 \((0,1)\)。
其中，爱德华曲线可以被映射为蒙哥马利曲线 \[ \begin{cases} u&=\displaystyle\frac{1+y}{1-y}\\ v&=\displaystyle\frac{2(1+y)}{x(1-y)}=\frac{2u}{x}\\ A&=\displaystyle\frac{4}{1-d}-2\\ B&=\displaystyle\frac{1}{1-d} \end{cases} \] 那么得到方程 \[ Bv^2=u^3+Au^2+u \] ## 扭曲爱德华曲线
同 2007 年，Daniel J. Bernstein 和 Tanja Lange 在论文 Faster addition and doubling on elliptic curves 中对 Edwards form 进行了扩展 \[ ax^2+y^2=1+dx^2y^2 \] 也被称为扭曲爱德华曲线（Twisted Edwards curve）。 > 有时可能会简单另一种形式下的爱德华曲线 > \[ > ax^2+y^2=c^2(1+dx^2y^2) > \] > 二者是等价的，对其进行仿射变换，令 > \[ > \begin{cases} > x'=\frac{x}{c}\\ > y'=\frac{y}{c}\\ > \end{cases} > \] > 那么得到 > \[ > a\left(\frac{x}{c}\right)^2+\left(\frac{y}{c}\right)^2=1+dc^4\left(\frac{x}{c}\right)^2\left(\frac{y}{c}\right)^2 > \] > 即一个新方程 > \[ > ax'^2+y'^2=1+Dc^4x'^2y'^2 > \]
对于扭曲爱德华曲线而言，加法公式为 \[ (x_1,y_1)+(x_2,y_2)=\left(\frac{x_1y_2+x_2y_1}{1+dx_1x_2y_1y_2},\frac{y_1y_2-ax_1x_2}{1-dx_1x_2y_1y_2}\right) \] 倍乘公式为 \[ \begin{align} 2(x_1,y_1)&=\left(\frac{2x_1y_1}{1+dx_1^2y_1^2},\frac{y_1^2-ax_1^2}{1-dx_1^2y_1^2}\right)\\ &=\left(\frac{2x_1y_1}{ax_1^2+y_1^2},\frac{y_1^2-ax_1^2}{2-ax_1^2-y_1^2}\right) \end{align} \] 点 \((x_1,y_1)\) 的逆是 \((-x_1,y_1)\)，零元为 \((0,1)\)。
对于扭曲爱德华曲线也可以被映射为蒙哥马利曲线 \[ \begin{cases} u=\displaystyle\frac{1+y}{1-y}\\ v=\displaystyle\frac{1+y}{x(1-y)}=\frac{u}{x}\\ A=\displaystyle\frac{2(a+d)}{a-d}\\ B=\displaystyle\frac{4}{a-d} \end{cases} \]
那么得到方程 \[ Bv^2=u^3+Au^2+u \]
二元爱德华曲线
二元爱德华曲线（Binary Edwards Curves）的标准方程为 \[ d_1(x+y)+d_2(x^2+y^2)=(x+x^2)(y+y^2) \] 加法公式为 \[ \begin{cases} (x_1,y_1)+(x_2,y_2)=(x_3,y_3)\\ x_3=\displaystyle\frac{d_1(x_1+x_2)+d_2(x_1+y_1)(x_2+y_2)+(x_1+x_1^2)[x_2(y_1+y_2+1)+y_1y_2]}{d_1+(x_1+x_1^2)(x_2+y_2)}\\ y_3=\displaystyle\frac{d_1(y_1+y_2)+d_2(x_1+y_1)(x_2+y_2)+(y_1+y_1^2)[y_2(x_1+x_2+1)+x_1x_2]}{d_1+(y_1+y_1^2)(x_2+y_2)} \end{cases} \] 倍乘公式为 \[ \begin{cases} 2(x_1,y_1)=(x_2,y_2)\\ x_2=\displaystyle\frac{2d_1x_1+d_2(x_1+y_1)^2+(x_1+x_1^2)[x_1(2y_1+1)+y_1^2]}{d_1+(x_1+x_1^2)(x_1+y_1)}\\ y_2=\displaystyle\frac{2d_1y_1+d_2(x_1+y_1)^2+(y_1+y_1^2)[y_1(2x_1+1)+x_1^2]}{d_1+(y_1+y_1^2)(x_1+y_1)} \end{cases} \] 求逆为 \(-(x_1,y_1)=(y_1,x_1)\)。
对于二元爱德华曲线也可以被映射为Weierstrass 曲线 \[ \begin{cases} u=\displaystyle d_1(d_1^2+d_1+d_2)\frac{x+y}{xy+d_1(x+y)}\\ v=\displaystyle d_1(d_1^2+d_1+d_2)\left(\frac{x}{xy+d_1(x+y)}+d_1+1\right)\\ a=d_1^2+d_2\\ b=d_1^4(d_1^4+d_1^2+d_2^2) \end{cases} \]
那么得到方程 \[ v^2+uv=u^3+au^2+b \]
蒙哥马利曲线
蒙哥马利曲线（Montgomery curve）是另一种形式的椭圆曲线，方程如下 \[ By^2=x^3+Ax^2+x \] 其中，\(B(A^2-4)\neq 0\)。
其点加法为 \[ (x_1,y_1)+(x_2,y_2)=\left(\frac{B(x_2y_1-x_1y_2)^2}{x_1x_2(x_2-x_1)^2},\frac{B(y_2-y_1)^3}{(x_2-x_1)^3}\right) \] Curve25519是蒙哥马利曲线形式的一个实例， 声称是最快的Diffie-Hellman密钥交换函数，方程为 \[ y^2=x^3+486662x^2+x\pmod{p} \] 素数 \(p=2^{255}-19\)，这就是名字中 25519 的由来。
而对于蒙哥马利曲线，可以被映射为 Weierstrass 曲线 \[ \begin{cases} u=\displaystyle\frac{x}{B}+\frac{A}{3B}\\ v=\displaystyle\frac{y}{B}\\ a=\displaystyle\frac{3-A^2}{3B^2}\\ b=\displaystyle\frac{2A^3-9A}{27B^3} \end{cases} \] 那么得到方程 \[ v^2=u^3+au+b \]
哈夫曲线
Huff 曲线定义为 \[ ax(y^2-1)=by(x^2-1) \]
加法公式为 \[ (x_1,y_1)+(x_2,y_2)=\left(\frac{(x_1+x_2)(1+ay_1y_2)}{(1+bx_1x_2)(1-ay_1y_2)},\frac{(y_1+y_2)(1+bx_1x_2)}{(1-bx_1x_2)(1+ay_1y_2)}\right) \] 倍乘公式为 \[ 2(x_1,y_1)=\left(\frac{2x_1(1+ay_1^2)}{(1+bx_1^2)(1-ay_1^2)},\frac{2y_1(1+bx_1^2)}{(1-bx_1^2)(1+ay_1^2)}\right) \] 点 \((x_1,y_1)\) 的逆是其本身 \((x_1,y_1)\)。
对于哈夫曲线可以被映射为蒙哥马利曲线 \[ \begin{cases} u=\displaystyle\frac{bx-ay}{y-x}\\ v=\displaystyle\frac{b0a}{y-x}\\ A=a+b\\ B=ab \end{cases} \] 那么得到方程 \[ Bv^2=u^3+Au^2+u \]
四次曲线
\[ y^2=ax^4+bx^3+cx^2+dx+e \]
佩尔曲线
佩尔方程也满足 ECC 的要求，其方程为 \[ x^2-d^2y^2=c^2 \] 具体可参见佩尔方程。
椭圆曲线转换
可以发现，SageMath 的一般化椭圆方程是 Weierstrass 模型，即一般的椭圆方程模型 \[ y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 \] 而没有蒙哥马利曲线、爱德华曲线等曲线的构造函数。
这是因为无论哪种曲线最终都可以被表示为 Weierstrass 模型，不过需要做一定的转化。
椭圆曲线参数
1 | #NIST P-256（Secp256r1） |
双线性配对
初步
最简单易懂的双线性配对（Bilinear Pairing）的例子就是线性空间中两向量的内积，即 \[ \beta(\mathbf{v},\mathbf{w})=\mathbf{v}\cdot \mathbf{w}=v_1w_1+\cdots+v_nw_n \] 其中，\(\beta\) 表示一种双线性配对，又或者叫做双线性映射（Bilinear Map）。
对于两向量内积的双线性配对，不难发现其具有双线性性，即对任一元素的线性运算都会推广到双线性配对的结果中，即 \[ \beta(a_1\mathbf{v}_1+a_2\mathbf{v}_2,\mathbf{w})=a_1\beta(\mathbf{v}_1,\mathbf{w})+a_2\beta(\mathbf{v}_2,\mathbf{w})\\ \beta(\mathbf{v},b_1\mathbf{w}_1+b_2\mathbf{w}_2)=b_1\beta(\mathbf{v},\mathbf{w}_1)+b_2\beta(\mathbf{v},\mathbf{w}_2) \] 那么推广到更一般的情况（数学总是这样），双线性配对指的是两个不同群的元素映射到第三个群的元素的映射关系，写作数学符号是 \[ G_1\times G_2\Rightarrow G_3 \] 就类似于函数是描述一个群（集合）的元素映射到另一个群（集合）的元素的映射关系那样。
不过在密码学中，我们关注的是有意义的，双线性性良好的双线性配对。
Weil 配对
Weil 配对（Weil Pairing）是一个有良好性质的，对椭圆群元素起作用的双线性映射。
其定义为，对一个椭圆曲线中的两点 \(P,Q\)，其中椭圆曲线的阶为 \(m\)，那么其 Weil 配对表示为 \(e_m(P,Q)\)，并且满足 \[ \begin{align} e_m(P_1+P_2,Q)=e_m(P_1,Q)e_m(P_2,Q)\\ e_m(P,Q_1+Q_2)=e_m(P,Q_1)e_m(P,Q_2) \end{align} \] 而其中， \[ e_m(P,Q)=\frac{f_P(Q+S)}{f_P(S)}/\frac{f_Q(P-S)}{f_Q(-S)} \] \(S\) 是任意椭圆曲线中的元素且 \(S\notin\{O,P,-Q,P-Q\}\)，只做中间计算；\(f_P,f_Q\) 是任意有理函数。
\(e_m(P,Q)\) 的值与 \(f_P,f_Q,S\) 的选取无关。
可以证明的是，\(e_m(P,Q)^m=1\) 恒定，即 \(e_m(P,Q)\) 一定是 \(m\) 次单位根。
Tate 配对
Tate 配对的计算效率要比 Weil 配对效率高，定义为 \[ \tau(P,Q)=\frac{f_P(Q+S)}{f_P(S)} \] 与 Weil 配对的关系为 \[ e_l(P,Q)=\frac{\tau(P,Q)}{\tau(Q,P)} \] 计算量约为 Tate 配对的两倍。
基于 ID 的公钥密码系统
基于 ID 的公钥密码系统的目标很简单，就是希望每个用户可以通过自己的 ID 创建公私钥对，而不是从密码系统中获取一个公私钥对后与自己的 ID 强行绑定，这样避免了复杂的证书签名，同时也避免了存储负担。
从 ID 中直接生成公钥是方便的，任何人都可以直接推导出某个 ID 的公钥，方便消息的发送；但从 ID 中直接生成私钥是不安全的，任何人都可以直接推导出某个 ID 的私钥，窃取其消息。
所以为了安全性考虑，需要一个第三方，一般来说称其为 PKG（Private Key Generator），PKG 有一对主公私钥对（Master Key）。
其中公钥是公开的，任何人可以根据主公钥和 ID 计算出基于 ID 的公钥；私钥是保密的，任何人可以使用身份 ID 通过 PKG 生成与主私钥相关联的基于 ID 的私钥。
这样，一个基于 ID 的公钥密码系统就完成了，安全性主要在于对主私钥的保密性。
一个实际的解决方案是这样的，PKG 发布两个哈希函数 \(H_1,H_2\)，其中 \(H_1\) 负责将用户的 ID 转化为一个椭圆曲线 \(E(F_q)[l]\) 上的点，\(H_2\) 负责将有限域 \(F_q^*\) 的元素转化为一个长度为 \(B\) 的字节流，\(B\) 是明文 \(M\) 的字节流长度。
描述时是使用二进制位长度，但实现时更多的是用字节流长度。
概括的说，\(H_1\) 与公钥生成相关，\(H_2\) 与加密相关。
那么 PKG 拥有的公私钥对为 \[ P^{\text{PKG}}=sP\in E(F_q)[l] \] 主私钥是 \(s\)，主公钥是 \(P^{\text{PKG}}\)。
那么加密流程如下，首先获取用户的公钥 \[ P^{\text{User}}=H_1(\text{UserID})\in E(F_q)[l] \] 选择一个随机数 \(1<r<q\)，计算 \[ \begin{align} C_1&=rP\\ C_2&=M\oplus H_2(e_l(P^{\text{User}}, P^{\text{PKG}})^r) \end{align} \] 其中，\(\oplus\) 表示异或操作，这样一个密文是一对值 \(C=(C_1,C_2)\)。
解密时计算用户的私钥， \[
Q^{\text{User}}=sP^{\text{User}}\in E(F_q)[l]
\] 随后计算 \[
M=C_2\oplus H_2(e_l(Q^{\text{User}},C_1))
\] 
ECC 求解
普通明文映射
task.sage
1 | from Crypto.Util.number import getPrime |
output.txt
1 | p = 74997021559434065975272431626618720725838473091721936616560359000648651891507 |
exp.sage
1 | p = 74997021559434065975272431626618720725838473091721936616560359000648651891507 |
普通离散对数
以下使用 sagemath，数据量不能太大
1 | a = 1234577 |
Pohlig-Hellman 攻击
原理
我们知道求解离散对数问题已经有较为高效的方法（例如
Pohlig Hellman 算法），而 Pohlig 和 Hellman
提出我们还可以使椭圆离散对数问题的求解变得更加有效率。
他们提出，假设 \(n\) 为椭圆曲线的阶，而 \(n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}\)，其中 \(p_i,1\leq i\leq r\) 为质因数，那么我们可以把计算 \(l=\log_P{Q}\) 转化为计算每一个 \(l_i=l\bmod{p_i^{e_i}}\)，得到一个同余方程组 \[ \begin{array}{rlr} l & \equiv l_{1} & \left(\bmod p_{1}^{e_{1}}\right) \\ l & \equiv l_{2} & \left(\bmod p_{2}^{e_{2}}\right) \\ & \ \vdots & \\ l & \equiv l_{r} & \left(\bmod p_{r}^{e_{r}}\right) \end{array} \] 使用中国剩余定理，我们就可解 \(l=\log_P{Q}\)。
现在的问题转化为求解 \(l_i=l\bmod{p_i^{e_i}}\)。
我们首先设 \(l_i\) 为一个 \(p_i\) 多项式（下面为方便表达，将 \(l_i,p_i,e_i\) 的下标忽略）： \[ l=z_{0}+z_{1} p+z_{2} p^{2}+\cdots+z_{e-1} p^{e-1} \] 其中 \(z_i\in [0,p-1]\)。
计算 \(P_0=(n/p)P\)，\(Q_0=(n/p)Q\)，有 \[ Q_0=\frac{n}{p}Q=l(\frac{n}{p}P)=lP_0=z_0P_0 \] 因此 \(z_0=\log_{P_0}{Q_0}\)。
同理我们计算 \(Q_1=(n/p^2)(Q-z_0P)\)，有 \[ Q_1=\frac{n}{p^2}(Q-z_0P)=\frac{n}{p^2}(l-z_0)P=(z_0+z_1p-z_0)\frac{n}{p^2}P=z_1P_0 \] 故 \(z_1=\log_{P_0}{Q_1}\)。
以此类推，我们可以得 \(z_t=\log_{P_0}{Q_t}\)，其中 \[
Q_t=\frac{n}{p^{t+1}}\left(Q-z_{0} P-z_{1} p P-z_{2} p^{2}
P-\cdots-z_{t-1} p^{t-1} P\right)
\] 除分散为子域计算，Sagemath 的 discrete_log
中已将以上叙述的 Pohlig Hellman 算法（对 \(p^k\) 阶的离散对数求解）内置。
代码
1 | p = 1256438680873352167711863680253958927079458741172412327087203 |
Smart 攻击
特征
椭圆曲线的阶和素数 \(p\)
恰好相等（E.order() == p）
p进数有理数域
例如 \(Q_p(p, 2)\) 表示以素数 \(p\) 为底，精度为 \(2\)（即小数点后保留两位）的 p-adic 有理数域。
在这个表示中，\(p\) 是指定的素数，而精度为 2 表示在小数点后保留两位数字。这意味着在 \(Q_p(p, 2)\) 中的数字可以用 \(p\) 的幂次表示，并且小数部分最多有两位数字。
对于一个椭圆上的点，我们可以用亨塞尔引理将该点提升到 \(Q_p(p,2)\) 上，例如椭圆曲线 \[ E:Y^2=X^3+39X^2+X+41\pmod{43} \] 该椭圆曲线上的一点 \(P=(0,16)\) 可提升为 \[ P=(0,16+20.43+O(43^2)) \]
p进数椭圆对数映射
对如上点不能简单进行对数映射，对其乘以 \(p\) 后能保证扩域上的所有点都满足 \(p\) 进数椭圆对数映射，即 \[ \overline{P}=p\cdot P=(38.43^{-2}+O(43^{-1})，41.43^{-3}+O(43^{-2})) \] 对一个可以进行映射的点可以将其映射到 \(Q_p\) 上的一个数，计算为 \[ \phi_p((x,y))\equiv -\frac{x}{y}\pmod{p^2} \] 例如 \(\overline{P}\) 可以映射为 \[ \phi_p(pP)=19.43+O(43^2) \]
原理
对于原本椭圆曲线的对数关系，有 \[ Q=k\cdot P \] 此时我们需要求解 \(k\)，即椭圆曲线上的点的离散对数问题。
此时我们对其进行提升，将域提升到 \(Q_p(p,2)\) 上，有 \[ Q-k\cdot P=R\in E_1(Q_p) \] 乘以 \(p\) 以便进行映射，必然得到 \[ p\cdot Q-k\cdot (p\cdot P)=p\cdot R\in E_2(Q_p) \] 进行映射即 \[ \phi_p(p\cdot Q)-k\phi_p(p\cdot P)=\phi_p(p\cdot R)\equiv 0\pmod{p^2} \] 那么可以很快计算得到 \[ k=\frac{\phi_p(p\cdot Q)}{\phi_p(p\cdot P)} \]
代码
1 | p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b |
MOV 算法
参考论文《Reducing elliptic curve logarithms to logarithms in a finite field》
简单来说就是使用双线性配对，使得原 ECDLP 问题变为了 DLP 问题，最重要的意义在于实质证明了 ECDLP 问题与 DLP 问题是等价的。
虽然在计算上 DLP 问题的求解要比 ECDLP 问题的求解稍微快一些，少了许多不必要的消耗。
一个简单的示例如下，但实际上由于问题等价，故实际不会使用该算法进行攻击。
1 | # Curve parameters |
已知点反推系数
一般曲线
已知两点 \(C_1(x_1,y_1),C_2(x_2,y_2)\)，那么有 \[ \begin{align} y_1^2&=x_1^3+ax_1+b\pmod{p}\\ y_2^2&=x_2^3+ax_2+b\pmod{p} \end{align} \] 两边相减可得 \[ y_1^2-y_2^2=(x_1^3-x_2^3)+a(x_1-x_2)\pmod{p} \] 即 \[ a=\frac{(y_1^2-y_2^2)-(x_1^3-x_2^3)}{x_1-x_2}\pmod{p} \] 简写成 \[ a=A_{1,2}=\frac{(y_1^2-y_2^2)-(x_1^3-x_2^3)}{x_1-x_2}\pmod{p} \] 那么 \[ b=y_1^2-x_1^3-ax_1 \] 已知三点 \(C_1(x_1,y_1),C_2(x_2,y_2),C_3(x_3,y_3)\)，可得 \[ \begin{align} a&=A_{1,2}\pmod{p}\\ a&=A_{1,3}\pmod{p} \end{align} \] 两式相减可得 \[ A_{1,2}-A_{1,3}=0\pmod{p} \] 即 \(p\) 的公倍数。
爱德华曲线
已知两点 \(C_1(x_1,y_1),C_2(x_2,y_2)\)，那么有 \[ \begin{align} x_1^2+y_1^2=c^2(1+dx_1^2y_1^2)\pmod{p}\\ x_2^2+y_2^2=c^2(1+dx_2^2y_2^2)\pmod{p} \end{align} \] 两式相减可得 \[ (x_1^2-x_2^2)+(y_1^2-y_2^2)-c^2d(x_1^2y_1^2-x_2^2y_2^2)=0\pmod{p} \] 即 \[ c^2d=\frac{(x_1^2-x_2^2)+(y_1^2-y_2^2)}{x_1^2y_1^2-x_2^2y_2^2}\pmod{p} \] 简写成 \[ c^2d=E_{1,2}=\frac{(x_1^2-x_2^2)+(y_1^2-y_2^2)}{x_1^2y_1^2-x_2^2y_2^2}\pmod{p} \] 原公式变形为 \[ \begin{align} c^2&=x_1^2+y_1^2-c^2dx_1^2y_1^2\pmod{p}\\ &=x_1^2+y_1^2-E_{1,2}x_1^2y_1^2\pmod{p} \end{align} \] 可求出 \(c,d\)。
已知三点 \(C_1(x_1,y_1),C_2(x_2,y_2),C_3(x_3,y_3)\)，可得 \[ \begin{align} c^2d&=E_{1,2}\pmod{p}\\ c^2d&=E_{1,3}\pmod{p} \end{align} \] 两式相减可得 \[ E_{1,2}-E_{1,3}=0\pmod{p} \] 即 \(p\) 的公倍数。
1 | def E(a: tuple[int, int], b: tuple[int, int]): |
查看 ECC 的 pem 密钥文件信息
使用 openssl
1 | #查看ECC私钥信息 |