第02章-3網(wǎng)絡(luò)信息安全理論基礎(chǔ)

1網(wǎng)絡(luò)信息安全

第2章網(wǎng)絡(luò)信息安全理論基礎(chǔ)

2第2章網(wǎng)絡(luò)信息安全理論基礎(chǔ)

本章主要內(nèi)容：2.1前言2.2密碼學(xué)的基本概念2.3密碼系統(tǒng)模型和密碼體制2.4密碼分析2.5古典密碼32.1前言基礎(chǔ)數(shù)論在密碼學(xué)中的作用

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

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

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

2.2密碼學(xué)的基本概念

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

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

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

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

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

2.2密碼學(xué)的基本概念

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

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

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

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

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

2.3密碼系統(tǒng)模型和密碼體制現(xiàn)代密碼系統(tǒng)模型102.3密碼系統(tǒng)模型和密碼體制密碼體制(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密碼系統(tǒng)模型和密碼體制12密碼體制(Cryptosystem)加密變換與解密變換的關(guān)系mMCc

2.3密碼系統(tǒng)模型和密碼體制13

保密系統(tǒng)應(yīng)當(dāng)滿足的要求

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

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

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

k=k1=k2或k1

k2

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

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

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

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

明文：m=m1m2m3…..

密鑰：k=k1k2k3….

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

密文：c=c1c2c3….

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

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

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

k1k2或k1不能k2

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

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

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

2.3密碼系統(tǒng)模型和密碼體制密碼學(xué)發(fā)展簡史密碼學(xué)發(fā)展史簡圖遠(yuǎn)古1949年1976年1977年1949年現(xiàn)代密碼古典密碼1976年私鑰密碼公鑰密碼1977年商用密碼23密碼學(xué)發(fā)展簡史古典密碼時期(—1949)特定應(yīng)用領(lǐng)域：軍事、政治、外交神秘性藝術(shù)性現(xiàn)代密碼學(xué)(1949—)：密碼技術(shù)成為一門學(xué)科

著名論文:

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

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

2.3密碼系統(tǒng)模型和密碼體制24密碼學(xué)發(fā)展簡史公鑰密碼學(xué)(1976—)計算機(jī)網(wǎng)絡(luò)環(huán)境中的應(yīng)用W.Diffie和M.E.Hellman提出公鑰密碼的思想(1976)著名論文：W.DiffieandM.E.Hellman,Newdirectionincryptography,IEEETran.OnInformationTheory,IT-22,(6),644-654,1976.密碼學(xué)的商業(yè)應(yīng)用(1977—)1977：美國國家標(biāo)準(zhǔn)局(NationalBureauofStandards)頒布數(shù)據(jù)加密標(biāo)準(zhǔn)DES(DataEncryptionStandard)1994：美國政府頒布數(shù)字簽名標(biāo)準(zhǔn)DSS(DataSignatureStandard)2001：美國政府頒布高級加密標(biāo)準(zhǔn)AES(AdvancedEncryptionStandard)

2.3密碼系統(tǒng)模型和密碼體制252.4密碼分析

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

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

密碼設(shè)計是利用數(shù)學(xué)來構(gòu)造密碼密碼分析除了依靠數(shù)學(xué)、工程背景、語言學(xué)等知識外，還要靠經(jīng)驗、統(tǒng)計、測試、眼力、直覺判斷能力……，有時還靠點(diǎn)運(yùn)氣。27利用密文推斷出明文或解密密鑰的學(xué)科稱為密碼分析學(xué)(Cryptanalysis)

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

竄改通信中的數(shù)據(jù)流，或在通信中產(chǎn)生虛假數(shù)據(jù)流被動攻擊(passiveattack)

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

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

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

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

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

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

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

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

選擇密文攻擊(chosenciphertextattack)

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

無條件安全

如果算法產(chǎn)生的密文不能給出唯一決定相應(yīng)明文的足夠信息，無論截獲多少密文，花費(fèi)所少時間都不能解密密文。

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

計算安全

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

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

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

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

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

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

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

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

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

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

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

解密變換：P=Ck(mod26)

密鑰：k

41

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

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

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

也稱換位密碼或轉(zhuǎn)置密碼。

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

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

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

初等密碼分析實例字母概率字母概率字母概率字母概率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

頻數(shù)6503283751010617

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

得到部分試譯結(jié)果：

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

Ek:hR.在余下的次高頻度字母集{a,i,n,s,r}中選擇適當(dāng)?shù)妮o音字母作為密文O的原像,即Ek:sO.利用構(gòu)詞分析