椭圆曲线加密体制的构建与应用

摘 要:采用Java提供的大数操作,对素数域上椭圆曲线进行深入分析,以国际上相关的研究和算法实现工作为基础,采用数学建模和面向对象的思想,根据椭圆曲线密码体制,实现素数域椭圆曲线加密系统,给出详细的设计,并分析了其中的关键算法。针对Java在网络上的广泛应用,将其应用于网络验证,保护网络应用系统的安全。关键词:椭圆曲线; 密码体制; 倍点; 数字签名; 面向对象

中图分类号:TN919-34; TP3097文献标识码:A

文章编号:1004-373X(2010)17-0117-04

Research and Application of Elliptic Curve Cryptosystem

LI Ming-xin, ZENG Xiao-ping, KANG Feng

(Department of Computer Engineering, Chengdu Aeronautic Vocational and Technical College, Chengdu 610021, China)

Abstract: The elliptic curve over prime finite field is analyzed deeply by using big integer provided by Java. Using mathematics modeling and object oriented method, according to EC public key encrypt theme, the elliptic curve encrypt system over prime finite field is achieved based on international relevant research and algorithms. Some important algorithms and detailed design of the system is proposed. In view of the wide application of Java in network, this cryptosystem is applied to network authentication for protecting the security of the system information.Keywords: elliptic curve; cryptosystem; point multiplying; digital signature; object-oriented

0 引 言

椭圆曲线密码系统是由Neal Koblitz和Victor Miller在1985年分别独立提出的,椭圆曲线密码系统在同等的安全级别下密钥最短,特别适用于计算能力较弱,存储空间较小,带宽较小的环境。同时,椭圆曲线资源丰富,同一个有限域上存在着大量不同的椭圆曲线,这为安全性增加了额外的保证,也为软、硬件实现带来方便。由于受美国安全出口限制,与Java开发包中椭圆曲线相关的API中提供的密钥长度达不到保障数据的安全,Java语言具有很好的跨平台性,所以本系统采用Java开发,并将其应用到网络传输中。

1 椭圆曲线及相关定义

定义1 韦尔斯特拉斯(Weierstrass)方程:

y2+axy+by=x3+cx2+dx+e(1)

所确定光滑平面曲线称为椭圆曲线,Ъ俏E,其中a,b,c,d,e∈Fp;Fp为有限域。满足式(1) 的(x,y) 称为Fp域上的点。此外,椭圆曲线还定义一个特殊的无穷点O。

设p是一个大于3的奇素数,参数a,b满足4a3┆+27b2┆≠0(mod p),那么有限素数域Fp上的椭圆曲线可以定义为:

E: y2x3+ax+b(mod p)(2)

素数域上Fp的椭圆曲线参数是一个六元组,它们是T={p,a,b,G,n,h},其中p,a,b用来确定一条椭圆曲线;G=(xG,yG)为椭圆曲线的基点;素数n为G的阶,n即为#E(Ep),Э梢岳用Hasse[1]定理来计算椭圆曲线的阶:

p+1-2p≤#E(Fp)≤p+1+2p(3)

h是n关于#E(Ep)的协因子,即h=#E(Ep)/n。素数域Fp的椭圆曲线参数准确指定了椭圆曲线及其基点,这对于基于EC公钥加密体制是必须的。

定义2 对满足式(2)的椭圆曲线,无穷远点为O,任取EC两点P(x1,y1),Q(x2,y2),P+Q=R(x3,y3)是PQ连线交于EC的第三点相对于x轴的对称点,且满足以下性质:

(1) O+P=P+O=P;

(2) P+Q=Q+P;

(3) P+Q+R=O;

(4) λ为PQ连线的斜率,若P和Q为椭圆曲线E上同一点时,取E上经过P点切线的斜率:

x3=λ2┆-x1-x2(mod p)

y3=λ(x1-x3)-y1(mod p)

当P=Q时:

λ=3x21+a2y1(mod p)

当P≠Q时:

λ=y2-y1x2-x1(mod p)

2 椭圆曲线加密体制实现

椭圆曲线加密体制是基于椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP),即:Ъ偕杌于E(Fp)上椭圆曲线E上有两点G和Q,其中G为基点,Q=kG,则由G和Q要计算出k是一个数学难题。Ц据对椭圆曲线的数学建模,对椭圆曲线加密体制进行抽象,并按照面向对象的程序设计方法,先给出椭圆曲线相关变量的定义,然后给出关键算法的实现。本系统大致分为以下4个主要类。

(1) class EllipticCurve:基于有限素域的椭圆曲线类。

(2) class ECPoint:基于有限素域的椭圆曲线点类。

(3) class ECKey:椭圆曲线密钥对类。

(4) class ECCryptoSystem:椭圆曲线加密体制类。

