一、简介

椭圆曲线密码（ECC）是基于椭圆曲线数学理论构建的非对称加密技术，其安全性依赖于椭圆曲线离散对数问题（ECDLP）的数学困难性。

$$ECC基于有限域上的椭圆曲线方程定义代数结构，通过点加法运算形成有限Abel群。$$

$$目前椭圆曲线主要采用的有限域有以素数为模的整数域 GF(p)和特征为2的伽罗华域 GF(2^m)$$

二、数学基础

离散对数

$$对整数b、指数p及其原根a，若可找到唯一指数使得b \equiv a^i \pmod p，其中i \in [0,p-1]，则称i为b的以a为基数的离散对数$$

阿贝尔群

一个集合G配备一个二元运算（通常称为加法或乘法）满足以下四条公理：

封闭性：$$\forall a,b \in G,a \cdot b\in G(或a+b \in G)$$
结合律：$$\forall a,b,c \in G,(a \cdot b)\cdot c=a \cdot (b \cdot c) $$
单位元：$$\exists e \in G,使得\forall a \in G,e \cdot a=a\cdot e=a$$
逆元：$$\forall a \in G,\exists b \in G使得a \cdot b=b\cdot a=e$$

交换律：$$\forall a,b \in G,a \cdot b=b \cdot a $$
唯一性：$$单位元和每个元素的逆元都是唯一的$$
子群：$$阿贝尔群的子群都是正规子群（所有子群在交换群中都是正规的）$$

椭圆曲线

$$椭圆曲线的定义式：y^2+axy+by=x^3+cx^2+dx+e$$

标准方程：$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$$

常用方程（短Weierstrass形式）

$$y^2=x^3+ax+b,\Delta =-16(4a^3 +27b^2)$$

$$\Delta \neq 0来保证曲线是非奇异的，即光滑没有尖点的$$

广义Weierstrass判断椭圆曲线是否为奇异的：解奇点方程组

在分析奇异椭圆曲线时，通过奇点的重数来判断是尖点还是结点

令$$F(x,y)=y^2+a_1xy+a_3y-x^3-a_2x^2-a_4x-a_6$$

$$偏导：F_x=a_1x-3x^2-2a_2x-a_4 \qquad F_y=2y-a_1x+a_3$$

若没有解说明曲线非奇异
若有唯一解（重根）说明曲线为尖点
若有两个不同解，曲线为结点

非椭圆曲线：

结点/自交点曲线

尖点曲线

椭圆曲线上的阿z贝尔群

$$R(x,y)的负元是(x,-y \mod p)=(x,p-y),有P+(-P)=O$$

几何加法：

任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），作直线交于椭圆曲线的另一点R’，过R’做y轴的平行线交于R，定义P+Q=R。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律

普通三点相加：P+Q+R=0
过一点的切线：P+P+Q=0
过两点的直线平行于y轴：P+Q+0=0
切线平行于y轴：P+P+0=0

代数加法：

$两非零非对称点P(x_1,y_1)Q(x_2,y_2),若P+Q=R$

$$则R(x_3,y_3)有： x_3=k^2-x_1-x_2,y_3=k(x_1-x_3)-y_1=k(x_2-x_3)-y_2$$

若P和Q不同：$k=\frac {y_1-y_2}{x_1-x_2)}$

若P和Q相同：$k=\frac {3x_1^2+a}{2y_1}$

数乘：

$$Q=nP=P+P+…+P=\sum _{i=0}^{n-1} (b_i \cdot 2^i)P,b_i={0,1},b_i 为n的各比特位值$$

离散对数：

Q=nP，已知Q，P，求n

三、有限域椭圆曲线

$椭圆曲线Ep(a,b),p为质数，x,y \in [0,p-1]:y^2=x^3+ax+b \pmod p,满足：a,b 小于p，且4a^3+27b^2 \neq 0 \pmod p $

曲线的阶：

椭圆曲线上所有有理数点（包括无穷远点O）的个数，通常用#$ E(\mathbb{F}_q)$ 表示。

椭圆线群的阶决定了群的规模，是安全性参数的基础。
阶的大小直接影响了离散对数问题的难度
根据Hasse定理，椭圆曲线的阶满足：

$q+1-2\sqrt {q} \leq $ #$ E(\mathbb {F}_q) \leq q+1+2\sqrt q$

点的阶：

$椭圆曲线上一点P，若\exists n 使得nP=O,则称n位P的阶$

$若不存在这样的n，则称P为无限阶点。（有限域上所有的点都是有限阶的）$

$由拉格朗日定理，对任意有限群G，其子群H的阶必整除群G的阶，即点的阶n必整除椭圆曲线的阶N=$#$E(\mathbb {F}_q)$

四、奇异曲线

