信息安全技術(shù)——

密碼學技術(shù)東北大學提綱密碼技術(shù)概述對稱密碼技術(shù)非對稱密碼技術(shù)密鑰分配與管理技術(shù)數(shù)字簽名技術(shù)信息隱藏技術(shù)提綱密碼技術(shù)概述對稱密碼技術(shù)非對稱密碼技術(shù)密鑰分配與管理技術(shù)數(shù)字簽名技術(shù)信息隱藏技術(shù)知識點密碼學的基本概念密碼學的發(fā)展歷程密碼學的應用密碼學的技術(shù)基礎(chǔ)什么是密碼學密碼學研究通信安全保密的學科密碼編碼學研究將明文轉(zhuǎn)換成密文的技術(shù)尋找生成高強度密碼的有效算法密碼分析學研究分析破譯密碼的方法破譯密碼、偽造密碼，竊取機密信息盾矛密碼體制的組成密碼體制的組成全體明文的集合M——明文空間全體密文的集合C——密文空間全體密鑰的集合K——密鑰空間加密算法E，由加密密鑰控制的加密變換的集合解密算法D，由解密密鑰控制的解密變換的集合密碼技術(shù)的發(fā)展歷程古典密碼技術(shù)階段~1949年現(xiàn)代密碼技術(shù)階段1949~古典密碼技術(shù)階段古典密碼技術(shù)階段早在四千年前，埃及人就開始使用密碼技術(shù)思路”看“的到，但”看“不懂”看“的懂，但”看“不到”看“不到，也”看“不懂技術(shù)暗語、文字游戲以及其他信息隱藏方法1918年，WilliamF.Friedman

“TheIndexofCoincidenceandItsApplicationsinCrytography”(重合指數(shù)及其在密碼學中的應用）特點基本依靠人工或借助器械小范圍應用，少數(shù)人掌握加密/解密更多的是依靠經(jīng)驗和直覺藝術(shù)的成分>科學的成分現(xiàn)代密碼技術(shù)階段（1/10）香農(nóng)（C.E.Shannon)1949在《貝爾系統(tǒng)技術(shù)雜志》上發(fā)表了“TheCommunicationTheoryofSecrecySystem”（保密系統(tǒng)的通信理論）奠定了密碼學的理論基礎(chǔ)藝術(shù)

科學（但仍不失藝術(shù)性的一面）現(xiàn)代密碼技術(shù)階段（2/10）戴維.卡恩

1967整理一戰(zhàn)和二戰(zhàn)的歷史資料，出版了《破譯者(TheCodebreakers)》為密碼技術(shù)公開化、大眾化奠定了基礎(chǔ)20世紀70年代，隨著IBM等公司陸續(xù)發(fā)表的關(guān)于密碼技術(shù)的報告，使密碼技術(shù)為更多的人所了解現(xiàn)代密碼技術(shù)階段（3/10）W.E.Diffie&M.E.Hellman1976發(fā)表“NewDirectioninCryptography(密碼學新方向）”，提出了一種全新的密碼設計思想（非對稱加密），首次證明了在發(fā)送端和接收端之間不需要傳送密鑰的保密通信是可能的開創(chuàng)了公鑰密碼技術(shù)的新紀元使科學高效的密鑰管理體制的建立成為可能現(xiàn)代密碼技術(shù)階段（4/10）美國國家標準局NBS（現(xiàn)在的NIST）

1977正式公布了數(shù)據(jù)加密標準DES(DataEncryptionStandard)DES算法公開，使密碼技術(shù)的研究進入一個嶄新的時代DES在相當長的時間內(nèi)成為事實上的國際標準由于安全性原因，1998年正式退役現(xiàn)代密碼技術(shù)階段（5/10）李維斯特（R.L.Rivest）,沙米爾（A.Shamir）,艾德曼（L.Adleman）

1978提出RSA公鑰密碼技術(shù)杰出的公鑰密碼技術(shù)現(xiàn)代密碼技術(shù)階段（6/10）Bennett.Charles

H&Brassard.Gill1984提出量子密碼技術(shù)——BB84協(xié)議基于量子定律的密碼技術(shù)可以抗擊具有無限計算能力的攻擊量子計算機誕生后，量子密碼技術(shù)有可能成為唯一真正安全的密碼技術(shù)現(xiàn)代密碼技術(shù)階段（7/10）N.Koblitz&V.Miller1985將橢圓曲線理論引入公鑰密碼技術(shù)橢圓曲線密碼體制——公鑰密碼技術(shù)研究的新亮點較之RSA相同的安全級別下，具有更短的密鑰長度實現(xiàn)速度快現(xiàn)代密碼技術(shù)階段（8/10）R.Mathews&D.Wheeleretc.1989將混沌理論應用到序列密碼及保密通信理論中為序列密碼技術(shù)的研究開辟了新的途徑混沌理論的應用主要用于密鑰的生成*序列密碼利用少量的密鑰（制亂元素，保密的）通過某種復雜的運算（密碼算法，公開的）產(chǎn)生大量的偽隨機位流，用于對明文位流的加密。解密是指用同樣的密鑰和密碼算法及與加密相同的偽隨機位流，用以還原明文位流。現(xiàn)代密碼技術(shù)階段（9/10）JoanDaemen&VincentRijmen2000Rijndael密碼算法

AES算法（AdvancedEncryptionStandard)新一代數(shù)據(jù)加密標準現(xiàn)代密碼技術(shù)階段（10/10）歐盟

