浅谈密码学的历史发展过程

前言
这是大三下学期选学的网络信息安全课程的期末作业，这个学期就是疫情爆发期间上网课的那段时期。。。

摘要

密码对我们都不陌生，在日常生活中也接触过密码，日常生活中所说的密码，通常是是登录界面的那种输入密码，银行卡密码等等之类的。这样的密码在密码学里更严格的意义上是称为 password、pin，中文上称为口令。我们通常想到的是把密码这些关键信息藏起来，用什么形式？用藏头诗的形式？用隐形墨水写一下，到时候火烧显示出来？这就是想当然的一种形式。那在互联网中我们又该怎么保密呢？密码学指的是什么呢？这里引用维基百科上的解释：Cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. 由此可以看出密码学是一套防止隐私泄露的体系，它可以达到的效果就是，即使你拿到了密码这个数据，你也看不懂。那密码学这一套体系又是怎么出现的呢？我们用的比较多的加密解密算法都有哪些呢？本文就密码学的发展历史来简述一下密码学里较常见的算法。

关键词：凯撒密码，单表替换密码，多表替换密码，机器密码，对称加密，非对称加密，哈希函数，消息认证码，认证中心，数字签名

一、密码学的分类 4

二、古典密码学： 4

（一）凯撒密码 4

（二）单表替换密码 4

穷举所有可能性。 5
用频率分析。 5

（三）多表替换密码 6

（四）Enigma 7

三：现代密码学 7

（一）对机密性的解决方法 8

1.1 对称加密 8

1.2 One-Time pad 9

2 . 非对称密码 10

混合加密 10

（二）对保证保证完整性的解决方法 11

哈希函数 11

2 .消息认证码 12

（三）针对否认的解决方法 13

（四）针对伪装的解决方法 14

四：总结 15

一、密码学的分类
纵观密码学的发展，感觉就像是创造加密算法的人和破解加密算法的人之间的一场博弈。密码学可以分为古典密码学和现代密码学。古典密码学研究的主要就是怎么让密码这个数据不泄露，不被破译。而现代密码学，除了研究密码信息的保密问题，还要考虑其他很多方面的安全隐患，比如窃听、篡改、伪装、否认。

二、古典密码学：
古典密码学主要解决的问题就是：我们想要发送的信息，不想要第三方知道，对这个信息进行加密。以下就介绍以下常见的加密算法。
（一）凯撒密码
主要思想就是按字母表往后平移n个字母，这个n值一般取3。

图 1 凯撒密码示意图

破解的话，全部可能性试一遍就可以，往后平移最多也就 26 种可能的情况。

（二）单表替换密码
可以看成凯撒密码的加强版，这个往后平移替换的过程没有规律可言，一个明文字母，对应着一个密文字母。

图 2 单表替换密码示意图

破解：
1.穷举所有可能性。
a对应着 26种可能，b对应着25种可能，c对应着24种可能，列出所有的可能。所有，最后总共由 26! 种可能。这个时间复杂度算比较高的了，这么破解也很麻烦。

2.用频率分析。
频率分析是在9世纪时，阿拉伯博学家－肯迪在其所著的《手稿上破译加密消息》中提出的。它对于***的文本研究发现阿拉伯文有一个特别的字母频率。主要说明在一篇文章中，每个字母出现的频率不是均等的。比如，字母E出现的频率很高，而X则出现得较少。类似地，ST、NG、TH，以及QU等双字母组合出现的频率非常高，NZ、QJ组合则极少。
基于此，单表替换密码的破译就会轻松很多。

图 3 频率分析示意图

（三）多表替换密码
再往后发展，单表替换密码可以很容易被破解出来。一个表不行了，就催生发展了多表替换密码。也叫维吉尼亚密码。该加密方法需要一个索引，这个索引就类似于我们平常所说的口令[ 就是我们平常所说的“密码”，在摘要部分有提到。]。索引要比原文短，用的时候复制到和原文一样长的就可以。

图 4 多表替换密码示意图

这样就有一个现象。（可以用上图的例子对照着看一下）。
因为索引不一样，
可能原来明文是一样的字母，可是替换之后的密文字母是不一样的。
替换之后密文字母是一样的，可能原来的明文并不是一样的字母。
基于这个现象，频率分析就失效了。

