第二章密碼學基礎知識內容提要密碼學概述1典型對稱密碼系統234典型公開密碼系統國密算法5密碼分析密碼案例1942年6月，在關系到日美太平洋戰爭轉折點的中途島海戰中，日軍出現了兩起嚴重泄密事件：一是在戰役發起前夕，日海軍第二聯合特別陸戰隊的一個副官，用低等級密碼發電說：六月五日以后，本部隊的郵件請寄到中途島。二是日軍軍港的一個后勤部門，用簡易密碼與擔任進攻中途島任務的部隊聯系淡水供應問題。結果，以上兩電均被設在珍珠港的美國海軍破譯，從而掌握了日軍進攻中途島的日期和兵力，致使日軍在戰役中遭到慘敗。密碼技術密碼技術通過對信息的變換或編碼，將機密的敏感信息變換成攻擊者難以讀懂的亂碼型信息，以此達到兩個目的：使攻擊者無法從截獲的信息中得到任何有意義信息；使攻擊者無法偽造任何信息。密碼技術不僅可以解決網絡信息的保密性，而且可用于解決信息的完整性、可用性及不可否認性，是網絡安全技術的核心和基石，是攻防都需了解的技術。概念：密碼系統密碼系統(Cryptosystem)，也稱為密碼體制，用數學符號描述為：S={M,C,K,E,D}M是明文空間，表示全體明文集合。明文是指加密前的原始信息，即需要隱藏的信息；C是密文空間，表示全體密文的集合。密文是指明文被加密后的信息，一般是毫無識別意義的字符序列；K是密鑰或密鑰空間。密鑰是指控制加密算法和解密算法得以實現的關鍵信息，可分為加密密鑰和解密密鑰，兩者可相同也可不同；密碼算法是指明文和密文之間的變換法則，其形式一般是計算某些量值或某個反復出現的數學問題的求解公式，或者相應的程序。E是加密算法，D是解密算法。解密算法是加密算法的逆運算，且其對應關系是唯一的。典型密碼系統組成發送者加密器c=E(k1,m)解密器m=D(k2,

c)接收者密鑰產生器非法侵入者密碼分析員（竊聽者）密鑰信道mccmm’=h(c)k1k2主動攻擊被動攻擊密鑰信道概念：密碼學密碼學(cryptology)：是一門關于發現、認識、掌握和利用密碼內在規律的科學，由密碼編碼學(cryptography)和密碼分析學(cryptanalysis)組成。密碼編碼學對信息進行編碼實現信息隱藏的一門學科。主要依賴于數學知識。主要方法有：換位、代換、加亂密碼系統的安全策略密碼系統可以采用的兩種安全策略：基于算法保密和基于密碼保護。基于算法保密的策略有沒有什么不足之處？？算法的開發非常復雜。一旦算法泄密，重新開發需要一定的時間；不便于標準化：由于每個用戶單位必須有自己的加密算法，不可能采用統一的硬件和軟件產品；不便于質量控制：用戶自己開發算法，需要好的密碼專家，否則對安全性難于保障。密碼系統的設計要求設計要求：系統即使達不到理論上不可破譯，也應該是實際上不可破譯的(也就是說，從截獲的密文或某些已知的明文和密文對，要決定密鑰或任意明文在計算上是不可行的)；加密算法和解密算法適用于所有密鑰空間的元素；系統便于實現和使用方便；系統的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰（著名的Kerckhoff原則，現代密碼學的一個基本原則）。密碼體制分類密碼體制從原理上分為兩類：單鑰密碼體制(One-keySystem)或對稱密碼體制（SymmetricCryptosystem）雙鑰密碼體制(Two-KeySystem)或公開密碼體制（PublicKeyCryptosystem）密碼學發展簡史(1/4)一般來說，密碼學的發展劃分為三個階段：第一階段為從古代到1949年。這一時期可以看作是科學密碼學的前夜時期，這階段的密碼技術可以說是一種藝術，而不是一種科學，密碼學專家常常是憑知覺和信念來進行密碼設計和分析，而不是推理和證明。密碼學發展簡史(2/4)一般來說，密碼學的發展劃分為三個階段：第二階段為從1949年到1975年。1949年Shannon發表的“保密系統的信息理論”為私鑰密碼系統建立了理論基礎，從此密碼學成為一門科學，但密碼學直到今天仍具有藝術性，是具有藝術性的一門科學。這段時期密碼學理論的研究工作進展不大，公開的密碼學文獻很少。密碼學發展簡史(3/4)一般來說，密碼學的發展劃分為三個階段：第三階段為從1976年至今。1976年diffie和hellman發表的文章“密碼學的新動向”一文導致了密碼學上的一場革命。他們首先證明了在發送端和接受端無密鑰傳輸的保密通訊是可能的，從而開創了公鑰密碼學的新紀元。密碼學發展簡史(4/4)在密碼學發展史上有兩個重要因素：戰爭的刺激和科學技術的發展推動了密碼學的發展。信息技術的發展和廣泛應用為密碼學開辟了廣闊的天地。一、對稱密碼系統對稱密碼體制：概述對稱密碼體制（symmetriccryptosystem）的加密密鑰和解密密鑰相同，也叫單鑰密碼體制或者秘密密碼體制。發送者加密器c=E(k

,m)解密器m=D(k,

c)接收者密鑰產生器密鑰信道mcmkk密鑰信道對稱密碼體制：概述對稱密碼算法的設計思想：古典密碼：以代換（或代替，Substitution）和置換（Permutation）運算為基礎現代對稱密碼：多以混亂（confusion）和擴散（diffusion）運算為基礎古典密碼思想：代換與置換置換對明文字符按某種規律進行位置的交換而形成新的排列代換將明文字母替換成其他字母、數字或符號的方法擴散所謂擴散，就是將算法設計得使每一比特明文的變化盡可能多地影響到輸出密文序列的變化，以便隱蔽明文的統計特性；將每一位密鑰的影響也盡可能迅速地擴展到較多的輸出密文比特中去。擴散的目的是希望密文中的任一比特都要盡可能與明文、密文相關聯，或者說，明文和密鑰中任何一比特的改變，對密文的每個比特都有影響，能夠以50%的概率改變密文的每個比特擴散的舉例說明無擴散技術的加密

