密碼學課件 古典密碼學

密碼學導論IntroductiontoCryptology主講教師：李衛(wèi)海第1章古典密碼學古典密碼學密碼學的發(fā)展與范疇代換技術置亂技術乘積密碼歷史上的教訓古典密碼學密碼學的發(fā)展與范疇代換技術置亂技術乘積密碼歷史上的教訓信息安全技術的發(fā)展01手工時代02機電/單機時代03網(wǎng)絡時代04量子/后量子時代信息簡單方法以技巧為主專人操作專門存放專人傳送機械帶動電路改變計算機模擬或計算算法保障安全專人操作專門存放專人\有線\無線電傳送密鑰傳遞成為關鍵開放、分布、互聯(lián)算法保障安全網(wǎng)絡傳送自動工具來保護存儲可靠措施來保護傳輸量子密鑰分配量子計算后量子密碼古典密碼學Medievalcryptology現(xiàn)代密碼學ModernCryptology3000年80年50年30年最早的有記載的“加密”文字公元前19世紀古埃及第十二王朝，MenetKhufu小鎮(zhèn)的一位祭祀為貴族KhnumhotepII撰寫的碑文目的：有人說是為了顯得更重要和更神秘，有人說是為了留住盜墓賊本質是一種編碼（code）編碼與加密是不同的，編碼是固定的確定的變換，一般是公開的，不改變的最早用于保護信息的密碼技術《六韜》記載，公元前11世紀，周武王時期姜太公發(fā)明“陰符”：是一種代換加密“陰書”：“一合而再離，三發(fā)而一知”是一種置亂密碼文字必須簡明扼要，收信人需要有一定的文學素養(yǎng)大勝克敵符長1尺警眾堅守符長6寸破陣離將符長9寸請糧益兵符長5寸降城得邑符長8寸敗軍亡將符長4寸卻敵極遠符長7寸失利亡士符長3寸陋有則山室龍名不唯則水在吾靈不高德斯在有馨是深仙更靈活的加密技術公元前4世紀，斯巴達-波斯的戰(zhàn)爭中，“天書”Scytale是一種置亂加密公元前1世紀，凱撒密碼C=m+3是第一種計算意義上的代換密碼手動時代的技巧與運氣手工時代主要以單表代換、多表代換、置亂為主防守方：手工加密、解密，有少量輔助設備出現(xiàn)代換以技巧為主，輔助以少量計算加密算法比較簡單，一般不公開攻擊方手工分析，主要靠猜字頻統(tǒng)計分析是主要且有效的工具密碼分析員以聰明的語言學家為主豬欄密碼宋代《武經總要》字檢機電時代的技術與暴力1919年轉輪密碼機出現(xiàn)美國人EdwardHughHebern首先獲得專利最具代表性的是德國的ENIGMA最早最廣泛使用犯了最多的錯誤最早被攻破的機械轉輪機機器破譯的代表Bombe密碼分析降低復雜度機器完成剩余的暴力分析密碼技術的變化算法復雜度大大增加，安全性大大提高算法開始公開，僅需保護密鑰數(shù)學家開始在密碼分析技術中占據(jù)重要地位計算機的出現(xiàn)將這一變化推至極致1949年，Shannon“TheCommunicationTheoryofSecrecySystem”，從理論上為密碼學奠定了科學基礎密碼學從技巧走向理論，開始融入大量現(xiàn)代數(shù)學理論網(wǎng)絡時代的密碼學、數(shù)學、物理網(wǎng)絡的出現(xiàn)使得信道完全開放商業(yè)需要有統(tǒng)一的密碼標準1976年，美國國家標準局公布實施DES數(shù)據(jù)加密標準2000年，美國國家標準局發(fā)布了AES代替DES密碼分配的困難催生了公開密鑰技術1975年，W.Diffie和M.Hellman首次提出公開密鑰思想1976年，W.Diffie、M.Hellman、R.Merkle提出密鑰交換方案1977年，R.Rivest、A.Shamir和L.Adleman提出RSA算法當代，混沌密碼、輕量級密碼、量子密碼、后量子密碼、同態(tài)密碼等新興技術發(fā)展密碼學與數(shù)學、物理緊密結合在一起信息安全與網(wǎng)絡空間安全Cyber：1948年美國數(shù)學家借用該詞用來指計算機，也指計算機網(wǎng)絡Cyberspace：指在計算機以及計算機網(wǎng)絡里的虛擬抽象世界?？苹眯≌f作家威廉·吉布森在1982年在短篇小說《全息玫瑰碎片（BurningChrome）》中首次創(chuàng)造，在小說《神經漫游者》中被普及CyberspaceSecurity：網(wǎng)絡空間安全Cyberspacesafety：網(wǎng)絡空間“安全”信息安全：關注信息的安全網(wǎng)絡空間安全：關注網(wǎng)絡及其服務的安全信息安全的范疇保密性（Confidentiality/Secrecy/Privacy）保密性：秘密信息不向非授權者泄露，也不被非授權者使用隱私性：個人能夠控制私人信息完整性（Integrity）數(shù)據(jù)完整性：信息只能以特定和授權的方式進行存儲、傳遞、改變系統(tǒng)完整性：系統(tǒng)以正常方式執(zhí)行預定功能，免于非授權操縱可用性（Availability）可用性：授權者能使用信息和信息系統(tǒng)訪問控制：通過授權限制用戶能訪問的資源可控性：對信息和信息系統(tǒng)實施安全監(jiān)控管理真實性（Authenticity）消息認證：消息未經篡改/確認來源實體認證：確認實體所聲稱的身份可追溯性/可審計性（Accountability/Auditability）收據(jù)與確認：告知已經收到信息或服務不可否認性：實體不能否認自己的行為信息系統(tǒng)通過在硬件、軟件、通信三個主要部分上確定和應用信息安全行業(yè)標準，實現(xiàn)在物理、個人、和組織三個層面上提供保護和預防機制。從本質上講，程序或政策的實施是用來告訴管理員，用戶和運營商如何使用產品以確保組織內的信息安全。維基百科上的信息安全屬性信息安全的范疇以我們學校為例，考慮一個信息系統(tǒng)請給出一個發(fā)布類型的例子，要求存儲數(shù)據(jù)的保密性是最重要的請給出一個發(fā)布類型的例子，要求存儲數(shù)據(jù)的完整性是最重要的請給出一個例子，此時對系統(tǒng)可用性的要求是最重要的網(wǎng)絡空間安全的挑戰(zhàn)對安全提要求容易，但實施很困難我們來做一個游戲：家園攻防AliceBobEve搭線竊聽偽裝身份重放篡改/刪節(jié)攔截DoS否認接受Mallory否認發(fā)送網(wǎng)絡安全的復雜性安全技術必須考慮各種各樣潛在威脅攻擊者當然不會按規(guī)矩出牌攻擊者只需要找到一個薄弱環(huán)節(jié)，而防護需要面面俱到信息安全要考慮到數(shù)據(jù)的復雜性網(wǎng)絡安全要考慮到設備、通信、網(wǎng)絡安全技術的應用位置：物理或邏輯上物理上，安全設備放置在什么位置邏輯上，安全機制放置在系統(tǒng)的什么位置秘密信息的產生、分配和保護等問題經常更新和持續(xù)監(jiān)管安全措施必然占用一定的資源用戶和安全管理員的排斥往往只有在發(fā)生安全事件后，才意識到安全投資的收益安全措施對系統(tǒng)效率必然帶來一定影響OSI（OpenSystemInterconnection）安全框架有效評價一個機構的安全需求；對各種安全產品和政策進行評估和選擇威脅、攻擊支撐用來檢測、阻止攻擊，或者從被攻擊狀態(tài)恢復到正常狀態(tài)的過程，或實現(xiàn)該過程的設備加強數(shù)據(jù)處理/傳輸/存儲系統(tǒng)的安全性的具體處理過程和措施安全性攻擊安全服務安全機制任何危及信息系統(tǒng)安全的行為安全機制多以密碼技術為基礎安全服務多以密碼協(xié)議或策略為基礎OSI安全框架安全服務增強某機構數(shù)據(jù)處理系統(tǒng)和信息傳輸?shù)陌踩杂涗洶踩羰录褂靡环N或多種安全機制提供服務復制與物理文檔相關聯(lián)的功能簽名，記錄日期防止泄露、篡改、破壞被證實或成為證據(jù)被記錄或許可X.800開放通信系統(tǒng)中協(xié)議層提供的服務，適當?shù)乇Ｗo系統(tǒng)和數(shù)據(jù)傳輸?shù)陌踩?。RFC2828系統(tǒng)提供的處理或通信服務，為系統(tǒng)資源提供特別的保護。OSI安全框架安全服務認證確保通信實體身份，并保護連接不受第三方干擾訪問控制防止資源的非授權使用數(shù)據(jù)保密性防止數(shù)據(jù)的非授權泄露數(shù)據(jù)完整性確保收到的數(shù)據(jù)與通信實體發(fā)送的數(shù)據(jù)相同不可否認性通信不可否認有效性服務確保系統(tǒng)或系統(tǒng)資源可以被授權實體按照規(guī)范訪問、使用OSI安全框架安全機制被設計用來檢測、防范安全攻擊，或從安全攻擊中恢復的特征單一的機制不能滿足所有需要的服務特定安全機制在特定的協(xié)議層實現(xiàn)加密、數(shù)字簽名、訪問控制、數(shù)據(jù)完整性、交換認證、流量填充、路由控制、公證通用安全機制不局限于任何安全服務或協(xié)議層可信功能、安全標簽、事件檢測、安全審計索引、安全恢復網(wǎng)絡通信安全模型消息消息秘密信息秘密信息安全相關變換安全相關變換可信第三方Trent（分配秘密信息、仲裁…）AliceBob攻擊者信道安全相關變換、秘密信息的產生與分配等是密碼學的核心網(wǎng)絡訪問安全模型需要合適的看門函數(shù)識別用戶需要可靠的安全控制，確保僅授權用戶可以使用指定信息或資源可信計算機系統(tǒng)有助于實現(xiàn)此模型信息系統(tǒng)用戶訪問通道計算資源（處理器、內存、輸入輸出等）數(shù)據(jù)進程軟件內部安全控制看門函數(shù)信任模型信任，是指對實體以不損害由其組成的系統(tǒng)的用戶安全的方式執(zhí)行的信心?？尚哦?，實體信任的一個特性，反映該實體被信任的程度能力善意完整性信任度關系中所冒的風險信賴披露感知的風險信任傾向影響可信度的因素冒險的結果信任模型古典密碼學密碼學的發(fā)展與范疇代換技術置亂技術乘積密碼歷史上的教訓經典加密技術代換（Substitution）技術明文內容的表示形式改變，內容元素之間相對位置不變明文字母用密文中對應字母代替置換（Transposition

