椭圆曲线密码体制的分析和展望

商艳红，侯金凤

（唐山师范学院 计算机科学系，河北 唐山 063000）

计算机科学与技术研究

椭圆曲线密码体制的分析和展望

商艳红，侯金凤

（唐山师范学院 计算机科学系，河北 唐山 063000）

椭圆曲线密码体制（ECC）已成为密码学的研究热点之一。相对于其他的公钥密码体制，椭圆曲线密码体制具有密钥短和计算效率高等优点。从椭圆曲线密码体制的各优点出发，介绍并分析椭圆曲线密码体制的发展前景。

椭圆曲线密码体制；移动办公；智能卡；无线网络

1 ECC的背景

随着计算机速度的迅速提高人们给出了多种加密方案及其改进[1,p384;2]，但仍旧不能满足Internet分布式计算能力的日益强大，而经典的公钥密码体制如RSA等，在密钥长度为512 bit下已经越来越不安全，增加密钥长度虽然能增强其安全性，但是加解密的效率越来越低，同时对系统要求越来越高，唯一的办法就是使用新的有效的密码体制。

椭圆曲线密码体制（ECC）是一种基于椭圆曲线数学的公钥密码体制。椭圆曲线在密码学中的使用是在 1985年由Neal Koblitz和Victor Miller分别独立提出的。在公钥密码体制中，相比较其他算法而言，ECC具有密钥短和计算效率高等优点，且ECC本身算法的数学理论非常复杂深奥。其原理[1,p190]在于：给定素数p和椭圆曲线E，对Q=kP，在已知P，Q的情况下求出小于p的正整数k，已知k和P计算Q比较容易，而已知Q和P计算k则比较困难，至今没有有效的方法来解决此问题。

一个利用椭圆曲线进行加解密通信的过程如下：

（1）用户A选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G；

（2）用户A选择一个私钥k，并生成公钥K=kG；

（3）用户A将E和点K、G传给用户B；

（4）用户B接到信息后，将待传输的明文编码到E上一点M，并产生一个随机整数r（r＜n）；

（5）用户B计算点C1=M+rK和C2=rG；

（6）用户B将C1、C2传给用户A；

（7）用户A接到信息后，计算C1-kC2，结果就是点M，再对其进行解码即可得到明文。

椭圆密码体制的安全性是基于求解椭圆曲线离散对数问题的最有效算法的时间复杂度，与一般的有限乘法群上的离散对数问题不同，有限域上的椭圆曲线离散对数问题的求解更难，不能被所有已知算法在多项式时间内求解。从数学理论的角度，ECC具有每比特最高安全强度，而且，ECC被公认为目前已知的公钥密码体制中每比特提供加密强度最高的一种体制。

2 ECC的优势分析及应用前景

椭圆曲线离散对数的计算难度是完全指数级的，相对于其他密码体制，ECC具有诸多优势。下面就从ECC的优势切入，对其优势进行分析并探讨它的应用展望。

2.1 安全性高

在所有密码体制中，安全性无疑是最核心的问题。由上给出的ECC算法数学原理可得出，有限域上的离散对数问题是ECC的核心，而次离散对数问题不能被所有已知算法在多项式时间内求解，可见ECC的抗攻击性占据绝对优势。由表1可以看出，同等安全条件下，ECC的安全性远远优于RSA，如采用160位的ECC和1 024位的RSA算法的安全强度相当；而且，在同等安全条件下，安全要求越高，其短密钥的优势会越明显。可见，相对于RSA，ECC每比特具有较高安全强度。

表1 ECC与RSA密钥长度及安全性的比较

基于这一特点，ECC在移动电子商务、电子政务和计算机网络安全以及软件的注册等领域具有广阔的应用前景[3]。

2.2 计算量小，处理速度快

公钥的生成速度主要是由其中的大数算术运算决定，而大数算术运算的速度跟大数的规模密切相关，在相同计算条件下，ECC的实现可以选取比RSA小得多的大数，ECC的实现速度比RSA快得多。如表2所示，在相同安全强度下，ECC在密钥对的生成、签名以及认证方面，实现速度均比RSA快得多。如在密钥对生成上，ECC仅需3.8 ms，而RSA需要4 708.3 ms，此外，对于ECC来说，所有应用于离散对数加密系统的计算技巧可以同样应用于基于椭圆曲线的系统中，对于基于ECC的密码系统的运算还可以采用快速冗余算法来降低计算开销。这使得ECC在私钥处理速度上快得多。

ECC的计算开销小以及速度快，尤其在存储容量有限且运算能力较低等方面，具有显著优势。实际应用中，在VPN安全隧道方面，考虑到嵌入式应用在计算机资源和存储资源方面的局限性，根据ECC加解密速度快、节省带宽、节省存储资源，可选择ECC来设计和实现身份鉴别[4]；在移动通信以及网络通信方面，需要高效地对数据进行加密，ECC处理速度快的特点使得移动通信的发展不再受存储容量及低计算能力的限制。此外，ECC在集成电路卡、数字签名等加密速度要求高的地方能够实现快速、安全的加密和签名。

表2 ECC密码与RSA密码软件实现速度的比较

2.3 存储空间小

ECC的密钥长度和系统参数与RSA相比要小得多，由表1可知，RSA算法需要512位，而仅需106位即可保证其安全性，这就意味着ECC所需的存储空间小得多。在计算上，所选素数小，计算开销小，这也使得ECC在存储空间有限制的设备上有更好的应用。

