【11.10】现代密码学1——密码学发展史：密码学概述、安全服务、香农理论、现代密码学

写在最前面

参考：密码学发展简史

骆婷老师的《现代密码学（32H）》课程，笔记+查找的资料补充
期末为闭卷考试的形式

密码学概述

密码学早在公元前400多年就已经产生，人类使用密码的历史几乎与使用文字的时间一样长，密码学的发展大致可以分为 3 个阶段:
1949年之前的古典密码学阶段;
1949 年至 1975 年密码学成为科学的分支;
1976年以后对称密钥密码算法得到进一步发展，产生了密码学的新方向—公钥密码学。
1976 年，W.Diffie 和 M.Hellman在发表的文章“密码学的新方向”中首次公开提出了公钥密码( Public-key Cryptography)的概念。公钥密码的提出实现了加密密钥和解密密钥之间的独立，解决了对称密码体制中通信双方必须共享密钥的问题，在密码学界具有划时代的意义。

现代密码学

在密码学的发展史上，公钥密码被认为是一个重大的突破。公钥密码中加密和解密使用不同的密钥，其中，用于加密的叫做公钥，用于解密的为私钥。这种密码的安全性不是建立在秘密性上，而是基于相应数学问题在计算机上的难解性来保证。RSA算法是公钥加密算法中最为广泛应用的一种，它的安全性是建立在大整数素因子分解在计算机上的困难性上的。但随着计算能力的不断增强和因子分解算法的不断改进，特别是量子计算机的发展，公钥密码的安全性也渐渐受到威胁。

1977年，美国麻省理工学院提出第一个公钥加密算法RSA算法，之后ElGamal、椭圆曲线、双线性对等公钥密码相继被提出，密码学真正进入了一个新的发展时期。

一般来说，公钥密码的安全性由相应数学问题在计算机上的难解性来保证。
以广为使用的 RSA算法为例，它的安全性是建立在大整数素因子分解在计算机上的困难性，如，对于整数22，我们易于发现它可以分解为2和11两个素数相乘，但对于一个500位的整数，即使采用相应算法，也要很长时间才能完成分解。

量子密码学

但随着计算能力的不断增强和因子分解算法的不断改进，特别是量子计算机的发展，公钥密码安全性也渐渐受到威胁。目前，研究者们开始关注量子密码、格密码等抗量子算法的密码，后量子密码等前沿密码技术逐步成为研究热点。

格密码则利用了数学中的格结构来构建密码系统，具有较强的抗量子特性。
后量子密码学主要利用非对称密码、哈希函数、消息认证码等技术来构建密码系统，这些技术都具有抗量子性质。

量子密码利用了量子力学中的不可克隆性原理保证消息的安全性，这种密码技术被认为是未来密码学发展的一个重要方向。量子密码术是一种新的重要加密方法,它利用单光子的量子性质,借助量子密钥分配协议可实现数据传输的可证性安全。量子密码具有无条件安全的特性(即不存在受拥有足够时间和计算机能力的窃听者攻击的危险)，而在实际通信发生之前，不需要交换私钥。

基本术语

1. 加密 (Encryption)
2. 解密 (Decryption)
3. 密钥 (Key)
4. 对称加密 (Symmetric Encryption)
5. 非对称加密 (Asymmetric Encryption)
6. 公钥 (Public Key)
7. 私钥 (Private Key)
8. 数字签名 (Digital Signature)
9. 散列函数 (Hash Function)
10. 消息认证码 (Message Authentication Code)
11. 密码强度 (Password Strength)
12. 随机数生成器 (Random Number Generator)
13. 密码学安全协议 (Cryptographic Security Protocols)
14. 密码学攻击 (Cryptographic Attacks)
15. 可逆密码 (Reversible Cipher)
16. 不可逆密码 (Irreversible Cipher)
17. 混淆器 (Confusion)
18. 扩散器 (Diffusion)
19. 流密码 (Stream Cipher)
20. 块密码 (Block Cipher)
21. 密码协议 (Cryptographic Protocol)

密码学、密码编码学、密码分析学 明文、密文、密钥。加密钥，解密，加密方案

1. 密码学 (Cryptography): 研究保护信息安全的一门学科，通过加密技术实现信息的保密、完整性和可靠性。

2. 密码编码学 (Cryptology): 既包括密码学也包括密码分析学，是一门研究加密和解密的科学。

3. 密码分析学 (Cryptanalysis): 研究破解密码和密码系统弱点的一门学科。

