簡單密碼體制及分析課件

1、課程名稱課程名稱:計算機密碼學計算機密碼學教材教材:計算機密碼應用基礎計算機密碼應用基礎1總 目 錄第1章 簡單密碼體制及分析第2章 分組密碼第3章 香農理論第4章 序列密碼和移位寄存器第5章 RSA公鑰密碼體制第6章 其它公鑰密碼體制第7章 數字簽名第1章 簡單密碼體制及分析1.1 密碼學的基本概念密碼學的基本概念1.2 一些簡單密碼體制與它的破譯一些簡單密碼體制與它的破譯 密碼學既屬于計算機科學密碼學既屬于計算機科學,也可算是應用數也可算是應用數學學,更確切地說更確切地說,它是二者之間的邊緣學科它是二者之間的邊緣學科,數學數學無疑是其重要的工具無疑是其重要的工具.計算機的出現和廣泛普計算機

2、的出現和廣泛普及及,使人類社會步入信息化時代使人類社會步入信息化時代,也使安全保密也使安全保密研究揭掉了神秘的面紗研究揭掉了神秘的面紗,成為大家感興趣并能成為大家感興趣并能為更多人服務的科學為更多人服務的科學. 信息在社會中的地位和作用越來越重要，信息在社會中的地位和作用越來越重要，已成為社會發(fā)展的重要戰(zhàn)略資源已成為社會發(fā)展的重要戰(zhàn)略資源.1.1 密碼學的基本概念密碼學的基本概念1.引言引言 信息安全所面臨的威脅來自很多方面，并信息安全所面臨的威脅來自很多方面，并且隨著時間的變化而變化。這些威脅可以宏觀且隨著時間的變化而變化。這些威脅可以宏觀地分為人為威脅和自然威脅。地分為人為威脅和自然威脅。

3、 自然威脅可能來自于各種自然災害、惡劣自然威脅可能來自于各種自然災害、惡劣的場地環(huán)境、電磁輻射和電磁干擾、網絡設備的場地環(huán)境、電磁輻射和電磁干擾、網絡設備自然老化等。這些事件有時會直接威脅信息的自然老化等。這些事件有時會直接威脅信息的安全，影響信息的存儲媒質。安全，影響信息的存儲媒質。 我們主要討論人為威脅，也就是對信息的我們主要討論人為威脅，也就是對信息的人為攻擊。這些攻擊手段都是通過尋找系統(tǒng)的人為攻擊。這些攻擊手段都是通過尋找系統(tǒng)的弱點，以便達到破壞、欺騙、竊取數據等目的，弱點，以便達到破壞、欺騙、竊取數據等目的，造成經濟上和政治上不可估量的損失。根據美造成經濟上和政治上不可估量的損失。根

4、據美國國FBI的調查的調查,美國每年因為網絡安全造成的經美國每年因為網絡安全造成的經濟損失超過濟損失超過1.70億美元億美元.面對如此嚴重危害計算面對如此嚴重危害計算機數據安全的種種威脅機數據安全的種種威脅,必須采取措施確保計必須采取措施確保計算機數據的安全保密算機數據的安全保密. 確保數據安全就是采取措施免受未授權的確保數據安全就是采取措施免受未授權的泄露、篡改和毀壞，主要包括數據秘密性、真泄露、篡改和毀壞，主要包括數據秘密性、真實性和完整性。實性和完整性。要確保計算機數據的安全保密，必須綜合采取要確保計算機數據的安全保密，必須綜合采取各種措施才能奏效，除法律、行政、教育等措各種措施才能奏效

5、，除法律、行政、教育等措施外，最重要的是要采取技術保護措施。施外，最重要的是要采取技術保護措施。技術措施可分為訪問控制技術和密碼技術兩大技術措施可分為訪問控制技術和密碼技術兩大類。我們主要討論密碼技術類。我們主要討論密碼技術.密碼學的發(fā)展歷程密碼學的發(fā)展歷程第一次世界大戰(zhàn)前，密碼學重要的進展很少出現第一次世界大戰(zhàn)前，密碼學重要的進展很少出現在公開文獻中在公開文獻中19181918年，年，2020世紀最有影響的分析文章，重合指數世紀最有影響的分析文章，重合指數及其在密碼學中的應用問世及其在密碼學中的應用問世19491949年，年，ShanonShanon發(fā)表了題為發(fā)表了題為“保密系統(tǒng)的通信理保密

