《Python工程應用-網絡信息安全》課件-chap3

chap.3密碼學編程網絡信息安全

通常，密碼是信息安全的核心保護措施。無論是存儲器或信道中的數據，都可以用密碼進行保護。密碼在早期僅對文字或數碼進行保護，隨著通信技術的發(fā)展，密碼也可以應用于語音、圖像、數據等。在現代信息安全領域，密碼學/技術進一步發(fā)展，衍生出一些新的保密應用。這些應用除了機密性保護之外，還可以對信息的完整性、不可否認性進行保護。密碼技術（Cryptography）包含了密碼學（Cryptography）和密碼分析學（Cryptanalysis）兩大分支，互為矛盾，對抗發(fā)展。本章內容對密碼學的典型加密算法Python程序實現進行介紹。3.1密碼學基礎3.1.1密碼學基礎定義

密碼學是研究如何隱密地傳遞信息的學科，是數學和計算機科學的分支。密碼學和信息論密切相關，往往也是信息安全相關議題的核心。與信息隱藏不同，密碼學的首要目的是隱藏信息的涵義，并不隱藏信息的存在。當前，除了密碼學產生的通信領域，密碼學也已被應用在日常生活信息安全的方方面面了。2.要素一套完整的密碼學實現規(guī)則、實例方案，稱為密碼體制。密碼體制的設計圍繞著明文、密文、密鑰、加密、解密幾個要素展開，其相互關系可以用圖3-1密碼體制框圖概括描述。

明文：是指沒有進行變換，能夠直接代表原文含義的數據，用m表示。全體明文m的集合構成明文空間，記為M。密文：是指明文經過變換后，隱藏了原文含義的數據，用c表示。全體密文c的集合構成密文空間，記為C。加密：是指將明文轉換成密文的實施過程。解密：是指將密文轉換成明文的實施過程。加密和解密互為反變換。隨著基于數學密碼技術的發(fā)展，加、解密方法一般用數學算法實現，因此分別稱為加密算法和解密算法，其中加密算法記為E，解密算法記為D。

密鑰：是指控制加密和解密的關鍵要素，分為加密密鑰和解密密鑰。通常每個密碼體制的密鑰k都有加密密鑰ke和解密密鑰kd組成。全體密鑰的集合構成密鑰空間，記為K。密鑰空間中不同密鑰的個數成為密鑰量是衡量密碼體制安全性的一個重要指標。因此，將解密過程通常可以形式化的表示為下式。3.發(fā)展密碼技術自古有之，回顧密碼學發(fā)展歷史，基本可以劃分為三個階段。第一個階段，是從古代到19世紀末，長達數千年。這個時期，由于生產力低下，產生的許多密碼體制都是可用紙筆或者簡單機械實現加解密的，所以稱這個時期產生出的密碼體制為“古典密碼體制”。古典密碼體制主要有兩大類：一類是單表代換體制，另一類是多表代換體制。用“手工作業(yè)”進行加解密，密碼分析亦是“手工作業(yè)”。這個階段所產生出來的所有密碼體制幾乎已全部被破譯了。第二個階段，是從20世紀初到20世紀50年代末。在這半個世紀期間，由于莫爾斯發(fā)明了電報，繼而電報通信建立起來了。為了適應電報通信，密碼設計者設計出了一些采用復雜的機械和電動機械設備實現加解密的體制。這個時期產生出的密碼體制為“近代密碼體制”。近代密碼體制主要是像轉輪機那樣的機械和電動機械設備。這些密碼體制基本上已被證明是不保密的，但是要想破譯它們往往需要很大的計算量。第三個階段，是從Shannon于1949年發(fā)表的劃時代論文《保密通訊系統(tǒng)理論》(CommunicationTheoryofSecrecySystem)開始的，這篇論文證明了密碼編碼需要堅實的數學基礎。在這一時期，微電子技術的發(fā)展使電子密碼走上了歷史舞臺，共同催生了“現代密碼體制”。特別是20世紀70年代中期，DES密碼算法的公開發(fā)表，以及公開密鑰思想的提出，更是促進了當代密碼學的蓬勃發(fā)展。到了20世紀80年代，大規(guī)模集成電路技術和計算機技術的迅速發(fā)展，現代密碼學得到了更加廣泛的應用。當前，隨著量子等新興技術的不斷出現與發(fā)展，密碼技術進入了一個全新的發(fā)展期。量子密碼術與傳統(tǒng)的密碼系統(tǒng)不同，它依賴于物理學作為安全模式的關鍵方面而不是數學，也預示著密碼新時代的到來。3.1.2密碼體制分類