orPermutation）技術明文內容元素的相對位置改變，內容的表示形式不變乘積密碼（ProductCiphers）多個加密技術的疊加基本模型、符號、約定明文：P

(Plaintext)或M(Message)密文：C(Ciphertext)密鑰：K(Secret

key)加密算法：E(Encryptionalgorithm)C=E(K,M)解密算法：D(Decryptionalgorithm)M=D(K,C)為便于區(qū)分，約定用小寫字母表示明文內容，大寫字母表示密文內容加密時通常舍棄標點、空格（無意義，且易被攻擊）信源密鑰源加密器E解密器D明文M密鑰K密文C明文M密碼分析員公開信道秘密信道一、算術密碼——移位密碼（ShiftCipher）又稱凱撒(JuliusCaesar)密碼Caesar

Cipher最早的代換密碼算法：將每個字母用字母表中它之后的第k個字母替代C=E(K,P)=(P+K)mod26，

P=D(K,C)=(C-K)mod26一些文獻中認為Caesar固定使用k=3例：K=3密鑰：abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC明文：meetmeafterthetogaparty密文：PHHWPHDIWHUWKHWRJDSDUWB安全性分析26個可能的密鑰，只有25個可用密鑰0不可用，否則密文與明文等同密碼分析通常認為：加密算法不會輸出有意義明文如果有一個算法能夠將一段明文映射為另一段可解釋的明文，則該算法具有很強的偽裝性和安全性信息隱藏可以使用窮舉攻擊，依次嘗試便可最壞情況需要嘗試25次平均需要嘗試25/2=12.5次注意，工程上的估算與數(shù)學期望不同(1+2+…+25)/25=13安全性分析采用并行運算可以同時嘗試多個甚至全部的可能密鑰，但每一個嘗試結果都需要判斷是否有意義機器可以勝任一種思路：在解密過程中，加入強制性人工參與（機器不能做）的任務雖然會增加解密人員的工作量，但對于抵抗窮舉攻擊非常有效CAPTCHA：區(qū)分人與機器的全自動公開圖靈測試Easyforhuman,andhardforcomputer一、算術密碼——仿射密碼（AffineCipher）目標：擴大密鑰空間映射關系簡單算法：密鑰：a,b加密：C=E([a,b],P)=(aP+b)mod26解密：P=D([a,b],C)=(C-b)/amod26安全性分析密鑰空間a=1時，蛻化為凱撒密碼，b有25種選擇a≠1時，b無限制相當于b=0的仿射加密后，再疊加一次凱撒加密a的取值有限制：gcd(a,26)=1，否則不能保證一一映射（兮禍所伏，禍兮福所倚）a=3,5,7,9,11,15,17,19,21,23,25例：a=2,b=1時P=3->C=7;P=16->C=7不同的明文對應同一密文，密文7無法唯一解密密鑰空間大小為11*26+25=286+25=311算術密碼的共性通過線性方程（組）進行加密、解密方程組越多，密鑰空間越大，窮舉攻擊的難度越大一旦竊聽者獲得了一組明文-密文對（已知明文攻擊），則很容易破譯一、算術密碼——希爾密碼（HillCipher）

