公鑰密碼體制

1、 1公鑰密碼學(xué)公鑰密碼學(xué) 2公鑰密碼學(xué)公鑰密碼學(xué)l公鑰密碼學(xué)思想lRSA算法l公鑰的應(yīng)用 3公鑰密碼學(xué)的發(fā)展是整個(gè)密碼學(xué)發(fā)公鑰密碼學(xué)的發(fā)展是整個(gè)密碼學(xué)發(fā)展歷史中最偉大的一次革命。展歷史中最偉大的一次革命。公鑰密碼體制公鑰密碼體制公鑰算法基于數(shù)學(xué)函數(shù)而不是基于替換和置換公鑰算法基于數(shù)學(xué)函數(shù)而不是基于替換和置換它使用兩個(gè)獨(dú)立的密鑰，在消息的保密性、它使用兩個(gè)獨(dú)立的密鑰，在消息的保密性、密鑰分配和認(rèn)證領(lǐng)域有重要意義。密鑰分配和認(rèn)證領(lǐng)域有重要意義。 4密鑰分配問題：如果密鑰被偷，設(shè)計(jì)再好的密鑰分配問題：如果密鑰被偷，設(shè)計(jì)再好的密碼體制都沒有用密碼體制都沒有用傳統(tǒng)密碼中的兩個(gè)問題傳統(tǒng)密碼中的兩個(gè)問題數(shù)字

2、簽名問題：能否設(shè)計(jì)一種方法確保數(shù)字?jǐn)?shù)字簽名問題：能否設(shè)計(jì)一種方法確保數(shù)字簽名出自某個(gè)特定的人，并且各方無異議？簽名出自某個(gè)特定的人，并且各方無異議？ 51976年年 Diffie和和Hellman針對上述問題提出針對上述問題提出了一種方法，它是密碼學(xué)的一次革命了一種方法，它是密碼學(xué)的一次革命密碼學(xué)革命密碼學(xué)革命 6公鑰密碼體制介紹 7n是密碼學(xué)一次偉大的革命是密碼學(xué)一次偉大的革命n1976年，年，Diffie和和Hellman 在在“密碼學(xué)新方密碼學(xué)新方向向”一文中提出。一文中提出。n使用兩個(gè)密鑰：公開密鑰、私有密鑰使用兩個(gè)密鑰：公開密鑰、私有密鑰n加解密的非對稱性加解密的非對稱性n利用數(shù)論的

3、方法利用數(shù)論的方法n是對對稱密碼的重要補(bǔ)充是對對稱密碼的重要補(bǔ)充 8僅根據(jù)僅根據(jù)密碼算法密碼算法和和加密密鑰加密密鑰來確定來確定解密密鑰解密密鑰在在計(jì)算上是不可行的。計(jì)算上是不可行的。公鑰密碼體制特點(diǎn)公鑰密碼體制特點(diǎn)兩個(gè)密鑰中的任何一個(gè)可以用來加密，另一個(gè)兩個(gè)密鑰中的任何一個(gè)可以用來加密，另一個(gè)用來解密。用來解密。有有6個(gè)組成部分：明文、加密算法、公鑰、個(gè)組成部分：明文、加密算法、公鑰、私鑰、密文、解密算法私鑰、密文、解密算法 9用公鑰進(jìn)行加密用公鑰進(jìn)行加密2 Alice產(chǎn)生一對密鑰，用于加密和解密產(chǎn)生一對密鑰，用于加密和解密3 Alice將一個(gè)密鑰公開，另一個(gè)密鑰私有將一個(gè)密鑰公開，另一個(gè)密

