第6章公鑰密碼體制

1、Information Security：Principles & Applications第第6章章 公鑰密碼體制公鑰密碼體制Char 7 pp.2本章概要本章概要o 公鑰密碼的概念、特點(diǎn)和應(yīng)用范圍。公鑰密碼的概念、特點(diǎn)和應(yīng)用范圍。o 數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)o RSARSA算法加、解密過(guò)程。算法加、解密過(guò)程。o 其它公鑰算法簡(jiǎn)介。其它公鑰算法簡(jiǎn)介。o 教學(xué)要求：原理要清楚，數(shù)論不深究。教學(xué)要求：原理要清楚，數(shù)論不深究。 Information Security：Principles & Applications6.1公鑰密碼的基本思想 Char 7 pp.4o 密鑰分配密鑰分配:

2、:通信密鑰太多，管理和分發(fā)困難。通信密鑰太多，管理和分發(fā)困難。n 傳統(tǒng)密鑰管理：兩兩分別用一對(duì)密鑰時(shí)，則傳統(tǒng)密鑰管理：兩兩分別用一對(duì)密鑰時(shí)，則n n個(gè)用戶個(gè)用戶需要需要C(n,2)=n(n-1)/2C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶量增大時(shí)，個(gè)密鑰，當(dāng)用戶量增大時(shí)，密鑰空間急劇增大。如密鑰空間急劇增大。如: :n n=100 n=100 時(shí)，時(shí)，C(100,2)=4,995C(100,2)=4,995n n=5000n=5000時(shí)，時(shí)，C(5000,2)=12,497,500C(5000,2)=12,497,500o 數(shù)字簽名和認(rèn)證數(shù)字簽名和認(rèn)證n 傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的需求傳

3、統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的需求對(duì)稱密鑰面臨的困題對(duì)稱密鑰面臨的困題Char 7 pp.5密碼體制上的突破密碼體制上的突破o DiffieDiffie & Hellman, & Hellman, 密碼學(xué)新方向密碼學(xué)新方向( (New Direction in New Direction in Cryptography), 1976Cryptography), 1976。o 首次公開提出了首次公開提出了“公開密鑰密碼編碼學(xué)公開密鑰密碼編碼學(xué)”的概念。的概念。o 這是一個(gè)與對(duì)稱密碼編碼截然不同的方案：這是一個(gè)與對(duì)稱密碼編碼截然不同的方案：n 公鑰算法是基于數(shù)學(xué)函數(shù)；傳統(tǒng)對(duì)稱密碼算法基

4、于公鑰算法是基于數(shù)學(xué)函數(shù)；傳統(tǒng)對(duì)稱密碼算法基于替換和置換。替換和置換。n 公鑰密碼學(xué)是非對(duì)稱的，它使用兩個(gè)獨(dú)立的密鑰；公鑰密碼學(xué)是非對(duì)稱的，它使用兩個(gè)獨(dú)立的密鑰；傳統(tǒng)對(duì)稱密碼使用一個(gè)密鑰。傳統(tǒng)對(duì)稱密碼使用一個(gè)密鑰。Char 7 pp.6公鑰密碼的定義（公鑰密碼的定義（1）用抽象的觀點(diǎn)來(lái)看，公鑰密碼是一種陷門單向函數(shù)。用抽象的觀點(diǎn)來(lái)看，公鑰密碼是一種陷門單向函數(shù)。單向陷門函數(shù)是滿足單向陷門函數(shù)是滿足下列條件的函數(shù)下列條件的函數(shù)f f：n(1)(1)給定給定x x，計(jì)算，計(jì)算y=y=f(xf(x) )是容易的；是容易的；n(2)(2)給定給定y, y, 計(jì)算計(jì)算x x使使x=fx=f-1-1(y)

5、(y)是困難的。是困難的。( (所謂計(jì)算所謂計(jì)算x=fx=f-1-1(y)(y)困難是指計(jì)算上相當(dāng)復(fù)雜，已無(wú)實(shí)際意義困難是指計(jì)算上相當(dāng)復(fù)雜，已無(wú)實(shí)際意義) )n(3)(3)存在存在，已知，已知 時(shí)時(shí), ,對(duì)給定的任何對(duì)給定的任何y y，若相應(yīng)的，若相應(yīng)的x x存在，則存在，則計(jì)算計(jì)算x x使使x=fx=f-1-1(y)(y)是容易的。是容易的。 僅滿足僅滿足(1)(1)、(2)(2)兩條的稱為單向函數(shù)；第兩條的稱為單向函數(shù)；第(3)(3)條稱為陷門性，條稱為陷門性， 稱為陷門稱為陷門信息；滿足（信息；滿足（1 1）、（）、（2 2）、（）、（3 3）就是單向陷門函數(shù)，公鑰密碼就是基）就是單向陷

6、門函數(shù)，公鑰密碼就是基于這一原理設(shè)計(jì)的，將輔助信息（陷門信息）作為秘密密鑰。于這一原理設(shè)計(jì)的，將輔助信息（陷門信息）作為秘密密鑰。 Char 7 pp.7o 當(dāng)用陷門函數(shù)當(dāng)用陷門函數(shù)f f作為加密函數(shù)時(shí)，可將作為加密函數(shù)時(shí)，可將f f公開，這相當(dāng)于公開公開，這相當(dāng)于公開加密密鑰。此時(shí)加密密鑰便稱為公開鑰，記為加密密鑰。此時(shí)加密密鑰便稱為公開鑰，記為KUKU。 f f函數(shù)的函數(shù)的設(shè)計(jì)者將設(shè)計(jì)者將 保密，用作解密密鑰，此時(shí)保密，用作解密密鑰，此時(shí) 稱為秘密鑰匙，稱為秘密鑰匙，記為記為KRKR。由于加密函數(shù)是公開的，任何人都可以將信息。由于加密函數(shù)是公開的，任何人都可以將信息x x加加密成密成y=y

7、=f(xf(x) )，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全信道傳送）；由于設(shè)計(jì)者擁有信道傳送）；由于設(shè)計(jì)者擁有KRKR，他自然可以解出，他自然可以解出x=fx=f-1-1(y)(y)。o 單向陷門函數(shù)的第單向陷門函數(shù)的第(2)(2)條性質(zhì)表明竊聽者由截獲的密文條性質(zhì)表明竊聽者由截獲的密文y=y=f(xf(x) )推測(cè)推測(cè)x x是不可行的。是不可行的。公鑰密碼的定義（公鑰密碼的定義（2）Char 7 pp.8o 一對(duì)（一對(duì)（兩個(gè)兩個(gè)）密鑰：）密鑰：n 使用一個(gè)密鑰進(jìn)行加密，用另一個(gè)相關(guān)的密鑰進(jìn)行使用一個(gè)密鑰進(jìn)行加密，用另一個(gè)相關(guān)的密鑰進(jìn)行解密解密o

8、用加密密鑰生成的密文只有使用其對(duì)應(yīng)的解用加密密鑰生成的密文只有使用其對(duì)應(yīng)的解密密鑰才能解密。密密鑰才能解密。n 兩個(gè)密鑰的關(guān)系滿足：兩個(gè)密鑰的關(guān)系滿足：o 兩個(gè)密鑰是不相同；兩個(gè)密鑰是不相同；o 在僅知道密碼算法和加密密鑰的情況下，要在僅知道密碼算法和加密密鑰的情況下，要推斷解密密鑰在計(jì)算上是推斷解密密鑰在計(jì)算上是不可行不可行的。的。o 兩個(gè)密鑰中的兩個(gè)密鑰中的任何一個(gè)任何一個(gè)都可以用來(lái)加密，另都可以用來(lái)加密，另一個(gè)用來(lái)解密。（如一個(gè)用來(lái)解密。（如RSARSA）公鑰算法基本特征公鑰算法基本特征Char 7 pp.9o 密鑰管理密鑰管理n 加密密鑰是公開的；加密密鑰是公開的； n 解密密鑰需要妥

