3,密码的基本编码原理.ppt

密码的基本编码原理 主要内容 易位密码的定义及应用 代替密码的定义及应用 代替密码的简单分析重点 易位密码和代替密码的基本工作原理难点 多表代替 单表代替的简单分析 编制密码的基本原理 通过各种不同的编码方法 使得在密钥及其相应密码算法的作用下 将明文集合变换成密文集合的过程 编制密码的方法 易位 代替 字典 加减和混合 本章简要介绍易位密码和代替密码的编制方法和发展过程 易位密码 易位密码是按某种密钥指示规则对明文进行位置移动的密码 易位密码的发展从低级到高级经历了简单易位 有限密钥指示易位和无限密钥指示易位 一 简单易位 简单易位是一种初级易位密码 其基本思想是按照一定的规则 简单打乱明文排列顺序生成密文 如电文倒置法是将明文按组倒排 明文为 23473489密文为 74329843 二 有限密钥指示易位 1 单码密钥指示易位 有限密钥指示易位是按密钥指示的规则将明文进行位置移动生成密文 它又分为单码密钥指示易位和双重密钥指示易位 单码密钥指示易位所用密钥可表示为置换 密钥长度为t 加密时 首先将明文分成长为t的明文组 对每一组用同一密钥加密 例如 设明文为M wewillmeet 加密密钥k为置换 254163 明文分组后为 M wewill meetzz 加密后所得密文为 C eliwlw eztmze 脱密时先由加密密钥求出脱密密钥 即置换t的逆置换T 416325 再按照脱密密钥指示的规则对密文分组进行位置移动即得明文 由于密钥长度为6 故加密时首先将明文分成长为6的子组 若不能分成整组 可将最后一组补虚码使成整组 不妨设虚码为z 然后对各子组按密钥指示的顺序进行位置移动即得密文 密钥变化量 是指所有可能的密钥总数 是衡量密码保密水平的重要数量指标 密钥变化量要足够大 以抗击密钥穷尽攻击 此例中密钥长度为6 共有6 种不同的密钥指示易位方法 密钥变化量为 6 一般地 密钥长度为l的单码密钥指示易位 其密钥变化量为 l 2 双重密钥指示易位 双重密钥指示易位密码的编制方法为 通信双方事先约定好一m n的方格及相应的行 列密钥 加密时 首先将明文分成长为m n的明文组 对每一组 按行密钥指示顺序将明文填入方格 再按列密钥指示顺序抄出即为密文 脱密时 按列密钥指示顺序将密文填入方格 再按行密钥指示顺序抄出即为明文 明文为 M abcdefghijklmnopqrstuvwxyzab 密文为 C jtyozeisxnzdfpukzahrwmbcgqvlab 密钥变化量为 三 无限密钥指示易位 无限密钥指示易位密码亦称无限易位密码 是指在明文中的每个字母均用一客观无限密钥来指示移位 注 易位密码只改变明文元素的位置 不改变明文的原形和统计特性 代替密码 代替密码是按照一定的规则 以特定的数码 字母等隐蔽明文原形的密码 代替密码的表现形式一般为代替表 收发双方按事先约定的代替表和使用方法实现收发报 代替密码的发展从低级到高级经历了单表代替 多表代替和无限代替 一 单表代替 1 大简便代替 大简便代替密码的编制方法为 以顺序的十个单码为明行 以乱序的十个单码为密行 加密时以密行数据取代相应的明行数据 脱密时以明行数据取代相应的密行数据 只有一个代替表的代替密码称为单表代替 常见的单表代替密码有 若明文为 M 1234789056120098 则密文为 C 3456982170341128 密钥变化量为 10 对于英文字母也可按同样的方法编制代替表 即为英文一般代替表 英文一般代替表的变化量为26 例如 凯撒密码的原理是指明文字母由该字母后第三字母代替 代替密码 例如 明文 密文rpqldjdooldhvwglylvdlqsduwhvwuhv ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC 2 凯撒密表 加密变换 将明文空间和密文空间都选为 英文ABCDEFGHIJKLMN数字012345678910111213英文OPQRSTUVWXYZ数字141516171819202122232425 脱密变换 其中n mod26 读作n模26 它是整数n被26除后所余的非负整数 后来统称所有自然序密表为凯撒密表 加密变换 脱密变换 其中 在这里英文字母A Z对应0 25的整数 密钥一旦取定 就确定一个代替表 密钥所有可能的取法为26 即凯撒密码的密钥量为26 3 仿射凯撒密表 加密变换 脱密变换 仿射凯撒密表的密钥变化量为 26 26 26 12 312 例 用凯撒密码加密得到的密文为 phhwphdiwhuwkhwrjdsduwb能求出原明文吗 已知条件 1 加密 解密算法是已知的 2 需尝试的密钥仅有25个 3 明文的语言是已知的且很容易识别 该密码的破译对我们有什么启示 如何改进 用穷尽法易得明文为 meetmeafterthetogaparty 加密实际上是对明文的一种变换 而明文通常是自然语言 自然语言有其固有的语法规则 从而存在明显的统计特性 频率规律 和跟随关系 所谓相关性 应当清醒地意识到 常用的高频字或高频短语的出现概率要显著高于其它的字母组合 这些模式字或模式短语为密码分析者使用猜字法提供了基础 需要强调的是 统计量越大 上述规律表现得就越明显 仅仅对少许几个单词进行统计是没有什么效果的 由于单码单表代替密码是以单码为单位进行代替的 因而明文的单码 双码 三码 高频字等统计规律 结合规律和格式规律都完全泄漏在密文之中 通过分析密文的这些规律就可确定出所使用的代替表 单表代替的缺点 1 明文字符相同 则密文字符相同 2 密文字符的频次 就是明文字符出现的频次 3 明文字符之间的跟随特性反映在密文中 因此 明文字符的统计规律就完全暴露在密文字符的统计规律之中 形态变但位置不变 单表代替的优缺点单表代替的优点 明文得到了掩蔽 因此在进行加密变换时 如何将明文的统计特性很好的隐蔽起来 是首先要考虑的问题 由于明文字母频率分布很不均匀 对明文进行加密变换后应使各字母的频率趋向于均匀分布 就是说加密变换后得到的密文符号应该是均匀分布的 从而隐蔽统计规律 采用多表代替可隐藏明文的统计规律 代替表越多 越大 效果越好 但实现起来很困难 现代密码算法一般采用小规模的代替多次加密以实现上述效果 二 多表代替 两行代替密码的编制方法为在大简便的基础上增加一个密行 加密时按约定的方法交替使用两密行 以增加密码强度 多表代替是使用两个或两个以上的代替表按约定方法对明文字母进行代替的加密方法 1 两行代替 加密时约定每组的第一 二单码用第一密行加密 第三 四单码用第二密行加密 明文为 01013377888845243333 密文为 13342299000056572266 当密行可重时密钥变化量为 10 10 密行不能重复时密钥变化量为 10 10 1 例如 2 维吉尼亚密码 1858年 法国人Vigenere提出 加密变换 脱密变换 维吉尼亚密码使用长度为的密钥 加密时先对明文进行分组 对每一组明文用同一组密钥加密得密文 维吉尼亚密码相当于行代替 每一密行是一个自然序代替表 用第一密行加密第一明文 第二密行加密第二明文 依此类推 第密行加密第明文 当明文长度超过时则重用密钥 维几利亚密码的代替表为 明文字母 密钥字母 密钥字母为d 明文字母为m时 查表得密文字母为p 假设维吉尼亚密码使用密钥为 K BAND明文为M RENAISSANCE RENA ISSA NCE 加密后可得密文C SEADJSFDOCR 三 无限代替 无限代替是指一次一密无限密钥指示的代替 由于在这种情况下密钥编制不规则 使用不重复 即相当于客观无周期地使用代替表 完全克服了固定代替的弱点 可以做到每发一个明文字母换一张代替表 注 代替密码与易位密码不同 易位密码只改变明文元素的位置 而代替密码则是对明文元素进行替代 结论 存在安全的多表代替密码 不存在安全的移位密码 将代替密码和移位密码轮番使用 必然可以发挥各自的长处 克服对方的缺点 必然可以设计出安全的密码体制 这就是分组密码的代替 移位模型 这就是现代密码的设计思想 例1破译以下密文 ykhlbajczsvijjzbtzvhijczvhjdrizxkhlbavssrdheidryvjvlbxskylbaylaljvsifzzxccvilefhdnzyevbtrdsyjczfhlevhthzvidbrdhjclicviwzzbjczvynzbjdrelxhdzszxjhdblxijczxdefszqljtdrjczrkbxjldbijcvjxvbbdpwzfzhrdhezywtjczevxclbzcvihlizbyhvevjlxvsstvivhziksjdrjclihzxzbjyznzsdfezbjlbjzxcbdsdatevbtdrjczxlfczhitijzeijcvjpzhzdbxzxdbilyzhzyizxkhzvhzbdpwhzvmvwsz 这份密文共含有338个字母 Duringthelasttowyearstheartofsecuringallformsofdataincludingdigitalspeechhasimprovedmanyfoldtheprimaryreasonforthishasbeentheadventofmicroeletronicsthecomplexityofthefunctionsthatcannowbeperformedbythemachinehasrisendramaticallyasaresultofthisrecentdevelopmentintechnologymanyoftheciphersystemthatwereonceconsideredsecurearenowbreakable 练习 已