4. 明文 (Plaintext): 未经加密的原始信息或数据。

5. 密文 (Ciphertext): 经过加密处理的信息或数据。

6. 密钥 (Key): 加密和解密的关键，是一组特定的参数或信息，使用正确的密钥才能获得正确的明文。

7. 加密 (Encryption): 将明文转换为密文的过程。

8. 解密 (Decryption): 将密文转换为明文的过程。

9. 加密方案 (Encryption Scheme): 加密和解密的完整流程和方法，包括选择加密算法、密钥生成、加密过程、解密过程等。

分组密码、流密码 对称密码、非对称密码 kerckhoffs假设 唯密文攻击、选择明文攻击、选择密文攻击

密码分析，主要是秘钥的分析。

1. 分组密码（Block cipher）：将明文按照一定长度（分组大小）进行分块，对每个分组进行加密，输出密文。

2. 流密码（Stream cipher）：将明文和密钥进行逐位异或（XOR）运算，逐位输出密文。

3. 对称密码（Symmetric key cryptography）：加密和解密使用相同的密钥。

4. 非对称密码（Asymmetric key cryptography）：加密和解密使用不同的密钥，包括公钥和私钥。

5. Kerckhoffs假设（Kerckhoffs’ principle）：密码系统的安全性不依赖于保密算法，而依赖于保密密钥。

在不同攻击能力的情况下，敌手获得信息的情况不一样。

6. 唯密文攻击（Ciphertext-only attack）：攻击者只拥有密文，试图通过分析密文来破解加密算法或密钥。

7. 选择明文攻击（Known-plaintext attack）：攻击者拥有明文和密文对，并试图破解加密算法或密钥。

明文攻击是指攻击者拥有加密的数据，但同时也拥有原始的明文数据，并通过比较加密和明文数据的差异来破解加密算法或密钥。
这种攻击方式通常用于简单的加密算法或者使用固定密钥的情况，因为即使密钥很大，但如果算法本身很简单，仍然容易受到明文攻击的影响。

例如：
如果一个加密算法使用的密钥是“123456”，攻击者可以拥有一些原始明文数据和相应的加密数据。攻击者可以在不知道密钥的情况下使用这些数据比较来推断出密钥是“123456”。然后攻击者就可以使用这个密钥来解密任何加密数据，而不需要进一步的破解工作。

8. 选择密文攻击（Chosen-ciphertext attack）：攻击者可以选择一些密文并获得其对应的明文（有条件询问加密机的权限），然后观察输出结果，以此来推断密钥或加密算法。

一个具体的例子是：
攻击者想要获取一条被AES加密的密文，但他并不知道原始明文是什么。他可以通过选择一些自己想要的密文并将其提交给加密系统，然后观察输出结果并记录下来。这些输出结果包括了密文本身以及加密使用的密钥。通过对这些信息的搜集和分析，攻击者可以试图推断出加密系统的密钥，从而获得解密的能力。

需要注意的是，选择密文攻击需要攻击者在攻击前能够选择一些密文进行提交。这通常意味着攻击者需要具有对加密系统的一些操作权限，例如截获网络传输的密文或者直接访问加密系统的加密接口。

加解密的通信模型

对称加密

使用同一个密钥，对数据镜像加密和解密，这种加密技术，称为对称加密。
在这里插入图片描述

对称加密常用算法：
DES，3DES，IDEA，AES

优点：
算法公开、计算量小、加密速度快、加密效率高

缺点：
不同通讯双方使用不同密钥，导致密钥过多，难以管理
通讯双方密钥交换，无法保证安全
无法验证发送者和接受者身份

PKI通信工作流程

从以上的介绍中可以看出，各种加密算法都有其特点和适用性：

使用非对称加密，发送者A使用私钥加密，接受者B能够验证数据的发送者A是谁，由于所有人都能使用发布者A公钥解密，这种方法只能适合发布公开的信息。
接受者B的公钥是公开的，用它加密数据后发给B，有可能被截获掉包。

非对称加密算法，加密速度很慢，强度高。对称加密算法，速度快，但是密钥交换是个问题。

单向加密不可逆，接收者无法还原到明文。

那么，就需要一种通信模型能够扬长避短，解决通信安全的问题，于是便有了下面的模型：PKI通信流程