6、系統(tǒng)的通信理論論”1949194919671967密碼學文獻很少密碼學文獻很少19761976年，年，W.Diffie,M.HellmanW.Diffie,M.Hellman提出了公開密鑰密提出了公開密鑰密碼碼19771977年，美國聯邦政府正式頒布年，美國聯邦政府正式頒布DESDES19771977年年至今，公開的密碼學研究爆炸性的增長至今，公開的密碼學研究爆炸性的增長2.2.密碼學的基本概念密碼學的基本概念通信雙方采用保密通信系統(tǒng)保護需要發(fā)送的消通信雙方采用保密通信系統(tǒng)保護需要發(fā)送的消息，使未授權者不能提取信息。發(fā)送方將要息，使未授權者不能提取信息。發(fā)送方將要發(fā)送的消息稱為明文，明文被變換

7、成看似無發(fā)送的消息稱為明文，明文被變換成看似無意義的隨機消息，稱為密文，這種變換過程意義的隨機消息，稱為密文，這種變換過程稱為加密；其逆過程，即由密文恢復出原明稱為加密；其逆過程，即由密文恢復出原明文的過程稱為解密。對明文進行加密操作的文的過程稱為解密。對明文進行加密操作的人員稱為加密員或密碼員。密碼員對明文進人員稱為加密員或密碼員。密碼員對明文進行加密時所采用的一組規(guī)則稱為加密算法。行加密時所采用的一組規(guī)則稱為加密算法。 傳送消息的預定對象稱為接收者，接收者傳送消息的預定對象稱為接收者，接收者對密文進行解密時所采用的一組規(guī)則稱為解密對密文進行解密時所采用的一組規(guī)則稱為解密算法。加密和解密算法

8、的操作通常都是在一組算法。加密和解密算法的操作通常都是在一組密鑰控制下進行的，分別稱為加密密鑰和解密密鑰控制下進行的，分別稱為加密密鑰和解密密鑰。傳統(tǒng)密碼體制所用的加密密鑰和解密密密鑰。傳統(tǒng)密碼體制所用的加密密鑰和解密密鑰相同，或實質上等同，即從一個易于得出另鑰相同，或實質上等同，即從一個易于得出另一個，稱其為單鑰或對稱密碼體制。若加密密一個，稱其為單鑰或對稱密碼體制。若加密密鑰和解密密鑰不相同，從一個難于推出另一個，鑰和解密密鑰不相同，從一個難于推出另一個，則稱為雙鑰或非對稱密碼體制。密鑰是密碼體則稱為雙鑰或非對稱密碼體制。密鑰是密碼體制安全保密的關鍵，它的產生和管理是密碼學制安全保密的關鍵

9、，它的產生和管理是密碼學中的重要研究課題。中的重要研究課題。 在信息傳輸和處理系統(tǒng)中，除了預定的接在信息傳輸和處理系統(tǒng)中，除了預定的接收者外，還有非授權者，他們通過各種辦法收者外，還有非授權者，他們通過各種辦法（如搭線竊聽、電磁竊聽、聲音竊聽等）來竊（如搭線竊聽、電磁竊聽、聲音竊聽等）來竊取機密信息，稱其為截收者。截收者雖然不知取機密信息，稱其為截收者。截收者雖然不知道系統(tǒng)所用的密鑰，但通過分析可能從截獲的道系統(tǒng)所用的密鑰，但通過分析可能從截獲的密文推斷出原來的明文或密鑰，這一過程稱為密文推斷出原來的明文或密鑰，這一過程稱為密碼分析，從事這一工作的人員稱為密碼分析密碼分析，從事這一工作的人員稱

10、為密碼分析員，研究如何從密文推演出明文、密鑰或解密員，研究如何從密文推演出明文、密鑰或解密算法的學問稱為密碼分析學。對一個保密通信算法的學問稱為密碼分析學。對一個保密通信系統(tǒng)采取截獲密文進行分析的這類攻擊稱為被系統(tǒng)采取截獲密文進行分析的這類攻擊稱為被動攻擊?，F代信息系統(tǒng)還可能遭受的另一類攻動攻擊?，F代信息系統(tǒng)還可能遭受的另一類攻擊是主動攻擊，非法入侵者、攻擊者或黑客主擊是主動攻擊，非法入侵者、攻擊者或黑客主動向動向系統(tǒng)采用刪除、增添、重放、偽造等竄改手系統(tǒng)采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達到利己害人的目的。段向系統(tǒng)注入假消息，達到利己害人的目的。這是現代信息系統(tǒng)中更為棘手

11、的問題。這是現代信息系統(tǒng)中更為棘手的問題。一個密碼系統(tǒng)，它由以下幾部分組成：一個密碼系統(tǒng)，它由以下幾部分組成： 明文明文消息空間消息空間M，密文消息空間，密文消息空間C，密鑰空間，密鑰空間K，在單鑰體制下，此時密鑰在單鑰體制下，此時密鑰ke=kdK 需經安全需經安全的密鑰信道由發(fā)送方傳給接收方；加密變換的密鑰信道由發(fā)送方傳給接收方；加密變換Eke：MC，其中，其中keK，由加密器完成；解，由加密器完成；解密變換密變換Dkd：CM，由解密器實現。稱，由解密器實現。稱(M,C,K,EKe,DKd)為密碼系統(tǒng)。對于給定明文為密碼系統(tǒng)。對于給定明文消息消息mM，密鑰，密鑰keK，加密變換將明文，加密變

