“椭圆曲线密码学”的意思、由来-中文百科全书

数学理论

ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

椭圆曲线密码学的许多形式有稍微的不同，所有的都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上，对应有限域上椭圆曲线的群。

对椭圆曲线来说最流行的有限域是以素数为模的整数域(参见模运算)<math>GF(p)</math>，或是特征为2的伽罗华域GF(2m)。後者在专门的硬件实现上计算更为有效，而前者通常在通用处理器上更为有效。专利的问题也是相关的。一些其他素数的伽罗华域的大小和能力也已经提出了，但被密码专家认为有一点问题。

给定一条椭圆曲线E以及一个域<math>GF(q)</math>，我们考虑具有<math>(x, y)</math>形式有理数点<math>E(q)</math>的阿贝尔群，其中x和y都在<math>GF(q)</math>中并且定义在这条曲线上的群运算"+"在文章椭圆曲线中描述。我们然後定义第二个运算"*" | Z×<math>E(q)->E(q)</math>：如果P是<math>E(q)</math>上的某个点，那么我们定义<math>2*P=P+P, 3*P=2*P+P=P+P+P</math>等等。注意给定整数 j和k，<math>j*(k*P)=(j*k)*P=k*(j*P)</math>。椭圆曲线离散对数问题(ECDLP)就是给定点P和Q，确定整数k使<math>k*P=Q</math>。

一般认为在一个有限域乘法群上的离散对数问题(DLP)和椭圆曲线上的离散对数问题(ECDLP)并不等价；ECDLP比DLP要困难的多。

在密码的使用上，曲线<math>E(q)</math>和其中一个特定的基点G一起被选择和公布。一个私钥k被作为随机整数来选择；值<math>P=k*G</math>被作为公钥来公布(注意假设的ECDLP困难性意味着k很难从P中确定)。如果Alice和Bob有私钥kA和kB，公钥是PA和PB，那么Alice能计算kA*PB=(kA*kB)*G；Bob能计算同样的值kB*PA=(kB*kA)*G。

这允许一个“秘密”值的建立，这样Alice和Bob能很容易地计算出，但任何的第三方却很难得到。另外，Bob在处理期间不会获得任何关于kA的新知识，因此Alice的私钥仍然是私有的。

基于这个秘密值，用来对Alice和Bob之间的报文进行加密的实际方法是适应以前的，最初是在其他组中描述使用的离散对数密码系统。这些系统包括：

Diffie-Hellman — ECDH

MQV — ECMQV

ElGamal discrete log cryptosystem — ECElGamal

DSA — ECDSA

对于ECC系统来说，完成运行系统所必须的群操作比同样大小的因数分解系统或模整数离散对数系统要慢。不过，ECC系统的拥护者相信ECDLP问题比DLP或因数分解问题要难的多，并且因此使用ECC能用小的多的密钥长度来提供同等的安全，在这方面来说它确实比例如RSA之类的更快。到目前为止已经公布的结果趋于支持这个结论，不过一些专家表示怀疑。

ECC被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。

国家标准与技术局和ANSI X9已经设定了最小密钥长度的要求，RSA和DSA是1024位，ECC是160位，相应的对称分组密码的密钥长度是80位。NIST已经公布了一列推荐的椭圆曲线用来保护5个不同的对称密钥大小(80, 112, 128, 192, 256)。一般而言，二进制域上的ECC需要的非对称密钥的大小是相应的对称密钥大小的两倍。

Certicom是ECC的主要商业支持者，拥有超过130项专利，并且已经以2千5百万美元的交易获得了国家安全机构(NSA)的技术许可。他们也已经发起了许多对ECC算法的挑战。已经被解决的最复杂的是109位的密钥，是在2003年初由一个研究团队破解的。破解密钥的这个团队使用了基于生日攻击的大块并行攻击，用超过10,000台奔腾级的PC机连续运行了540天以上。对于ECC推荐的最小密钥长度163位来说，当前估计需要的计算资源是109位问题的108倍。

在2005年2月16日，NSA宣布决定采用椭圆曲线密码的战略作为美国政府标准的一部分，用来保护敏感但不保密的信息。NSA推荐了一组被称为Suit B的算法，包括用来密钥交换的Menezes-Qu-Vanstone椭圆曲线和Diffie-Hellman椭圆曲线，用来数字签名的椭圆曲线数字签名算法。这一组中也包括AES和SHA。

一些具体的内容

有关的基本概念

(1) 无穷远元素（无穷远点，无穷远直线）

