第6章公鑰密碼體制

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

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

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

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

5、(y)是困難的。是困難的。( (所謂計算所謂計算x=fx=f-1-1(y)(y)困難是指計算上相當復雜，已無實際意義困難是指計算上相當復雜，已無實際意義) )n(3)(3)存在存在，已知，已知 時時, ,對給定的任何對給定的任何y y，若相應的，若相應的x x存在，則存在，則計算計算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ù)，公鑰密碼就是基于這一原理設計的，將輔助信息（陷門信息）作為秘密密鑰。于這一原理設計的，將輔助信息（陷門信息）作為秘密密鑰。 Char 7 pp.7o 當用陷門函數(shù)當用陷門函數(shù)f f作為加密函數(shù)時，可將作為加密函數(shù)時，可將f f公開，這相當于公開公開，這相當于公開加密密鑰。此時加密密鑰便稱為公開鑰，記為加密密鑰。此時加密密鑰便稱為公開鑰，記為KUKU。 f f函數(shù)的函數(shù)的設計者將設計者將 保密，用作解密密鑰，此時保密，用作解密密鑰，此時 稱為秘密鑰匙，稱為秘密鑰匙，記為記為KRKR。由于加密函數(shù)是公開的，任何人都可以將信息。由于加密函數(shù)是公開的，任何人都可以將信息x x加加密成密成y=y

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

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

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

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

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

12、lice知道其自身的私鑰，所以其他接收者均不能解密出消知道其自身的私鑰，所以其他接收者均不能解密出消息。息。o 在公鑰密碼中，通信各方均可以訪問公鑰，而私鑰是各通在公鑰密碼中，通信各方均可以訪問公鑰，而私鑰是各通信方在本地產(chǎn)生的，不進行分配。只要控制了私鑰，通信就信方在本地產(chǎn)生的，不進行分配。只要控制了私鑰，通信就是安全的。在任何時候，用戶可以改變其私鑰并公布相應的是安全的。在任何時候，用戶可以改變其私鑰并公布相應的公鑰以代替原來的公鑰。公鑰以代替原來的公鑰。Char 7 pp.13公鑰密碼通信保密性分析圖公鑰密碼通信保密性分析圖對稱密碼保密性對稱密碼保密性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個元素是某個有個元素是某個有窮字母表上的字符，窮字母表上的字符，A A欲將消息欲將消息X X發(fā)送給發(fā)送給B B。B B產(chǎn)生公鑰產(chǎn)生公鑰KUKUb b和和私鑰私鑰KRKRb b，其中只有，其中只有B B知道知道KRKRb b，而，而KUKUb b則是公開的可訪問的，則是公開的可訪問的，所以所以A A也可訪問也可訪問KUKUb b。o 對作為輸入的消息對作為輸入的消息X X和加密密鑰和加密密鑰KUbKUb，A A生成密文生成密文Y=YY=Y1 1,Y,Y2

