密碼學(xué)基礎(chǔ)課件：第四講 古典密碼學(xué)

1、第四講 古典密碼學(xué)-3置換密碼及其密碼分析密碼學(xué)中的輪子對稱密碼設(shè)計(jì)的基本原則擴(kuò)散混淆現(xiàn)代密碼學(xué)設(shè)計(jì)的基本原則古典密碼（Classical Cipher） 代換密碼(Substitution Cipher)是明文中的每一個(gè)字符被替換成密文中的另一個(gè)字符。接收者對密文做反向替換就可以恢復(fù)出明文。置換密碼(Permutation Cipher)又稱換位密碼（Transposition Cipher)，加密過程中明文的字母保持相同，但順序被打亂了。置換密碼 置換密碼(Permutation Cipher)。置換密碼又稱為換位密碼，通過改變明文消息各元素的相對位置，但明文消息元素本身的取值或內(nèi)容形式不

2、變。它是對明文L長字母組中的字母位置進(jìn)行重新排列，而每個(gè)字母本身并不改變。 明文：m=m1 m2,mL。， 加密變換：c=(c1,c2,cL)=E(m)=m(1) m(2) m(L)。 解密變換： 置換密碼換序構(gòu)詞的聲明意大利天文學(xué)家伽利略用他的望遠(yuǎn)鏡發(fā)現(xiàn)了土星這顆行星似乎由三顆星組成，用拉丁語表示為：altissimum planetam tergeminum observavi調(diào)換字母順序之后，伽利略“公開”了他的發(fā)現(xiàn)：SMAISMRMIL MEPOETAL EUMIBUNENU GTTAUIRAS換序構(gòu)詞的聲明惠更斯后來發(fā)現(xiàn)土星不是三顆星，他發(fā)現(xiàn)“它的周圍環(huán)繞著一個(gè)扁平的環(huán)，兩者沒有接觸

3、，環(huán)向黃道傾斜”這個(gè)發(fā)現(xiàn)使用了簡單的依照字母表順序重新排列的方式“公開了”。三年后才明確了這一發(fā)現(xiàn)。致桑道夫伯爵的信一個(gè)小混混偷走了編碼框。使用密鑰字的置換方法首先把明文寫成方框，例如寫成7*15的矩陣，明文不足則填充使用密鑰字的置換方法選擇大于列數(shù)的提示詞，例如 “在綠色的草地上”選擇與列數(shù)相同的句子，根據(jù)字母表順序?qū)渥又械淖帜妇幪?hào)，重復(fù)字母按照出現(xiàn)順序依次編號(hào) 使用密鑰字的置換方法按照編號(hào)大小調(diào)換列的順序原文置換后按列寫出得到密文使用密鑰字的置換方法再復(fù)雜一些，可以再為行選擇提示詞，類似調(diào)換行上述置換方法的分析攻擊者可以通過密文數(shù)量推測方框的行和列（因式分解）之后攻擊者可以根據(jù)自然語言中

4、雙字符的統(tǒng)計(jì)特性推斷列與列之間的先后關(guān)系，例如英語中“CH”和“TH”等組合，嘗試破譯。用英語說這件事情Because the cipher operates on blocks of size e, the plaintext and the ciphertext have to have a length which is some multiple of L. This causes two weaknesses in the system: first, the plaintext may have to be padded (if the padding is identifiabl

5、e then part of the key is revealed) and second, information relating to the length of the key is revealed by the length of the ciphertext. To see this, note that if the ciphertext is of length i then L must be one of the divisors of i. With the different possible key sizes different possible permuta

6、tions are tried to find the permutation which results in the highest number of frequent bigrams and trigrams as found in the underlying language of the plaintext. 置換方法的可識(shí)別性Because the cipher doesnt change any of the characters, the ciphertext will have exactly the same letter frequencies as the unde

7、rlying plaintext. This means that the cipher can in many cases be identified as a transposition by the close similarity of its letter statistics with the letter frequencies of the underlying language 給定一個(gè)集合1，2， . . .，n的置換，寫出置換矩陣為 這時(shí)，置換矩陣是每一行和每一列都剛好有一個(gè)“1”，而其余元素為“0”的稀疏矩陣。如加解密置換=(3 5 1 6 4 2)， =（3 6 1

8、5 2 4），對應(yīng)的置換矩陣（按照右乘）為：；表示僅第i行中第(i)個(gè)元素為1，其余為零。置換密碼的數(shù)學(xué)分析 加密變換： 解密變換： = 所以，置換密碼實(shí)質(zhì)上是輸入分組的一個(gè)線性變換。 置換密碼的數(shù)學(xué)分析置換密碼在實(shí)質(zhì)上是Hill密碼的特例密碼學(xué)中的輪子下面是把a(bǔ),b,c,d映射為C,A,D,B的輪子密碼學(xué)中的輪子上述輪子可以轉(zhuǎn)動(dòng)（輪子內(nèi)部連接方式與上圖相同）輪子的分析當(dāng)4字母換為26個(gè)字母之后，每加密一個(gè)字母輪子旋轉(zhuǎn)1/26周，因此相當(dāng)于我們學(xué)習(xí)過的維吉尼亞密碼或者改進(jìn)的維吉尼亞密碼一種多表代換的方法兩個(gè)輪子W1輪旋轉(zhuǎn)4次，W2輪旋轉(zhuǎn)1次。類似鐘表。此時(shí)可以表示16種4位字符的排列。赫貝恩5

9、個(gè)輪子的密碼機(jī)用同一臺(tái)機(jī)器加密解密可以看到按c輸出B。按b輸出C。最左側(cè)的輪子叫做互助輪舍爾比烏斯的啞謎希特勒的啞謎啞謎的弱點(diǎn)古典密碼小結(jié)對稱密碼體制主要分為分組密碼和流密碼對稱密碼的兩個(gè)基本運(yùn)算代換和置換(Substitution & permutation)對稱密碼的兩個(gè)基本設(shè)計(jì)原則:擴(kuò)散（Diffusion):明文的統(tǒng)計(jì)結(jié)構(gòu)被擴(kuò)散消失到密文的長程統(tǒng)計(jì)特性 ,使得明文和密文之間的統(tǒng)計(jì)關(guān)系盡量復(fù)雜。 混淆(confusion)：使得密文的統(tǒng)計(jì)特性與密鑰的取值之間的關(guān)系盡量復(fù)雜 擴(kuò)散擴(kuò)散是使得明文的統(tǒng)計(jì)特性分散在密文中混淆混淆是使得密文的統(tǒng)計(jì)特性與每一個(gè)密鑰比特相關(guān)經(jīng)典密碼算法特點(diǎn)要求的計(jì)算強(qiáng)

10、度小DES之前以字母表為主要加密對象代換和置換技術(shù)數(shù)據(jù)安全基于算法的保密密碼分析方法基于明文的可讀性以及字母和字母組合的頻率特性現(xiàn)代密碼學(xué)的基本原則Principle 1 ： the first step in solving any cryptographic problem is the formulation of a rigorous and precise denition of security. Principle 2： when the security of a cryptographic construction relies on an unproven assumption, this assumption must be precisely stated. Furthermore, the assumption should be as minimal as possible.Principle 3 ：cryptographic constructions should be accompanied with a rigorous proof o