9、善保存；解密密鑰需要妥善保存； n 在當(dāng)今具有用戶量大、消息發(fā)送方與接收方具有明在當(dāng)今具有用戶量大、消息發(fā)送方與接收方具有明顯的信息不對(duì)稱特點(diǎn)的應(yīng)用環(huán)境中表現(xiàn)出了令人樂(lè)顯的信息不對(duì)稱特點(diǎn)的應(yīng)用環(huán)境中表現(xiàn)出了令人樂(lè)觀的前景。觀的前景。 o 數(shù)字簽名和認(rèn)證數(shù)字簽名和認(rèn)證n 只有解密密鑰能解密，只有正確的接收者才擁有解只有解密密鑰能解密，只有正確的接收者才擁有解密密鑰。密密鑰。公鑰密碼體制優(yōu)點(diǎn)公鑰密碼體制優(yōu)點(diǎn)Char 7 pp.10o 明文明文：算法的輸入。可讀信息或數(shù)據(jù)。：算法的輸入。可讀信息或數(shù)據(jù)。o 加密算法加密算法：對(duì)明文進(jìn)行各種轉(zhuǎn)換。：對(duì)明文進(jìn)行各種轉(zhuǎn)換。o 公鑰和私鑰公鑰和私鑰：算法的輸

10、入。一個(gè)用于加密，一個(gè)用：算法的輸入。一個(gè)用于加密，一個(gè)用于解密。算法執(zhí)行的變換依賴于公鑰和私鑰。于解密。算法執(zhí)行的變換依賴于公鑰和私鑰。o 密文密文：算法的輸出。依賴于明文和密鑰，對(duì)于給定：算法的輸出。依賴于明文和密鑰，對(duì)于給定的消息，不同的密鑰產(chǎn)生不同明文。的消息，不同的密鑰產(chǎn)生不同明文。o 解密算法：接收密文和相應(yīng)的密鑰，并產(chǎn)生原始的解密算法：接收密文和相應(yīng)的密鑰，并產(chǎn)生原始的明文。明文。公鑰密碼組成公鑰密碼組成Char 7 pp.11公鑰密碼加密公鑰密碼加密/解密模型解密模型對(duì)稱密碼通信模型對(duì)稱密碼通信模型Char 7 pp.12公鑰密碼公鑰密碼/加解過(guò)程加解過(guò)程o 每一用戶產(chǎn)生一對(duì)密

11、鑰，用來(lái)加密和解密消息。每一用戶產(chǎn)生一對(duì)密鑰，用來(lái)加密和解密消息。o 用戶將其中一個(gè)密鑰存于公開的寄存器或其他可訪問(wèn)的文件用戶將其中一個(gè)密鑰存于公開的寄存器或其他可訪問(wèn)的文件中，該密鑰稱為公鑰，另一個(gè)密鑰是私有的，稱為私鑰。用中，該密鑰稱為公鑰，另一個(gè)密鑰是私有的，稱為私鑰。用戶可以擁有若干其他用戶的公鑰戶可以擁有若干其他用戶的公鑰o 若若BobBob要發(fā)消息給要發(fā)消息給AliceAlice，則，則BobBob用用AliceAlice的公鑰對(duì)消息加密。的公鑰對(duì)消息加密。o AliceAlice收到消息后，用其私鑰對(duì)消息進(jìn)行解密。由于只有收到消息后，用其私鑰對(duì)消息進(jìn)行解密。由于只有 AliceA

12、lice知道其自身的私鑰，所以其他接收者均不能解密出消知道其自身的私鑰，所以其他接收者均不能解密出消息。息。o 在公鑰密碼中，通信各方均可以訪問(wèn)公鑰，而私鑰是各通在公鑰密碼中，通信各方均可以訪問(wèn)公鑰，而私鑰是各通信方在本地產(chǎn)生的，不進(jìn)行分配。只要控制了私鑰，通信就信方在本地產(chǎn)生的，不進(jìn)行分配。只要控制了私鑰，通信就是安全的。在任何時(shí)候，用戶可以改變其私鑰并公布相應(yīng)的是安全的。在任何時(shí)候，用戶可以改變其私鑰并公布相應(yīng)的公鑰以代替原來(lái)的公鑰。公鑰以代替原來(lái)的公鑰。Char 7 pp.13公鑰密碼通信保密性分析圖公鑰密碼通信保密性分析圖對(duì)稱密碼保密性對(duì)稱密碼保密性Char 7 pp.14公鑰密碼通信

13、保密性分析公鑰密碼通信保密性分析o 消息源消息源A A產(chǎn)生消息產(chǎn)生消息X=XX=X1 1,X,X2 2,X Xm m,其中其中X X的的M M個(gè)元素是某個(gè)有個(gè)元素是某個(gè)有窮字母表上的字符，窮字母表上的字符，A A欲將消息欲將消息X X發(fā)送給發(fā)送給B B。B B產(chǎn)生公鑰產(chǎn)生公鑰KUKUb b和和私鑰私鑰KRKRb b，其中只有，其中只有B B知道知道KRKRb b，而，而KUKUb b則是公開的可訪問(wèn)的，則是公開的可訪問(wèn)的，所以所以A A也可訪問(wèn)也可訪問(wèn)KUKUb b。o 對(duì)作為輸入的消息對(duì)作為輸入的消息X X和加密密鑰和加密密鑰KUbKUb，A A生成密文生成密文Y=YY=Y1 1,Y,Y2

14、2,Y Yn n: Y=: Y=E EKUbKUb(X(X) )o 期望的接收方因?yàn)閾碛邢鄳?yīng)的私鑰，所以可進(jìn)行逆變換：期望的接收方因?yàn)閾碛邢鄳?yīng)的私鑰，所以可進(jìn)行逆變換：X=X=D DKRbKRb(Y(Y) )o 攻擊者可以觀察到攻擊者可以觀察到Y(jié) Y并且可以訪問(wèn)并且可以訪問(wèn)KUKUb b，但是它不能訪問(wèn)，但是它不能訪問(wèn)KRKRb b或者或者X X，所以他無(wú)法知道，所以他無(wú)法知道X X，從而實(shí)現(xiàn)了保密通信。，從而實(shí)現(xiàn)了保密通信。Char 7 pp.15公鑰密碼認(rèn)證模型公鑰密碼認(rèn)證模型Char 7 pp.16公鑰密碼認(rèn)證過(guò)程公鑰密碼認(rèn)證過(guò)程o 每一用戶產(chǎn)生一對(duì)密鑰，用來(lái)加密和解密消息。每一用戶產(chǎn)生

