椭圆曲线密码体制

由于硬件提升和因子分解算法的发展不断威胁着RSA，最年来RSA密钥位数在不断增加
而另一种公钥加密技术——椭圆曲线加密法ECC可以使用短得多的密钥获得与RSA相同的安全性

椭圆曲线基础

椭圆曲线并不是椭圆，该名称只是因为其方程与计算椭圆周长的方程相似
密码学中我们只考虑椭圆曲线的简化形式

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

除了方程所定义的点外，椭圆曲线还包含一个无穷远点（或称零点）$O$，他们共同组成点集$E(a,b)$

若上述方程中的系数$a,b$满足

$4a^3+27b^2\neq 0$

则可基于$E(a,b)$定义一个加群
从几何角度定义椭圆曲线上的加法规则为：若椭圆曲线上三点在一条直线上，则它们的和为$O$

根据该加法定义，$E(a,b)$满足如下条件

加法定义：设$P,Q$为曲线上两个不同点，他们的连线与椭圆曲线交于另一点$R$，则$P+Q=-R$
可以证明$R$存在且唯一，除非连线在$P$（或$Q$）点与椭圆曲线相切，此时令$R=P$（或$R=Q$）
此外若$P=Q$，则画出该点切线找到另一交点$R$，则$P+P=-R$
单位元：$O$是$E(a,b)$的单位元。对于椭圆曲线上任一点$P$，有$P+O=P$
负元：若点$P=(x,y)$，则$P$的负元为$-P=(x,-y)$，有$P+(-P)=O$
负元的定义可解释为用一条与$x$轴垂直的线连接$P$与$-P$，在无穷远点与椭圆曲线相交

容易看出$E(a,b)$是Abel群

elliptic_curve

我们还可以给出实数域上椭圆曲线加法的代数描述

若$P=(x_P,y_P),Q=(x_Q,y_Q)$为不同点且不互为逆元，则$R=(x_R,y_R)=P+Q$满足

$\begin{cases} x_R=\Delta^2-x_P-x_Q\\ y_R=-y_R+\Delta(x_P-x_R) \end{cases}$

其中$\Delta=\frac{y_Q-y_P}{x_Q-x_P}$为$P,Q$连线的斜率

若$P=Q$且$y_P\neq0$，则有

$\begin{cases} x_R=(\frac{3x_P^2+a}{2y_P})^2-2x_P\\ y_R=-(\frac{3x_P^2+a}{2y_P})(x_P-x_R)-y_P \end{cases}$

在密码学的近世代数基础中提到密码学主要关注$GF(p)$和$GF(2^n)$两个有限域，ECC也是如此

定义在GF(p)上的椭圆曲线称为素曲线，其中的系数和变量均取自$Z_p$，运算为模$p$运算，其方程为

$y^2 \mod p=(x^3+ax+b)\mod p$

可以证明当满足如下条件时$E_p(a,b)$为有限Abel群

$(4a^3+27b^2)\mod p \neq 0$

有限域上的椭圆曲线算术没有显而易见的几何解释，我们试着从代数角度解释

对于任意点$P,Q\in E_p(a,b)$

$P+O=P$
若$P=(x,y)$，则$P$的负元为$-P=(x,-y)$，但是要注意负数取膜
例如$E_{23}(1,1)$上的点$P=(13,7)$，其逆元为$-P=(13, (-7)\mod 23)=(13, 16)$
若$P=(x_P,y_P),Q=(x_Q,y_Q)$且$P,Q$不互为逆元，设$R=(x_R,y_R)=P+Q$，则有
$\begin{cases} x_R=(\lambda^2-x_P-x_Q) \mod p\\ y_R=(\lambda(x_P-x_R)-y_P) \mod p \end{cases}$
其中
$\lambda= \begin{cases} \frac{y_Q-y_P}{x_Q-x_P}\mod p && 若p\neq Q\\ \frac{3x_P^2+a}{2y_P}\mod p && 若p=Q \end{cases}$
计算$\lambda$的除法定义在$Z_p$上，即需要计算乘法逆元
$E_p(a,b)$上的乘法定义为重复相加，例如$4P=P+P+P+P$

定义在$GF(2^n)$上的椭圆曲线称为二元曲线，其中的系数和变量均取自$GF(2^n)$，运算为$GF(2^n)$上的运算

$GF(2^n)$适用于椭圆密码曲线的三次方程与$GF(p)$上的略有不同，如下所示

$y^2+xy=x^3+ax^2+b$

可以证明，只要$b\neq 0$，即可在$E_{2^m}(a,b)$上定义一个有限Abel群

对于任意点$P,Q\in E_{2^,}(a,b)$

$P+O=P$
若$P=(x,y)$，则$P$的负元为$-P=(x,x+y)$
若$P=(x_P,y_P),Q=(x_Q,y_Q)$为不同点且不互为逆元，设$R=(x_R,y_R)=P+Q$，则
$\begin{cases} x_R=\lambda^2+\lambda+x_P+x_Q+a\\ y_R=\lambda(x_P+x_R)+x_R+y_P \end{cases}$
其中
$\lambda=\frac{y_Q+y_P}{x_Q+x_P}$
若$P=(x,y)$，设$R=(x_R,y_R)=P+P$，则
$\begin{cases} x_R=\lambda^2+\lambda+a\\ y_R=x_P^2+(\lambda+1)x_R \end{cases}$
其中
$\lambda=x_P+\frac{y_P}{x_P}$

椭圆曲线密码体制的建立是基于椭圆曲线上的计算离散对数的困难性，这个问题称为椭圆曲线对数问题

考虑$Q=kP$，其中$Q,P\in E_p(a,b)$且$k<p$
给定$k,p$，计算$Q$比较容易，而给定$Q,P$，计算$k$则比较困难

在密钥长度相当时，ECC与RSA所需的计算量也差不多，但与具有同等安全性的RSA相比，ECC的密钥短得多。SP 800-57 建议至少到2030年，可接受的密钥长度对于RSA为3072~14360位，对ECC则为256~512位

以$GF(p)$上的ECC为例，首先选定大素数$p$和系数$a,b$确定$E_p(a,b)$

在$E_p(a,b)$中挑选基点$G$满足$G$的阶很大，其中$G$的阶$n$定义为使得$nG=O$的最小正整数

假设A希望和B交换密钥
A选择一个整数$n_A<n$作为私钥，然后产生公钥$P_A=n_A\times G$，同理B产生私钥$n_B$和公钥$P_B$
之后A、B分别计算$K=n_A\times P_B$和$K=n_B\times P_A$，至此A、B完成了密钥K的共享

椭圆曲线实现的加密/解密方法有很多种，这里总结一个最简单的方法

与上面ECC的DH密钥交换同理，确定$p,a,b,G$几个参数，A、B分别产生自己的公钥、私钥

假设A要给B发送消息
A首先将明文消息$m$编码为形如$(x,y)$的点$Pm$
然后A选择一个随机正整数$k$，计算密文$C_m={kG,P_m+kP_B}={c{m1}, c{m2}}$
B要解密只需计算$P_m=c{m2}-nBc{m1}$

上述方法中，攻击者若要从密文恢复出明文，需要从$G$和$kG$求出$k$，但这被认为是很困难的