二、代換密碼——單表代換密碼（MonoalphabeticCipher）每個明文字母按照代換表（密鑰）替換為一個新的字母密鑰長度26個字母例：密鑰：a

bcdefghijklmnopqrstuvwxyzDKVQFIBJWPESCXHTMYAUOLRGZN明文：ifwewishtoreplaceletters密文：WIRFRWAJUHYFTSDVFSFUUFYA空格略去，不做處理密鑰空間大?。?6!≈4×1026部分密鑰存在部分不動點，不可用輔助工具阿爾伯蒂(Alberti)密碼盤意大利文藝復興時期。第一個用于加密的機械裝置，大圈為定子，小圈為轉子。雙密碼盤估計始于18或19世紀。外層圓盤上有類似詞匯表的明文，包括字母、和常用單詞密文由兩位十進制數(shù)組成。頻率統(tǒng)計分析單表替換不改變相應字母的出現(xiàn)頻率自然語言存在高冗余，字母出現(xiàn)頻率不同英語中，e的頻率最高其次是t,a,o,i,n,s,h,rz,q,x,j的頻率近似為0阿拉伯人于9世紀最先注意到頻率統(tǒng)計對單表代換密碼的作用頻率統(tǒng)計分析對凱撒密碼的頻率攻擊攻擊通過識別a-e-i或r-s-t三元組的峰，或jk和xyz的特征，可以獲得密鑰明文統(tǒng)計密文統(tǒng)計，對比易知k=3頻率統(tǒng)計分析高頻出現(xiàn)的雙、三字母組合雙字母組合th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,…三字母組合the,ing,and,her,ere,ent,tha,nth,…常見的多字母組合tion,tiousBible頻率統(tǒng)計分析對單表替換密碼的頻率統(tǒng)計攻擊統(tǒng)計密文字母出現(xiàn)頻率將統(tǒng)計結果與自然語言頻率表對比，確定部分密鑰結合多字母組合和連接特征，確定部分密鑰從語義上，猜測其它密鑰連接特征：前后字母存在一定關聯(lián)性英語中，q后幾乎百分之百連接著ux前幾乎總是i和e，只在極個別情況下是o和ae和e之間，r的出現(xiàn)頻率很高頻率統(tǒng)計分析例：密文頻率最高的P（15次）和Z（14次）可能對應e和t猜ZW是th（最常用二字組合），ZWP是the（最常用三字組合）UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZteetethteetVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXetttheeeethtEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQeeettetheet頻率統(tǒng)計分析{S、U、O、M、H}可能對應{a、h、i、n、o、r、s}{A、B、G、Y、I、J}可能對應{b、j、k、q、v、x、z}注意到“th*t”逐漸分析，最終得到UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZtaeeteathateeaatVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXettathaeeeaethtaEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQeeetatetheetUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZitwasdiscolsedyesterdaythatseveralinformalbutVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXdirectcontactshavebeenmadewithpoliticalEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQrepresentativesofthevietconginmoscow頻率統(tǒng)計分析對于短信息，沒有足夠的資源進行頻率統(tǒng)計。窮舉攻擊可行?例：密文：ABCDEFGHIJ一組可能解