15、一對(duì)密鑰，用來(lái)加密和解密消息。o 每一個(gè)用戶將其中一個(gè)密鑰存于公開的寄存器或其他可訪問(wèn)每一個(gè)用戶將其中一個(gè)密鑰存于公開的寄存器或其他可訪問(wèn)的文件中，該密鑰稱為公鑰，另一個(gè)密鑰是私有的。每一個(gè)的文件中，該密鑰稱為公鑰，另一個(gè)密鑰是私有的。每一個(gè)用戶可以擁有其他若干個(gè)其他用戶的公鑰。用戶可以擁有其他若干個(gè)其他用戶的公鑰。o 若若BobBob要發(fā)消息給要發(fā)消息給AliceAlice，且需要向，且需要向AliceAlice提供認(rèn)證，則提供認(rèn)證，則BobBob用用私鑰對(duì)消息加密。私鑰對(duì)消息加密。o AliceAlice收到消息后，用收到消息后，用BobBob的公鑰對(duì)消息進(jìn)行解密。由于只有的公鑰對(duì)消息進(jìn)行

16、解密。由于只有 BobBob知道其自身的私鑰，所以其他發(fā)送者均不能生成能用知道其自身的私鑰，所以其他發(fā)送者均不能生成能用BobBob公鑰解密的消息。由此可以確認(rèn)此消息來(lái)源于公鑰解密的消息。由此可以確認(rèn)此消息來(lái)源于BobBob。Char 7 pp.17公鑰密碼認(rèn)證分析圖公鑰密碼認(rèn)證分析圖Char 7 pp.18公鑰密碼認(rèn)證分析公鑰密碼認(rèn)證分析o消息源消息源A A產(chǎn)生消息產(chǎn)生消息X=XX=X1 1,X,X2 2,X Xm m,其中其中X X的的M M個(gè)元素是某個(gè)有窮字母表上個(gè)元素是某個(gè)有窮字母表上的字符，的字符，A A欲將消息欲將消息X X發(fā)送給發(fā)送給B B。A A產(chǎn)生公鑰產(chǎn)生公鑰KUKUa a和

17、私鑰和私鑰KRKRa a，其中只有，其中只有A A知道知道KRaKRa，而，而KUKUa a則是公開的可訪問(wèn)的，所以則是公開的可訪問(wèn)的，所以B B也可訪問(wèn)也可訪問(wèn)KUKUa a。oA A向向B B發(fā)送消息前，先用發(fā)送消息前，先用A A的私鑰對(duì)消息加密，的私鑰對(duì)消息加密，B B則用則用A A的公鑰對(duì)消息解密。的公鑰對(duì)消息解密。由于是用由于是用A A的私鑰對(duì)消息加密，所以只有的私鑰對(duì)消息加密，所以只有A A可加密消息，因此，整個(gè)加密可加密消息，因此，整個(gè)加密后的消息就是數(shù)字簽名。除此之外只有擁有后的消息就是數(shù)字簽名。除此之外只有擁有A A 的私鑰才能產(chǎn)生上述加密的私鑰才能產(chǎn)生上述加密后的消息，因此

