第3講公鑰密碼學(xué)

1、網(wǎng)絡(luò)與信息安全技術(shù)網(wǎng)絡(luò)與信息安全技術(shù)第三講第三講公鑰密碼公鑰密碼華中科技大學(xué)軟件工程碩士課程華中科技大學(xué)軟件工程碩士課程公鑰密碼學(xué)的歷史 76年Diffie和Hellman發(fā)表了“密碼學(xué)的新方向”, 奠定了公鑰密碼學(xué)的基礎(chǔ) 公鑰技術(shù)是二十世紀(jì)最偉大的思想之一 改變了密鑰分發(fā)的方式廣泛用于數(shù)字簽名和身份認(rèn)證服務(wù) 78年, RSA算法對(duì)稱算法的不足 密鑰管理量的困難！ 傳統(tǒng)密鑰管理: 兩兩分別用一個(gè)密鑰時(shí), 則n個(gè)用戶需要C(n,2)=n(n-1)/2個(gè)密鑰, 當(dāng)用戶量增大時(shí),密鑰空間急劇增大, 如: n=100 時(shí), C(100,2)=4,995 n=5000時(shí), C(5000,2)=12,49

2、7,500 對(duì)傳輸信道安全性的要求！ 密鑰必須通過某一信道協(xié)商傳輸，對(duì)這個(gè)信道的安全性的要求比正常的傳送消息的信道的安全性要高 數(shù)字簽名問題！ 傳統(tǒng)加密算法無法實(shí)現(xiàn)抗抵賴的需求公鑰體制加密的框圖公鑰體制認(rèn)證的框圖公鑰體制認(rèn)證保密的框圖公鑰密碼基于的數(shù)學(xué)難題 背包問題 大整數(shù)分解問題 ( RSA體制 ) 離散對(duì)數(shù)問題 有限域的乘法群上的離散對(duì)數(shù)問題 (ElGamal體制) 定義在有限域的橢圓曲線上的離散對(duì)數(shù)問題 (類比的ElGamal體制)公鑰密碼主要算法 Diffie-Hellman密鑰交換算法 背包算法 RSA算法 EIGamal算法 橢圓曲線密碼算法ECCDiffie-Hellman密鑰交

3、換RSA算法 1977年由Ron Rivest、Adi Shamir和Len Adleman發(fā)明, 1978年公布; 是一種分組加密算法; 明文和密文在0n-1之間, n是一個(gè)正整數(shù) 應(yīng)用最廣泛的公鑰密碼算法; 只在美國(guó)申請(qǐng)專利, 且已于2000年9月到期; RSA算法RSA密鑰生成與使用 產(chǎn)生密鑰對(duì) 選擇兩個(gè)大素?cái)?shù)p,q, pq 計(jì)算n=pq,(n)=(p-1)(q-1) 選擇整數(shù)e,使得gcd(e,(n)=1 計(jì)算d e-1 mod (n) 公鑰: KU=e,n, 私鑰: KR=d,n 使用: 將明文劃分成塊, 使得每個(gè)明文報(bào)文P長(zhǎng)度m滿足0mn 加密: C = me mod n 解密:

4、m = Cd mod nRSA算法中的計(jì)算問題 如何計(jì)算ab mod n 密鑰產(chǎn)生 如何計(jì)算ab mod n 中間結(jié)果非常大 6677 mod 119, 先求6677再取模, 則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)允許的整數(shù)取值范圍 (a x b) mod n = (a mod n) x (b mod n) mod n 冪運(yùn)算的效率 求x16, 直接計(jì)算的話需做15次乘法. 然而如果重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求x, x2, x4, x8, x16則只需4次乘法。求am可如下進(jìn)行, 其中a，m是正整數(shù)： 將m表示為二進(jìn)制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此120