密鑰：a-E,e-H,f-A,n-F,o-B,

r-D,s-I,t-J,w-G,x-C

明文：foxranwest另一組可能解

密鑰：a-I,d-E,e-H,f-A,h-D,

i-E,n-G,o-B,r-J,x-C

明文：foxhidnear二、代換密碼——Playfair密碼（二維單表代換）CharlesWheatstone于1854年發(fā)明，用他的朋友BaronPlayfair命名。曾在二戰(zhàn)期間廣泛被美英軍方使用密鑰矩陣：以MONARCHY為例5×5矩陣先填入密鑰字母（不重復）再在剩余位置填入其它字母MONARCHYBDEDGI/JKLPQSTUVWXZSirCharlesWheatstoneLyonPlayfair,FirstBaronPlayfair加解密算法加密過程：每次加密或解密兩個字母加密規(guī)則：如果兩字母是重復的，則在其中插入字母x。

例如balloon劃分為balxloon如果兩字母位于同一行，則各自用右側字母代換。

例如ar->RM如果兩字母位于同一列，則各自用下側字母代換。

例如mu->CM否則各自用同行異列字母代換。

例如hs->BP；ea->IM或JM解密過程：加密過程的逆需統(tǒng)計26×25＝650個字母對，單字母的統(tǒng)計規(guī)律有改善頻率統(tǒng)計表需650個表項，需要更多密文才能有效統(tǒng)計MONARCHYBDEFGI/JKLPQSTUVWXZ二、代換密碼——多表代換加密（PolyalphabeticCipher）采用多個單表，輪流代換明文字母，使得同一個字母被映射為多種密文字母，改變密文字母出現(xiàn)頻率單表1單表2···單表s代換逆代換單表1單表2···單表s明文p明文p密鑰k密鑰k單表k單表k密文C輔助工具杰斐遜的輪子密碼機M-941942年前被美國陸軍廣泛使用，主要針對低級軍事通信安全。共有25個直徑35mm的鋁盤，外緣上可有字母。條形密碼設備M-138-T4二戰(zhàn)中美國陸軍和海軍使用。25個可選取的紙條按預先編排的順序編號和使用。加密強度相當于M-94。Kryha密碼機1926年由AlexandervonKryha發(fā)明，密鑰長度442，周期固定，一個有數(shù)量不等的齒的輪子引導密文輪不規(guī)則地運動。二、代換密碼：維吉尼亞密碼（VigenèreCipher）是最簡單的多表替換密鑰，由多個凱撒替換表循環(huán)構成密鑰：K＝K0K1…Kd-1第i位密鑰Ki

表示采用K=Ki

的凱撒替換表密鑰重復使用加密算法：Ci=E(K,Pi)=(Pi

+Kimodd)mod26解密算法：Pi=D(K,Ci)=(Ci

-Kimodd)mod26例：

密鑰：deceptive密鑰：deceptive|deceptive|deceptive明文：wearedisc|overedsav|eyourself密文：ZICVTWQNG|RZGVTWAVZ|HCQYGLMGJGiovanBattistaBellaso,1553BlaisedeVigenère,19世紀輔助工具Saint-Cyr滑軌：帶有重復字母表的滑軌密碼盤密碼表頻率統(tǒng)計攻擊？對不同位置的同一明文字母，會用多個密鑰加密字母的出現(xiàn)頻率被模糊，但并未完全消失頻率統(tǒng)計攻擊？嘗試分組統(tǒng)計若獲得了替換表的個數(shù)（密鑰長度）d，則可以逐個分析位于i,i+d,i+2d,…的密文，獲得密鑰Ki例：密鑰：deceptive，d=9明文密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ重排列，在每一列上進行字頻攻擊問題：如何找出密鑰長度d？ZICVTWQNGRZGVTWAVZHCQYGLMGJKasiski方法假設：明文中存在重復字段當重復字段的間隔是d的整數(shù)倍時，將得到重復的密文不同的明文獲得相同密文的巧合很少發(fā)生操作過程在密文中尋找重復字段計算重復字段的間距密鑰長度d應是這些間距的公約數(shù)缺點：查找算法運算量大，耗時長偶爾發(fā)生的巧合影響機器判斷例：一段Vigenère密碼加密的密文：CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWQIMMQMNKGRFVGXWTRZXWIAXLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRICHRCLQOHPWQAIIWXNRMGWOIIFKEECHR共出現(xiàn)5次，位置1,166,236,276,286。間隔為165,70,40,10，最大公約數(shù)是5重合指數(shù)法(IndexofCoincidence)

ZICVTWQNGRZGVTWAVZHCQYGLMGJ重合指數(shù)法(IndexofCoincidence)

重合指數(shù)法(IndexofCoincidence)過程：若Y是通過Vigenère密碼獲得的密文，把Y分成d個長為n/d的子串，記為Y1，Y2，…，Yd。如果d確為密鑰長度，則每個Yi都是由同一個密鑰加密得到的，有Ic(Yi)≈0.065否則，d猜錯了，Yi是由不同密鑰加密得到，顯得更隨機些，有Ic(Yi)≈0.038Y1Y2Y3…Yd***…****…****…*例：一段Vigenère密碼加密的密文：CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWQIMMQMNKGRFVGXWTRZXWIAXLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRICHRCLQOHPWQAIIWXNRMGWOIIFKEEd=1時，0.045d=2時，0.046,0.041d=3時，0.043,0.050,0.047d=4時，0.042,0.039,0.046,0.040d=5時，0.063,0.068,0.069,0.061,0.072重合互指數(shù)(MutualIndexofCoincidence)