2000啟動歐洲數(shù)據(jù)加密、數(shù)字簽名、數(shù)據(jù)完整性計劃NESSIE目的：提出一套高魯棒性的密碼體制包括分組密碼、序列密碼、散列函數(shù)、消息認證碼（MAC）、數(shù)字簽名和公鑰加密密碼標準密碼技術(shù)的作用密碼技術(shù)作用基本功能提供保密性，使非授權(quán)用戶無法知道信息的真實內(nèi)容其他功能鑒別：信息的接收者應能夠確認信息的真實來源完整性：信息的接收者應能驗證信息在傳輸過程中有沒有發(fā)生改變不可否認性：信息的發(fā)送方不能否認已發(fā)送過的信息密碼技術(shù)的應用密碼技術(shù)的應用所有需要信息保密的領(lǐng)域軍事政治企/事/工/商業(yè)個人——信息時代尤為重要知識點密碼學的基本概念密碼學的發(fā)展歷程密碼學的應用密碼學的技術(shù)基礎(chǔ)技術(shù)基礎(chǔ)密碼技術(shù)分類密碼分析計算復雜性理論密碼學的技術(shù)基礎(chǔ)Kerckhoff

假設對于所有的密鑰，加密和解密算法迅速有效；密碼體制的安全性不依賴于算法的保密，而是依賴于密鑰的保密當前和今后較長的時間內(nèi)，密鑰仍然是密碼體制安全性的關(guān)鍵；密鑰的產(chǎn)生、分配和管理是密碼技術(shù)中重要的研究方向現(xiàn)代密碼技術(shù)普遍依賴于數(shù)學無論是加密/解密技術(shù)，還是密碼分析技術(shù)密碼技術(shù)的分類密碼技術(shù)按執(zhí)行的操作方式按收發(fā)雙方使用的密鑰是否相同替換密碼技術(shù)換位密碼技術(shù)對稱密碼技術(shù)非對稱密碼技術(shù)序列密碼技術(shù)分組密碼技術(shù)密碼技術(shù)的可破譯分析密碼技術(shù)的可破譯分析根據(jù)密文可以推算出明文或密鑰，或者能夠根據(jù)明文和相應的密文推算出密鑰，則該密碼技術(shù)是可破譯的；否則是不可破譯的；根據(jù)kerckhoff假設只要密鑰是保密的、安全的，則密碼技術(shù)就是安全的密碼分析的主要方法（1/3）窮舉法通過試遍所有的明文或密鑰來進行破譯窮舉明文將可能的明文進行加密，將得到的密文同截獲的密文進行比對，從而確定正確的明文；窮舉密鑰用可能的密鑰解密密文，直到得到有意義的明文，從而確定正確的明文和密鑰對抗手段在明文和密文中增加隨機冗余信息增加密鑰長度，提高生成密鑰的隨機性密碼分析的主要方法（2/3）統(tǒng)計分析法通過分析密文、明文和密鑰的統(tǒng)計規(guī)律來達到破譯密碼技術(shù)的方法；對抗手段設法使明文的統(tǒng)計特性與密文的統(tǒng)計特性不一樣密碼分析的主要方法（3/3）密碼技術(shù)分析法根據(jù)所掌握的明文、密文的有關(guān)信息，通過數(shù)學求解的方法找到相應的加解密算法原則上，受密碼技術(shù)分析破譯的密碼技術(shù)已經(jīng)不能使用對抗手段選用具有堅實數(shù)學基礎(chǔ)和足夠復雜的加解密算法對密碼技術(shù)進行攻擊的4種情況惟密文攻擊密碼分析者僅知道一些密文，并試圖恢復盡可能多的明文，并進一步推導出加密信息的密鑰已知明文攻擊分析者不僅知道一些信息的密文，而且還知道與之對應的明文，根據(jù)明文和密文試圖推導出加密密鑰或加密算法選擇明文攻擊分析者可以選擇一些明文，并得到相應的密文，而且可以選擇被加密的明文，并試圖推導出加密密鑰的酸法。選擇密文攻擊分析者可以選擇不同的密文，并能得到相應的明文，并試圖推導出加密密鑰。其他自適應選擇明文攻擊、自適應選擇密文攻擊，…攻擊方案的選擇取決于能夠掌握的可靠信息和所具有的技術(shù)手段計算復雜性理論密碼技術(shù)的安全性在密碼技術(shù)領(lǐng)域，安全性是相對的，而不是絕對的可證明安全性從理論上證明破譯某個密碼系統(tǒng)的代價不低于求解某個已知的數(shù)學難題計算安全性用已知的最好算法和利用現(xiàn)有的最大計算資源，仍然不可能在合理的時間內(nèi)完成破譯該系統(tǒng)所需要的計算——可證明安全性和計算安全性統(tǒng)稱實際安全性密碼安全性理論的基礎(chǔ)密碼安全性理論的基礎(chǔ)計算復雜性理論給出問題求解困難性的數(shù)量指標，并確定其安全性密碼分析所需的計算量是密碼體制安全性的生命指標如果破譯一個密碼體制所需要的時間為指數(shù)階的，則它在計算上是安全的

