1、信息保密技術信息保密技術密碼學中常見的兩種體制:u對稱密碼體制(單鑰密碼體制) u 如果一個加密系統的加密密鑰和解密密鑰相同，或者雖然不相同，但是由其中的任意一個可以很容易地推導出另一個，即密鑰是雙方共享的,則該系統所采用的就是對稱密碼體制。 u非對稱密碼體制(公鑰密碼體制) u 在公鑰體制中，加密密鑰不同于解密密鑰。將加密密鑰公之于眾，誰都可以使用；而解密密鑰只有解密人自己知道。 一、對稱加密算法DESn美國數據加密標準美國數據加密標準DES（Data Encryption Standard）美國制定數據加密標準簡況美國制定數據加密標準簡況n目的目的 通信與計算機相結合是人類步入信息社會的一

2、個階梯，通信與計算機相結合是人類步入信息社會的一個階梯，它始于六十年代末，完成于它始于六十年代末，完成于90年代初。計算機通信網的形年代初。計算機通信網的形成與發展，要求信息作業標準化，安全保密亦不例外。成與發展，要求信息作業標準化，安全保密亦不例外。只只有標準化，才能真正實現網絡的安全，才能推廣使用加密有標準化，才能真正實現網絡的安全，才能推廣使用加密手段，以便于訓練、生產和降低成本。手段，以便于訓練、生產和降低成本。 背景背景發明人發明人：美國：美國IBM公司公司 W. Tuchman 和和 C. Meyer 1971-1972年研制成功年研制成功基礎：基礎：1967年美國年美國Horst

3、 Feistel提出的理論提出的理論產生：美國國家標準局（產生：美國國家標準局（NBS)1973年年5月到月到1974年年8月兩次發布通告，月兩次發布通告， 公開征求用于電子計算機的加密算法。經評選從一大批算法中采納公開征求用于電子計算機的加密算法。經評選從一大批算法中采納 了了IBM的的LUCIFER方案方案標準化：標準化：DES算法算法1975年年3月公開發表，月公開發表，1977年年1月月15日由美國國家標日由美國國家標 準局頒布為數據加密標準（準局頒布為數據加密標準（Data Encryption Standard），于），于 1977年年7月月15日生效日生效背景背景美國國家安全局（

4、美國國家安全局（NSA, National Security Agency)參與了美國國參與了美國國家標準局制定數據加密標準的過程。家標準局制定數據加密標準的過程。NBS接受了接受了NSA的某些建議，的某些建議，對算法做了修改，并將密鑰長度從對算法做了修改，并將密鑰長度從LUCIFER方案中的方案中的128位壓縮到位壓縮到56位位1979年，美國銀行協會批準使用年，美國銀行協會批準使用DES1980年，年，DES成為美國標準化協會成為美國標準化協會(ANSI)標準標準1984年年2月，月，ISO成立的數據加密技術委員會成立的數據加密技術委員會(SC20)在在DES基礎上基礎上制定數據加密的國際

5、標準工作制定數據加密的國際標準工作 DES首次被批準使用五年，并規定每隔五年由美國國首次被批準使用五年，并規定每隔五年由美國國家保密局作出評估，并重新批準它是否繼續作為聯邦加密家保密局作出評估，并重新批準它是否繼續作為聯邦加密標準。最近的一次評估是在標準。最近的一次評估是在1994年年1月，美國已決定月，美國已決定1998年年12月以后將不再使用月以后將不再使用DES。因為按照現有的技術水平，采。因為按照現有的技術水平，采用不到幾十萬美元的設備，就可破開用不到幾十萬美元的設備，就可破開DES密碼體制。目前密碼體制。目前的新標準是的新標準是AES，它是由比利時的密碼學家，它是由比利時的密碼學家J

6、oan Daemen和和Vincent Rijmen設計的分組密碼設計的分組密碼Rijndael（榮代爾）。（榮代爾）。美國制定數據加密標準簡況美國制定數據加密標準簡況n1997年年DESCHALL小組經過近小組經過近4個月的努力，通過個月的努力，通過Internet搜索了搜索了31016個密鑰，找出了個密鑰，找出了DES的密鑰，恢的密鑰，恢復出了明文。復出了明文。n1998年年5月美國月美國EFF(electronics frontier foundation)宣布，他們以一臺價值宣布，他們以一臺價值20萬美元的計算機改裝成的專用解萬美元的計算機改裝成的專用解密機，用密機，用56小時破譯了小