1、发送者A准备好信息明文。
2、发送者A对信息进行哈希运算（单向加密算法），得到一个信息摘要。
3、发送者A使用自己的私钥（SK）对信息摘要进行加密，即数字签名，之后将其附件在发送的信息上。（实现不可否认性）
4、发送者A随机生成一个对称加密密钥，并使用它对发送的信息包括摘要进行对称加密，生成密文。
5、发送者A再使用接收方的公钥（PK）对第4步使用的随机对称密钥进行加密，之后将其附加至第4步生成的密文上，一并发给接收者B。
6、接收者B收到发送者A的密文后，首先使用自己的私钥（SK）解密出对称加密的密钥。
7、接收者B使用对称密钥解密密文，得到附加摘要的信息明文。
8、接收者B使用发送者的公钥（PK）解密摘要，获得哈希值
9、接收者B使用同样的哈希算法再次对信息明文计算，得到新的信息摘要，与解密后的摘要比对，如果一致，则说明收到的信息明文未被篡改。（保证数据完整性）

以上的通信模型很好的解决了数据完整性、不可否认性，但这个模型的依赖的关键点是双方公钥。

这个模型中双方公钥来源无法验证，而且在通讯前，如何获得每个人的可信任的公钥也成了整个系统的关键。

因此，需要一套系统，能够解决以上存在的种种问题：身份认证、数据完整性、密钥交换、操作的不可否认性，它就是PKI。

古典密码与分析

古代密码的加密

古典密码的加密方式是使用某种规则将明文转化为密文，而解密就是将密文转化为明文。在这个过程中，密钥起到了重要的作用，密钥是一个参数，用于决定加密和解密的规则。

这一时期的密码学更像是一门艺术，其核心手段是代换和置换。代换是指明文中的每一个字符被替换成密文中的另一个字符，接收者对密文做反向替换便可恢复出明文；置换是密文和明文字母保持相同，但顺序被打乱。

古代的藏宝图，经过层层的加密化，其实也是我国古典密码学的一个表现。
代换密码的著名例子有:古罗马的凯撒密码（公元前1世纪）和法国的维吉尼亚密码（16世纪）。
凯撒密码是对字母表中每个字母用它之后的第k个字母来代换，如，将“comeatnine”加密为“htrjfysnsj”（k=5）。
但这种加密方式无法掩盖各字母的频率特征，易被破解。
维吉尼亚密码相比之下提升了安全性，它的密钥通常是一个单词，如，“hear”，对于上述明文“comeatnine”，加密时将第1个字母后移8位（密钥“hear”的第一个字母h处于字母表第8位），第2个字母后移5位（密钥的第二个字母e处于字母表第5位），……，因此加密后的结果是“jsmvhxnzui”。

抗战片里面发报文的时候发的是密文，这个密文会对应一个密码本，比方说《三国演义》这本书。它的加密方式会告诉你加密的文字属于书中的那个字，当你解密完成之后，就可以得到明文的报文。这是一种常见的古典加密方法。

古典密码的分析

古典密码的分析方法有很多种，其中比较常用的是频率分析和差分分析。

频率分析是指通过分析密码中出现频率最高的字母来推断密钥。在英语中，字母“e”出现的频率最高，所以攻击者可以通过分析密文中出现频率最高的字母来猜测密钥。

差分分析是指通过对明文和密文之间的差异进行分析来推断密钥。攻击者可以选择两个密文，并比较它们在明文中的差异，然后推测密钥。

安全服务

身份认证、传输加密、存储加密、应用程序保护

身份认证是安全服务的基础，它通过验证用户身份来保护系统和数据的安全。身份认证可以采用多种方式，如用户名密码、指纹识别等，其目的是确认用户的身份，确保只有授权用户才能访问敏感信息。

传输加密是通过使用加密技术来保护数据在传输过程中不被恶意攻击者窃取或篡改。加密技术可以采用公开密钥加密（PKI）、SSL/TLS等方式来保护敏感数据在传输过程中的安全。

存储加密是指采用加密技术来保护数据在存储时的安全。通过对存储数据进行加密，可以保护数据不被未授权访问或窃取，增强数据安全性。

应用程序保护是指在应用程序开发过程中，采用安全开发、代码审计等方法来保护应用程序的安全性。应用程序保护可以增强应用程序的鲁棒性和防御能力，有效预防各种漏洞和攻击。

香农理论

香农理论，又称信息论，是由美国数学家克劳德·香农于1948年发明的一种基于数学原理的理论体系。它主要研究如何量化信息的传输和处理，包括信息的压缩、传输、存储以及加密等方面。它的贡献在于提供了一套清晰的数学工具，用于衡量信息的容量、可靠性和传输速度等问题，从而为通信领域提供了强有力的支持和指导。

