椭圆曲线密码体制的安全性分析

1.椭圆曲线密码体制的优点

目前，椭圆曲线密码体制在理论上和实践上都取得了很大的进展，椭圆曲线密码体制是代替RSA公钥密码体制最强有力的竞争者。椭圆曲线算法与RSA算法相比，有以下优点：

1）安全性能更高，如160比特ECC与1024比特RSA有相同的安全强度。

2）计算量小，处理速度快，在私钥的处理速度上（解密和签名），ECC远比RSA快得多。

3）存储空间占用小，ECC的密钥尺寸和系统参数与RSA相比要小得多，所以占用的存储空间小得多。

4）带宽要求低，这使得ECC具有广泛的应用前景。(www.xing528.com)

2.对椭圆曲线密码体制的攻击

随着椭圆曲线密码体制的广泛应用，它的安全性分析引起了密码学界的高度重视，ECC算法是基于椭圆曲线上离散对数计算问题的。一般认为，当p的长度为160bit时，p元域上的椭圆曲线密码体制其安全性相当于RSA密码体制使用1024bit的模数。

使用椭圆曲线作为公钥密码体制的基础是，定义在有限域GF（p）上的椭圆曲线的点集可以构成阿贝尔群，由此可定义椭圆曲线上的离散对数。一个椭圆曲线E_p（a，b）上的离散对数问题就是寻找一个k∈GF（p），当P、Q∈E_p（a，b）时，有Q=kP。椭圆曲线离散对数问题比大整数因子分解问题和一般有限域上的离散对数问题更难，因而构建一个基于椭圆曲线离散对数问题上的公钥密码体制也就更安全。

对于一般群的离散对数问题，当该群的阶较小时，有许多算法可以对其求解。目前，有两种比较有效的解决离散对数问题的算法，即Shanks的Baby-step Giant-step算法和任意循环群上的指数计算法。Baby-step Giant-step算法为完全指数时间，仅当椭圆曲线上的点加群的阶不含有大素数因子时才是有效的，并且指数计算法也不能有效地用来攻击椭圆曲线密码体制。目前，相对来说最好的求解椭圆曲线离散对数问题的算法是Pollard ρ法和Pohlig-Hell-man法，但是当椭圆曲线上的阶含有较大素数因子时，这两种方法也是无效的。1993年，Menezes、Okamoto和Vanstone发现了一种新的解决椭圆曲线离散对数问题的方法，即MOV归约法。

对于定义在GF（p）上的椭圆曲线E_p（a，b），MOV归约法利用Weil理论对将椭圆曲线嵌入到某个扩域GF（k，p）上的乘法群中，将椭圆曲线离散对数问题归约为乘法群上的离散对数问题。然而，为了这种方法适用于任何场合，扩度k必须很小。当k很小时，椭圆曲线都是超奇异的。然而，大量的椭圆曲线是非超奇异的。对于这样的非超奇异椭圆曲线，使用MOV归约法后也没有亚指数时间的有效算法。为了安全起见，适于构建密码体制的椭圆曲线应当满足k≥B的条件，这里的B是某个比扩度k还小的下界。所以，高安全性的椭圆曲线密码体制可以靠选择能够防止MOV归约法攻击的椭圆曲线来获得。