p1:00000000c1:00000010p2:00000001c2:00000011有擴散技術的加密

p1:00000000c1:01011010p2:00000001c2:11101011混亂所謂混亂，是指在加密變換過程中使得明文、密鑰以及密文之間的關系盡可能地復雜化，以防密碼破譯者采用統計分析法進行破譯攻擊。混亂可以用“攪拌機”來形象地解釋，將一組明文和一組密鑰輸入到算法中，經過充分混合，最后變成密文。執行這種“混亂”作業的每一步都必須是可逆的，即明文混亂以后能得到密文，反之，密文經過逆向的混亂操作以后能恢復出明文。對稱密碼體制：概述對稱密碼體制對明文加密有兩種方式：序列密碼（或流密碼，StreamCipher）分組密碼(BlockCipher)序列密碼（1/2）主要原理：以明文的比特為加密單位，用某一個偽隨機序列作為加密密鑰，與明文進行異或運算，獲得密文序列；在接收端，用相同的隨機序列與密文進行異或運算便可恢復明文序列。=10111101…---------------=00110010…

10001111…

00110010…=

10111101…密鑰序列產生算法密鑰序列種子密鑰密鑰序列產生算法密鑰序列種子密鑰序列密碼（2/2）序列密碼算法的安全強度完全取決于偽隨機序列的好壞，因此關鍵問題是：偽隨機序列發生器的設計。優點：錯誤擴散小（一個碼元出錯不影響其它碼元）；速度快、實時性好；安全程度高。缺點：密鑰需要同步分組密碼（1/3）主要原理：在密鑰的控制下一次變換一個明文分組；將明文序列以固定長度進行分組，每一組明文用相同的密鑰和加密函數進行運算。加密算法解密算法密鑰K=(k0,k1,…,kL-1)密鑰K=(k0,k1,…,kL-1)明文X=(x0,x1,…,xm-1)明文X=(x0,x1,…,xm-1)密文Y=(y0,y1,…,ym-1)工作模式電碼本模式(ElectronicCodebookMode，ECB)密碼分組鏈接模式(CipherBlockChaining，CBC)密碼反饋模式(CipherFeedback，CFB)計數器模式(Counter，CTR)輸出反饋模式

(OutputFeedback，OFB)實際應用時，分組密碼名稱中常帶上工作模式，如DES-CBC分組密碼（2/3）分組密碼（3/3）優缺點：容易檢測出對信息的篡改，且不需要密鑰同步，具有很強的適應性；（與序列密碼相比）分組密碼在設計上的自由度小。最典型分組密碼是DES數據加密標準，它是單鑰密碼體制的最成功的例子。二、公開密碼系統公開密碼體制1976年，Diffie、Hellmann在論文“Newdirectionsincryptography”提出了雙鑰密碼體制（奠定了公鑰密碼系統的基礎），每個用戶都有一對密鑰：一個是公鑰（PK），可以像電話號碼一樣進行注冊公布；另一個是私鑰（SK），由用戶自己秘密保存；兩個密鑰之間存在某種算法聯系，但由一個密鑰無法或很難推導出另一個密鑰。又稱為公鑰密碼體制或非對稱密碼體制（asymmetriccryptosystem）。發送者加密器c=E(m,k1)解密器m=D(c,k2)接收者密鑰產生器密鑰信道mcmk1k2密鑰信道公開密碼體制：特點整個系統的安全性在于：從對方的公鑰PK和密文中要推出明文或私鑰SK在計算上是不可行的公開密碼體制的主要特點是將加密和解密能力分開，可以實現：多個用戶加密的消息只能由一個用戶解讀：保密通信；只由一個用戶加密消息而使多個用戶可以解讀：數字簽名認證。公開密碼體制：實現技術根據其所依據的數學難題可分為4類：大整數分解問題類：RSA密碼體制（最著名的雙鑰密碼體制）橢圓曲線類（橢園曲線上的離散對數問題）離散對數問題類（基于有限域乘法群上的離散對數問題）背包問題三、對稱和公開的混合使用鏈式加密對稱和非對稱結合內容提要密碼學概述1典型對稱密碼系統234典型公開密碼系統國密算法5密碼分析一、DESDES密碼體制DES是IBM公司于1970年研制的DES(DataEncryptionStandard)算法。該算法于1977年1月15日被美國國家標準局NBS頒布為商用數據加密標準，每5年被評估1次。DES加密過程64bit明文數據初始置換IP乘積變換（16次迭代）逆初始置換IP-164bit密文數據64bit密鑰子密鑰生成輸入輸出初始置換初始置換對輸入的比特位置進行調整。通過初始置換表實現初始置換的功能舉例來看，輸入為8位01110010初始置換表為：則輸出為：10001101輸入位12345678輸出位35612487DES加密過程64bit明文數據初始置換IP乘積變換（16次迭代）逆初始置換IP-164bit密文數據64bit密鑰子密鑰生成輸入輸出通過64bit密鑰產生16個不同的子密鑰，每個子密鑰為48bit，在每一輪中使用。子密鑰產生有專門的算法，圖4.1416次迭代通過初始置換得到X0，X0被分為左右兩部分，即X0

=L0R0

16次迭代：i=1,2,…,16

Xi-1=Li-1Ri-1，Li=Ri-1，Ri=Li-1

