椭圆曲线及其在密码学中的应用研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇椭圆曲线及其在密码学中的应用研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：现代密码学协议的安全性多数是建立在数学难题基础之上，比如：大整数因子分解、有限域上的离散对数问题。通常情况下，这些算法不存在多项式时间问题，但随着攻击算法地不断改进，要求使用这些安全协议的算法密钥不断的加大，才得保证其使用的安全性。但密钥的加大增加了算法的复杂性，因此，找到一种能抵抗各种常见攻算法，运算量小，速度快的离散对数密码算法非常重要，椭圆曲线密码算法正好满足这种需要。论文回顾了常用公钥密码体制协议，相对于目前应用的其它密码体制，椭圆曲线密码体制有很大的优势，最后，分析了椭圆曲线密码体制在实际应用中可能受到的各种攻击算法。

关键词：椭圆曲线密码体制；对称密码体制；非对称密码体制

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）34-7776-06

密码学可以认为是数学的一个分支，它是密码编码学和密码分析学的总称。通常主要用于保护通信双方实施安全的信息传递，且不被非授权的第三方知道。密码学的发展经历了三个阶段：手工加密技术、经典加密技术、现代计算机加密技术[1]。当前的密码技术和理论都是基于以算法复杂性理论为特征的现代密码学。

Shannon在1949年发表的“The Communication Theory of Secrecy System”奠定了密码学的理论基础，并使之成为一门独立的科学。1976年，Diffie & Hellman发表的“New Direction of The Cryptography”首次提出了公钥密码学的基本思想，开创了公钥密码学的新纪元[2]。

当前通用的密码体制一般基于以下三类数学难题：

1） 基于大整数因子分解。1978年，麻省理工学院Rivest、Shamir、Adlman三位学者首次发表的RSA公钥密码体制就是基于此的一种公钥密码体系，简称RSA算法。

2） 基于有限域上离散对数。最著名的有ElGamal、DSA数字签名算法。

3） 基于椭圆曲线离散对数。基于椭圆曲线有限加法群上的椭圆曲线离散对数问题的求解困难性，同其他公钥密码体制相比较，在相同安全强度下，椭圆曲线密码系统具有密钥短、占用空间和带宽小、处理速度快等优势。基于椭圆曲线建立的密码体制还有两大优点：一是可用于构造有限点群的椭圆曲线数量多；二是计算椭圆曲线有限点群的离散对数亚指数算法不存在，解密算法难度很大，安全性高。

1 公钥密码算法相关研究

由于对称密码算法在密钥管理、分发和数字签名方面的缺陷，1976年W. Diffie和 M. Hellman提出了一种巧妙的密钥交换协议，称为Diffie-Hellman密钥交换协议/算法[8]，比如Alice和Bob希望通过公共通信网协商一个会话密钥，只需要以下操作过程：

这种算法是安全的，对于窃听者Charlie，他只能得到ga mod p或者gb mod p，如果他想构造出gab mod p，这便属于一个离散对数问题，我们知道目前这还是一个数学难题。

在公钥密码系统中，每位计算机网络的通信者都应该拥有两个密钥，其中一个是对外保密的“私钥”，另一个是对网络上所有人公开的“公钥”。私钥和公钥都可以对信息加密，但私钥加密的信息须用对应的公钥解开，公钥加密则须用对应的私钥解开。使用公钥密码系统，网络上的双方无需事先传递密钥就能进行保密通信[11]。

首个公钥密码系统由形Rivest、Shamir和Adleman在1978年提出来，简称为RSA公钥密码[9]，RSA的安全性是基于大整数因子分解难题。目前，国内外大多数使用公钥密码进行加密、解密和数字签名/验证的产品都是基于RSA密码体系。RSA密码体系的安全性完全依赖于大整数因子分解问题，随着解决因子分解方法的进步及完善、计算机运算速度的不断提高和计算机网络的发展， RSA密码的安全性受到了前所未有的挑战，人们必须选择更大的整数，以增加破解的难度。目前，安全的RSA密码需要的大整数都在1024位以上的二进制长度，造成了RSA密码实现的代价变得越来越难以任受， 导致了RSA应用的效率越来越低，成为RSA应用的主要瓶颈。

