谢宗晓　李达　马春旺

1 概述

公钥密码算法的产生主要是为了解决密钥分发困难的问题1）。1976年，Whitfield Diffie和Martin Hellman提出了公开密钥加密的设计思想，但当时并未能给出实现的算法。之后，有多种算法被提出，但经得住考验得到大面积应用的主要是Ron Rivest、Adi Shamir和Leonard Adleman在1978年提出的RSA算法。直到现在，RSA几乎成了公钥密码领域事实上的标准。关于公钥密码算法的更多基础知识，请参考文献[1]。

RSA算法的安全性，主要是基于大整数质因数分解的困难性，这意味着如果这个整数太小，就很容易受到暴力攻击。所以，RSA算法的密钥，越来越长。NIST2）建议在2010年12月31日前停止使用RSA1024，升级至RSA2048。当然，到目前，也没有明确的证据表明RSA1024已经被破解了，但是从当前计算能力的升级速度推测，RSA1024确实已经不安全了。

密钥长度的不断增加意味着效率在不停地降低，与一味地增加密钥长度相比，寻求更合适的陷门单向函数是解决这个问题更佳途径。Neal Koblitz3）和Victor Miller4）分别独立地在1985年将椭圆曲线引入密码学领域。

2 椭圆曲线密码学

椭圆曲线密码学（Elliptic curve cryptography，ECC）的数学基础远没有RSA算法那么易于理解。首先，椭圆曲线和椭圆是两码事，两者之间联系不大。最常见的椭圆曲线方程，如公式（1）典型的二元三次方程。

但是这个方程的几何表现形式并不是椭圆，或者说，跟椭圆基本没什么关系。其图形如图1中的示例。

之所以被命名为椭圆曲线方程，是因为圆周长有固定的公式，很容易求解，但是椭圆就复杂得多，开始人们想利用微积分计算椭圆的周长，其最终表达式类似于公式（2）。……