第二讲：密码学与计算机安全 -----密码学历史 第二讲：密码学与计算机安全 -----密码学历史

1.古典密码 密码学的历史已有4000多年 古埃及人曾把象形文字写在石碑上

2.Caesar Cipher-恺撒密码 2千年前，Julius Ceasar 使用了一种简单的替换密码- ——后被人称为恺撒密码（Caesar cipher ） 首先被应用于军事上 (cf Gallic Wars) 替换方法，每个字母用其后的第三个字母替换 eg. L FDPH L VDZ L FRQTXHUHG -> I CAME I SAW I CONQUERED Caesar cipher 可以描述如下： Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: DEFGHIJKLMNOPQRSTUVWXYZABC 练习 解密 "RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV"

3.恺撒密码的一般形式 一般形式，可以把Caesar cipher 中字母移动的位数由3变为1-25中的任何一个 例如：密钥字母F表示： A F, B — G, ... Y — D, Z — E 即每个字母移动5位 共有26种可能的密码算法（25种可用）

4.混合单码替换密码 不仅仅是移位变换 每个字母可以用其它任何一个字母替换（不能重复） 每个字母可以随机的映射到其它一个 因此密钥长度是26个字母 单字母替换密码（ Monoalphabetic Substitution Cipher ） 例如： 明文: ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: IFWEWISHTOREPLACELETTERS Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA

5.简单的单码替换密码 the Mixed Monoalphabetic Cipher has a 26 letter key 需要一种简单方法指定密钥 有多种方法，一种简单方法是写没有重复字母的“密钥字”，其它字母按顺序写在密钥字最后字母后面 例如， 给定密钥字 "JULIUSCAESAR" Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: JULISCASRTVWXYZBDFGHKMNOPQ

6.单码替换密码历史 不同种类的替换密码用在政府和军事上 频率攻击方法由阿拉伯科学家提出 "A Manuscript on Deciphering Cryptographic Messages", published in the 9th century stronger monoalphabetic ciphers with several replacement symbols for each letter, for common words, and nulls were developed in middle ages eventually all were susceptible to analysis cf. execution of Mary Queen of Scots, Great Cipher of Louis XIV

8. Vigenère Cipher Blaise de Vigenère 发明了多字母替换密码（polyalphabetic substitution cipher） 使用多个单字母替换表 因此一个字母可以被多个字母替换 方法，用一个密钥选择对每个字母使用哪个字母表 密钥的第I个字母表示使用第 ith 个字母表 依次使用每个字母表 当密钥的字母使用完后，在从头开始

9. Vigenère Example 例： 写出明文 在明文下重复写出密钥字 依次使用每个字母作为caesar cipher 的密钥 加密对应的明文字母 Plaintext THISPROCESSCANALSOBEEXPRESSED Keyword CIPHERCIPHERCIPHERCIPHERCIPHE Plaintext VPXZTIQKTZWTCVPSWFDMTETIGAHLH

9.1 Vigenère Example （续） C -> CDEFGHIJKLMNOPQRSTUVWXYZAB I -> IJKLMNOPQRSTUVWXYZABCDEFGH P -> PQRSTUVWXYZABCDEFGHIJKLMNO H -> HIJKLMNOPQRSTUVWXYZABCDEFG E -> EFGHIJKLMNOPQRSTUVWXYZABCD R -> RSTUVWXYZABCDEFGHIJKLMNOPQ ABCDEFGHIJKLMNOPQRSTUVWXYZ to map the above plaintext letters. ‘ T' uses key 'C' maps to 'V' ‘ H' uses key 'I' maps to 'P' ‘ I' ises key 'P' maps to 'X' etc

10. History of the Vigenère Cipher 可以看出，越安全的密码使用起来越复杂 因此，在有些场合还可以看到单码替换密码 随着破译单码密码的技术提高， 使得vigenère cipher 逐渐被各国使用 1854年，首次被 Charles Babbage 攻破，但没有公开 Friedrich Kasiski 与1863年攻破并发表了 此密码的各种变形被沿用到20世纪 cf. the Zimmermann telegram in WW1

11. Ciphers Machines 1--1 为了简化加密/解密过程，导致密码设备出现 Jefferson cylinder, 1790s被研制成功，包含36个 圆盘，每个圆盘有个随机字母表 1920年还被美国军队使用

11. Ciphers Machines 1--2 Wheatstone disc, by Wadsworth in 1817, and Wheatstone in 1860's, comprised two concentric wheels to generate a polyalphabetic cipher

12. Ciphers Machines 2 随着密码技术的提高，要求有更高级的密码装置 高级密码装置可以实现更复杂的密码 这些装置在二战时期广泛使用 例： the German Enigma, the Swedish Hagelin (below) and the Japanese Purple

13.Computers and Cryptography 现代电子系统与计算机能够实现更复杂的密码系统 70年代中期, 首次出现了现代分组密码—DES 70年代末, 公钥密码学问世 直到今天,我们使用的密码学系统

15. 小结（Summary） 主要讨论了密码学历史 密码设计与密码分析之间的联系 介绍了恺撒密码caesar与vigenère ciphers 参考文献：《密码传奇-从军事隐语到电子芯片》 上海译文出版社