實際上也是安全的Diffie和Hellman通過證明指出，NPC問題更適合構(gòu)造密碼體制提綱密碼技術(shù)概述對稱密碼技術(shù)非對稱密碼技術(shù)密鑰分配與管理技術(shù)數(shù)字簽名技術(shù)信息隱藏技術(shù)知識點對稱密碼技術(shù)概述古典密碼技術(shù)數(shù)據(jù)加密標準DES國際數(shù)據(jù)加密算法IDEA高級加密標準AES技術(shù)思路對稱密碼技術(shù)概述對稱密碼技術(shù)加密密鑰和解密密鑰相同解密算法是加密算法的逆算法特點密鑰必須安全傳送和妥善保管典型代表古典密碼技術(shù)序列密碼技術(shù)分組密碼技術(shù)（如DES，IDEA，AES等）對稱密碼技術(shù)的安全性對稱密碼技術(shù)的安全性依賴兩個因素加密算法必須足夠強，僅基于密文本身去解密在實踐是不可能的加密方法的安全性依賴于密鑰的安全性，而不是算法的秘密性對稱密碼技術(shù)的應用對稱密碼技術(shù)的應用優(yōu)勢實現(xiàn)速度快，算法公開，應用廣泛，固化成本低存在的問題密鑰的分發(fā)與管理非常復雜，代價高N個用戶的網(wǎng)絡，需要N（N-1）/2個密鑰不能實現(xiàn)數(shù)字簽名知識點對稱密碼技術(shù)概述古典密碼技術(shù)數(shù)據(jù)加密標準DES國際數(shù)據(jù)加密算法IDEA高級加密標準AESDES產(chǎn)生的歷史背景DES產(chǎn)生的歷史背景美國國家標準巨為了滿足計算機通信網(wǎng)絡的發(fā)展對安全保密的需求，實現(xiàn)系統(tǒng)同一水平的安全性和兼容性，降低數(shù)據(jù)加密產(chǎn)品的生產(chǎn)成本，推廣使用密碼算法，而公開征集一種用于政府部門及民間進行計算機數(shù)據(jù)加密的密碼算法1973年5月13日向社會首次公開征集——不理想1974年8月27日向社會再次公開征集——IBM公司的方案1976年11月23日——被采納，并授權(quán)在非密級的政府通信中使用1977年1月15日——公布DES正式文本DES的使用DES的使用存在疑問，但仍被迅速推廣使用最主要質(zhì)疑：密鑰長度不足（56位）在最初的使用中，DES沒有受到實質(zhì)性威脅順利通過1983、1987、1992、1994年的安全性評估到1998年以后不再使用近年來，DES的問題逐漸暴露出來1991年，RSA數(shù)據(jù)安全公司宣布該公司發(fā)起的對56位DES的攻擊已經(jīng)由一個稱為電子邊境基金會的組織在22小時15分鐘內(nèi)完成（通過互聯(lián)網(wǎng)上100000計算機合作完成）有必要以新的對稱加密技術(shù)取代DES64位碼64位碼初始變換逆初始變換乘積變換明文密文輸入輸出IPIP-1DES實現(xiàn)過程+?K1+?K2+?KnDES設計原理重復交替使用選擇函數(shù)S和置換運算P兩種變換（confusion+diffusion)使用Feistel方法16次迭代變換每一次迭代變換都是以前一次迭代變換的結(jié)果（第一次以x0=L0R0作為輸入）和用戶密鑰擴展得到的子密鑰Ki作為輸入；每一次迭代變換只變換一半數(shù)據(jù)，將輸入數(shù)據(jù)的右半部分經(jīng)過函數(shù)f后，將其輸出與輸入數(shù)據(jù)的左半部分進行異或運算，并將得到的結(jié)果作為新的右半部分，而原來的右半部分變成新的左半部分。）在最后一輪，左、右半部分并圍變換，而直接將R16L16并在一起作為末置換的輸入。f函數(shù)f函數(shù)非線性函數(shù)，DES算法安全性的關(guān)鍵以長度為32位的比特串作為輸入，產(chǎn)生的中間結(jié)果為48位，并在最終產(chǎn)生長度為32位的比特串作為輸出F以前一輪迭代的結(jié)果Ri-1作為輸入，首先根據(jù)一個固定的擴展函數(shù)E“擴展”為48位。與子密鑰異或：f將置換得到得到48位輸出與子密鑰Ki（48位）進行異或S盒替代：以6比特為單位將與子密鑰異或得到的結(jié)果分為8個小組，并將它們送入替代函數(shù)（S盒）中進行替代運算S盒是函數(shù)f的核心，是非線性的。48位比特串經(jīng)過8個S盒后，得到8個4位的分組，重新組合后形成一個32位的比特串。P盒置換：將S盒輸出的32位比特串根據(jù)固定的置換P盒置換到相應的位置。P盒置換后得到的輸出就是函數(shù)f(Ri-1,ki)的結(jié)果輸入（64位）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157輸出（64位）初始變換IPL0（32位）R0（32位）加密函數(shù)(A,Ki)A(32位)加密時A=Ri;解密時A=Li;擴展置換E48位結(jié)果Ki+選擇函數(shù)組(S1~S8)32位結(jié)果f(A,Ki)置換運算P32位左32位右32位Li-1Ri-1擴展置換48位(明文)64位密鑰作第i次迭代的計算機子密鑰Ki密鑰程序表48位(密鑰)8組6位碼S1S2S8模2加S盒輸入：6位輸出：4位+++++…+++++32位置換32位32位LiRi左32位右32位Ri-1Li-1模2加+++++...++++++乘積變換中的一次迭代A32位3212345456789891011121312131415161716171819202120212223242524252627282928293031321選擇運算E選擇運算E的結(jié)果48位選擇運算E擴展函數(shù)E的第一分組的工作過程123455678123453248……

