密碼學(xué)-經(jīng)典換位加密法.ppt

1、1,經(jīng)典換位加密法,2,內(nèi)容綱要,3,Cipher Structure,4,Transpositions（換位）,換位加密法不是用其他字母來代替已有字母，而是重新排列文本中的字母，類似于拼圖游戲，所有的圖塊都在一個框中，只是排列的位置不同。 兩種不同的換位加密法：單圖（monographic）換位（例如skytale）和多圖（polygraphic）換位。 換位加密法一般是利用幾何圖形（正方形、矩形），按一個方向填寫構(gòu)造明文，按另一個方向讀取形成密文。 railfence（柵欄）加密法 三角形方式的換位,5,Rail Fence,Process: 明文字母重排次序 柵欄加密法 明文: this

2、 is a test 密文: tiehsstsiat,t,h,t,i,s,i,t,a,s,s,e,6,Other Figures,三角形方式:,明文: You must do that now,將明文逐行排列,m,u,o,Y,t,s,u,h,t,o,d,w,o,n,t,a,按列讀取得到明文,tuhosayuttmdnoow,7,Permutation Method（置換法）,Break the plaintext up into groups of a fixed size, d define a permutation of the integers 1 to d called f with

3、in each block, permute the letters according to f the key is (d,f)（d為每組字母數(shù)，f為置換規(guī)則） For example, let d = 5 and let f be given by:,g e t t h e b a l l,8,CAP Implementation,Select Permutation under the cipher menu,9,換位加密法分析,已知明文攻擊步驟： 找出包含有與已知單詞相同字母的塊 通過比較已知單詞與密文塊，確定置換方式 在密文的其他塊上測試上面得出的置換方式 例如密文：eialcii

4、thsansaehitcpoierhwipetzkors 如果“alice”出現(xiàn)在明文中，則找出包含有單詞“alice”的所有字母的塊，比如這里的第一塊 eialc 可以得出：1移到3，2移到4，3移到2，4移到5，5移到1，將這個置換方式應(yīng)用到密文的其他字母，就可以還原明文了。,10,Breaking a Permutation,A known word attack can match the word with the ciphertext to discover the permutation,11,列置換加密法,把明文按行書寫成一個矩陣，然后按給定的列的順序依次書寫成行就得到密文 例

5、如明文： “encryption algorithms” ，寫成一個 5x4 的矩陣,選擇列的順序是： 4 - 2 - 1 - 3,12,列置換的密鑰,列置換的密鑰是列標(biāo)（反映了多少列作為一個置換單元）和它們先后被選定的順序,這兩件事能用一個關(guān)鍵詞來表示:,關(guān)鍵詞的長度反映了置換單元的列數(shù),關(guān)鍵詞中字母的順序確定了被選的列的順序 the order of the letters in the keyword determines the order in which the columns are selected,13,密鑰例子,例如, 關(guān)鍵詞是 “general” 定義了一個7列的置換 根

6、據(jù)關(guān)鍵詞中字母在字表中出現(xiàn)的先后順序依次賦予從1到7的數(shù)字，這樣得到了7個數(shù)字的一個排列，用這個排列來確定生成密文的順序,g e n e r a l,1,2,3,4,5,6,7,14,Transpositions in CAP,When you select Column Transposition, CAP presents a key window:,15,破解列置換,下面講述能夠?qū)懗梢粋€完整矩形的列置換的密文的破解過程 看看下面的密文, 我們首先要確定什么呢？,NETEF LTDSR TSSTF MDCET DRHXS WHOHO EEADU OUUFI RRRRS NEROT CFIE

7、M EDSHA RTCPJ AOEGE WNLHO EPMWA WERUV AAINA TSDDS OEOAC EHNTL HFLAU RAEEN OTOTS SOSYS TNNCG EMETT YDYRR NEOOE RESTH INR,16,任務(wù),破解列置換加密要完成以下三個任務(wù)：There are three tasks involved in breaking a column transposition cipher: Find possible rectangle sizes（嘗試找出換位矩形的可能大?。憾嗌傩校嗌倭校?Select the correct rectangle（嘗

8、試找出這些可能的矩形中哪個是正確的） Find the column order（知道了正確的矩形后，嘗試重新排列矩形列，以便還原消息）,17,可能的矩形,分析列換位算法的第一步就是確定列的數(shù)目（矩形的大小：幾行幾列） 在一個完全填充的換位算法中）, 密文字母總數(shù)是列數(shù)乘以行數(shù) 因此, 這個字母總數(shù)的因子就可能是這個矩形的行數(shù)或列數(shù),18,例子,首先, 計算例子密文字母總數(shù) 這條信息總共有153 個字母，而 153的因子有3, 9, 17,和51 可能的矩形大小 (列乘以行): 3 x 51, 51 x 3, 9 x 17, or 17 x 9 9 x 17 和17 x 9 可能性大些 其他兩

9、種情形（行和列相差太大）,19,到底是哪種情形的矩陣呢?,由于這些因子只提供了列和行的可能大小，但是不確定那種情形是對的，這里要用一個元音檢測工具對每行進(jìn)行測試（元音測試） any line of plaintext should contain about 40% vowels（明文英語的每行應(yīng)包含大約40的元音字母） 計算每個矩形的每行的元音字母個數(shù) 如果某個矩形的元音檢測最接近 40% ，那么這個矩形就是最適合選作正確的矩形 具體是：計算出每行的元音字母數(shù)與期望的元音字母數(shù)（字母總數(shù)乘以40%）之差的絕對值，將這些差值相加，生成該矩形的得分。,20,矩形1,下面是 17 x 9的矩形，