破解：
步骤1：看密文，看2一样的字母，要相隔一段距离。他们对应的明文和索引可能是一样的。不是确定，只是说可能性比较大。
步骤2：根据这个特点，猜索引的长度，然后把明文划分成一段一段的，和索引等长。
步骤3：这样我们就能对索引里的每个字母人为地确定一个，就可以用频率分析了。

（四）Enigma
再之后，就有划时代意义的密码出现了。那就是Enigma，是一种使用机器加密解密的密码，在二战时期，德国就是使用这样的技术。当时德国人认为，这是一种不可破解的密码。

工作原理：
和具体的机器构造细节有关。2方都需要有 Enigma 机器，还有他们之间通信的密码。（就是战争时叫的密码本）

破解：
1.波兰人雷耶夫斯基，先提出了一种方法，这种方法叫 bomba，中文可以翻译成波兰的炸弹机。
思想：主要用数学中的群论理论。主要思路就是用一些简单的弱口令，进行尝试破解。（猜一些弱口令，比如123456什么的），甚至把这些常见的弱口令都记在一个本子上。

2.英国人图灵，创造了破解的机器，起名叫bomba，致敬 bombe，中文可以翻译成英国的炸弹机。
思想：对方用机器工作，我也用机器工作，用机器来对抗机器。是一种通用的破解方法。也是枚举方法，但是这个机器可以减少很多不必要的可能性。
有声音说，Enigma的破解，至少使二战提前2年时间结束。

三：现代密码学
主要关注信息安全所面临的威胁，针对这些威胁提出加解密算法。保密不应该是这些算法，而是这些算法所要使用到的密钥。

图 5 现代密码学的整体面貌

（一）对机密性的解决方法
主要思路：窃听只能窃听到密文，不知道密钥也是看不懂。。
1.1 对称加密
密钥的特征：是一个比原文短的“索引”（加注释），用短的来加密长的。
所以现在的问题就是怎么在传输的时候保证这个索引不被窃听。这也叫Key distribution problem，密钥分发问题。

图 6 对称加密示意图

代表性的对称加密算法： DES、AES（常用）、Blowfish、Twofish。
AES-128：密钥是 128个bit。
AES-256：密钥是 256个bit。

加密的方式，对 AES-128来举例：一种很容易想到的实现方式（这样实现不好）。
思路：密钥是 128 位，明文对应也要划分成 128 的片段，对每个片段进行加密，再将密文拼接起来。
漏洞：如果划分的明文段是一样的，那么加密后出来的密文也是一样的。
那么这样第三方就可能猜出来明文，或者篡改这些相同的密文。

现实中比较常用的一种加密方式：
CBC（Cipher Block Chaining 密文分组链接模式）
1.分段也是按照上面那种方式划分。
2.不同的是，我们有个初始化的向量，可以理解为，一开始有个随机数。
3.用这个初始化的向量，对明文分段1 ，作异或操作，得到密文分段1。
4.再用密文分段1 对明文分段2，作异或操作，得到密文分段2。
5.这样依次下去，把得到的密文分段拼接起来即可。
也就是每一步都依赖于前一步得到的结果。
避免漏洞：如果划分的明文段是一样的，是用之前得到的密文分段加密的，最后得到的密文也一样的可能性就非常小了。
如果篡改信息，也会知道，因为解密之后的明文就是乱的了。。

当然还有其他的加密方式，比如ECB、CFB、OFB、CTR模式。
1.2 One-Time pad
中文可以翻译成一次性便签、一次性密码本。是属于对称密码的一种形式，只不过密钥长度是和原文一样长的。
思想：之前的是密钥要比原文短，所以要分段。
现在把密钥都弄成和原文一样长，直接异或加密。再异或解密。

香农，在理论上证明了这是无法破译的，不可能破译出来的。
但是需要几个条件：
1.明文、密钥等长
2.密钥必须完全随机
3.密钥不能重复。即便加密同一串明文，后面使用的密钥也要不一样。
这样就有一个问题：
如果每次传输能保证密钥是安全的，为什么不直接传输明文呢？这就形成了一种悖论，也就是说这个不可能破译，所要的条件太严格了，几乎很难很难达到。
无法破解的原因：
破解就是枚举嘛，枚举所有可能的密钥，得到所有可能的明文。但是你不知道哪一个明文是正确的，那个明文是和原来一样的。
虽然条件很严格，但这是量子密钥分发所依赖的基本理论。

