经典换位加密法PPT.ppt

经典换位加密法经典换位加密法1内容纲要Permutation（置换）（置换）Column Transposition（列换位）（列换位）2Cipher StructureTranspositionSubstitutionpolyalphabeticmonoalphabeticBlockStreamClassical...ShiftAffineKeywordMultiLiteralVigenereHillNihilist3Transpositions（换位）•换位加密法不是用其他字母来代替已有字母，而是重新排列文本中的字母，类似于拼图游戏，所有的图块都在一个框中，只是排列的位置不同•两种不同的换位加密法：单图（monographic）换位（例如skytale）和多图（polygraphic）换位•换位加密法一般是利用几何图形（正方形、矩形），按一个方向填写构造明文，按另一个方向读取形成密文•rail－fence（栅栏）加密法 三角形方式的换位 4Rail Fence•Process: 明文字母重排次序•栅栏加密法 –明文: this is a test–密文: tiehsstsiat明文锯齿形排列后明文锯齿形排列后按行读取得到密文按行读取得到密文thtisitasse5Other Figures•三角形方式:明文: You must do that now将明文逐行排列将明文逐行排列muoYtsuhtodwonta按列读取得到明文按列读取得到明文tuhosayuttmdnoow6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: 1324314552g e t t h e b a l lg etthe ball7CAP Implementation•Select Permutation under the cipher menu8换位加密法分析•已知明文攻击步骤：–找出包含有与已知单词相同字母的块–通过比较已知单词与密文块，确定置换方式–在密文的其他块上测试上面得出的置换方式•例如密文：eialciithsansaehitcpoierhwipetzkors•如果“alice”出现在明文中，则找出包含有单词“alice”的所有字母的块，比如这里的第一块 eialc•可以得出：1移到3，2移到4，3移到2，4移到5，5移到1，将这个置换方式应用到密文的其他字母，就可以还原明文了。

9Breaking a Permutation•A known word attack can match the word with the ciphertext to discover the permutation10列置换加密法•把明文按行书写成一个矩阵，然后按给定的列的顺序依次书写成行就得到密文•例如明文： “encryption algorithms” ，写成一个 5x4 的矩阵RCNEITPYLANOIROGSMHTISLIR1 12 2 3 3 4 4选择列的顺序是：选择列的顺序是： 4 - 2 - 1 - 3KEYCTARMRILISOHNPNGTOYERMATCNPNOHEYOGT11列置换的密钥•列置换的密钥是列标（反映了多少列作为一个置换单元）和它们先后被选定的顺序 这两件事能用一个关键词来表示这两件事能用一个关键词来表示:关键词的长度反映了置换单元的列数关键词的长度反映了置换单元的列数关键词中字母的顺序确定了被选的列的顺序关键词中字母的顺序确定了被选的列的顺序the order of the letters in the keyword determines the order in which the columns are selected12密钥例子•例如, 关键词是 “general” 定义了一个7列的置换•根据关键词中字母在字表中出现的先后顺序依次赋予从1到7的数字，这样得到了7个数字的一个排列，用这个排列来确定生成密文的顺序g e n e r a l123456713Transpositions in CAP•When you select Column Transposition, CAP presents a key window:14破解列置换•下面讲述能够写成一个完整矩形的列置换的密文的破解过程•看看下面的密文, 我们首先要确定什么呢？NETEF LTDSR TSSTF MDCET DRHXS WHOHO EEADU OUUFI RRRRSNEROT CFIEM EDSHA RTCPJ AOEGE WNLHO EPMWA WERUV AAINATSDDS OEOAC EHNTL HFLAU RAEEN OTOTS SOSYS TNNCG EMETT YDYRR NEOOE RESTH INR15任务•破解列置换加密要完成以下三个任务：There are three tasks involved in breaking a column transposition cipher:–Find possible rectangle sizes（尝试找出换位矩形的可能大小：多少行，多少列）–Select the correct rectangle（尝试找出这些可能的矩形中哪个是正确的）–Find the column order（知道了正确的矩形后，尝试重新排列矩形列，以便还原消息）16可能的矩形•分析列换位算法的第一步就是确定列的数目（矩形的大小：几行几列）•在一个完全填充的换位算法中）, 密文字母总数是列数乘以行数•因此, 这个字母总数的因子就可能是这个矩形的行数或列数17例子•首先, 计算例子密文字母总数•这条信息总共有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 可能性大些• 其他两种情形（行和列相差太大）18到底是哪种情形的矩阵呢?•由于这些因子只提供了列和行的可能大小，但是不确定那种情形是对的，这里要用一个元音检测工具对每行进行测试（元音测试）–any line of plaintext should contain about 40% vowels（明文英语的每行应包含大约40％的元音字母）–计算每个矩形的每行的元音字母个数–如果某个矩形的元音检测最接近 40% ，那么这个矩形就是最适合选作正确的矩形–具体是：计算出每行的元音字母数与期望的元音字母数（字母总数乘以40%）之差的绝对值，将这些差值相加，生成该矩形的得分。

