第9章非對稱密碼體制(1)

1、第9章 非對稱密碼體制第9章 非對稱密碼體制第9章 非對稱密碼體制主要內(nèi)容 公鑰密碼體制概述 RSA加密算法 算法描述 快速實現(xiàn) 安全性分析第9章 非對稱密碼體制現(xiàn)代密碼學 對稱密碼算法通信雙方事先商定好同一個密鑰 流密碼：RC4等 分組密碼: DES，AES等 非對稱密碼算法通信雙方無需事先商定密鑰 公鑰加密算法：RSA，ElGamal等 公鑰簽名算法：RSA，DSS等第9章 非對稱密碼體制對稱密碼體制 加密和解密由同一個密鑰來控制，也叫單鑰算法第9章 非對稱密碼體制對稱密碼體制 特點 共享密鑰，密鑰必須保密 可提供保密和消息完整性認證 對稱密碼體制的問題 加密能力與解密能力是捆綁在一起的

2、密鑰更換、傳遞和交換需要可靠信道，密鑰分發(fā)困難 無法實現(xiàn)數(shù)字簽名why第9章 非對稱密碼體制對稱加密算法如何保證消息保密性和完整性 對稱密碼算法假設(shè)消息的收發(fā)雙方共享同一密鑰K，發(fā)送方將消息M用共享密鑰K加密后得到的密文C在公開信道上傳輸。只要算法安全，只有知道共享密鑰K的人，即接收方才能由C恢復消息M，知道消息M的內(nèi)容。敵手截獲了C是無法計算出M的任何信息的，從而保證消息保密性保密性。 同時，如果消息是有意義的，或者具有某種易于識別的特性或結(jié)構(gòu)，接收方可根據(jù)解密得到的消息是否具有這種結(jié)構(gòu)，而判斷消息在傳輸過程中有沒有被篡改，從而保證消息的完整性完整性。 第9章 非對稱密碼體制公鑰密碼學 是密

3、碼學最偉大的革命 實現(xiàn)密鑰的分離，不對稱 1976年，Diffie和Hellman ，“密碼學的新方向” （1970， James Ellis，英國政府通信總部1997年解密） 1977年，Rivest、Shamir、Adleman提出著名的RSA密碼體制 （1973，Clifford Cocks，同上） ElGamal密碼體制、Rabin密碼體制等 各種公鑰加密和簽名算法 數(shù)學困難問題第9章 非對稱密碼體制公鑰密碼體制實現(xiàn)加密第9章 非對稱密碼體制公鑰密碼體制的組成 明文：算法的輸入，可讀信息或數(shù)據(jù) 加密算法：對明文進行各種轉(zhuǎn)換 公鑰和私鑰：算法的輸入，分別用于加密和解密 密文：算法的輸出，

4、依賴于明文和密鑰 解密算法：根據(jù)密文和密鑰，還原明文第9章 非對稱密碼體制公鑰算法的主要步驟 每個用戶產(chǎn)生密鑰，用來加密和解密消息 每個用戶將其中一個密鑰(公鑰)存于公開的寄存器或其他可訪問的文件中，另一密鑰私有，每個用戶可以擁有若干其他用戶的公鑰 若Bob要發(fā)消息給Alice，則要用Alice的公鑰對消息加密 Alice收到消息后，用其私鑰對消息解密，由于只有Alice知道其自身的私鑰，所以其他的接收者均不能解密消息 需要認證認證時示證方用自己的私鑰加密消息(簽名) 驗證方用示證方的公鑰解密消息(驗證)，如果結(jié)果證實公鑰與示證方的私鑰相吻合，則可以確認示證方確為合法的用戶(認證) 加密和認證