其中,EllipticCurve提供参数并构造椭圆曲线操作;ECPoint类提供椭圆曲线上的点运算;ECKey提供生成密钥对;ECCryptoSystem类抽象ElGamal加密体制,提供加密解密功能。接下来将会详细介绍各个类的定义和关键算法的实现。

2.1 椭圆曲线域参数

利用上面介绍的椭圆曲线域参数,用Elliptic Curve类抽象椭圆曲线,其中BigInteger为Java语言所提供的实现大数运算类。下面是椭圆曲线的抽象定义,接下来介绍椭圆曲线域参数生成算法。

class EllipticCurve

{

private BigInteger a,b,p;

private BigInteger n;//椭圆曲线的阶

private ECPoint G;//椭圆曲线的基点

private BigInteger h;//协因子

…

EllipticCurve(){}//构造EC参数

…

}

素数域Fp上椭圆曲线参数的产生,算法如下:

算法1[1]:输入:椭圆曲线参数所要求大概的安全级别t必须是一个整数。

t∈{56,64,80,96,112,128,192,256}

输出:素数域Fp上椭圆曲线参数T=(p,a,b,G,n,h),算法大概需要2t次操作。

操作:素数域Fp上椭圆曲线参数产生如下步骤:

(1) 选择一个素数p,t≠256,满足log2p

=2t,并且t=256,满足log2p=521来决定有限域Fp。

(2) 在素数域Fp上选择a,b,并且满足方程(2)。椭圆曲线E(Fp)基点G=(xG,yG),阶n,余因子h=#E(Fp)/n,д庑┎问必须满足下列限制条件:

4a3┆+27b2┆≠0(mod p)

#E(Fp)≠p