香农理论的核心概念是信息熵和信道容量。
信息熵是指信息的不确定性程度，即信息中所包含的“信息量”。比如，如果一组信息有多种可能的取值，那么它的信息熵就比较高，因为我们无法确定具体的取值。
信道容量则是指在一定的信道条件下，信道可以传输的最大信息量。这两个概念被广泛应用于通信领域，例如在数据压缩、数据传输和信道编码等方面。

此外，香农理论还提出了一种被广泛应用的加密方法，即信息论加密。它利用信息熵的概念，将明文数据转化为一种无规律可循的密文数据，从而保证了信息的保密性和语义安全性。

现代密码学

乘积密码方案

乘积密码方案是一种经典的加密方法，其基本思想是将明文转化为数字序列，并在一定规则下进行乘法运算，得到密文。其加密过程简单、安全性高，曾经被广泛应用于电报通信和军事领域的加密。

具体的实现方法是，首先将明文进行编码，得到数字序列。然后选取两个长度相等的密钥，分别为公钥和私钥。公钥可以公开，而私钥只有接收方知道。接下来，将明文数字序列中的每个数字与公钥中的对应数字相乘，并取模得到密文数字序列。接收方可以使用私钥将密文数字序列进行解密，还原出明文。

例如，假设明文为“hello world”，
编码为数字序列为[8,5,12,12,15,0,23,15,18,12,4]，
选取公钥为[2,3,5,7,11,13,17,19,23,29,31]，
私钥为[59,61,67,71,73,79,83,89,97,101,103]。
则加密过程为：[8,5,12,12,15,0,23,15,18,12,4] * [2,3,5,7,11,13,17,19,23,29,31] = [16,15,60,84,165,0,391,285,414,348,124]
[16,15,60,84,165,0,391,285,414,348,124] % [59,61,67,71,73,79,83,89,97,101,103] = [50,11,26,13,16,0,62,7,93,15,10]解密过程为：[50,11,26,13,16,0,62,7,93,15,10] * [59,61,67,71,73,79,83,89,97,101,103] = [2950,671,1734,923,1168,0,5146,623,9021,1515,1030]
[2950,671,1734,923,1168,0,5146,623,9021,1515,1030] % [2,3,5,7,11,13,17,19,23,29,31] = [8,5,12,12,15,0,23,15,18,12,4]

可以发现，加密后的密文数字序列与原始的明文数字序列没有任何关联，因此具有较高的安全性。

虽然乘积密码方案已经被现代密码学所取代，但其思想和基本原理依然具有参考价值，尤其是在一些传统的通信和加密场景中仍然得到了广泛应用。

代换-置换网络

代换-置换网络（Substitution-Permutation Network，SPN）是一种常用的对称密钥密码算法结构。它采用代换和置换两种基本操作，使得密文与明文之间的关系变得非常复杂，从而增强加密的安全性。

代换操作是指将明文某一部分替换成密文的另一部分，常见的代换操作包括置换、S盒代换等。例如，置换操作可以将明文中的某个比特位置与其他比特位置交换，S盒代换则是将一组输入映射到一组输出。在SPN中，代换操作通常是通过多个轮次的代换层实现的。

置换操作则是指通过重排明文的比特顺序来生成密文。置换操作可以增强加密算法的弥散性，使得每一位明文比特对最终密文的影响都非常均衡。在SPN中，置换操作通常是通过最终的置换层实现的。

下面以AES密码算法为例，介绍SPN的具体实现。在AES算法中，SPN采用四个基本操作：字节代换（SubBytes）、行移位（ShiftRows）、列混淆（MixColumns）和轮密钥加（AddRoundKey）。其中字节代换和行移位属于代换操作，列混淆属于置换操作，轮密钥加则是在每一轮加入密钥来增强加密的安全性。

在AES算法中，SPN的基本流程如下：

1. 确定加密轮数和密钥长度。

2. 将明文分割成16个字节的块，并进行填充。

3. 初始轮密钥加，即将明文与初始密钥进行异或操作。

4. 进行多轮SPN操作，每轮都包括字节代换、行移位、列混淆和轮密钥加四个操作，并使用不同的轮密钥。

5. 最后一轮仅包含字节代换、行移位和轮密钥加三个操作。

6. 将加密后的各个块组合成密文。

通过SPN的代换和置换操作，结合轮密钥加等安全机制，AES算法能够保证较高的加密安全性。因此，SPN被广泛应用于实际的加密通信、数据存储等领域。

安全性概念

