【正文】 030.05 4 c u m w f g y p b 0.010.03 5 v k j x q z 0.01,31,六、單表密碼分析,第四章 傳統(tǒng)密碼學(xué),字母、三字母組合是分析單表密碼的有力手段 。收方有一個同樣的亂碼本，并依次使用亂碼本上的每個密鑰去解密密文的每個字符，然后銷毀亂碼本中用過的一頁。 每個密鑰僅對一個消息使用一次。發(fā)方用亂碼本中的某一頁密鑰加密明文。T公司的Gilbert Vernam在1917年提出。 多表密碼加密算法結(jié)果將使得對單表置換用的簡單頻率分析方法失效。 設(shè)密鑰k=k1k2…kn，明文M=m1m2…mn，加密變換Ek(M)=c1c2…cn。： 例如：明文為System，密鑰為dog，加密過程如下： 明文：S y s t e m 密鑰：d o g d o g 密文：V m g w r s 在這個例子中，每三個字母中的第一、第二、第三個字母分別移動（mod 26）3個，14個和6個位置。密文是長方形的另兩個頂點(diǎn)。密文是其右邊字母。 （6）I、J看成是相同字母。在m1和m2之間加一個無效字母。密文是長方形的另兩個頂點(diǎn)。密文是其下邊字母。密文是其右邊字母。 每一對明文字母 m1和m2，都根據(jù)下面的6條規(guī)則進(jìn)行加密。 2539。 2339。 239。,(,0 1 2 3 23 24 25 039。 仿射密碼：如果選取k1，k2兩個參數(shù)，其中 k1 與 26 互素，令c≡(k1m + k2)mod 26。,24,置換密碼： 1*. 置換π的表示： π＝ 2*密鑰空間K很大，|k|=26! ≈ 41026，破譯者窮舉搜索是不行的，然而，可由統(tǒng)計的方式破譯它。 凱撒加密變換實(shí)際上是c≡ (m + k) mod 26 其中m是明文對應(yīng)的數(shù)據(jù)，c是與明文對應(yīng)的密文數(shù)據(jù)，k是加密用的參數(shù)，叫密鑰。 例：維吉尼亞密碼。例：Playfair密碼。 （2）同音代替密碼：它與簡單代替密碼系統(tǒng)相似，唯一的不同是單個字符明文可以映射成密文的幾個字符之一同音代替的密文并不唯一。加密過程中是從明文字母表到密文字母表的一一映射。對密文進(jìn)行逆替換就可恢復(fù)出明文。 例如：線路加密法 明文以固定的寬度水平寫出，密文按垂直方向讀出。 如：消息認(rèn)證協(xié)議、數(shù)字簽名協(xié)議等 （1）密鑰建立協(xié)議：在兩個或多個實(shí)體之間建立會話密鑰 （2）認(rèn)證協(xié)議：防止假冒攻擊 將認(rèn)證和密鑰建立協(xié)議結(jié)合在一起，是網(wǎng)絡(luò)通信中最普遍應(yīng)用的安全協(xié)議。 密碼學(xué)待解決的各種問題圍繞著：機(jī)密性、完整性、認(rèn)證性、匿名性、公平性。 作為一個法則，攻擊的復(fù)雜性取這三個因數(shù)的最小化，有些攻擊包括這三種復(fù)雜性的折中：存儲需求越大，攻擊可能越快。 存儲需求。 處理復(fù)雜性。 可以用不同方式衡量攻擊方法的復(fù)雜性： 數(shù)據(jù)復(fù)雜性。,19,三、密碼分析,第四章 傳統(tǒng)密碼學(xué),密碼學(xué)更關(guān)心在計算上不可破譯的密碼系統(tǒng)。 如果不論密碼分析者有多少密文，都沒有足夠的信息恢復(fù)出明文，那么這個算法就是無條件保密的，只有一次一密亂碼本，才是無條件安全的。 （3）從密文探測出簡單卻有用的事實(shí)應(yīng)該是難的，如相同的信息被發(fā)送了兩次。 選擇密文攻擊 暫時接近密碼機(jī)，可選擇密文串，并構(gòu)造出相應(yīng)的明文。 選擇明文攻擊（chosen plaintext attacks）。 已知：截獲部分密文 已知明文攻擊（know plaintext attacks）。 常用的密碼分析攻擊有四類 ： 加密算法：公開 。 密碼分析學(xué)：研究分析破譯密碼的學(xué)問。 側(cè)重于通信鏈路上而非信源和信宿 端到端加密：為網(wǎng)絡(luò)提供從源到目的的傳輸加密保護(hù)。這些密碼體制有的只適合于密鑰交換，有的只適合于加密/解密。 公開密鑰算法主要用于加密/解密、數(shù)字簽名、密鑰交換。,二、加密和解密——對稱密鑰、公開密鑰算法,第四章 傳統(tǒng)密碼學(xué),13,公開密鑰算法中用作加密的密鑰不同于用作解密的密鑰，而且解密密鑰不能根據(jù)加密密鑰計算出來（至少在合理假定的長時間內(nèi)），所以加密密鑰能夠公開，每個人都能用加密密鑰加密信息，但只有解密密鑰的擁有者才能解密信息。,二、加密和解密——對稱算法,第四章 傳統(tǒng)密碼學(xué),12,分組密鑰：將明文分成固定長度的組（塊），如64比特一組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。 圖4.6 反饋移位寄存器,第四章 傳統(tǒng)密碼學(xué),二、加密和解密——對稱算法,11,最簡單的反饋移位寄存器是線形反饋移位寄存器，反饋函數(shù)是寄存器中某些位簡單異或。移位寄存器的長度用位表示，如果是n位長，稱為n位移位寄存器。 基于移位寄存器的序列密碼應(yīng)用十分廣泛。 加密： 解密：,二、加密和解密——對稱算法,第四章 傳統(tǒng)密碼學(xué),10,對于一個序列如果對所有的i總有Ki+p=Ki，則序列是以p為周期的，滿足條件的最小的p稱為序列的周期。 對多數(shù)對稱算法，加/解密密鑰是相同的 又稱之為秘密密鑰算法或單密鑰算法 對稱算法有兩類：序列密碼（流密碼）和分組密碼。 4*.若Alice和Bob在一次通信中使用相同的密鑰，那么這個加密體制為對稱的，否則稱為非對稱的。 2*.加密函數(shù)ek必須是單射函數(shù)，就是一對一的函數(shù)。 DK（EK（M））=M.,5,二、加密和解密,第四章 傳統(tǒng)密碼學(xué),DK2 （EK1（P））=P 雙鑰密碼體制,6,定義: (密碼體制）它是一個五元組（P,C,K,E,D)滿足條件： （1）P是可能明文的有限集；（明文空間） （2）C是可能密文的有限集；（密文空間） （3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間） *（4）任意k∈ K,有一個加密算法 和相應(yīng)的解密算法 ，使得 和 分別為加密解密函數(shù)，滿足dk(ek(x))=x, 這里 x ∈P。即 c=Ek(m) 這個過程稱之為加密，參數(shù)k稱為密鑰。,第四章 傳統(tǒng)密碼學(xué),3,二、加密和解密,第四章 傳統(tǒng)密碼學(xué),加密,解密,明文P,密文C,原始明文M,E（P）=C.,D（C）=P,D（E（P））=P,明文Plaintext 密文Cipher text 加密Encryption 解密Decryption 密鑰key,4,二、加密和解密,第四章 傳統(tǒng)密碼學(xué),密碼就是一組含有參數(shù)k的變換E。1,信息安全與管理,第四講 密碼學(xué),2,一、密碼學(xué)概述,密碼體制：1）傳統(tǒng)密碼體制 2）現(xiàn)代密碼體制 傳統(tǒng)密碼體制：對稱密碼體制（單鑰體制） 現(xiàn)代密碼體制：非對稱密碼體制（公鑰密碼體制、雙鑰體制） 按照對明文的處理方式分為：分組密碼算法和序列密碼算法。 分組密碼算法：把明文分成等長的組分別加密 序列密碼算法：是一個比特一個比特地處理，用已知的密鑰隨機(jī)序列與明文按位異或。設(shè)已知信息m，通過變換E得到密文c。解密算法D是加密算法E的逆運(yùn)算，解密算法也是含參數(shù)k的變換。,二、加密和解密,第四章 傳統(tǒng)密碼學(xué),7,二、加密和解密,第四章 傳統(tǒng)密碼學(xué),加密通信的模型,8,1*.Alice要將明文Ｘ在不安全信道上發(fā)給Bob，設(shè)X=x1 x2… xn , 其中xi ∈P, Alice用加密算法ek作yi=ek(xi) 1≤ i≤ n 結(jié)果的密文是 Y=y1y2….yn ,在信道上發(fā)送， Bob收到后解密：xi=dk(yi) 得到明文X=x1 x2… xn .。 3*.好的密鑰算法是唯密鑰而保密的。,二、加密和解密,第四章 傳統(tǒng)密碼學(xué),9,對稱算法：加密密鑰能夠從解密密鑰中推算出來，反之也成立。 序列密碼算法：已知的密鑰隨機(jī)序列與明文按位異或。密鑰流發(fā)生器產(chǎn)生的序列周期應(yīng)該足夠的長，如一個反饋移位寄存器由兩部分組成：移位寄存器和反饋函數(shù)。移位寄存器每次向右移動一位，新的最左邊的位根據(jù)反饋函數(shù)計算得到，移位寄存器輸出的位是最低位。 產(chǎn)生好的序列密碼的主要途徑之一是利用移位寄存器產(chǎn)生偽隨機(jī)序列，典型方法有： (1)反饋移位寄存器：采用非線性反饋函數(shù)產(chǎn)生大周期的非線性序列 （2）利用線性移位寄存器序列加非線性前饋函數(shù)，產(chǎn)生前饋序列 （3）鐘控序列，利用一個寄存器序列作為時鐘控制另一寄存器序列（或自己控制自己）來產(chǎn)生鐘控序列，這種序列具有大的線性復(fù)雜度。 著名的分組密碼包括出自IBM被美國政府正式采納的數(shù)據(jù)加密算法（Data Encryption Algorithm，DEA）、由中國學(xué)者Xuejia Lai和 James L. Massey 在蘇黎世的ETH開發(fā)的國際數(shù)據(jù)加密算法IDEA（International Data Encryption Algorithm）、比利時Joan Daemen 和 Vincent Rijmen 提交，被美國國家標(biāo)準(zhǔn)和技術(shù)研究所（US National Institute of Standards and Technology，NIST）選為美國高級加密標(biāo)準(zhǔn)（AES）的Rijndael。在公開密鑰算法系統(tǒng)中，加密密鑰叫做公開密鑰（簡稱公鑰），解密密鑰叫做秘密密鑰（私有密鑰，簡稱私鑰）。自從1976年公鑰密碼的思想提出以來，國際上已經(jīng)出現(xiàn)了許多種公鑰密碼體制，比較流行的有基于大整數(shù)因了分解問題的RSA體制和Rabin體制、基于有限域上的離散對數(shù)問題的DifferHellman公鑰體制和ElGamal體制、基于橢圓曲線上的離散對數(shù)問題的DifferHellman公鑰體制和ElGamal體制。,二、加密和解密 ——公開密鑰算法,第四章 傳統(tǒng)密碼學(xué),14,對傳輸中的數(shù)據(jù)可以在通信的不同層次來實(shí)現(xiàn)，即： 鏈路加密：對兩個節(jié)點(diǎn)之間的單獨(dú)通信線路上數(shù)據(jù)進(jìn)行加密保護(hù)。,三、密碼分析,15,三、密碼分析 密碼體制評價,第四章 傳統(tǒng)密碼學(xué),保密強(qiáng)度：與數(shù)據(jù)的重要性有關(guān) 密鑰的長度：安全、保管、記憶 算法的復(fù)雜度：開銷大小 差錯的傳播性：不應(yīng)