2.2 密码学的历史

密码是一项有着久远历史的技术，它伴随着战争的出现而出现，古代的密写术或隐蔽书写是它的起源。虽然这一技术由来已久，但在20世纪60年代之前，密码还仅仅是政府机关和军事部门的专利。20世纪70年代以后，计算机科学和技术的发展促使密码学从外交和军事领域走向公开，开始应用于银行等商业部门，形成为一门新的学科。在计算机网络深入普及的今天，密码学成为了一个非常活跃的研究热点，研究密码算法的数家公司都因为互联网的发展而身价倍增。

密码学的发展可以划分为三个阶段：

第一阶段为1949年之前，这一时期的密码学还不是科学，可以说是一门艺术，出现了一些密码算法和加密设备。加密算法属于古典密码，密码算法的基本手段是针对字符的代替（Substitution）和置换（Permutation），也出现了一些简单的密码分析手段。

公元前1900年，在古埃及，象形文字已经发明，并得到普遍使用，为克努姆霍特普二世撰写碑文的祭司别出心裁，用了一些奇怪的象形符号来代替通常所用的象形文字，这种对标准书写符号的修改是手写密码第一次有记载的使用情况，图2.3是古埃及的原始密码。这个例子蕴涵了一个密码变换的基本思想：代替，一种符号（明文）用另一种符号（密文）代替。

公元前487年，斯巴达人发明了Spartan Scytale，它是斯巴达人用于加解密的一种军事设备，发送者把一条羊皮螺旋形地缠在一个圆柱形棒上。消息沿着棒子的长度方向从左至右书写，写完一行，旋转木棒，再从左至右书写，直至写完，然后把羊皮带从木棒上解下展开。解密过程就是把羊皮条缠绕在相同直径的木棒上，便可以读出明文。这个例子蕴涵了密码变换的另一个基本思想：置换，按一定规则把明文中的字符变换一个位置，重新排列。假设明文是：start attack at eleven，去掉空格，按行书写，每行至多写五个字符，如下表所示：

当羊皮带解开后，读到的密文为：sakettavatteraentcl。

第二阶段为1949年至1975年，这一时期，计算机使得基于复杂计算的密码成为可能，数据的安全基于密钥而不是算法的保密。1949年Shannon发表了“保密系统的通信理论”（The Communication Theory of Secret Systems），该文首先将信息论引入了密码，利用数学方法对信息源、密钥源、接收和截获的密文进行了数学描述和定量分析，提出了通用的秘密钥密码体制模型，奠定了密码学的理论基础，从此密码学成为一门科学。这一时期的一些重要事件有：1967年David Kahn出版了一本专著《破译者》（The Codebreakers），该书记载了1967年之前密码学发展的历史，使许多不知道密码学的人了解了密码学。1971年至1973年IBM Watson实验室的Horst Feistel和他的同事们发表了几篇技术报告，这些报告是DES算法提出的基础。

第三个阶段为1976年以后，1976年Diffie和Hellman在“密码学的新方向”（New Directions in Cryptography）一文中，提出了不对称密钥密码的思想，首次证明发送端和接收端无密钥传输的保密通信是可能的，但他们在这篇文章中并没有提出一个真正实用的算法，直到1977年，Rivest，Shamir和Adleman才提出了RSA公钥算法，这是第一个真正实用的公钥密码体制。该算法的三个人因此获得了计算机界的诺贝尔奖——图灵奖。1990年后逐步出现椭圆曲线等其他公钥算法。同一时期，对称密钥密码算法也获得了进一步的发展，1977年DES正式成为数据加密标准，该算法采用完全公开的加密、解密体制，并批准用于非机密单位和商业上的保密通信，此举使得密码学在商业等民用领域得到广泛应用。随后出现了一些分组加密算法，如IDEA，RCx，CAST等。20世纪90年代对称密钥密码进一步成熟，出现了Rijndael，RC6，MARS，Twofish，Serpent等算法，2001年Rijndael成为高级数据加密标准AES，取代已经变得越来越不安全的DES。

现代密码学的另一个重要标志是基于计算复杂性理论的密码算法安全性证明。姚期智教授因为在保密通信计算复杂性理论上的重大贡献获得了图灵奖。在密码分析领域，王小云教授对经典散列算法MD5、SHA-1等的破解也是近年密码学的重大进展。