尖点曲线（同构加法群）

$$y^2=x^3$$

$该曲线在原点处有奇异点，记非原点的P(a^2,a^3),Q(b^2,b^ 3),P+Q=R$

$则k=\frac{a^3-b^3}{a^2-b^2}=\frac{a^2+ab+b^2}{a+b},x_R=k^2-x_P-x_Q=(\frac{ab}{a+b})^2,y_R=(\frac{ab}{a+b})^3$

$注意到\frac{1}{a}+\frac{1}{b}=\frac{a+b}{ab}，即\frac{x_P}{y_P}+\frac{x_Q}{y_Q}=\frac{x_R}{y_R}$

$考虑构造映射f(x,y)\rightarrow\frac{x}{y}，那么可以将原曲线上的加法运算同构到整数上的加法运算：$

$$f(P+Q)=f(P)+f(Q)$$

$$f(mP)=mf(P)$$

结点曲线（同构乘法群）

$$y^2=x^3+x^2$$

$考虑代换：令u=\frac{y}{x}，则u^2=x+1，x=u^2-1，y=u(u^2-1)，即：$

$$\begin {cases} x=t^2-1 \ y=t(t^2-1) \end {cases}$$

$不妨记P(a^2-1,a(a^2-1)),Q(b^2-1,b(b^2-1))，P+Q=R$

$$k=\frac{a(a^2-1)-b(b^2-1)}{a^2-b^2}=\frac{a^2+ab+b^2-1}{a+b}$$

联立方程：

$$ \begin {cases} y=k(x-x_1)+y_1 \ y^2=x^3+x^2 \end {cases}$$

(很难) 不难发现：$$\frac{y_P-x_P}{y_P+x_P} \cdot \frac{y_Q-x_Q}{y_Q+x_Q}=\frac{y_R-x_R}{y_R+x_R}$$

考虑构造映射：

$$f(x,y) \rightarrow \frac{y-x}{y+x}$$

那么可以将原曲线上的加法运算同构到整数上的乘法运算：

$$f(P+Q)=f(P) \cdot f(Q)$$

$$f(mP)=f(P)^m$$

一般的

对于广义Weierstrass方程：

$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$$

$奇点(x_0,y_0)满足$

$$\begin {cases} F(x_0,y_0)=0\ F_x(x_0,y_0)=0\ F_y(x_0,y_0)=0 \end {cases}$$

$只需令X=x-x_0,Y=y-y_0，即可将奇点平移到原点$

五、通信算法

密钥生成：

$选择一条椭圆曲线E_p(a,b)，并取椭圆曲线上的一点作为基点G$
$设G的阶为n，再选择一个正整数n_a作为密钥，计算P_a=n_a$
$公开E_p(a,b),p,G.公钥为P_a,私钥为n_a$

加密：

$选定一条椭圆曲线E_p(a,b)，并选择一点作为基点$
$选择一个私钥k(k < n),生成公钥K=kG$
$将带传输的明文编码到E_p(a,b)上一点M，并随机生成一个整数r(r<n)$
$计算C_1=M+rK，C_2=r$

解密：

$$M=C_1-rK=C_1-kC_2$$

六、代码实现

生成ECC密钥：

from Crypto.PublicKey import ECC
#生成ECC密钥
key=ECC.generate(curve='NIST P-256')
#输出密钥（私钥k，基点G）
print(key)
#公钥（x，y G的坐标）
print(key.public_key())
#椭圆曲线
print(key.curve)
#私钥l
print(key.d)
#输出pem文件
print(key.export_key(format='PEM'))
key=ECC.import_key(f.read())

常见参数：

#常见参数
#NIST P-256（Secp256r1）
#p = 2^224(2^32 − 1) + 2^192 + 2^96 − 1
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

#Secp256k1（比特币使用）
#p = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1 = 2^256 – 2^32 – 977 
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
a = 0
b = 7

#NIST P-384
#p = 2^384 – 2^128 – 2^96 + 2^32 – 1
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575

#NIST P-521
p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
a = -3
b = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984

sage常用函数：

E = EllipticCurve(GF(p),[a,b]) :定义曲线
E.random_point():在椭圆曲线E上随机取一点
E.set_order():设置椭圆曲线的阶
E.point((x,y)):创建一个椭圆曲线上的点对象，该点对象的坐标为(x,y)
discrete_log(K,G,operation='+'):求解，自动选取BSGS算法或Pohlig-Hellman算法
E.order()：计算椭圆曲线的阶。
discrete_log_rhp(K,G,operation='+'):用Pollard rho算法求解私钥
discrete_log_lambda(K,G,bound,operation='+'):用Pollard Lambda算法求解私钥，能够确定所求值在某一小范围时效率较高