012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S11

0110

0

1020010輸入6位輸出4位使用選擇函數(shù)S1的例子64位碼64位碼初始變換逆初始變換L0明文密文輸入輸出IPIP-1R0選擇函數(shù)的輸出（32位）1672021291228171152326518311028241432273919133062211425置換P加密函數(shù)的結(jié)果（32位）置換碼組輸入（64位）40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725輸出（64位）逆初始變換IP-164位密鑰置換選擇1C0(28位)D0(28位)循環(huán)左移循環(huán)左移C1(28位)D1(28位)置換選擇2K1(48位)(56位)循環(huán)左移循環(huán)左移Ci(28位)Di(28位)置換選擇2Ki(48位)(56位)密鑰表的計算邏輯循環(huán)左移：11912110232112421225213262142721528216157494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124置換選擇1密鑰（64位）C0(28位)D0(28位)Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)置換選擇2L0R0←IP(明文)L1←R0

R1←L0(R0,K1)L2←R1

R2←L1(R1,K2)……L16←R15

R16←L15(R15,K16)密文←IP-1(R16L16)加密方程：L0R0←IP(<64位明文>)Ln←Rn-1Rn←Ln-1(Rn-1,Kn)<64位密文>←IP-1(R16L16)解密方程：R16L16←IP(<64位密文>)Rn-1←LnLn-1←Rn(Ln,Kn)<64位明文>←IP-1(L0R0)DES算法的脆弱性DES的半公開性：S盒的原理至今保密，所以不能算作真正的公開加密算法。1）函數(shù)構(gòu)造與作用域：加密強度取決于函數(shù)f的復雜度(S、P)和f的執(zhí)行次數(shù)。64位固定分組，短組模式，易造成密文重復組塊有限的函數(shù)作用域ASCII碼0~127子密鑰只參與異或簡單的運算，有可能損害變換精度。2）迭代問題無法證明迭代16次最好迭代在有限的作用域中存在封閉性；迭代次數(shù)多不僅費時，還可能被一次簡單的變換所代替。DES算法的脆弱性3）S盒中的重復因子及密鑰多值問題S盒設計中利用重復因子，導致S盒對不同輸入可能產(chǎn)生相同輸出，使加密、解密變換的密鑰具有多值性。子密鑰長度48位，只影響32位輸出，因此加密強度達不到256，實際只有232x16=236S盒是精心設計的，它有利于設計者破譯密碼。提高加密強度（如增加密鑰長度），系統(tǒng)開銷呈指數(shù)增長，除提高硬件、并行處理外，算法本身和軟件技術(shù)無法提高加密強度。DES算法存在的問題與挑戰(zhàn)數(shù)據(jù)加密標準強力攻擊：255次嘗試窮盡搜索蠻力攻擊差分密碼分析法：247次嘗試1991年提出，選擇明文攻擊。分析明文對的差值對密文對差值的影響。很有效。線性密碼分析法：243次嘗試1992年提出，已知明文攻擊。尋找一個近似的線性表達式，通過選擇充分多的明文——密文對來破解密鑰。對DES更有效。多重DES及IDEA二重DES（二個密鑰，長度112位）

