3、第三讲 古典密码.ppt

计算机安全保密第三讲古典密码 wzy 武汉大学 计算机学院 2 古典密码 虽然用近代密码学的观点来看 许多古典密码是很不安全的 或者说是极易破译的 但是我们不能忘记古典密码在历史上发挥的巨大作用 另外 编制古典密码的基本方法对于编制近代密码仍然有效 3 第三讲古典密码 换位法替代法 4 置换密码 把明文中的字母重新排列 字母本身不变 但其位置改变了 这样编成的密码称为置换密码 最简单的置换密码是把明文中的字母顺序倒过来 然后截成固定长度的字母组作为密文 明文 明晨5点发动反攻 MINGCHENWUDIANFADONGFANGONG密文 GNOGNAFGNODAFNAIDUWNEHCGNIM 5 例如 明文 MINGCHENWUDIANFADONGFANGONG矩阵 MINGCH选出顺序 按列ENWUDIANFADO改变矩阵大小和取出序列NGFANG可得到不同的密码ONG密文 MEANOINNGNNWFFGGUAACDDNHIOG 把明文按某一顺序排成一个矩阵 然后按另一顺序选出矩阵中的字母以形成密文 最后截成固定长度的字母组作为密文 6 古典密码 换位法思路打乱明文中各字母的顺序 使明文中的单词错乱 隐蔽其含义 7 古典密码 换位法方法加密时 将明文的字符 一维数据 按照一定顺序放入高维空间 一维以上 中 然后按照另一种顺序取出字符 形成密文 一维数据 解密时 先将密文按照相应顺序放入高维空间中 再按照原始顺序取出明文 8 古典密码 换位法举例明文 M INTELLIGENT放入3 4的矩阵 9 古典密码 换位法加密方法整体加密 取列向量密文为Ek M ILENLNTITEG按行加密 取列顺序2413密文为Ek M NEITLGLINET 10 古典密码 双轨密码 1861 1865年明文 DiscreteAndSystem加密 DsrtAdytmiceenSse密文 DsrtAdytmiceenSse 11 理论上 置换密码的加密钥是置换矩阵p 解密钥是置换矩阵p 1 置换密码经不起已知明文攻击 123 na1a2a3 an P 12 习题 已知换位密码的换位表为 2 7 5 3 8 4 6 1 试对明文software加密 答案 13 习题 已知换位密码的换位表为 2 7 5 3 8 4 6 1 试对明文software加密 答案 orwfetas 14 古典密码 换位法算法特点 易于手工操作 明密文都是字符串且等长算法缺陷 明文密文中的各字母出现次数是相同的 只是位置不同 密码分析员可以通过移动字母顺序进行破译 15 古典密码 替代法简单替代多表替代同音替代组合替代 16 替代法 简单替代思路将明文中字母按照一定规律替换成其他字母 隐蔽其含义方法设定规则 将明文中的字母x替换成字母f x 17 替代法 简单替代举例设密钥为k 加密规则是f x x k mod26当k 3时明文M FIGHTATNIGHT 被加密成密文Ek M ILJKWDWQLJKWC语言的实现方式c a A k 26 A 选择具有自反特点的加密函数f a k a mod26 18 替代法 简单替代特点易于手工操作 明密文都是字符串且等长 明文中的字母在密文中都以其他字母所取代缺陷明文字母的出现次数与相应密文字母的出现次数是相同的 因而明文中的字母统计特性在密文中也存在 容易被攻击 例如 明文中字母e出现得最多 而加密后字母h出现得最多 19 替代法 多表替代思路采用多个代替密钥交替加密明文 以减弱频率特性 20 替代法 多表替代Vigenere密码设明文字母为a 当前密钥字母为ki 则密文字母为fi a a ki mod26举例 21 替代法 多表替代举例设明文M INTELLIGENT密钥k PLAYPLAYPLA密文Ek M XYTCAMIETYT 22 23 例 用Vigenere密码加密明文 intrusiondetection 密钥为NEU 答案 vrneymvshqinrgnvshM intrusiondetectionK neuneuneuneuneuneuC vrneymvshqinrgnvsh 24 替代法 多表替代特点明文字母周期性地被不同的密钥字母加密缺陷被相同密钥字母加密的密文仍然具有频率统计特性 一旦密码分析员猜对了密码长度后 容易在密文中发现频率统计特性 然后分别对每个密钥字母破译 25 替代法 多表替代攻击思路 首先猜测密钥长度 即加密周期 再分别破译各密钥字母猜测周期的方法重合度 indexofcoincidence 粗糙度 measureofroughness 26 替代法 游动密钥密码思路采用很长的 不重复的密钥加密明文 避免密钥周期方法利用诸如字典 圣经等 又长又不重复的文本作为密钥 采用多表替换加密明文 27 替代法 同音代替密码思路对于出现频率较高的明文字母采用多个不同的密文表示 以消除密文中的频率统计特性方法根据明文字母表中各字母的一般出现概率 为每个明文字母分配一定数量的不重复的随机数 加密时从中随机选取一个作为密文 28 替代法 同音代替密码举例设加密矩阵为 29 替代法 同音代替密码举例设明文M PLAINPILOT则加密的结果可能为 C 91445665593308762878 30 替代法 同音代替密码特点单字母频率特性在密文中被消除 不易破译缺陷多字母频率特性仍不能完全消除 31 替代法 组合替代思路 一次替代明文中的多个字母特点 一定程度上消除字母频率统计特性明文字母之间产生了相关性 其基本思想被应用于后面将详细讲述的对称分组密码 32 代数密码 Vernam密码明文 密文 密钥都表示为二进制位 M m1 m2 mnK k1 k2 knC c1 c2 cn 加密 c1 mi ki i 1 2 n解密 m1 ci ki i 1 2 n 因为加解密算法是模2加 所以称为代数密码 对合运算 f f 1 模2加运算是对合运算 密码算法是对和运算 则加密算法 解密算法 工程实现工作量减半 Vernam密码经不起已知明文攻击 33 Vernam密码与一次一密密码 Vernam密码 加密 ci mi kimod2解密 mi ci kimod2例 11000 10010 01010一次一密 密钥为一个随机且不重复的字符序列 34 代数密码 如果密钥序列有重复 则Vernam密码是不安全的 一种极端情况 一次一密 密钥是随机序列 密钥至少和明文一样长 一个密钥只用一次 一次一密是绝对不可破译的 但它是不实用的 一次一密给密码设计指出一个方向 人们用序列密码逼近一次一密 35 古典密码的穷举分析 单表代替密码分析 加法密码因为f ai bi ajj i kmodn所以k 1 2 n 1 共n 1种可能 密钥空间太小 以英文为例 只有25种密钥 经不起穷举攻击 36 古典密码的穷举分析 单表代替密码分析密钥词语代替密码因为密钥词语的选取是随机的 所以密文字母表完全可能穷尽明文字母表的全排列 以英文字母表为例 n 26 所以共有26 种可能的密文字母表 26 4 1026用计算机也不可能穷举攻击 注意 穷举不是攻击密钥词语代替密码的唯一方法 37 古典密码的统计分析 密钥词组单表代替密码的统计分析任何自然语言都有自己的统计规律 如果密文中保留了明文的统计特征 就可用统计方法攻击密码 由于单表代替密码只使用一个密文字母表 一个明文字母固定的用一个密文字母来代替 所以密文的统计规律与明文相同 因此 单表代替密码可用统计分析攻破 38 单字母频率分布图 39 古典密码的统计分析 英语的统计规律每个单字母出现的频率稳定 最高频率字母E次高频率字母TAOINSHR中高频率字母DL低频率字母CUMWFGYPB最低频率字母VKJXQZ 40 古典密码的统计分析 英语的统计规律频率最高的双字母组 THHEINERANREEDONESSTENATTONTHANDOUEANGASORTIISETITARTESEHIOF 41 古典密码的统计分析 英语的统计规律频率最高的三字母组 THEING