10、每行的期望是3.6 個元音字母 (9 x 0.4),21,矩形 2,第2個矩形是 9 x 17(每行期望元音個數(shù)17 x 0.4= 6.8),這兩個矩形，那個是這個最可能的矩形呢?,22,字母的親近關(guān)系,一旦矩形被確定，那么解下來就是找出正確的列的順序 利用明文語言的所有特性： 1, 在所有的語言中都有一種現(xiàn)象，就是某些中低頻字母與其他字母組合后會形成一個高頻組合 如： H (中頻) 與 T 組合成 TH (高頻組合) H 與 C (中頻) 組合成 CH V (低頻) 與E 組合成VE (在軍事類文章中是中頻組合),23,引導(dǎo)字母,2, there is usually in every la

11、nguage at least one letter which can be followed by only certain other letters forming an obligatory sequence or invariable digraph(固定的雙字母組合體) Q 后面一般有 U J 后面經(jīng)常是元音字母 X前面一般是元音字母，除非它是單詞的末尾；它的后面只能是元音字母或 C, H, P, T 像前面說的字母，具有親近關(guān)系特性（或限制）的字母叫做 （引導(dǎo)字母）pilot letters,24,拼字謎,破解換位加密的過程就像是一個拼字謎的過程，利用上述的引導(dǎo)字母和常見的雙字

12、母組合以及同行中的其他字母來進(jìn)行拼單詞或猜單詞,例如, 在第8列中找到 J字母，然后尋找可能的匹配 . . .,25,Centiban Table（百分比加權(quán)表）,美國政府研究了5000連字集，用該表記錄每個連字頻率的2倍的對數(shù)值， 加權(quán)值越大，連字出現(xiàn)越多。,26,可能的配對,利用連字集的值來檢測字母對JU 是由哪兩列來搭配形成的,結(jié)果: 第 8和第13列更匹配,27,尋找第3個字母,連體字母JU 后面應(yīng)該是個輔音字母, 更可能是N 或 S ，即第15 列或第11列 是候選列,28,找單詞,繼續(xù)尋找新的字母對和可能的單詞 如：能否和同行的其他字母形成單詞呢？,繼續(xù)嘗試?yán)眠B體字集和尋找單詞,

13、enemy,29,明文解,Enemy patrol encountered just three hundred yards south of cross roads seven eight three stop. after exchange of small arms fire, enemy withdrew into woods and further contact was lost. 在783站的十字路口向南300碼處，遇到敵人巡邏小隊，在雙方進(jìn)行了短暫交火后，敵人撤退，進(jìn)入林子中，接著就失去聯(lián)系了。,30,Column Size in CAP,CAP will determine

14、both possible column sizes and run a vowel analysis of each column:,31,Anagramming（回文構(gòu)詞） in CAP,CAP provides a tool to aid in the anagramming process,32,多重?fù)Q位,換位加密的目的就是隨機(jī)打亂明文字母 這種混亂可以使用多重（次）使用換位加密，如: 雙重列換位加密 旋轉(zhuǎn)方格加密（Turning Grille）,33,概念,雙重列換位加密的操作就像它的名字提示的那樣： 對已經(jīng)使用過列換位加密后的結(jié)果再次使用列換位加密 每次換位加密使用的關(guān)鍵詞可以是同

15、一個關(guān)鍵詞，也可以不同. 結(jié)果是：明文字母被完全打亂了,34,例子,加密短語是 “encryption algorithms” ，并進(jìn)行兩次加密:,第一次用關(guān)鍵詞：next: 2-1-4-3,第二次用關(guān)鍵詞 image: 4-5-1-3-2,35,Using CAP,CAP will implement a double column transposition:,36,雙重列換位加密的分析,A weakness of the double column transposition cipher lies in the use of the same pair of keys on sever

16、al plaintext messages all of the same size.（弱點：使用相同密鑰多次加密相同大小的明文） 例如, 假如下列4個消息都是從 Bob和 Alice 的通信中截取的:,etmai atecb bsbnq xivjb eecqu heikn oxlct sedwn oowqq texda aqmue caeon ioox,panbt tjliu eeyhq xotbi dttqy dwbml bxooa oweal hoaqp nexbh tqaut iekau wocx,monat rtwle bocoq xhofb aurqe oxino oxlir de

17、far uhoqe mexbn nqttn cgwoo rtox,awsbe lymtt ernrq xtnei olfqt lebne uxorb okorl ocmqf iexru oqwhe oogao aacx,37,過程,把4則消息對齊疊起排列 就像處理一個大的拼字游戲一樣,etmai atecb bsbnq xivjb eecqu heikn oxlct sedwn oowqq texda aqmue caeon ioox panbt tjliu eeyhq xotbi dttqy dwbml bxooa oweal hoaqp nexbh tqaut iekau wocx mon

18、at rtwle bocoq xhofb aurqe oxino oxlir defar uhoqe mexbn nqttn cgwoo rtox awsbe lymtt ernrq xtnei olfqt lebne uxorb okorl ocmqf iexru oqwhe oogao aacx,Columns of “x” should all go to the end 其他列可以通過查看引導(dǎo)字母和可能的單詞來排列,38,etmai atecb bsbnq ivjb eecqu heikn olct sedwn oowqq teda aqmue caeon ioo panbt tjli

19、u eeyhq otbi dttqy dwbml booa oweal hoaqp nebh tqaut iekau woc monat rtwle bocoq hofb aurqe oxino olir defar uhoqe mebn nqttn cgwoo rto awsbe lymtt ernrq tnei olfqt lebne uorb okorl ocmqf ieru oqwhe oogao aac,39,Using CAP,CAP provides a special anagramming tool for Double Column Transpositions:,40,Turning Grilles（旋轉(zhuǎn)方格）,Turning Grilles 加密法是通過旋轉(zhuǎn)面上明