7、時破譯了56 比特密鑰的比特密鑰的DES。美國制定數據加密標準簡況美國制定數據加密標準簡況n盡管如此，盡管如此，DES對于推動密碼理論的發展和應用畢竟起了對于推動密碼理論的發展和應用畢竟起了重大作用，對于掌握分組密碼的基本理論、設計思想和實重大作用，對于掌握分組密碼的基本理論、設計思想和實際應用仍然有著重要的參考價值。際應用仍然有著重要的參考價值。DES 算法算法n分組長度為分組長度為64 bits (8 bytes)n密文分組長度也是密文分組長度也是64 bits。n密鑰長度為密鑰長度為64 bits，有，有8 bits奇偶校驗，有效密鑰長奇偶校驗，有效密鑰長度為度為56 bits。n算法主

8、要包括：初始置換算法主要包括：初始置換IP、16輪迭代的乘積變換、輪迭代的乘積變換、逆初始置換逆初始置換IP-1以及以及16個子密鑰產生器。個子密鑰產生器。 DES加密算法框圖子密鑰產生器子密鑰產生器16輪迭代輪迭代的乘積變換的乘積變換DES算法框圖算法框圖 輸入 64 bit明文數據 初始置換IP 乘積變換 （16輪迭代） 逆初始置換IP-1 64 bit密文數據 輸出 標準數據加密算法58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135

9、63554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725（a）初始置換）初始置換IP(b)逆初始置換逆初始置換IP -1初始置換初始置換IPIPn將將64 bit明文的位置進行置換，得到一個亂明文的位置進行置換，得到一個亂序的序的64 bit明文組，而后分成左右兩段，每明文組，而后分成左右兩段，每段為段為32 bit，以，以L0和和R0表示，表示，IP中各列元素中各列元素位置號數相差為

10、位置號數相差為8。n逆初始置換逆初始置換IPIP-1 -1 將將16輪迭代后給出的輪迭代后給出的64 bit組進行置換，得到輸出的密文組。輸出為組進行置換，得到輸出的密文組。輸出為陣中元素按行讀得的結果。陣中元素按行讀得的結果。nIP和和IPIP-1-1在密碼意義上作用不大，它們的作在密碼意義上作用不大，它們的作用在于打亂原來輸入用在于打亂原來輸入x x的的ASCII碼字劃分的碼字劃分的關系。關系。DES加密算法的輪結構加密算法的輪結構密鑰流生成器密鑰流生成器乘積變換乘積變換n它是它是DES算法的核心部分。將經過算法的核心部分。將經過IP置換后的數據分成置換后的數據分成32 bit的左右兩組，

11、在迭代過程中彼此左右交換位置。的左右兩組，在迭代過程中彼此左右交換位置。n每次迭代時只對右邊的每次迭代時只對右邊的32 bit進行一系列的加密變換，在此進行一系列的加密變換，在此輪迭代即將結束時，把左邊的輪迭代即將結束時，把左邊的32 bit與右邊得到的與右邊得到的32 bit逐位逐位模模2相加，作為下一輪迭代時右邊的段，并將原來右邊未經相加，作為下一輪迭代時右邊的段，并將原來右邊未經變換的段直接送到左邊的寄存器中作為下一輪迭代時左邊變換的段直接送到左邊的寄存器中作為下一輪迭代時左邊的段。的段。n在每一輪迭代時，右邊的段要經過在每一輪迭代時，右邊的段要經過選擇擴展運算選擇擴展運算E E、密鑰加

12、、密鑰加密運算、選擇壓縮運算密運算、選擇壓縮運算S S、置換運算、置換運算P P和左右混合運算和左右混合運算。選擇擴展運算選擇擴展運算E E 將輸入的將輸入的32 bit Ri-1擴展擴展成成48 bit的輸出，令的輸出，令s表示表示E原輸入數據比特的原下標，原輸入數據比特的原下標，則則E的輸出是將原下標的輸出是將原下標s 0或或1(mod 4)的各比特重復的各比特重復一次得到的，即對原第一次得到的，即對原第1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29，32各位都重各位都重復一次復一次,實現數據擴展。將實現數據擴展。將表中數據按行讀