平面上任意两相异直线的位置关系有相交和平行两种。引入无穷远点，是两种不同关系统一。

AB⊥L1， L2∥L1，直线AP由AB起绕A点依逆时针方向转动，P为AP与L1的交点。

Q=∠BAP→p /2 AP → L2

可设想L1上有一点P∞，它为L2和L1的交点，称之为无穷远点。

直线L1上的无穷远点只能有一个。

（因为过A点只能有一条平行于L1的直线L2，而两直线的交点只能有一个。）

结论：

1*. 平面上一组相互平行的直线，有公共的无穷远点。

（为与无穷远点相区别，把原来平面上的点叫做平常点）

2*.平面上任何相交的两直线L1,L2有不同的无穷远点。

原因：若否，则L1和L2有公共的无穷远点P∞，则过两相异点A和P ∞有相异两直线，与公理相矛盾。

3*. 全体无穷远点构成一条无穷远直线。

注：欧式平面添加上无穷远点和无穷远直线，自然构成射影平面。

(2) 齐次坐标

解析几何中引入坐标系，用代数的方法研究欧氏空

间。这样的坐标法也可推广至摄影平面上，建立平面摄影

坐标系。

牋 L1,L2

L1: a1x+b1y+c1=0

L2: a2x+b2y+c2=0

其中a1,b1不同时为0；a2,b2也不同时为0。

设

D= a1 b1 Dx= b1 c1 Dy= c1 a1

a2 b2 b2 c2 c2 a2

若D≠0，则两直线L1,L2相交于一平常点P(x,y)，其坐标为x=Dx/D，y=Dy/D.

这组解可表为：x/Dx=y/Dy=1/D

(约定：分母Dx，Dy有为0时，对应的分子也要为0）

上述表示可抽象为（Dx，Dy，D).

若 D=0，则L1∥L2，此时L1和L2交于一个无穷远点P∞。

这个点P∞可用过原点O且平行于L2的一条直线L来指出他

的方向，而这条直线L的方程就是：a2x+b2y=0.

为把平常点和无穷远点的坐标统一起来，把点的坐标用

（X，Y，Z)表示，X，Y，Z不能同时为0，且对平常点

（x，y)来说，有Z≠0，x=X/Z，y=Y/Z，于是有：

i.e.

X / Dx = Y / Dy = Z / D，

有更好的坐标抽象，X,Y,Z),这样对于无穷远点则有Z=0，

也成立。

注：

a).若实数p≠0，则(pX,pY,pZ)与（X,Y,Z)表示同一个点。实质上用（X:Y:Z)表示。3个分量中，只有两个是独立的，</pre>

<pre>具有这种特征的坐标就叫齐次坐标。

b).设有欧氏直线L，它在平面直角坐标系Oxy上的方程为：

ax+by+c=0

则L上任一平常点(x,y)的齐次坐标为(X,Y,Z)，Z≠0，代入得：

aX+bY+cZ=0

给L添加的无穷远点的坐标(X,Y,Z)应满足aX+bY=0，Z=0;平面上无穷远直线方程自然为：Z=0 !!

(3)任意域上的椭圆曲线

K为域，K上的摄影平面P2(K)是一些等价类的集合{(X:Y:Z)}。考虑下面的Weierstrass方程(次数为3的齐次方程)：

Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3

(其中系数ai∈K，或ai∈K为K的代数闭域）

Weierstrass方程被称为光滑的或非奇异的是指对所有适合

以下方程的射影点P=(X:Y:Z) ∈ P2(K)来说，

F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0

在P点的三个偏导数之中至少有一个不为

0若否称这个方程为奇异的。

椭圆曲线E的定义：

椭圆曲线E是一个光滑的Weierstrass方程在P2(K)中的

全部解集合。

Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3

注：

a) 在椭圆曲线E上恰有一个点，称之为无穷远点。即(0:1:0)用θ表示。

b) 可用非齐次坐标的形式来表示椭圆曲线的Weierstrass方程:

设 x=X/Z，y=Y/Z，于是原方程转化为：

y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)

此时，椭圆曲线E就是方程（1)在射影平面P2(K)上的全部平常点解，外加一个无穷远点θ组成的集合。

c) 若a1,a2,a2,a4,a6∈K，此时椭圆曲线E被称为定义在K上，用E/K表示。如果E能被限定在K上，那么E的K--</pre>

<pre>有理点集合表示为E(K)，它为E中的全体有理坐标点的集合外加无穷远点θ.

(4)实域R上的椭圆曲线