5、12222kkkbbbbbmaaaaaa 例: 19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1)2a1從而可得以下快速指數(shù)算法：c=0; d=1；for i=k downto 0 d0 c=2c;d=(dd) mod n; if bi=1 then c=c+1;d=(da) mod nreturn d. d是中間結(jié)果, d的終值即為所求結(jié)果. c在這里的作用是表示指數(shù)的部分結(jié)果, 其終值即為指數(shù)m c對(duì)計(jì)算結(jié)果無任何貢獻(xiàn), 算法中完全可將之去掉密鑰產(chǎn)生 如何找到足夠大的素?cái)?shù)p和q? 選擇e或d計(jì)算另外一個(gè)?選取滿足1e(n)和gcd(n),e)=1的e

6、, 并計(jì)算滿足de1 mod (n)的d, 可由推廣的Euclid算法完成.大素?cái)?shù)產(chǎn)生 素?cái)?shù)生成過程: 隨機(jī)選擇一個(gè)奇數(shù)n(如通過偽隨機(jī)數(shù)發(fā)生器) 隨機(jī)選擇a, 使ad Euclid（f, d） 1. Xf; Yd； 2. if Y=0 then return X=gcd(f,d)； 3. R=X mod Y； 4. X=Y； 5. Y=R； 6. goto 2。例4.2 求gcd(1970, 1066)。1970=11066+904,gcd(1066, 904)1066=1904+162,gcd(904, 162)904=5162+94,gcd(162, 94) 162=194+68,gcd

7、(94, 68) 94=168+26,gcd(68, 26)68=226+16,gcd(26, 16) 26=116+10,gcd(16, 10) 16=110+6,gcd(10, 6) 10=16+4,gcd(6, 4)6=14+2,gcd(4, 2) 4=22+0,gcd(2, 0)因此gcd(1970, 1066)=2。擴(kuò)展Euclid算法 ExtEclid(d,f):求最大公約數(shù)或模逆, 假定df (X1,X2,X3)(1,0,f), (Y1,Y2,Y3)(0,1,d) if Y3 = 0 then return X3, no inverse if Y3 = 1 then return

8、 1, inverse is Y2 Q (X3/Y3)的整數(shù)部分 (Y1,Y2,Y3)(X1-QY1, X2-QY2, X3-QY3) (X1,X2,X3) (Y1,Y2,Y3) goto fX1+dX2=X3, fY1+dY2=Y3 若Y3=1,則 fY1+dY2=1 dY2=(-Y1)f+1 dY2 1 mod f Y2 = d-1 mod f例 求gcd(1769, 550)。所以gcd(1769,550)=1，550-1 mod 1769=550。循環(huán)次數(shù)QX1X2X3Y1Y2Y3初值-1017690155013015501-3119241-3119-4137431-413745-16

9、45415-1645-9292951-9292914-45166114-4516-23741371-23741337-11938437-1193-1715501 橢圓曲線密碼體制ECCy2=x3+ax+b mod p 橢圓曲線(con.)引進(jìn)一個(gè)0元素, 并定義如下的加法運(yùn)算: 引進(jìn)一個(gè)無窮點(diǎn)0(, )作為0元素 任何解點(diǎn)R(x,y)的逆就是R(x,-y) 設(shè)P(x1,y1)和Q(x2,y2)是橢圓曲線上的兩個(gè)點(diǎn),則連接P(x1,y1)和Q(x2,y2)的直線與橢圓曲線的另一交點(diǎn)關(guān)于橫軸的對(duì)稱點(diǎn)即為 P(x1,y1)+Q(x2,y2)點(diǎn)橢圓曲線上的離散對(duì)數(shù)問題 橢圓曲線群上的離散對(duì)數(shù)問題 考慮等式Q=kP，其中Q、P屬于Ep(a,b)，kp 已知k和P，計(jì)算Q，是容易的 已知Q和P，計(jì)算k，是困難的橢圓曲線密碼體制的優(yōu)點(diǎn) 安全性高 運(yùn)算復(fù)雜度更高, 因此橢圓曲線密碼體制比基于有限域上的離散對(duì)數(shù)問題的公鑰體制更安全. 密鑰量小 在實(shí)現(xiàn)相同的安全性能條件下,ECC所需的密鑰量遠(yuǎn)比基于有限域上