椭圆曲线公钥在网络安全密码体系中的应用

高建明

摘 要： 移动设备和无线设备的大量使用需要一种新的公钥密码方案，来适应这些设备在计算能力和带宽方面的限制，同时要满足安全性级别的要求。椭圆曲线密码体制作为一种新兴的加密及身份认证技术，以其自身的多项特点，已从学术理论研究阶段逐步走向实际应用阶段，成为目前最有前途的一种公钥密码体系，极有可能成为现存公钥密码体系RSA的替代者。椭圆曲线密码算法具有高安全性、低消耗、运算速度快的特点，具有良好的应用前景。文章对椭圆曲线方程、算法的原理、加密算法、安全性进行了分析，实现了椭圆曲线公钥在网络Diffie-Hellman密钥交换中的应用。

关键词： 椭圆曲线； 密码学； 编码； 密钥； 安全性

中图分类号：TP311 文献标志码：A 文章编号：1006-8228（2013）08-25-03

0 引言

目前，大多数使用公钥密码学进行加密和数字签名的产品和标准都使用RSA算法。为了保证RSA在使用中的安全性，最近这些年来密钥设置的位数一直在增加，这对使用RSA的应用是一个很重的负担，近年来，出现了一种具有较强竞争力的椭圆曲线密码学（ECC），它对RSA提出了挑战[1]。ECC突出的优点是可以使用比RSA短得多的密钥，但却能得到相同的安全性，因此在应用上可以大大减少运行负荷。

1 椭圆曲线方程概述

1.1 椭圆曲线方程

一般地说，椭圆曲线是由方程y2+dxy+ey=x3+ax2+bx+c定义的曲线，其中定义a，b，c，d，e为系数，从数学上讲，椭圆曲线的形状并非椭圆，之所以被称为椭圆曲线，是因为该方程右边的多项式x3+ax2+bx+c与椭圆曲线的积分有关。

现分析以下椭圆曲线类方程：

令K（b，c）为式⑴的椭圆曲线上所有（x，y）的不同点组成的集合。

这类椭圆曲线的特征是曲线上的点具有加法性质，一般可用于构造交换群，交换群（M，+）满足以下5个性质的代数结构，其中M为集合，集合上元素的加法运算用符号“+”表示。

⑴ 对任意x，y∈M，x+y∈M，则满足集合上的封闭性。

⑵ 对任意x，y，z∈M，x+（y+z）=（x+y）+z），则满足集合上的结合性。

⑶ 单位元：存在0∈M，使得对任意x∈M，则x+0=0+x=0。

⑷ 逆元素：对任x∈M，显然存在元素x'∈M使x+x'=x'+x。将x'记为-x，并将x+（-y）记为x-y。

⑸ 对任意x，y∈M，x+y=y+x，则满足集合上交换性。

在交换群中单位元称为零元。现令X，Y为椭圆曲线上的任意一点，则有以下两种情形：

⑴ 当X≠Y时，可令L为连接这两个点的直线。若L不垂直，则可以推出L一定与曲线上第三点相交，并且惟一。

⑵ 当X=Y时，可令L为曲线在点X的切线。若L不垂直，则L一定与曲线上的另一个点相交，且惟一。

在上面两种情形中，如果当L为垂直线时，则L和曲线不相交。引进一个虚拟点P，假设它在无穷远处与L线相交。虚拟点P设定为单位元的角色，称为零点，定义K'（b，c）=K（b，c）∪{0}[2]。对集合K'（b，c）上的点可以定义一个加法运算“+”如下：

⑴ 对任意的K'（b，c），令X+0=X。

⑵ 对任意的X，Y∈K（b，c），如果X≠Y，若它们的X坐标相同，则根据椭圆曲线的性质，则X和Y与X轴互为映像，即X=（x，y），Y=（x，-y）。令X+Y=0，因此，-X=（x，y）。