设K=R，此时的椭圆曲线可表为平面上的通常曲线上

的点，外加无穷远点θ。

实域R上椭圆曲线的点的加法运算法则：

设L ∈ P2(R)为一条直线。因为E的方程是三次的，所以L可与E在P2(R)恰有三个交点，记为P,Q,R

（注意：如果L与E相切，那么P,Q,R可以不是相异的）。按下述方式定义E上运算⊙：

设P,Q ∈ E，L为联接P,Q的直线（若P=Q，则L取过P点的切线）；设R为L与E的另一个交点；

再取连接R与无穷远点的直线L′。则L′与E的另一个交点定义为P ⊙Q。

上页的实际图像为椭圆曲线y2=x3 - x的一般化。来自对具体曲线的抽象。对运算更具体一些：

设 P=(x1,y1)，Q=(x2,y2)，P⊙Q=(x3,y3),

由P Q的定义，设y=αx+β为通过P,Q两点直线L的方程，可算出：

α=( y2-y1 )/(x2-x1), β=y1-αx1

易见，直线L上的一个点（x, αx+β)是在椭圆曲线E上，

当且仅当(αx+β)2= x3 - x 。

P⊙Q=(x1,y1) (x2,y2)=(x3,y3) =(x3,-(αx3+β))

其中，x3= α2-x1-x2=((y2-y1) / (x2-x1) )2-x1-x2；

y3=-y1+((y2-y1)/(x2-x1))(x1-x3)

当P=Q时： P⊙Q=（x3，y3）算得：

x3=((3x12-1)/2y1)2-2x1; y3= -y1+((3x12-1)/2y1)(x1-x3)

注：

a) 如果直线L与E相交与三点P,Q,R(不一定相异），那么 (P⊙Q)R=θ(从图中可见）。

b) 任给P∈E, P⊙θ =P (此时设Q= θ ，易见L=L′)

c) 任给P,Q∈E有： P⊙Q =Q⊙P

d) 设P∈E，那么可以找到 - P∈E使P -P= θ

e) 任给P,Q,R∈E，有(P⊙Q)⊙R= P⊙(Q⊙R)

综上所述，知E对运算形成一个Abel群。

f) 上述规则可开拓到任意域上，特别是有限域上。假定

椭圆曲线是定义在有限域Fq上（q=pm)，那么

E(Fq)={(x,y)∈Fq×Fq | y2+a1xy+a3y=x3+a2x2+a4x+a6} ∪{θ}

它对? 斝纬梢桓鋈海?狝bel群。

有限域上椭圆曲线的运算

令Fq表示q个元素的有限域，用E(Fq)表示定义在Fq上

的一个椭圆曲线E。

定理1.(Hass定理) E(Fq)的点数用#E(Fq)表示，则

| #E(Fq)-q-1|≤2q1/2

(1) Fp（素域，p为素数）上椭圆曲线

牋 p>3 a,b Fp 4a3+27b2 0 a b

义的Fp上的一个椭圆曲线方程为：

y2=x3+ax+b (2)

它的所有解(x,y)，(x Fp，y Fp)，连同一个称为撑耷钤?

点敚?俏?龋┑脑?刈槌傻募?霞俏狤(Fp)，由Hass定理

知：p+1-2p1/2≤#E(Fp) ≤ p+1+2p1/2

集合E(Fp)对应下面的加法规则，且对加法形成

一个Abel群：

(i) θ⊙ θ=θ （单位元素）

(ii) (x,y)⊙ θ=(x,y), 任给(x,y) ∈E(Fp)

(iii) (x,y)⊙ (x,-y)=θ，任给(x,y) ∈E(Fp),即点(x,y)的逆元

为(x,-y).

(iv) 令(x1,y1),(x2,y2)为E(Fp)中非互逆元，则

(x1,y1)⊙ (x2,y2)=(x3,y3),其中

x3=α2-2x1，y3= α(x1-x3)-y1

且α=(y2-y1)/(x2-x1) （3）

(v)（倍点运算规则）

设(x1,y1) ∈E(Fp),y1≠0，则2(x1,y1)=(x3,y3)，其中

x3= α2-2x1, y3=α(x1-x3)-y1

这里α=(3x12+a)/(2y1) (4)

注：若#E(Fp)=p+1，曲线E(Fp)称为超奇异的，否则称为

非超奇异的。

例子：F23上的一个椭圆曲线

令y2=x3+x+1是F23上的一个方程(a=b=1)，则该椭圆曲