19矩形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.6E E O I E A T S Y 73.4T T U E W I L O R 4 .4E D U M N N H S R 21.6F R F E L A F Y N 3 .6L H I D H T L S E 21.6T X R S O S A T O 3 .6D S R H E D U N O 3 .6S W R A P D R N E 2 1.6R H R R M S A C R 12.6T O S T W O E G E 4 .4S H N C A E E E S 4 .4S O E P W O N M T 3 .6T E R J E A O E H 51.4F E O A R C T T I 4 .4M A T O U E O T N 51.4D D C E V H T Y R 21.6总差值 20.620矩形 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.2E T T H U E E J H R S E U T N D R 6 .8T S D O F R D A O U D H R S C Y E 6 .8E S R E I O S O E V D N A S G R S 7 .2F T H E R T H E P A S T E O E R T 6 .8L F X A R C A G M A O L E S M N H 5 1.8T M S D R F R E W I E H N Y E E I 7 .2D D W U R I T W A N O F O S T O N 6 .8S C H O S E C N W A A L T T T O R 5 1.8 总差值8.4这两个矩形，那个是这个最可能的矩形呢?21字母的亲近关系•一旦矩形被确定，那么解下来就是找出正确的列的顺序•利用明文语言的所有特性：•1, 在所有的语言中都有一种现象，就是某些中低频字母与其他字母组合后会形成一个高频组合•如：–H (中频) 与 T 组合成 TH (高频组合)–H 与 C (中频) 组合成 CH–V (低频) 与E 组合成VE (在军事类文章中是中频组合)22引导字母•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 letters23拼字谜•破解换位加密的过程就像是一个拼字谜的过程，破解换位加密的过程就像是一个拼字谜的过程，利用上述的引导字母和常见的双字母组合以及同利用上述的引导字母和常见的双字母组合以及同行中的其他字母来进行拼单词或猜单词行中的其他字母来进行拼单词或猜单词例如例如, 在第在第8列中找到列中找到 J字母，然后字母，然后寻找可能的匹配寻找可能的匹配 . . .1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17N R E O U N M P L E T C A O N Y EE T T H U E E J H R S E U T N D RT S D O F R D A O U D H R S C Y EE S R E I O S O E V D N A S G R SF T H E R T H E P A S T E O E R TL F X A R C A G M A O L E S M N HT M S D R F R E W I E H N Y E E ID D W U R I T W A N O F O S T O NS C H O S E C N W A A L T T T O R8J24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 ZA 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 00C 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 00D 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 00E 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 13F 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 00G 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 00H 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 00I 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 25J 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 00K 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 00L 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 00M 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 00N 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 00O 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 00P 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 00Q 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 00R 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 00S 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 00T 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 13U 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 00V 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 00W 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 00Y 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 00Z 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 00Second LetterFirst Letter美国政府研究了美国政府研究了美国政府研究了美国政府研究了50005000连字集，用该表记录每个连字频率的连字集，用该表记录每个连字频率的连字集，用该表记录每个连字频率的连字集，用该表记录每个连字频率的2 2倍的对数值，倍的对数值，倍的对数值，倍的对数值，加权值越大，连字出现越多。

