经典换位加密法PPT.ppt

Slide Title,广东警官学院 计算机系,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,经典换位加密法,2,内容纲要,Permutation,（置换）,Column Transposition,（列换位）,3,Cipher Structure,Transposition,Substitution,polyalphabetic,monoalphabetic,Block,Stream,Classical,.,Shift,Affine,Keyword,MultiLiteral,Vigenere,Hill,Nihilist,4,Transpositions,（换位）,换位加密法不是用其他字母来代替已有字母，而是重新排列文本中的字母，类似于拼图游戏，所有的图块都在一个框中，只是排列的位置不同。,两种不同的换位加密法：单图（,monographic,）换位（例如,skytale,）和多图（,polygraphic,）换位。,换位加密法一般是利用几何图形（正方形、矩形），按一个方向填写构造明文，按另一个方向读取形成密文。,rail,fence,（栅栏）加密法 三角形方式的换位,5,Rail Fence,Process,:,明文字母重排次序,栅栏加密法,明文,:this 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,within each block,permute the letters according to f,the key is(d,f),（,d,为每组字母数，,f,为置换规则）,For example,let d=5 and let f be given by:,1,3,2,4,3,1,4,5,5,2,g e t t h e b a l l,g,e,t,t,h,e,b,a,l,l,8,CAP Implementation,Select Permutation under the cipher menu,9,换位加密法分析,已知明文攻击步骤：,找出包含有与已知单词相同字母的块,通过比较已知单词与密文块，确定置换方式,在密文的其他块上测试上面得出的置换方式,例如密文：,eialciithsansaehitcpoierhwipetzkors,如果“,alice”,出现在明文中，则找出包含有单词“,alice”,的所有字母的块，比如这里的第一块,eialc,可以得出：,1,移到,3,，,2,移到,4,，,3,移到,2,，,4,移到,5,，,5,移到,1,，将这个置换方式应用到密文的其他字母，就可以还原明文了。,10,Breaking a Permutation,A known word attack can match the word with the ciphertext to discover the permutation,11,列置换加密法,把明文按行书写成一个矩阵，然后按给定的列的顺序依次书写成行就得到密文,例如明文：“,encryption algorithms”,，写成一个,5x4,的矩阵,R,C,N,E,I,T,P,Y,L,A,N,O,I,R,O,G,S,M,H,T,I,S,L,I,R,1,2,3,4,选择列的顺序是：,4-2-1-3,KEY,C,T,A,R,M,R,I,L,I,S,O,H,N,P,N,G,T,O,Y,E,R,M,A,T,C,N,P,N,O,H,E,Y,O,G,T,12,列置换的密钥,列置换的密钥是,列标,（反映了多少列作为一个置换单元）和它们先后被选定的顺序,这两件事能用一个关键词来表示关键词的长度反映了置换单元的列数,关键词中字母的顺序确定了被选的列的顺序,the order of the letters in the keyword determines,the order in which the columns are selected,13,密钥例子,例如,关键词是“,general”,定义了一个7列的置换,根据关键词中字母在字表中出现的先后顺序依次赋予从1到7的数字，这样得到了7个数字的一个排列，用这个排列来确定生成密文的顺序,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,破解列置换,下面讲述能够写成一个完整矩形的列置换的密文的破解过程,看看下面的密文,我们首先要确定什么呢？,NETEF LTDSR TSSTF MDCET DRHXS WHOHO EEADU OUUFI RRRRS,NEROT CFIEM EDSHA RTCPJ AOEGE WNLHO EPMWA WERUV AAINA,TSDDS OEOAC EHNTL HFLAU RAEEN OTOTS SOSYS TNNCG EMETT,YDYRR NEOOE RESTH INR,16,任务,破解列置换加密要完成以下三个任务：,There are three tasks involved in breaking a column transposition cipher:,Find possible rectangle sizes,（尝试找出换位矩形的可能大小：多少行，多少列）,Select the correct rectangle,（尝试找出这些可能的矩形中哪个是正确的）,Find the column order,（知道了正确的矩形后，尝试重新排列矩形列，以便还原消息）,17,可能的矩形,分析列换位算法的第一步就是确定列的数目（矩形的大小：几行几列）,在一个完全填充的换位算法中）,密文字母总数是列数乘以行数,因此,这个字母总数的因子就可能是这个矩形的行数或列数,18,例子,首先,计算例子密文字母总数,这条信息总共有,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,可能性大些,其他两种情形（行和列相差太大）,19,到底是哪种情形的矩阵呢,?,由于这些因子只提供了列和行的可能大小，但是不确定那种情形是对的，这里要用一个元音检测工具对每行进行测试（元音测试）,any line of plaintext should contain about 40%vowels,（明文英语的每行应包含大约,40,的元音字母）,计算每个矩形的每行的元音字母个数,如果某个矩形的元音检测最接近,40%,，那么这个矩形就是最适合选作正确的矩形,具体是：计算出每行的元音字母数与期望的元音字母数（字母总数乘以,40%,）之差的绝对值，将这些差值相加，生成该矩形的得分。,20,矩形,1,下面是,17 x 9,的矩形，每行的期望是,3.6,个元音字母,(9 x,0,.4),1 2 3 4 5 6 7 8 9,元音个数 与期望的差值,N C U F G A N S E 21.6,E E O I E A T S Y 73.4,T T U E W I L O R 4.4,E D U M N N H S R 21.6,F R F E L A F Y N 3.6,L H I D H T L S E 21.6,T X R S O S A T O 3 .6,D S R H E D U N O 3.6,S W R A P D R N E 2 1.6,R H R R M S A C R 12.6,T O S T W O E G E 4.4,S H N C A E E E S 4.4,S O E P W O N M T 3.6,T E R J E A O E H 51.4,F E O A R C T T I 4 .4,M A T O U E O T N 51.4,D D C E V H T Y R 21.6,总差值,20.6,21,矩形,2,第2个矩形是,9,x 17(,每行期望元音个数,17 x,0.4=,6.8),1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,元音个数 与期望的差值,N R E O U N M P L E T C A O N Y E 8 1.2,E T T H U E E J H R S E U T N D R 6 .8,T S D O F R D A O U D H R S C Y E 6 .8,E S R E I O S O E V D N A S G R S 7 .2,F T H E R T H E P A S T E O E R T 6 .8,L F X A R C A G M A O L E S M N H 5 1.8,T M S D R F R E W I E H N Y E E I 7 .2,D D W U R I T W A N O F O S T O N 6 .8,S C H O S E C N W A A L T T T O R 5 1.8,总差值,8.4,这两个矩形，那个是这个最可能的矩形呢,?,22,字母的亲近关系,一旦矩形被确定，那么解下来就是找出正确的列的顺序,利用明文语言的所有特性：,1,在所有的语言中都有一种现象，就是某些中低频字母与其他字母组合后会形成一个高频组合,如：,H(,中频,),与,T,组合成,TH(,高频组合,),H,与,C(,中频,),组合成,CH,V(,低频,),与,E,组合成,VE(,在军事类文章中是中频组合,),23,引导字母,2,there is usually in every language at least one letter which can be followed by only certain other letters forming an,obligatory sequence,or,invariable digraph,(,固定的双字母组合体,),Q,后面一般有,U,J,后面经常是元音字母,X,前面一般是元音字母，除非它是单词的末尾；它的后面只能是元音字母或,C,H,P,T,像前面说的字母，具有亲近关系特性（或限制）的字母叫做（引导字母）,pilot letters,24,拼字谜,破解换位加密的过程就像是一个拼字谜的过程，利用上述的引导字母和常见的双字母组合以及同行中的其他字母来进行拼单词或猜单词,例如,在第8列中找到,J,字母，然后,寻找可能的匹配,.,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,N R E O U N M P L E T C A O N Y E,E T T H U E E J H R S E U T N D R,T S D O F R D A O U D H R S C Y E,E S R E I O S O E V D N A S G R S,F T H E R T H E P A S T E O E R T,L F X A R C A G M A O L E S M N H,T M S D R F R E W I E H N Y E E I,D D W U R I T W A N O F O S T O N,S C H O S E C N W A A L T T T O R,8,J,25,Centiban Table,（百分比加权表）,A B C D E F G H I J K L M N O P Q R S T U V W X Y Z,A 33 45 61 73 13 38 45 25 64 13 25 76 61 89 25 58 00 82 80 83 59 48 33 00 58 00,B 38 00 00 00 66 00 00 00 25 13 00 45 13 00 38 00 00 25 13 13 25 00 00 00 48 00,C 67 00 33 13 76 13 00 61 48 00 38 42 13 13 80 00 00 38 13 61 38 00 13 00 13 00,D 76 38 38 51 77 51 25 25 73 13 00 33 42 38 63 42 25 58 59 62 42 33 38 00 13 00,E 78 38 76 88 81 66 38 48 73 13 00 74 61 99 58 67 58 94 86 79 33 67 48 48 38 13,F 42 00 25 13 55 56 13 00 80 00 00 25 13 00 80 13 00 53 33 56 33 00 13 00 13 00,G 48 00 25 13 61 25 13 67 42 13 00 25 13 33 45 25 00 42 33 38 25 00 13 00 00 00,H 67 13 33 25 67 42 00 00 77 00 00 13 25 33 67 13 13 64 38 74 51 00 13 00 13 00,I 51 25 69 45 59 55 67 00 00 00 25 70 53 92 80 48 00 73 78 73 00 72 00 62 00 25,J 18 00 00 00 25 00 00 00 00 00 00 00 00 00 25 00 00 00 00 00 25 00 00 00 00 00,K 13 00 13 00 45 00 00 00 25 00 00 13 00 13 00 00 00 00 13 00 00 00 00 00 00 00,L 74 33 33 53 79 33 13 13 67 00 00 73 25 13 59 33 00 25 45 51 25 25 25 00 55 00,M 78 45 33 13 72 13 00 13 53 00 00 00 59 00 55 51 00 25 38 25 25 00 00 00 25 00,N 72 25 67 85 87 53 73 38 75 13 25 42 42 51 66 33 13 38 71 93 48 33 33 00 42 00,O 48 38 51 58 33 72 25 33 42 13 25 67 72 92 45 72 00 89 61 67 79 48 51 13 25 00,P 61 13 13 13 70 25 00 33 45 00 00 59 38 13 64 56 00 66 45 51 33 13 13 00 13 00,Q 00 00 00 00 00 00 00 00 00 00 00 00 13 00 00 00 00 13 00 00 62 00 00 00 00 00,R 80 25 53 64 96 45 48 33 75 13 13 42 53 48 74 59 00 56 75 81 42 42 38 00 53 00,S 71 33 59 42 84 58 25 72 77 00 13 25 33 38 62 55 00 42 67 88 56 13 38 00 13 00,T 74 33 45 45 91 48 13 92 82 00 00 42 45 48 84 25 13 64 67 67 42 00 78 00 80 13,U 42 33 33 33 56 13 51 00 42 00 00 45 42 68 13 25 00 75 58 58 00 13 00 00 00 00,V 45 00 00 00 87 00 00 00 58 00 00 00 00 00 13 00 00 00 00 13 00 00 00 00 00 00,W 58 00 00 00 69 00 00 38 59 00 00 13 00 25 67 00 00 13 13 00 00 00 00 00 13 00,X 25 00 25 13 13 13 00 13 25 00 00 00 00 13 13 25 00 13 13 48 00 00 00 00 00 00,Y 45 25 38 38 53 56 13 13 33 00 00 25 25 45 55 33 00 38 56 62 13 00 13 00 00 00,Z 13 00 00 00 25 00 00 00 13 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00,Second Letter,F,i,r,s,t,L,e,t,t,e,r,美国政府研究了,5000,连字集，用该表记录每个连字频率的,2,倍的对数值，,加权值越大，连字出现越多。,26,可能,的,配对,利用连字集的值来检测字母对,JU,是由哪两列来搭配形成的,8 5 rank8 13 rank,P U 33P A 61,J U 25J U 25,A F 38A R 82,O I 42O A 48,E R 94E E 81,G R 42G E 61,E R 94E N 99,W N 25W O 67,N S 71N T 93,求和,464,求和,617,结果,:,第,8,和第,13,列更匹配,27,寻找第3个字母,连体字母,JU,后面应该是个辅音字母,更可能是,N,或,S,，即第,15,列或第,11,列 是候选列,8 13 15 rank8 13 11 rank,P A N 89P A T 83,J U N 68J U S 58,A R C 53A R D 64,O A G 45O A D 73,E E E 81E E S 86,G E M 61G E O 58,E N E 87E N E 87,W 0 T 67W O O 45,N T T 67N T A 74,618 628,28,找单词,继续寻找新的字母对和可能的单词,如：能否和同行的其他字母形成单词呢？,8 13 11 1 2 3 4 5 6 7 9 10 12 14 15 16 17,P A T N R E O U N M L E C O N Y E,J U S E T T H U E E H R E T N D R,A R D T S D O F R D O U H S C Y E,O A D E S R E I O S E V N S G R S,E E S F T H E R T H P A T O E R T,G E O L F X A R C A M A L S M N H,E N E T M S D R F R W I H Y E E I,W O O D D W U R I T A N F S T O N,N T A S C H O S E C W A L T T O R,继续尝试利用连体字集和寻找单词,enemy,29,明文解,3 6 17 7 16 8 13 11 2 14 9 10 1 12 4 5 15,E N E M Y P A T R O L E N C O U N,T E R E D J U S T T H R E E H U N,D R E D Y A R D S S O U T H O F C,R O S S R O A D S S E V E N E I G,H T T H R E E S T O P A F T E R E,X C H A N G E O F S M A L L A R M,S F I R E E N E M Y W I T H D R E,W I N T O W O O D S A N D F U R T,H E R C O N T A C T W A S L O S T,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码处，遇到敌人巡逻小队，在双方进行了短暂交火后，敌人撤退，进入林子中，接着就失去联系了。,30,Column Size in CAP,CAP will determine both possible column sizes and run a vowel analysis of each column:,31,Anagramming,（回文构词）,in CAP,CAP provides a tool to aid in the anagramming process,32,多重换位,换位加密的目的就是随机打乱明文字母,这种混乱可以使用多重（次）使用换位加密，如:,双重列换位加密,旋转方格加密（,Turning Grille,）,33,概念,双重列换位加密的操作就像它的名字提示的那样：,对已经使用过列换位加密后的结果再次使用列换位加密,每次换位加密使用的关键词可以是同一个关键词，也可以不同,.,结果是：明文字母被完全打乱了,34,例子,加密短语是“,encryption algorithms”,，并进行两次加密,:,第一次用关键词：,next:2-1-4-3,C,T,A,R,M,R,I,L,I,S,N,P,N,O,H,E,Y,O,G,T,1,2,3,4,第二次用关键词,image:4-5-1-3-2,H,O,N,P,N,N,H,O,N,P,1,2,3,4,5,CM,R,A,T,T,G,O,Y,E,E,T,G,O,Y,M,R,A,T,C,S,I,L,I,R,R,S,I,L,I,T,I,Y,P,R,I,G,O,R,I,G,O,M,S,T,H,C,R,E,N,A,L,O,N,M,S,T,H,C,R,E,N,T,I,Y,P,A,L,O,N,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 several 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 defar 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,monat 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,其他列可以通过查看引导字母和可能的单词来排列,38,etmai atecb bsbnq ivjb eecqu heikn olct sedwn oowqq teda aqmue caeon ioo,panbt tjliu 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,（旋转方格）,Turning Grilles,加密法是通过旋转面上明文有开口（开槽）的格兰或（窗）,首次出现在,C.F.Hindenburg,于,1796,年写的一本书中,18,世纪末期使用频繁,后来，德国军队在,WWI,曾使用过,41,解释,考虑 有,n=4v,2,个字母的信息,构造一个方形棋盘（,2v,行和列）,在每一个象限都填入,1,到,v,等数字，,通过旋转依次填充其他的三个象限,从这四个像限中选出数字,1,到,v,，这里用来确定开口的位置,42,例子,信息,:,This is a test of the method ok you are done no,共,36,个字母，所以,v=3,1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1,9,8,7,6,5,4,3,2,1,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,1,Result:,43,加密,Use the grille and its 4 rotations to create the ciphertext,h,t,i,s,i,s,a,t,e,h,t,i,s,i,s,a,t,e,s,t,o,f,t,h,e,m,e,s,t,o,f,t,h,e,m,e,t,h,o,d,o,k,y,o,u,t,h,o,d,ok,y,o,u,a,r,e,d,o,n,e,n,o,a,r,e,d,o,n,e,n,o,Write the message in the open slots,44,解密,在密文上旋转,grille,，通过开口读取明文,h,t,i,s,i,s,a,t,e,s,t,o,f,t,h,e,m,e,t,h,o,d,o,k,y,o,u,a,r,e,d,o,n,e,n,o,45,Using CAP,Select Turning Grille under the cipher menu,46,Summary,Introduction to Transpositions,Permutation,Column Transposition,Double Column Transposition,Turning Grilles,