4、鑰私有BobAlice1 Bob要發(fā)送消息給要發(fā)送消息給Alice4 Bob用用Alice的公鑰對消息加密，發(fā)送給的公鑰對消息加密，發(fā)送給Alice。只有。只有Alice能解密能解密 10用公鑰進(jìn)行認(rèn)證用公鑰進(jìn)行認(rèn)證BobAlice 11用公鑰進(jìn)行認(rèn)證用公鑰進(jìn)行認(rèn)證:問題？問題？問題問題1 需要對整條消息加密，占用大量存儲(chǔ)空間需要對整條消息加密，占用大量存儲(chǔ)空間解決的方法：僅對消息的認(rèn)證符加密解決的方法：僅對消息的認(rèn)證符加密問題問題2 不能提供保密性不能提供保密性如何解決？如何解決？ 12公鑰密碼體制的種類公鑰密碼體制的種類1 加密加密/解密解密2 數(shù)字簽名數(shù)字簽名3 密鑰交換密鑰交換算法算法

5、 RSA 橢圓曲線橢圓曲線 Diffie-Hellman DSS是是是是是是是是是是是是否否否否是是否否是是否否 13對公鑰密碼體制的要求：對公鑰密碼體制的要求：1 B產(chǎn)生一對密鑰（Kpb，Ksb）在計(jì)算上是容易的2 發(fā)送方A加密消息 C=EKpb(M) 在計(jì)算上是容易的3 接收方B對密文解密 M=DKsb(C) 在計(jì)算上是容易的4 攻擊者從Kpb計(jì)算出Ksb在計(jì)算上不可行的5 攻擊者從Kpb和C計(jì)算出M在計(jì)算上不可行的 14只有兩個(gè)算法被普遍接受只有兩個(gè)算法被普遍接受1 RSA2 橢圓曲線 就是要找一個(gè)單向陷門函數(shù)：不太容易所謂單向陷門函數(shù)是這樣的函數(shù)，即除非知道某種附所謂單向陷門函數(shù)是這樣

6、的函數(shù)，即除非知道某種附加的信息，否則這樣的函數(shù)在一個(gè)方向上容易計(jì)算，加的信息，否則這樣的函數(shù)在一個(gè)方向上容易計(jì)算，而在反方向上要計(jì)算是不可行的。而在反方向上要計(jì)算是不可行的。 15單向陷門函數(shù)（單向陷門函數(shù)（1）Y=fk(X) 容易(k 和X已知)X=fk-1(Y) 計(jì)算上不可行（k未知，Y已知）X=fk-1(Y) 容易（k已知，Y已知）尋找合適的單向陷門函數(shù)是公鑰密碼體制應(yīng)用的關(guān)鍵！ 16單向陷門函數(shù)（單向陷門函數(shù)（2）l困難程度困難程度l舉例舉例打碎打碎/拼接、平方拼接、平方/開方、乘法開方、乘法/分解分解* 單向函數(shù)存在否單向函數(shù)存在否尚無嚴(yán)格的數(shù)學(xué)證明尚無嚴(yán)格的數(shù)學(xué)證明 17單向陷門

7、函數(shù)（單向陷門函數(shù)（3）l單向陷門函數(shù)單向陷門函數(shù)如果知道某個(gè)陷門如果知道某個(gè)陷門(秘訣秘訣)，即能容易恢復(fù)，即能容易恢復(fù)x（陷門即為私鑰）（陷門即為私鑰）l舉例舉例魔方的置亂魔方的置亂/恢復(fù)恢復(fù)l如果有那個(gè)口訣，就能很快恢復(fù)如果有那個(gè)口訣，就能很快恢復(fù) 18RSA 算法算法l先從一個(gè)簡單例子開始先從一個(gè)簡單例子開始l給出算法給出算法l證明證明 19簡單例子簡單例子選中兩個(gè)素?cái)?shù) p7，q17 npq(n)請練習(xí)任務(wù)：對明文 M=19 加密 npq119(n)(p-1)(q-1)61696選取整數(shù)1e (n)與(n) 互素：e5求e的逆元d：ed1 mod (n) 請練習(xí)計(jì)算 C=Me(mod

8、n)=? 其中M=19 請練習(xí) 計(jì)算 M=Cd(mod n)=? 請練習(xí) d=77c=66 20RSA 示例總結(jié)示例總結(jié)l選p7，q17則npq119且(n)(p-1)(q-1)61696l取e5則d77 (57738549611 mod 96)l公鑰（5，119），私鑰（77，119） l加密m19則cme mod n= 195 mod 119 = 66 mod 119l解密c66mcd mod n = 6677mod 11919 mod 119 21 22RSA算法算法l作者作者1977年，年，R, S, AlRon RivestlAdi ShamirlLen Adleman l基本參數(shù)基