第二个著名的公钥密码是EGamal密码[10]，它的安全性依赖于离散对数问题。假设G为一个有限乘法循环群， g为G的生成元，x为任意的整数，如果已知g及gx，如何求解x的问题在数学上称为离散对数问题。在当前环境下，当群G选择适当，且整数x充分大时，求解是非常困难的，现己知最快的求解数域上离散对数的方法是亚指数级时间复杂度。

第三个著名的公钥密码是基于有限域上椭圆曲线加法群的离散对数问题，它是华盛顿大学的Neal Koblitz[4]和在IBM工作的Victor Miller[5]各自独立地提出来的，这使得研究了150多年的椭圆曲线在密码领域中得以发挥重要作用。椭圆曲线密码体制（Elliptic Curves Cryptography ， ECC）的数学基础是椭圆曲线上的点构成的Abel加法群中离散对数的计算困难性。可以证明基于有限域上ECDLP的困难性要高于一般乘法群上的离散对数问题的困难性，而且椭圆曲线域的运算位数远小于传统离散对数，且很容易使用软件或硬件在计算机上进行实现。同时，利用ECC实现速度非常快，在同等安全强度下，ECC所需的计算量、存储量、带宽、开销都较小，且加密和签名的速度高。因此，ECC特别适用于计算能力、带宽和集成空间受限的地方，比如Smart卡。由于ECC具有其他公钥密码体制无法替代的优点，ECC从提出就得了到广泛关注，而且被认为是下一代最通用的公钥密码系统。

2 椭圆曲线基本理论

2.1椭圆曲线定义

椭圆曲线是一门古老且内容丰富的数学分支，1985年，Victor Miller和Neal Koblitz各自独立地提出椭圆曲线公钥密码学，它的基本思想仍然是基于有限域乘法群的公钥密码体制，用有限域上椭圆曲线构成的群来类比有限域的乘法群，从而获得类似的公钥密码体制。ECC的安全性是基于椭圆曲线离散对数问题的难解性，经证明它目前还没有亚指数攻击方法，所以，ECC具有一些其它公钥密码体制无法比拟的优点。

椭圆曲线并非我们通常意义上的椭圆，这样命名的原因是因为对椭圆曲线的研究来源于椭圆周长计算问题，以及所描述的椭圆积分等问题，这里[E（x）]是[x]的三次或四次多项式。

2.2椭圆曲线上点的加法规则

以上加法规则在复数、实数、有理数和有限域[GF（p）]上均有效。值得指出的是，对于有限域[GF（p）]的情形，上述加法规则得到的应是[modp]的结果。对于有限域[GF（2m）]，由于所用椭圆曲线形式发生变化，因此上述加法规则应做相应修改，这方面可参考相关资料。

2.3 椭圆曲线分类

3 椭圆曲线在密码学中的应用

3.1椭圆曲线密码体制的建立[7]

首先选取一个基域[Fq]，它可以是一个素域，也可以是一个特征为2的域[F2m]（[m]为素数）。其次在[Fq]上选取一条椭圆曲线[E]，并使其群阶为一个大素数[N]，或者是一个大素数与一个小整数的乘积。然后选取[E]上的一个阶为大素数的[n]的点[P]。有限域[Fq]、曲线[E]、点[P]和其阶[N]均为公开的信息。

3.2 椭圆曲线密钥对的生成

每一个参与者需要完成下述过程：

3.3 椭圆曲线加密方案

现在假设Alice要向Bob发送信息，则Alice加密过程如下：

3.4 椭圆曲线签名方案（ECDSA）

我们给出基于椭圆曲线的数字签名方案，称为ECDSA。

ECDSA签名生成：设Alice 要对信息M签名后，传送给Bob，则Alice要完成以下步骤：

3.5椭圆曲线密钥生成协议（ECKEP）

这里给出一个基于椭圆曲线的密钥协议：