2 . 非对称密码
就没有了之前的密钥分发问题。加密方和解密方使用的密钥是不一样的。

图 7 非对称密码示意图

代表性的非对称加密算法： RSA、DH、DSA、ECDSA
所依赖的数学原理：因数分解、离散对数、椭圆曲线。

以RSA 举例。
公钥：有 E、N。私钥：有 D、N
加密：密文 = 明文的 E 次幂，再对 N 求余。
解密：明文 = 密文的 D 次幂，在对 N 求余。
如果没有对N求余这步，直接开 E 次根号就好了。有了这步，就很难用公钥
来解密了。

不好破解的原因：
1.对于发出去的是公钥这个过程：
即便第三方窃取到公钥，也没事，破解不了，只有用私钥才能解密。

2.对于收回来的密文这个过程：
就看第三方能不能用公钥来破解出私钥来。
理论上来说是可以的，但是这个破解（要分解质因数）的时间复杂度很高很高，可以说是很难破解了。这个就涉及到了RSA生成公钥和私钥的过程（算法）。数学原理涉及到：欧拉函数、质数。

混合加密
RSA 这个非对称加密算法可以说非常好了，但为什么不能替代之前的对称加密算法了呢？就是因为这个非对称加密算法计算的时间是很慢的，在现实中体现就是效率比较低。
结合对称加密和非对称加密的优缺点，就有了混合密码。

整体思路：整个过程还是对称加密的过程，只不过传输的密钥是用非对称加密技术来加密的。（这个密钥是相对短的数据，所以这种方案是可行的。）

（二）对保证保证完整性的解决方法

哈希函数
哈希函数，也叫散列函数。不管多大的数据，经过哈希算法计算之后，都会生成一个固定长度的哈希值。也叫生成了摘要。

特点：
1.雪崩效应：原始数据有一点点的不一样，生成的哈希值都会完全不同。
2.单向的：不能根据哈希值推算出原来是什么数据。
基于这2个特点，哈希函数就可以用来保证数据的完整性。

常见的哈希算法：
MD5（产生128位）、SHA-1、SHA-256（区块链中用的比较多）、SHA-512
Java 中的 hashCode 方法。（也是单独的一种算法）

遇到的应用：
MySQL 官网用 md5 校验用户下载文件的完整性。
Ubuntu 官网用 SHA-256 校验用户下载文件的完整性。

哈希碰撞的问题：
虽然哈希算法很好了，但是有个哈希碰撞的问题。
跟抽屉原理是一个道理。比如说有7个抽屉，8个鸽子。规定每个抽屉必须要有鸽子。那这样必然有个抽屉里有2个鸽子。就是不一样的数据，可能会生成相同的哈希值。

只有哈希也不行。还会有篡改的问题。
比如传过去消息 + 哈希值。
如果在传输的过程中，第三方窃取到了这个数据。搞了个自己的消息+哈希值传过去。
所以有了消息认证码MAC，Message Authentication Code。

2 .消息认证码
这里介绍一种算 MAC 的方法，还有很多其他的方法：
这个MAC 的原理跟 MD5 加盐存储用户口令是差不多的。
思路：
1.双方共享一个密钥。这个密钥的分布问题就用非对称密码算法加密一下就可以了。
2.然后就是将消息 + 密钥，生成一个哈希值，即我们说的MAC。
3.传送消息和这个MAC。
4.然后接受方，用密钥和这个消息拼接，算下哈希值（MAC），看和传过来的MAC一不一样，就知道有没有被篡改了。

图 8 消息验证码示意图

但是这样就完美了，没有问题存在了吗？当然不是的！还有问题！
现在保证了完整性，保证了认证（是来自你的消息）。还有个重放攻击的问题。

重放攻击问题说明：
我们要求是这个数据只传送过去1遍。
如果第三方，拿到这个正确的数据了，但是给接受方传过去了好几遍。。。
就比如说这个数据是给你说要扣100元钱的，但是第三方发几次，你就要扣几次，因为你每次接受到的数据都是对的！