12、換將明文m變換為密文變換為密文c，即，即c=f(m,ke)=Eke(m)mM,keK接收方利用通過安全信道送來的密鑰接收方利用通過安全信道送來的密鑰k（kK，單鑰體制下）或用本地密鑰發(fā)生器，單鑰體制下）或用本地密鑰發(fā)生器產生的解密密鑰產生的解密密鑰kd（雙鑰體制下）控制解密（雙鑰體制下）控制解密操作操作D，對收到的密文進行變換得到明文消息，對收到的密文進行變換得到明文消息，即：即：m=Dkd(c)mM,kdK而密碼分析者，則用其選定的變換函數而密碼分析者，則用其選定的變換函數h，對截獲的密文對截獲的密文c進行變換，得到的明文是明文進行變換，得到的明文是明文空間中的某個元素空間中的某個元素,即即

13、m=h(c)一般一般mm。如果。如果m=m，則分析成功。，則分析成功。 密碼系統(tǒng)模型密碼系統(tǒng)模型為了保護信息的保密性，抗擊密碼分析為了保護信息的保密性，抗擊密碼分析,密碼密碼系統(tǒng)應當滿足下述要求：系統(tǒng)應當滿足下述要求： 系統(tǒng)即使達不到理論上是不可破的，也應系統(tǒng)即使達不到理論上是不可破的，也應當為實際上不可破的。就是說，從截獲的密文當為實際上不可破的。就是說，從截獲的密文或某些已知的明文密文對，要決定密鑰或任意或某些已知的明文密文對，要決定密鑰或任意明文在計算上是不可行的。明文在計算上是不可行的。 系統(tǒng)的保密性不依賴于對加密體制或算法系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是

14、著名的的保密，而依賴于密鑰。這是著名的Kerckhoff原則。原則。 加密和解密算法適用于所有密鑰空間中的加密和解密算法適用于所有密鑰空間中的元素。元素。 系統(tǒng)便于實現和使用。系統(tǒng)便于實現和使用。16密碼學分類：密碼編制學和密碼分析學密碼學分類：密碼編制學和密碼分析學密碼系統(tǒng)的組成：密碼系統(tǒng)的組成：（1 1）明文空間）明文空間M M； （2 2）密文空間）密文空間C C； （3 3）密鑰空間）密鑰空間K K，對任意，對任意kKkK，k=k=（k kd d，k ke e）；）； （4)4)加密算法加密算法E E，C=EC=E（M M，k ke e）；）；（5 5）解密算法）解密算法D D，M=D

15、M=D（C C，k kd d）。）。一個密碼系統(tǒng)包含明文字母空間、密文字母空一個密碼系統(tǒng)包含明文字母空間、密文字母空間、密鑰空間和算法。密碼系統(tǒng)的兩個基本間、密鑰空間和算法。密碼系統(tǒng)的兩個基本單元是算法和密鑰。單元是算法和密鑰。密碼系統(tǒng)的兩個基本單元中，算法是相對穩(wěn)定密碼系統(tǒng)的兩個基本單元中，算法是相對穩(wěn)定的，視為常量；密鑰則是不固定的，視為變的，視為常量；密鑰則是不固定的，視為變量。為了密碼系統(tǒng)的安全，頻繁更換密鑰是量。為了密碼系統(tǒng)的安全，頻繁更換密鑰是必要的。一般來說算法是公開的，真正需要必要的。一般來說算法是公開的，真正需要保密的是密鑰。因此在密鑰的分發(fā)和存儲時保密的是密鑰。因此在密鑰的

16、分發(fā)和存儲時應當特別小心。應當特別小心。密碼體制根據密鑰可劃分為兩大類，即單鑰密碼體制根據密鑰可劃分為兩大類，即單鑰體制和雙鑰體制。體制和雙鑰體制。 密碼體制分類密碼體制分類單鑰體制的加密密鑰和解密密鑰相同。采用單鑰單鑰體制的加密密鑰和解密密鑰相同。采用單鑰體制的系統(tǒng)的保密性主要取決于密鑰的保密性，體制的系統(tǒng)的保密性主要取決于密鑰的保密性，與算法的保密性無關，即由密文和加解密算法不與算法的保密性無關，即由密文和加解密算法不可能得到明文。換句話說，算法無需保密，需保可能得到明文。換句話說，算法無需保密，需保密的僅是密鑰。密的僅是密鑰。密鑰可由發(fā)送方產生然后再經一個安全可靠密鑰可由發(fā)送方產生然后再