重合互指數(shù)(MutualIndexofCoincidence)

二、代換密碼——Vernam密碼

二、代換密碼——Autokey密碼維吉尼亞密碼的密鑰修改變體從安全角度出發(fā)，希望密鑰與明文等長Autokey加密算法中，加解密密鑰以密鑰為前綴，以明文為后繼加解密密鑰＝

”密鑰”+”明文”例如：密鑰deceptive加解密密鑰：deceptivewearediscoveredsav明文：wearediscoveredsaveyourself密文：ZICVTWQNGKZEIIGASXSTSLVVWLA安全性分析以密鑰長度d分段，明文記為P1P2P3…，密文C1=K

+P1C2=P1+P2C3=P2+P3C4=P3+P4…做差處理：D1=C1=P1+KD2=C2-D1=(P1+P2)-(P1+K)=P2-KD3=C3-D2=(P2+P3)-(P2-K)=P3+KD4=C4-D3=(P3+P4)-(P3+K)=P4-K…可修改重合指數(shù)法進行破譯二、代換密碼——一次一密體系（One-TimePad）名稱來源于特工攜帶的密碼本，每用一頁后撕去可以認為是密鑰只用一次的維吉尼亞密碼當隨機密鑰與明文等長時，絕對安全唯一可理論證明的無條件安全任一個密文，總存在某個密鑰使之與任意明文相對應隨機密鑰產生的密文中完全沒有統(tǒng)計關系實現(xiàn)困難：難以產生大量真隨機密鑰難以及時、安全地分發(fā)大量密鑰量子密鑰分配可解決此難題俄羅斯亂數(shù)本。數(shù)字的排列具有俄國特色。古典密碼學密碼學的發(fā)展與范疇代換技術置亂技術乘積密碼歷史上的教訓置亂技術置亂（Scramble,

Transposition,Permutation）通過重排字母順序隱藏信息不改變字母表示形式不改變字母的統(tǒng)計概率與代換算法的本質區(qū)別可藉此辨別密碼算法類型柵欄技術（RailFenceCipher）將明文按對角線方向寫成若干行按行輸出加密結果例如：明文：meetmeafterthetogaparty鋸齒形書寫為兩行：

mematrhtgpry

etefeteoaat密文：MEMATRHTGPRYETEFETEOAAT縱行換位（RowTranspositionCipher）將明文按密鑰的位數(shù)寫為若干列按照密鑰，順序輸出各列例如：attackpostponeduntiltwoam密鑰：4312567明文：attackp

ostpone

duntilt

woamxyz密文:TTNAAPTMTSUOAODWCOIXKNLYPETZ

旋轉漏格板通過旋轉一個同樣的格子，得到不同的窗口例：明文：attackpostponeduntilseventwenty-fouram密文：ACSODLVTUTKTNTEWYAAOUIETNOMTPPNSNEFRattackpostponduntilseventwentyfouramattackpostponduntilseventwentyfouramattackpostponduntilseventwentyfouramattackpostponduntilseventwentyfouramattackpostponduntilseventwentyfouram如何生成漏格板？更多的置亂設計一維變換－矩陣轉置二維變換－圖形轉置DNATSREDNUUOYNAC明文：canyouunderstand密文：codtaueanurnynsd輸入輸出UUOYNACSREDNNATD密文明文明文：canyouunderstand密文：dnsuaruteodynnac置亂的抽象：變位字給出若干字母，猜測原文例：Harry?Potter中TOM?MARVOLO?RIDDLE也是IAMLORDVOLDEMORT牛頓寫給萊布尼茲：a7c2d2e14f2i7l3m1n8o4q3r2s4t8v12x1，

意思是dataaequationequodcumquefluentesquantitatesinvolvente,fluxionesinvenireetviceversa(fromagivenequationwithanarbitrarynumberoffluentestofindthefluxionesandviceversa)問題：能否從明文字母統(tǒng)計特性恢復明文？若能系統(tǒng)地解決變位字，就能破譯所有的置換密碼任意一堆的字母，是否只能組成唯一有意義的消息？答案顯然不是目前沒有能夠說明變位字唯一解密的一個長度或原則多重置亂單次置換規(guī)則簡單，易泄露特征信息，易被重構多種或多重置換迭代后，規(guī)則更加復雜，重構的難度有所增加例：明文：01020304050607080910111213141516171819202122232425262728加密算法：縱行換位密鑰：4312567一次加密

431256701020304050607080910111213141516171819202122232425262728密文：03101724

04111825

02091623

01081522

05121926

06132027

07142128。遞增關系規(guī)律仍可見二次置換后：17090527241612071002222003251513042319141101262118080628。規(guī)律不明顯置換的理論：置亂的表示

置換的理論：K循環(huán)

3是不動點2是不動點置換的理論：循環(huán)的分解

不動點階為4100prisonersproblem監(jiān)獄中有100個囚犯，每人有一個號牌，編號為1-100?？词孛恐芘c他們玩一個游戲：在一間屋子里，有一個包含100個抽屜的柜子?？词貙?00個號牌隨機放在抽屜中（每個抽屜放一個）。第一個囚犯進入房間，隨機打開50個抽屜，檢查號牌，然后關上抽屜。如果其中有他的號牌，那么他立即進入一個房間休息等候，然后下一個囚犯進入房間重復操作，繼續(xù)下去。如果所有囚犯都找到了自己的號牌，則釋放所有囚犯。如果在此過程中，某個囚犯沒有發(fā)現(xiàn)自己的號牌，則游戲立刻結束，所有囚犯返回囚室?？词亟忉屨f：每個囚犯找到自己號牌的概率是1/2每個囚犯都是獨立操作，因此100人都找到自己號牌的概率是2-100，此概率小到可以忽略真的么？100prisonersproblem

