《古典替换密码.ppt》由会员分享，可在线阅读，更多相关《古典替换密码.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三讲 古典替换密码 Classical substitution ciphers上海交通大学计算机科学与工程系Zheng-Tel:021-62932135 zheng dong1.古典加密技术n两个基本组成部分：替换与置换 (substitution and transposition)2.恺撒密码恺撒密码Caesar CiphernCaesar 密码的数学表示 设：A the value 0,B 1,C 2,.Y 24,Z 25;n加密算法：Ek:i-i+k(mod 26)n解密算法：Dk:i-i-k(mod 26)3.密码分析（Cryptanalysis of Caesar cipher
2、s）n只有 26 种可能（only have 26 possible ciphers）nA maps to A,B,.Z n可以简单的实验每个密钥（穷密钥搜索）n给定一些密文，实验每个密钥。LIZHZLVKWRUHSODFHOHWWHUV Original ciphertext KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 IFWEWISHTOREPLACELETTERS try shift of 3*plaintext HEVDVHRGSNQDOKZBDKDSSDQR try s
3、hift of 4 GDUCUGQFRMPCNJYACJCRRCPQ try shift of 5.MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 neg.break ciphertext GCUA VQ DTGCM 4.语言冗余度与密码分析n人类语言是有冗余度的n字母使用的频率是不相同的n在英语中，e 的使用率是最高的n其次，T,R,N,I,O,A,S n其它字母使用的较低5.英语字母使用频率6。字母频率在密码分析中的应用n计算密文中字母出现的频率n与已知字母分布比较n单码替换不改变相对字母出现的频率n阿拉伯科学家提出此方法7.英语字母中常见的组合8。打乱的
4、密码代换n不仅仅是简单的移位变换n每个字母可以避免随意变换到其它不重复的字母n每个字母变换到不同的字母 n密钥长度是26个字母 neg.Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher:DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext:IFWEWISHTOREPLACELETTERS Ciphertext:WIRFRWAJUHYFTSDVFSFUUFYA 9。打乱的密码代换的安全性n密钥总数：26！n如此多的密钥，可以认为安全吗？n!NO!n仍然有语言统计规律n 需要其它方法隐藏这种规律性n 10.一般单码替换密码n简单的方法给出密钥n写出
5、密钥（删除重复字母）write key(with repeated letters deleted)n在其下面依次写出剩余字母（以横、纵行）n按列读取字母得到密文。then read off by columns to get ciphertext equivalents 11.一般单码替换密码 举例n给定密钥字 STARWARS n去掉重复字母得到 STARW n填写剩余字母：STARW BCDEF GHIJK LMNOP QUVXY Z n按列读取字母得到密文 nPlain:ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher:SBGLQZTCHMUADINVREJOXWFK
6、PY n可以用这个密钥加密、解密n 例如 Plaintext:I KNOW ONLY THAT I KNOW NOTHING n Ciphertext:H UINF NIAP OCSO H UINF INOCHIT n 12.一般单码替换密码 的密码分析n根据频率统计进行分析 n确定每个字母被映射到什么字母n如果知道单词之间的间隙知道,则破译会很容易.n单个字母出现的可能是A或In一般来说个字母出现的可能是THE或ANDn还可以用其他通常出现的双字母或三字母组合)n还可以应用其它很少应用的字母12.一般单码替换密码 的密码分析（续）n甚至能够恢复出关键字n关键字总是使得其它字母连续出现 n分析
7、密钥排列的“宽度”neg.in the above example,if have recovered the mapping:n Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZ nCipher:SBGLQZTCHMUADINVREJOXWFKPYn *nsee pattern BCDEF and LMNOP n你能够重新构造替换表,n并恢复出 keyword STARW 13.信息论与熵C.E.Shannon（香农）,1948,A mathematical theory of communication.确立了现代信息论。1949,Communication theory
8、of secrecy systems.定义了密码系统的精确数学模型。13.2熵 entropyn熵（Entropy，定义为事件集X中事件出现的信息的统计平均值它表示它表示X中出现一个事件平均给出的信息量，中出现一个事件平均给出的信息量，或事件的平均不确定性或事件的平均不确定性Exercises nencrypt 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 natured she thought still it had very long claws and a great many teeth so she felt that it ought to be treated with respect n OK!