F(Ri-1,Ki)Li-1Ri-1F+LiRiKi每次迭代只對右邊的32bit進行一系列的加密變換：擴展運算E、密鑰加密運算、選擇壓縮運算S、置換運算T及左右異和運算。F(Ri-1,Ki)=P(S(E(Ri-1)Ki))每次迭代的最后，把左邊的32bit與右邊變換得到的32bit逐位模2加，作為下一輪迭代時右邊的段將變換前的右邊的段直接送到左邊的寄存器中作為下一輪迭代時左邊的段S是一組八個變換S1，S2，S3，…，S8，稱為S盒，每個盒以6位輸入，4位輸出，S盒構成了DES安全的核心。S盒替換共8個S盒S盒的規則S-盒2S-盒3S-盒4S-盒6S-盒7S-盒8S-盒1S-盒5S-盒的構造P盒置換保證上一輪某個s盒的輸出對下一輪多個s盒產生影響DES解密解密方法：把子密鑰的順序顛倒過來，即把K1～K16換為K16～K1,再輸入密文，采用與加密同樣的算法，就可還原明文DES的安全性DES系統的保密性主要取決于什么？密鑰的安全性。窮舉法破解有人認為S盒可能含有某種“陷門”，美國國家安全機關可以解密。如何將密鑰安全、可靠地分配給通信雙方，在網絡通信條件下就更為復雜，包括密鑰產生、分配、存儲、銷毀等多方面的問題，統稱為密鑰管理。密鑰管理是影響DES等單鑰密碼體制安全的關鍵因素。因為即使密碼算法再好，若密鑰管理處理不當，也很難保證系統的安全性。DES的56位密鑰可能太小1998年7月，EFE宣布攻破了DES算法，他們使用的是不到25萬美元的特殊的“DES破譯機”，這種攻擊只需要不到3天的時間。以現有網絡計算能力，破解非常容易DES的迭代次數可能太少（16次恰巧能抵抗差分分析）DES的安全性DES破解器1998年，電子前哨基金會（EFF）制造了一臺DES破解器，它使用多個DeepCrack芯片搭成而成，造價約$250,000，包括1,856個自定義的芯片，在56個小時內利用窮盡搜索的方法破譯了56位密鑰長度的DES2025/3/1851二、3DES3DES在DES算法的基礎上，于1985年提出了TripleDES（3DES）加密算法，在1999年被加入到DES系統當中。原理：3個密鑰或2個密鑰執行3次常規的DES加密。c=E(k3,D(k2,E(k1,m)))m=D(k1,E(k2,D(c,k3)))優點：3DES的密鑰長度是192位，其中去除校驗位的有效密鑰長度為168位，足夠抵抗窮舉攻擊。缺點：算法較慢，相當于執行3遍DES。3DES三、AESAES1997年4月15日美國國家標準技術研究所(NIST)發起征集AES（AdvancedEncryptionStandards）算法的活動，并專門成立了AES工作組基本要求：AES應該像DES和TDES那樣是一個塊加密方法，并且至少像TDES一樣安全，但是其軟件實現應該比TDES更加有效NIST指定AES必須：公開算法；分組大小為128比特的分組密碼，支持密鑰長度為128、192和256比特；通用性對AES候選方案的評審標準有3條：（1）全面的安全性，這是最為重要的指標。（2）性能，特別是軟件實現的處理性能。（3）算法的知識產權等特征。

AES1998年確定第一輪15個候選者1999年確定第二輪五個候選者