14、2,Y Yn n: Y=: Y=E EKUbKUb(X(X) )o 期望的接收方因為擁有相應的私鑰，所以可進行逆變換：期望的接收方因為擁有相應的私鑰，所以可進行逆變換：X=X=D DKRbKRb(Y(Y) )o 攻擊者可以觀察到攻擊者可以觀察到Y Y并且可以訪問并且可以訪問KUKUb b，但是它不能訪問，但是它不能訪問KRKRb b或者或者X X，所以他無法知道，所以他無法知道X X，從而實現(xiàn)了保密通信。，從而實現(xiàn)了保密通信。Char 7 pp.15公鑰密碼認證模型公鑰密碼認證模型Char 7 pp.16公鑰密碼認證過程公鑰密碼認證過程o 每一用戶產(chǎn)生一對密鑰，用來加密和解密消息。每一用戶產(chǎn)生

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、加法逆元。加法逆元。o乘法逆元乘法逆元 ：設：設 ，如果存在，如果存在 滿足滿足 ，則稱，則稱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ù)和模定義：設定義：設a,b,ca,b,c是任意的三個整數(shù)，若滿足是任意的三個整數(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 設設a,ba,b是兩個整數(shù)，是兩個整數(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的一個公因子，對的一個公因子，對a a1 1,a,a2 2,a,an n的任一個公因子的任一個公因子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ù)中, 不一定有素數(shù)不一定有素數(shù). 例如例如(25,36)=1, 但但25和和36都都不是素數(shù)而是合數(shù)不是素數(shù)而是合數(shù).Char 7 pp.36最大公因子的性質(zhì)最大公因子的性質(zhì)任何不全為任何不全為0的兩個整數(shù)的最大公因子存在且唯一的兩個整數(shù)的最大公因子存在且唯一o 設整數(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ù)設設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ù)中最小的那一個所有公倍數(shù)中最小的那一個, , 稱為稱為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素數(shù)定義素數(shù)定義o 一個大于一個大于1且只能被且只能被1和它本身整除的整數(shù)和它本身整除的整數(shù), 稱為素數(shù)稱為素數(shù); 否則否則, 稱為合數(shù)稱為合數(shù).o 素數(shù)有無窮多個；素數(shù)有無窮多個；o 如果如果p是一個素數(shù)，且是一個素數(shù)，且p|ab,則則p|a或或p|b;o 記記PAI(x)為不大于為不大于x的素數(shù)個數(shù)，則的素數(shù)個數(shù)，則o 即對于

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

37、，p1 ,p2, ,pk是質(zhì)數(shù)，是質(zhì)數(shù)，r1,r2,rk是是正整數(shù)。正整數(shù)。Char 7 pp.40強素數(shù)強素數(shù)on n是一個整數(shù)，是一個整數(shù)，n=n=pqpq, ,且且p p、q q滿足以下屬性時，稱滿足以下屬性時，稱n n為強素數(shù)：為強素數(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都是素數(shù)都是素數(shù)o對于強素數(shù)，即使采用特殊的因子分解方法，對整數(shù)對于強素數(shù)，即使采用特殊的因子分解方法，對整數(shù)n n的因子分解也非的因子分解也非常困難。常困難。o強素數(shù)：強素數(shù)：439351292910452432574786963588089477522344331強素數(shù)強素數(shù)第六章第六章一種強素數(shù)因子分解的量子算法一種強素數(shù)因子分解的量子算法.pdf實現(xiàn)實現(xiàn)Char 7 pp.41歐拉函數(shù)歐拉函數(shù)歐拉函數(shù)歐拉函數(shù)(n n) )：表示區(qū)間：表示區(qū)間1,n1,n中中與與 n n 互素的整數(shù)的個數(shù)；互素的整數(shù)的個數(shù)；習慣上，習

39、慣上，歐拉函數(shù)的性質(zhì)：歐拉函數(shù)的性質(zhì)：( (1 1) )素數(shù)素數(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)對于對于n n屬于屬于Z Z，n n22，(4)(4)對于素數(shù)對于素數(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ù)論上，對于正整數(shù)在數(shù)論上，對

40、于正整數(shù)n的一個算術函數(shù)的一個算術函數(shù) f(n)，當，當中中f(1)=1且當且當a,b互質(zhì)，互質(zhì)，f(ab)=f(a)f(b)完全積性函數(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項項Char 7 pp.43歐拉定理歐拉定理對于任意互素的對于任意互素的a 和和 n ，有：，有：等價形式：等價形式：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)可以看出，對兩個整數(shù)，如果第二個整數(shù)是可以看出，對兩個整數(shù)，如果第二個整數(shù)是0，那么第一個數(shù)就是這兩個數(shù)的最大公約數(shù)。那么第一個數(shù)就是這兩個數(shù)的最大公約數(shù)。o 從從(2)可以看出，如何去改變可以看出，如何去改變a和和b的值，直到使的值，直到使b為為0的方法，當?shù)姆椒?，當b變?yōu)樽優(yōu)?時，直接得到最大公約數(shù)。時，直接得到最大公約數(shù)。o 如如gcd(36,10)=gcd(10,6)=gcd(6,4)o =gcd(4,2)=gcd(2,0)=2用于計算兩個整數(shù)的最大公因子用于計算兩個整數(shù)的最大公因子Char 7 pp.45Eu

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

