密碼學基礎（1）目錄密碼學的起源、發展和現狀密碼學基本概念常規加密的現代技術密碼學發展階段1949年之前密碼學是一門藝術1949～1975年密碼學成為科學1976年以后密碼學的新方向——公鑰密碼學第1階段－古典密碼

密碼學還不是科學,而是藝術出現一些密碼算法和加密設備密碼算法的基本手段出現，針對的是字符簡單的密碼分析手段出現主要特點：數據的安全基于算法的保密第1階段－古典密碼Phaistos圓盤，一種直徑約為160mm的Cretan-Mnoan粘土圓盤，始于公元前17世紀。表面有明顯字間空格的字母，至今還沒有破解。20世紀早期密碼機第1階段－古典密碼1883年Kerchoffs第一次明確提出了編碼的原則：加密算法應建立在算法的公開不影響明文和密鑰的安全。這一原則已得到普遍承認，成為判定密碼強度的衡量標準，實際上也成為傳統密碼和現代密碼的分界線。計算機使得基于復雜計算的密碼成為可能相關技術的發展1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實驗室的HorstFeistel等幾篇技術報告主要特點：數據的安全基于密鑰而不是算法的保密

第2階段1949~19751976年：Diffie&Hellman

的

“NewDirectionsinCryptography”提出了不對稱密鑰密1977年Rivest,Shamir&Adleman提出了RSA公鑰算法90年代逐步出現橢圓曲線等其他公鑰算法主要特點：公鑰密碼使得發送端和接收端無密鑰傳輸的保密通信成為可能第3階段1976~1977年DES正式成為標準80年代出現“過渡性”的“PostDES”算法,如IDEA,RCx,CAST等90年代對稱密鑰密碼進一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出現2001年Rijndael成為DES的替代者第3階段1976~目錄密碼學的起源、發展和現狀密碼學基本概念常規加密的現代技術信息傳遞的一般問題信源、信道、信宿攻擊的種類：中斷（Interruption)（干擾）截取（Interception)(偵聽）修改（Modification）偽造（Fabrication)角色：通信雙方、可信第三方、不可信第三方介質：軟件、硬件、數據數據的性質Interruption--Interception--Modification--Fabrication--

AvailabilityConfidentiality

Integrity

Authenticity被動攻擊竊聽獲取消息內容流量分析主動攻擊中斷修改偽造破壞可用性破壞完整性破壞真實性攻擊分類基本概念密碼學(Cryptology):是研究信息系統安全保密的科學.密碼編碼學(Cryptography):主要研究對信息進行編碼,實現對信息的隱蔽.密碼分析學(Cryptanalytics):主要研究加密消息的破譯或消息的偽造.明文（Plaintext）：消息的初始形式；密文（CypherText）：加密后的形式記： 明文記為P且P為字符序列，P=[P1,P2,…,Pn]

密文記為C,C=[C1,C2,…,Cn]

明文和密文之間的變換記為C=E(P)及P=D(C)

其中C表示密文，E為加密算法；P為明文，D為解密算法 我們要求密碼系統滿足：P=D(E(P))基本概念需要密鑰的加密算法，記為：C=E(K,P),即密文消息同時依賴于初始明文和密鑰的值。實際上，E是一組加密算法，而密鑰則用于選擇其中特定的一個算法。加密與解密的密鑰相同，即：P=D(K,E(K,P))

加密與解密的密鑰不同，則：P=D(KD,E(KE,P))基本概念常規加密簡化模型加密算法足夠強大：僅知密文很難破譯出明文基于密鑰的安全性，而不是基于算法的安全性：基于密文和加/解密算法很難破譯出明文算法開放性：開放算法，便于實現常規加密的安全性常規加密系統的模型密碼體系是一個五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構成的有限集；（密鑰空間）（4）任意k∈K，有一個加密算法和相應的解密算法，使得和分別為加密解密函數，滿足dk(ek(x))=x

，這里x∈P。密碼體系形式化描述保密內容密鑰數量明文處理的方式密碼編碼系統分類受限制的（restricted)算法算法的保密性基于保持算法的秘密基于密鑰（key-based)的算法算法的保密性基于對密鑰的保密保密內容對稱密碼算法（symmetriccipher)

加密密鑰和解密密鑰相同，或實質上等同，即從一個易于推出另一個又稱秘密密鑰算法或單密鑰算法非對稱密鑰算法（asymmetriccipher)

加密密鑰和解密密鑰不相同，從一個很難推出另一個又稱公開密鑰算法（public-keycipher)

公開密鑰算法用一個密鑰進行加密,而用另一個進行解密其中的加密密鑰可以公開,又稱公開密鑰（publickey)，簡稱公鑰。解密密鑰必須保密,又稱私人密鑰（privatekey)私鑰，簡稱私鑰密鑰數量分組密碼（blockcipher)

將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。

流密碼（streamcipher)