密碼體制劃分方法大致分為三種：換位與代替密碼體制、序列與分組密碼體制、對稱與非對稱密鑰密碼體制。除此之外，單向函數還可用來保護數據的完整性。換位與代替密碼體制

在對明文進行加密變換時，通?？梢圆捎锰娲蛽Q位兩種方法。替代是將明文中的一個字母用密文字母表中其他字母替代。換位是對數據的位置進行的置換的方法。2.分組與序列密碼體制

分組密碼是對數據定長的塊上進行加解密操作。序列密碼的加密變換只改變一位明文，故它可以看成是塊長度為1的分組密碼。3.對稱與非對稱密鑰密碼體制對稱密碼體制（或單密鑰密碼密碼體制）的加密密鑰與解密密鑰相同。非對稱密碼體制（或雙密鑰密碼密碼體制）的加密密鑰與解密密鑰不相同。進一步，如果在一個雙密鑰密碼密碼體制中，加密密鑰ke計算解密密鑰kd是困難的，公開ke不會損害kd的安全性，則可以將加密密鑰ke公開，這樣的密碼體制稱為公鑰密碼體制。還有些學者，將單向散列函數（或稱為：單向函數,One-wayfunction)歸為同對稱與非對稱密鑰密碼并列的密碼體制。單向函數是一種具有下述特點的單射函數：對于每一個輸入，函數值都容易計算（多項式時間），但是給出一個隨機輸入的函數值，算出原始輸入卻比較困難（無法在多項式時間內使用確定性圖靈機計算）。由于單向函數的結果值，對于輸入非常敏感，即使輸入有微量變化，輸出都會有劇烈變化，因此被用于檢測數據的完整性是否遭到破壞。密碼體制還可以按照加密對象、軟硬件等進行劃分，在此不再贅述。3.2古典密碼編程3.2.1古典密碼思想

古典密碼編碼方法主要有兩種，即：置換和代換。把明文中的字符重新排列，字母本身不變，但其位置改變了，這樣編成的密碼稱為置換密碼。最簡單的置換密碼是把明文中的字母順序倒過來，然后截成固定長度的字母組作為密文。代換密碼則是將明文中的字符替代成其他字符。在進行代換時，可以采用一張代換表，稱為單表代換。單表代替的缺點就是，明文字符相同,則密文字符也相同，因此就無法隱藏明文的字符統(tǒng)計特性，因此安全性較差（字母統(tǒng)計特性如圖3-2）。為了克服這一確定，人們采用周期順次使用多張代換表的方法實現加密，這種方法就是多表代換。比較置換和代換密碼的特點可知，移位密碼位置變但形態(tài)不變，代替密碼形態(tài)變但位置不變。將代替密碼和移位密碼輪番使用,就可以發(fā)揮各自的長處,克服對方的缺點，這也是現代密碼可借鑒的設計思想。3.2.2移位密碼

移位密碼將明文中的字母順序被重新排列以形成密文。其中純文本中的每個字符都是水平寫入的，具有指定的字母寬度，而密文垂直寫入，可創(chuàng)建完全不同于明文的密文。例如：純文本helloworld的柱狀轉置技術如下圖3-3所示

明文字符串水平放置，密文以垂直格式創(chuàng)建：“holewdlolr”。接收方必須使用相同的表，才能將密文解密為明文。以下是實現代碼(transposition.py)。加密函數encryptMessage首先創(chuàng)建一個key個元素的空列表，每個元素用來存儲一列?；為了使得形成一個完整的方陣，需要使用函數對輸入的消息補齊長度，長度為行數乘列數(key)?；設置將當前列號作為指針?，順序讀取該列的明文(相鄰兩個字符相互間隔key個字符)內容存儲到對應列中，具體過程如圖3-4所示。解密函數decryptMessage工作方式與encryptMessage函數類似，只是按照行數的跨度提取字符?，最后將解密明文分別填充到各行組成的列表中。3.2.3置換密碼