13、出得到表中數據按行讀出得到48 bit輸出。輸出。(表表c)3212345456789891011121312131415161716171819202120212223242524252627282928293031321密鑰加密運算密鑰加密運算 將子密鑰產生器輸出的將子密鑰產生器輸出的48 bit子子密鑰密鑰ki與選擇擴展運算與選擇擴展運算E輸出的輸出的48 bits數據按位模數據按位模2相加。相加。 選擇壓縮運算選擇壓縮運算S。將前面送來的將前面送來的48 bit數據自左至右分成數據自左至右分成8組，每組為組，每組為6 bit。而后并行送入。而后并行送入8個個S盒，每個盒，每個S盒為一盒

14、為一非線性代換網絡，有非線性代換網絡，有4個輸出，運算個輸出，運算S的框圖如下。的框圖如下。48 bit 寄存器32 bit 寄存器S1S2S3S4S5S6S7S8DES的的S1-盒的輸入和輸出關系盒的輸入和輸出關系nx5 x0 x5 x4 x3 x2 x1 x0 1 0 1 0 1 1 0 0 列號列號 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行號行號 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15

15、 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13 (y3 , y2, y1 , y0)=(0,0,1,0)置換運算置換運算P P 對對S1至至S8盒輸出的盒輸出的32 bit數據進行坐標置換，置換數據進行坐標置換，置換P輸出的輸出的32 bit數據與左邊數據與左邊32 bit即即Li-1逐位模逐位模2相加，所得到的相加，所得到的32 bit作作為下一輪迭代用的右邊的數字段為下一輪迭代用的右邊的數字段Ri 。并將。并將Ri-1并行送到左邊并行送到左邊的寄存器，作為下一輪迭代用的左邊的數字段的寄存器，作為下一輪迭代用的左邊的數字段Li

16、 。（表。（表d） 1672021291228171152326518311028241432273919133062211425函數F(R,K)計算過程R (32比特)K (48比特)48比特E+P32比特1S2S3S4S5S6S7S8S子密鑰產生器子密鑰產生器n將將64 bit初始初始密鑰經過：密鑰經過：置換選擇置換選擇PC-PC-1 1循環移位循環移位置換選擇置換選擇PC-PC-2 2n給出每次迭給出每次迭代加密用的子密代加密用的子密鑰鑰ki，置換選擇164比特子密鑰產生器框圖子密鑰產生器框圖 密鑰（64 bit ）置換選擇1，PC1置換選擇2，PC2 Ci(28 bit) Di(28

17、bit) 循環左移ti+1bit 循環左移ti+1bit除去第8,16, ,64位(8個校驗位)ki574941332517915850423426181025951433527191136050443663554739312315762544638302214661534537292113528201241417112415328156211023191242681672720132415231374755304051453348444939563453464250362932置換選擇置換選擇2（PC-2）置換選擇置換選擇1（PC-1）迭代次數12345678循環左移位數11222222迭代

18、次數910111213141516循環左移位數12222221左循環移位位數左循環移位位數 DES的安全性安全性n窮舉攻擊分析窮舉攻擊分析 窮舉攻擊就是對所有可能的密鑰逐個進窮舉攻擊就是對所有可能的密鑰逐個進行脫密測試，直到找到正確密鑰為止的一種行脫密測試，直到找到正確密鑰為止的一種攻擊方法。攻擊方法。 窮舉攻擊判斷正確密鑰的方法：窮舉攻擊判斷正確密鑰的方法： 將利用試驗密鑰解密得到的可能明文與將利用試驗密鑰解密得到的可能明文與已掌握的明文的信息相比較，并將最吻合的已掌握的明文的信息相比較，并將最吻合的那個試驗密鑰作為算法輸出的正確密鑰。那個試驗密鑰作為算法輸出的正確密鑰。 窮舉攻擊又稱為窮盡

