ECDLP

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

ECDLP介绍

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

ECDLP问题概述

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原理

椭圆曲线上离散对数问题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，可送去下面一对数偶：，k是随机产生的整数。A可以从kB求得k(aAB)。通过：Pm+k(aAB)- k(aAB)=Pm恢复Pm。同样对应DSA，考虑如下等式：

K=kG

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

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

ECDLP相关比较

ECC与RSA的比较

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

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

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

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

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

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

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

RSA和ECC安全模长得比较

RSA和ECC速度比较