基本介紹
問題概述,原理,相關比較,
問題概述
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就相對困難了。
相關比較
ECC與RSA的比較
ECC和RSA相比，在許多方面都有對絕對的優勢，主要體現在以下方面：
抗攻擊性強。相同的密鑰長度，其抗攻擊性要強很多倍。
計算量小，處理速度快。ECC總的速度比RSA、DSA要快得多。
下面兩張表示是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.0 |
RSA和ECC速度比較
