ECC方案的安全性分析.doc

课程（论文）题目： ECC方案的安全性分析内容：摘要：本文分析了相对于RSA具有诸多优点的椭圆曲线密码系统(ECC)的原理和安全性。对于特殊曲线，攻击法主要有MOV法和Smart法；对于一般曲线主要有大步小步法和Pollard 法。关键词：ECC；攻击；安全性能Abstract:This paper analyzes the principle and safety of Elliptic Curve Cryptosystem (ECC) which has many merits compared with RSA. For special curve, attack methods are mainly MOV method and Smart method; For general curve ,there are Baby Step Giant Step and Pollard method.Keywords:ECC;attack;safety1、引言 公开密钥算法于1976年提出其安全性依赖于对离散对数的计算难度。从那以后，离散对数问题引起了人们的重视和广泛研究，被应用到在公开密钥密码系统和数字签名中。其安全性是基于有限域上椭圆曲线加法群的离散对数问题(ECDLP)。由于在一般的椭圆曲线群中没有次指数时间算法解ECDLP所以椭圆曲线密码体制的加密算法是目前对每比特提供加密强度最高的一种算法1。 椭圆曲线密码系统(ECC)，即基于椭圆曲线离散对数问题的各种公钥密码体制，最早是在1985年分别由V.S.Miller和Neal Koblitz独立提出的。从1985年以来，ECC受到了全世界密码学家、数学家和计算机科学家的密切关注。许多研究成果和应用实例不断涌现。 ECC相对于RSA和DSA等系统在解决其数学问题椭圆曲线离散对数问题(ECDLP)时也要用完全指数时间2。椭圆曲线加密方法与RSA 方法相比，有以下优点3: (1) 安全性能更高 加密算法的安全性能一般通过该算法的抗攻击强度来反映。ECC 和其他几种公钥系统相比，其抗攻击性具有绝对的优势。如160 位ECC 与1024 位RSA、DSA 有相同的安全强度。而210 位ECC 则与2048bit RSA、DSA 具有相同的安全强度。 (2) 计算量小，处理速度快 虽然在RSA 中可以通过选取较小的公钥(可以小到3) 的方法提高公钥处理速度,即提高加密和签名验证的速度，使其在加密和签名验证速度上与ECC有可比性，但在私钥的处理速度上(解密和签名)，ECC 远比RSA、DSA 快得多。因此ECC 总的速度比RSA、DSA 要快得多。 (3) 存储空间占用小 ECC 的密钥尺寸和系统参数与RSA、DSA 相比要小得多，意味着它所占的存贮空间要小得多。 (4) 带宽要求低当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消息时ECC 带宽要求却低得多。而公钥加密系统多用于短消息，例如用于数字签名和用于对对称系统的会话密钥传递。带宽要求低使ECC 在无线网络领域具有广泛的应用前景。ECC方法具有的诸多优点使得其成为密码学研究的热点，同时具有广阔的发展前景和应用前景。2、 二进制域椭圆曲线 椭圆曲线的研究来源于椭圆积分，这里E(x)是x的三次或四次多项式。由于这样的积分不能用函数表示，为此引入椭圆曲线的概念。椭圆曲线指的是，在射影平面上满足韦尔斯特拉斯方程 的所有点的集合，且曲线上的每个点都是非奇异(或光滑)的。所谓“非奇异”或“光滑”是指曲线上任意一点的偏导数不能同时为0，即满足方程的任意一点都存在切线。满足非奇异方程的所有点外加一个无穷远点O，就组成了椭圆曲线。 有限域上的椭圆曲线方程为：，此方程由参数确定。 椭圆曲线域参数是用以构造一个椭圆曲线密码系统所需的参数集，包括：有限域、椭圆曲线、椭圆曲线的基点、基点的阶。当选择二迸制域上的椭圆曲线时，它是由一个七元组构成的：其中确定了有限域的定义多项式 a和b确定了椭圆曲线E的方程 G是所定义椭圆曲线的基点(Base Point) n是基点G的阶，且要求n为大素数 椭圆曲线方程的所有解，连同“无穷远点”(记为O)组成的集合记为，即表示了二进制域上的一个椭圆曲线。其中椭圆曲线上的点数用来表示。其判别式=一b。椭圆曲线非奇异当且仅当b0。3、安全性分析 椭圆曲线离散对数问题(ECDLP)是椭圆曲线密码学的基础。设E是定义在有限域上的椭圆曲线，点乘，其中P、Q是椭圆曲线E上的点，k1，n一1，n是椭圆曲线的阶，由给定的P和Q求解k，称为椭圆曲线上的离散对数问题4。由椭圆曲线的运算规则可知，根据k、P计算Q是相当简单的；反之，由Q、P求出k在计算上则是非常困难的，这就是椭圆曲线离散对数问题的难解性。 椭圆曲线密码系统的安全性建立在ECDLP的难解性上。其它常用的公钥密码系统(RSADSA)的安全性则是建立在分解两个大素数积的基础之上的，解这类问题的通用方法是亚指数时间复杂度的算法。与整数因子分解问题和一般离散对数问题(DLP)不同，目前已知的求解椭圆曲线离散对数问题的最佳算法是Pollard -因子分解算法，它是全指数时间复杂度的算法。因此，一般的用于离散对数的有效攻击不能应用到ECDLP上来。从这种意义上讲，椭圆曲线密码系统(ECC)是目前安全性最高的公钥密码系统。 虽然ECC系统的安全性很高，但是对它的攻击方法也有些是很有效的。一些特殊曲线的密码体制能够较快实现，过去它们曾经被建议用以构造密码体制。但是目前对几类特殊曲线的攻击已有了比较有效的方法，如MOV方法和Smart方法。因此，在系统进行椭圆曲线选取时，已禁止使用这几类曲线。 1）MOV方法一种将ECDLP归约为有限域上离散对数问题的方法采用指数计算法，只适用于超奇异椭圆曲线。对于超奇异椭圆曲线MOV算法利用WeilParing方法，可建GF(q)扩域上椭圆曲线的加法群与GF(q)的乘法群之间的联系，特别是把计算椭圆曲线的ECDLP转化为计算有限域的乘法群的离散对数，这也证明了建立在ECDLP上的椭圆曲线密码体制比基于有限域上的离散对数密码体制更具优越性。 2）Smart方法 设q是素数，对定义在上，当时的椭圆曲线E称为“畸形” (Anamalous)曲线。Smart在1998年提出了一种时间内求解的方法，同时Semaev也给出了一种在时间内求解的方法。Smart方法就是构造了到的加法群的一个同构映射，使得在多项式时间内可求解这类ECDLP。 畸形椭圆曲线和超奇异椭圆曲线这两类特殊的曲线都应该避免使用。对一般曲线的攻击主要有：大步小步法和Pollard P方法。 1大步小步法(Baby Step Giant Step) 设群的阶为n，令，取，m可唯一表示成，也就是。依次对b=0,1，2，L，计算bP并列表；依次对a=0，1，L，计算,并且在并列表查找，这样可以得到m。其时间复杂度为和空间复杂度都为。这一算法是对“穷搜索方法在时间和空间上的一种折衷。 2Pollard 方法 1978年Pollard提出了一种概率求解的方法，其时间复杂度大约是，与Shanks的大步小步法相当，但由于其空间复杂度仅为，所以一般认为Pollard的方法优于大步小步法。Orschot和Wiener在此基础上提出了分布式Pollard 算法，时间复杂度约为，其中r表示进程数。目前分布式Pollard 算法是已知的对一般椭圆曲线离散对数最好的攻击方法。攻击者利用算法Pollard p攻击的途径有硬件攻击(Hardware Attacks)和软件攻击(Software Attacks)。硬件攻击需要攻击者拥有高性能的特殊用途的硬件设施。目前，200比特长的椭圆曲线密码已经有非常高的安全强度。椭圆曲线密码体制的诱人之处在于安全性能相当的前提下，其密钥的长度更短5。4、 结束语 相对于RSA，椭圆曲线密码系统(ECC)具有诸多优点。本文简要分析了ECC的原理和安全性能。对于特殊曲线，攻击法主要有MOV法和Smart法；对于一般曲线主要有大步小步法和Pollard 法。国内的对其的实际应用研究还远远不足，有待进一步从理论研究转化为相应的成果。参考文献1罗涛，易波.关于椭圆曲线数字签名算法研究J.计算机