5、可以結(jié)合起來，同時實現(xiàn)保密性和認證第9章 非對稱密碼體制公鑰密碼體制的要求 Diffie&Hellman 產(chǎn)生一對密鑰(公鑰ke和私鑰kd)是計算上容易的 已知明文m和公鑰ke ，加密是計算上容易的，C=E(ke, m) 已知密文m和私鑰kd ，解密是計算上容易的， m=D(kd, C) 由ke確定kd是計算上不可行的 不知道kd，即使知道ke, E, D及C，計算m也不可行 對明文m, E(ke, m)有定義，且D(kd, E(ke, m)=m 對密文c, D(kd, C)有定義，且E(ke, D(kd, C)=C 加解密順序可交換（適用于部分算法），即D(E(m)=E(D(m)第9

6、章 非對稱密碼體制公鑰密碼體制的基本觀點 關(guān)鍵：單向陷門函數(shù) 計算復雜性的角度考慮11( ) 1.,( )2 .,() )( f xxyf xyxfyoneway functiontrapdoor oneway functiofyn：定義域中計算是容單向函數(shù)（）單向陷門函數(shù)：已知陷門信易的值域中幾乎所有計算是不可行的是容易的息，求陷門信息幫助合法接收者解密第9章 非對稱密碼體制 對稱密碼 公鑰密碼一般要求：一般要求：1、加解密用相同的密鑰和算法2、收發(fā)雙方必須共享密鑰安全性要求：安全性要求：1、密鑰必須保密2、沒有密鑰，解密不可行3、知道算法和若干密文不足以確定密鑰一般要求：一般要求：1、加解

7、密算法相同，但密鑰不同2、發(fā)送方和接收方擁有不同密鑰安全性要求：安全性要求：1、兩個密鑰必有一個保密2、無私鑰，解密或簽名不可行3、知道算法和其中一個密鑰以及若干密文或簽名不能確定另一個密鑰第9章 非對稱密碼體制Are these opinions right? Public key crypto is safer than private key crypto Public key crypto will replace private key crypto(X)(X)第9章 非對稱密碼體制RSA加密算法 1977年，Rivest、Shamir、Adleman提出的非對稱密碼體制，基于大合數(shù)

8、的素因子分解問題的困難性 廣泛應用的公鑰密碼算法 明文和密文均為0, n-1之間的整數(shù)第9章 非對稱密碼體制(Left to Right: Ron ivest, Adi hamir, Len Adleman)2002年圖靈獎獲得者-RSA-2002第9章 非對稱密碼體制Ronald L. Rivest Professor Rivest is the Professor of Electrical Engineering and Computer Science in MITs Department of Electrical Engineering and Computer Science.

9、He is a founder of RSA Data Security (now merged with Security Dynamics to form RSA Security). Professor Rivest has research interests in cryptography, computer and network security, electronic voting, and algorithms. RivestRivest博士現(xiàn)任美國麻省理工學院博士現(xiàn)任美國麻省理工學院電子工程和計算機科學系教授。電子工程和計算機科學系教授。第9章 非對稱密碼體制Adi Sha

10、mir ShamirShamir是以色列是以色列WeizmannWeizmann科學學院科學學院應用數(shù)學系的教授。應用數(shù)學系的教授。第9章 非對稱密碼體制Len AdlemanAdlemanAdleman現(xiàn)現(xiàn)在是美國南在是美國南加州大學的加州大學的計算機科學計算機科學以及分子生以及分子生物學教授。物學教授。第9章 非對稱密碼體制RSA 密鑰產(chǎn)生過程 隨機選擇兩個大素數(shù) p，q 計算 n=pq注意(n) =(p-1)(q-1) 選擇一個隨機數(shù) e使得1e(n)，且gcd (e, (n)=1 解下列方程求出 d ed=1 mod (n) 且 0dn 公開公鑰pk: e, n 保密私鑰sk: d,

11、p, q 第9章 非對稱密碼體制RSA 加解密過程 發(fā)送方加密消息 M: 獲得接收方的公鑰 KU=e,N 計算: C=Me mod N, 其中 0MN 接收方解密密文 C： 使用自己的私鑰 KR=d,N 計算: M=Cd mod N 注意：M N (可根據(jù)需要分組處理)第9章 非對稱密碼體制例子解密者（接收者）：隨機選取兩個素數(shù): p=17 & q=11計算 n = pq =1711=187計算 (n)=(p1)(q-1)=1610=160隨機選取e=7，滿足 gcd(e,160)=1計算 d: 滿足de=1 mod 160 且d 160，得 d=23 （ 237=161=160+1）

12、(可利用擴展的Euclid算法)公開公鑰 KU=7,187保密私鑰 KR=23,17,11第9章 非對稱密碼體制例子 加密者（發(fā)送方）： 加密消息 M = 88 (注意. 881是素數(shù)當且僅當它只有因子1和p。 0，1都不是素數(shù) 2是最小的素數(shù)，也是唯一的偶素數(shù) 如2,3,5,7是素數(shù), 4,6,8,9,10不是 素數(shù)是數(shù)論的核心第9章 非對稱密碼體制28費馬小定理定理定理 (費馬小定理) 若p是素數(shù), a是正整數(shù)且不能被p整除, 則ap-1 mod p=1 費馬小定理等價形式apa mod p, p是素數(shù) 費馬小定理前一種形式要求a，p互素。 等價形式則沒有要求。練習：驗證1、a=7,p=1

13、9 2、a=3,p=5 3、a=10,p=54、利用費馬定理計算3201 mod 11答案：324816118162749 11(m od19)7121 7(m od19)749 11(m od19)7121 7(m od19)7777 11 1(m od19)pa 第9章 非對稱密碼體制29剩余類集/完全剩余類集/縮剩余類集 定義比n小的非負整數(shù)集合Zn， Zn =0,1,(n-1)為剩余類集。 Zn中每一個整數(shù)都代表著一個剩余類。 模n的完全剩余類集：如果對每個整數(shù)a，在集合r1,r2,rn中恰有一個余數(shù)ri，使得 a=ri mod n ,則稱r1,r2,rn為模n的完全剩余集。 Zn形成

14、模n的完全剩余類集。 模n的縮剩余類集：完全剩余集的一個子集，指的是集合中的元素都和n互素，記為Zn* Z10= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; Z10*= 1, 3, 7, 9第9章 非對稱密碼體制30歐拉函數(shù)(n) (n)是比n小且與n互素的正整數(shù)的個數(shù)，即模n的縮剩余系中元素之個數(shù)。第9章 非對稱密碼體制31 計算 (n) 需要計算與n不互素的元素的個數(shù) 例如 (37) = 36 (14) = #1,3,5,9,11,13=6 對素數(shù)p， (p) = p-1 對 n=pq (p, q 是素數(shù)) (n) = (p-1)(q-1) 例如(14) = (21)(71

15、) = 16 = 6 歐拉函數(shù)(n)第9章 非對稱密碼體制32歐拉函數(shù)(n) 定理：p和q是素數(shù), n=p*q, (n)= (p)(q)=(p-1)(q-1) 證明： 考慮余數(shù)集合0, 1, , (pq-1)中不與n互素的余數(shù)集合是p, 2p, , (q-1)p, q, 2q, , (p-1)q和0, 所以 (n)= pq-(q-1)+(p-1)+1 =pq-(p+q)+1 = (p-1)(q-1) =(p)(q)N 的分解 (n)的求解第9章 非對稱密碼體制33Eulers Theorem a generalisation of Fermats Theorem (歐拉定理): 對任意互素的a

16、和n, 有a(n) 1 mod n eg. a=3;n=10; (10)=4; hence 34 = 81 = 1 mod 10 a=2;n=11; (11)=10; hence 210 = 1024 = 1 mod 11第9章 非對稱密碼體制34歐拉定理的等價形式 a(n)+1 a (mod n) 同費馬小定理一樣，歐拉定理前一種形式要求a，n互素。等價形式則沒有要求。 用于證明RSA算法的正確性。 第9章 非對稱密碼體制35素性檢測Primality Testing 在建立RSA密碼體制的過程中，如何生成大的“隨機素數(shù)”？ 首先生成大的隨機整數(shù)，然后利用概率算法概率算法(Miller-Ra

17、bin算法)來檢測它們的素性 可行性分析? 素數(shù)個數(shù)定理:()lnNNN()N為小于等于N的素數(shù)的個數(shù)51211ln2355問:1024bit的N, p和q為512,則一個隨機512bit整數(shù)為素數(shù)的概率約為？限定奇數(shù)，概率加倍：2355第9章 非對稱密碼體制隨機算法的分類類型 Las Vegas Monte Carlo第9章 非對稱密碼體制Las Vegas 計算結(jié)果總是對的或最佳的. 運算時間是隨機的, 但運行時間有界 也許不給出一個回答，但任何回答總是正也許不給出一個回答，但任何回答總是正確的確的第9章 非對稱密碼體制Monte Carlo 運算結(jié)果可能不正確或不是最佳 結(jié)果不正確或非最

18、佳出現(xiàn)的概率有界 可以通過多次運行該算法可使得出錯的概率變的很小 (相當于多次的獨立實驗) 總是給出一個回答，但回答也許不正確總是給出一個回答，但回答也許不正確 偏是（yes-biased）：“是”回答總是正確的，但“否”回答也許是不正確的 偏否（no-biased）：“否”回答總是正確的，但“是”回答也許是不正確的第9章 非對稱密碼體制39素性檢測 密碼學中常常需要尋找大素數(shù) 傳統(tǒng)的方法是用試除法來過濾素數(shù) 即依次除小于該數(shù)平方根的所有素數(shù) 這種方法只對較小的數(shù)有用 可以采用基于素數(shù)特性的統(tǒng)計素性測試方法 其中所有的素數(shù)都滿足素數(shù)特性 但是有一些合數(shù)也滿足該素數(shù)特性，這樣的合數(shù)稱為“偽素數(shù)偽

19、素數(shù)”第9章 非對稱密碼體制40Miller-Rabin素性檢測算法 這是一種基于費馬小定理的方法 假設(shè)n是素數(shù), 則有an-1 = 1 mod n（反之不成立） 背景：對于候選奇整數(shù)n=3, 偶數(shù)(n-1)可表示為 n-1 = 2kq k0, q是奇數(shù) 為證明這一點，用2去除偶數(shù)(n-1)，直至所得結(jié)果為奇數(shù)q，此處共做k次除法；如果n是二進制數(shù)，則將該數(shù)右移，直到最右邊的比特為1，共移動了k次。第9章 非對稱密碼體制41素數(shù)性質(zhì)之一 如果p是素數(shù), a是小于p的正整數(shù), 則 a2modp=1, 當且僅當amodp=1或者amodp= -1modp=p-1 如果a2modp=1, 則a2-1

20、=0modp =(a-1)(a+1)成立的條件是amodp=1或者amodp=-1 反之,根據(jù)(amodp)(amodp)=a2modp, 如果amodp=1或amodp= -1, 則有a2modp=1第9章 非對稱密碼體制42素數(shù)性質(zhì)之二 設(shè)p是大于2的素數(shù), 有p-1=2kq, k0, q是奇數(shù). 設(shè)a是整數(shù)且1a 0, q odd, so that (n1)=2kq2. Select a random integer a, 1an13. if aq mod n = 1 then return (“maybe prime);4. for j = 0 to k 1 do5. if (a2jq

21、 mod n = n-1) then return( maybe prime )6. return (composite)第9章 非對稱密碼體制45重復使用Miller-Rabin算法如果如果Miller-Rabin算法返回算法返回“composite”, 這數(shù)肯定不是素數(shù)；返回這數(shù)肯定不是素數(shù)；返回“不確定不確定”時是素數(shù)或者時是素數(shù)或者偽素數(shù)偽素數(shù)給定一個奇合數(shù)給定一個奇合數(shù)n和一個隨機整數(shù)和一個隨機整數(shù)a, 1an-1, 程序程序TEST返回不確定的返回不確定的概率小于概率小于 (即不能確定即不能確定n是素數(shù)是素數(shù))因此因此,對于一個奇合數(shù)對于一個奇合數(shù)n， 如果選擇如果選擇t個不同的個不同的a, 則它們都能通過測試則它們都能通過測試(返返回不確定回不確定)的概率小于的概率小于(1/4)t 取取 t=10, 則一個非素整數(shù)通過則一個非素整數(shù)通過10次測試的概率小于