由于ECC的安全性和优势非常明显，再加上许多标著名组织在椭圆曲线密码算法标准化方面做了大量工作，在1998年ECC被确定为ISO/IEC数字签名标准，1999年椭圆曲线数字签名算法被ANSI确定为数字签名标准。

3.6 椭圆曲线密码体制分析

同以往的公钥密码体制相比较，椭圆曲线密码体制有以下三个方面的优点[2]。

1） 安全性高

目前，针对有限域上的离散对数问题攻击的最快算法是指数积分法，其运算复杂度为：

而攻击椭圆曲线上的离散对数问题的常用算法为大步小步算法，它的复杂度为：

2） 密码长度更小

对以上两种攻击密码算法的复杂度进行比较，可知在同等安全性能下，椭圆曲线密码体制算法需要的密钥长度远小于有限域上离散对数问题的公钥密码长度，因此，椭圆曲线密码体制更适合于存储空间有限、带宽小、运算速度高的环境中。

3） 算法灵活性更好

通常情况下，如果有限域[GF（p）]确定，那么其上的循环群也就确定了，但有限域上的椭圆曲线却可以通过改变曲线参数而进行随机变化，相应地生成不同的循环群，从而导致椭圆曲线有着丰富的结构和多种选择，与RSA/DSA相比较，在安全性同等的条件下，椭圆曲线密钥长度更小，灵活性也高。

4 结论

自公钥密码体系被提出来，都是以某一含有“陷门”的数学难题作为其安全性基础的，各种椭圆曲线公钥密码体系的安全性都与相应的椭圆曲线离散对数问题的求解困难性等价。如果离散对数可以计算，那么从一个用户的公钥就可以推导出相应的私钥，这样系统就不安全了。目前，有许多针对椭圆曲线离散对数的攻击算法，主要有以下几类：针对一般离散对数问题的攻击算法，比如大步小步算法和Pollard-p算法；针对特殊椭圆曲线的攻击算法，如针对超奇异型椭圆曲线的MOV类演化算法，还有针对畸异型椭圆曲线的SSAS多项式时间算法等。

从以上分析可知，只要选取的椭圆曲线能抵抗上述几种常见的攻击算法，即选取一条安全的椭圆曲线，那么椭圆曲线密码的安全性是可以保证的，但如何才能选取一条安全的椭圆曲线，这是一个深刻的数学难题，有待于相关领域的深入研究。总之，我们在给椭圆曲线选择参数时应该谨慎，为避免安全隐患，所选择的椭圆曲线上的离散对数问题必须能够抵抗上述的所有攻击。

参考文献：

[1] 郭海民，白永祥. 数论在密码学中的应用[J].电脑知识与技术，2010（6）.

[2] William Stallings.Cryptography and Network Security –Principles and Practice， Fifth Edition[M].Publish House of Electronics Industry， 2011.

[3] 胡向东，魏琴芳，等.应用密码学[M]. 2版.北京：电子工业出版社，2011.

[4] Victor S.Miller. Elliptic curves and their use in cryptography[J]. Mathematics of Computation， 1997（61）：1-15.

[5] Neal Koblitz. Elliptic curves cryptosystems. Mathematics of Computation， 1987（177） ：203-209.

[6] Miller. Use of elliptic curve in cryptography. In advances in cryptology-CRYPTO’85（Santa Barbara Calif.），Spring-Verlag，1985：417-412.

[7] 张方国.超椭圆曲线密码体制的研究[D].西安：电子科技大学，2001.

[8] 吴世忠，祝世雄.应用密码学[M].北京：机械工业出版社，2000.

[9] W.Diffie and M.Hellman. New directions in cryptography[J]. IEEE Trans. Inf. Thy. 1976，22：644-654.

[10] Rivest， Shamir，Adleman. A method for obtaining digital signatures and public-key cryptosystems[J]. Comm Assoc. Computer Math，1978（21）：120-126.

[11] EIGamal T. A public key cryptosystem and signature scheme based on discrete logarithms[J]. IEEE Trans. Inf. Thy.， 1985（31）：469-472.

[12] http：//.cn/templates/T_second/index.aspx？nodeid=36&page=ContentPage&contentid=333.