17、經一個安全可靠的途徑（如信使遞送）送至接收方，或由第三的途徑（如信使遞送）送至接收方，或由第三方產生后安全可靠地分配給通信雙方。如何產方產生后安全可靠地分配給通信雙方。如何產生滿足保密要求的密鑰以及如何將密鑰安全可生滿足保密要求的密鑰以及如何將密鑰安全可靠地分配給通信雙方是這類體制設計和實現的靠地分配給通信雙方是這類體制設計和實現的主要課題。密鑰產生、分配、存儲、銷毀等問主要課題。密鑰產生、分配、存儲、銷毀等問題，統(tǒng)稱為密鑰管理。這是影響系統(tǒng)安全的關題，統(tǒng)稱為密鑰管理。這是影響系統(tǒng)安全的關鍵因素，即使密碼算法再好，若密鑰管理問題鍵因素，即使密碼算法再好，若密鑰管理問題處理不好，就很難保證系統(tǒng)的

18、安全保密。處理不好，就很難保證系統(tǒng)的安全保密。雙鑰體制是由雙鑰體制是由Diffie和和Hellman于于1976年首先年首先引入的。采用雙鑰體制的每個用戶都有一對選引入的。采用雙鑰體制的每個用戶都有一對選定的密鑰：一個是可以公開的，可以像電話號定的密鑰：一個是可以公開的，可以像電話號碼一樣進行注冊公布；另一個則是秘密的。因碼一樣進行注冊公布；另一個則是秘密的。因此雙鑰體制又稱為公鑰體制。此雙鑰體制又稱為公鑰體制。雙鑰密碼體制的主要特點是將加密密鑰和解雙鑰密碼體制的主要特點是將加密密鑰和解密密鑰分開，因而可以實現多個用戶加密的消密密鑰分開，因而可以實現多個用戶加密的消息只能由一個用戶解讀，或由一

19、個用戶加密的息只能由一個用戶解讀，或由一個用戶加密的消息而使多個用戶可以解讀。前者可用于公共消息而使多個用戶可以解讀。前者可用于公共網絡中實現保密通信，而后者可用于實現對用網絡中實現保密通信，而后者可用于實現對用戶的認證。戶的認證。根據對明文的劃分與密鑰的使用方法不同根據對明文的劃分與密鑰的使用方法不同,可可將密碼體制分為兩種方式：將密碼體制分為兩種方式： 一是明文消息按一是明文消息按字符（如二元數字）逐位地加密，稱之為流密字符（如二元數字）逐位地加密，稱之為流密碼或序列密碼；另一種是將明文消息分組（含碼或序列密碼；另一種是將明文消息分組（含有多個字符），逐組地進行加密，稱之為分組有多個字符）

