公鑰密碼技術(shù)理論及應(yīng)用介紹

1、第三章 公鑰密碼技術(shù) 第三章 公鑰密碼技術(shù) 1公鑰密碼的概念 公鑰密碼學(xué)的理論基礎(chǔ) 公鑰密碼算法 密鑰交換 公鑰密碼算法的應(yīng)用 提出公鑰密碼的動(dòng)因密鑰分配問題。使用對(duì)稱加密算法的通信雙方要進(jìn)行加密通信時(shí)，需要通過秘密的安全信道協(xié)商加密密鑰，而這種安全信道如何實(shí)現(xiàn)呢？機(jī)械階段 數(shù)字簽名問題。信息的電子化對(duì)密碼學(xué)提出了新的要求：電子報(bào)文和電子文件需要一種與書面材料中使用的簽名等效的認(rèn)證手段。 公鑰密碼的初始化階段加密通信階段公鑰密碼的概念 公鑰密碼學(xué)的理論基礎(chǔ) 公鑰密碼算法 密鑰交換 公鑰密碼算法的應(yīng)用 第三章 公鑰密碼技術(shù) 2計(jì)算復(fù)雜度與公鑰密碼計(jì)算復(fù)雜度 P問題和NP完全問題 密碼與計(jì)算復(fù)雜度

2、的關(guān)系 單向陷門函數(shù)單向陷門函數(shù)的數(shù)學(xué)問題分解整數(shù)問題。離散對(duì)數(shù)問題。 RSA問題。 公鑰密碼的概念 公鑰密碼學(xué)的理論基礎(chǔ) 公鑰密碼算法 密鑰交換 公鑰密碼算法的應(yīng)用 第三章 公鑰密碼技術(shù) 3公開密鑰算法公鑰算法的種類很多，具有代表性的三種密碼： 基于離散對(duì)數(shù)難題（DLP）的算法體制，例如Diffie-Hellman 密鑰交換算法； 基于整數(shù)分解難題（IFP）的算法體制，例如RSA算法； 基于橢圓曲線離散對(duì)數(shù)難題（ECDLP）的算法體制；RSA算法麻省理工學(xué)院的Ron Rivest, Adi Shamir和Len Adleman于1977年研制，并于1978年首次發(fā)表；RSA是一種分組密碼，其

3、理論基礎(chǔ)是一種特殊的可逆模冪運(yùn)算，其安全性基于分解大整數(shù)的困難性；既可用于加密，又可用于數(shù)字簽名，已得到廣泛采用；RSA已被許多標(biāo)準(zhǔn)化組織(如ISO、ITU、IETF和SWIFT等)接納；RSA-155(512 bit), RSA-140于1999年分別被分解；Euler 函數(shù) 歐拉函數(shù) (Eulers totient function)，記為(n)，表示小于n而且與n互素的正整數(shù)個(gè)數(shù)； 對(duì)于任一素?cái)?shù)p，(p)=p-1; 對(duì)于兩個(gè)不同的素?cái)?shù)p和q，若n=pq， 則(n)= (pq) (p)(q)(p-1)(q-1)；Euler 函數(shù)舉例 設(shè)p=3, q=5, 那么 n=pq=15；1）小于15

4、而且與15互素的正整數(shù)是： 1，2，4，7，8，11，13，14 因此， （15）8；2）（15）=（3-1）*（5-1）=8歐拉定理 對(duì)于任何互素的整數(shù)a和n， (mod n)，或者寫作 a(mod n) 給定兩個(gè)素?cái)?shù)p和q，以及整數(shù)n=pq，和m，其中0mn，則 mod n mod nRSA算法的描述對(duì)于明文分組M和密文分組C，加密解密形式分別為：C = Me mod nM = Cd mod n = (Me)d mod n = Med mod n因此，公鑰 KU=e,n,私鑰 KR=d,n,公鑰算法必須滿足: 1）有可能找到e、d、n的值，使得對(duì)所有Mn有Med =M mod n；2）對(duì)于