随着移动互联网时代的到来，ECC的这一优势决定了它在移动通信设备、智能卡等存储空间小、运算能力差的设备上的发展地位[5]。智能卡作为电子媒介的主要形式具有体积小、便于携带、安全性高并具一定的数据存储和处理能力、可进行数据加密、解密和数字签名等特点，从而在电子交易中得以广泛的应用。然而，由于其存储容量和计算速度的限制，在对其进行加密时所使用的密钥应尽可能的短，这样才能为智能卡的实用化奠定基础。智能卡的数据传送相对较慢，为提高应用效率，基本数据单元必须小，这样可以减少智能卡与卡的终端之间的数据流量。将ECC应用于智能卡的优点是生成私钥公钥方便、节省存储空间、节省带宽、提高实用性、节省处理时间，而且不需要增加硬件的处理。ECC密钥短所带来的优点弥补了智能卡硬件的局限，不仅有效降低了智能卡的生产成本，也提高了实用性。

2.4 带宽要求低

由于ECC比其他加密算法密钥短，使得其在传输时带宽要求更低。当对长信息进行加密时，ECC、RSA密码系统有相同的带宽要求，但应用于短信息时ECC的带宽要求却低得多，使得ECC在无线网络中具有广阔的应用前景[6]。

目前而言，在无线网络方面，WLAN的安全问题一直是业界广泛关注的问题，它一直制约着WLAN的大规模推广及企业级应用。现在使用的SSL标准安全套接层握手协议带宽开销大而使得网络数据通信效率低，ECC可减少一定量的带宽开销，使得通信效率得到提高。同时，在Web服务器上的带宽有限使得带宽的费用高昂，而ECC恰恰解决了Web服务器的实现遇到的这种瓶颈，节省了计算时间和带宽。在 3G网络方面，针对计算资源和带宽资源有限的弱点，基于ECC涉及安全的支付流程，可实现端对端的信息安全传输。

3 ECC的发展

椭圆曲线密码体制是现有公钥密码体制中比特位强度最高的密码体制，其发展前景相当广泛，且适应于当代社会的需求。但就目前而言，还面临着很多理论以及技术上的问题，如何选取合适的有限域GF(Qm)的椭圆曲线E，如何选取基点P对于ECC的速度、效率、密钥长度以及安全性来说至关重要。

3.1 对于安全性而言，如何选取合适的适合安全条件的随机椭圆曲线的问题

椭圆曲线密码系统若没有采用安全的椭圆曲线，那么整个系统就不安全。所谓安全椭圆曲线是指能够抗各种已有攻击的曲线，目前对椭圆曲攻击比较有效的方式是Mov攻击、Smart方法，大步小步法。为抵抗上述攻击，有限域GF上的椭圆曲线必须满足：

（1）阶有最大的素因子；

（2）不是超奇异曲线；

（3）不是畸形曲线。

确定椭圆曲线的参数后，还必须找出一个基点以构造各种基于椭圆曲线的密码体制。

3.2 对于运算效率而言，如何产生合适的符合安全条件的椭圆曲线并快速实现的问题

有效地计算椭圆曲线的阶是主要问题。因为安全的椭圆曲线的核心步骤是对椭圆曲线阶的计算，对椭圆曲线阶的有效算法的研究也是实现安全椭圆曲线密码体制的一个极其重要的环节。

椭圆曲线密码体制中，椭圆曲线群上的点的倍乘占了整个运算的很大比例，其效率关系到整个体制的执行效率，对于椭圆曲线中的 kP倍乘计算仍需研究更高效、快捷的方法。

4 结束语

ECC是一种能适应未来通信技术和信息安全技术发展的新型密码体制。目前，在实际应用中，相关产品不是很多，主要集中在软件实现上。相信在理论算法的突破以及实现技术的更新下，ECC的实现会越来越迅猛。随着其标准的成型，相关的ECC产品，尤其是能体现ECC优势的智能卡将很快问世和得到很好推广。

[1] 张焕国,王张宜.密码学引论(第二版)[M].武汉：武汉大学出版社,2009：384.

[2] 商艳红,张静.一种基于 PlayFair密码的改进算法[J].光盘技术,2009(3)：50.

[3] 麻胜海.基于椭圆曲线的数字签名在移动办公中的应用[J].科技信息,2010(5)：483-484.

[4] 丛清日,胡金初.基于椭圆曲线密码体制的通信认证[J].上海师范大学学报(自然科学版),2010(3)：45-47.

[5] 项灿.ECC智能卡在电子交易中的安全应用[J].科技信息,2008(20)：370-371.

[6] 曹阳,权双燕.ECC在无线局域网安全中的研究与应用[J].乐山师范学院学报,2009(5)：76-78.

（责任编辑、校对：赵光峰）

Analysis and Forecast of Elliptic Curve Cryptosystem

SHANG Yan-hong, HOU Jin-feng

(Department of Computer Science, Tangshan Teachers College, Tangshan 063000, China)

Elliptic Curve Cryptosystem (ECC) has become one of the research hotspots in cryptography. Compared to other public-key cryptosystem, Elliptic Curve Cryptosystem has shorter key and calculation of high efficiency. Based the advantages of Elliptic Curve Cryptosystem this article introduces and analyzes the development prospect of elliptic curve cryptosystem.

ECC; mobile office; smart card; wireless network

唐山师范学院教育教学改革研究项目（2012001021）

2012-05-23

商艳红（1979-），女，河北乐亭人，硕士，讲师，研究方向为密码学、信息安全。

TP309.7

A

1009-9115(2012)05-0044-03