MARSRC6RijndaelSerpentTwofishAES經過多輪評估、測試，NIST于2000年10月2日正式宣布選中比利時密碼學家JoanDaemen和VincentRijmen提出的密碼算法RijndaelNIST于2001年11月26日發布于FIPSPUB197，并在2002年5月26日成為有效的標準AESRijndael匯聚了安全、效率、易用、靈活等優點，使它能成為AES最合適選擇不屬于Feistel結構加密、解密相似但不完全對稱支持128/192/256(/32=Nb)數據塊大小支持128/192/256(/32=Nk)密鑰長度有較好的數學理論作為基礎結構簡單、速度快AESAES算法與Rijndael算法常常將DES算法稱為Rijndael算法嚴格地講，Rijndael算法和AES算法并不完全一樣，因為Rijndael算法是數據塊長度和加密密鑰長度都可變的迭代分組加密算法，其數據塊和密鑰的長度可以是128位、192位和256位。盡管如此，在實際應用中二者常常被認為是等同的AESRijndael算法采用替換/轉換網絡，每一輪包含三層非線性層：字節替換，由16個S-盒并置而成，主要作用是字節內部混淆；線性混合層：通過列混合變換和行移位變換確保多輪密碼變換之后密碼的整體混亂和高度擴散；輪密鑰加層：簡單地將輪（子）密鑰矩陣按位異或到中間狀態矩陣上S-盒選取的是有限域GF（28）中的乘法逆運算AES算法描述預處理：先對要加密的數據塊進行預處理，使其成為一個長方形的字陣列，每個字含4個字節，占一列，每列4行存放該列對應的4個字節，每個字節含8bit信息。Nb表示分組中字的個數（也就是列的個數），Nk表示密鑰中字的個數AES算法描述預處理：先對要加密的數據塊進行預處理，使其成為一個長方形的字陣列，每個字含4個字節，占一列，每列4行存放該列對應的4個字節，每個字節含8bit信息。Nb表示分組中字的個數（也就是列的個數），Nk表示密鑰中字的個數AES算法描述預處理多輪迭代：明文分組進入多輪迭代變換，迭代的輪數Nr由Nb和Nk共同決定，可查表AES加解密過程AES最后一輪不做列混合運算安全性：Rijndael算法進行8輪以上即可對抗線性密碼分析、差分密碼分析，亦可抵抗專門針對Square算法提出的Square攻擊。當密鑰長度分別為128比特、192比特和256比特時，對應的運算量分別為2127、2191和2255靈活性：Rijndael的密鑰長度可根據不同的加密級別進行選擇。Rijndael的循環次數允許在一定范圍內根據安全要求進行修正。AES四、IDEAIDEA國際數據加密算法(IDEA,InternationalDataEncryptionalgorithm)中國學者來學嘉博士與著名密碼學家JamesMassey于1990年提出的一種分組密碼算法定義了三種基本運算：異或，整數加密，整數乘數，并設計了具有良好擴散功能的MA乘加結構IDEAIDEA安全性1992年進行了改進：抗差分攻擊密鑰為128bit，窮舉攻擊要試探2128個密鑰，若用每秒100萬次加密的速度進行試探，大約需要1013年。分組密碼算法比較算法密鑰長度分組長度循環次數DES566416三重DES112/1686448IDEA128648AES128/192/256128/192/25610/12/14五、流密碼RC4RC4（RivestCipher4）是一種流密碼算法，由RonRivest在1987年設計出的密鑰長度可變的加密算法簇。起初該算法是商業機密，直到1994年，才公諸于眾RC4基本概念RC4算法過程RC4算法過程RC4算法過程RC4安全性分析當密鑰長度超過128位時，以當前的技術而言，RC4是很安全的，RC4也是唯一對2011年TLS1.0BEAST攻擊免疫的常見密碼。近年來RC4爆出多個漏洞，安全性有所下降。例如，2015年比利時魯汶大學的研究人員MathyVanhoef與FrankPiessens，公布了針對RC4加密算法的新型攻擊方法，可在75小時內取得cookie的內容。因此，2015年IETF發布了RFC7465，禁止在TLS中使用RC4，NIST也禁止在美國政府的信息系統中使用RC4。著名的分布式代碼管理網站Github從2015年1月5日起也停止對RC4的支持RC4單鑰密碼體制的優缺點單鑰密碼技術可以用來做什么？加密和認證單鑰密碼體制具有加解密算法簡便高效，加解密速度快、安全性很高的優點，應用非常廣泛；存在一些問題，而且靠自身無法解決：密鑰分配困難；需要密鑰量大（n個用戶之間互相進行保密通信，需要n(n-1)/2個密鑰）內容提要密碼學概述1典型對稱密碼系統234典型公開密碼系統國密算法5密碼分析一、RSARSA密碼體制RSA公鑰體制是1978年由麻省理工學院3位年青數學家：Rivest,Shamir,Adleman提出的基于數論的雙鑰密碼體制。（開始被稱作“MIT體制”）RSA體制基于“大數分解和素數檢測”這一著名數論難題：將兩個大素數相乘十分容易，但將該乘積分解為兩個大素數因子卻極端困難；素數檢測就是判定一個給定的正整數是否為素數。84整數的因子分解問題（1/3）整數的因子分解問題：將兩個素數11927和20903相乘，可以很容易地得出249310081。但是將它們的積249310081分解因子得出上述兩個素數卻要困難得多。即使最大型的計算機將一個大的乘積數分解還原為組成此數的兩個素數也要很長時間。從一個公鑰和密文中恢復出明文的難度等價于分解兩個大素數之積。整數的因子分解問題（2/3）Rivest，Shamir，Adleman提出，分解一個130位的兩個素數的乘積數需要幾百萬年的時間，為了證明這一點，他們找到1個129位數，并向世界挑戰找出它的兩個因子。RSA129：11431862575788886766923577997614661201021829672124236256256184293570693524573389783059712356395870558989075147599290026879543541整數的因子分解問題（3/3）世界各地600多個研究人員和愛好者通過Internet協調各自計算機的工作向這個129位數發動了進攻。花費了近一年的時間，終于分解出了這個數的兩個素數，其中一個長64位，另一個長65位，這兩個素數分別為：349052951084765094914784961990389813341776463849338784399082057732769132993266709549961988190834461413177642967992942539539798288533

說明兩個問題：（1）整數的因子分解問題是一個計算開銷非常大的問題；（2）Internet協同計算能力的強大。RSA密鑰產生過程產生過程如下：生成兩個大素數p

和q；計算這兩個素數的乘積n=p*q；計算小于n并且與n互質的整數的個數，即歐拉函數φ(n)=(p-1)*(q-1)；隨機選擇一個加密密鑰e，使e滿足1<e<φ(n)，并且e和φ(n)互質；利用歐幾里德擴展算法計算e的逆元d，以滿足：

e*d

≡1modφ(n)公鑰PK={e,n}；對應的私鑰SK=d6xt5af歐拉函數在數論中，對正整數n，歐拉函數是小于或等于n的數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為Euler’stotientfunction、φ函數、歐拉商數等，例如：φ(1)=1，唯一和1互質的數就是1本身；φ(8)=4，因為1,3,5,7均和8互質。歐拉函數給定一個正整數n，用ψ(n)表示比n小且與n互為素數的正整數的個數，稱ψ(n)為歐拉函數ψ(n)＝r1a1-1(r1-1)r2a2-1(r2-1)…rnan-1(rn-1)

其中n=r1a1r2a2…rnan例如：

24=23*31

ψ(24)=23-1(2-1)*31-1(3-1)=8{1,5,7,11,13,17,19,23}

歐拉定理若整數a和n互素，則aψ(n)

=1(modn)舉例說明：ψ(24)=8{1,5,7,11,13,17,19,23}是小于24并與24互素的數18=1mod24即：1ψ(24)=1mod2458=1mod24即：5ψ(24)=1mod2478=1mod24即：7ψ(24)=1mod24……RSA密鑰產生過程產生過程如下：生成兩個大素數p

和q；計算這兩個素數的乘積n=p*q；計算小于n并且與n互質的整數的個數，即歐拉函數φ(n)=(p-1)*(q-1)；隨機選擇一個加密密鑰e，使e滿足1<e<φ(n)，并且e和φ(n)互質；利用歐幾里德擴展算法計算e的逆元d，以滿足：

e*d≡1modφ(n)公鑰PK={e,n}；對應的私鑰SK=6dzf9yu歐幾里德擴展算法歐幾里德算法又稱輾轉相除法，用于計算兩個整數a,b的最大公約數。其計算原理依賴于下面的定理：gcd(a,b)=gcd(b,amodb)RSA密鑰產生過程產生過程如下：生成兩個大素數p

和q；計算這兩個素數的乘積n=p*q；計算小于n并且與n互質的整數的個數，即歐拉函數φ(n)=(p-1)*(q-1)；隨機選擇一個加密密鑰e，使e滿足1<e<φ(n)，并且e和φ(n)互質；利用歐幾里德擴展算法計算e的逆元d，以滿足：