置換密碼利用置換表對明文進行置換，置換的方法可以采用加法、乘法、仿射、密鑰短語等。1.加法密碼加法密碼是用明文字母在字母表中后面第k個字母來代換，得到的就是密文字母。K=3時的加法密碼就是密碼學中廣為人知的凱撒密碼?！皭鹑雒艽a”是古羅馬愷撒大帝在西塞羅戰(zhàn)役時，用來保護重要軍情的加密系統(tǒng)，記載于（《高盧戰(zhàn)記》）。作為一種最古老的對稱加密體制，它的加密原理是通過移動指定位數的字母，以此實現加密和解密。所有字母都在字母表上向后(或者向前)，按照固定數字進行偏移后，通過替換形成密文。而進行偏移所按照的固定數字稱之為偏移量。例如，所有的字母A都被替換成了C，而B變成D，到了字母表后面，Y也被替換成A，Z被替換成B，則它的偏移量是2，若偏移量為3時，明密對照關系如圖3-5所示：由此可見，凱撒密碼加解密的密鑰就是偏移的位數。以下是加法密碼的實現代碼。

上述代碼encrypt為加密函數，該函數首先將待加密的消息全部轉換為大寫字母?，然后進行處理；對于非字母的字符忽略不處理?；在進行移位時在原字母序號基礎上加上秘鑰值，然后以width為除數求余數，以“A”的ASIIC碼為基址計算密文字符?。上述程序中，函數ord(c)的參數是長度為1的字符串(即：字符)。當參數為統(tǒng)一對象時（unicodeobject），返回能代表該字符的統(tǒng)一編碼，當參數為8比特的字符串時，返回該字節(jié)的值。例如，ord(‘a’)返回整形數值97，ord(u’\u2020’)返回8224。函數chr(i)返回一個字符，字符的ASCII碼等于參數中的整形數值。例如chr(97)返回字符’a’，該方法是ord()的反方法。參數必須是0-255的整形數值，否則會拋出valueError錯誤。解密函數decrypt操作與encrypt相反。通過對加法密碼的算法分析可知，加法密碼的密鑰空間僅為25。2.乘法密碼在使用凱撒密碼技術時，加密和解密符號涉及使用簡單的加法或減法，基本過程將值轉換為數字。如果使用乘法，也可用于轉換為密文。乘法密碼的加解密公式如下：注意：k-1不是k的倒數，而是k模q的逆元。以密鑰為7為例，進行加密的密文對應關系如下圖3-6所示。

由于并不是每個整數都可以作為乘法密的密鑰，很多數字會破壞明密文的映射關系，乘法密碼的密碼空間大小是Φ(n)，Φ(n)是歐拉函數（小于n且與n互素的數的個數）。當n為26字母，則與26互素的數是1、3、5、7、9、11、15、17、19、21、23、25，共有12個，即Φ(n)=12。因此乘法密碼的密鑰空間為12（此外，k=1時加密變換為恒等變換）。

乘法密碼的解密密鑰不是原密鑰，而是前面所述的密鑰對于26的逆元。逆元是指對于同余方程滿足：ax≡1(modb),稱x為a關于模b的乘法逆元,計算逆元的常見方法有：擴展歐幾里得算法(見3.5.2節(jié)介紹)、費馬小定理/歐拉定理、遞推求逆元、等幾種。

以下是乘法密碼的實現代碼(MultiplicativeCipher.py)。decrypt函數，在進行移位時在原字母序號基礎上乘秘鑰值，然后以width為除數求余數，以“A”的ASIIC碼為基址計算密文字符?；進行解密的函數decrypt使用的秘鑰是key的模26逆元，通過inverseElement函數計算得出?。3.仿射密碼仿射密碼是乘法密碼和加法密碼算法的組合。以下是乘法密碼的實現代碼(AffineCipher.py)。由上述代碼可以看出，放射密碼就是加法密碼和乘法密碼的結合?，通過這樣的結合秘鑰空間擴展為12×26=312，但依然很有限。3.2.4維吉尼亞密碼