PB┆≠1(mod n)(1≤B

h≤4

(3) 输出椭圆曲线域参数六元组T=(p,a,b,G,n,h)

2.2 素数域椭圆曲线的点运算

椭圆曲线加密系统要实现的本质是椭圆曲线上的点构成的Abel群上的点乘运算,而Abel群是一个加法群,根据加法群的运算特点,椭圆曲线上的点乘运算又需要转化成椭圆曲线上的点加运算来实现,当两个加数相同的时候,点加运算又变成了倍点运算,所以椭圆曲线上的点乘运算需要转化成椭圆曲线上的点加和倍点运算实现。使用ECCPoint类,抽象椭圆曲线上的点,并实现倍点运算规则,下面是椭圆曲线点的抽象类,定义如下:

class ECCPoint

{

private EllipticCurve e;

private BigInteger x,y;

private boolean iszero;//判断是否为0点

…

public ECPoint multiply(BigInteger k){}

//椭圆曲线倍点运算

…

}

在椭圆曲线加密系统中最重要和耗费时间的操作是倍点。倍点的定义如下:

Q=kP=∑ki=1P(4)

式中:P代表椭圆曲线上的点;k为随机的整数。下面给出Double-and-add算法,为二进制法。

算法2:Double-and-add算法如下[2]:

(1) k=∑m-1i=1b┆i2i┆,b┆i∈(0,1)

(2) P:=P(x1,x2)

(3) Q:=P

(4) for i from m-1 down to 0 do

Q=Q+Q

if bi=1, then Q=Q+P

(5) return Q

对于常规的算法,需要k次点加法,在Double-and-add算法中,平均只需3/2[log2 n]次运算,最多需要2[log2 n]次运算[3]。

2.3 椭圆曲线密钥对

给定椭圆曲线的域参数T=(p,a,b,G,n,h),可以产生椭圆曲线密钥对(d,Q),其中d为一个整数,为秘钥;d∈[1,n-1];公钥Q=(xQ,yQ),并且Q=dG。

下面的类用来抽象椭圆曲线的密钥对:

class ECCKey

{

protected boolean secret;

protected BigInteger d;

protected ECCPoint G,Q;

protected EllipticCurve e;

…

public ECCKey(EllipticCurve e){};//产生密钥

public Key getPublicKey() {}//产生公钥

…

}

算法3:椭圆曲线的密钥对产生如下:

输入:正确的椭圆曲线域参数T=(p,a,b,G,n,h)。

输出:一条和T相关的椭圆曲线密钥对(d,Q)。

操作:椭圆曲线的密钥对产生如下:

(1) 在区间[1,n-1]随机地选择一个整数d;

(2) 计算Q=dG;

(3) 输出(d,Q);

有了密钥对,接下来就可以介绍基于ElGamal椭圆曲线公钥加密体制。

2.4 椭圆曲线密码体制

在本系统中,使用椭圆曲线ElGamal加密体制(ECES),用ECCryptoSystem抽象,在这个类中,提供加密解密函数,接下来将会描述加密解密过程,类的定义如下:

class ECCryptoSystem

{

MessageDigest hash;

private EllipticCurve e;

…

/*解密函数*

byte[] decrypt(byte[] input, int num,ECKey key){}

/*解密函数*/

byte[]encrypt(byte[] input,int num,ECKey key){}

/*签名函数*/

byte[] sign(byte[] input,int num,ECKey key){}

/*验证函数*/

bool verify(byte[] message,int num,ECKey key){}

…

}

椭圆曲线加密解密的过程描述如下: 假想Alice想使用ElGamal椭圆曲线加密体制,其中椭圆曲线E(Fp)给定,他将执行下面的步骤:

(1) 选择一个随机整数d,并且满足2≤d≤(#E-1);

(2) 计算Q=dG=(xQ,yQ);

(3) 公开(G,Q,p,#E)为公钥,d为密匙,由算法3生成。

接下来,假设Bob想要发送一条消息(x1,x2)给Alice,他将执行下面的步骤:

(1) 选择一个随机数k,满足2≤k≤(#E-1);

(2) 执行下面的计算:

R=kG;

(c1,c2)=kQ;

(y1,y2)=(c2x1,c2x2)(mod p)

(3) 发送(R,y1,y2)给Alice,接收到密文,Alice按照下面的步骤恢复密文(x1,x2):

(c1,c2)=dR;

(x1,x2)=(c-11y1,c-12y2)(mod p)

2.5 椭圆曲线数字签名

假设Bob发送的信息为m,由上面生成的密钥对为(d,Q),签名的过程如下:

(1) 计算信息m的消息摘要e=SHA1(m);

(2) 选择一个随机数k,1≤k≤n-1;

(3) 计算kG=(x,y);

(4) 计算r=x mod n

(5) s=k-1(e+dr)mod n

则签名的信息为(r,s);发送签名消息(r,s)给Alice,Alice按照下面的步骤验证:

(1) 计算c=s-1mod n;

(2) 计算u1=ec mod n;u2=rc mod n;

(3) 计算X=u1G+u2Q=(x,y);

(4) 计算v=x mod n,如果v=r,签名有效,否则无效。

3 应 用

利用椭圆曲线的数学构建和面向对象程序设计思想,实现了素数域上的椭圆曲线密码体制。本系统基于Java语言实现,由于Java在网络中的广泛应用,而网络中的用户名密码消息一般是明文传送的,所以很容易被截获下来,造成重要资料的损失。本试验根据前面介绍的算法,采用160 b长度的椭圆曲线参数,客户端传输加密数据,数据在非安全信道上传输,然后服务器端解密。可以安全地传输数据,但是这种方式也有其自身的缺点,不能解决中间人攻击。所以本应用是采用基于椭圆曲线的签名机制来避免中间人攻击的问题,图1是基于椭圆曲线签名验证的流程图。

客户端将用户名密码的Hash值传递给服务端,由于Hash值是不可逆的,这样能避免中间人攻击。由于数据库中存放是用户名和密码的Hash值,也可以避免由于服务器的数据泄露带来的危害。采用基于签名验证的方式,采用签名验证的方式登陆性能和安全更好。

图1 基于ECDSA登陆的流程图

根据RSA实验室破解不同加密算法所耗的时间来看,采用160 b椭圆曲线加密的安全性和1 024 b的RSA加密安全性相当,需要花费600个月的时间[4],因此,在160 b的情况下,其安全性系数适合在网络中应用。

4 结 语

ECC算法的数学背景比较深奥,本文在椭圆曲线

的数学建模和面向对象的程序实现上还有待加强。借

助Java提供的大数操作,实现了椭圆曲线加密系统,能够直接应用于网络上数据加密传输和签名验证,本系统功能比较简单,执行效率性有待提高,下一步的主要工作是实现并完善本系统,进一步完善椭圆曲线的数学模型和改进执行效率,规范系统调用接口,供其他程序调用。

参考文献

[1]US EPA. SEC1: SECG released standards[S/OL]. [2000-02-10]. .

[2]MOON Sangook. Elliptic curve scalar point multiplication using radix-4 booth′s algorithm[J]. Computer and Information,2005,1(1):1-8.

[3]侯整风,李岚.椭圆曲线密码系统(ECC)整体算法设计及优化研究[J].电子学报,2004,32(11):1904-1906.

[4]QIU Qi-zhi, XIONG Qian-xing. Research on elliptic curve cryptography[J/OL]. [2004-05-26]. /.

[5]IEEE Computer Society. IEEE standard specifications for public-key cryptography[J/OL]. [2004-10-11]. /.

[6]IEEE Computer Society. IEEE standard specifications for public-keycryptography-amendment 1: additional techniques[J/OL]. [2004-11-10]. Http:///.

[7]ECKEL Bruce.Java编程思想[M].陈昊鹏,译.北京:机械工业出版社,2002.

[8]DOUGLAS Stinson R.密码学原理与实践[M].冯登国,译.北京:电子工业出版社,2003.

[9]Tom St Denis.程序员密码学[M].沈斌,译.北京:机械工业出版社,2007.

[10]KNUTH Donald E. The art of computer programming[M]. 3rd ed. [S.l.]: Addison Wesley, 1997.