18、該消息可用于認(rèn)證源與數(shù)據(jù)完整性。后的消息，因此該消息可用于認(rèn)證源與數(shù)據(jù)完整性。o作為任何第三方只要都可以很容易的收到認(rèn)證消息作為任何第三方只要都可以很容易的收到認(rèn)證消息Y Y，因此該過(guò)程不提，因此該過(guò)程不提供保密。供保密。Char 7 pp.19公鑰密碼的保密與認(rèn)證圖公鑰密碼的保密與認(rèn)證圖Char 7 pp.20公鑰密碼保密與認(rèn)證過(guò)程分析公鑰密碼保密與認(rèn)證過(guò)程分析o 對(duì)于單次加密只提供認(rèn)證或保密的問(wèn)題，可以采用兩次運(yùn)用對(duì)于單次加密只提供認(rèn)證或保密的問(wèn)題，可以采用兩次運(yùn)用公鑰密碼的方式即提供加密又提供認(rèn)證：公鑰密碼的方式即提供加密又提供認(rèn)證：Z=Z=E EKUbKUbEEKRaKRa(X(X)

19、) X=X=D DKUaKUaDDKRbKRb(Z(Z)o 發(fā)送方首先用其私鑰對(duì)消息加密，得到數(shù)字簽名，然后再用發(fā)送方首先用其私鑰對(duì)消息加密，得到數(shù)字簽名，然后再用接收方的公鑰加密，所得密文只有被擁有私鑰的接收方解密。接收方的公鑰加密，所得密文只有被擁有私鑰的接收方解密。這樣可保證消息的保密性。這樣可保證消息的保密性。o 缺點(diǎn)：在每次通信中要執(zhí)行四次復(fù)雜的公鑰算法。缺點(diǎn)：在每次通信中要執(zhí)行四次復(fù)雜的公鑰算法。Char 7 pp.21常見(jiàn)公鑰算法適用范圍常見(jiàn)公鑰算法適用范圍Char 7 pp.22對(duì)稱密碼和公鑰密碼比較（對(duì)稱密碼和公鑰密碼比較（1） 對(duì)稱密碼對(duì)稱密碼運(yùn)行條件：運(yùn)行條件：1、加密和

20、解密使用同一個(gè)、加密和解密使用同一個(gè)密鑰和一個(gè)算法。密鑰和一個(gè)算法。2、發(fā)送方和接收方必須共、發(fā)送方和接收方必須共享密鑰和算法。享密鑰和算法。 公公鑰密碼鑰密碼運(yùn)行條件：運(yùn)行條件：1 1、用同一個(gè)算法進(jìn)行加密、用同一個(gè)算法進(jìn)行加密和解密，而密鑰有一對(duì)，和解密，而密鑰有一對(duì)，其中一個(gè)用于加密，另一其中一個(gè)用于加密，另一個(gè)用于解密。個(gè)用于解密。2 2、發(fā)送方和接收方每個(gè)擁、發(fā)送方和接收方每個(gè)擁有一對(duì)相互匹配的密鑰中有一對(duì)相互匹配的密鑰中的一個(gè)的一個(gè)( (不是同一個(gè)不是同一個(gè)) )。Char 7 pp.23對(duì)稱密碼和公鑰密碼比較（對(duì)稱密碼和公鑰密碼比較（2） 對(duì)稱密碼對(duì)稱密碼安全條件：安全條件：1、

21、密鑰必須保密。、密鑰必須保密。2、如果不掌握其他信息，要、如果不掌握其他信息，要想解密報(bào)文是不可能或者想解密報(bào)文是不可能或者至少是不現(xiàn)實(shí)的。至少是不現(xiàn)實(shí)的。3、知道所用的算法加上密文、知道所用的算法加上密文的樣本必須不足以確定密的樣本必須不足以確定密鑰。鑰。 公鑰密碼公鑰密碼安全條件：安全條件：1 1、兩個(gè)密鑰中的一個(gè)必、兩個(gè)密鑰中的一個(gè)必須保密。須保密。2 2、如果不掌握其他信息，、如果不掌握其他信息，要想解密報(bào)文是不可能要想解密報(bào)文是不可能或者至少是不現(xiàn)實(shí)的。或者至少是不現(xiàn)實(shí)的。3 3、知道所用的算法加上、知道所用的算法加上一個(gè)密鑰加上密文的樣一個(gè)密鑰加上密文的樣本必須不足以確定密鑰。本必

22、須不足以確定密鑰。Char 7 pp.24公鑰密碼的保密與認(rèn)證圖公鑰密碼的保密與認(rèn)證圖Char 7 pp.25公鑰密碼保密與認(rèn)證過(guò)程分析公鑰密碼保密與認(rèn)證過(guò)程分析o 對(duì)于單次加密只提供認(rèn)證或保密的問(wèn)題，可以采用兩次運(yùn)用對(duì)于單次加密只提供認(rèn)證或保密的問(wèn)題，可以采用兩次運(yùn)用公鑰密碼的方式即提供加密又提供認(rèn)證：公鑰密碼的方式即提供加密又提供認(rèn)證：Z=Z=E EKUbKUbEEKRaKRa(X(X) ) X=X=D DKUaKUaDDKRbKRb(Z(Z)o 發(fā)送方首先用其私鑰對(duì)消息加密，得到數(shù)字簽名，然后再用發(fā)送方首先用其私鑰對(duì)消息加密，得到數(shù)字簽名，然后再用接收方的公鑰加密，所得密文只有被擁有私鑰

23、的接收方解密。接收方的公鑰加密，所得密文只有被擁有私鑰的接收方解密。這樣可保證消息的保密性。這樣可保證消息的保密性。o 缺點(diǎn)：在每次通信中要執(zhí)行四次復(fù)雜的公鑰算法。缺點(diǎn)：在每次通信中要執(zhí)行四次復(fù)雜的公鑰算法。Char 7 pp.26常見(jiàn)公鑰算法適用范圍常見(jiàn)公鑰算法適用范圍Char 7 pp.27對(duì)稱密碼和公鑰密碼比較（對(duì)稱密碼和公鑰密碼比較（1） 對(duì)稱密碼對(duì)稱密碼運(yùn)行條件：運(yùn)行條件：1、加密和解密使用同一個(gè)、加密和解密使用同一個(gè)密鑰和一個(gè)算法。密鑰和一個(gè)算法。2、發(fā)送方和接收方必須共、發(fā)送方和接收方必須共享密鑰和算法。享密鑰和算法。 公公鑰密碼鑰密碼運(yùn)行條件：運(yùn)行條件：1 1、用同一個(gè)算法進(jìn)行

24、加密、用同一個(gè)算法進(jìn)行加密和解密，而密鑰有一對(duì)，和解密，而密鑰有一對(duì)，其中一個(gè)用于加密，另一其中一個(gè)用于加密，另一個(gè)用于解密。個(gè)用于解密。2 2、發(fā)送方和接收方每個(gè)擁、發(fā)送方和接收方每個(gè)擁有一對(duì)相互匹配的密鑰中有一對(duì)相互匹配的密鑰中的一個(gè)的一個(gè)( (不是同一個(gè)不是同一個(gè)) )。Char 7 pp.28對(duì)稱密碼和公鑰密碼比較（對(duì)稱密碼和公鑰密碼比較（2） 對(duì)稱密碼對(duì)稱密碼安全條件：安全條件：1、密鑰必須保密。、密鑰必須保密。2、如果不掌握其他信息，要、如果不掌握其他信息，要想解密報(bào)文是不可能或者想解密報(bào)文是不可能或者至少是不現(xiàn)實(shí)的。至少是不現(xiàn)實(shí)的。3、知道所用的算法加上密文、知道所用的算法加上密

25、文的樣本必須不足以確定密的樣本必須不足以確定密鑰。鑰。 公鑰密碼公鑰密碼安全條件：安全條件：1 1、兩個(gè)密鑰中的一個(gè)必、兩個(gè)密鑰中的一個(gè)必須保密。須保密。2 2、如果不掌握其他信息，、如果不掌握其他信息，要想解密報(bào)文是不可能要想解密報(bào)文是不可能或者至少是不現(xiàn)實(shí)的。或者至少是不現(xiàn)實(shí)的。3 3、知道所用的算法加上、知道所用的算法加上一個(gè)密鑰加上密文的樣一個(gè)密鑰加上密文的樣本必須不足以確定密鑰。本必須不足以確定密鑰。Char 7 pp.29公鑰密碼算法應(yīng)滿足條件公鑰密碼算法應(yīng)滿足條件 假設(shè)消息源為假設(shè)消息源為A，要發(fā)送的消息為，要發(fā)送的消息為M，消息接收方為，消息接收方為B。B的公鑰的公鑰KUb，私

26、，私鑰鑰KRb。oB產(chǎn)生一對(duì)密鑰（公鑰產(chǎn)生一對(duì)密鑰（公鑰KUb ，私鑰，私鑰KRb ）在計(jì)算上是容易的。）在計(jì)算上是容易的。o已知公鑰已知公鑰KUb和要加密的消息和要加密的消息M，發(fā)送方，發(fā)送方A產(chǎn)生相應(yīng)的密文在計(jì)算上是產(chǎn)生相應(yīng)的密文在計(jì)算上是容易的：容易的：C=EKUb（M）o接收方接收方B使用其私鑰對(duì)接收方的密文解密以恢復(fù)明文在計(jì)算上是容易的：使用其私鑰對(duì)接收方的密文解密以恢復(fù)明文在計(jì)算上是容易的：M=DKRb（C）= DKRbEKUb（M）o已知公鑰時(shí)，攻擊者要確定私鑰，在計(jì)算上是不可行的。已知公鑰時(shí)，攻擊者要確定私鑰，在計(jì)算上是不可行的。o已知公鑰和密文，攻擊者要恢復(fù)明文已知公鑰和密文

27、，攻擊者要恢復(fù)明文M在計(jì)算上是不可行的。在計(jì)算上是不可行的。o加密和解密函數(shù)的順序可以交換：加密和解密函數(shù)的順序可以交換： M= DKUb EKRb（M）=EKUb DKRb （M）目前只有兩個(gè)滿足這些條件的算法：目前只有兩個(gè)滿足這些條件的算法：RSA、橢圓密碼體制、橢圓密碼體制Char 7 pp.30(1)(1)基于大整數(shù)因子分解的基于大整數(shù)因子分解的RSARSA算法；算法；(2)(2)橢圓曲線公鑰算法；橢圓曲線公鑰算法；(3)(3)基于因子分解問(wèn)題的基于因子分解問(wèn)題的RabinRabin算法；算法；(4)(4)基于有限域中離散對(duì)數(shù)難題的基于有限域中離散對(duì)數(shù)難題的ElGamalElGamal

28、公鑰密碼算公鑰密碼算法法(5)(5)基于代數(shù)編碼系統(tǒng)的基于代數(shù)編碼系統(tǒng)的McElieceMcEliece公鑰密碼算法；公鑰密碼算法； (6)(6)基于基于“子集和子集和”難題的難題的Merkle-HellmanMerkle-Hellman Knapsack Knapsack公鑰密碼算法；公鑰密碼算法； (7)(7)目前被認(rèn)為安全的目前被認(rèn)為安全的KnapsackKnapsack型公鑰密碼算法型公鑰密碼算法Chor-Chor-RivestRivest。 公鑰密碼算法公鑰密碼算法Information Security：Principles & Applications6.2 6.2 數(shù)論

29、簡(jiǎn)介數(shù)論簡(jiǎn)介Char 7 pp.32數(shù)論術(shù)語(yǔ)數(shù)論術(shù)語(yǔ)o最大公因子最大公因子 ：任意有限個(gè)整數(shù)：任意有限個(gè)整數(shù) 的公因子中的最大一個(gè)。必的公因子中的最大一個(gè)。必然存在并且惟一，記為然存在并且惟一，記為 。o最小公倍數(shù)最小公倍數(shù) ：任意有限個(gè)整數(shù)：任意有限個(gè)整數(shù) 的公倍數(shù)中的最小一個(gè)的公倍數(shù)中的最小一個(gè) 。必然存在并且惟一，記為必然存在并且惟一，記為 。o同余式同余式 ：設(shè)：設(shè)n是一個(gè)正整數(shù)，是一個(gè)正整數(shù)， 如果如果 ，則稱，則稱a和和b模模n同余，記作：同余，記作： ，稱整數(shù)，稱整數(shù)n為同余模。為同余模。o加法逆元加法逆元 ：設(shè)：設(shè) ，如果存在，如果存在 滿足滿足 ，則稱，則稱x是是a的的模模n

30、加法逆元。加法逆元。o乘法逆元乘法逆元 ：設(shè)：設(shè) ，如果存在，如果存在 滿足滿足 ，則稱，則稱x是是a的模的模n乘法逆元，記為乘法逆元，記為 a-1 (mod n)。naaa,21 ),gcd(21naaa naaa,21 ),(21naaalcm Zba,nbnamodmod)(modnba nZanZx)(mod0naxnZanZx)(mod1nax Char 7 pp.33整數(shù)和模整數(shù)和模定義：設(shè)定義：設(shè)a,b,ca,b,c是任意的三個(gè)整數(shù)，若滿足是任意的三個(gè)整數(shù)，若滿足b=acb=ac則稱則稱a a整除整除b,ab,a( (或或c c）是）是b b的因子，的因子，b b是是a a（或（

31、或c c）的倍數(shù)，記）的倍數(shù)，記為為 abab; ;若若a a不能整除不能整除b b，記為記為a a！b.b.性質(zhì)：性質(zhì)：（1 1） 若若baba, , 則下列各式成立則下列各式成立 (b0) (b0) (b)ab)a, , b(ab(a), (), (b)(ab)(a), ), baba（2 2）若）若cbcb且且baba (c0,b0), (c0,b0), 則則caca（3 3）若）若baba (b0), (b0), 則則bacbac（4 4） 若若baba且且bcbc (b0), (b0), 則則b(ab(ac c) )（5 5） 若若abab且且baba (a0,b0), (a0,b0

32、), 則則a=a=b bChar 7 pp.34定理定理6.2.1 6.2.1 設(shè)設(shè)a,ba,b是兩個(gè)整數(shù)，是兩個(gè)整數(shù)，b1b1，則存在唯一確，則存在唯一確定的整數(shù)定的整數(shù)q q、r r使?jié)M足使?jié)M足a=a=bq+rbq+r； 其中其中0rb0r=2)=2)是任意整數(shù)，若有是任意整數(shù)，若有 d|ad|a1 1,d| a,d| a2 2,d|ad|an n，則稱則稱d d是是a a1 1,a,a2 2,a,an n的公因子。的公因子。 若若d d是是a a1 1,a,a2 2,a,an n的一個(gè)公因子，對(duì)的一個(gè)公因子，對(duì)a a1 1,a,a2 2,a,an n的任一個(gè)公因子的任一個(gè)公因子c c，存

