ECDLP即椭圆曲线上的离散对数问题。1987年，Koblitz利用椭圆曲线上点形成的Abelian加法群构造了ECDLP。实验证明，在椭圆曲线加密算法中采用160bits的密钥可与1024bits密钥的RSA算法的安全性相当，且随着模数的增大，它们之间安全性的差距猛烈增大。因此，它可以提供一个更快、具有更小的密钥长度的公开密钥密码系统，备受人们的广泛关注，为人们提供了诸如实现数据加密、密钥交换、数字签名等密码方案的有力工具。

ECC

在1976年，由于对称加密算法已经不能满足需要，Diffie 和Hellman发表了一篇叫《密码学新动向》的文章，介绍了公匙加密的概念，由Rivet、Shamir、Adelman提出了RSA算法。

随着分解大整数方法的进步及完善、计算机速度的提高以及计算机网络的发展，为了保障数据的安全，RSA的密钥需要不断增加，但是，密钥长度的增加导致了其加解密的速度大为降低，硬件实现也变得越来越难以忍受，这对使用RSA的应用带来了很重的负担，因此需要一种新的算法来代替RSA。

1985年N.Koblitz和Miller提出将椭圆曲线用于密码算法，根据是有限域上的椭圆曲线上的点群中的离散对数问题ECDLP。ECDLP是比因子分解问题更难的问题，它是指数级的难度。

原理——椭圆曲线上的难题

椭圆曲线上离散对数问题ECDLP定义如下：给定素数p和椭圆曲线E，对Q＝kP，在已知P，Q 的情况下求出小于p的正整数k。可以证明由k和P计算Q比较容易，而由Q和P计算k则比较困难。

将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，将椭圆曲线中的乘法运算与离散对数中的模幂运算相对应，我们就可以建立基于椭圆曲线的对应的密码体制。

例如，对应Diffie-Hellman公钥系统，我们可以通过如下方式在椭圆曲线上予以实现：在E上选取生成元P，要求由P产生的群元素足够多，通信双方A和B分别选取a和b，a和b 予以保密，但将aP和bP公开，A和B间通信用的密钥为abP，这是第三者无法得知的。

对应ELGamal密码系统可以采用如下的方式在椭圆曲线上予以实现：

将明文m嵌入到E上Pm点，选一点B∈E，每一用户都选一整数a，0＜a＜N，N为阶数已知，a保密，aB公开。欲向A送m，可送去下面一对数偶：［kB，Pm+k(aAB)］，k是随机产生的整数。A可以从kB求得k(aAB)。通过：Pm+k(aAB)- k(aAB)=Pm恢复Pm。同样对应DSA，考虑如下等式：

K=kG [其中 K，G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数]

不难发现，给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难了。

这就是椭圆曲线加密算法采用的难题。我们把点G称为基点（base point），k（k<n，n为基点G的阶）称为私有密钥（privte key），K称为公开密钥（public key)。

ECC与RSA的比较

ECC和RSA相比，在许多方面都有对绝对的优势，主要体现在以下方面：

抗攻击性强。相同的密钥长度，其抗攻击性要强很多倍。

计算量小，处理速度快。ECC总的速度比RSA、DSA要快得多。

存储空间占用小。ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多，意味着它所占的存贮空间要小得多。这对于加密算法在IC卡上的应用具有特别重要的意义。

带宽要求低。当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消息时ECC带宽要求却低得多。带宽要求低使ECC在无线网络领域具有广泛的应用前景。

ECC的这些特点使它必将取代RSA，成为通用的公钥加密算法。比如SET协议的制定者已把它作为下一代SET协议中缺省的公钥密码算法。

下面两张表示是RSA和ECC的安全性和速度的比较。

攻破时间(MIPS年)　RSA/DSA(密钥长度)　ECC密钥长度　RSA/ECC密钥长度比

10　512　106　5：1

10　768　132　6：1

10　1024　160　7：1

10　2048　210　10：1

10　21000　600　35：1

RSA和ECC安全模长得比较

功能　Security Builder 1.2　BSAFE 3.0

163位ECC(ms)　1,023位RSA(ms)

密钥对生成　3.8　4,708.3

签名　2.1(ECNRA)　228.4

3.0(ECDSA)

认证　9.9(ECNRA)　12.7

10.7(ECDSA)

Diffie—Hellman密钥交换　7.3　1,654.0RSA和ECC速度比较