e*d≡1modφ(n)公鑰PK={e,n}；對應的私鑰SK=vu6mrobRSA密鑰產生的實例選擇素數:p=17，q=11計算n=p*q=17*11=187計算φ(n)=(p–1)*(q-1)=16*10=160選擇

e：gcd(e,160)=1；選擇e=7確定d：d*e=1mod160andd<160；d=23因為23*7=161=1*160+1公鑰PK={7,187}私鑰SK={23}RSA的加解密操作為了對消息內容M進行加密，發送者:獲得接收者的公鑰PK={e,n}計算:C=Memodn為了解密密文C，接收者：使用自己的私鑰SK=fx8i1hn計算:M=Cd

modnRSA加解密操作實例假定：接收方公鑰PK={7,187}接收方私鑰SK={23}

給定消息M=88加密:C=887mod187=11解密:M=1123mod187=88應用一：加密通信用戶將自己的公鑰登記在一個公開密鑰庫或實時公開，私鑰則被嚴格保密。信源為了向信宿發送信息，去公開密鑰庫查找對方的公開密鑰，或臨時向對方索取公鑰，將要發送的信息用這個公鑰加密后在公開信道上發送給對方。對方收到信息（密文）后，則用自己的私鑰解密密文，從而讀取信息。優點：省去了從秘密信道傳遞密鑰的過程RSA的應用應用二：數字簽名RSA的應用RSA公鑰體制的優缺點優點：保密強度高密鑰分配及管理簡便可以用于數字簽名實現身份認證缺點：運算復雜，速度慢：硬件實現時，RSA比DES要慢大約1000倍，軟件實現時，RSA比DES要慢大約100倍。很多實際系統中，只用RSA來交換DES的密鑰，而用DES來加密主體信息。RSA公鑰體制的安全性依賴于未被證明的“整數的因子分解問題”假若數學理論進一步發展，發現“整數的因子分解問題”是一個可以快速解決的問題？以RSA為代表的公鑰體制的加密操作是公開的，任何人都可以選擇明文，并利用公開的公鑰來攻擊RSA公鑰體制。明文空間必須足夠大才能夠防止窮盡搜索明文空間攻擊；如果用公鑰體制加密會話密鑰，會話密鑰必須足夠的長。RSA攻擊方法窮舉攻擊：嘗試所有可能的密鑰數學攻擊：對兩個素數乘積的因子分解（FAC問題）計時攻擊：依賴于解密算法的運行時間選擇密文攻擊：利用了RSA算法的性質RSA安全性數學攻擊RSA安全性計時攻擊RSA安全性RSA安全性二、Diffie-Hellman密鑰交換算法Diffie-Hellman密鑰交換算法（簡稱為“DH算法”或“DH交換”）由WhitfieldDiffie和MartinHellman于1976提出，是最早的密鑰交換算法之一，它使得通信的雙方能在非安全的信道中安全的交換密鑰，用于加密后續的通信消息。該算法被廣泛應用于安全領域，如TLS和IPsec協議DHDiffie-Hellman算法的有效性依賴于計算離散對數的難度DH算法過程DH示例：假定素數q=97，取97的一個原根a=5。A和B分別選擇私有密鑰XA=36和XB=58，各自計算得到公鑰分別為：YA=50，YB=44，秘密密鑰K=75DH示例DH優點僅當需要時才生成密鑰，減小了將密鑰存儲很長一段時間而致使遭受攻擊的機會除對全局參數的約定外，密鑰交換不需要事先存在的基礎設施DH缺點沒有提供雙方身份的任何信息，因此易受中間人攻擊。這一缺陷可以通過數字簽名和公鑰證書來解決容易遭受阻塞性攻擊。由于算法是計算密集性的，如果攻擊者請求大量的密鑰，被攻擊者將花費大量計算資源來求解無用的冪系數而不是在做真正的工作DHDH三、ElGamal公鑰密碼體制ElGamal公鑰密碼體制是由T.ElGamal于1984年提出，算法既能用于數據加密也能用于數字簽名。與Diffie-Hellman算法一樣，其安全性也依賴于計算有限域上離散對數這一難題ElGamal密鑰產生方法選擇一個素數q，獲取素數q的一個原根

。其中，q和

是公開的，并且可由一組用戶共享生成一個隨機數x作為其秘密的解密密鑰，使得1≤x≤q–1，計算y=

xmodq，則公鑰為(y,

,q)，私鑰是xElGamal加密如果用戶B要向A發送信息，則其利用A的公鑰(y,

,q)對信息進行加密解密通過計算U=m1xmodq恢復密鑰，然后恢復明文：m=m2×(U)-1modqElGamal安全分析ElGamal算法的安全性是建立在有限域上求離散對數問題的難解性上為了安全，一般要求在ElGamal密碼算法的應用中，素數q按十進制數表示，那么至少應該有150位數字，并且q–1至少應該有一個大的素數因子。同時，加密和簽名所使用的k必須是一次性的。如果k不是一次性的，時間長了就可能被攻擊者獲得。ElGamal四、ECC橢圓曲線密碼（EllipticCurveCryptography,ECC）是一種公開密鑰密碼體制，于20世紀80年代由華盛頓大學的NealKoblitz和IBM的VictorMiller分別獨立提出。ECC以橢圓曲線理論為基礎，利用有限域上橢圓曲線的點構成的Abel群離散對數難解性，實現加密、解密和數字簽名，將橢圓曲線中的加法運算與離散對數中的模乘運算相對應，就可以建立基于橢圓曲線的對應密碼體制。ECCEC橢圓群上的離散對數問題（EllipticCurveDiscreteLogarithmProblem,ECDLP）指的是：從橢圓曲線E[K]上的解點所構成的交換群中可以找到一個n階循環子群，當n是足夠大的素數時，這個循環子群中的離散對數問題是困難的。具體而言，設A和B是橢圓曲線上的兩個解點，以點A為生成元來生成n階循環子群，x為一正整數，且