33、在存在c c d d，則稱則稱d d是是a a1 1,a,a2 2,a,an n的最大公因子，記為的最大公因子，記為 gcdgcd （ a a1 1,a,a2 2,a,an n ）若若gcd(al,a2,an)=1, 稱稱al,a2,an是互素。是互素。在互素的正整數(shù)中在互素的正整數(shù)中, 不一定有素?cái)?shù)不一定有素?cái)?shù). 例如例如(25,36)=1, 但但25和和36都都不是素?cái)?shù)而是合數(shù)不是素?cái)?shù)而是合數(shù).Char 7 pp.36最大公因子的性質(zhì)最大公因子的性質(zhì)任何不全為任何不全為0的兩個(gè)整數(shù)的最大公因子存在且唯一的兩個(gè)整數(shù)的最大公因子存在且唯一o 設(shè)整數(shù)設(shè)整數(shù)a與與b不全為不全為0，則存在整數(shù)，則存

34、在整數(shù)x和和y，使得，使得ax+by=gcd(a,b)。特別地，如果。特別地，如果a、b互素，則有互素，則有ax+by=1o 若若gcd(a,b)=d, 則則gcd (a|d, b|d)=1o 若若gcd(a,x)=gcd(b,x)=1,那么那么gcd(ab,x)=1o 若若c|(ab),gcd(b,c)=1,則則c|aChar 7 pp.37最小公倍數(shù)最小公倍數(shù)設(shè)設(shè)a a1 1,a,a2 2,a,an n和和m m都是正整數(shù)都是正整數(shù), , n2. n2. 若若a ai i|m|m, , 1in, 1in, 則稱則稱m m是是a a1 1,a,a2 2,a,an n的公倍數(shù)的公倍數(shù). .o

35、在在a a1 1,a,a2 2,a,an n所有公倍數(shù)中最小的那一個(gè)所有公倍數(shù)中最小的那一個(gè), , 稱為稱為a a1 1,a,a2 2,a,an n的最小公倍數(shù)的最小公倍數(shù), , 記為記為lcm(alcm(a1 1,a,a2 2,a,an n）Char 7 pp.38素?cái)?shù)定義素?cái)?shù)定義o 一個(gè)大于一個(gè)大于1且只能被且只能被1和它本身整除的整數(shù)和它本身整除的整數(shù), 稱為素?cái)?shù)稱為素?cái)?shù); 否則否則, 稱為合數(shù)稱為合數(shù).o 素?cái)?shù)有無(wú)窮多個(gè)；素?cái)?shù)有無(wú)窮多個(gè)；o 如果如果p是一個(gè)素?cái)?shù)，且是一個(gè)素?cái)?shù)，且p|ab,則則p|a或或p|b;o 記記PAI(x)為不大于為不大于x的素?cái)?shù)個(gè)數(shù)，則的素?cái)?shù)個(gè)數(shù)，則o 即對(duì)于

36、充分大的即對(duì)于充分大的x，可以用，可以用xlnx近似的表示近似的表示PAI(x)Char 7 pp.39算術(shù)基本定理算術(shù)基本定理o 算術(shù)基本定理：任意一個(gè)正整數(shù)算術(shù)基本定理：任意一個(gè)正整數(shù)n(n1)可以唯一地可以唯一地表示為若干個(gè)素?cái)?shù)的乘積。這里唯一的意義表示為表示為若干個(gè)素?cái)?shù)的乘積。這里唯一的意義表示為不考慮素因子的次序。不考慮素因子的次序。o 任意一個(gè)整數(shù)任意一個(gè)整數(shù)n(n0,n1)可以唯一地表示為可以唯一地表示為p1 p2 pk ( k=1 )，p1 ,p2, ,pk是素?cái)?shù)。是素?cái)?shù)。o 任意一個(gè)整數(shù)任意一個(gè)整數(shù)n(n0,n1)可以唯一地表示為可以唯一地表示為 p1r1 p2r2 pkrk