：加密：C=Ek2[Ek1(P)]解密：P=Dk1[Dk2(C)]要防止中途攻擊三重DES（二個密鑰）加密：C=Ek1[Dk2[Ek1(P)]]解密：P=Dk1[Ek2[Dk1(C)]]IDEA加密算法1992年，瑞士的Lai和Massey128位密鑰，8輪，快速，軟硬件實現(xiàn)。高級加密標準(AES)

NIST(國家標準技術(shù)研究所)1997年9月12日發(fā)出征集高級加密標準的通知。1998年8月首次選出15個候選者，1999年3月遴選出5個，包括：E2、MARS、RC6、Rijndael、Twofish。2000年10月2日，美國商務部部長宣布比利時的Rijndael算法成為新的AES。選擇的基本條件：公開；分組單鑰，分組長度128；密鑰可為128，192，256；可軟硬件實現(xiàn)。優(yōu)劣標準：安全性；計算效率；內(nèi)存要求；簡便靈活。此外：適應性；減少專利糾紛；分散目標減少攻擊。AES被開發(fā)用于替代DES，但NIST預測TripleDES仍將在近期作為一種實用的算法，單DES將逐步退出。

提綱密碼技術(shù)概述對稱密碼技術(shù)非對稱密碼技術(shù)密鑰分配與管理技術(shù)數(shù)字簽名技術(shù)信息隱藏技術(shù)知識點非對稱密碼技術(shù)概述RSA算法其他非對稱密碼技術(shù)簡介傳統(tǒng)密碼體制的缺陷傳統(tǒng)密碼體制的缺陷密鑰管理的麻煩n個用戶保存n*(n-1)/2個密鑰不能提供法律證據(jù)不僅要保密還要解決證實問題非對稱密碼技術(shù)的提出1976年，美國學者Diffie和Hellman發(fā)表了著名論文《密碼學的新方向》，提出了建立“公開密鑰密碼體制”若用戶A有加密密鑰ka（公開），不同于解秘密鑰ka’（保密），要求ka的公開不影響ka’的安全。若B要向A保密送去明文m,可查A的公開密鑰ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密鑰ka’對x進行解密得到m。公鑰體制的理論基礎(chǔ)從本質(zhì)上講，設計一個公開密碼體制就是構(gòu)造一個陷門單向函數(shù)。設X為明文，Y為密文。滿足以下兩條件的f則稱為陷門單向函數(shù)。算Y=f(X)容易，而已知Y，反求X則很難，即求X=f(Y)很難若陷門（參數(shù)）已知，則容易由Y求X保證從已知的Y，X和公鑰難以推出秘密密鑰的這種安全性，往往建立在著名的數(shù)學難題基礎(chǔ)上，即要破譯某種公鑰密碼，相當于要解一個公認的數(shù)學難題。目前世界上用得最多的公鑰密碼算法是RSA、離散對數(shù)和ECC。其中，RSA是基于大整數(shù)分解難題的基礎(chǔ)上，而ECC是基于求橢圓曲線離散對數(shù)的難題基礎(chǔ)上。陷門參數(shù)正是秘密密鑰公鑰密碼體制的特點公鑰密碼體制有以下特點密鑰分發(fā)簡單由于加密密鑰與解密密鑰不能互推，使得加密密鑰表可以像電話號碼本一樣由主管部門發(fā)給各個用戶。需要秘密保存的密鑰量少網(wǎng)絡中每個成員只需秘密保存自己的解密密鑰，N個成員只需產(chǎn)生N對密鑰互不相識的人之間也能進行保密對話一方只要用對方的公開密鑰加密發(fā)出，收方即用自己密藏的私鑰解密，而任何第三方即使知道加密密鑰也無法對密文進行解密?？梢赃M行數(shù)字簽名發(fā)信者用他的秘密密鑰進行簽名，收信者可用發(fā)信者的公鑰進行驗證。公鑰密碼體制的意義（1/2）解決大規(guī)模網(wǎng)絡應用中密鑰的分發(fā)和管理問題

