優(yōu)秀碩士論文參考橢圓曲線公鑰密碼體制(ECC)課件

1、橢圓曲線公鑰密碼體制橢圓曲線公鑰密碼體制(ECC)e_mail: yongzhe 電話：電話：關于橢圓曲線關于橢圓曲線橢圓曲線問題的研究有橢圓曲線問題的研究有150多年的歷史多年的歷史 1985年年 Washington 大學的大學的Neal Koblitz IBM 的的Victor Miller 把橢圓曲線應用于密碼領域把橢圓曲線應用于密碼領域目前，橢圓曲線和目前，橢圓曲線和RSA算法是使用最廣泛的公鑰加算法是使用最廣泛的公鑰加密算法密算法實數域上的橢圓曲線實數域上的橢圓曲線 橢圓曲線并非橢圓，之所以稱為橢圓曲線是因為橢圓曲線并非橢圓，之所以稱為橢圓曲線是因為它的曲線方程與計算橢圓周長的方程

2、類似。一般它的曲線方程與計算橢圓周長的方程類似。一般來講，橢圓曲線的曲線方程是以下形式的三次方來講，橢圓曲線的曲線方程是以下形式的三次方程：程： y2+axy+by=x3+cx2+dx+e 其中其中a，b，c，d，e是滿足某些簡單條件的實數是滿足某些簡單條件的實數。典型橢圓曲線典型橢圓曲線E : Y2 = X3 5X + 8- 4 -特點特點: 可以應用幾何學使橢圓曲線上的點形成一個群. 橢圓曲線的加法橢圓曲線的加法依據：依據： 如果在橢圓曲線上有三個點存在于一條直線上，則如果在橢圓曲線上有三個點存在于一條直線上，則它們的和為無窮遠點它們的和為無窮遠點。其中無窮遠點記為其中無窮遠點記為 點點P

3、和點和點-P相加相加垂直直線沒有第三個交點垂直直線沒有第三個交點Q在無限遠處增加點在無限遠處增加點 O點點 O位于位于每個垂線上位于位于每個垂線上OPQ = P點點P和點和點-P相加的和為無窮遠點相加的和為無窮遠點點點P和點和點Q相加相加PQP+QR設連接點設連接點P和和Q的直線，交橢圓曲線于點的直線，交橢圓曲線于點R, 則點則點P和和Q的和為點的和為點-R求點求點P的二倍的二倍P2*PR過過P點作切線點作切線通過點通過點P作曲線的切線，交曲線于另一點作曲線的切線，交曲線于另一點R, 則則2P=-R求點求點P的二倍的特例的二倍的特例P若點若點P的切線的斜率是的切線的斜率是0，則，則2P=O,

4、3P=P,4P=O,5P=P有限域上的橢圓曲線有限域上的橢圓曲線 定義：定義：對于曲線對于曲線 y2 = x3 + ax + b(mod p)，a,ba,b為小于為小于p p的整數的整數當當4a3 + 27b2(mod p)不為零時構成有限域不為零時構成有限域Fp上上的橢圓曲線群。記為的橢圓曲線群。記為Ep(a,b)有限域上的橢圓曲線的點的構造有限域上的橢圓曲線的點的構造 1.1.對于每一個對于每一個x (0=x 3 q = p 3y y2 2 + xy = x + xy = x3 3 + ax + ax2 2 + b + b 對于對于 q = 2 q = 2m m 1 1基點基點 G = (

5、x G = (xG G,y,yG G) ) G G的階的階n n h = #E/n. h = #E/n. （#E #E 為橢圓曲線的階）為橢圓曲線的階）橢圓曲線的密鑰的生成橢圓曲線的密鑰的生成已知參數已知參數T: (q, a, b, G, n, h) ,橢圓曲線的公鑰橢圓曲線的公鑰 Q = (xQ,yQ)是這樣生成的是這樣生成的:在區(qū)間在區(qū)間 1,n-1選擇一個隨機數或偽隨機數選擇一個隨機數或偽隨機數d. 計算計算 Q = dG. Q為公鑰為公鑰; d為私鑰為私鑰. 橢圓曲線密鑰對的驗證橢圓曲線密鑰對的驗證 已知公鑰已知公鑰Q = (xQ,yQ) 和參數和參數T:(q, a, b, G, n,

6、 h) 按照如下步驟檢查公鑰的有效性按照如下步驟檢查公鑰的有效性檢查檢查 Q O 檢查檢查xQ 和和 yQ 是否屬于是否屬于GF(q). 檢查檢查Q 是否位于橢圓曲線上是否位于橢圓曲線上 檢查檢查 nQ = O. 密鑰長度比較密鑰長度比較安全級別安全級別對稱密碼對稱密碼ECC(n)DSA/RSA(模）模） 56561125128080160102411211222420481281282563072192192384768025625651215360具有具有128位安全強度的實例：位安全強度的實例：secp256k1T = (p;a;b;G;n;h) :p = FFFFFFFF FFFFFF

7、FF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2256 -232-29-28-27-26-24-1a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000b = 00000 00000 00000 00000G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A

8、8 FD17B448 A6855419 9C47D08F FB10D4B8n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141h = 01具有具有128位安全強度的實例：位安全強度的實例： sect283k1T = (m; f (x);a;b;G;n;h):m=283 f (x) = x283+x12 +x7+x5+1a = 00000 00 00000 00000b = 00000 00 00000 00000G = 04 0503213F 78CA4488 3F1A3B81 62F188E5

9、53CD265F 23C1567A 16876913 B0C2AC24 58492836 01CCDA38 0F1C9E31 8D90F95D 07E5426F E87E45C0 E8184698 E4596236 4E341161 77DD2259n = 01FFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFE9AE 2ED07577 265DFF7F 94451E06 1E163C61h = 04公鑰密碼系統中公鑰密碼系統中ECC與與RSA的對比的對比 RSA算法的特點之一是數學原理簡單、在工程應用算法的特點之一是數學原理簡單、在工程應用中比較易于實現，但它的單位安全強度相對較低。中比較易于實現，但它的單位安全強度相對較低。一般數域篩一般數域篩( (NFS) )方法去破譯和攻擊方法去破譯和攻擊RSA算法，它算法，它的破譯或求解難度是亞指數級的。的破譯或求解難度是亞指數級的。 ECC算法的數學理論非常深奧和復雜，在工程應用算法的數學理論非常深奧和復雜，在工程應用中比較難于實現，但它的單位安全強度相對較高。中比較難于實現，但它的單位安全強度相對較高。Pollard rho方法去破譯和攻擊方法去破譯和攻擊ECC算法，它的破譯算法，它的破譯或求解難度基本上是指數級的?；蚯蠼怆y度基本上是指數級的。 公鑰密碼現狀公鑰