...3...8...15...45......8...15...45...3...古典密碼學密碼學的發(fā)展與范疇代換技術置亂技術乘積密碼歷史上的教訓密碼算法迭代單純的代換或置亂都不能保證安全規(guī)則不夠復雜，易被猜到或算出迭代使用多種加密算法，可以提供更高的安全性連續(xù)兩次代換可以構造更復雜的代換，但等效為一次規(guī)則復雜的代換連續(xù)兩次置亂可以構造更復雜的置亂，但等效為一次規(guī)則復雜的置亂交替使用代換和置亂如何？這是構造現(xiàn)代密碼的基本技術之一轉輪機RotorMachines是機械時代最復雜的密碼機二戰(zhàn)時期被廣泛應用德國Enigma，盟軍Hagelin，日本Purple其核心是復雜的多表代換密碼系統(tǒng)由連續(xù)的多個轉輪來構造基本原理：多次簡單的多表代換構造復雜的多表代換包括一系列轉輪，每個轉輪表示一個多表代換每個轉輪的輸入輸出由內部連線連接每當一個字母加密后，轉輪旋轉，改變代換表單個機械轉輪aD轉輪機RotorMachines三個轉輪可以提供263=17576個代換表http://enigmaco.de/enigma/enigma.htmlEnigma工作原理aDEnigma（迷）傳奇密碼學的兩個里程碑Enigma：機器加密Bombe：機器解密凝聚了密碼應用中的經驗與教訓德國的工作：到一戰(zhàn)結束，古典密碼學是唯一選擇手工編碼/分析：效率低下，安全性不高，攻擊相對有效1918年，謝爾比烏斯提出轉輪密碼機專利申請，同年開始生產Enigma銷路很差：商人不信任它，軍方相信原有密碼1923年，帶反射板的Enigma-A問世成本折半，但銷路仍然不好Enigma的救星——丘吉爾一戰(zhàn)中丘吉爾歷任海軍大臣、軍需大臣。1922年內閣倒臺，丘吉爾開始寫回憶錄“TheWorldCrisis”，1923年出版。書中寫道“德國的密碼在一戰(zhàn)剛開始不久，就已經被協(xié)約國破譯了”1926年，德國海軍采購Enigma之后，Enigma商用型、軍用型迅速發(fā)展ArthurScherbius亞瑟·謝爾比烏斯Enigma（迷）傳奇波蘭的工作：1918年波蘭復國，總參謀部二部“情報部”密碼處成功破譯德、蘇密碼1926年，德軍方采購Enigma英、法發(fā)現(xiàn)德國電文漸漸無法破譯，但并不關心波蘭人急了：招募懂德語的優(yōu)秀數(shù)學家，定向培養(yǎng)密碼人才1928年的一個周末，德駐波使館的外交郵包事件。波蘭人得到了商業(yè)型Enigma1931年德國密碼局的漢斯·蒂洛·施密特向法國叛變，代號“灰燼先生”以1萬德國馬克，出賣Enigma操作手冊、核心原理文件、新機型的部分細節(jié)之后7年，提供了38個月的密碼本，大量Enigma細節(jié)雷耶夫斯基針對指標組的循環(huán)圈現(xiàn)象發(fā)起攻擊指標組：為了減少同一密鑰對不同電文的加密次數(shù)，每次發(fā)報前隨機選取3個字母，作為指標組。用密鑰將指標組連續(xù)加密兩遍，發(fā)送6個密文字母。用指標組加密報文，并發(fā)送Enigma繼續(xù)升級。波蘭開發(fā)出了“炸彈”，可以同時模擬6臺Enigma1938年，Enigma繼續(xù)升級。波蘭人沒經費了，也沒時間了1939年7月24日，波蘭向英、法贈送兩臺仿制Enigma、Bomba的設計圖紙等MarianRejewski馬里安·雷耶夫斯基Enigma（迷）傳奇英/美的工作：1918-1926年，幾乎沒有任何成果1934-1937年，改進商業(yè)型Enigma，英國裝備“打字機X”英國人對Enigma的威力認識相當深刻，但未投入足夠精力去破譯1938，布萊奇利莊園成為國家破譯中心諾克斯的Rodding方法，1940年成功破譯德密電針對一種沒有連接板的Enigma1940年，德軍規(guī)定指標組不再連續(xù)加密兩遍波蘭人的方法失靈了圖靈在密文中猜測明文，尋找明文-密文的關聯(lián)1940年3月，按圖靈思路設計的Bombe出廠最終，有200多臺Bombe在英國各地運轉，常規(guī)性

地破譯德國空軍和陸軍的密碼德國海軍的Enigma使用8選3的每日轉輪設定，但

英國沒有附加轉輪的電路，因而無法破譯AlanTuring阿蘭·圖靈Enigma（迷）傳奇英/美的工作：1941年5月9日，英國捕獲德國潛艇U-110，繳獲德國海軍的附加轉輪，

以及未來兩個月的密鑰,

Bombe可以破譯德國海軍情報了潛艇部隊司令官AdmiralDonitz開始懷疑盟軍有能力解讀德國情報，

決定在潛艇Enigma上增加第四個轉輪。12月，一個德國密碼員用四個

轉輪加密了一條消息?？紤]到第四個輪子尚未被最高統(tǒng)帥部正式官方

采用，他又將原文用標準的三個輪子加密了一遍。這個錯誤使得

Bletchley莊園在該輪子被正式采用前就破解了轉輪的電路。1941年12月，美國參戰(zhàn)。因美國艦隊未加密，或者仍是手工