又稱序列密碼。序列密碼每次加密一位或一字節的明文。明文處理方式密碼分析試圖破譯單條消息試圖識別加密的消息格式，以便借助直接的解密算法破譯后續的消息試圖找到加密算法中的普遍缺陷（無須截取任何消息）密碼分析的條件與工具已知加密算法截取到明文、密文中已知或推測的數據項數學或統計工具和技術語言特性計算機技巧與運氣密碼分析類型加密方案的安全性無條件安全：無論提供的密文有多少，如果由一個加密方案產生的密文中包含的信息不足以唯一地決定對應的明文除了一次一密的方案外，沒有無條件安全的算法安全性體現在：破譯的成本超過加密信息的價值破譯的時間超過該信息有用的生命周期攻擊的復雜性分析數據復雜性（datacomplexity）用作攻擊輸入所需要的數據處理復雜性（processingcomplexity）完成攻擊所需要的時間存儲需求（storagerequirement）進行攻擊所需要的數據量密鑰搜索所需平均時間替代置換轉子機經典加密技術明文的字母由其它字母或數字或符號代替若該明文被視為一個比特序列，則替代涉及到用密文比特模式代替明文比特模式替代愷撒密碼破譯以下密文：wuhdwb

lpsrvvleohTREATYIMPOSSIBLECi=E(Pi)=Pi+3加密算法：字母表：(密碼本）

ABCDEFGHIJKLMNOPQRSTUVWXYZ

defghijklmnopqrstuvwxyzabc愷撒密碼的特點單字母密碼（簡單替換技術）簡單，便于記憶缺點：結構過于簡單，密碼分析員只使用很少的信息就可預言加密的整個結構愷撒密碼的改進已知加密與解密算法C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)25個可能的密鑰k，適用Brute-ForceCryptanalysis明文的語言是已知的且易于識別其它單字母替換使用密鑰keyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopqrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectaulrbdfghijkmnoqvwxyz泄露給破譯者的信息更少其它單字母替換對字母進行無規則的重新排列

E(i)=3*imod26 ABCDEFGHIJKLMNOPQRSTUVWXYZ

adgjmpsvybehknqtwzcfilorux單字母變換任意替換：26！>4x1026可能的key，大于56位DES的密鑰空間。基于語言統計規律仍可破譯例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQPlayfair

密碼Hill密碼Hill密碼例子多字母密碼總結替換是密碼學中有效的加密方法。本世紀上半葉用于外交通信破譯威脅來自頻率分布重合指數考慮最可能的字母及可能出現的單詞重復結構分析及克思斯基方法持久性、組織性、創造性和運氣通過執行對明文字母的置換，取得一種類型完全不同的映射，即置換密碼。若該明文被視為一個比特序列，則置換涉及到用密文比特模式代替明文比特模式置換柵欄技術Key:3412567Plaintext:attackpostponeduntiltwoamxyzCiphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZ置換技術通過多個加密階段的組合，能使密碼分析變得極為困難對置換和替代都適合轉子機具有連線的三轉子機器（用編號的觸點表示）目錄密碼學的起源、發展和現狀密碼學基本概念常規加密的現代技術安全密碼的特性Shannon特性（1949）所需的保密程度決定了用于加密和解密過程的相應的工作量密鑰的組或加密算法應該不受其復雜性的影響處理的實現應盡可能簡單編碼中的錯誤不應傳播及影響后面的消息加密后正文的尺寸不應大于明文的尺寸Feistel加密過程輸入：

長為2w比特的明文分組

密鑰k輸出：長為2w比特的密文分組Feistel網絡的特點明文分組分為：L0，R0，數據的這兩部分通過n次循環處理后，再結合起來生成密文分組每i次循環都以上一循環產生的Li-1和Ri-1和K產生的子密鑰Ki作為輸入。一般說來，子密鑰Ki與K不同，相互之間也不同，它是用子密鑰生成算法從密鑰生成的Feistel網絡的特點所有循環的結構都相同，置換在數據的左半部分進行，其方法是先對數據的右半部分應用循環函數F，然后對函數輸出結果和數據的左半部分取異或(XOR)循環函數對每次循環都有相同的通用結構，但由循環子密鑰Ki來區分在置換之后，執行由數據兩部分互換構成的交換Feistel網絡的特點解密過程與加密過程基本相同。規則如下：用密文作為算法的輸入，但以相反順序使用子密鑰Ki意味著加密和解密不需要用兩種不同的方法。Feistel結構定義加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)解密:Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)FeistelCipherDecryptionFeistel網絡的設計特點分組大小：較大的分組意味著較強的安全性，但會降低加密解密速度。64位的分組大小是合理的折中，幾乎所有的分組設計中都使用它密鑰大小：較大的密鑰意味著較強的安全性，但會降低加密解密速度。現代算法中最常用的是128位密鑰循環次數：本質是單一循環的不足，多重循環能夠加強安全性。典型的循環次數為16子密鑰生成算法：較大的復雜性會增大密鑰分析的難度循環函數：較大的復雜性意味著給密碼分析帶來更大的難度Feistel網絡的實現快速軟件加/解密：常將加密嵌入到應用程序中，以預防硬件實現的方式，因此速度很重要分析的簡易性：算法表示簡潔清晰，則易于分析算法中加密技術的缺陷安全密碼的特性Shan