，若給定A和x，可以很容易地計算出B=xA，但要是已知A，B點，要想找出x則很困難ECDLP目前也只有特殊的幾類橢圓曲線的ECDLP被解決，大多數仍然無解。對已解決的幾類ECDLP，可以找到一條橢圓曲線Y，將明文編碼后嵌入Y的解點中，再對Y進行加密，加密算法可以是我們以前熟知的算法。常見橢圓曲線密碼有：用于加必的EC-ElGamal（EllipticCurveElGamal），用于密鑰交換的ECDH（EllipticCurveDiffie-Hellman）和ECDHE（ECDHEphemeral），用于數字簽名的ECDSA（EllipticCurveDigitalSignatureAlgorithm）等ECCECE：用于加密EC與EIGamalECDH：用于密鑰交換ECDHE：動態分配密鑰ECC與DH結合(ECDH)ECDSA：用于數字簽名ECC與DSA結合（ECDSA）ECC的主要優勢是密鑰小，算法實施方便，計算速度快，非常適于無線應用環境（在IoT領域應用廣泛），而且安全性高ECC安全性ECC依賴的橢圓曲線離散對數難題的計算復雜度是指數級，而RSA所采用的整數因式分解難題的計算復雜度是亞指數級，所以橢圓曲線密碼從理論上來說更難以攻破，更安全ECC非對稱密碼比傳統對稱密碼更安全？不是！任何加密方法安全性依賴于密鑰的長度和破譯密文所需要的計算量討論非對稱密碼是一種通用的方法，傳統對稱密碼已經過時？不是！非對稱密碼的計算量大，目前不能取代傳統密碼“非對稱密碼學僅限于用在密鑰管理和簽名此類應用上，這幾乎是被廣泛接受的事實”討論傳統對稱密碼中與密鑰分配中心KDC的握手是一件麻煩的事情，非對稱密碼的密鑰管理非常簡單？不！只是有所簡化，但也需要某種形式的協議，該協議一般包含一個中心代理，處理并不比傳統密碼中的那些工程更簡單討論內容提要密碼學概述1典型對稱密碼系統234典型公開密碼系統國密算法5密碼分析發展歷程國密算法是國家商用密碼算法的簡稱。自2012年以來，國家密碼管理局以《中華人民共和國密碼行業標準》的方式，陸續公布了SM2/SM3/SM4/SM9、祖沖之（ZUC）等密碼算法標準及其應用規范，并相繼納入ISO/IEC標準體系還有未公開的對稱密碼算法SM1/SM7國密算法主要的國密算法國密算法主要的國密算法國密算法主要的國密算法國密算法2015年4月起，陸續提交三個國密算法國際標準提案：SM3雜湊算法納入ISO/IEC10118-3，SM2數字簽名算法和SM9數字簽名算法納入ISO/IEC14888-3，SM4算法納入ISO/IEC18033-3。2017年11月，SM2和SM9正式成為ISO/IEC國際標準。2018年4月，SM3正式成為ISO/IEC國際標準中的算法。國密算法加入國際標準2020年8月，ZUC序列密碼算法作為“ISO/IEC18033-4:2011/AMD1:2020信息技術—安全技術—加密算法—第四部分：序列密碼—補篇1：ZUC”正式發布（2018年4月提交的標準草案）國密算法加入國際標準2021.6:SM4分組密碼算法作為ISO/IEC18033-3:2010補篇正式發布（2016.10正式提交，2017.4立項）國密算法加入國際標準北京大學關志副研究員的密碼學研究組開發維護了一個國密算法的開源實現項目GmSSL（官網：/，后改為/gmssl/index.jsp），項目源碼托管于GitHub（/guanzhi/GmSSL.git）支持所有公開的國密算法與OpenSSL兼容國密算法2020年1月1日《中華人民共和國密碼法》正式實施國密算法2020年1月1日《中華人民共和國密碼法》正式實施近年來，已有大量國內安全廠商在其各類安全產品中支持國密算法。密碼法實施后，很多單位在招標采購時，也要求支持國密算法。國密算法內容提要密碼學概述1典型對稱密碼系統234典型公開密碼系統國密算法5密碼分析密碼分析學（cryptanalysis）密碼分析學，俗稱：密碼破譯截收者在不知道解密密鑰和通信者所采用的加密算法的細節條件下，對密文進行分析，試圖獲取機密信息、研究分析解密規律的科學。密碼分析除了依靠數學、工程背景、語言學等知識外，還要依靠經驗、統計、測試、眼力、直覺判斷能力等因素，有時還要靠運氣。主要分析途徑窮舉破譯法(ExhaustiveAttackorBrute-forceMethod)分析破譯法窮舉破譯法解密思路：m=D(c,k2)方法一（

k2）：對截收的密文依次用各種可解的密鑰試譯，直接得到有意義的明文方法二（m）：在不變密鑰下，對所有可能的明文加密直到得到與截收的密文一致為止只要有足夠多的計算時間和存儲容量，原則上窮舉法破譯總是可以成功的。因此，密碼設計應使窮舉不可行。分析破譯法確定性分析法（數字分析法）：利用一個或幾個已知量（如已知密文或明文密文對）用數學關系式表示出所求未知量（如密鑰等）的方法統計分析法：利用明文的已知統計規律進行破譯的方法。對截收的密文進行統計分析，總結出密文的統計規律，并與明文的統計規律進行對照比較，從而提取出明文和密文之間的對應或變換信息。