5、所有Mn，要計(jì)算Me和Cd相對(duì)簡單；3）給定e和n時(shí)，判斷出d是不可行的；RSA算法的描述如何找到：？參考?xì)W拉定理可以得到：ed= k(n)+1也就是說：RSA算法的實(shí)現(xiàn)實(shí)現(xiàn)的步驟如下：Bob為實(shí)現(xiàn)者 (1) Bob尋找出兩個(gè)大素?cái)?shù)p和q (2) Bob計(jì)算出n=pq 和(n)=(p-1)(q-1) (3) Bob選擇一個(gè)隨機(jī)數(shù)e (0e (n)，滿足(e,(n)=1 (4) Bob使用輾轉(zhuǎn)相除法計(jì)算d=e-1mod(n) (5) Bob在目錄中公開n和e作為公鑰密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于如何分解n。若分解成功使n=pq，則可以算出(n)（p-1)(q-1)，然后由公開的e，解出秘密

6、的dRSA算法舉例設(shè) p=7, q=17, n=7*17=119; 參數(shù)T=n=119;(n)=(7-1)(17-1)=96;選擇e=5, gcd(5,96)=1; 計(jì)算d, d*e =1 mod 96; d=77; 因?yàn)?753854961設(shè):明文m=19 加密：（19）5 mod 119 = 66 解密：（66）77 mod 119 = 19RSA算法的安全性分析密碼分析者攻擊RSA體制的關(guān)鍵在于分解n,若分解成功使n=pq，則可以算出(n)（p-1)(q-1)，然后由公開的e，解出秘密的d;若使RSA安全，p與q必為足夠大的素?cái)?shù)，使分析者沒有辦法在多項(xiàng)式時(shí)間內(nèi)將n分解出來,建議選擇p和q

7、大約是100位的十進(jìn)制素?cái)?shù),模n的長度要求至少是512比特;RSA算法的安全性分析EDI攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長度為512至1024比特位之間，但必須是128的倍數(shù);國際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC 9796中規(guī)定n的長度位512比特位;為了提高加密速度，通常取e為特定的小整數(shù),如EDI國際標(biāo)準(zhǔn)中規(guī)定 e2161;ISO/IEC9796中甚至允許取e3;這時(shí)加密速度一般比解密速度快10倍以上;RSA算法的安全性分析 為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)RSA模n的素因子p和q還有如下要求： (1) |p-q|很大，通常 p和q的長度相同； (2) p-1 和q-1分別含有大素因子p1和q1

8、； (3) P1-1和q1-1分別含有大素因子p2和q2； (4) p+1和q+1分別含有大素因子p3和q3；橢圓曲線密碼編碼學(xué)ECC1985年Miller,Koblitz 獨(dú)立提出y2+axy+by=x3+cx2+dx+e表示曲線上的點(diǎn)連同無窮遠(yuǎn)點(diǎn)O的集合加法:若曲線三點(diǎn)在一條直線上,則其和為O；倍數(shù):一個(gè)點(diǎn)的兩倍是它的切線與曲線的另一個(gè)交點(diǎn)；橢圓曲線上的加法規(guī)則 加法公式:O 作為加法的單元，O=-O，P+O=P如果P=(x,y)，則P+(x,-y)=O，(x,-y)點(diǎn)是P的負(fù)點(diǎn)，記為-P,而且(x,-y)也在EP(a,b)中如果P=(x1,y1)，Q=(x2,y2)，則 P+Q=(x3,

9、y3)為x3=2-x1-x2 (mod p)y3=(x1-x3)-y1 (mod p)其中，如果PQ，則 = (y2-y1)/(x2-x1) 如果P=Q，則 = (3x12+a)/(2y1)橢圓曲線示例橢圓曲線上的加法: P + Q = -R 橢圓曲線上一點(diǎn)的2倍: Q+Q=-S 有限域上的橢圓曲線有限域上的橢圓曲線定義如下：y2x3+ax+b (mod p) p是素?cái)?shù),a,b為非負(fù)整數(shù)，且滿足4a3+27b2 (mod p) 0 針對(duì)所有的0= x p，可以求出有效的y，得到曲線上的點(diǎn) (x,y)，其中x,y p。曲線記為EP(a,b),EP(a,b)中也包括O點(diǎn)例如，令P=23，a=b=1

