密码学-经典换位加密法.ppt

1 经典换位加密法 2 内容纲要 3 CipherStructure 4 Transpositions 换位 换位加密法不是用其他字母来代替已有字母 而是重新排列文本中的字母 类似于拼图游戏 所有的图块都在一个框中 只是排列的位置不同 两种不同的换位加密法 单图 monographic 换位 例如skytale 和多图 polygraphic 换位 换位加密法一般是利用几何图形 正方形 矩形 按一个方向填写构造明文 按另一个方向读取形成密文 rail fence 栅栏 加密法三角形方式的换位 5 RailFence Process 明文字母重排次序栅栏加密法明文 thisisatest密文 tiehsstsiat t h t i s i t a s s e 6 OtherFigures 三角形方式 明文 Youmustdothatnow 将明文逐行排列 m u o Y t s u h t o d w o n t a 按列读取得到明文 tuhosayuttmdnoow 7 PermutationMethod 置换法 Breaktheplaintextupintogroupsofafixedsize ddefineapermutationoftheintegers1todcalledfwithineachblock permutethelettersaccordingtofthekeyis d f d为每组字母数 f为置换规则 Forexample letd 5andletfbegivenby gettheball 8 CAPImplementation SelectPermutationundertheciphermenu 9 换位加密法分析 已知明文攻击步骤 找出包含有与已知单词相同字母的块通过比较已知单词与密文块 确定置换方式在密文的其他块上测试上面得出的置换方式例如密文 eialciithsansaehitcpoierhwipetzkors如果 alice 出现在明文中 则找出包含有单词 alice 的所有字母的块 比如这里的第一块eialc可以得出 1移到3 2移到4 3移到2 4移到5 5移到1 将这个置换方式应用到密文的其他字母 就可以还原明文了 10 BreakingaPermutation Aknownwordattackcanmatchthewordwiththeciphertexttodiscoverthepermutation 11 列置换加密法 把明文按行书写成一个矩阵 然后按给定的列的顺序依次书写成行就得到密文例如明文 encryptionalgorithms 写成一个5x4的矩阵 选择列的顺序是 4 2 1 3 12 列置换的密钥 列置换的密钥是列标 反映了多少列作为一个置换单元 和它们先后被选定的顺序 这两件事能用一个关键词来表示 关键词的长度反映了置换单元的列数 关键词中字母的顺序确定了被选的列的顺序theorderofthelettersinthekeyworddeterminestheorderinwhichthecolumnsareselected 13 密钥例子 例如 关键词是 general 定义了一个7列的置换根据关键词中字母在字表中出现的先后顺序依次赋予从1到7的数字 这样得到了7个数字的一个排列 用这个排列来确定生成密文的顺序 general 1 2 3 4 5 6 7 14 TranspositionsinCAP WhenyouselectColumnTransposition CAPpresentsakeywindow 15 破解列置换 下面讲述能够写成一个完整矩形的列置换的密文的破解过程看看下面的密文 我们首先要确定什么呢 NETEFLTDSRTSSTFMDCETDRHXSWHOHOEEADUOUUFIRRRRSNEROTCFIEMEDSHARTCPJAOEGEWNLHOEPMWAWERUVAAINATSDDSOEOACEHNTLHFLAURAEENOTOTSSOSYSTNNCGEMETTYDYRRNEOOERESTHINR 16 任务 破解列置换加密要完成以下三个任务 Therearethreetasksinvolvedinbreakingacolumntranspositioncipher Findpossiblerectanglesizes 尝试找出换位矩形的可能大小 多少行 多少列 Selectthecorrectrectangle 尝试找出这些可能的矩形中哪个是正确的 Findthecolumnorder 知道了正确的矩形后 尝试重新排列矩形列 以便还原消息 17 可能的矩形 分析列换位算法的第一步就是确定列的数目 矩形的大小 几行几列 在一个完全填充的换位算法中 密文字母总数是列数乘以行数因此 这个字母总数的因子就可能是这个矩形的行数或列数 18 例子 首先 计算例子密文字母总数这条信息总共有153个字母 而153的因子有3 9 17 和51可能的矩形大小 列乘以行 3x51 51x3 9x17 or17x99x17和17x9可能性大些其他两种情形 行和列相差太大 19 到底是哪种情形的矩阵呢 由于这些因子只提供了列和行的可能大小 但是不确定那种情形是对的 这里要用一个元音检测工具对每行进行测试 元音测试 anylineofplaintextshouldcontainabout40 vowels 明文英语的每行应包含大约40 的元音字母 计算每个矩形的每行的元音字母个数如果某个矩形的元音检测最接近40 那么这个矩形就是最适合选作正确的矩形具体是 计算出每行的元音字母数与期望的元音字母数 字母总数乘以40 之差的绝对值 将这些差值相加 生成该矩形的得分 20 矩形1 下面是17x9的矩形 每行的期望是3 6个元音字母 9x0 4 21 矩形2 第2个矩形是9x17 每行期望元音个数17x0 4 6 8 这两个矩形 那个是这个最可能的矩形呢 22 字母的亲近关系 一旦矩形被确定 那么解下来就是找出正确的列的顺序利用明文语言的所有特性 1 在所有的语言中都有一种现象 就是某些中低频字母与其他字母组合后会形成一个高频组合如 H 中频 与T组合成TH 高频组合 H与C 中频 组合成CHV 低频 与E组合成VE 在军事类文章中是中频组合 23 引导字母 2 thereisusuallyineverylanguageatleastoneletterwhichcanbefollowedbyonlycertainotherlettersforminganobligatorysequenceorinvariabledigraph 固定的双字母组合体 Q后面一般有UJ后面经常是元音字母X前面一般是元音字母 除非它是单词的末尾 它的后面只能是元音字母或C H P T像前面说的字母 具有亲近关系特性 或限制 的字母叫做 引导字母 pilotletters 24 拼字谜 破解换位加密的过程就像是一个拼字谜的过程 利用上述的引导字母和常见的双字母组合以及同行中的其他字母来进行拼单词或猜单词 例如 在第8列中找到J字母 然后寻找可能的匹配 25 CentibanTable 百分比加权表 美国政府研究了5000连字集 用该表记录每个连字频率的2倍的对数值 加权值越大 连字出现越多 26 可能的配对 利用连字集的值来检测字母对JU是由哪两列来搭配形成的 结果 第8和第13列更匹配 27 寻找第3个字母 连体字母JU后面应该是个辅音字母 更可能是N或S 即第15列或第11列是候选列 28 找单词 继续寻找新的字母对和可能的单词如 能否和同行的其他字母形成单词呢 继续尝试利用连体字集和寻找单词 enemy 29 明文解 Enemypatrolencounteredjustthreehundredyardssouthofcrossroadsseveneightthreestop afterexchangeofsmallarmsfire enemywithdrewintowoodsandfurthercontactwaslost 在783站的十字路口向南300码处 遇到敌人巡逻小队 在双方进行了短暂交火后 敌人撤退 进入林子中 接着就失去联系了 30 ColumnSizeinCAP CAPwilldeterminebothpossiblecolumnsizesandrunavowelanalysisofeachcolumn 31 Anagramming 回文构词 inCAP CAPprovidesatooltoaidintheanagrammingprocess 32 多重换位 换位加密的目的就是随机打乱明文字母这种混乱可以使用多重 次 使用换位加密 如 双重列换位加密旋转方格加密 TurningGrille 33 概念 双重列换位加密的操作就像它的名字提示的那样 对已经使用过列换位加密后的结果再次使用列换位加密每次换位加密使用的关键词可以是同一个关键词 也可以不同 结果是 明文字母被完全打乱了 34 例子 加密短语是 encryptionalgorithms 并进行两次加密 第一次用关键词 next 2 1 4 3 第二次用关键词image 4 5 1 3 2 35 UsingCAP CAPwillimplementadoublecolumntransposition 36 双重列换位加密的分析 Aweaknessofthedoublecolumntranspositioncipherliesintheuseofthesamepairofkeysonseveralplaintextmessagesallofthesamesize 弱点 使用相同密钥多次加密相同大小的明文 例如 假如下列4个消息都是从Bob和Alice的通信中截取的 etmaiatecbbsbnqxivjbeecquheiknoxlctsedwnoowqqtexdaaqmuecaeonioox panbttjliueeyhqxotbidttqydwbmlbxooaowealhoaqpnexbhtqautiekauwocx monatrtwlebocoqxhofbaurqeoxinooxlirdefaruhoqemexbnnqttncgwoortox awsbelymtternrqxtneiolfqtlebneuxorbokorlocmqfiexruoqwheoogaoaacx 37 过程 把4则消息对齐叠起排列就像处理一个大的拼字游戏一样 etmaiatecbbsbnqxivjbeecquheiknoxlctsedwnoowqqtexdaaqmuecaeoniooxpanbttjliueeyhqxotbidttqydwbmlbxooaowealhoaqpnexbhtqautiekauwocxmonatrtwlebocoqxhofbaurqeoxinooxlirdefaruhoqemexbnnqttncgwoortoxawsbelymtternrqxtneiolfqtlebneuxorbokorlocmqfiexruoqwheoogaoaacx Columnsof x shouldallgototheend其他列可以通过查看引导字母和可能的单词来排列 38 etmaiatecbbsbnqivjbeecquheiknolctsedwnoowqqtedaaqmuecaeonioopanbttjliueeyhqotbidttqydwbmlbooaowealhoaqpnebhtqautiekauwocmonatrtwlebocoqhofbaurqeoxinoolirdefaruhoqemebnnqttncgwoortoawsbelymtternrqtneiolfqtlebneuorbokorlocmqfieruoqwheoogaoaac 39 UsingCAP CAPprovidesaspecialanagrammingtoolforDoubleColumnTranspositions 40 TurningGrilles 旋转方格 TurningGrilles加密法是通过旋转面上明文有开口 开槽 的格兰或 窗 首次出现在C F Hindenburg于1796年写的一本书中18世纪末期使用频繁后来 德国军队在WWI曾使用过 41 解释 考虑有n 4v2个字母的信息构造一个方形棋盘 2v行和列 在每一个象限都填入1到v等数字 通过旋转依次填充其他的三个象限从这四个像限中选出数字1到v 这里用来确定开口的位置 42 例子 信息 Thisisatestofthemethodokyouaredoneno共36个字母 所以v 3 43 加密 Usethegrilleandits4rotationstocreatetheciphertext h t i