9、本參數(shù)分組密碼算法分組密碼算法基于整數(shù)乘法基于整數(shù)乘法明明/密文分組以及公密文分組以及公/私鑰被看作小于私鑰被看作小于n的整數(shù)的整數(shù)加加/解密是模乘運(yùn)算解密是模乘運(yùn)算 23RSA算法總結(jié)：密鑰產(chǎn)生算法總結(jié)：密鑰產(chǎn)生l找素?cái)?shù)找素?cái)?shù)選取兩個(gè)大的隨機(jī)的素?cái)?shù)選取兩個(gè)大的隨機(jī)的素?cái)?shù)p，ql計(jì)算模計(jì)算模n和和Euler函數(shù)函數(shù)(n)npq(n)=(p-1)(q-1)l找找ed1 mod (n)隨機(jī)取一個(gè)數(shù)隨機(jī)取一個(gè)數(shù)e(與與(n)互素互素)，用擴(kuò)展，用擴(kuò)展Euclid算法求算法求d即可即可l發(fā)布發(fā)布d保密，保密，(d, n)是私鑰是私鑰 Ks發(fā)布發(fā)布(e,n)，這是公鑰，這是公鑰Kp銷毀銷毀p、q 24R

10、SA的正確性的正確性l加密加密明文分組明文分組m做為整數(shù)須小于做為整數(shù)須小于nc=me mod nl解密解密m=cd mod n 25RSA考慮考慮l素?cái)?shù)素?cái)?shù)必須夠大，否則對手可能很快分解必須夠大，否則對手可能很快分解n判定，采用判定，采用Miller-Rabin概率測試方法概率測試方法l假素?cái)?shù)意味著加解密不能正確進(jìn)行，故可放棄之假素?cái)?shù)意味著加解密不能正確進(jìn)行，故可放棄之強(qiáng)素?cái)?shù)強(qiáng)素?cái)?shù)l(p-1)/2和和(q-1)/2應(yīng)是素?cái)?shù)應(yīng)是素?cái)?shù)l選取較小的選取較小的e和較大的和較大的de：3、65537l發(fā)布公鑰發(fā)布公鑰證書中心證書中心 CA 26攻擊攻擊RSA數(shù)學(xué)方法數(shù)學(xué)方法l分解分解n得到得到p和和q

11、，就可以知道，就可以知道(n)，就可從，就可從e求得求得dl直接求直接求(n)不分解不分解n，而直接求，而直接求(n)，再求再求d l直接求直接求d 不求不求(n)，直接求，直接求d 27使用公鑰傳遞會(huì)話密鑰使用公鑰傳遞會(huì)話密鑰 l直接使用公鑰算法太慢直接使用公鑰算法太慢l只用來傳遞會(huì)話密鑰只用來傳遞會(huì)話密鑰(假設(shè)假設(shè)A已經(jīng)有已經(jīng)有B的公鑰的公鑰KeB)A發(fā)起和發(fā)起和B的通信的通信A產(chǎn)生會(huì)話密鑰產(chǎn)生會(huì)話密鑰Ks，并用，并用KeB加密后傳給加密后傳給BB能用自己的私鑰能用自己的私鑰KdB解開解開他人不會(huì)知道他人不會(huì)知道Ks 28對稱算法對稱算法 vs. 公鑰算法公鑰算法l速度速度典型相差典型相差1000倍倍l密鑰管理密鑰管理對稱算法需要額外安全信道對稱算法需要額外安全信道公鑰公鑰l證書中心證書中心l混合密碼體制混合密碼體制公鑰算法用于簽名和認(rèn)證