加权值越大，连字出现越多加权值越大，连字出现越多加权值越大，连字出现越多25可能的配对•利用连字集的值来检测字母对JU 是由哪两列来搭配形成的8 5 rank8 13 rankP U 33P A 61J U 25J U 25A F 38A R 82O I 42O A 48E R 94E E 81G R 42G E 61E R 94E N 99W N 25W O 67N S 71N T 93求和 464 求和 617结果: 第 8和第13列更匹配26寻找第3个字母•连体字母JU 后面应该是个辅音字母, 更可能是N 或 S ，即第15 列或第11列 是候选列8 13 15 rank8 13 11 rankP A N 89P A T 83J U N 68J U S 58A R C 53A R D 64O A G 45O A D 73E E E 81E E S 86G E M 61G E O 58E N E 87E N E 87W 0 T 67W O O 45N T T 67N T A 74 618 62827找单词•继续寻找新的字母对和可能的单词•如：能否和同行的其他字母形成单词呢？8 13 11 1 2 3 4 5 6 7 9 10 12 14 15 16 17P A T N R E O U N M L E C O N Y EJ U S E T T H U E E H R E T N D RA R D T S D O F R D O U H S C Y EO A D E S R E I O S E V N S G R SE E S F T H E R T H P A T O E R TG E O L F X A R C A M A L S M N HE N E T M S D R F R W I H Y E E IW O O D D W U R I T A N F S T O NN T A S C H O S E C W A L T T O R继续尝试利用连体字集和寻找单词继续尝试利用连体字集和寻找单词enemyenemy28明文解3 6 17 7 16 8 13 11 2 14 9 10 1 12 4 5 15E N E M Y P A T R O L E N C O U NT E R E D J U S T T H R E E H U ND R E D Y A R D S S O U T H O F CR O S S R O A D S S E V E N E I GH T T H R E E S T O P A F T E R EX C H A N G E O F S M A L L A R MS F I R E E N E M Y W I T H D R EW I N T O W O O D S A N D F U R TH E R C O N T A C T W A S L O S TEnemy patrol encountered just three hundred yards south of cross Enemy patrol encountered just three hundred yards south of cross roads seven eight three stoproads seven eight three stop. . after exchange of small arms fire after exchange of small arms fire, , enemy withdrew into woodsenemy withdrew into woods andand further contact was lostfurther contact was lost. .在在783783站的十字路口向南站的十字路口向南300300码处，遇到敌人巡逻小队，在双方进行码处，遇到敌人巡逻小队，在双方进行了短暂交火后，敌人撤退，进入林子中，接着就失去联系了。

