1網絡信息安全

第2章網絡信息安全理論基礎

2第2章網絡信息安全理論基礎

本章主要內容：2.1前言2.2密碼學的基本概念2.3密碼系統模型和密碼體制2.4密碼分析2.5古典密碼32.1前言基礎數論在密碼學中的作用

基礎數論作為一門古老的數學學科，在整個數學學科中占有非常重要的位置。數論中許多基本內容，如同余理論、中國剩余定理（CRT）、高次剩余理論等，在新型密碼體制、密鑰分配與管理、數字簽名、身份認證等方面有直接的應用。

現代密碼與近代數學形影不離近代數學在現代密碼研究中比比皆是：群論，有限域上橢圓曲線理論，多項式理論與跡函數理論，陷門單向函數等。42.2密碼學的基本概念

密碼學(Cryptology)：研究信息系統安全保密的科學。它包含兩個分支。密碼編碼學(Cryptography)，對信息進行編碼實現隱蔽信息的一門學問密碼分析學(Cryptanalytics)，研究分析破譯密碼的學問。5

2.2密碼學的基本概念

明文(消息)(Plaintext)：被隱蔽消息。

密文(Ciphertext)或密報(Cryptogram)：明文經密碼變換成的一種隱蔽形式。

加密(Encryption)：將明文變換為密文的過程。

解密(Decryption)：加密的逆過程，即由密文恢復出原明文的過程。

加密員或密碼員(Cryptographer)：對明文進行加密操作的人員。6

2.2密碼學的基本概念

加密算法(Encryptionalgorithm)：密碼員對明文進行加密時所采用的一組規則。接收者(Receiver)：傳送消息的預定對象。解密算法：接收者對密文進行解密時所采用的一組規則。密鑰(Key)：控制加密和解密算法操作的數據處理，分別稱作加密密鑰和解密密鑰。截收者(Eavesdropper)：在信息傳輸和處理系統中的非受權者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機密信息。72.2密碼學的基本概念

密碼分析(Cryptanalysis)：截收者試圖通過分析從截獲的密文推斷出原來的明文或密鑰。

密碼分析員(Cryptanalyst)：從事密碼分析的人。

被動攻擊(Passiveattack)：對一個保密系統采取截獲密文進行分析的攻擊。

主動攻擊(Activeattack)：非法入侵者(Tamper)、攻擊者(Attcker)或黑客(Hacker)主動向系統竄擾，采用刪除、增添、重放、偽造等竄改手段向系統注入假消息，達到利已害人的目的。82.3密碼系統模型和密碼體制Shannon的保密系統模型9

2.3密碼系統模型和密碼體制現代密碼系統模型102.3密碼系統模型和密碼體制密碼體制(Cryptosystem)——六元組(M,C,K1,K2,E,D)明文空間:M，mM稱為明文(plaintext)密文空間:C，cC稱為密文(ciphertext)加密密鑰空間:K1，

k1K1

稱為加密密鑰(encryptionkey)解密密鑰空間:K2k2K2

稱為解密密鑰(decryption

key)

密鑰(key):k=(k1,k2)11密碼體制(Cryptosystem)——六元組(M,C,K1,K2,E,D)加密變換簇:E解密變換簇:D

2.3密碼系統模型和密碼體制12密碼體制(Cryptosystem)加密變換與解密變換的關系mMCc

2.3密碼系統模型和密碼體制13

保密系統應當滿足的要求

系統即使達不到理論上是不可破的，即pr{m’=m}=0，也應當為實際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計算上是不可行的。系統的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。加密和解密算法適用于所有密鑰空間中的元素。系統便于實現和使用。14認證與認證系統認證系統(Authenticationsystem)

防止消息被竄改、刪除、重放和偽造的一種有效方法,使發送的消息具有被驗證的能力，使接收者或第三者能夠識別和確認消息的真偽。實現這類功能的密碼系統稱作認證系統保密性

