上海交大密码学课件--第三讲古典替换密码.ppt

第三讲 古典替换密码 Classical substitution ciphers,上海交通大学 Tel:zheng dong,1.古典加密技术,两个基本组成部分： 替换与置换 (substitution and transposition),2. 恺撒密码Caesar Cipher,Caesar 密码的数学表示 设： A the value 0, B 1, C 2, . Y 24, Z 25; 加密算法： Ek: i - i + k (mod 26) 解密算法： Dk: i - i - k (mod 26),3.密码分析（Cryptanalysis of Caesar ciphers）,只有 26 种可能（only have 26 possible ciphers ） A maps to A,B,Z 可以简单的实验每个密钥（穷密钥搜索） 给定一些密文，实验每个密钥。 LIZHZLVKWRUHSODFHOHWWHUV Original ciphertext KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 IFWEWISHTOREPLACELETTERS try shift of 3 * plaintext HEVDVHRGSNQDOKZBDKDSSDQR try shift of 4 GDUCUGQFRMPCNJYACJCRRCPQ try shift of 5 . MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 eg. break ciphertext “GCUA VQ DTGCM“,4.语言冗余度与密码分析,人类语言是有冗余度的 字母使用的频率是不相同的 在英语中，e 的使用率是最高的 其次，T,R,N,I,O,A,S 其它字母使用的较低,5. 英语字母使用频率,6。字母频率在密码分析中的应用,计算密文中字母出现的频率 与已知字母分布比较 单码替换不改变相对字母出现的频率 阿拉伯科学家提出此方法,7.英语字母中常见的组合,8。打乱的密码代换,不仅仅是简单的移位变换 每个字母可以避免随意变换到其它不重复的字母 每个字母变换到不同的字母 密钥长度是26个字母 eg. Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: IFWEWISHTOREPLACELETTERS Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA,9。打乱的密码代换的安全性,密钥总数：26！ 如此多的密钥，可以认为安全吗？ !NO! 仍然有语言统计规律 需要其它方法隐藏这种规律性,10. 一般单码替换密码,简单的方法给出密钥 写出密钥（删除重复字母）write key (with repeated letters deleted) 在其下面依次写出剩余字母（以横、纵行） 按列读取字母得到密文。then read off by columns to get ciphertext equivalents,11. 一般单码替换密码 举例,给定密钥字 “STARWARS“ 去掉重复字母得到 “STARW“ 填写剩余字母： STARW BCDEF GHIJK LMNOP QUVXY Z 按列读取字母得到密文 Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: SBGLQZTCHMUADINVREJOXWFKPY 可以用这个密钥加密、解密 例如 Plaintext: I KNOW ONLY THAT I KNOW NOTHING Ciphertext: H UINF NIAP OCSO H UINF INOCHIT,12. 一般单码替换密码 的密码分析,根据频率统计进行分析 确定每个字母被映射到什么字母 如果知道单词之间的间隙知道,则破译会很容易. 单个字母出现的可能是A或I 一般来说个字母出现的可能是THE或AND 还可以用其他通常出现的双字母或三字母组合) 还可以应用其它很少应用的字母,12.一般单码替换密码 的密码分析（续）,甚至能够恢复出关键字 关键字总是使得其它字母连续出现 分析密钥排列的“宽度” eg. in the above example, if have recovered the mapping: Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: SBGLQZTCHMUADINVREJOXWFKPY * * * * * see pattern “BCDEF“ and “LMNOP“ 你能够重新构造替换表, 并恢复出 keyword “STARW“,13.信息论与熵,C.E. Shannon （香农）, 1948, A mathematical theory of communication. 确立了现代信息论。 1949, Communication theory of secrecy systems. 定义了密码系统的精确数学模型。,13.2熵 entropy,熵（Entropy，定义为事件集X中事件出现 的信息的统计平均值 它表示X中出现一个事件平均给出的信息量， 或事件的平均不确定性,Exercises,encrypt and then decrypt by hand, the text below using a general monoalphabetic cipher with a key of “NIFTY“: the cat only grinned when it saw alice it looked good