在现实中，也有这个问题。
比如锁汽车门，你用电子车钥匙开车门了，但是有人复制了这个钥匙的电波。就可以用这个复制的电波去无限次的开车门了。

解决重放攻击问题：
在消息里面，加上一个数（随机数也好，顺序数也好），这个数只能用一次，下次消息过来还是这个数的话，就说明是重放攻击了。
这个数也要加到消息里，一起生成 MAC 值，要不然仍然会有之前的问题。
这个MAC在现实中还是很常用的，HTTPS里的SSL协议就必须要用到MAC。
（三）针对否认的解决方法
数字签名：这个就和非对称加密相反的用了。签名就像现实生活中我们的指纹。
主要思路：
1.对要发送的消息，用自己的私钥来加密一下，就生成了一个数字签名。
2.传输过去的就是消息和这个数字签名。
3.验证是不是你发的，就用公钥对这个数字签名解密一下，看和给的消
息一不一样，因为私钥是只有你自己有的，这个公钥只能解开你私钥加密的东西，这样就知道了是不是你发的。
如果消息数据量很大的话，就对消息取个哈希值，再来进行签名的过程。

图 9 数字签名示意图

数字签名的应用：
IOS 系统的APP商店。对发布的安装包还要附加个自己的签名。

那有了数字签名就万事大吉了吗？
不是的！还有个叫中间人攻击的问题，也就是伪装的问题。
中间人攻击说明：
这个中间人，对通信的双方来说，就相当于一个隐形人。
因为数字签名需要分布公钥出去，问题就出在这里。。
如果你收到的并不是真正传输方的公钥呢，而是一个中间人自己的公钥。
这个中间人就在通信的双方来捣乱，可怕的是通信双方不知道中间人的存在。

其实我们上网，这种问题还是经常可以遇到的。通过的网关代理服务器，防火墙这些，都可以看成是中间人的存在，就看他们有没有恶意了。

（四）针对伪装的解决方法
那我们怎么保证这个数字签名，就是你传输方真正的数字签名呢。
这时候就需要认证机构来介入了。
前提：这个认证机构可以保证是权威的，绝对可靠的。

主要思路：
1.就是在传输消息接收方的公钥时候，先给认证机构，用认证机构的私钥对传输的公钥进行签名。
2.给消息发送方的就是，消息接收方的公钥和认证机构的签名。
3.用认证机构的公钥来验证传过来的认证机构给的签名的，从而确定消息
接收方的公钥的合法性。
4.然后就可以用公钥来加密发出去给有私钥的那个人了。

图 10 认证机构示意图

那现在的问题就是：怎么才能保证这个认证机构的绝对可靠的了。
所以，我们还需要另一个认证机构，来保证他的可靠。
对这另一个认证机构，依次采取这样的方法。
这样一直到最顶上的，最顶端的，我们叫RCA（Root Certificate Authority），即根认证机构。
这整个体系，就是 PKI（Public Key Infrastructure），即公钥基础设施。

这就决定了 RCA 的数量是非常少的，目前全球只有50多家。
如果出了问题，这些CA（Certificate Of Authority）认证中心是要负责的，通过法律的形式来约束。
这些RCA的公钥，一般都是在我们的电脑的操作系统里就内嵌的，自带的。所以，最好不要去安装盗版的操作系统，如果这操作系统里面的RCA是改
过的话，那就相当于裸奔在互联网这个大世界中了，是一种很危险的行为。

四：总结
人类长久以来都在不断改进密码技术，即使到了计算机和互联网时代，技术进步也从未停止，现阶段人们对密码学的研究主要在量子密码领域。然而，即便使用量子计算机，也无法实现完美的密码技术，即便真的有完美的密码技术，也不可能实现完美的完全性。因为这个过程我们人类必然参与其中，我们人类本身就是不完美的。通过本文了解了一些密码学的发展历史及其局限性之后，我们应该要懂得在生活中不应该盲目相信计算机，而是应该注重培养健全的安全意识。

参考文献：
[1] 浅谈密码学及其在计算机网络安全中的作用，2020-06-08
[2] 网络安全和加密领域的“下件大事”，2020-05-26
[3] 密码应用安全专刊序言 (中英文) ，2020-06-15
[4] 密码学中算法加密技术应用研究，2016-06-12