在整数域中，离散对数（Discrete logarithm）是一种基于同余运算和原根的一种对数运算，具有运算速度高，安全性强，简洁高效等特点，目前已经在公钥加密体系中广为应用。本文在前文（“离散对数密码学原理”）的基础上，进一步阐述基于离散对数的椭圆曲线加密方法。

一、预备知识

G是有限乘法群，阶为n，并且
$gin G$

g∈G，于是满足
$g^t=1$

gt=1的最小正整数t称为g的阶。t一直存在且为n的分解因子。
$lang grang={g^i:0leq ileq t-1}$

⟨g⟩=gi:0≤i≤t−1构成一个g的指数集合，该集合构成一个群，满足类似于群G的操作。这个群也称为由g生成的G的循环子群。如果G是加法写的，类似的断言也成立。在这个例子中，
$gin G$

g∈G的阶是n的最小正分解因子t，满足
$tg=0$

tg=0，且
$lang grang={g^i:0leq ileq t-1}$

⟨g⟩=gi:0≤i≤t−1。
$tg$

tg表示增加t份g拷贝的元素。如果G有一个阶为n的元素g，那么G称为循环群，g称为G的生成因子。

二、广义离散对数问题

假设
$(G,centerdot)$

(G,⋅)是一个由g生成的阶为n的乘法循环群，我们可以在
$G$

G中描述类似上文的离散对数系统。例如，公共域参数为g和n，私钥为整数
$x（xin [1,n-1]）$

x（x∈[1,n−1]），且公钥为
$y=g^t$

y=gt。在群G中，离散对数问题就描述为给定
$(g,n,y)$

(g,n,y)求
$x$

x的问题。
任意2个具有相同阶数的循环群是基本相同的，也就是说，他们具有相同的结构，即便群元素可能书写不同，但具有相同的结构。群元素的不同表示方法可以引起算法实现上时间效率的变化。

三、椭圆曲线群

假如
$p$

p是质数，
$F_p$

Fp​表示模为
$p$

p的整数域，其上的椭圆曲线E可以定义为如下公式：

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

y2=x3+ax+b
其中，
$a,bin F_p$

a,b∈Fp​满足
$4a^2+27b^3neq0(mod p)$

4a2+27b3​=0(modp)。表示曲线上的点。在曲线上的无穷点用
$infin$

∞表示，将椭圆曲线E的所有点用来表示，举一个栗子，如果E是数据域上的椭圆曲线，满足公式：。

于是，E上的点包括：

现在， 任2个椭圆曲线上的点
$(x_1,y_1)$

(x1​,y1​)和
$(x_2,y_2)$

(x2​,y2​)的和称为点加，点加产生椭圆曲线上的第3个点。加法规则仅仅要求在
$F_p$

Fp​上执行一系列关于
$(x_1,y_1,x_2,y_2)$

(x1​,y1​,x2​,y2​)的算数运算（加，减，乘，反转）。依赖加法规则，点集
$E(F_p)$

E(Fp​)形成一个（加法）阿贝尔群，以
$infin$

∞为单位元（幺元）。椭圆曲线的循环子群可以用于执行离散对数系统。
接下来，通过描述一个与离散对数加密相似的椭圆曲线方法，进一步说明椭圆曲线加密算法背后的主要思想。

四、椭圆曲线密钥生成

设
$E$

E为有限域
$E(F_p)$

E(Fp​)上的椭圆曲线，
$P$

P为数据域上的点，假设
$P$

P具有质数阶n。于是由P生成的的循环子群
$E(F_p)$

E(Fp​)表示为：

质数p，椭圆曲线E的等式，点P和它的阶n构成了公共参数域。私钥是一个从数据域
$[1,n-1]$

[1,n−1]中随机选取的整数d，相应的公钥为
$Q=dP$

Q=dP。

给定公共参数域和
$Q$

Q，确定整数d的问题称为椭圆曲线离散对数问题。

椭圆曲线密钥对生成算法

五、椭圆曲线加密方案

正如在前文（“离散对数密码学原理”）提到了基本ElGamal加密算法一样，我们将展现基于椭圆曲线的加密和解密程序。明文m首先表示为点M，然后通过加上
$kQ$

kQ实现加密，其中k是随机选择的整数，Q是对应接收者的公钥。接下来，发送者传送点
$C_1=kP$

C1​=kP和
$C_2=M+kQ$

C2​=M+kQ给接收者，最后，接收者使用私钥d计算：

之后执行
$M=C_2-kQ$

M=C2​−kQ恢复明文m。窃密者想恢复M需要计算kQ。给定公共参数Q，计算kQ和
$C_1=kP$

C1​=kP是椭圆曲线问题（类似Diffie-Hellman问题）。

基本椭圆曲线加密算法

基本椭圆曲线解密算法

六、总结

离散对数的椭圆曲线加密方法的本质是建立出一套基于椭圆曲线的公共参数域，在实施椭圆曲线系统前，需要做出几个关于有限域和密码学协议的选择：
1、有限域能否满足域元素和执行域运算的算法。
2、椭圆曲线能否满足椭圆去点点集和执行椭圆曲线运算的算法。
3、协议和算法能否满足协议运算。
此外， 运算的安全性和效率也是设计离散对数椭圆曲线方案的考虑因素。

[1]: Darrel Hankerson (Author), Alfred J. Menezes (Author), Scott Vanstone (Author)，Guide to Elliptic Curve Cryptography，book，Springer Professional Computing，2003。