如前所述，單表代替的密碼使用一張表進行代替，安全性很差。人們提出采用多張表進行周期使用的方法。在多表代替密碼中，代替表的使用由密鑰來指示，維吉尼亞密碼就是這種方法的典型代表。維吉尼亞密碼與凱撒算法類似，只有一個主要區(qū)別，即：維吉尼亞密碼包含一個字符移位的表，而維吉尼亞密碼包含多個字母移位的表，全部的密碼表見下圖3-7所示。

上圖3-7中，橫排第一行為明文，左側第一列為密鑰字母，中間區(qū)域是密文，例如：依據圖中明密對照表，密鑰字母為d，明文字母為b時查表得密文字母為e?？梢栽O定一個周期，循環(huán)使用維吉尼亞密碼表的不同列，就行成了多表加密。以下是維吉尼亞密碼的實現代碼(Vigenere.py)

上述函數translateMessage可以工作于加密（encrypt）和解密（decrypt）兩種模式。首先計算待處理(加45密或解密)字母在LETTERS表中的位置?(通過字符串函數find查找)；加密時，根據密鑰k的每個字母在LETTERS表中的序號，得到移位數，利用移位數執(zhí)行加法密碼?，最終對所有明文加密。解密方法，反之進行?。秘鑰將被循環(huán)使用，從而形成多表的密碼替代?。顯然，對于秘鑰“ASIMOV”，上述代碼會依次使用A、S、I、M、O、V對應的共6張表。

近代密碼學實際是古典密碼學多表替代方法的機械化，下圖3-8即為著名的恩尼格瑪機鍵盤與轉子結構。該結構由至少1個鍵盤、1個轉子和顯示器構成。按下鍵盤中的字符按鈕將接通電源，電流經導線和轉子上的連接線觸發(fā)顯示器顯示，形成明密映射。當鍵盤每按下一次，轉子會發(fā)生轉動，則明密映射關系也發(fā)生變化，就形成了多表密碼替代。由于實際的恩尼格碼機有多個轉子和反射器，因此形成1億億余種可能。3.3分組密碼編程3.3.1分組密碼基礎

1.分組密碼提出分組密碼（BlockCipher），又稱塊密碼，它是將明文消息編碼后的數字序列劃分成固定長度的分組，各分組作為一個整體在密鑰控制下變換成等長度的密文組。分組密碼算法的設計是由香農(C.E.Shannon)提出的。為了確保分組密碼的安全性，香農充分利用擴散（diffusion）和擾亂（confusion）的思想。所謂擴散的目的是讓明文中的單個數字影響密文中的多個數字，從而使明文的統(tǒng)計特征在密文中消失，相當于明文的統(tǒng)計結構被擴散；而擾亂是指讓密鑰與密文的統(tǒng)計信息之間的關系變得復雜，從而增加通過統(tǒng)計方法進行攻擊的難度。由于分組密碼的思想與現代通信的分組交換不謀而合，因此具有很好的應用價值。在現代通信系統(tǒng)中廣泛應用的分組密碼包括：DES、IDEA、SAFER、Blowfish和Skipjack等。2.Feistel網絡

在設計安全的分組加密算法時，應最大限度地抵抗現有密碼分析，如：差分分析、線性分析等，還需要考慮密碼安全強度的穩(wěn)定性。此外，用軟件實現的分組加密要保證每個組的長度適合軟件編程（二進制2n），盡量避免位置換操作，以及盡可能地使用加法、乘法、移位等處理器提供的標準指令。從硬件實現的角度，加密和解密要在同一個器件上都可以實現，即加密解密硬件實現的相似性?；谶@些考慮，大部分的分組密碼都是基于Feistel網絡這種經典結構。

Feistel網絡是由密碼學家Feistel提出的，具體結構如圖3-9所示。

Feistel提出：利用乘積密碼可獲得簡單的代換密碼。乘積密碼指順序地執(zhí)行兩個或多個基本密碼系統(tǒng)，使得最后的密碼強度高于每個基本密碼系統(tǒng)產生的結果。其思想實際上是Shannon提出的利用乘積密碼實現混淆和擴散思想的具體應用。

