椭圆曲线密码体制是代替RSA公钥密码体制的非常有力的竞争者之一。从现有的研究结果看,RSA和ElGamal密码体制的安全强度是亚指数的,椭圆曲线密码体制的安全强度是指数的。
椭圆曲线密码系统的安全性基于椭圆曲线离散对数问题的困难性,目前求解椭圆曲线离散对数问题主要有通用方法和特殊方法2类。
通用方法适合全部有限循环群上的离散对数问题,主要包括大步小步法、Pollard rho算法和Pohlig-Hellman算法等。通用方法没有利用具体的椭圆曲线的特征,都是完全指数时间的。
特殊方法主要含素域异常曲线攻击、MOV约化攻击和Weil下降攻击等,这些攻击方法利用了特殊曲线明显的特征,因而效率较高。但这些特殊曲线在构建椭圆曲线密码系统时很易被检测出来。比如FIPS 186-3就对选择椭圆曲线的参数做了限制,并给出了一些检测算法,防止攻击者用较弱的参数攻击。
对于设计完善的椭圆曲线密码系统,目前最有效的攻击算法是Pollard rho算法。该算法基于生日攻击,由Pollard在1978年提出。2001年以后,Pollard rho算法在理论上逐渐成熟,攻击效率主要依赖于硬件条件及在具体平台上的实现。
为了提高密码学界对椭圆曲线密码系统安全性的认识,加拿大的Certicom公司在1997年公布了一系列椭由线密码系统挑战,这些挑战分为三个级别:练习级、一级和二级,其中练习级挑战的规模为79bit、89bit和97bit,一级挑战的规模为109bit和131bit,二级挑战的规模为163bit、191bit、239bit和359bit。每个规模的挑战有三个,一个基于素数域上的椭圆曲线,另外两个分别基于二进制扩域上的一般椭圆曲线和Koblitz曲线。练习级的挑战在2000年之前就被全部解决,一级挑战中109bit规模上的三个挑战2004年之前被解决，131bit规模上的挑战到2015年9月都还没有解决。
目前已解决的ECC挑战都是由Pollard rho算法完成的,由于该算法是一个完全指数时算法,因此对ECC的攻击需要巨大的计算量。2002年,Monico在攻击ECCp-109中利用了100多台计算机,耗时549天;2004年,Monico在攻击EC2109中利用了2600台计算机,耗时17个月。目前ECC攻击的最新进展为Bos等学者在2009年解决了SEC2密码标准中的ECCp-112。