了短暂交火后，敌人撤退，进入林子中，接着就失去联系了29Column Size in CAP•CAP will determine both possible column sizes and run a vowel analysis of each column:30Anagramming（回文构词） in CAP•CAP provides a tool to aid in the anagramming process31多重换位•换位加密的目的就是随机打乱明文字母•这种混乱可以使用多重（次）使用换位加密，如:•双重列换位加密•旋转方格加密（Turning Grille）32概念• 双重列换位加密的操作就像它的名字提示的那样： –对已经使用过列换位加密后的结果再次使用列换位加密–每次换位加密使用的关键词可以是同一个关键词，也可以不同. –结果是：明文字母被完全打乱了33例子•加密短语是 “encryption algorithms” ，并进行两次加密:第一次用关键词：第一次用关键词：第一次用关键词：第一次用关键词：next: 2-1-4-3next: 2-1-4-3CTARMRILISNPNOHEYOGT1 12 2 3 3 4 4第二次用关键词第二次用关键词第二次用关键词第二次用关键词 image: 4-5-1-3-2image: 4-5-1-3-2HONPNNHONP1 12 2 3 3 4 4 5 5CMRATTGOYEETGOYMRATCSILIRRSILITIYPRIGORIGOMSTHCRENALONMSTHCRENTIYPALON34Using CAP•CAP will implement a double column transposition:35双重列换位加密的分析•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 oow etmai atecb bsbnq xivjb eecqu heikn oxlct sedwn oow texda aqmue caeon iooxtexda aqmue caeon iooxpanbt tjliu eeyhq xotbi dttqy dwbml bxooa oweal hoaqp panbt tjliu eeyhq xotbi dttqy dwbml bxooa oweal hoaqp nexbh tqaut iekau wocxnexbh tqaut iekau wocxmonat rtwle bocoq xhofb aurqe oxino oxlir defar uhoqe monat rtwle bocoq xhofb aurqe oxino oxlir defar uhoqe mexbn nqttn cgwoo rtoxmexbn nqttn cgwoo rtoxawsbe lymtt ernrq xtnei olfqt lebne uxorb okorl ocmqf awsbe lymtt ernrq xtnei olfqt lebne uxorb okorl ocmqf iexru oqwhe oogao aacxiexru oqwhe oogao aacx36过程•把4则消息对齐叠起排列–就像处理一个大的拼字游戏一样etmai atecb bsbnq xivjb eecqu heikn oxlct sedwn oow texda aqmue caeon iooxetmai atecb bsbnq xivjb eecqu heikn oxlct sedwn oow texda aqmue caeon iooxpanbt tjliu eeyhq xotbi dttqy dwbml bxooa oweal hoaqp nexbh tqaut iekau wocxpanbt tjliu eeyhq xotbi dttqy dwbml bxooa oweal hoaqp nexbh tqaut iekau wocxmonat rtwle bocoq xhofb aurqe oxino oxlir defar uhoqe mexbn nqttn cgwoo rtoxmonat rtwle bocoq xhofb aurqe oxino oxlir defar uhoqe mexbn nqttn cgwoo rtoxawsbe lymtt ernrq xtnei olfqt lebne uxorb okorl ocmqf iexru oqwhe oogao aacxawsbe lymtt ernrq xtnei olfqt lebne uxorb okorl ocmqf iexru oqwhe oogao aacxColumns of “x” should all go to the end其他列可以通过查看引导字母和可能的单词来排列其他列可以通过查看引导字母和可能的单词来排列37•etmai atecb bsbnq ivjb eecqu heikn olct sedwn oow 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 aac38Using CAP•CAP provides a special anagramming tool for Double Column Transpositions:39Turning Grilles（旋转方格）•Turning Grilles 加密法是通过旋转面上明文有开口（开槽）的格兰或（窗）–首次出现在C.F.Hindenburg于1796年写的一本书中–18世纪末期使用频繁–后来，德国军队在WWI曾使用过40解释•考虑 有n = 4v2 个字母的信息–构造一个方形棋盘 （2v 行和列）–在每一个象限都填入1 到 v等数字，–通过旋转依次填充其他的三个象限–从这四个像限中选出数字 1 到 v ，这里用来确定开口的位置 41例子•信息: This is a test of the method ok you are done no–共36个字母，所以 v = 3123456789987654321987654321987654321234567891Result:42加密•Use the grille and its 4 rotations to create the ciphertexthtisisatehtisisatestofthemestofthemethodokyouthodokyouaredonenoaredonenoWrite the message in the open slotsWrite the message in the open slots43解密•在密文上旋转 grille ，通过开口读取明文htisisatestofthemethodokyouaredoneno44Using CAP•Select Turning Grille under the cipher menu45Summary•Introduction to Transpositions–Permutation–Column Transposition–Double Column Transposition–Turning Grilles46 刚才的发言，如刚才的发言，如有不当之处请多指有不当之处请多指正。

谢谢大家！　　正谢谢大家！　　47。