Feistel加密算法的輸入是分組長為2w的明文和一個密鑰k，將每組明文分成左右兩半L和R，在進行完n輪迭代后，左右兩半再合并到一起產生密文分組。第i輪迭代的前一輪輸出的函數：Feistel解密過程本質上和加密過程是一樣的，算法使用密文作為輸入，但使用子密鑰Ki的次序與加密過程相反。這一特征保證了解密和加密可采用同一算法。影響Feistel結構安全的因素主要包括：分組大小、密鑰大小、輪數、子密鑰生成算法、輪函數。3.3.2DES算法編程Feistel結構的最著名實例就是DES密碼。DES是1976年由美國國家標準（NBS）頒布，由IBM公司研制的一種算法。作為美國的商用加密標準算法DES（DataEncryptionStandard）得到了廣泛的支持和應用，極大地促進了分組密碼發(fā)展。DES以64位為分組(64位一組的明文從算法一端輸入，64位密文從另一端輸出)，加密和解密用同一密鑰，有效密鑰長度為56位（密鑰通常表示為64位數，但每個第8位用作奇偶校驗，可以忽略）。DES加密過程

DES在加密過程分為三個階段，具體描述如下(以輸入64bit明文為例)：

第一階段，用一個初始置換IP重新排列明文分組的64比特數據(如圖3-10所示)。

圖3-10中數字為二進制數的腳標序號。第二階段：進行具有相同功能的16輪循環(huán)變換，每輪變換中都含置換和代換運算(如圖3-11所示，下圖相當于圖3-9中的一輪，具體操作過程將結合后續(xù)編程進行介紹)。第三階段：最后再經過一個逆初始置換逆IP-1從而產生64比特密文。這里需要注意的是，無論是初始置換還是最終的逆初始置換，都不能增減DES的安全性。其設計的初衷并不被人所知，但是看起來其目的是將明文重新排列，使之適應8-bit寄存器。其映射規(guī)則如下：矩陣為8×8矩陣，自左至右，自上至下依次排位，矩陣中的某次位數目即為明文中該次位的比特值映射到buffer的偏移量。2.DES加解密實現下面按照DES的加密順序對DES加密的程序進行介紹。

(1)初始置換IP與IP逆變換由于上述第一階段初始置換IP與第三階段IP逆變換效果相反，原理類似，因此這里一并進行介紹。代碼如下：擴充/置換實現的代碼如下：

上述expend函數通過查表方法，對內容source進行擴展，可以看出有16個數重復出現2次。

②與子秘鑰進行混合等長的數據與子秘鑰數組作異或，代碼如下。上面代碼中，數據與子秘鑰按位作異或操作?。置換選擇的實現代碼如下：

上述代碼首先給出諸S盒的定義?；然后將輸入的數據分成8個6bit分組?；將每個分組的最高位和最低位組成二進制數作為x?；將2345組成二進制數作為y?，用x、y在S盒表中查出輸出值。上述代碼還調用了函數dataP完成P盒置換?，P盒的定義如圖3-15所示。圖中數字為二進制數的腳標序號。代碼如下：P盒置換與IP置換類似，也是進行了位置變換。④與左半部分混合與左半部分進行異或操作后交換輸出，與上面步驟3)操作類似，代碼略。3.DES子密鑰生成實現

在進行各輪循環(huán)時，使用的密鑰是不同的子密鑰，子密鑰生成首先將輸入DES的56-bit密鑰經過一個置換運算(其置換規(guī)則與上文IP矩陣類似)；然后將64-bit分成8組，每組8-bit，僅取每組前7-bit組成56-bit密鑰，則每個子密鑰是為48-bit；再進行如下圖3-16所示的移位操作，就生成了子密鑰。①密鑰置換PC-1

為了生成48-bit子密鑰，需要進行子置換，其輸入數據為旋轉后得到的密鑰舍去其中8-bit(8、16、24、32、40、48、56、64位)，而后再用一個6×8的矩陣進行置換，代碼如下：②循環(huán)左移