10、，橢圓曲線為y2x3+x+1，4132712(mod 23)=8 0滿足模23橢圓群的條件橢圓曲線上的密鑰交換1）雙方選擇EP(a,b)以及EP(a,b)的一個(gè)元素G,使得nG=0的最小n值是一個(gè)非常大的素?cái)?shù)；2）A選擇私鑰Xn,計(jì)算公鑰PA=XG；3）B選擇私鑰Yn,計(jì)算公鑰PB=YG； 4）A計(jì)算秘密密鑰:K=X(PB)=XYG5）B計(jì)算秘密密鑰:K=Y(PA)=YXG=XYG因此，雙方獲得了一個(gè)共享會(huì)話密鑰(XYG)橢圓曲線上的密鑰交換攻擊雙方選擇EP(a,b)以及EP(a,b)的一個(gè)元素G,使得G的階n是一個(gè)大素?cái)?shù)A選擇私鑰Xn,計(jì)算公鑰PA=XG, AB: PAE截獲PA,選私鑰Z,

11、計(jì)算PE=ZG,冒充AB:PEB選擇私鑰Yn,計(jì)算公鑰PB=YG, BA: PBE截獲PB,冒充BA: PEA計(jì)算: XPE = XZGB計(jì)算: YPE = YZGE計(jì)算: ZPA=ZXG, ZPB =ZYGE無法計(jì)算出XYGE永遠(yuǎn)必須實(shí)時(shí)截獲并冒充轉(zhuǎn)發(fā),否則會(huì)被發(fā)現(xiàn).橢圓曲線加密/解密1）雙方選擇橢圓群EP(a,b)以及EP(a,b)的一個(gè)元素G,使得nG=0的最小n值是一個(gè)非常大的素?cái)?shù)；2）A選擇私鑰Xn,計(jì)算公鑰PA=XG；3）B選擇私鑰Yn,計(jì)算公鑰PB=YG； 4）A若想加密和發(fā)送報(bào)文Pm給B，選擇隨機(jī)數(shù)k，并產(chǎn)生一對(duì)點(diǎn)組成的密文Cm=kG,Pm+kPB；5）B解密密文， Pm+kP

12、B-YkG Pm+kYG- YkG= Pm除了A，無人知道k，因此無法破譯兩類加密算法比較公鑰密碼的概念 公鑰密碼學(xué)的理論基礎(chǔ) 公鑰密碼算法 密鑰交換 公鑰密碼算法的應(yīng)用 第三章 公鑰密碼技術(shù) 4Diffie-Hellman密鑰交換算法若用戶A和用戶B希望交換一個(gè)密鑰，如何進(jìn)行？1）全局公開參數(shù)：一個(gè)素?cái)?shù)q和其一個(gè)原根a；2）用戶A選擇一個(gè)隨機(jī)數(shù)XAq，計(jì)算YA=aXA mod q，YA公開；3）用戶B選擇一個(gè)隨機(jī)數(shù)XBq，計(jì)算YB=aXB mod q ，YB公開；4）用戶A計(jì)算密鑰K=(YB)XAmod q;5）用戶B計(jì)算密鑰K=(YA)XBmod q;Diffie-Hellman密鑰交換算

13、法證明：K = (YB)XA mod q = (aXB mod q)XA mod q =(aXB)XA mod q =a XBXA mod q =(aXA)XB mod q =(aXA mod q)XB mod q =(YA)XB mod q攻擊分析：公開數(shù)據(jù) q，a，YA和YB，若想攻擊用戶B的秘密密鑰，攻擊者必須計(jì)算 XB = inda,q(YB)；安全性分析：計(jì)算模一個(gè)素?cái)?shù)的指數(shù)相對(duì)容易，計(jì)算離散對(duì)數(shù)卻很難；Diffie-Hellman密鑰交換算法舉例1）密鑰交換基于素?cái)?shù)q=97和q的一個(gè)原根a=5；2）A和B分別選擇密鑰 XA=36和XB=58，并分別計(jì)算其公開密鑰YA = 536= 50 mod 97YB = 558= 44 mod 973）交換了公開密鑰后，每人計(jì)算共享的秘密密鑰如下K=