保密性是使截獲者在不知密鑰條件下不能解讀密文的內容。認證性使任何不知密鑰的人不能構造一個密報，使意定的接收者解密成一個可理解的消息(合法的消息)。15安全認證系統應滿足下述條件意定的接收者能夠檢驗和證實消息的合法性和真實性。消息的發送者對所發送的消息不能抵賴。除了合法消息發送者外，其它人不能偽造合法的消息。而且在已知合法密文c和相應消息m下，要確定加密密鑰或系統地偽造合法密文在計算上是不可行的。必要時可由第三者作出仲裁。16密碼體制系統的分類對稱密碼體制(symmetriccryptosystem)

k=k1=k2或k1

k2

單鑰、私鑰(one-key,privatekey)密碼體制

2.3密碼系統模型和密碼體制17單鑰體制(One-keysystem)：

加密密鑰和解密密鑰相同，即能簡單的由加（解）密密鑰求得解（加）密密鑰。注意：一個保密系統的加密密鑰和解密密鑰相同，或者雖然不同，但由其中的任意一個很容易的求得另外一個，即使用的是對稱密鑰密碼體制，那么某個實體有能力加密，也就有能力解密。18密碼體制系統的分類對稱密碼體制(symmetriccryptosystem)分組密碼(blockcipher)

將明文消息分為包含若干個符號的組，在選定密鑰后使用固定的加密變換對明文分組逐組地進行加密。例如，DES(1977),AES(2001)流密碼(streamcipher)

明文：m=m1m2m3…..

密鑰：k=k1k2k3….

加密：c1=Ek1(m1),c2=Ek2(m2),c3=Ek3(m3),….

密文：c=c1c2c3….

例如，GSM移動臺（手機）到基站BS之間無線傳輸中使用的加密算法A5/1是一種流密碼

2.3密碼系統模型和密碼體制19非對稱密碼體制(asymmetriccryptosystem)

雙鑰、公鑰(two-key,publickey)密碼體制

k1k2或k1不能k2

公鑰:k1=pk；私鑰:k2=sk

2.3密碼系統模型和密碼體制20雙鑰體制(Twokeysystem)：加密密鑰和解密密鑰不同。一個保密系統把加密和解密分開，加密和解密分別用兩個不同的密鑰實現，并且由加密密鑰推導出解密密鑰是計算是不可行的，則該系統使用的是非對稱密鑰密碼體制（公鑰密碼體制）如：RSA、EIGaMal、橢圓曲線密碼體制等是非對稱密碼體制的典型代表。使用公鑰密碼體制的每個用戶都有一對選定的密鑰，其中一個是可以公開的，稱為公鑰，另外一個是用戶自己秘密保存。

思考：用于加密的還是解密的秘鑰保存？212.3密碼系統模型和密碼體制密碼系統的設計原則設計加密函數與解密函數的學科稱為密碼編碼學(Cryptography)、密碼學或保密學。具有某種安全性理論上不可破實際上不可破Kerckhoff假設：系統的保密性不依賴于對加密體制或加（解）密算法的保密，而僅依賴于密鑰的保密。加密和解密算法適用于密鑰空間的全部元素系統便于實現和使用方便22

2.3密碼系統模型和密碼體制密碼學發展簡史密碼學發展史簡圖遠古1949年1976年1977年1949年現代密碼古典密碼1976年私鑰密碼公鑰密碼1977年商用密碼23密碼學發展簡史古典密碼時期(—1949)特定應用領域：軍事、政治、外交神秘性藝術性現代密碼學(1949—)：密碼技術成為一門學科

著名論文:

Communicationtheoryofsecrecysystems,BellSyst.Tech.J.,Volume28,656-715,1949.

仙農(C.D.Shannon:1916-2001)

2.3密碼系統模型和密碼體制24密碼學發展簡史公鑰密碼學(1976—)計算機網絡環境中的應用W.Diffie和M.E.Hellman提出公鑰密碼的思想(1976)著名論文：W.DiffieandM.E.Hellman,Newdirectionincryptography,IEEETran.OnInformationTheory,IT-22,(6),644-654,1976.密碼學的商業應用(1977—)1977：美國國家標準局(NationalBureauofStandards)頒布數據加密標準DES(DataEncryptionStandard)1994：美國政府頒布數字簽名標準DSS(DataSignatureStandard)2001：美國政府頒布高級加密標準AES(AdvancedEncryptionStandard)