19、攻擊、強力攻擊、窮舉攻擊又稱為窮盡攻擊、強力攻擊、蠻干攻擊等。只要明文不是隨機的，就蠻干攻擊等。只要明文不是隨機的，就可實施窮舉攻擊。可實施窮舉攻擊。二重二重DESn明文為明文為P，兩個加密密鑰，兩個加密密鑰k1和和k2，密文，密文為：為：C=Ek2Ek1Pn解密時，解密時，P=Dk1Dk2CXEEDDPCPXC k1 k1k2k2討論：使用二重討論：使用二重DES產生的映射是否等價于單產生的映射是否等價于單重重DES加密加密?二重二重DES 用用DES進行兩次加密，但這是否就意味著進行兩次加密，但這是否就意味著兩重兩重DES加密的強度等價于加密的強度等價于112 bit密鑰的密密鑰的密碼的強

20、度？答案是否定的。碼的強度？答案是否定的。 三重三重DES加密加密加密：加密：y=Ek1Dk2Ek1 x解密：解密：x=Dk1Ek2Dk1yn稱其為加密稱其為加密-解密解密-加密方案，簡記為加密方案，簡記為EDE(encrypt-decrypt-encrypt)。n此方案已在此方案已在ANSI X9.17和和ISO 8732標準中采用，并標準中采用，并在保密增強郵遞在保密增強郵遞(PEM)系統中得到利用。系統中得到利用。n破譯它的窮舉密鑰搜索量為破譯它的窮舉密鑰搜索量為2112 51035量級，而量級，而用差分分析破譯也要超過用差分分析破譯也要超過1052量級。此方案仍有足量級。此方案仍有足夠

21、的安全性。夠的安全性。 分組密碼的運行模式分組密碼在加密時，明文分組的長度固定。分組密碼在加密時，明文分組的長度固定。實際應用中待加密消息的數據長度和格式各實際應用中待加密消息的數據長度和格式各有不同。有不同。為了能在各種應用場合使用為了能在各種應用場合使用DES，定義了，定義了DES的的4種運行模式，這些模式也可用于其他種運行模式，這些模式也可用于其他分組密碼。分組密碼。1 電碼本（電碼本（ECB）模式）模式消息分為長為消息分為長為64比特的分組，最后一個分組如果不比特的分組，最后一個分組如果不夠夠64比特，則需要比特，則需要填充填充。明文是由分組長為明文是由分組長為64比特的分組序列比特的

22、分組序列P1，P2，PN構成，相應的密文分組序列是構成，相應的密文分組序列是C1，C2，CN。 ECB的的最大特性最大特性是同一明文分組在消息中重復出現是同一明文分組在消息中重復出現的話，產生的密文分組也相同。的話，產生的密文分組也相同。ECB用于長消息時可能不夠安全，如果消息有固定用于長消息時可能不夠安全，如果消息有固定結構，密碼分析者有可能找出這種關系。結構，密碼分析者有可能找出這種關系。ECB在用于在用于短數據短數據（如加密密鑰）時非常理想，因（如加密密鑰）時非常理想，因此如果需要安全地傳遞此如果需要安全地傳遞DES密鑰，密鑰，ECB是最合適的模是最合適的模式。式。2 密碼分組鏈接（密碼

23、分組鏈接（CBC）模式）模式11111KnnKKnnnnnnnDCCDECPCCPCP1nKnnCECP解密時：每一個密文分解密時：每一個密文分組被解密后，再與前一組被解密后，再與前一個密文分組異或得明文個密文分組異或得明文解決解決ECB的安全缺陷的安全缺陷：可以讓重復的明文分組可以讓重復的明文分組產生不同的密文分組產生不同的密文分組加密時：輸入是當前加密時：輸入是當前明文分組和前一次密明文分組和前一次密文分組的異或文分組的異或初始向量初始向量IVIV應像密鑰一樣被保護，可使用應像密鑰一樣被保護，可使用ECB加密模式來發加密模式來發送送IV。保護保護IV的原因：如果敵手篡改的原因：如果敵手篡改

24、IV中的某些比特，則中的某些比特，則接收方收到的接收方收到的P1中相應的比特也發生了變化。中相應的比特也發生了變化。1111KKCEIVPPIVDC第一次加、解密需第一次加、解密需IV由于由于CBC 模式的鏈接機制，模式的鏈接機制，CBC模式對模式對加密長消息加密長消息非常合適。非常合適。CBC模式除能夠獲得保密性外，還能用于認證。模式除能夠獲得保密性外，還能用于認證。3 密碼反饋（密碼反饋（CFB）模式）模式加密算法的輸入是加密算法的輸入是64比特比特移位寄存器，其初值為某個移位寄存器，其初值為某個初始向量初始向量IV。加密算法輸出的最左（最高加密算法輸出的最左（最高有效位）有效位）j比特與