43、稱得的余數(shù)相同，則稱a和和b對模對模m同余同余.記為記為 或或o 一切整數(shù)一切整數(shù)n可以按照某個自然數(shù)可以按照某個自然數(shù)m作為除數(shù)的余數(shù)作為除數(shù)的余數(shù)進行分類，即進行分類，即n=pm+r（r=0，1，m-1），?。?，恰好好m個數(shù)類個數(shù)類.于是同余的概念可理解為于是同余的概念可理解為,若對若對n1、n2，有有n1=q1m+r，n2=q2m+r，那么，那么n1、n2對模對模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) 每個整數(shù)恰與每個整數(shù)恰與0,1,，m-1，這，這m個整數(shù)中的某一個對模個整數(shù)中的某一個對模m同余；同余；(4) 同余關系是一種等價關系：同余關系是一種等價關系： 反身性反身性 ； 對稱性對稱性 ，則，則 ，反之亦然，反之亦然. 傳遞性傳遞性 ， ，則，則 ；(5)如果如果 ， ，則，則 ； 特別地特別地Char 7 pp.51中國剩余定理中國剩余定理o 數(shù)學名著數(shù)學名著孫子算經(jīng)孫子算經(jīng)中：中：o “今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何。七七數(shù)之剩二，問物幾何。”o 即即“有一批物品，三個三個地數(shù)余

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

46、。/上面乘得的三個積相加的和如超過上面乘得的三個積相加的和如超過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這三個數(shù)分別乘以它這三個數(shù)分別乘以它們的余數(shù)，再把三個積加起來是們的余數(shù)，再把三個積加起來是233，符合題意，但不是最小，而，符合題意，但不是最小，而105又又是是3、5、7的最小公倍數(shù)，去掉的最小公倍數(shù)，去掉10