需要管理的秘密密鑰數(shù)量大大減少采用公鑰密碼體制，N個用戶只需要產(chǎn)生N對密鑰。以100萬個用戶為例，只需100萬對密鑰，需要秘密保存的僅100萬個私鑰。而利用傳統(tǒng)密碼體制，為保證不被第三方竊聽，需要N（N–1）/2=4950萬個密鑰！分發(fā)簡單，安全性好公鑰密碼加密密鑰通常是公開的，而解密密鑰是秘密的，由用戶自己保存，不需要往返交換和傳遞減少了密鑰泄露的危險性公鑰密碼體制的意義（2/2）實現(xiàn)網(wǎng)絡中的數(shù)字簽名機制

數(shù)字簽名的數(shù)據(jù)需要有惟一性、私有性，而對稱密鑰技術(shù)中的密鑰至少需要在交互雙方之間共享，因此，不滿足惟一性、私有性，無法用做網(wǎng)絡中的數(shù)字簽名。公鑰密碼技術(shù)由于存在一對公鑰和私鑰，私鑰可以表征惟一性和私有性，而且經(jīng)私鑰加密的數(shù)據(jù)只能用與之對應的公鑰來驗證，其他人無法仿冒，所以，可以用做網(wǎng)絡中的數(shù)字簽名服務。知識點非對稱密碼技術(shù)概述RSA算法其他非對稱密碼技術(shù)簡介RSA算法的提出與發(fā)展