2.3密碼系統模型和密碼體制252.4密碼分析

截收者在不知道解密密鑰及通信者所采用的加密體制的細節條件下，對密文進行分析，試圖獲取機密信息。研究分析解密規律的科學稱作密碼分析學。密碼分析在外交、軍事、公安、商業等方面都具有重要作用，也是研究歷史、考古、古語言學和古樂理論的重要手段之一。262.4密碼分析

密碼設計和密碼分析是共生的、又是互逆的，兩者密切有關但追求的目標相反。兩者解決問題的途徑有很大差別

密碼設計是利用數學來構造密碼密碼分析除了依靠數學、工程背景、語言學等知識外，還要靠經驗、統計、測試、眼力、直覺判斷能力……，有時還靠點運氣。27利用密文推斷出明文或解密密鑰的學科稱為密碼分析學(Cryptanalysis)

分析(analysis)=破譯(break)=攻擊(attacks)攻擊方式主動攻擊(activeattack)

竄改通信中的數據流，或在通信中產生虛假數據流被動攻擊(passiveattack)

竊聽或監視通信過程，從中獲得信息2.4密碼分析28攻擊方法

2.4密碼分析29窮舉破譯法(exhaustiveattackmethod)方法：對截獲的密文依次用各種可能的密鑰試譯，直到獲得有意義的明文；或者利用對手已注入密鑰的加密機（比如繳獲得到），對所有可能的明文依次加密直到得出與截獲的密文一致的密文。對策：將密鑰空間和明文空間設計得足夠大。確定性分析法方法：利用密文或者明文—密文對等已知量以數學關系式表示出所求未知量（如密鑰等），然后計算出未知量。對策：設計具有堅實數學基礎和足夠復雜的加密函數統計分析法方法：密碼破譯者對截獲的密文進行統計分析，找出其統計規律或特征，并與明文空間的統計特征進行對照比較，從中提取出密文與明文間的對應關系，最終確定密鑰或明文。對策：擾亂密文的語言統計規律

攻擊方法30物理破譯方法(Kocher,1996)

利用加密執行時的物理現象來確定密鑰的密碼分析方法，也被稱為“邊信道攻擊”（side-channelattack）。所利用的物理現象有密碼算法執行器件（加密芯片）的功耗，各算法步執行時間度量，甚至主機執行加密任務時主板上電容器發出的聲音等等。

攻擊方法31攻擊類型唯密文攻擊(ciphertext-onlyattack)

密碼分析者僅知道有限數量用同一個密鑰加密的密文已知明文攻擊(knownplaintextattack)

密碼分析者除了擁有有限數量的密文外，還有數量限定的一些已知“明文—密文”對選擇明文攻擊(chosenplaintextattack)

密碼分析者除了擁有有限數量的密文外，還有機會使用注入了未知密鑰的加密機，通過自由選擇明文來獲取所希望的“明文—密文”對

選擇密文攻擊(chosenciphertextattack)

密碼分析者除了擁有有限數量的密文外，還有機會使用注入了未知密鑰的解密機，通過自由選擇密文來獲取所希望的“密文—明文”對32無條件安全和計算安全

無條件安全

如果算法產生的密文不能給出唯一決定相應明文的足夠信息，無論截獲多少密文，花費所少時間都不能解密密文。

Shannon指出，僅當密鑰至少和明文一樣長時達到無條件安全（即一次一密）

計算安全

破譯密文的代價超過被加密信息的價值破譯密文所花時間超過信息的有效期331）代替密碼（替換密碼）

可分為單表密碼、多表密碼單表密碼：將明文中的字母或符號用另一種字母或符號來代替，這種代替是一一對應的。明文與密文之間只有一種對應關系。多表密碼：代替不是一一對應的。代替規律不同，密碼體制也不同。代替規律相同，明密文間字母對應關系不同，代替出的密碼也不同。e.g.同余密碼（加同余、乘同余、線性同余）隨機替代、密鑰詞組、多表組合2.4古典密碼34*

一般單碼替換密碼?簡單的方法給出密鑰?寫出密鑰（刪除重復字母）?在其下面依次寫出剩余字母（以橫、縱行）?按列讀取字母得到密文。2.4古典密碼35

