ECDLP

ECDLP即橢圓曲線上的離散對數問題。1987年，Koblitz利用橢圓曲線上點形成的Abelian加法羣構造了ECDLP。實驗證明，在橢圓曲線加密算法中採用160bits的密鑰可與1024bits密鑰的RSA算法的安全性相當，且隨着模數的增大，它們之間安全性的差距猛烈增大。因此，它可以提供一個更快、具有更小的密鑰長度的公開密鑰密碼系統，備受人們的廣泛關注，為人們提供了諸如實現數據加密、密鑰交換、數字簽名等密碼方案的有力工具。

在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、DSA要快得多。

存儲空間佔用小。ECC的密鑰尺寸和系統參數與RSA、DSA相比要小得多，意味着它所佔的存貯空間要小得多。這對於加密算法在IC卡上的應用具有特別重要的意義。

帶寬要求低。當對長消息進行加解密時，三類密碼系統有相同的帶寬要求，但應用於短消息時ECC帶寬要求卻低得多。帶寬要求低使ECC在無線網絡領域具有廣泛的應用前景。

ECC的這些特點使它必將取代RSA，成為通用的公鑰加密算法。比如SET協議的制定者已把它作為下一代SET協議中缺省的公鑰密碼算法。

下面兩張表示是RSA和ECC的安全性和速度的比較。

RSA和ECC安全模長得比較

RSA和ECC速度比較