1978年，美國麻省理工學院(MIT)的研究小組成員：李維斯特(Rivest)、沙米爾(Shamir)、艾德曼(Adleman)提出了一種基于公鑰密碼體制的優(yōu)秀加密算法——RSA算法。

RSA算法是一種分組密碼體制算法，它的保密強度是建立在具有大素數(shù)因子的合數(shù)，其因子分解是困難的。 RSA得到了世界上的最廣泛的應用，ISO在1992年頒布的國際標準X.509中，將RSA算法正式納入國際標準。1999年美國參議院已通過了立法，規(guī)定電子數(shù)字簽名與手寫簽名的文件、郵件在美國具有同等的法律效力。

公開密鑰算法數(shù)論知識簡介互素：若gcd(a,b)=1，則整數(shù)a和b互素。定義：若a?xmodn=1，則稱a與x對于模n互為逆元。用歐幾里得Euclid算法求乘法逆元 若a和n互素，則a在模n下有逆元歐拉Euler函數(shù)φ(n)=與n互素的、小于n的正整數(shù)的個數(shù)，n>1。例： φ(3)=φ(4)=φ(6)=2，φ(5)=4，φ(7)=6 φ(12)=6

數(shù)論知識簡介模運算性質(zhì)：同余模運算滿足自反性、對稱性、傳遞性；

a=amodn；

若a=bmodn，則b=amodn；

若a=bmodn，b=cmodn，則a=cmodn若amodn=bmodn，則(a-b)modn=0；[(amodn)+(bmodn)]modn=(a+b)modn；--；**；例：152

mod12=(3*3)mod12=9若n是素數(shù)，則φ(n)=n-1若n=p*q，p、q是素數(shù)，則φ(n)=(p-1)*(q-1)

例：φ(21)=φ(3*7)=2*6=12費爾瑪Fermat小定理：若m是素數(shù)，且a不是m的倍數(shù)，則am-1modm=1?；蛘撸喝鬽是素數(shù)，則ammodm=a例：47-1mod7=4096mod7=1

47

mod7=16384mod7=4歐拉Euler定理：aφ(n)modn=1推論：若a與n互素，則a與aφ(n)-1

互為逆元。

例：a=4，n=7，φ(7)=6，aφ(7)-1

=45=1024

所以，4和1024在模7下互為逆元。驗證：4x1024mod7=1求乘法逆元FunctionEuclid(d,f)//求d在模f下的逆元(x1,x2,x3)<-(1,0,f);(y1,y2,y3)<-(0,1,d);Ify3=1thenprint“逆元是”y2elseprint“無逆元”;End.Q=[x3/y3](t1,t2,t3)<-(x1-Q*y1,x2-Q*y2,x3-Q*y3)(x1,x2,x3)<-(y1,y2,y3);(y1,y2,y3)<-(t1,t2,t3)Goto2)高次冪剩余的運算公開密鑰算法

要計算gn

modp，因g、n、p都是大數(shù)而不能采用先高次冪再求剩余的方法來處理，而要采用平方取模的算法，即每一次平方或相乘后，立即取模運算。歐幾里德算法歐幾里德算法可以迅速地找出給定的兩個整數(shù)a和b的最大公因數(shù)gcd（a，b），并可判斷a與b是否互素，因此該算法可用來尋找加密密鑰和解密密鑰。

