现代密码学第2章：经典密码学概要.ppt

经典密码学 本章主要内容 1、密码体制的定义与分类 2、代替密码与移位密码 3、变换密码 4、乘积密码 5、密码机的发展历史 简单密码举例 密码学的历史已有4000多年 古埃及人曾把象形文字写在石碑上 简单密码举例 练习 解密 RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV OMNIA GALLIA EST DIVISA IN PARTES TRES 恺撒密码的一般形式 一般形式，可以把Caesar cipher 中字母移动的位数由3变为1-25中的任何一个。 可以指定一个密钥字母作为字母A的密文。 例如：密钥字母F表示： A F, B — G, ... Y — D, Z — E 即每个字母移动5位 共有26种可能的密码算法（25种可用） Caesar密码分析（Cryptanalysis of Caesar ciphers） 只有 26 种可能（only have 26 possible ciphers ） A maps to A,B,..Z 可以简单的实验每个密钥（穷密钥搜索） 给定一些密文，实验每个密钥。 Original ciphertext LIZHZLVKWRUHSODFHOHWWHUV try shift of 1 KHYGYKUJVQTGRNCEGNGVVGTU try shift of 2 JGXFXJTIUPSFQMBDFMFUUFST try shift of 3 IFWEWISHTOREPLACELETTERS *** plaintext HEVDVHRGSNQDOKZBDKDSSDQR try shift of 4 GDUCUGQFRMPCNJYACJCRRCPQ try shift of 5 ..... MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 eg. break ciphertext GCUA VQ DTGCM 语言冗余度与密码分析 人类语言是有冗余度的 字母使用的频率是不相同的 在英语中，e 的使用率是最高的 其次，T,R,N,I,O,A,S 其它字母使用的较低 英语字母使用频率 字母频率在密码分析中的应用 计算密文中字母出现的频率 与已知字母分布比较 单码替换不改变相对字母出现的频率 阿拉伯科学家提出此方法 英语字母中常见的组合 单表代替密码 每个字母可以用其它任何一个字母替换（不能重复） 每个字母可以随机的映射到其它一个 因此密钥长度是26个字母 单字母替换密码（ Monoalphabetic Substitution Cipher ） 例如： 明文: ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: IFWEWISHTOREPLACELETTERS Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA 单表代替密码举例 给定密钥字 “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 单表代替密码 需要一种简单方法指定密钥。 有多种方法，一种简单方法是写没有重复字母的“密钥字”，其它字母按顺序写在密钥字最后字母后面。 例如， 给定密钥字 JULIUSCAESAR Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: JULISCASRTVWXYZBDFGHKMNOPQ 单表代替密码的密码分析 根据频率统计进行分析，确定每个字母被映射到什么字母，单个字母出现的可能是A或I（since know single words are A or I ） 一般来说个字母出现的可能是THE或AND，还可以用其他通常出现的双字母或三字母组合。 还可以应用其它很少应用的字母 Blaise de Vigen