37、，p1 ,p2, ,pk是質(zhì)數(shù)，是質(zhì)數(shù)，r1,r2,rk是是正整數(shù)。正整數(shù)。Char 7 pp.40強(qiáng)素?cái)?shù)強(qiáng)素?cái)?shù)on n是一個(gè)整數(shù)，是一個(gè)整數(shù)，n=n=pqpq, ,且且p p、q q滿足以下屬性時(shí)，稱滿足以下屬性時(shí)，稱n n為強(qiáng)素?cái)?shù)：為強(qiáng)素?cái)?shù)：o(1)gcd(p-1,q-1)(1)gcd(p-1,q-1)比較??；比較?。籵(2)p-1(2)p-1和和q-1q-1都有大素因子都有大素因子( (記記p p* *,q,q* *) )；o(3)p(3)p* *-1-1和和q q* *-1-1都有大的素因子；都有大的素因子；o(4)p+1(4)p+1和和q+1q+1都有大的素因子；都有大的素因子；o(

38、5)(p-1)/2(5)(p-1)/2和和(q-1)/2(q-1)/2都是素?cái)?shù)都是素?cái)?shù)o對(duì)于強(qiáng)素?cái)?shù)，即使采用特殊的因子分解方法，對(duì)整數(shù)對(duì)于強(qiáng)素?cái)?shù)，即使采用特殊的因子分解方法，對(duì)整數(shù)n n的因子分解也非的因子分解也非常困難。常困難。o強(qiáng)素?cái)?shù)：強(qiáng)素?cái)?shù)：439351292910452432574786963588089477522344331強(qiáng)素?cái)?shù)強(qiáng)素?cái)?shù)第六章第六章一種強(qiáng)素?cái)?shù)因子分解的量子算法一種強(qiáng)素?cái)?shù)因子分解的量子算法.pdf實(shí)現(xiàn)實(shí)現(xiàn)Char 7 pp.41歐拉函數(shù)歐拉函數(shù)歐拉函數(shù)歐拉函數(shù)(n n) )：表示區(qū)間：表示區(qū)間1,n1,n中中與與 n n 互素的整數(shù)的個(gè)數(shù)；互素的整數(shù)的個(gè)數(shù)；習(xí)慣上，習(xí)

39、慣上，歐拉函數(shù)的性質(zhì)：歐拉函數(shù)的性質(zhì)：( (1 1) )素?cái)?shù)素?cái)?shù) p p，有，有( (p p)=)=p p11；( (2 2) )( (n n) )為積性函數(shù)，即，如果為積性函數(shù)，即，如果gcd(m,ngcd(m,n)=1,)=1, ( (mnmn)=)=( (m m) )( (n n) )(3)(3)對(duì)于對(duì)于n n屬于屬于Z Z，n n22，(4)(4)對(duì)于素?cái)?shù)對(duì)于素?cái)?shù)p,q,np,q,n= =pq,pq,( (n n)=)=(pq(pq)=(p-1)(q-1)=(p-1)(q-1)(5)(5)如果如果n n屬于屬于Z Z，n5n5，則，則積性函數(shù)：積性函數(shù)：在數(shù)論上，對(duì)于正整數(shù)在數(shù)論上，對(duì)

40、于正整數(shù)n的一個(gè)算術(shù)函數(shù)的一個(gè)算術(shù)函數(shù) f(n)，當(dāng)，當(dāng)中中f(1)=1且當(dāng)且當(dāng)a,b互質(zhì)，互質(zhì)，f(ab)=f(a)f(b)完全積性函數(shù)完全積性函數(shù): 若某算術(shù)函數(shù)若某算術(shù)函數(shù)f(n)符合符合f(1)=1，且就算，且就算a,b不互質(zhì)，不互質(zhì)，f(ab)=f(a)f(b)。Char 7 pp.42歐拉函數(shù)前歐拉函數(shù)前30項(xiàng)項(xiàng)Char 7 pp.43歐拉定理歐拉定理對(duì)于任意互素的對(duì)于任意互素的a 和和 n ，有：，有：等價(jià)形式：等價(jià)形式：nanmod1)(fnanmoda)+1(fChar 7 pp.44Euclidean算法算法(1)根據(jù)根據(jù): (1)：gcd (a, 0) = a; (2)：

41、gcd (a, b) = gcd (b, a mod b) 。o 從從(1)可以看出，對(duì)兩個(gè)整數(shù)，如果第二個(gè)整數(shù)是可以看出，對(duì)兩個(gè)整數(shù)，如果第二個(gè)整數(shù)是0，那么第一個(gè)數(shù)就是這兩個(gè)數(shù)的最大公約數(shù)。那么第一個(gè)數(shù)就是這兩個(gè)數(shù)的最大公約數(shù)。o 從從(2)可以看出，如何去改變可以看出，如何去改變a和和b的值，直到使的值，直到使b為為0的方法，當(dāng)?shù)姆椒ǎ?dāng)b變?yōu)樽優(yōu)?時(shí)，直接得到最大公約數(shù)。時(shí)，直接得到最大公約數(shù)。o 如如gcd(36,10)=gcd(10,6)=gcd(6,4)o =gcd(4,2)=gcd(2,0)=2用于計(jì)算兩個(gè)整數(shù)的最大公因子用于計(jì)算兩個(gè)整數(shù)的最大公因子Char 7 pp.45Eu

42、clidean算法算法(2)Char 7 pp.46擴(kuò)展擴(kuò)展Euclidean算法算法(1) o 給定兩個(gè)整數(shù)給定兩個(gè)整數(shù)a和和b，我們還經(jīng)常需要求得另外兩個(gè)，我們還經(jīng)常需要求得另外兩個(gè)整數(shù)整數(shù)s和和t，使得，使得擴(kuò)展擴(kuò)展Euclidean算法可以計(jì)算算法可以計(jì)算gcd(a,b)，也可以同，也可以同時(shí)計(jì)算時(shí)計(jì)算s和和t的值。的值。 Char 7 pp.47擴(kuò)展擴(kuò)展Euclidean算法流程算法流程(2)Char 7 pp.48擴(kuò)展擴(kuò)展Euclidean算法算法(3)Char 7 pp.49同余式同余式o 定義定義:設(shè)設(shè)a、b、m為整數(shù)（為整數(shù)（m0），若），若a和和b被被m除除得的余數(shù)相同，則

43、稱得的余數(shù)相同，則稱a和和b對(duì)模對(duì)模m同余同余.記為記為 或或o 一切整數(shù)一切整數(shù)n可以按照某個(gè)自然數(shù)可以按照某個(gè)自然數(shù)m作為除數(shù)的余數(shù)作為除數(shù)的余數(shù)進(jìn)行分類，即進(jìn)行分類，即n=pm+r（r=0，1，m-1），恰），恰好好m個(gè)數(shù)類個(gè)數(shù)類.于是同余的概念可理解為于是同余的概念可理解為,若對(duì)若對(duì)n1、n2，有有n1=q1m+r，n2=q2m+r，那么，那么n1、n2對(duì)模對(duì)模m的的同余，即它們用同余，即它們用m除所得的余數(shù)相等除所得的余數(shù)相等.Char 7 pp.50同余式性質(zhì)同余式性質(zhì)(1) 若若 ,則則m|(b-a).反之反之,若若m|(b-a),則則 ;(2) 如果如果a=km+b(k為整數(shù)為

44、整數(shù)),則則 ;(3) 每個(gè)整數(shù)恰與每個(gè)整數(shù)恰與0,1,，m-1，這，這m個(gè)整數(shù)中的某一個(gè)對(duì)模個(gè)整數(shù)中的某一個(gè)對(duì)模m同余；同余；(4) 同余關(guān)系是一種等價(jià)關(guān)系：同余關(guān)系是一種等價(jià)關(guān)系： 反身性反身性 ； 對(duì)稱性對(duì)稱性 ，則，則 ，反之亦然，反之亦然. 傳遞性傳遞性 ， ，則，則 ；(5)如果如果 ， ，則，則 ； 特別地特別地Char 7 pp.51中國(guó)剩余定理中國(guó)剩余定理o 數(shù)學(xué)名著數(shù)學(xué)名著孫子算經(jīng)孫子算經(jīng)中：中：o “今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何。七七數(shù)之剩二，問(wèn)物幾何。”o 即即“有一批物品，三個(gè)三個(gè)地?cái)?shù)余