20、，逐組地進行加密，稱之為分組密碼。密碼。nikmEcnikmEceiiiii1),(1),(密碼體制一般可分為密碼體制一般可分為傳統(tǒng)密碼傳統(tǒng)密碼序列密碼、序列密碼、分組密碼、分組密碼、公鑰密碼、公鑰密碼、量子密碼體制。量子密碼體制。廣泛應用于軍事、商業(yè)經濟、網絡間的通信等領廣泛應用于軍事、商業(yè)經濟、網絡間的通信等領域，涉及了數學、物理、計算機科學、電子學、域，涉及了數學、物理、計算機科學、電子學、系統(tǒng)工程、語言學等學科內容。系統(tǒng)工程、語言學等學科內容。密碼分析者攻擊密碼的方法主密碼分析者攻擊密碼的方法主要有以下三種要有以下三種窮舉攻擊窮舉攻擊統(tǒng)計分析攻擊統(tǒng)計分析攻擊數學分析攻擊數學分析攻擊密碼

21、編制與密碼分析示意圖 M M=DAB（C） 明文 C=EAB(M)密文 明文 密鑰KAB 密鑰KAB密碼分析員發(fā)送方A接收方B密碼系統(tǒng)的攻擊類型的劃分是由攻擊者可獲密碼系統(tǒng)的攻擊類型的劃分是由攻擊者可獲取的信息量決定。其中，最困難的攻擊類型是取的信息量決定。其中，最困難的攻擊類型是唯密文攻擊，這種攻擊的手段一般是窮搜索法，唯密文攻擊，這種攻擊的手段一般是窮搜索法，即對截獲的密文依次用所有可能的密鑰試譯，即對截獲的密文依次用所有可能的密鑰試譯，直到得到有意義的明文。只要有足夠多的計算直到得到有意義的明文。只要有足夠多的計算時間和存儲空間，原則上窮舉攻擊總是可以成時間和存儲空間，原則上窮舉攻擊總是

22、可以成功的。但實際中，任何一種能保障安全要求的功的。但實際中，任何一種能保障安全要求的實用密碼都會設計得使這一方法在實際上是不實用密碼都會設計得使這一方法在實際上是不可行的。敵手因此還需對密文進行統(tǒng)計分析，可行的。敵手因此還需對密文進行統(tǒng)計分析，為此需要知道被加密的明文的類型，比如英文為此需要知道被加密的明文的類型，比如英文文本、法文文本、法文 根據密碼分析者可利用的數據來分類根據密碼分析者可利用的數據來分類文本、文本、MD-DOS執(zhí)行文件等。唯密文攻擊時，執(zhí)行文件等。唯密文攻擊時，敵手知道的信息量最少，因此最易抵抗。然而，敵手知道的信息量最少，因此最易抵抗。然而，很多情況下，敵手可能有更多的

23、信息，也許能很多情況下，敵手可能有更多的信息，也許能截獲一個或多個明文及其對應的密文，也許知截獲一個或多個明文及其對應的密文，也許知道消息中將出現的某種明文格式。例如道消息中將出現的某種明文格式。例如ps格式格式文件開始位置的格式總是相同的，電子資金傳文件開始位置的格式總是相同的，電子資金傳送消息總有一個標準的報頭或標題。這時的攻送消息總有一個標準的報頭或標題。這時的攻擊稱為已知明文攻擊，敵手也許能夠從已知的擊稱為已知明文攻擊，敵手也許能夠從已知的明文被變換成密文的方式得到密鑰。明文被變換成密文的方式得到密鑰。根據密碼分析者可利用的數據來根據密碼分析者可利用的數據來分類，破譯密碼的類型分為三種

24、分類，破譯密碼的類型分為三種僅知密文攻擊僅知密文攻擊已知明文攻擊：計算機程序易受這種攻擊已知明文攻擊：計算機程序易受這種攻擊選擇明文攻擊：計算機文件系統(tǒng)和數據庫選擇明文攻擊：計算機文件系統(tǒng)和數據庫易受這種攻擊易受這種攻擊 攻擊類型分類人為攻擊可分為被動攻擊和主動攻擊人為攻擊可分為被動攻擊和主動攻擊 被動攻擊被動攻擊-即竊聽，是對系統(tǒng)的保密性即竊聽，是對系統(tǒng)的保密性進行攻擊，如搭線竊聽、對文件或程序的非法進行攻擊，如搭線竊聽、對文件或程序的非法拷貝等，以獲取他人的信息。被動攻擊又分為拷貝等，以獲取他人的信息。被動攻擊又分為兩類，一類是獲取消息的內容，很容易理解；兩類，一類是獲取消息的內容，很容易

25、理解；第二類是進行業(yè)務流分析，假如我們通過某種第二類是進行業(yè)務流分析，假如我們通過某種手段，比如加密，使得攻擊者從截獲的消息無手段，比如加密，使得攻擊者從截獲的消息無法得到消息的真實內容，然而敵手卻有可能獲法得到消息的真實內容，然而敵手卻有可能獲得消息的格式、確定通信雙方的位置和身份以得消息的格式、確定通信雙方的位置和身份以及通信的次數和消息的長度，這些信息可能對及通信的次數和消息的長度，這些信息可能對通信雙方來說是敏感的。通信雙方來說是敏感的。 被動攻擊因不對消息做任何修改，因而是被動攻擊因不對消息做任何修改，因而是難以檢測的，所以抗擊這種攻擊的重點在于預難以檢測的，所以抗擊這種攻擊的重點在

26、于預防而非檢測。防而非檢測。主動攻擊主動攻擊這種攻擊包括對數據流的某些這種攻擊包括對數據流的某些篡改或產生某些假的數據流。主動攻擊又可分篡改或產生某些假的數據流。主動攻擊又可分為以下三個子類：為以下三個子類：中斷：是對系統(tǒng)的可用性進行攻擊，如破中斷：是對系統(tǒng)的可用性進行攻擊，如破壞計算機硬件、網絡或文件管理系統(tǒng)。壞計算機硬件、網絡或文件管理系統(tǒng)。篡改：是對系統(tǒng)的完整性進行攻擊，如修篡改：是對系統(tǒng)的完整性進行攻擊，如修改數據文件中的數據、替換某一程序使其執(zhí)行改數據文件中的數據、替換某一程序使其執(zhí)行不同的功能、修改網絡中傳送的消息內容等。不同的功能、修改網絡中傳送的消息內容等。偽造：是對系統(tǒng)的真實

27、性進行攻擊。如在偽造：是對系統(tǒng)的真實性進行攻擊。如在網絡中插入偽造的消息或在文件中插入偽造的網絡中插入偽造的消息或在文件中插入偽造的記錄。記錄。 絕對防止主動攻擊是十分困難的，因為需絕對防止主動攻擊是十分困難的，因為需要隨時隨地對通信設備和通信線路進行物理保要隨時隨地對通信設備和通信線路進行物理保護，因此抗擊主動攻擊的主要途徑是檢測，以護，因此抗擊主動攻擊的主要途徑是檢測，以及對此攻擊造成的破壞進行恢復。及對此攻擊造成的破壞進行恢復。 1.2 一些簡單密碼體制與它的破譯1.置換密碼把明文中的字母重新排列，字母本身不變例：明文為this cryptosystem is not secure。 排

28、成矩陣： thiscr yptosy stemis notsec ure密文為tysnu hptor itete soms csie rysc。 2.單表代替密碼首先構造一個密文字母表，然后用密文字母表首先構造一個密文字母表，然后用密文字母表中的字母或字母組來代替明文字母表中的字中的字母或字母組來代替明文字母表中的字母或字母組，各字母或字母組的相對位置不母或字母組，各字母或字母組的相對位置不變，但其本身改變了。變，但其本身改變了。設設A=aA=a0 0，a a1 1，a an-1n-1 為含為含n n個字母的明文字個字母的明文字母表，母表，B=bB=b0 0，b b1 1，b bn-1n-1

29、為含為含n n個字母的個字母的密文字母表，定義一個由密文字母表，定義一個由A A到到B B的一一映射。的一一映射。f f：ABAB，f f（a ai i）=b=bi i設明文設明文M=M=（m m0 0，m m1 1，m mn-1n-1），則相應的密文），則相應的密文C=C=（f f（m m0 0），），f f（m m1 1），），f f（m mn-1n-1）1. 因子因子設設a，b(b0)是兩個整數，如果存在另一整數是兩個整數，如果存在另一整數m，使得，使得a=mb，則稱，則稱b整除整除a，記為，記為b|a，且，且稱稱b是是a的因子。的因子。 數論簡介整數具有以下性質：整數具有以下性質： a

30、|1，那么，那么a=1。 a|b且且b|a，則，則a=b。 對任一對任一b (b0)，b|0。 b|g，b|h，則對任意整數，則對任意整數m、n有有b|(mg+nh)。這里只給出的證明，其他這里只給出的證明，其他3個性質的證明個性質的證明都很簡單。都很簡單。性質的證明：性質的證明： 由由b|g，b|h知，存在整數知，存在整數g1、h1，使得，使得g=bg1,h=bh1所以所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此因此b|(mg+nh)。2. 素數素數稱整數稱整數p(p1)是素數，如果是素數，如果p的因子只有的因子只有1，p。任一整數任一整數a(a1)都能惟一地分解為以下形式

31、：都能惟一地分解為以下形式： 其中其中p1p2pt是素數，是素數，ai0(i=1,t)。例如。例如91=711，11011=7112131212ttappp這一性質稱為整數分解的惟一性，也可如下這一性質稱為整數分解的惟一性，也可如下陳述：陳述： 設設P是所有素數集合，則任意整數是所有素數集合，則任意整數a (a1)都都能惟一地寫成以下形式：能惟一地寫成以下形式：其中其中ap0,等號右邊的乘積項取所有的素數，等號右邊的乘積項取所有的素數，然而大多指數項然而大多指數項ap為為0。相應地，任一正整數。相應地，任一正整數也可由非也可由非0指數列表表示。例如：指數列表表示。例如： 11011可表可表示為

32、示為a7=1,a11=2,a13=1。兩數相乘等價于對應的指數相加，即由兩數相乘等價于對應的指數相加，即由k=mn 可得：對每一素數可得：對每一素數p,kp=mp+np。而由。而由a|b可得：可得： 對每一素數對每一素數p,apbp。pap Pap設設n是一正整數，是一正整數，a是整數，如果用是整數，如果用n除除a，得商為，得商為q，余數為余數為r，則，則 a=qn+r,0rn, 其中其中 為小于或等于為小于或等于 的最大整數。的最大整數。用用a mod n表示余數表示余數r，則，則 。如果如果(a mod n)=(b mod n)，則稱兩整數，則稱兩整數a和和b模模n同同余，記為余，記為ab

33、 mod n。稱與。稱與a模模n同余的數的全體為同余的數的全體為a的同余類，記為的同余類，記為a，稱，稱a為這個同余類的表示元素。為這個同余類的表示元素。注意：注意： 如果如果a0(mod n)，則，則n|a。 模運算aqnmodaanannna同余有以下性質：同余有以下性質： 若若n|(a-b)，則，則ab mod n。 (a mod n)(b mod n)，則，則ab mod n。 ab mod n,則則ba mod n。 ab mod n,bc mod n,則則ac mod n。從以上性質易知，同余類中的每一元素都可從以上性質易知，同余類中的每一元素都可作為這個同余類的表示元素。作為這個

34、同余類的表示元素。求余數運算（簡稱求余運算）求余數運算（簡稱求余運算）a mod n將整將整數數a映射到集合映射到集合0,1, ,n-1，稱求余運算在，稱求余運算在這個集合上的算術運算為模運算，模運算有這個集合上的算術運算為模運算，模運算有以下性質：以下性質： (a mod n)+(b mod n) mod n=(a+b) mod n。 (a mod n)-(b mod n) mod n=(a-b) mod n。 (a mod n)(b mod n) mod n=(ab) mod n。性質的證明：性質的證明： 設（設（a mod n）=ra，(b mod n)=rb，則存在整數，則存在整數j、

35、k使得使得a=jn+ra，b=kn+rb。因此因此(a+b) mod n=(j+k)n+ra+rb mod n=(ra+rb) mod n= (a mod n)+(b mod n) mod n （證畢）（證畢）性質、的證明類似。性質、的證明類似。最大公因數最大公因數稱稱c是兩個整數是兩個整數a、b的最大公因數，如果的最大公因數，如果 c是是a的因子也是的因子也是b 的因子，即的因子，即c是是a、b的的公因子。公因子。 a和和b的任一公因子，也是的任一公因子，也是c的因子。的因子。表示為表示為c=gcd(a, b)或或c=(a,b)。由于要求最大公因子為正，所以由于要求最大公因子為正，所以gcd

36、(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一。一般般gcd(a,b)=gcd(|a|,|b|)。由于任一非。由于任一非0整數能整數能整除整除0，可得，可得gcd(a,0)=|a|。如果將。如果將a，b都表都表示為素數的乘積，則示為素數的乘積，則gcd（a, b）極易確定。）極易確定。例如：例如：300=22315218=2132gcd(18,300)=213150=6一般由一般由c=gcd(a,b)可得：可得： 對每一素數對每一素數p，cp=min(ap,bp)。由于確定大數的素因子不很容易，所以這種由于確定大數的素因子不很容易，所以這種方法不能直接用于求兩個大

37、數的最大公因子方法不能直接用于求兩個大數的最大公因子.如果如果gcd(a,b)=1，則稱，則稱a和和b互素。互素。于是下面討論用輾轉相除法求兩個大數的最于是下面討論用輾轉相除法求兩個大數的最大公因子。大公因子。定理定理:設設a,b,c是任意三個不全為零的整數是任意三個不全為零的整數,且且a=bn+c,0cn,則則gcd(a,b)=gcd(b,c),或記為或記為(a,b)=(b,c)再用再用b除除c,一直繼續(xù)下去一直繼續(xù)下去,直到余數為直到余數為0,則最后則最后一個非一個非0余數即為余數即為a和和b的最大公因數的最大公因數.最小公倍數最小公倍數稱稱c是兩個整數是兩個整數a、b的的最小公倍數最小公

38、倍數，如果，如果 c是是a的倍數也是的倍數也是b 的倍數，即的倍數，即c是是a、b的的公倍數。公倍數。 c是一切公倍數中最小的正數。是一切公倍數中最小的正數。表示為表示為c=lcma, b或或c=a,b。幾類單表代替密碼幾類單表代替密碼加法密碼：加法密碼：f f（a ai i）=a=aj j，ji+kji+k（mod nmod n），），0 0k kn n，取取n=26n=26。乘法密碼：乘法密碼：f f（a ai i）=a=aj j，jikjik（mod nmod n），），0 0k kn n，（k k，n n）=1=1。仿射密碼：仿射密碼：f f（a ai i）=a=aj j，jikjik

39、1 1+k+k0 0（mod nmod n），（），（k k1 1，n n）=1=1。密鑰詞組代替密碼密鑰詞組代替密碼用一詞組或短語作密鑰，去掉密用一詞組或短語作密鑰，去掉密鑰中的重復字母，把結果作為矩陣的第一行，其次鑰中的重復字母，把結果作為矩陣的第一行，其次從明文字母表中補入其余字母，最后按某一順序從從明文字母表中補入其余字母，最后按某一順序從矩陣中取出字母構成密文字母表。矩陣中取出字母構成密文字母表。例：密鑰為例：密鑰為red star，明文為，明文為data security。字母與數字對應表abcdefghi012345678jklmnopqr91011121314151617stu

40、vwxyz18192021222324253.單表代替密碼的統(tǒng)計分析極高頻率字母組：極高頻率字母組：e z次高頻率字母組：次高頻率字母組：taonirsh jvbhdilc中等頻率字母組：中等頻率字母組：dlucm xseyr低頻率字母組：低頻率字母組：pfywgbv tfkawnp甚低頻率字母組：甚低頻率字母組：jkqxz mqgou雙字母：雙字母：th he in er an re ed 三字母：三字母：the ing and her are ent英文字母出現的頻率如表英文字母出現的頻率如表1-2.舉例YKHLBA JCZ SVIJ JZB LZVHI JCZ VHJ DR IZXKHL

41、BA VSS RDHEI DR YVJV LBXSKYLBA YLALJVS IFZZXC CVI LEFHDNZY EVBTRDSY JCZ FHLEVHT HZVIDB RDH JCLI CVI WZZB JCZ VYNZBJ DR ELXHDZSZXJHDBLXI JCZ XDEFSZQLJT DR JCZ RKBXJLDBI JCVJ XVB BDP WZ FZHRDHEZY WT JCZ EVXCLBZ CVI HLIZB YHVEVJLXVSST VI V HZIKSJ DR JCLI HZXZBJ YZNZSDFEZBJ LB JZXCBDSDAT EVBT DR JCZ XLF

42、CZH ITIJZEI JCVJ PZHZ DBXZ CDBILYZHZY IZXKHZ VHZ BDP WHZVMVWSZZe，Va，三字母單詞JCZ？e：the2字母單詞VIa？：an，as，am，at，I s三字母單詞VHZa？e：are，age Hr。三字母單詞JZBte？： Bn4字母單詞JCLIth？s： LI4字母單詞WZZB？een： Wb6字母單詞HZVIDBreas？n： Do2字母單詞DRo？： Rf3字母單詞BDPno？： Pw4字母單詞DBXZon？e： Xc4字母單詞EVBT？any： Em2字母單詞WTB？： Ty3字母單詞BDPno？： Pw4字母單詞DBXZo

43、n？e： Xc4字母單詞EVBT？any： EmIFZZXCs？eech： FpFZHRDHEZYperforme？：YdVSSa？： SlJZXCBDSDATtechnono？yAg3字母單詞結尾LBAi？g： BnYKHLBAd？ring： KuLEFHDNZYimpro？ed： NvWHZVMVWSZbrea？able Mk4.多表代替密碼構造構造d個密文字母表個密文字母表設設B Bj j=b=bj0j0，b bj1j1，b bjn-1jn-1 ，j=0j=0，1 1，d-1d-1為為d d個含個含n n個字母的密文字母表個字母的密文字母表,A=a,A=a0 0，a a1 1，a an-

44、1n-1 為含為含n n個字母的明文字母表，定義個字母的明文字母表，定義d d個映個映射。射。f fj j：ABABj j，f fj j（a ai i）=b=bjiji設明文設明文M=M=（m m0 0，m m1 1，m mn-1n-1），則相應的密文），則相應的密文C=C=（f f0 0（m m0 0），），f f1 1（m m1 1），），f fd-1d-1（m md-1d-1），）， f f0 0（m md d），）， ）例:Vigenere密碼若若K=k1k2km， M=m1m2mn， C=c1c2cn其中其中cimi+ki（mod 26）至于密鑰至于密鑰k可以通過周期性地延長，周而復

45、始，反復可以通過周期性地延長，周而復始，反復以至無窮。即以至無窮。即ki+lm=ki例：密鑰為例：密鑰為cipher，明文為，明文為thiscryptosystem。明文明文:19 7 8 18 2 17 24 15 19 14 18 24 18密鑰密鑰:2 8 15 7 4 17 2 8 15 7 4 17 2 密文密文:21 15 23 25 6 8 0 23 8 21 22 15 20 這樣密文串為這樣密文串為VPXZGIAXIVWPUBTT.例:已知vigenere密碼中,密鑰為cipher,試對密文VPXZGIAXIVWPUBTT解密.解:密文:21 15 23 25 6 8 0 2

46、3 8 21 22 15 20 密鑰:2 8 15 7 4 17 2 8 15 7 4 17 2 明文:19 7 8 18 2 17 24 15 19 14 18 24 18于是明文為thiscryptosystem.例：試破譯vigenere密碼加密得到的密文UFQUIUDWFHGLZARIHWLLWYYFSYYQATJPFKMUXSSWWCSVFAEVWWGQCMVVSWFKUTBLLGZFVITYOEIFASJWGGSJEPNSUETPTMPOPHZSFDCXEPLZQWKDWFXWTHASPWIUOVSSSFKWWLCCEZWEUEHGVGLRLLGWOFKWLUWSHEVWSTTUARCWHWBVTGNITJRWWKCOTPGMILRQESKWGYHAENDIULKDHZIQASFMPRGWRVPBUIQQDSVMPFZMVEGEEPFODJQCHZIUZZM5.對對Vigenere密碼的分析密碼的分析確定密鑰字的長度確定密鑰字的長度m：1Kasiski測試，測試，2使用重合指數。使用重合指數。 DWF 7 112 105 EVW 47 162 115 LLG 64 149 85 BJW 78 278 200由于由于105、115、85、200的最大公約數為的最大公約數為5，所以它非?？赡苁敲荑€字的長度。所