25、明文的第一比特與明文的第一個單元個單元P1進行異或，產生出進行異或，產生出密文的第密文的第1個單元個單元C1，并傳送，并傳送該單元。該單元。然后將移位寄存器的內容左然后將移位寄存器的內容左移移j位并將位并將C1送入移位寄存器送入移位寄存器最右邊（最低有效位）最右邊（最低有效位）j位。位。這一過程繼續到明文的所有這一過程繼續到明文的所有單元都被加密為止。單元都被加密為止。設設Sj(X)是是X的的j個最高有限個最高有限位，那么：位，那么：11jCPSE IV11jPCSE IV加密加密解密解密CFB特點特點nDES是分組長為是分組長為64比特的分組密碼，但利比特的分組密碼，但利用用CFB模式或模式

26、或OFB模式可將模式可將DES轉換為流轉換為流密碼。密碼。如果需要發送如果需要發送字符流字符流，每個字符長為，每個字符長為8比特比特,就應使用就應使用8比特密鑰來加密每個字符比特密鑰來加密每個字符.通常取通常取j=8流密碼不需要對消息填充，而且運行是實時流密碼不需要對消息填充，而且運行是實時的的圖3.13 OFB模式示意圖4 輸出反饋輸出反饋(OFB)模式模式OFB（output feedback）模式的結構類似于）模式的結構類似于CFB。不同之處不同之處OFB模式是將加密算法的輸出反饋到移位寄存器，模式是將加密算法的輸出反饋到移位寄存器，CFB模式中是將密文單元反饋到移位寄存器。模式中是將密

27、文單元反饋到移位寄存器。OFB優點：傳輸過程中的比特錯誤不會被傳播。優點：傳輸過程中的比特錯誤不會被傳播。OFB 中，中，C1中出現中出現1比特錯誤，在解密結果中只有比特錯誤，在解密結果中只有P1受到影響，以受到影響，以后各明文單元則不受影響。后各明文單元則不受影響。CFB中，中，C1也作為移位寄存器的輸入，因此它的也作為移位寄存器的輸入，因此它的1比特錯誤會影響比特錯誤會影響解密結果中各明文單元的值。解密結果中各明文單元的值。OFB的缺點：比的缺點：比CFB模式更易受到對消息流的篡改攻擊。模式更易受到對消息流的篡改攻擊。比較和選用比較和選用nECB模式，簡單、高速，但最易受重發攻擊。模式，簡

28、單、高速，但最易受重發攻擊。nCBC適用于文件加密，但較適用于文件加密，但較ECB慢。慢。nOFB和和CFB較較CBC慢許多。每次迭代只有少數慢許多。每次迭代只有少數bit完成加密。完成加密。nOFB用于高速同步系統，傳輸過程中的比特錯誤用于高速同步系統，傳輸過程中的比特錯誤不會被傳播不會被傳播.nCFB多用在字符為單元的流密碼中多用在字符為單元的流密碼中,有錯誤擴展有錯誤擴展分組密碼的分析方法n解密與密碼分析解密與密碼分析u 解密是加密的逆過程，是指掌握密鑰解密是加密的逆過程，是指掌握密鑰和密碼算法的合法人員從密文恢復出和密碼算法的合法人員從密文恢復出明文的過程。明文的過程。u密碼分析則是指