45、二個(gè)，五個(gè)五個(gè)有一批物品，三個(gè)三個(gè)地?cái)?shù)余二個(gè)，五個(gè)五個(gè)地?cái)?shù)余三個(gè)，七個(gè)七個(gè)地?cái)?shù)余二個(gè)，問(wèn)這批物品最地?cái)?shù)余三個(gè)，七個(gè)七個(gè)地?cái)?shù)余二個(gè)，問(wèn)這批物品最少有多少個(gè)。少有多少個(gè)?！盋har 7 pp.52中國(guó)剩余定理中國(guó)剩余定理o明朝數(shù)學(xué)家程大位：明朝數(shù)學(xué)家程大位：三人同行七十（三人同行七十（7070）?。唬┫?；/除以除以3 3的余數(shù)用的余數(shù)用7070去乘；去乘；五樹梅花廿一（五樹梅花廿一（2121）枝；）枝；/除以除以5 5的余數(shù)用的余數(shù)用2121去乘；去乘；七子團(tuán)圓正月半（七子團(tuán)圓正月半（1515）；）；/除以除以7 7的余數(shù)用的余數(shù)用1515去乘去乘除百零五（除百零五（105105）便得知。）便得知

46、。/上面乘得的三個(gè)積相加的和如超過(guò)上面乘得的三個(gè)積相加的和如超過(guò)105105，就減去，就減去105105的倍數(shù)的倍數(shù)o70702 221213 315152 21051052=232=23o70是是5和和7的公倍數(shù)，且除以的公倍數(shù)，且除以3余余1。21是是3和和7的公倍數(shù)，且除以的公倍數(shù)，且除以5余余1。15是是3和和5的公倍數(shù)，且除以的公倍數(shù)，且除以7余余1。把。把70、21、15這三個(gè)數(shù)分別乘以它這三個(gè)數(shù)分別乘以它們的余數(shù)，再把三個(gè)積加起來(lái)是們的余數(shù)，再把三個(gè)積加起來(lái)是233，符合題意，但不是最小，而，符合題意，但不是最小，而105又又是是3、5、7的最小公倍數(shù)，去掉的最小公倍數(shù)，去掉10

47、5的倍數(shù)，剩下的差就是最小的一個(gè)答的倍數(shù)，剩下的差就是最小的一個(gè)答案。案。Char 7 pp.53o 求解如下形式的同余方程組求解如下形式的同余方程組 o 其中：其中： ， ， ， 。 中國(guó)剩余定理中國(guó)剩余定理Char 7 pp.54中國(guó)剩余定理中國(guó)剩余定理Char 7 pp.55中國(guó)剩余定理中國(guó)剩余定理o 一個(gè)數(shù)被一個(gè)數(shù)被3除余除余1，被，被4除余除余2，被，被5除余除余4，這個(gè)數(shù)最小是幾？，這個(gè)數(shù)最小是幾？o 解：解：3、4、5三個(gè)數(shù)兩兩互質(zhì)。三個(gè)數(shù)兩兩互質(zhì)。o 則則4，5=20；3，5=15；3，4=12；3，4，5=60。o 為了使為了使20被被3除余除余1，用，用202=40；o 使

48、使15被被4除余除余1，用，用153=45；o 使使12被被5除余除余1，用，用123=36。o 然后，然后，401452364=274，o 因?yàn)?，因?yàn)椋?7460，所以，所以，274604=34， o http:/ 7 pp.56Information Security：Principles & Applications6.3 RSA算法算法Char 7 pp.58RSA算法算法 簡(jiǎn)介簡(jiǎn)介o 分組密碼，安全性依賴于分組密碼，安全性依賴于大數(shù)的因子分解大數(shù)的因子分解。 o 第一個(gè)較為完善的公鑰算法。第一個(gè)較為完善的公鑰算法。 o 能夠同時(shí)用于加密和數(shù)字簽名，且易于理解和操作。能夠同時(shí)用

49、于加密和數(shù)字簽名，且易于理解和操作。 o RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，被普遍認(rèn)為年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，被普遍認(rèn)為是目前最優(yōu)秀的公鑰算法之一。是目前最優(yōu)秀的公鑰算法之一。 o 目前仍然目前仍然無(wú)法無(wú)法從理論上證明它的保密性能究竟如何從理論上證明它的保密性能究竟如何 ，因?yàn)椋驗(yàn)槟壳叭藗儾](méi)有從理論上證明破譯目前人們并沒(méi)有從理論上證明破譯RSA的難度與大整數(shù)分解的難度與大整數(shù)分解問(wèn)題的難度等價(jià)。問(wèn)題的難度等價(jià)。 Char 7 pp.59RSA算法描述（算法描述（1

50、）o 設(shè)分組長(zhǎng)度為設(shè)分組長(zhǎng)度為l bit，每個(gè)分組，每個(gè)分組 M 被看作是一個(gè)被看作是一個(gè) l bit 的二的二進(jìn)制值。進(jìn)制值。n 取某一個(gè)整數(shù)取某一個(gè)整數(shù) n ，使對(duì)所有，使對(duì)所有 M，有，有 M no 一般，一般， n 的取值滿足的取值滿足 2l n 2 l+1。n 加密算法加密算法o C = Me mod n。n 解密算法解密算法o M = Cd mod n = (Me)d mod n = Med mod n。n 加密密鑰（公開密鑰）為加密密鑰（公開密鑰）為 KU = e,n。n 解密密鑰（私有密鑰）為解密密鑰（私有密鑰）為 KR = d,n。 Char 7 pp.60RSA算法描述（算

51、法描述（2）o 要求：要求：n e, d, n 使對(duì)所有使對(duì)所有 M n 都有：都有：M = Med mod nn 對(duì)所有對(duì)所有 M n ， Me 和和 Cd 的計(jì)算相對(duì)簡(jiǎn)單。的計(jì)算相對(duì)簡(jiǎn)單。n 給定給定 e, n ，要推斷，要推斷 d 在計(jì)算上不可行。在計(jì)算上不可行。o 問(wèn)題：?jiǎn)栴}：怎樣找到滿足怎樣找到滿足 M = Med mod n 的的 e, d, n ？o 需要利用數(shù)論作為其數(shù)學(xué)基礎(chǔ)。需要利用數(shù)論作為其數(shù)學(xué)基礎(chǔ)。Char 7 pp.61歐拉定理與RSA算法o RSA算法要求：算法要求：M = Med mod no 歐拉定理推論：歐拉定理推論：n有兩個(gè)素?cái)?shù)有兩個(gè)素?cái)?shù) p 和和 q, 令令