47、5的倍數(shù)，剩下的差就是最小的一個答的倍數(shù)，剩下的差就是最小的一個答案。案。Char 7 pp.53o 求解如下形式的同余方程組求解如下形式的同余方程組 o 其中：其中： ， ， ， 。 中國剩余定理中國剩余定理Char 7 pp.54中國剩余定理中國剩余定理Char 7 pp.55中國剩余定理中國剩余定理o 一個數(shù)被一個數(shù)被3除余除余1，被，被4除余除余2，被，被5除余除余4，這個數(shù)最小是幾？，這個數(shù)最小是幾？o 解：解：3、4、5三個數(shù)兩兩互質(zhì)。三個數(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 因為，因為，27460，所以，所以，274604=34， o http:/ 7 pp.56Information Security：Principles & Applications6.3 RSA算法算法Char 7 pp.58RSA算法算法 簡介簡介o 分組密碼，安全性依賴于分組密碼，安全性依賴于大數(shù)的因子分解大數(shù)的因子分解。 o 第一個較為完善的公鑰算法。第一個較為完善的公鑰算法。 o 能夠同時用于加密和數(shù)字簽名，且易于理解和操作。能夠同時用

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

50、）o 設分組長度為設分組長度為l bit，每個分組，每個分組 M 被看作是一個被看作是一個 l bit 的二的二進制值。進制值。n 取某一個整數(shù)取某一個整數(shù) n ，使對所有，使對所有 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 使對所有使對所有 M n 都有：都有：M = Med mod nn 對所有對所有 M n ， Me 和和 Cd 的計算相對簡單。的計算相對簡單。n 給定給定 e, n ，要推斷，要推斷 d 在計算上不可行。在計算上不可行。o 問題：問題：怎樣找到滿足怎樣找到滿足 M = Med mod n 的的 e, d, n ？o 需要利用數(shù)論作為其數(shù)學基礎。需要利用數(shù)論作為其數(shù)學基礎。Char 7 pp.61歐拉定理與RSA算法o RSA算法要求：算法要求：M = Med mod no 歐拉定理推論：歐拉定理推論：n有兩個素數(shù)有兩個素數(shù) p 和和 q, 令令

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

53、ZxnyyDdk mod)(nZyChar 7 pp.63RSA算法實現(xiàn)步驟密鑰的產(chǎn)生密鑰的產(chǎn)生o生成兩個大素數(shù)生成兩個大素數(shù) p 和和 q ，pq；o計算計算 ， ；o選擇隨機數(shù)選擇隨機數(shù) e（即加密密鑰）（即加密密鑰）, 使之滿使之滿足足 , ；o計算解密密鑰計算解密密鑰 ；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體制的關鍵點體制的關鍵點在于如何分解在于如何分解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必須是足夠大的素數(shù)，使分析者沒有辦必須是足夠大的素數(shù)，使分析者沒有辦法在法在多項式時間多項式時間內(nèi)將內(nèi)將n n分解出來。建議選擇分解出來。建議選擇p p和和q q大約

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

56、對為了抵抗現(xiàn)有的整數(shù)分解算法，對RSARSA模模n n的素因子的素因子p p和和q q還有還有如下要求：如下要求：(1)|(1)|p-q|p-q|很大，通常很大，通常 p p和和q q的長度相同；的長度相同；(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ī)定準中規(guī)定 e e2 216161 1，ISO9796ISO9796中甚至允許取中甚至允許取e e3 3。這時加。這時加密速度一般比解密速度快密速度一般比解密速度快1010倍以上。倍以上。Char 7 pp.66RSA 實現(xiàn)上的問題n密鑰生成時，如何找到足夠大的素數(shù)密鑰生成時，如何找到足夠大的素數(shù) p 和和 q ？n對一個很大的整數(shù)對一個很大的整數(shù)，如何判定它是否是素數(shù)？如何判定它是否是素數(shù)？n在在 n、m、e、d 非常大的情況下，如何計算非常大的情況下，如何計算 me mod n ?Char 7 pp.67RSA 實現(xiàn)上的相關算法o模加；模加

58、；o模乘；模乘；o擴展的輾轉(zhuǎn)相除法（歐幾里德（擴展的輾轉(zhuǎn)相除法（歐幾里德（ Euclidean ）算法）算法 ）；）；o求逆；求逆；o中國剩余定理；中國剩余定理；o求冪算法；求冪算法；o素性測試算法。素性測試算法。 Char 7 pp.68RSA算法舉例一（算法舉例一（1）明文明文M=88,p=17,q=11,給出給出RSA 算法加算法加/解密過程。解密過程。密鑰生成密鑰生成1 1、選擇兩個素數(shù)，題中已經(jīng)給出，、選擇兩個素數(shù)，題中已經(jīng)給出，p=17,q=11p=17,q=11。2 2、計算、計算n =n =pqpq=17=17* *11=18711=187。3 3、計算、計算(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。因為。因為2323* *7=161=107=161=10* *16+116+1，所以所以d=23d=23。Char 7 pp.69RSA算法舉例一（算法舉例一（2）加密加密公鑰公鑰KU=7，187加密時，需計算加密時，需計算C=887mod187。利用模算術的性質(zhì)，得利用模算術的性質(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解密時，需計算解密時，需計算M=1123mod187。利用模算術的性質(zhì)，得利用模算術的性質(zhì)，得1123mod187=(111mod187)*(112mod187)*(114mod187)*(118mod187)*(118mod187)=88積的模等于模積RSARSA加密演示加密演示Char 7 pp.70RSA算法舉例二（算法舉例二（1）明文明文M=“its all greek to me”