线方程在F23上的解为(y2=x3+x+1的点)：

(0,1)，(0,22)，(1,7)，(1,16)，(3,10)，(3,13)，(4,0)，(5,4)，(5,19)，(6,4)，</pre>

<pre>(13,16)，(17,3)，(17,20)，(18,3)，(18,20)，(19,5)，(19,18)；θ。

群E(F23)有28个点（包括无穷远点θ ）。

2) F2m上的椭圆曲线

F2m上由参数a,b∈F2m，b≠0定义的一个非超奇异椭

圆曲线E(F2m)是方程

y2+xy=x3+ax2+b (5)

的解集合(x,y)，其中x,y∈F2m，连同θ 。

E(F2m)的加法规则如下：

(i) θ +θ= θ

(ii) 任给(x,y) ∈E(F2m)，则(x,y)⊙ θ=(x,y)

(iii) 任给(x,y) ∈E(F2m)，则(x,y)+(x,x+y)= θ，

即点(x,y)的逆为(x,x+y).

(iv) 两个相异且不互逆的点的加法规则：

令(x1,y1),(x2,y2) ∈E(F2m)且有x1≠x2则

(x1,y1) (x2,y2)=(x3,y3)，其中

x3=α2+α+x1+x2+a；

y3=α(x1+x3)+x3+y1.

其中 α= (y2+y1)/(x2+x1)

(v) 倍点规则

令(x1,y1) ∈E(F2m)，其中x1≠0。则

2(x1,y1)=(x3,y3)，其中

x3= α 2+ α +a, y3=x12+(α +1)x3, 这里α =(x1+y1/x1)

易见，群E(F2m)为Abel群。

例：F24上的一个椭圆曲线

f(x)=x4+x+1为F2上的一个不可约多项式，易见

F24=F2[x] / (f(x)) = {(k0,k1,k2,k3) | (k0,k1,k2,k3)=k0+k1α+k2α2+k3α3， </pre>

<pre>α为f(x)的零点，ki∈F2}

假定F24上的非超奇异椭圆曲线有下述方程定义：

y2+xy=x3+α4x2+1，注意f(α)=0。

方程应表为：

(1000)y2 + (1000)xy = (1000)x3 + (1100)x2 +(1000)

椭圆曲线密码体制

1985年，N. Koblitz和V. Miller分别独立提出了椭圆曲线密码体制(ECC)，</pre>

<pre>其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。

（1）知E(Fq)对点的?斣怂阈纬梢桓鯝bel群

设p∈E(Fq)，若p的周期很大，即使

p⊙p⊙ …… ⊙p= θ (共有 t个p相加）

成立的最小正整数 t，希望 t 很大。

(t = p的周期，表示为∏(p)=t)。

并且对Q∈E(Fq)，定有某个正整数m使

Q=m·p=p⊙ …… ⊙p (共有t个p相加)

定义

m=㏒pQ (m为以p为底Q的对数）。

椭圆曲线上的点形成的群E(Fq)，相关它的离散对数

问题是难处理的。

建立椭圆曲线密码体制

选取基域Fq，Fq的椭圆曲线具体给定为确定的形式。

在E(Fq)中选一个周期很大的点，如选了一个点P=(xp,yp)，

它的周期为一个大的素数n，记∏ (P)=n(素数)。

注意：在这个密码体制中，具体的曲线及点P和它的n都

是公开信息。密码体制的形式采用EIGamal体制，是完全

类比过来。

a)密钥的生成

Bob(使用者）执行了下列计算：

i) 在区间[1,n-1]中随机选取一个整数d。

ii) 计算点Q:=dP (d个P相）

iii) Bob公开自己的公开密钥-- (E(Fq),p,n,Q)

iv) Bob的私钥为整数d！

Alice要发送消息m给Bob，Alice执行：

i) 查找Bob的公钥(E(Fq),p,n,Q),

ii) 将m表示成一个域元素m∈Fq,

iii) 在区间[1，n-1]内选取一个随机数k,

iv) 依据Bob的公钥计算点 (x1,y1):=kP(k个P相）

v) 计算点(x2,y2):=kQ,如果x2=0,则回到第iii)步

ⅵ) 计算C:=m·x2

ⅶ) 传送加密数据(x1,y1,C)给Bob

b) Bob的解密过程

Bob收到Alice的密文(x1,y1,C)后，执行

i) 使用私钥d，计算点(x2，y2):=d(x1,y1)，再计算Fq中x2-1=

通过计算m:=C·x2-1，恢复出明文数据