⑶ 对任意X，Y∈K（b，c），如果X坐标不相同，定义L为经过这两个点的直线，若L不是曲线的切线，则L必定与K（b，c）上的惟一的第三点Z相交，设X+Y=-Z，则X+Y是Z在X轴上的映像。如果L为点X上的切线，可令X+Y=-X。如果L为在点Y上的切线，则可令X+Y=-Y。

⑷ 对任意X∈K（b，c），令Lx为曲线在点X上的切线，令Y为LX与曲线相交的另一点，令X+X=-Y。

可以证明（K'（b，c），+）是一个交换群。为便于将传送的明文编码，通常只考虑K（b，c）上的格点（x，y），通常也称为整数点，即X、Y都是整数。

1.2 离散椭圆曲线

2 椭圆曲线的编码定义

用椭圆曲线将明文进行加密首先需要将明文M编码，使它成为椭圆曲线上的一个整数点，从这个点上可惟一推算出明文M[5]。但到目前为止仍不知道这种编码能否被多项式时间算法所产生。不过，这种编码可以用概率算法产生，且速度较快，尽管概率算法不一定能保证总能生成一个编码，但可以证明这种情况发生的几率是很小的[6]。

假设N是比P小的多的正整数。先令x=N，然后检查N3+bN+c是否等于模P下的整数平方[7]。如果不是，在N的末尾加入和修改一些数字而得到一个新的整数N'，并且检查N3+BN+C是否为模P下的整数平方，下面是一个概率编码的算法。

令￠>0为一个非常小的数，使得（N+1）￡

因为对于每个J，x3+bx+c不是整数平方的概率约为1/2。因此，可以知道算法失败的概率为ε，给定Pm=（x，y），容易看出N=[x/￡]，并称Y为椭圆曲线编码参数。

如令p=179，b=3，c=34，￡=15，则（4b3+27c2）mod p=174≠0。

从（M+1）￡<176得1≤M≤12，令M=10，则x=N￡+j=150+j=150+j，0≤N≤15，当j=0时，得x=150，且（x3+bx+c）mod p=（1503+3.150+34）mod179=81=92。

所以y=9，即P10=（150，9）是N=10在集合K'179（3，34）上的编码（这里设￡=15），因为[150/15]=10，所以从点（150，9）可推算出N=10[9]。

3 椭圆曲线加密算法的应用

3.1 椭圆曲线加密算法

通常将椭圆曲线加密和解密算法分别简称为ECC加密和ECC解密。

令K为任意大于1的整数。对任意X∈K'（b，c），令kX=X+（k-1）X，椭圆曲线对数问题指的就是从给定k×X和X∈K'（b，c）求K的值，通常认为椭圆曲线对数问题没有快速算法，这个问题就是研究椭圆曲线公钥体系的基础。

与Diffie-Hellman密钥交换体系类似，椭圆曲线公钥体系要求用户共享同一参数，首先选取参数B，C，P并构造模P下的离散椭圆曲线Kp（b，c），然后在Kp（b，c）上选取一个G并选取编码参数￡，共享参数是（Kp（b，c），G，￡）[10]。

假设甲方拟设立椭圆曲线公钥体系的公钥和私钥，则甲方首先随机选取一个正整数KA作为私钥，然后计算PA=kAG作为公钥，假设乙方需要将明文M用ECC加密后送给甲方，这里的M是满足（M+1）￡

乙方首先选取一个随机正整数K，将M编码得PM=（x，y），然后计算如下Kp（b，c）中的两个点作为密文：C=（kG，PM+kPA），用∏0（C）表示 kG，∏1（C）表示PM+kPA。甲方收到密文C后用ECC解密算法将C解密，算法如下：

PM=∏1（C）—kA∏0（C）

然后从PM=（x，y）算出M=[x/y]。

3.2 椭圆曲线密码的安全性

ECC的安全性是建立在由P和kP确定的困难程度之上的，这个问题称为椭圆曲线对数问题，Pollard rho方法是已知的求椭圆曲线对数的最快方法之一，表1表示了从密码分析所需计算量的角度，通过给出可比较的密钥大小，比较了各种算法。由此可知，ECC使用的密钥比RSA中使用的密钥要短得多，而且在密钥长度相同时，ECC与RSA所执行的计算量也差别不多。因此，与具有同等安全性的RSA相比，由于ECC使用的密钥更短，所以ECC所需的计算量比RSA少。