時代密碼，整個春季成為德國潛艇的“幸福時光”1942年2月，潛艇Enigma開始使用四個轉輪。英國的Bombe能

力不足1943年9月，美國人自己的Bombe開始以每周四臺的速度交付

海軍。到戰(zhàn)爭結束時，121臺Bombe每天24小時破譯德國Enigma

密鑰九七式歐文印字機——Purple紫密Hagelin密碼機中心機構是一個齒數(shù)可變的印字輪映射由若干個密鑰輪的轉動位置所控制，每加密一個明文字母，所有密鑰輪同時轉動一格，但每個密鑰輪轉動一圈的格數(shù)不同。Hagelin密碼機C-36Hagelin密碼機M-2091936年造，轉輪分別有17,19,21,23,25個齒，密鑰周期的長度為3,900,225為美國陸軍制造。增加了一個26齒的密鑰輪，周期數(shù)達101,405,950古典密碼學密碼學的發(fā)展與范疇代換技術置亂技術乘積密碼歷史上的教訓一、不能妄想對手不知道Kerckhoff原則：在判斷一類方法的加密安全性時，必須考慮到對手知道該類方法（除當前明文和密鑰外，對手知道一切）復雜的變換規(guī)則難以記憶的，需要用文字方式記錄。而密碼設備和文字記錄都可能被對手竊取、繳獲，可能被間諜出賣ENIGMA軍民混用，被盟軍購買過、偷取過、繳獲過、被間諜出賣過密碼設備可能被用在多個單位，多個用途中，其受保護的程度是不同的，其中最脆弱的一環(huán)也必定是對手所關注的ENIGMA曾用于天氣預報，也曾被用于生日祝賀保護密碼本，總比保護密碼設備要容易二戰(zhàn)時德國海軍曾用一種易溶于水的紙來制作密碼本更換密碼本的成本比更換密碼系統(tǒng)要低硬件設備的制作成本高，運輸成本高密碼本僅僅是幾張紙，便于隱藏；數(shù)字密鑰數(shù)據(jù)量小，便于保密傳輸多個備選算法，僅相當于增加極少的密鑰比特一、不能妄想對手不知道中革軍委二局“破譯三杰”曾希圣、曹祥仁、鄒畢兆毛澤東說：“和蔣介石打仗，我們是玻璃杯押寶，看得準，贏得了。這個玻璃杯就是破譯敵人密碼工作。”從1932年10月至1938年1月，軍委二局共破譯國民黨中央軍和地方軍各種密碼達1050多個，平均每月17個，及時準確地偵悉了敵人兵力部署等大量密息情報，為黨中央、中革軍委正確指揮紅軍實施兩占遵義、四渡赤水、突破烏江、巧渡金沙江等作戰(zhàn)行動，勝利完成二萬五千里長征，實現(xiàn)會師陜北，提供了有力的情報保障。二、不要低估自己的魅力和對手的能力不應當?shù)凸缹κ值哪芰κ炙度氲钠谱g力量，是隨信息的重要性而增加的在密碼學歷史上，“不可能被攻破”的密碼屢屢被破譯在整個二戰(zhàn)中，甚至戰(zhàn)爭結束之后相當長一段時間里，德國人固執(zhí)地相信ENIGMA是牢不可破的。即使當?shù)弥艽a機被截獲、舊密碼本被出賣后，仍放心使用ENIGMA對Enigma的安全性過于自負過高估計安全性：危險時未能及時銷毀低估對手能力：多次密碼機丟失未能引起重視Enigma被過分重視Enigma被廣泛應用在各個領域：被敵人重視Enigma被逐步升級但不更換：敵人的研究也逐步升級英國布萊奇利莊園六號棚屋的負責人曾說：ENIGMA密碼機，就其本身而言，如果被正確使用，將會是堅不可摧的。二、不要低估自己的魅力和對手的能力DES的網(wǎng)絡破解1973年，美國國家標準局采納DES密碼時，估計普通人至少需要數(shù)十年的時間破譯1977年，Whitfield&Martin，設想專用破譯

機，20小時完成窮舉1997年，RSA公司發(fā)起首屆“DES挑戰(zhàn)賽”，

DESCHALLProject，網(wǎng)絡協(xié)作“人肉”蠻力

破解，第一次公眾破譯，96天1998年，EFF制造DESCracker(DeepCrack)，

1856個芯片，$250,000，56小時破譯1999年，EFFDESCracker&

合作，22.25小時破譯二、不要低估自己的魅力和對手的能力《人民日報》的報道《中國畫報》出現(xiàn)王進喜在鉆井旁的照片《人民中國》“最早鉆井是在北安附近開始的?！薄巴踹M喜一到馬家窯子，看到一片荒野說：好大的