29、非法人員對密碼的破密碼分析則是指非法人員對密碼的破譯，而且破譯以后不會告訴對方。譯，而且破譯以后不會告訴對方。分組密碼的分析方法n根據攻擊者掌握的信息，可將分組密碼的攻擊分為以下幾類：u唯密文攻擊：攻擊者除了所截獲的密文外，沒有其他可利用的信息。u已知明文攻擊： 攻擊者僅知道當前密鑰下的一些明密文對。u選擇明文攻擊：攻擊者能獲得當前密鑰下的一些特定的明文所對應的密文。u選擇密文攻擊：攻擊者能獲得當前密鑰下的一些特定的密文所對應的明文。分組密碼的分析方法(續）u一種攻擊的復雜度可以分為兩部分：數據復雜度和處理復雜度。p數據復雜度是實施該攻擊所需輸入的數據量。p處理復雜度是處理這些數據所需的計算量

30、。 u對某一攻擊通常是以這兩個方面的某一方面為主要因素，來刻畫攻擊復雜度 。n 【例如】p窮舉攻擊的復雜度實際就是考慮處理復雜度；p差分密碼分析其復雜度主要是由該攻擊所需的明密文對的數量來確定。幾種常見的攻擊方法n1.強力攻擊強力攻擊n強力攻擊可用于任何分組密碼，且攻擊的復雜度n只依賴于分組長度和密鑰長度，嚴格地講攻擊所 n需的時間復雜度依賴于分組密碼的工作效率（包n括加解密速度、密鑰擴散速度以及存儲空間等）。n強力攻擊常見的有：窮舉密鑰搜索攻擊窮舉密鑰搜索攻擊、n字典攻擊字典攻擊、查表攻擊和時間查表攻擊和時間-存儲權衡攻擊存儲權衡攻擊等。幾種常見的攻擊方法（續）n2.差分密碼分析差分密碼分析

31、n基本思想基本思想n通過分析明文對的差值對密文對的差值的影響來恢復某些密鑰比特。n 若給定一個r輪的迭代密碼，對已知n長明文對為 n 和 ，定義其差分為n 式中 表示集合中定義的群運算， 為 在群中的逆元。n密碼分析者可隨機選擇具有固定差分的一對明文（只要求它們符合特定差分條件），然后使用輸出密文中的差分，按照不同的概率分配給不同的密鑰。隨著分析的密文對越來越多，其中最可能的一個密鑰就顯現出來了。這就是正確的密鑰。XX1XXX1XX幾種常見的攻擊方法（續）n3.線性密碼分析線性密碼分析u本質： 一種已知明文攻擊方法。u基本思想 ：通過尋找一個給定密碼算法的有效的n線性近似表達式來破譯密碼系統。

32、n對已知明文密文和特定密鑰，尋求線性表示式n n式中， 是攻擊參數。對所有可能密鑰，此表n達式以概率 成立。對給定的密碼算法，n使 極大化。為此對每一盒的輸入和輸n出構造統計線性路線，并最終擴展到整個算法。xdybxadba,2/1LP2/1LP二、公鑰加密算法RSA二、公鑰加密算法二、公鑰加密算法RSARSA 公鑰密碼體制的基本原理公鑰密碼體制的基本原理公鑰密碼體制采用了兩個不同的密鑰，這公鑰密碼體制采用了兩個不同的密鑰，這對在公開的網絡上進行對在公開的網絡上進行保密通信保密通信、密鑰密鑰分配分配、數字簽名和認證數字簽名和認證有著深遠的影響。有著深遠的影響。 對稱密碼的不足對稱密碼的不足 密

33、鑰管理量的困難：密鑰管理量的困難：兩兩分別用一個密鑰時，兩兩分別用一個密鑰時，則則n n個用戶需要個用戶需要C(n,2)=n(n-1)/2C(n,2)=n(n-1)/2個密鑰，當用戶量個密鑰，當用戶量增大時，密鑰空間急劇增大。如增大時，密鑰空間急劇增大。如:n=100 :n=100 時，共時，共4,9954,995個；個；n=5000n=5000時增加到時增加到12,497,50012,497,500個。個。 密鑰建立問題：密鑰建立問題：對協商密鑰的信道的安全性的對協商密鑰的信道的安全性的要求比正常的傳送消息的信道的安全性要高。要求比正常的傳送消息的信道的安全性要高。 數字簽名的問題：數字簽名

34、的問題：傳統加密算法無法實現抗抵傳統加密算法無法實現抗抵賴的需求。賴的需求。 公鑰密碼體制的起源公鑰密碼體制的起源q公鑰密碼又稱為雙鑰密碼和非對稱密碼，是公鑰密碼又稱為雙鑰密碼和非對稱密碼，是19761976年由年由DiffieDiffie和和HellmanHellman在其在其“密碼學新方向密碼學新方向”一文中提出的，文獻：一文中提出的，文獻：W.Diffie and W.Diffie and M.E.Hellman, New DirectrionsM.E.Hellman, New Directrions in Cryptography, in Cryptography, IEEE Tran

35、saction on Information Theory, V.IT-IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976,PP.644-65422.No.6, Nov 1976,PP.644-654qRSARSA公鑰算法是由公鑰算法是由Rivest,ShamirRivest,Shamir和和AdlemanAdleman在在19781978年提出來的年提出來的, , 見見CommunitionsCommunitions of the ACM. of the ACM. Vol.21.No.2. Feb.1978, PP.1

36、20-126Vol.21.No.2. Feb.1978, PP.120-126公鑰密碼體制加密框圖公鑰密碼體制認證框圖部分數學基礎部分數學基礎n乘法逆元乘法逆元n費爾瑪（費爾瑪（Fermat）定理）定理n歐拉函數歐拉函數n歐拉定理歐拉定理通過三個方面研究：通過三個方面研究： RSA算法描述算法描述 RSA實現中的問題實現中的問題 RSA的應用的應用RSARSA算法算法RSA算法算法 1977年由年由Ron Rivest、Adi Shamir和和Len Adleman發明，發明，1978年年公布是一種分組加密算法，明文和密文公布是一種分組加密算法，明文和密文在在0-（n-1）之間，）之間，n是一

37、個正整數；應是一個正整數；應用最廣泛的公鑰密碼算法只在美國申請用最廣泛的公鑰密碼算法只在美國申請專利，且已于專利，且已于2000年年9月到期。月到期。n RSA RSA體制的體制的安全性基于安全性基于數論中的數論中的EulerEuler定定理和計算復雜性理論中的下述論斷：理和計算復雜性理論中的下述論斷：求求兩個大素數的乘積是很容易計算的，但兩個大素數的乘積是很容易計算的，但要分解兩個大素數的乘積，求出它們的要分解兩個大素數的乘積，求出它們的素因子則是非常困難的素因子則是非常困難的。RSARSA算法描述算法描述 1 1、密鑰生成、密鑰生成（1 1）隨機選取兩個大素數）隨機選取兩個大素數p p 、

38、q q，令，令n=pqn=pq，隨，隨機選取兩個整數機選取兩個整數e e和和d d。使得。使得e,de,d與與 (n)(n)互素，互素，且且（2 2）公開）公開n,en,e，作為，作為E E，記為，記為E=(e,nE=(e,n) )（3 3）保密）保密p,q,dp,q,d與與 (n)(n)，作為，作為D D，記為，記為D=(d,nD=(d,n) )(mod1ned2 2、加密過程、加密過程（1 1）在公開密鑰數據庫中，查得用戶）在公開密鑰數據庫中，查得用戶U U的公的公鑰：鑰：E(n,e)；（2 2）將明文分組）將明文分組 ，使得每個，使得每個 n,in,i=1,2=1,2r r（3 3）對每

39、一組明文作加密變換）對每一組明文作加密變換 （4) 4)將密文將密文 傳送給用戶傳送給用戶U U。rxxxxx2ixryyyy21nxxEyeiiimod)( 3 3、解密過程解密過程（1 1）先對每一組明文做解密變換：）先對每一組明文做解密變換： （2 2）合并分組得到明文）合并分組得到明文 nyyDxdiiimod)(思考：思考：RSA算法中如何體現安全性？算法中如何體現安全性？證明解密過程的正確性：證明解密過程的正確性：ix)(mod1ned 存在某個整數存在某個整數k，使得，使得設設 與與n互素，即互素，即nyyDdiimod)(nxedimodnxnkimod1)(nxxnkiimo

40、d)(ix1),gcd(nxi1)(nked討論討論RSA算法的安全性：算法的安全性： 在算法中，在算法中，e和和n作為公開密鑰，任何人都作為公開密鑰，任何人都可以用來加密消息；而可以用來加密消息；而p、q、d和和 是保密是保密的，用來解密密文，只有私鑰擁有者知道，也的，用來解密密文，只有私鑰擁有者知道，也就是只有接收者知道。就是只有接收者知道。 由于由于n為兩個大素數的乘積，又為兩個大素數的乘積，又n=pq，那么，那么可以得到可以得到(n)=(p-1)(q-1)。發信者并不知道。發信者并不知道n的的兩個素因子兩個素因子p和和q，就無法計算，就無法計算(n)。 又由于又由于ed1 moded1 mod(n)(n)，d d是通過此式計算是通過此式計算出來的，因此出來的，因此無法計算無法計算d，所以就無法進行解密。，所以