Xrmodp的快速算法流程圖A<-xB<-rC<-1B=0輸出CBmod2=0B<-B/2A<-A*AmodpB<-B-1C<-C*AmodpYNNYRSA算法概述

公開密鑰算法每個合數(shù)都可以唯一地分解出素數(shù)因子 6=2·3 999999=3·3·3·7·11·13·37 27641=131·121 從2開始試驗每一個小于等于√27641的素數(shù)。素數(shù)：只能被1和它本身整除的自然數(shù)；否則為合數(shù)。整數(shù)n的十進制位數(shù)因子分解的運算次數(shù)所需計算時間（每微秒一次） 50 1.4x1010 3.9小時 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年素數(shù)的檢驗素數(shù)的檢驗Wilson定理：P是素數(shù)(P-1)!ModP=-1

當P較大時，很費時間，無實際價值。Rabin-Miller方法：概率檢驗適用于RSA算法的最實用的辦法是概率測試法。該法的思想是隨機產(chǎn)生一個大奇數(shù)，然后測試其是否滿足條件，如滿足，則該大奇數(shù)可能是素數(shù)，否則是合數(shù)。

Witness(a,n){/*將n-1表示為bk

bk-1…b0的形式

n是待檢驗的數(shù)，a是小于n的整數(shù)。若返回True，則n肯定不是素數(shù)；若返回False，則n有可能是素數(shù)。*/d=1fori=kdownto0{x=d;d=(d?d)modn;ifd=1&(x<>1)&(x<>-1)returnTrue;ifbi=1thend=(d?a)modn}ifd<>1thenreturnTrue;returnFalse;}對于s個不同的a，重復調(diào)用此算法，每次返回False，則n是素數(shù)的概率至少為1-2-sRabin-Miller方法RSA算法的實現(xiàn)

公開密鑰算法RSA加密算法的過程

1．取兩個隨機大素數(shù)p和q（保密）2．計算公開的模數(shù)n=p*q(公開)3．計算秘密的歐拉函數(shù)

(n)=（p-1)*(q-1)（保密），丟棄p和q，不要讓任何人知道。4．隨機選取整數(shù)e,滿足gcd(e,

(n))=1(公開e加密密鑰)5．計算d滿足de≡1(mod

(n))(保密d解密密鑰)6．將明文x（按模為r自乘e次冪以完成加密操作，從而產(chǎn)生密文y（X、Y值在0到n-1范圍內(nèi)）。Y=xe

modn7．解密：將密文y按模為n自乘d次冪。X=Ydmodn舉例

公開密鑰算法例設p=43,q=59,r=p?q=43*59=2537,

(r)=(p-1)(q-1)=42*58=2436,取e=13,求e的逆元d解方程d?e=1

mod24362436=13*187+5,13=2*5+35=3+2,3=2+1所以1=3-2，2=5-3，3=13-2*55=2436-13*187所以，1=3-2=3-（5-3）=2*3-5=2*（13-2*5）-5=2*13-5*5=2*13-5*（2436-13*187）=937*13-5*2346即937*13≡1mod2436取e=13時d=937RSA算法的實現(xiàn)

公開密鑰算法若有明文publickeyencryptions先將明文分塊為pu

bl

ic

ke

nc

ryptions將明文數(shù)字化令abz分別為000125得1520011108021004240413021724151908141418利用加密可得密文0095164814101299136513792333213217511289公開密鑰算法關(guān)于素數(shù)的分布1-10025101-20021201-30016301-40016401-50017501-60014601-70016701-80014801-90015901-100014素數(shù)定理：當X變得很大時，從2到X區(qū)間的素數(shù)數(shù)目

(X)與X/ln(X)的比值趨近于1，即(X)X/ln(X)=1limx

X

(X) X/ln(X)

(X)X/ln(X)10001681451.15910,0001,2291,0861.132100,0009,5928,6861.1041,000,00078,49872,3821