油海，我們要把中國石油落后的帽子拋到太平洋去！”“為把沉重的設備運到油井的位置，采用了人拉肩扛的方式?！逼渌麍蟮劳踹M喜個人事跡“大慶已有820口油井出油”確定大慶油田真實存在位于齊齊哈爾到哈爾濱之間油井離某個車站不遠定位反應塔的加工原油能力在100萬噸上下大慶油田的開工不晚于1959年反應塔煉油能力跟不上原油產量——準備低價現(xiàn)貨出售煉油設備三、不要自我感覺良好只有密碼分析者，而不是其他任何人，可以評價一個密碼體制的安全性美國密碼歷史學家DavidKahn曾經說過：幾乎每個密碼體制的發(fā)明者都無一例外地相信他的杰作是不可破譯的。對密碼系統(tǒng)的攻擊是五花八門的，密碼分析的方法是多種多樣的，甚至直接猜測。如何能預測這種攻擊？例如：差分攻擊、加密圖像的攻擊非零系數(shù)計數(shù)攻擊三、不要自我感覺良好目前有一些公認的標準來評價是一密碼系統(tǒng)是否不好，但沒有任何辦法可以評價一個密碼系統(tǒng)是否好！例如：相關性、雪崩效應等一個很不嚴謹?shù)牧晳T：用密鑰的組合數(shù)來評估系統(tǒng)的安全性，即用窮舉攻擊的計算規(guī)模來表示系統(tǒng)的安全性這是安全性的上限，是針對密碼分析員采用最笨拙的攻擊方式所形成的“安全性”，會給人“安全”的假象但除此之外沒有關于安全性的量化表示方法目前，衡量一個密碼系統(tǒng)是否安全的一個通用的做法是：公開接受來自全世界的研究和攻擊選擇安全的密碼系統(tǒng)時，選擇公開的、公認的密碼系統(tǒng)四、不是復雜了就安全表面的復雜性可能是虛假的，因為它們可以為密碼編制者給出一種安全性的錯覺為增強系統(tǒng)安全性，密碼編制者往往會增加各種紛雜的辦法，或者增加一些使用規(guī)范和行政要求可能使得通常的密碼分析方法失效，但也往往會造成另一些意想不到的突破口編碼時復雜不代表分析時必然復雜，例如德國人規(guī)定一個月內密鑰不得重復，效果是英國人減少工作量Enigma每個轉輪的進位點固定在不同位置，效果是便于敵人推測是幾號轉輪禁止連續(xù)兩天將同一轉輪放在同一位置，效果是英國人減少工作量字母表上連續(xù)字母不許交換，連接板上下相鄰字母不許交換，效果是英國人減少工作量采用固定的格式，例如數(shù)字前后加字母y等，效果是幫助英國人識別數(shù)字四、不是復雜了就安全例，考慮這樣一個系統(tǒng)：在分組加密中，假設每組的加密運算是密鑰與明文的異或，后一塊用前一塊的加密結果作為密鑰，即C1=k

m1,C2=C1

m2,C3=C2

m3，…該系統(tǒng)中，密鑰僅用了一次，而后面每一塊都用了新的密鑰，似乎很安全。但密文是公開的，m2=C1C2,m3=C2C3,…kC1C2C3……m1m2m3m4……C1C2C3C4……四、不是復雜了就安全美國密碼博物館的展品：二戰(zhàn)太平洋戰(zhàn)場上日軍曾用過的隨機數(shù)發(fā)生器簡單的也許就是最好的編織籃隨機數(shù)的產生是密碼科學與藝術的關鍵?！半S機”這個詞指“沒有特定模式、目的、或目標。簡單來說，系統(tǒng)的變化越多，保護得就越好?，F(xiàn)在，美國及其他一些現(xiàn)代化實體采用前沿的強大的技術來實現(xiàn)所需達到的隨機性級別，然而在過去，特別是無法獲得技術資源的戰(zhàn)爭時期，密碼人員往往不得不采取“現(xiàn)場應急”的辦法。這里展出的是一個在二戰(zhàn)太平洋戰(zhàn)爭期間繳獲的日軍編織籃，里面裝著一些寫著四位數(shù)字的紙條，用手抽取，以產生附加的隨機數(shù)。四、不是復雜了就安全2016年BruceSchneier（美國安全專家）專訪：所有的密碼最終都能破解，唯一的問題是要投入多少精力。密碼學使得國家安全局在收集數(shù)據(jù)方面不得不提高針對性，只會以少數(shù)人為目標，其余人則能夠得到保護。優(yōu)秀的加密算法并不意味著百分之百確保安全，因為這些算法必須在真實世界的系統(tǒng)中加以實現(xiàn)，實現(xiàn)的方法往往有缺陷。能夠破解密碼的攻擊者很少從數(shù)學方面下手，它們一般都會從系統(tǒng)、網(wǎng)絡以及落實安全的人這些方面發(fā)起攻擊。削弱安全標準的手段之一便是提高復雜程度?；ヂ?lián)網(wǎng)工程任務組（IETF）的互聯(lián)網(wǎng)標準工作對安全并沒有太大意義，因為這些標準都是一個委員會所做的妥協(xié)。他們將所有選擇都囊括進來，好讓大家皆大歡喜。他們加入了盡可能多的靈活性，使系統(tǒng)盡可能包羅萬象。這種方法就是安全的大敵。安全需要盡可能少的選擇，盡可能簡單,不能妥協(xié)。必須讓某一個選擇勝出，因為這個選擇具有獨立完整的邏輯。如果你這里搞一點，那里搞一點，就會出現(xiàn)一些被忽略的相互作用。這種相互作用就會成為系統(tǒng)的薄弱環(huán)節(jié)。五、人是最不安全的元素判斷一類加密方法的安全性時，必須考慮密碼錯誤和其它違反安全紀律的情況技術人員同樣要關心行政管理！歷史上，密碼系統(tǒng)往往就是毀在不在乎管理的技術人員，特別是密碼操作員手上不及時更換密鑰一戰(zhàn)，德國ADFGX密碼，每天更換密鑰。法軍潘萬上校雖然找到了

破譯方法，但總是不能及時破譯；后來德國人改進為ADFGVX密碼，

不再每天更換密鑰。結果，法國人得到機會獲取足夠的密文來及時

破譯情報。在使用Enigma時，早期三個月一換，戰(zhàn)時才改為8小時一換使用常用詞或短語作為密鑰需要時常更新密鑰的操作員非常容易發(fā)生這個惰性錯誤Enigma發(fā)報員常用三重碼、連續(xù)字母、或密鑰做指標組懶得更改轉輪初始位置（1940年德軍規(guī)定，不規(guī)定轉輪位置，由報務員自己