3.3 椭圆曲线密码实现Diffie-Hellman密钥交换

利用椭圆曲线可实现如下密钥交换。首先，挑选一个大整数q，及椭圆曲线参数a和b，这里q为素数p或是形式为2m的整数。由此可以定义出点的椭圆群为Kq（a，b）；其次，在Kp（a，b）中挑选一个基点G，G=（x1，y1），G的阶为一个非常大的数n。使得nG=0成立的最小正整数是椭圆曲线上的点G的阶n。G和Kq（a，b）是该密码体制中通信各方都已知的参数。

用户A和用户B之间完成密钥交换过程如图1所示。

⑴ A选择一个小于n的整数nA作为其私钥，然后产生其公钥PA= G×nA；该公钥是Kq（a，b）中的一个点。

⑵ B可选择私钥nB并计算公钥PB。

⑶ A产生秘密钥k=PB×nA，B产生秘密钥k=PA×nB。

要破译这种体制，攻击者必须由kG和G计算出k，这通常被认为是非常难的[11]。如取p=211，Kp（0，-4），G=（2，2），这里Kp（0，-4）即是曲线y2=x3-4，则计算可得240G=0。A的私钥nA=121，所以A的公钥PA=121（2，2）=（115，48）。B的私钥nB=203，所以B的公钥为203（2，3）=（130，203），它们共享的密钥为121（130，203）=203（115，48）=（161，69）。

这里得出的密钥是一对数字，若将它当作传统密码中的会话密钥，则必须是一个数字，可以简单地选取x坐标或者x坐标中的某个简单函数[12]。

4 结束语

利用椭圆曲线公钥加密是目前公钥加密发展的方向，但是，椭圆曲线公钥密码的理论复杂，选取不同的椭圆曲线参数和加密算法对加密的安全性和效率影响很大；椭圆曲线公钥体系的强度依赖于椭圆曲线离散为难题的难解性。椭圆曲线公钥体系对参数长度的要求虽然没有RSA公钥体系的要求高，但是椭圆曲线公钥体系破译方法的研究还没有像RSA公钥体系破译方法研究得那么广泛和深入，这可能与椭圆公钥体系用到较深的数学有关。利用本文所述方法选取椭圆曲线等参数和相关算法进行加密被证明是安全的、有效的，也真正达到了现阶段公钥加密的要求。

参考文献：

[1] 刘淳，张其善.基于智能卡的ECC算法的实现[J].计算机工程与应用，2009.4：65-68

[2] 蔡庆华，程一飞.一个基于超椭圆曲线的单向数字签名[J].计算机技术与发展，2006.1：89-90

[3] 王杰.计算机网络安全的理论与实践[M].高等教育出版社，2011.

[4] 唐勇，许金玲.RSA密码系统有效实现算法[J].微处理机，2011.3：128-130

[5] 杨晋.现代电子商务安全技术研究[J].网络安全技术与应用，2009.1：89-92

[6] 杨敏，杜瑞颖.密码编码学与网络安全原理与实践[M].电子工业出版社，2012.

[7] 陈颂，何良生，王建华，徐旸.ECC数字签名协议的安全性研究与分析[J].信息网络安全，2007.6.

[8] 朱艳琴.基于ECC的密码系统研究与设计[J].微电子学与计算机，2007.12.

[9] 高冬妮，陈云峰.一种改进的ECC数字签名方案[J].信息技术，2009.10：96-99

[10] 徐秋亮，李大兴.圆曲线密码体制[J].计算机研究与发展，2009.5：102-104

[11] 赵泽茂，刘凤玉：基于椭圆曲线密码体制的签名方程的构造方法[J].计算机工程，2007.6：132-135

[12] 张龙军，沈钧毅，赵霖：椭圆曲线密码体制安全性研究[J].西安交通大学学报，2010.10：56-58