ECDLP

ECC與RSA的比較 3.0(ECDSA) 10.7(ECDSA)

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 公開密鑰(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密鑰長度比
105121065:1
107681326:1
1010241607:1
10204821010:1
102100060035:1

RSA和ECC安全模長得比較
功能Security Builder 1.2BSAFE 3.0
163位ECC(ms)1,023位RSA(ms)
密鑰對生成3.84,708.3
簽名2.1(ECNRA)228.4
3.0(ECDSA)
認證9.9(ECNRA)12.7
10.7(ECDSA)
Diffie—Hellman密鑰交換7.31,654.0
RSA和ECC速度比較

相關詞條

相關搜尋

熱門詞條

聯絡我們