五種攻擊唯密文攻擊(CiphertextOnlyAttacks)已知明文攻擊(KnownPlaintextAttacks)選擇明文攻擊(ChosenPlaintextAttacks)選擇密文攻擊(ChosenCiphertextAttack)選擇文本攻擊(ChosenTextAttack)2025/3/18149密碼攻擊唯密文攻擊(CiphertextOnlyAttacks)在僅知已加密文字的情況下進行窮舉攻擊，可取得原始明文中的全部信息、部分信息或解密密鑰。此時攻擊的條件就是：已知算法，不知道密鑰，要對密文進行強行破解。此方案適用于何種密碼體制？同時適用于對稱密碼體制和非對稱密碼體制2025/3/18150密碼攻擊已知明文攻擊(KnownPlaintextAttacks)前提條件：已知密文，已知明文，已知算法，求密鑰。2025/3/18151密碼攻擊選擇明文攻擊(ChosenPlaintextAttacks)攻擊者不但可以獲取明文―密文對（如事先任意選擇一定數量的明文，讓被攻擊的加密算法加密，并得到相應的密文），而且可以對這些明文-密文對進行選擇，從而選擇那些擁有更多特征的明文-密文對，以有利于對密碼的分析通過這一過程獲得關于加密算法的一些信息，以利于在將來更有效的破解由同樣加密算法（以及相關密鑰）加密的信息。在最壞情況下，攻擊者可以直接獲得解密用的鑰匙。適用于什么樣的密碼機制？2025/3/18152密碼攻擊選擇密文攻擊(ChosenCiphertextAttack)指密碼分析者可以選擇一些密文，并得到相應的明文。任務目標是推出密鑰。多用于攻擊公鑰密碼體制，也可用于對稱密碼體制2025/3/18153選擇文本攻擊(ChosenTextAttack)選擇明文攻擊和選擇密文攻擊的組合，即密碼分析者在掌握密碼算法的前提下不僅能夠選擇明文并得到對應的密文，而且還能選擇密文得到對應的明文。這種情況往往是密碼分析者通過某種手段暫時控制加密機和解密機密碼攻擊分析破譯法王小云院士：模差分比特分析法：MD4、MD5、RIPEMD、HAVAL-128、SHA12025/3/18155密碼分析前面講到的是傳統的密碼分析學，這類方法將密碼算法看作是一個理想而抽象的數學變換，假定攻擊者不能獲取除密文和密碼算法以外的其他信息。密鑰越長，上述方法越難破解。就沒有其它分析方法嗎？密碼分析思考：密碼算法的設計安全性等于密碼算法的實現安全性嗎？旁路分析現實世界中，密碼算法的實現總需要基于一個物理平臺，即密碼芯片。由于芯片的物理特性會產生額外的信息泄露，如密碼算法在執行時無意泄露的執行時間、功率消耗、電磁輻射、Cache訪問特征、聲音等信息，或攻擊者通過主動干擾等手段獲取的中間狀態比特或故障輸出信息等，這些泄露的信息同密碼的中間運算、中間狀態數據存在一定的相關性，從而為密碼分析提供了更多的信息，利用這些泄露的信息就有可能分析出密鑰，這種分析方法稱為旁路分析。旁路分析密碼旁路分析中攻擊者除了可在公開信道上截獲消息，還可觀測加解密端的旁路泄露，然后結合密碼算法的設計細節進行密鑰分析，避開了分析復雜的密碼算法本身，使得一些傳統分析方法無法破解的密鑰成為可能。旁路分析旁路分析旁路分析旁路分析近幾年來，密碼旁路分析技術發展較快，出現了多種旁路分析方法。根據旁路泄露信息類型的不同，可分為計時分析、探討分析、故障分析、功耗分析、電磁分析、Cache分析、聲音分析；根據旁路分析方法的不同，可分為簡單旁路分析、差分旁路分析、相關旁路分析、模板旁路分析、隨機模型旁路分析、互信息旁路分析、Cache旁路分析、差分故障分析、故障靈敏度分析、旁路立方體分析、代數旁路分析、代數故障分析等。密碼算法和協議的工程實現分析即使密碼體系在理論上無懈可擊，在工程實現上也可能千瘡百孔，人們近年已經從密碼體系固若金湯的錯誤迷思中清醒過來，越來越多的密碼實現層面的漏洞被發現，2016年形成針對密碼實現漏洞發掘的高潮。Heartbleed漏洞是密碼協議實現時代碼層面的問題Poodle攻擊是密碼協議實現時的兼容性問題Logjam是密碼協議實現時的設計問題安卓上的MasterKey漏洞是因上層Java語言與下層C語言語義的不匹配對簽名證書校驗造成失效的問題2021.8.24：OpenSSL國密SM2爆出8.1分高危漏洞CVE-2021-3711細節：/news/secadv/20210824.txt成因：SM2解密時分配了一塊內存，解密后的結果可能大于該分配內存的容量，造成內存越界寫。該漏洞影響OpenSSL1.1.1l之前的所有包含SM2商密算法版本。業界一些基于OpenSSL改造過的商用國密算法版本也可能受該漏洞影響密碼算法和協議的工程實現分析2022.3.15：OpenSSL拒絕服務漏洞(CVE-2022-0778)