一般單碼替換密碼舉例?給定密鑰字"STARWARS"?去掉重復字母得到"STARW"?填寫剩余字母：STARWBCDEFGHIJKLMNOPQUVXYZ?按列讀取字母得到密文?Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZ?

Cipher:SBGLQZTCHMUADINVREJOXWFKPY?可以用這個密鑰加密、解密?例如Plaintext:IKNOWONLYTHATIKNOWNOTHING?Ciphertext:HUINFNIAPOCSOHUINFINOCHIT36

一般單碼替換密碼的密碼分析?根據頻率統計進行分析?確定每個字母被映射到什么字母?如果知道單詞之間的間隙知道,則破譯會很容易.?單個字母出現的可能是A或I?一般來說3個字母出現的可能是THE或AND?還可以用其他通常出現的雙字母或三字母組合)?還可以應用其它很少應用的字母37同余密碼

(1)加同余碼：一種移位密碼，如凱撤(Cacsar)密碼：以查碼表方式進行一對一替換。收發雙方采用同一碼表。凱撤密碼加密變換：C=P+3(mod26)

凱撤密碼解密變換：P=C-3(mod26)密鑰：338

若明文m=Casearcipherisashiftsubstitution則密文C=E(m)=FDVHDUFLSHULVDVKLIWVXEVWLWXWLRQ明文abcdefghijklm密文DEFGHIJKLMNOP明文nopqrstuvwxyz密文QRSTUVWXYZABC39凱撤密碼擴展：C=P+n(mod26)P=C-n(mod26)

密鑰：n密碼分析（１）加解密算法已知（２）可能嘗試的密鑰只有２6個通過強力攻擊得到明文40

(2)乘同余碼：移位或等間隔抽取碼，明密文之間沒有一一對應關系。（容易產生多義性）。變換按照同余乘法進行：加密變換：C=Pk(mod26)

解密變換：P=Ck(mod26)

密鑰：k

41

(3)線性同余：加同余與乘同余密碼的結合。正常字母順序替換，解碼容易42隨機替換密碼隨機改變字母替換順序，改變單一字母組合，增加字符或者專用符號替換，從而增加了密鑰數量，使密碼破譯困難，但用戶自己記憶也困難。通常以碼表查閱實現。密鑰詞組密碼解決密鑰記憶困難問題，任選一詞組作為密鑰。加解密均也采用查表方式。上述密碼均是字母、符號的排列和組合，用計算機可以對上述密碼進行破譯。43多表密碼

利用多碼表組合形成的加解密機制，打亂明文統計規律，提高保密強度。多表代換密碼是以一系列(兩個以上)代換表依次對明文消息的字母進行代換的加密方法

e.g.維吉尼亞密碼、博福特密碼等441．維吉尼亞密碼一種以移位代換為基礎的周期代換密碼，為1858年法國密碼學家維吉尼亞提出。首先構造一個維吉尼亞方陣：它的基本陣列是26行26列的方陣.方陣的第一行是按正常順序排列的字母表,第二行是第一行左移循環1位得到的,依此類推,得到其余各行.然后在基本方陣的最上方附加一行,最左側附加一列,分別依序寫上a到z26個字母,表的第一行與與附加列上的的字母a相對應,表的第二行與附加列上的字母b相對應..最后一行與附加列上的字母z相對應.如果把上面的附加行看作是明文序列，則下面的26行就分別構成了左移0位，1位，2位…，25位的26個單表代換加同余密碼的密文序列。加密時，按照密鑰字的指示，決定采用哪一個單表。45ABCDEFGHIJ...YZAABCDEFGHIJ...YZBBCDEFGHIJK...ZACCDEFGHIJKL...ABDDEFGHIJKLM...BCEEFGHIJKLMNCDFFGHIJKLMNODEGGHIJKLMNOPEFHHIJKLMNOPQFGZZABCDEFGHI...XY46維吉尼亞密碼密鑰字encryptionencryptione明文：publickeydistribution密文：thdcgrdmmqmfvrgqnbwbr由于密鑰字比明文短，所以要重復書寫密鑰字，以得與明文等長的密鑰序列。47Vigenérecipher-破譯依然保留了字符頻率某些統計信息重碼分析法：間距是密鑰長度整數倍的相同子串有相同密文，反過來，密文中兩個相同的子串對應的密文相同的可能性很大。482）置換密碼