52、 n = pq , 對(duì)任意整數(shù)對(duì)任意整數(shù) k 和和 m (0mn), 有下列等式成立：有下列等式成立：m = mk(n) +1 mod n其中：其中：(n) = (p-1)(q-1)。Char 7 pp.62RSA算法描述n選取足夠大的兩個(gè)素?cái)?shù)選取足夠大的兩個(gè)素?cái)?shù) p 和和 q, 令令 n = pq , 則則(n) = (p-1)(q-1)。n選取適當(dāng)?shù)募用苊荑€選取適當(dāng)?shù)募用苊荑€ e 和解密密鑰和解密密鑰 d ，使之滿，使之滿足足 。 n公開公開 n 和和 e ，保密，保密 p, q 和和 d。 n加密運(yùn)算：加密運(yùn)算： n解密運(yùn)算：解密運(yùn)算： )( mod 1nedfnxxEek mod)(n

53、ZxnyyDdk mod)(nZyChar 7 pp.63RSA算法實(shí)現(xiàn)步驟密鑰的產(chǎn)生密鑰的產(chǎn)生o生成兩個(gè)大素?cái)?shù)生成兩個(gè)大素?cái)?shù) p 和和 q ，pq；o計(jì)算計(jì)算 ， ；o選擇隨機(jī)數(shù)選擇隨機(jī)數(shù) e（即加密密鑰）（即加密密鑰）, 使之滿使之滿足足 , ；o計(jì)算解密密鑰計(jì)算解密密鑰 ；o公布整數(shù)公布整數(shù) n 和加密密鑰和加密密鑰 e，公鑰，公鑰KU=e，n。o私鑰私鑰KR=d，n。qpn) 1)(1()( qpnf)( 0nbf)( ,gcd(nef)( mod1nedf=1加密加密明文明文 MnMn密文密文 C=Me(mod n)C=Me(mod n)解密解密密文密文 C C明文明文 M=M=C

54、Cd d(mod(mod n) n)Char 7 pp.64RSA算法的特殊要求（）算法的特殊要求（）密碼分析者密碼分析者攻擊攻擊RSARSA體制的關(guān)鍵點(diǎn)體制的關(guān)鍵點(diǎn)在于如何分解在于如何分解n n。若分解成。若分解成功使功使n=n=pqpq，則可以算出，則可以算出(n(n) )（p-1)(q-1)p-1)(q-1)，然后由公開的，然后由公開的e e，解出秘密的，解出秘密的d d。o 若使若使RSARSA安全，安全，p p與與q q必須是足夠大的素?cái)?shù)，使分析者沒(méi)有辦必須是足夠大的素?cái)?shù)，使分析者沒(méi)有辦法在法在多項(xiàng)式時(shí)間多項(xiàng)式時(shí)間內(nèi)將內(nèi)將n n分解出來(lái)。建議選擇分解出來(lái)。建議選擇p p和和q q大約

55、是大約是100100位位的十進(jìn)制素?cái)?shù)。的十進(jìn)制素?cái)?shù)。 模模n n的長(zhǎng)度要求至少是的長(zhǎng)度要求至少是512512比特比特。EDIEDI標(biāo)準(zhǔn)使標(biāo)準(zhǔn)使用的用的RSARSA算法中規(guī)定算法中規(guī)定n n的長(zhǎng)度為的長(zhǎng)度為512512至至10241024比特位之間，但必比特位之間，但必須是須是128128的倍數(shù)。國(guó)際數(shù)字簽名標(biāo)準(zhǔn)的倍數(shù)。國(guó)際數(shù)字簽名標(biāo)準(zhǔn)ISO9796ISO9796中規(guī)定中規(guī)定n n的長(zhǎng)度的長(zhǎng)度位位512512比特位。比特位。運(yùn)行時(shí)間最多是輸運(yùn)行時(shí)間最多是輸入量的多項(xiàng)式函數(shù)入量的多項(xiàng)式函數(shù) 不是不是DSSChar 7 pp.65RSA算法特殊要求（算法特殊要求（2）o 為了抵抗現(xiàn)有的整數(shù)分解算法，

56、對(duì)為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)RSARSA模模n n的素因子的素因子p p和和q q還有還有如下要求：如下要求：(1)|(1)|p-q|p-q|很大，通常很大，通常 p p和和q q的長(zhǎng)度相同；的長(zhǎng)度相同；(2)(2)p-1 p-1 和和q-1q-1分別含有大素因子分別含有大素因子p p1 1和和q q1 1(3)p(3)p1 1-1-1和和q q1 1-1-1分別含有大素因子分別含有大素因子p p2 2和和q q2 2(4)p+1(4)p+1和和q+1q+1分別含有大素因子分別含有大素因子p p3 3和和q q3 3o 為了提高加密速度，通常取為了提高加密速度，通常取e e為特定的小整數(shù)，

57、如為特定的小整數(shù)，如EDIEDI國(guó)際標(biāo)國(guó)際標(biāo)準(zhǔn)中規(guī)定準(zhǔn)中規(guī)定 e e2 216161 1，ISO9796ISO9796中甚至允許取中甚至允許取e e3 3。這時(shí)加。這時(shí)加密速度一般比解密速度快密速度一般比解密速度快1010倍以上。倍以上。Char 7 pp.66RSA 實(shí)現(xiàn)上的問(wèn)題n密鑰生成時(shí)，如何找到足夠大的素?cái)?shù)密鑰生成時(shí)，如何找到足夠大的素?cái)?shù) p 和和 q ？n對(duì)一個(gè)很大的整數(shù)對(duì)一個(gè)很大的整數(shù)，如何判定它是否是素?cái)?shù)？如何判定它是否是素?cái)?shù)？n在在 n、m、e、d 非常大的情況下，如何計(jì)算非常大的情況下，如何計(jì)算 me mod n ?Char 7 pp.67RSA 實(shí)現(xiàn)上的相關(guān)算法o模加；模加

58、；o模乘；模乘；o擴(kuò)展的輾轉(zhuǎn)相除法（歐幾里德（擴(kuò)展的輾轉(zhuǎn)相除法（歐幾里德（ Euclidean ）算法）算法 ）；）；o求逆；求逆；o中國(guó)剩余定理；中國(guó)剩余定理；o求冪算法；求冪算法；o素性測(cè)試算法。素性測(cè)試算法。 Char 7 pp.68RSA算法舉例一（算法舉例一（1）明文明文M=88,p=17,q=11,給出給出RSA 算法加算法加/解密過(guò)程。解密過(guò)程。密鑰生成密鑰生成1 1、選擇兩個(gè)素?cái)?shù)，題中已經(jīng)給出，、選擇兩個(gè)素?cái)?shù)，題中已經(jīng)給出，p=17,q=11p=17,q=11。2 2、計(jì)算、計(jì)算n =n =pqpq=17=17* *11=18711=187。3 3、計(jì)算、計(jì)算(n)=(p-1)

59、(n)=(p-1)* *(q-1)=16(q-1)=16* *10=16010=160。4 4、選擇、選擇e e，使其與，使其與(n)=160(n)=160互素且小于互素且小于(n)(n)；這里選；這里選e=7e=7。5 5、確定、確定d d使得使得dede1mod1601mod160且且d d160160。因?yàn)椤Ｒ驗(yàn)?323* *7=161=107=161=10* *16+116+1，所以所以d=23d=23。Char 7 pp.69RSA算法舉例一（算法舉例一（2）加密加密公鑰公鑰KU=7，187加密時(shí)，需計(jì)算加密時(shí)，需計(jì)算C=887mod187。利用模算術(shù)的性質(zhì)，得利用模算術(shù)的性質(zhì)，得8

60、87=(884mod187)*(882mod187)*(881mod187)=11明文 加密88 88mod187=11 11 23 mod187=88 88 密文11 解密 明文KU=7，187KR=23，187解密解密私鑰私鑰KR=23，187解密時(shí)，需計(jì)算解密時(shí)，需計(jì)算M=1123mod187。利用模算術(shù)的性質(zhì)，得利用模算術(shù)的性質(zhì)，得1123mod187=(111mod187)*(112mod187)*(114mod187)*(118mod187)*(118mod187)=88積的模等于模積RSARSA加密演示加密演示Char 7 pp.70RSA算法舉例二（算法舉例二（1）明文明文M=“its all greek to me”