任何使用了OpenSSL中的BN_mod_sqrt()函數的程序，在攻擊者可以控制輸入的前提下，均受此漏洞影響，易受攻擊的場景包括：使用了服務器證書的TLS客戶端，使用客戶端證書的TLS服務器，從客戶那里獲取證書或私鑰的托管服務提供商，認證機構解析來自訂閱者的認證請求，以及任何存在解析ASN.1橢圓曲線參數的功能實現等密碼算法和協議的工程實現分析本章小結作業參考內容一、柯克霍夫原則（Kerckhoffs’sPrinciple）Thesystemmustbepractically,ifnotmathematically,indecipherable;Itmustnotberequiredtobesecret,anditmustbeabletofallintothehandsoftheenemywithoutinconvenience;Itskeymustbecommunicableandretainablewithoutthehelpofwrittennotes,andchangeableormodifiableatthewillofthecorrespondents;柯克霍夫原則Itmustbeapplicabletotelegraphiccorrespondence;Itmustbeportable,anditsusageandfunctionmustnotrequiretheconcourseofseveralpeople;Finally,itisnecessary,giventhecircumstancesthatcommanditsapplication,thatthesystembeeasytouse,requiringneithermentalstrainnortheknowledgeofalongseriesofrulestoobserve.柯克霍夫原則用一句話總結：“密碼系統的安全性應該僅僅依賴于密鑰的安全（thesecurityofacrypto-systemshoulddependsolelyonthesecrecyofthekey）”。柯克霍夫原則香農（Shannon）：敵人了解你的系統柯克霍夫原則隨著時代的發展，大家越發意識到柯克霍夫原則的重要性：對復雜的系統中的每一個細節進行保密既非常困難，同時一旦泄密也難以更換。而如果系統安全性僅僅依賴于很短的一串秘密信息，那么不但對其進行保密更為可行，且泄密之后可以用最小代價更新整個系統的安全性。因此，現代密碼系統基本上都拋棄了傳統的securitythroughobscurity理念，采用了開放式設計，所有系統實現均可公開，更多地把安全性防護集中在對密鑰的機密性保護之上。柯克霍夫原則進入計算機時代的密碼學應用中，沒有哪個加密算法和協議還依賴于人工操作，芯片和內存成為了加密運算的主戰場，人們開始逐漸將目光投向了網絡和計算機世界中的機密信息保護，關心如何在新時代繼續按照柯克霍夫原則來守衛關鍵系統的安全。可是，信息系統的變化，反過來卻引發了一場針對柯克霍夫原則的風暴！柯克霍夫原則2008：普林斯頓大學，后來成為安全研究領域巨星的J.AlexHalderman（/）和NadiaHeninger（/~nadiah/）兩位80后研究人員共同完成了一篇USENIXSecurity當年的最佳學生研究論文：利用物理技術冷卻被攻擊設備的內存，并將其轉移到其它系統上讀取其中信息：內存中的數據在低溫下并不會馬上消失，而是“逐漸凋零”柯克霍夫原則NadiaHeninger和HovavShacham很快在2009年的美密會上發表了另一篇論文ReconstructingRSAPrivateKeysfromRandomKeyBits，給出了一個非常具有震撼力的結論——攻擊者只需要隨機得到內存中RSA私鑰27%的部分，就可以有很大的概率完全恢復整個私鑰！柯克霍夫原則2014年的Heartbleed事件：僅僅因OpenSSL代碼中存在的內存破壞漏洞導致的內存信息泄露，在密碼學完全無關的維度上對密鑰防護一擊致命，可以說是反過來利用了Kerckhoffs'sPrinciple——攻擊者只需要竊取數據量微不足道的密鑰信息，就可以攻破整個密碼系統的安全屏障！柯克霍夫原則Kerckhoffs‘sPrinciple誕生之初，對密鑰的安全管理完全是交給人工解決的，可是到了互聯網時代，密鑰和其它數據一樣，都成了CPU和內存中無數需要處理的bit中的普通成員，對這種高度敏感的bit信息的保護遠遠不夠！柯克霍夫原則CCS2018:K-Hunt:PinpointingInsecureCryptographicKeysinExecutionTraces(/publications/ccs18.pdf)柯克霍夫原則需要精確地對程序中和密鑰相關的敏感信息進行全面的標記、追蹤和防護柯克霍夫原則二、計算上不可行討論計算上不可行：一個動態變化的概念討論討論討論討論討論關于京滬量子通信工程的爭論從未停止討論關于京滬量子通信工程的爭論從未停止討論關于京滬量子通信工程的爭論從未停止討論三、古典密碼古典密碼體制古典密碼大都比較簡單，可用手工或機械操作實現加解，現在已很少采用，但很多思想值得借鑒代換密碼（SubstituteCipher）換位密碼（TranspositionCipher）代換密碼代換密碼：將明文中字母由另一個或另一組字母替換。單表代換密碼：只使用一個密文字母表，并且用密文字母表中的一個字母來代換明文字母表中的一個字母。具有代表性的密碼是凱撒密碼（JuliusCaesar）。多表代換密碼：每次對明文的多個字母進行代換，其優點是容易將字母的自然頻度隱蔽或均勻化。采用特定的映射，將明文字母映射為密文字母e.g.例子:

明文：ATTACKATDAWN

密文：XCCXQJXCMXBF單表代換密碼（1/2）單表代換密碼（2/2）如何破解單表置換密碼算法？利用窮舉法？非常困難，要嘗試的次數：26!=4x1026利用統計法英文中字母出現的頻率是已知的可以通過分析字母在文檔出現頻率來推斷明文到密文的轉換。例如，在密文中出現最頻繁的字母很可能對應于字母‘e’還可以對二元字母組合和三元字母組合進行分析二元字母組合:如‘th’,‘an’,‘ed’三元字母組合:如‘ing’,‘the’,‘est’凱撒密碼(1/2)原理：明文中的字母在密文中用該字母循環右移k位后所對應的字母替換，其中k就是密鑰。例如，令k=3 ATTACKATDAWN

DWWDFNDWGDZQ凱撒密碼(2/2)如何破解凱撒密碼算法？利用窮舉法位移量k在1到25之間，逐個嘗試比普通的單表代換密碼的破解要簡單換位密碼算法換位密碼（TranspositionCipher）涉及到對明文字母進行一些位置變換，也稱置換密碼(Permutationcipher)，例如：將消息“ATTACKATDAWN”寫為:ATCADWTAKTAN進一步得到密文ATCADWTAKTAN現代密碼算法通常將代換和置換結合在一起使用換位密碼算法{1234}3421密鑰type4×4矩陣柵欄技術明文：canyoubelieveher問題？沒有消除字母的使用頻率，容易識別1234canyoubelievehercanyoubelievehernyacbe

u

oeviler

h

e密碼位置明文位置

2025/3/18202e=000h=001i=010k=011l=100r=101s=110t=111heilhitler001000010100001010111100000101111101110101111100000101110000110101100001110110111001110101srlhssthsr加密:

明文密鑰=密文Plaintext:Key:Ciphertext:Vernam或OTP加密2025/3/18203e=000h=001i=010k=011l=100r=101s=110t=111srlhssthsr110101100001110110111001110101111101110101111100000101110000001000010100001010111100000101heilhitler解密:

密文密鑰=明文Ciphertext:Key:Plaintext:Vernam或OTP加密四、分組密碼的五種加密模式分組密碼的五種模式ECB模式

CBC模式

CFB模式

OFB