也稱換位密碼或轉置密碼。

加密方式與密文形式不同于代替密碼體制。

不改變組成明文消息的符號本身，只對符號進行重新排列。可以分類為：倒序密碼：顛倒明文書寫順序。柵欄密碼：明文交替書寫排列。行列轉置：明文行列轉置書寫。49變換密碼的關鍵思想◆按一定規則寫出明文，按另一規則讀出密文?！裘荑€：用于讀密文的方法和寫明文的方法50例、行變換密碼-（Rowtranspositionciphers）按行寫出字母以密鑰給出的順序按行讀出密文（總是有一個密鑰對）51行變換密碼(續1)1)Plain:THESIMPLESTPOSSIBLETRANSPOSITIONSXXKey(R): 25413Key(W): 41532 THESI STIEH MPLES EMSLP TPOSS STSOP IBLET EITLB RANSP SRPNA OSITI TOIIS ONSXX XOXSNCipher:STIEHEMSLPSTSOPEITLBSRPNATOIISXOXSN523）代碼密碼

可以對明文字母、符號、詞組和短語等進行替換，甚至對明文句子進行替換。不考慮明文的結構，代碼替換可以是等長的，也可以是不等長的。短碼替換使明文長度縮短，實現明文壓縮。長碼替換使明文長度增長，實現明文擴展。e.g.以各種編碼實現替換：二進制碼、八或16進制碼、五中出二碼、格雷碼等。53一次一密密碼一次一密密碼，由AT&T公司的GilbertVernam在1917年提出。發方和收方各保存一份一次一密亂碼本，它是一個大的不重復的真隨機密鑰字母集。發方用亂碼本中的某一頁密鑰加密明文。加密方法：明文字符和亂碼本密鑰字符的模26加法。每個密鑰僅對一個消息使用一次。發方對所發的消息加密，然后銷毀亂碼本中用過的一頁。收方有一個同樣的亂碼本，并依次使用亂碼本上的每個密鑰去解密密文的每個字符，然后銷毀亂碼本中用過的一頁。54語言的統計規律性C.E.Shannon1949年第一次透徹地闡明了密碼分析的真諦，指出密碼能夠被破譯的最根本原因是于明文空間非均勻的統計特性英文字母頻率表

初等密碼分析實例字母概率字母概率字母概率字母概率ABCDEFG0.081670.014920.027820.042530.127020.022280.02015HIJKLMN0.060940.069660.001530.0080.0400.0240.067OPQRSTU0.0750.0190.0010.0600.0630.0910.028VWXYZ0.0100.0230.0010.0200.00155單表代換密碼分析

給定密文：EJMHAFJPDPBKRNMQJANONPSMNBQOAFJPDNIWQRGGSOQANFHMWNNIJSWRQJYNQNMOQHQBOQBPHFHIHFXOBOQRNAFJPDFNIWQRJEYNOGHXANQRNORJMQNOQJIN

首先求出密文字母的頻度分布表密文字母ABCDEFGHIJKLMNOPQRSTUVWXYZ

頻數6503283751010617

10614730004220先猜測Ek:eN,，再利用英文高頻度的雙字母知識，比對密文中出現的雙字母（詞）及次高頻度字母集{t,a,o,i,n,s,h,r}，猜測Ek:tQ,oJ,

得到部分試譯結果：

EoMHbFoPDPBKReMtobeOePSMeBtObFoPDFeIWtRGGSOtbeFHMWeeIoSWRtoYeteMOtHtBOtBPHFHIHFXOBOtRebFoPDFeIWtRoEYeOGHXbetReORoMteOtoIe56利用三字母組合和元音輔音拼寫知識，猜測單詞tRe為the，即

Ek:hR.在余下的次高頻度字母集{a,i,n,s,r}中選擇適當的輔音字母作為密文O的原像,即Ek:sO.利用構詞分析