可证明安全性——规约（*规约证明的方案——会考）

可证明安全性指的是一种安全证明，即证明一个密码协议在某些假设下是安全的。可证明安全性的证明不仅可以增加对加密算法的信任度，也可以帮助设计密码协议的人们更好地理解安全性考虑的所有细节，从而设计更加安全的协议。

密码学中的归约（Reducibility）是指将一个复杂问题转化为一个已知解法的问题。具体来说，它是一种证明方法，通过将一个待证明的问题转化为另一个已知解法的问题，来证明待证明问题的正确性。

假设我们想证明一个新的对称加密算法（称为算法X）的安全性。
我们可以将算法X归约到另一个已知的对称加密算法（称为算法Y）的安全性证明上。这可以通过构造一个将算法X的任意输入转换为算法Y的输入的“黑盒”模拟来完成。然后，我们可以使用算法Y的安全性证明来证明算法X的安全性。

例如，我们要证明一个加密算法A是安全的，我们可以使用归约的方法。
归约（reduction）是一种证明算法安全性的常见方法，其基本思想是将要证明的算法A转化为一个已知安全的算法B。具体流程如下：

1. 假设存在攻击算法C，可以在有限时间内破解算法A。

2. 利用攻击算法C构造一个新的攻击算法D，探索该算法D是否可以在有限时间内破解算法B，即D能够得到B的正确性输出。

3. 将算法D作为黑盒，输入算法B的挑战密文和加密密钥，输出正确的明文。

4. 如果算法D可以成功地破解算法B，则说明攻击算法C可以成功地破解算法A。此时，A的安全性就无法得到保证。

5. 如果算法D无法成功地破解算法B，则说明攻击算法C无法成功地破解算法A。此时，A的安全性得到了保证。

这就是归约的基本过程，通过将一个问题转化为另一个已知解法的问题，来证明原问题的正确性。

加密方案的定义

在密码学中，加密方案的目标是将一个明文消息m加密为一个密文c，使得只有拥有相应密钥的人能够解密并获得原始的明文消息。为了实现这个目标，加密方案可以采用对称加密或公钥加密的方式。

对称加密方案的加密密钥和解密密钥是相同的，通常用一个变换函数E来表示，即

$$c=E_k(m)$$

其中，k表示密钥，m表示明文消息，c表示密文。
基本思路是，用密钥k对明文m进行加密得到密文c，然后将密文c传输给接收者，接收者再使用密钥k进行解密得到明文m。

而在公钥加密方案中，加密密钥和解密密钥是不同的，通常用一个加密函数E和一个解密函数D来表示，即

$$c=E_{pk}(m),m=D_{sk}(c)$$

其中，pk表示公钥，sk表示私钥，m表示明文消息，c表示密文。
基本思路是，使用接收者的公钥pk对明文m进行加密得到密文c，然后将密文c传输给接收者，接收者再使用自己的私钥sk进行解密得到明文m。

完善保密性

完善保密性的方法主要包括密钥管理、密钥交换、随机数生成等。其中，密钥管理是指保证密钥的安全性，如生成、存储、更新和销毁密钥；密钥交换是指在不安全信道上安全地交换密钥，常用的方法包括Diffie-Hellman密钥交换、RSA密钥交换等；随机数生成是指生成高质量的随机数以保证加密算法的安全性。
$$P(m|c)=\frac{P(c|m)P(m)}{P(c)}$$

其中，$P(m|c)$为明文$m$在得到密文$c$的情况下的后验概率，$P(c|m)$为明文$m$加密后得到密文$c$的概率，$P(m)$为明文$m$的先验概率，即$m$出现的概率，$P(c)$为密文$c$的先验概率，即$c$出现的概率。

如果对于任意的$m$和$c$，都有$P(m|c)=P(m)$，则密码体制具有完善保密性。

实际应用中，常用的完善保密性的密码体制有一次性密码本（One-Time Pad）和矩阵加密（Matrix Encryption）等。这些密码体制的基本思想是利用随机性和密钥的唯一性来实现完善保密性。同时，在应用过程中，也需要确保密钥的安全性和随机性，以免被攻击者破解。

语义安全性

语义安全性是指对于任意两个不同的明文消息m和m’，加密后的密文c和c’几乎是相互独立的，即对于任意的攻击者攻击策略，攻击者无法在多项式时间内区分出密文c是由明文消息m加密得到还是由明文消息m’加密得到。常用的语义安全加密方案包括基于单向函数的加密方案和基于公钥密码的加密方案。