56-bit密鑰首先將會分成兩部分，這兩部分將會各自循環(huán)移位。其移位規(guī)則為：在第1、2、9、16輪時，兩個子部密鑰向左循環(huán)移位1-bit，在其它輪時，兩個子部密鑰向左循環(huán)移位2-bit?？梢园l(fā)現，16輪過后，兩個子部密鑰正好旋轉了28-bit，即旋轉一周。

代碼如下。

上述代碼中，根據輪次i獲得為當前輪次移位數ls?；每次循環(huán)時將最左側(0位)位數值記錄下來?；?左移一位；?把最左側一位補到右側，每完成一次移位操作就可以得到一個子密鑰。③密鑰置換PC-2子密鑰的置換PC-2實現代碼如下。DES加解密算法相同，解密子密鑰使用順序與加密相反。此外，直接對各數據獨立進行DES加密的模式稱為：ECB(電子電報密碼本ElectronicCodeBook），其缺點是：可能遭受對明文的主動攻擊，信息塊可被替換、重排、刪除、重放。為了抵御這種密碼本攻擊，DES通過初始化向(IV)）和分組密碼塊之間的相互鏈接，實現的多種改進，其中：CBC(密碼分組鏈接CipherBlockChaining，前分組加密結果作為輸入與后一分組進行混合，如圖3-17所示）、安全性好于ECB、適合于傳輸長度大于64位的報文，還可以進行用戶鑒別，是大多系統(tǒng)的標準如SSL、IPSec；CFB(密碼反饋方式CipherFeedBack）它特別適于用戶數據格式的需要，能隱蔽明文數據圖樣，也能檢測出對手對于密文的篡改；OFB(輸出反饋方式OutFeedBack）用于高速同步系統(tǒng)。對于這些DES的工作模式，將不作具體介紹。3.4序列密碼3.4.1序列密碼原理

序列一般指二進制數據流，而序列密碼是針對二進制數據流的加密。序列密碼的加密變換只改變一位明文，故它可以看成是塊長度為1的分組密碼。序列密碼是各國軍事和外交等領域使用的主要密碼體制，其主要問題是如何生成密鑰流周期長、復雜度高、隨機性特性足夠好，從而使之盡可能地接近一次一密的密碼體制。序列密碼的工作流程如圖3-18所示。其過程是，一方面將種子密鑰k導入密鑰序列生成器，生成出密鑰流，與明文流mi進行加密，生成出密文流，然后在公開信道中傳輸；另一方面通過安全信道將種子密鑰k傳給接收方，接收方亦將種子密鑰k導入密鑰序列生成器(注意要與發(fā)送方嚴格同步)，生成出密鑰流，與密文流進行解密，恢復出明文流mi。

對于二進制的明文流，E和D操作，一般是異或操作。序列密碼的關鍵在于獲得良好的偽隨機序列。這個序列應該盡量滿足以下條件：（1）0、1分布均勻（2）0、1游程分布平衡（3）所有異相自相關函數值相等（4）序列的周期足夠大，如大于1050；（5）序列易于高速生成；（6）序列的不可預測性充分大。目前通信用的偽隨機序列密鑰流，都是由偽隨機序列發(fā)生器的硬件設備產生。發(fā)生器一般包括驅動部分和非線性組合部分，其中驅動部分用一個或多個長周期線性反饋移位寄存器構成，它將控制生成器的周期和統(tǒng)計特性；非線性組合部分對驅動器各輸出序列進行非線性組合，控制和提高生成器輸出序列的統(tǒng)計特性、線性復雜度和不可預測性等。3.4.2序列密碼編程本節(jié)介紹序列密碼編程技術，分為加密和序列生成部分。

1.序列密碼程序設計以下是序列密碼的編程(Stream.py)。

上述代碼生成一個與消息等長的隨機序列?；序列與消息按位異或?；接收端將密文與隨機序列再次異或就可以恢復出明文(注意收發(fā)雙發(fā)進行異或操作一定要保證嚴格的同步)?。2.偽隨機序列生成

序列密碼的關鍵在于偽隨機序列的生成。偽隨機序列又稱為偽噪聲序列。二進制偽隨機序列在信號同步、擴頻通信和多址通信等領域得到了廣泛的應用。例如，在擴頻通信中，使用偽噪聲序列作為擴頻信號，可使得擴頻后的信號具有很寬的頻譜，因此具有頻率譜密度很小的特性。通常加密采用的是M序列。所謂M序列是最長線性移位寄存器序列的簡稱。下面是軟件實現代碼(M.py)。

上述代碼利用函數real_calculate_prbs生成偽隨機序列，其中value是二進制表示的生成序列的位數，expression表示從value中揀去的數；該函數將value轉化為列表，作為初始種子?；采用將揀去的兩位相加對2求模的方法得到新的一位二進制數，插入序列的最前面，如此反復，指導序列達到value要求的長度?。隨機數生成的方法還有很多，在此不做一一介紹。3.5公鑰密碼編程3.5.1公鑰密碼思想公鑰密碼將加、解密分開，采用兩個不同密鑰，其中一個密鑰公開，稱為公鑰，另一個密鑰為用戶私有，稱為私鑰。公私鑰之間相互關聯，但從公鑰求私鑰在計算上不可能的。公鑰加密的提出具有很多對稱密碼體制所有具有的特點，具體可以概括為：

(1）密鑰分發(fā)簡單，存儲量?。?/p>

(2）不僅能加密，還能完成數字簽名、密鑰協(xié)商等；

(3）適用于網絡，實現不相識用戶間保密安全通信。

上述這些特點也是公鑰密碼的優(yōu)勢所在，并使得密碼應用發(fā)生革命性變化，為密碼學的發(fā)展開辟了新56方向。然而公鑰密碼的設計需要更復雜的數理基礎，對設計的要求更加嚴格，需要至少滿足以下要求：

(1）密鑰對的產生在計算上容易；(2）加解密計算在計算上容易；

(3）由公鑰求私鑰在計算上不可行；

(4）由密文和接收者的公鑰恢復明文在計算上不可行?；谏鲜鲆?，密碼學家一般是圍繞著一個具有單向性的數學難題而設計，常見的此類數學難題有大整數因子分解、多項式求解、橢圓曲線、離散對數等，因篇幅所限無法對這些密碼算法進行一一介紹，下面主要介紹RSA算法及其編程實現。3.5.2RSA算法編程1.RSA算法基礎RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一種用數論構造的、也是迄今為止理論上最為成熟和完善的公鑰密碼體制，該體制已得到廣泛的應用。它是建立在大數分解困難問題上的，既可用于加密，也可用于數字簽名。所謂大數分解困難問題就是：若已知兩個大素數p和q，求n=pq只需一次乘法，但若已知n，求p和q，則是一個要攻克的難題。

RSA的算法核心利用了歐拉公式的下面性質(推導略)：關鍵就是是找到找到n、e、d，三者關系是：d為e的模φ(n)逆元。如果三個數足夠大，就極難由其中部分猜到另外部分，這就是RSA的安全基礎和加解密基本思想?；谏鲜鲇嬎?，RSA的公鑰與私鑰的生成，Python可以采用以下兩種方法實現。方法一：采用RSA的算法數值逐步計算實現(RSA_Key_Generator_no_module.py)。

這種方法嚴格按照上述五步步驟，從素數選取直至生成公鑰和私鑰對，具體代碼設計如下。第一步，產生一個大素數：素數是RSA的基礎，為了取得足夠的安全性，所選的素數應該足夠大。目前找到素數的方法主要是采用篩選的方法，包括：埃氏篩法、歐拉篩法等，下面代碼采用拉賓米勒方法獲得素數。安裝后，生成pubkey和privkey的代碼如下。

上述代碼利用rsa模塊生成指定長度的(公鑰,私鑰)元組。注意，生成較長密鑰的時間可能較長。通常，生成的公鑰和私鑰需要以文件的方式保存起來，下面代碼展示的公鑰、私鑰的文件保存與裝入的實現。公鑰與私鑰的文件存儲格式為：.pem格式，如下圖3-22所示。

在讀取.pem格式文件后，需要使用rsa.PrivateKey.load_pkcs1、rsa.PublicKey.load_pkcs1將私鑰與公鑰裝入才能進行使用。裝入后的密鑰格式(與rsa.newkeys產生時的格式相同)，形如：b'i\xcd\xbeV!\x1f\xdf\xe2a\xd5\xae\x8a\xa7!\xb4\xb3T\x12\x8d\xfaX\xbbWwg\xcc\xdd\x94\xa2\r*\x80\xabu\xec|\xa6\xacO\xa0d\xb0\'8J\x01\xd2\x9au"k\x99\xab>\xd8\xf7\x1d7\xd4\xc9P\xe4T\xce’上述密鑰是以字節(jié)為格式單元的表示。

(1)RSA加密模式公鑰密碼體制利用公鑰加密，私鑰解密稱為加密模式。公鑰可以從公開渠道獲取，因此就免去了一對一的密鑰分發(fā)問題。經過公鑰加密的明文，只有被擁有對應私鑰的用戶解密，因此確保了數據安全。

RSA的加密代碼如下（使用方法一自行生成的公鑰和私鑰）。求解過程中，采用了Python的快速冪模算法，其核心思想在于：將大數的冪運算拆解成了相對應的乘法運算，利用下式：(2)RSA認證模式公鑰密碼體制利用私鑰加密，公鑰解密稱為認證模式。因為只有擁有私鑰的用戶，才能加密出聲明身份對應公鑰(數字證書中包含，由CA頒發(fā))可以解密的密文，從而進行身份驗證。

RSA的簽名代碼如下（采用方法二RSA模塊提供的函數工具）RSA的驗證代碼如下。raw_data為簽名前的數據，sign為經過私鑰簽名(加密)的輸出值?？梢?，認證模式與加密模式相比，只是使用的公鑰、私鑰的順序不一樣。3.5.3DH算法編程DH算法基礎

現代密碼，秘密全部寓于密鑰，密鑰分發(fā)就成為一個問題。雖然，公鑰密碼體制一定程度上解決了該問題，但是在現代信息系統(tǒng)中，對稱密碼還占據著很大的應用領域，如何進行對稱密鑰分發(fā)的難題依然無法回避。進一步，由于任何密鑰都有使用期限，因此密鑰的定期（或不定期）更換是密鑰管理的一個基本任務。為了盡可能地減少人的參與，密鑰的分配需要盡可能地自動進行。

1976年，W.Diffie和M.E.Hellman于提出，讓A和B兩個陌生人之間建立共享秘密密鑰的公開密鑰算62法，稱為Diffie-Hellman算法(簡稱DH算法)。DH算法利用了原根的性質，即：

利用該性質，用戶雙發(fā)可以在不公開自己秘密的情況下，與對方交換混合，就可以得到相同的計算值，作為后續(xù)對稱加密時的密鑰，也就是完成了密鑰協(xié)商，具體如下圖3-23所示。在DH密鑰交換算法中，選擇的單向函數是模指數運算。由于它的逆過程是離散對數問題，根據公鑰密碼的理論可知，具有很高的安全性。2.DH算法編程工作順序①Alice選一個素數p；②找到這個素數的原根，從眾多個中選擇其中一個g；③選一個小于上面選定素數p的隨機整數(私鑰)a，并計算gamodp得到公鑰A，形成公鑰私鑰對，并將g、p、A通過公開信道發(fā)送給對方Bob；④Bob接收到g、p、A后，選定一個小于p的素數作為自己的私鑰b，一方面計算gbmodp得到公鑰B，將B發(fā)送給Alice，另一方面通過計算Abmodp得到會話密鑰K；⑤Alice收到B后，通過計算Bamodp亦可得到會話密鑰K。

DH代碼如下。使用函數prime_num隨機找一個大于n的素數。

上述代碼給出了一種不同于前面的素數尋找方法。首先創(chuàng)建一個放置素數的空列表list?；然后通過除以已知素數(list中存儲)的方法，依次找出2到10?n內的所有素數?；對list進行隨機排序，找出第一個素數作為輸出?。下面代碼找到素數的原根。計算會話密鑰K的函數代碼如下。它的目的是使得兩個用戶安全地交換一個密鑰以便用于以后的報文加密，這個算法本身限于密鑰交換的用途，許多商用產品都使用這種密鑰交換技術。3.6單向函數編程3.6.1單向函數算法基礎