CryptographyⅠ笔记

2022-06-04 密码学 Cryptography, Dan Boneh, 密码学评论字数统计: 11.5k(字) 阅读时长: 40(分)

斯坦福教授Dan Boneh的密码学课程《Cryptography》
课程链接：https://www.bilibili.com/video/BV1Ht411w7Re
讲义：https://www.cs.virginia.edu/~evans/courses/crypto-notes.pdf

目标：课程结束后可以推导加密机制的安全性，可以破解不安全的加密机制

绪论

密码学用途

安全通信，例如https，Bluetooth
加密磁盘文件，例如EFS
内容保护，例如DVD使用CSS
用户认证

高阶用途：

外包计算（同态加密）
安全多方计算
零知识证明

安全通信

在web服务中使用https协议进行通信，起到安全通信作用的是TLS协议，TLS协议主要包括两部分：

握手协议：使用公钥密码体制建立共享密钥
Record层：使用共享密钥传输数据，保证数据的机密性和完整性

加密磁盘文件

加密磁盘文件从哲学角度来看就是今天的Alice和明天的Alice进行安全通信
图 2

对称加密

Alice和Bob双方共享密钥k，攻击者不知道密钥k，他们使用两个算法进行通信，分别是加密算法E，解密算法D。加密算法以原信息和密钥为输入产生相应密文；解密算法正好相反，以密文和密钥为输入，输出原信息。加密解密算法是公开的，只有密钥k是保密的。我们应当使用公开的算法，因为它的安全性经过业内人士的审查。
图 3

密钥使用次数

可以根据密钥使用次数分为一次使用的密钥，多次使用的密钥
一次使用的密钥只用来加密一个信息，例如加密邮件，为每一封邮件都生成一个新的密钥。
多次使用的密钥可以用来加密多个消息，例如用同一密钥加密文件系统的许多文件，多次使用的密钥需要更多机制来确保加密系统是安全的
图 4

一些结论

任何依赖可信第三方的计算都可以不借助可信第三方完成
图 5

密码算法提出三步骤

明确描述威胁模型。例如数字签名算法中，攻击者如何攻击数字签名？伪造签名目的何在？
提出算法构成
证明在该威胁模型下，攻击者破解了算法等同于破解了根本性难题。意思就是算法的安全性由根本性难题保证，例如RSA依赖大整数质因数分解困难问题

密码历史

对称密码历史

图 6

替换式密码

替换式密码的密钥是一张替换表
图 1

例如：凯撒密码

凯撒密码是没有密钥或者只有一个固定密钥的替换式密码
图 3

假设替换式密码的密钥只能使用26个英文字母，它的密钥空间有多大？是 $26!$ ，约等于 $2^{88}$ ，也就是说可以用88位比特表示密钥，这个密钥空间是足够大的，但是这个加密算法不安全
图 4

如何破解这个加密算法？

使用字母频率来破解。在英文文献中，出现频次最高的字母是e，那么我们统计密文中出现频次最高的那个字母，例如c，那么这个替换式密码的密钥k中很可能包含了e->c；同样的道理，出现频次第二高的是t，第三高的是a，分别找到密文中对应的字母进行还原
使用字母配对（组合）。在英语中，最常见的二元配对有“he”，“an”，“in”，“th”。第一种方法还原出了eta，根据配对规则可以还原配对中的另一个字母。

这种攻击方式叫唯密文攻击（CT only attack），替换式密码抵御不了这种攻击

Vigener密码

Vigener密码的密钥是一个单词，加密算法是将密钥重复直到和明文一样长，与明文逐位求和模26得到密文，解密算法是对密文逐位减去密钥
图 5

如何破解Vigener密码？

首先假设攻击者已知密钥长度（未知也不影响破解，枚举长度即可），例如密钥长度为6，那么攻击者可以将密文按照每6个字母一组进行分组。然后看每组的第一个字母，他们都是由同一个字母加密的，例如上图中k的字母C。我们同样可以使用唯密文攻击，在每组的第一个字母中找到出现频次最高的字母，它们对应的明文位为E，然后对应的密钥为为密文位-E = 密钥位。同样的方法对密钥第2位直到最后一位执行。这种破解方法的实质是多次使用唯密文攻击
图 6

轮轴机

最早的轮轴机：Hebern machine（一个轮轴）

本质上是一个替换式密码。按下A，假如A加密成了T，此时轮轴机转动一格，再次按下A，A就加密成了S。轮轴机一经提出很快就被破解了，同样是唯密文攻击。
图 7

最著名的轮轴机：Enigma（3-5轮轴）
图 8

数字时代的密码

1974：DES（keys = $2^{56}$ , block size = 64 bits)

Today: AES(2001), Salsa20(2008) (and others)

离散概率

有限集合与概率分布

图 9

事件

事件是有限集合的子集

图 12

事件的并集发生的概率存在上界
图 13

随机变量

随机变量是一个函数 X：U(有限集合)->V(某个集合)
集合V是随机变量取值的地方。例如定义随机变量 $X:\{0,1\}^n\longrightarrow \{0,1\}$ ; $X(y)=lsb(y) \in \{0,1\}$
这个随机变量将n位长度的字符串集合映射成了只有0和1的两个元素的集合，具体做法是取最低位。任意一个n位长度的字符串会被映射出0或者1
图 14

均匀随机变量

图 15
图 16

随机化算法

随机化算法相比于确定的算法，在原像中加入了随机因子，所以对同一条消息进行随机化，结果一般是不同的
图 17

独立性

图 18

异或

异或就是逐位模2和
图 20

异或在密码学中非常重要，在一个有限集合上有一个随机变量Y，有一个独立的均匀随机变量X，那么 $Z:=Y\bigoplus X$ 仍然是这个集合上的均匀随机变量
图 21

生日悖论

图 22

r指的是随机变量的值

独立同分布举例：假设U = {00,01,10,11}表示抛硬币两次的结果，令随机变量 $X：U\rightarrow\{0,1\}$ 表示第一次抛硬币的结果， $Y：U\rightarrow\{0,1\}$ 表示第二次抛硬币的结果。X和Y是相互独立的且概率一样，所以这两个随机变量是独立同分布的

流密码

流密码是一种对称密码。
对称密码的严格定义：定义在 $\mathcal{K,M,C}$ 上的一对“有效”加解密算法 $(E,D)$
$\mathcal{K}$ 指密钥空间， $\mathcal{M}$ 指明文空间， $\mathcal{E}$ 指密文空间
$E: \mathcal{K\times M\rightarrow C}$
$D:\mathcal{K\times C\rightarrow M}$
即 $\forall m \in \mathcal{M}, k \in \mathcal{K}: D(k, E(k, m))=m$
"有效"这个词在理论密码学家看来，时间复杂度是多项式时间内的就是有效的，真正运行时间取决于输入规模。在应用密码学家看来，可能是加解密1GB数据要在10s内就算有效。
图 23
特别注意，加密算法是随机化算法，解密算法是确定性的算法

一次性密码本

一次性密码本的明文空间、密文空间、密钥空间均相同
图 24
一次性密码本的加密算法是将明文与密钥做异或运算，解密也是将密文与密钥做异或运算，根据异或运算的结合律可以知道加解密算法是正确的
图 25

如何证明这个密码的安全性？

信息论的创始人香农提出一个观点：不能从密文得出关于明文的任何信息
图 26
攻击者截获一段密文，如果满足下面的等式，即不同明文经过同一个密钥加密后等于这个密文的概率是相同的，那么攻击者就无法得知真正的明文，这种密码是完美保密性的
图 28

一次性密码本是完美保密性的
图 29
完美保密性只是意味着没有唯密文攻击，并不意味着在实际使用中是安全的
图 30

香农在给出完美保密性的证明后又给出了一个定理，想要完美保密性，密钥长度要大于等于明文长度，所以完美保密性的密码是不实用的
图 31

流密码（Stream ciphers）

流密码是使用的一次性密码本，它的思想是使用伪随机密钥代替随机密钥

伪随机数生成器是一个函数，它可以将s位的01比特串扩展成n位的01比特串，n>>s。注意，伪随机数生成器算法是不具备随机性的，具备随机性的是种子
图 32

流密码使用伪随机数生成器（PRG），将密钥当做种子，生成真正用于加密的比特串
图 33
因为密钥长度远小于明文长度，所以流密码并不是完美保密性的
图 34
流密码的安全性不同于完美保密性，它需要另外一种安全性定义，这种安全性依赖具体的伪随机数生成器
图 36
安全的伪随机数生成器必须是不可预测的。
假设伪随机数生成器是可预测的，那么存在某种算法可以根据PRG的前i位推测出后面的n-i位。在SMTP协议中，明文头是“from:” , 攻击者可以用这段已知的明文与截获的密文做异或得出PRG输出的前i位，再根据预测算法得出完整的密钥，再与密文异或得出明文
图 37

严格定义PRG是可预测的：
存在“有效”算法A，对PRG的前i位做计算，输出的值与PRG的第i+1位相同的概率大于 $1/2+\epsilon, (\epsilon \ge 1/2^{30})$ , $\epsilon$ 大于 $1/2^{30}$ 时是不可忽略的
图 38
图 39

不安全的PRG例子

线性同余法的PRG

可忽略和不可忽略
图 42
图 43

针对一次性密码本和流密码的攻击

两次密码本攻击

流密码的密钥一旦使用两次就不安全
图 44
图 45
图 46

WEP还有一个问题就是它的PRG使用的是RC4，它的不可预测性是较弱的，存在有效算法可以从四万帧中恢复PRG的输出
图 1
图 2

完整性攻击

一次性密码本和流密码都只保护数据的机密性，但不保证完整性，攻击者可以修改将密文与攻击者的置换密钥做异或从而定向影响明文，这种攻击无法被检测出来
图 3
图 4

流密码实际应用

图 5
图 6

现代流密码：eStream

eStream支持5种PRG，这里讲其中一种，这种PRG的输入除了种子（密钥）还有一个随机数，好处是不用每次更换密钥，因为输入还包括随机数，整体是唯一的
图 7

eStream中同时支持软硬件的流密码Salsa20

图中的 || 并不是简单的拼接。这个PRG首先构造一个64kb的字符串，里面包含k，r，i（从0开始），通过多次一一映射h，最后与原字符串进行加法（不是异或）得出输出
图 8
图 9

PRG的安全定义

PRG的输出与均匀随机变量的输出不可区分
图 10

统计测试

为了定义不可区分，首先引入统计测试，统计测试是一个算法，输入值是“随机数”，输出0表示不是真随机数，1表示是真随机数
图 11

上图的例子1，这个统计测试输出1的情况当且仅当随机数中0和1的个数差小于等于随机数的长度开根号乘以10

统计测试算法有好有坏，可能并不随机的字符串也认为是随机的。所以我们需要评估统计测试算法的好坏

我们定义一个变量叫做优势，优势是统计测试算法相对于伪随机数生成器的，优势越接近1，统计测试算法越能区分伪随机数和真随机数

图 13
图 14

PRG的密码学安全定义

PRG是安全的当且仅当不存在有效的统计算法，它的优势是不可忽略的。即所有统计算法都认为PRG的输出是真随机数

但是，我们不能构造一个PRG并证明PRG是安全的，即不存在有效的统计算法。但是我们还是有大量的PRG候选方案

图 15

我们可以证明当PRG是可预测时，PRG是不安全的
图 16
当存在一个好的预测算法和好的统计测试算法，如下图。那么统计测试算法可以以一个不可忽略的 $\epsilon$ 分辨出伪随机数和真随机数
图 17
姚期智证明了上面命题的逆命题也成立，即当PRG是不可预测时，PRG是安全的
图 18

不可区分的更通用的定义如下
图 19

语义安全

什么是安全的密码？

攻击者不能从密文中恢复密钥
攻击者不能从密文中恢复明文

香农认为不能从密文中获得任何关于明文的信息才是安全的密码

图 20

香农的完美保密性定义约束太强，可以用计算不可区分代替
图 21

一次性密码本的语义安全

定义语义安全的的方式是通过两个实验，攻击者发送两个明文信息，挑战者（应该是被挑战者）随机选取密钥，做两次实验，第一次实验加密第一个信息，第二次实验加密第二个信息，攻击者判断密文对应的明文是哪个
图 22
上图定义了语义安全的优势，等于实验0中攻击者输出1的概率和实验1中输出1的概率之差的绝对值。简单理解一下，假如攻击者不能区分两次实验，那么实验0和实验1的输出1的概率是一样的，那么攻击者的优势为0，不能区分两次实验，意味着加密算法是语义安全的；如果攻击者能区分实验0和实验1，那么概率差不可忽略，攻击者有一定的优势区分两次实验
图 23
图 24

事实上，一次性密码本不仅是语义安全的，而且是完美保密性的
图 25

安全的PRG可以构成语义安全的流密码

图 26

我们做两次实验证明流密码的语义安全，第一次使用伪随机数生成器，第二次使用真随机数
图 27
图 28
图 29

分组密码

分组密码也属于对称密码，将明文分解成固定大小的分组，使用密钥加密成同样大小的密文
图 30
分组密码的加密过程是将密钥扩展成多个，使用轮函数多次计算分组得出密文
图 31
图 32

PRPs和PRFs

K表示密钥空间，X表示明文空间，Y表示密文空间
给定密钥后，伪随机置换的加密函数是一个一一映射，也就意味着存在解密函数。伪随机置换和分组密码十分相似，有时候会混用术语
图 33
图 34

安全的PRFs

Funs[X,Y]表示所有从明文空间到密文空间的真随机函数的集合，易知这个集合大小等于明文空间大小的密文空间大小次，而伪随机函数的集合大小由密钥决定，一个密钥决定了一个伪随机函数，一个安全的PRF与真随机函数不可区分
图 35
图 36
图 37
上图的G问题在于x=0时，输出固定了，攻击者可以通过x=0时的输出是否为0来判断他在和真随机函数交互还是伪随机函数，因为x=0，输出为0的概率实在太低了，等于密文空间的倒数
图 38
可以使用安全的PRF来构造安全的PRG

DES

DES的轮（回合）函数使用的是Feistel网络，核心思想是每个分组2n bits，右边n bits原封不动变成下一层分组左边n bits，左边n bits经过伪随机函数转换再和右边n bits异或变成下一层右边n bits
图 39
易知这个网络是可逆的，注意，不要求伪随机函数是可逆的
图 40
图 41

定理：如果伪随机函数使用的密钥是相互独立的，那么Feistel网络是一个安全的PRP
图 42
回合函数f由F根据回合密钥推导出来，回合密钥由主密钥推导得来，IP和IP逆是伪随机置换，和DES安全性无关，仅仅是标准要求
图 43
图 44
图 45

线性函数：函数可以表示成矩阵乘以入参
图 46
如果所有的置换盒子都是线性的，那么整个DES就是线性的，因为只有DES算法中只有置换盒子可能是非线性的，其它就是异或、位移等线性运算。如果是线性DES，那么存在一个矩阵B，DES可以写成B乘以一个包含明文和回合密钥的向量
图 47
图 48

针对DES的攻击

密钥穷举攻击

给定一些明文密文对，找到一个密钥使得明文密文配对，这个密文极大概率是唯一的
图 49
图 50

为了抵抗穷举攻击，衍生出了3DES
图 51

2DES存在安全性问题
图 52

针对分组密码的攻击

旁道攻击

通过测试加解密的时间或者功耗来推测密钥

错误攻击

通过外部手段影响加解密硬件，比如提高时钟频率、加热芯片，使得加密的最后一回合发生错误，根据错误信息可以推测出密钥
这两种攻击需要先窃取到硬件，比如上图的IC卡

图 53

线性和差分攻击

同样是需要给定明文密文对，推测密钥，比穷举攻击效率更高

加密算法中使用了线性函数导致下面等式以一个不可忽略的概率成立
图 54
图 55
图中的MAJ表示majority
图 56

量子攻击

图 58
图 59

AES

AES基于代换置换网络构建，和Feistel最大的区别在于，在这个网络的每一回合函数会影响每一位bit
图 60
图 61
图 62
图 63
图 64
图 65
图 66

使用PRGs构造分组密码

分组密码实质是PRP，首先考虑能不能使用PRG构造PRF
图 67
图 68
图 69
图 70
图 71
使用安全的PRG可以构造一个安全的PRF，但是并不实用
图 72
有了安全的PRF，我们可以使用Luby-Rackoff定理转换成PRP，因此可以使用PRG来构造分组密码，但是不如AES启发性PRF实用

使用分组密码

图 1
图 2
很显然，真随机置换空间和伪随机置换空间大小一样，所以它是安全的PRP
图 3
这个PRP不是安全的PRF，因为明文空间太小了
图 4

使用一次性密钥的分组密码

图 6
图 7

ECB的问题在于相同的明文会加密成相同的密文，攻击者可能不知道明文内容，但也会从中学到明文的一些信息
图 8
攻击者来挑战算法，本来不应该知道两张加密图片的区别，但是ECB将头发加密成了很多1，头发又重复出现，这样密文就会出现很多1，攻击者就能根据这个区别分辨两张图片

图 9

ECB被用来加密长于一个分组的消息时不是语义安全的
图 1

安全的电子密码本是为每个分组生成一个随机密钥进行加密，类似于AES的密钥扩展
图 3
图 4

使用密钥多次利用的分组密码

图 5

密钥多次利用的分组密码的选择明文攻击就是进行多次的语义安全实验（CPA安全）
图 6
图 7

确定的加密对于选择明文攻击不可能是语义安全的，所以多次使用一个密钥加密时，相同的明文，应该产生不同的输出，有两种方法。

第一种：随机化算法
图 8
图 9

第二种：基于新鲜值的加密

新鲜值不必随机但是不能重复
图 10
随机化的新鲜值和上面的随机化算法是一样的

基于新鲜值的加密的选择明文攻击下的安全性
图 1
图 2

密钥多次利用的运行方式（CBC）

CBC：密码分组链接模式
图 3
图 4
图 5
L是加密的明文长度，单位是分组。q是在CPA攻击下，攻击者获得的密文数，现实意义是使用某个密钥加密的明文数量
图 6
图 8
图 9
图 10
图 11

密钥多次利用的运行方式（CTR）

CTR：计数器模式

CTR不使用分组密码，使用PRF足够
图 12
图 13
图 14
图 15
图 16
图 17

信息完整性

本节先考虑信息完整性，不考虑机密性。信息完整可以保证公开信息没有被篡改，例如广告投放商不在乎广告的机密性，但在乎广告有没有被篡改

MACs

图 9

图 10

CRC是循环冗余校验算法，为检测信息中的随机发生的错误而设计，并非针对恶意错误

安全的MACs

图 11
图 12
图 13

图 15

图 16

MAC可以帮助抵御数据篡改，但是无法抵御认证消息的交换

构造安全的MAC

可以用安全的PRF来构造安全的MAC
图 17

但是，PRF的输出不能太短，不然攻击者能以一个不可忽略的概率猜出消息认证码

图 18

图 19

不等式右边 1/|Y| 是因为攻击者可以猜

图 20

PRF的输出不能太短，同时为了增大输入空间，需要有一些新的构造，将小输入空间的PRF转换成大输入空间的PRF
图 21

图 22

如果PRF是安全的，那么截断PRF的输出，依然是安全的，当然，如果要用PRF构造MAC，不能截到太短

CBC-MAC和NMAC

图 23

n是底层PRF的分组大小

图 24

L是分组大小

图 25

这两种构造的最后一步都至关重要，没有最后一步，攻击者可以实施存在性伪造（扩展攻击）。
第二种构造的原因很简单，攻击者询问m的函数结果，将结果与w分别作为函数的密钥和明文（F公开），计算函数结果

图 26
图 27

第一种构造的原因
图 29

图 28

图 30
图 31
图 32
图 33
图 34

MAC padding

当数据的长度不是分组长度的倍数时，需要填充数据

全部补0会有出现存在性伪造
图 35

填充函数必须是一一映射的
图 36

ISO的这种填充方法，不管是不是分组长度的倍数都要进行填充

图 37

并行的MAC

CBC-MAC和NMAC将一个处理短信息的PRF转换成一个处理长信息的PRF，这两种算法是串行的

P是某个有限域上的乘法
图 38
图 39
图 40

一次性MAC

图 41
图 42
图 43
图 44

HMAC(略)

抗碰撞章节细说

抗碰撞

抗碰撞在信息完整性中扮演着重要角色。我们说MAC系统是安全的，如果它在选择信息攻击下，是不可被存在性伪造的。前面4种MAC构造是通过PRF或随机数来构造的，现在通过抗碰撞的哈希函数来构造MAC
图 45

抗碰撞：没有有效算法A，能以一个不可忽略的概率找到hash函数的碰撞值

图 46

可以用抗碰撞哈希函数和处理短信息的安全MAC组合成处理长信息的安全MAC
图 47
图 48

只用抗碰撞哈希函数也可以构造安全的MAC，而且不像之前的MAC需要密钥，但是需要一个只读空间用来存信息的hash值。这种方式非常流行
图 49

针对抗碰撞哈希函数的通用攻击（生日攻击）

针对分组密码的通用攻击是穷举攻击，抵御穷举攻击的方法是增大密钥空间；为了抵御生日攻击，哈希函数的输出也必须大于某个下界

下面这种攻击算法通常几轮就能找到碰撞值
图 50

生日悖论的证明

下面的证明在非均匀分布时，n的下界更低
图 51

通用攻击

图 52
图 53

使用Merkle-Damgard机制组建抗碰撞的哈希函数

图 54

下面的IV是永远固定的，写在代码和标准里的值，填充函数在信息长度是分组长度倍数的时候也会填充一个哑分组
图 55

这种机制流行的原因是只要小hash函数（即上面的压缩函数）是抗碰撞的，那么大hash函数也是抗碰撞的

构建抗碰撞的压缩函数

使用分组密码来构建压缩函数，将信息作为密钥。SHA函数都使用了Davies-Mayer压缩函数
图 56
图 57
图 58

另外一类压缩函数是由数论里的困难问题构建的，这类压缩函数的抗碰撞性规约于数论难题，也就是说破解了压缩函数的抗碰撞性也就破解了数论难题。但是这类压缩函数很少使用，因为分组密码更快
图 60

SHA256

使用了Merkle-Damgard机制和Davies-Mayer压缩函数，底层分组密码用的是SHACAL-2
图 59

HMAC

图 61
图 62
图 63
图 64
图 65

针对MAC验证时的计时攻击

图 66
图 67
图 68
图 69

认证加密

到目前为止,我们了解了机密性和信息完整性, 我们将构建同时满足这两种性质的密码
图 70

机密性: 在选择明文攻击下满足语义安全
机密性只能抵抗攻击者窃听而不能抵抗篡改数据包

客户端加密数据后通过网络发送给服务器, 服务器解密后分发至对应端口
图 71

如果没有保证完整性, 那么攻击者可以拦截客户端的数据包, 把端口改成自己能控制的服务器的端口
图 72

可以抵抗CPA攻击的CBC分组密码不能抵抗篡改数据包, 攻击者可以简单地修改IV从而修改加密后的端口
图 73

攻击者甚至不用进入服务器, 直接利用网络来攻击。在CTR模式下，攻击者截获数据包，将加密的校验和与t异或，将加密的数据与s异或。CTR模式的特点是对密文异或，解密后等于对明文异或。攻击者重复很多次攻击，直到得到足够数量的合法的t、s对，从而恢复数据D（插值法？）
图 1

这种攻击叫做选择密文攻击。攻击者提交他选择的密文，是由他想解密的密文所推出的，然后看服务器响应，攻击者可以从中学到明文的一些信息。重复这个操作，用许多不同t、s值，攻击者可以还原明文

选择明文攻击下的安全不能保证主动攻击（前面两种攻击）下的安全
如果要保证信息完整性但不需要机密性，使用MAC
如果同时保证信息完整性和机密性，使用认证加密模式
图 2

认证加密定义

目标：提供选择明文攻击下的语义安全和密文完整性
图 3

密文完整性：攻击者不能造出合法的密文
图 4

CBC是选择明文攻击（CPA）下的安全密码，它的解密算法从不输出bottom符号，所以它不能直接被用作认证加密
图 5

认证加密不能抵抗重放攻击
图 6
图 7

图 8

选择密文攻击下的安全

攻击者的能力是既能选择明文攻击也能选择密文攻击，也就是说既能拿到想要的明文的加密结果，也能拿到想要的密文的解密结果
图 9

攻击者选择的密文不能是CPA的返回
图 10

CBC密码不是选择密文安全的，因为在选择密文时，通过对IV异或修改CPA的返回，同时由于CBC的特性，CCA的返回时对明文的异或，这样攻击者可以以1的优势赢下语义安全实验
图 11

如果密码能够提供认证加密，那么它就是选择密文安全的
图 12
图 13

所以认证加密能够选择密文攻击，但是不能防止重放攻击和旁道攻击
图 1

认证加密直到2000年才被正式提出，在这之前，已经有CPA安全的密码和安全的MAC，当时的工程师想将两者组合，但不是所有的组合可以作为认证加密
图 1

图 2

图 3

SSH的MAC签名算法的输出会泄漏明文中的一些位；
SSL的加密和MAC算法之间会有一些不好的互动导致选择密文攻击。IPsec无论怎么组合CPA安全的密码和安全的MAC都可以作为认证加密。SSL的特点是MAC-than-ENC，IPsec的特点是ENC-than-MAC
图 4

这几种认证加密都支持AEAD（认证加密与关联数据，例如ip报文的报文头是关联数据不加密，报文体用加密，整个报文需要认证）。MAC对整个报文使用，加密只对报文体使用

图 5

aad是需要认证、但不需要加密的相关数据，data是需要认证和加密的数据
图 6

图 7

直接从PRP构造认证加密

图 8

OCB比前面几种认证加密快的多，但没有被广泛使用因为各种各样的专利
图 10

认证加密的例子

图 11
图 12
图 13
图 15

图 16
图 17

针对认证加密的攻击

图 18
图 19
图 20
图 21
图 22
图 23
图 24
图 25
图 26
图 27

图 28
图 29
图 30

零碎

本章讲对称密码的一些零碎

密钥推导

KDF：key drivation function
源密钥由硬件随机数生成器生成或者密钥交换协议生成
图 31

CTX：参数上下文，每个进程的ctx不同
当源密钥服从均匀分布，我们使用PRF来作为密钥推导函数（其实就是用PRF作为伪随机数生成器）
图 32
图 33

当源密钥不服从均匀分布，那么伪随机函数的输出看起来就不随机了，源密钥不服从均匀分布的原因可能是密钥交换协议的密钥空间的子集是均匀分布，或者伪随机数生成器有偏差
图 34

构建KDF的机制

先提取再扩展

因为源密钥可能不是均匀的，我们使用一个提取器和一个随机选择的固定的但可以不保密的盐值将源密钥转换为服从均匀分布的密钥k，然后再使用PRF扩展密钥
图 35

HMAC既用于PRF进行扩展，又用于提取器
图 36

基于密码的KDF

PBKDF通过多次迭代哈希函数推导密钥
图 37

确定性加密

确定性加密总是把给定明文映射到同一个密文。

为什么需要确定性加密？假设有个加密数据库和服务器，服务器用k1加密索引，用k2加密数据，如果加密是确定的，服务器请求数据时可以直接使用加密后的索引作为查询条件请求数据
图 38

确定性加密有致命缺点就是不能抵御选择明文攻击，攻击者看到相同的密文就知道他们的明文是相同的
图 39
图 40

解决方法是不要用同一个密钥加密同一个消息两次，要么密钥从一个很大空间随机选择，要么明文就是唯一的，比如说用户id
图 41

确定性加密的CPA安全

在标准的选择明文攻击实验基础上，Chal不会给相同的m0加密，不会给相同的m1加密。注意上面的图40不是标准的确定性加密的CPA实验，因为攻击者两次查询的m0都是同一个
图 42

一个常见的错误是，固定IV的CBC不是确定性CPA安全的， $0^n1^n$ 表示消息有两个分组，第一个分组全0，第二个分组全1
图 1

固定IV的CTR也是不安全的
图 2

可以抵御确定性CPA的确定性加密

确定性加密是需要的，但是不能抵御选择明文攻击，因为攻击者看到两个相同的密文就知道了对应的明文是一样的。我们对确定性加密降低选择明文攻击的能力，加密者不使用一个密钥多次加密同样的明文，这样叫确定性CPA。
图 3

构造1：合成的IV（SIV）

CPA安全的密码会有一个随机值，我们用PRF生成这个随机值
图 4

SIV天然提供密文完整性，不需要MAC就能作为DAE（确定性认证加密），例如SIV-CTR
图 5
图 6

当需要确定性加密，特别是明文很长时，适合用SIV，如果明文很短，比如说少于16个字节，可以用构造2

构造2：仅仅使用一个PRP

实验0，攻击者看到q个随机值，实验1中，攻击者也看到q个随机值，两次实验的结果的概率分布是一样的，攻击者无法区分。这种构造不能保证密文完整性。同时只能加密16个字节
图 7

我们先考虑如何将PRP扩展成一个大的PRP
EME有两个密钥K，L，L是由K推出的。先为每个分组用L推导出一个密码本作异或，然后用PRP加密得到PPP，将所有PPP异或得到MP，再用PRP加密MP得到MC。然后计算MP异或MC，得到另外一个密钥M用于推导更多密码本，分别对PPP异或得到CCC，然后把所有这些CCC异或得到CCCO，再用PRP加密再异或密码本
图 1

现在考虑增加完整性
图 2
图 3

微调加密（Tweakable encryption）

先以硬盘加密问题引入微调加密，
硬盘扇区大小是固定的，明文和密文空间必须一致，我们最多可以使用确定性加密，因为随机性加密需要额外空间来放随机数，完整性需要额外空间放认证码
定理：如果确定性CPA安全的密码的明文空间和密文空间一样，那么这个密码一定是个PRP
图 4
图 5
图 6
图 7

这个微调分组密码的安全实验与常规的分组密码安全实验区别在于，在常规分组密码中，攻击者只能与一个置换进行互动，目标是分辨自己在和伪随机置换交互还是在和一个真随机置换交互。而在微调分组密码的安全实验中，攻击者与|T|个随机置换交互，目标是区分这|T|个随机置换是真是伪
图 8
图 1
图 2
图 3
图 4
图 5

保格式加密（Format Preserving encryption）

pos机刷卡时，我们希望卡号只在终端和银行可见，但是中间又有些服务商也想得到"卡号"，我们可以用将卡号加密成卡号格式的密文。
图 6
图 7

我们截断使用PRF，明文后面补0（例如AES就补到128位），密文截断，然后带入Luby-Rackoff构造PRP
图 9
图 10
图 11

密钥交换

现在我们知道两个用户可以通过共享一个密钥来保护通信数据，问题是，这两个用户如何产生共享密钥，这个问题将把我们带入公钥密码的世界。我们先看一些玩具性质的密钥交换协议。
图 12
图 13
图 14
图 17
图 18

能否设计出可以抵御窃听和主动攻击的没有可信第三方的密钥交换协议？可以的，这就是公钥密钥的出发点
图 19

不需要TTP的密钥交换

首先考虑攻击者只能窃听不能篡改消息，能不能只使用对称密码体系的算法来实现不需要TTP的密钥交换？
图 20

可以的，首先给出puzzle定义：需要花一些功夫解决的问题。例如已经给出AES密钥的前96位，明文固定，那么枚举 $2^{32}$ 个可能的后32位密钥可以找到能正确解密
图 21

Alice准备 $2^{32}$ 个puzzle，全部发给Bob，Bob选择一个然后开始枚举，只要解密出的原文开头包含"Puzzle", 对应的k作为共享密钥，x发送给Alice，Alice就知道Bob选择了哪个
图 22

这个协议不实用但是有一个很好的想法，参与者花费线性的时间，而攻击者必须花费平方的时间，当攻击者想破解这个协议，有一个“平方鸿沟”横亘在参与者与攻击者的工作之间。
只用对称密码体系，我们不能建立一个更大的“鸿沟”
图 23

我们需要具备非常特殊性质的函数，为了构建这些函数，我们必须依赖某些代数

Diffie-Hellman协议

这是第一个实用的密钥交换机制。
同样，我们考虑攻击者只能窃听不能篡改。我们尝试建立参与者与攻击者之间的指数级鸿沟

Diffie-Hellman协议开创了密码学的新纪元，现在不仅仅是关于开发分组密码，而且是关于设计基于代数的协议
图 24
图 25

下面有张表是不同密钥长度的分组密码安全性等价于对应模数的DH函数安全性，如果用椭圆曲线，模数可以更小
图 26
图 1

上面的协议当存在主动攻击（中间人攻击）时就不安全
图 2

事实上，上面的协议也可以改成无交互的
图 3

一个开放的问题，两个参与方的密钥交换使用DH即可，三个参与方的密钥交换使用Joux提出的方法，四个及以上还没有有效方法
图 4

公钥加密

这是另外一种密钥交换的方法
图 5
图 6
图 7

在公钥加密中，没有必要赋予攻击者实施选择明文攻击的能力。因为在对称密钥系统中，攻击者必须请求他选择的明文的加密，而在公钥系统中，攻击者拥有公钥，所以他可以自己加密任何他想加密的明文，他不需要Chal的帮助来计算他选择的明文的加密。因此在公钥的设定中，选择明文攻击是与生俱来的，没有理由给攻击者多余的能力去实施选择明文攻击（公钥加密也是随机性的，每次密文不同）
图 8
图 9

可以抵抗窃听但也不能抵抗中间人攻击
图 10
图 11

图 12

数论简介

图 13
图 14
图 15
图 16
图 17
图 19
图 20

扩展欧几里得算法是已知最有效的求元素模逆的方法（也给了我们求模线性方程的方法）
图 21

注意这里是n，不是N，n=logN
图 22

费马小定理和欧拉定理

费马小定理给了我们另一个计算模质数逆的方法，但是与扩展欧几里得算法有两个不足，首先它只能用在质数模上，其次算法效率更低
图 24

我们可以用费马小定理以极大概率生成一个随机质数（期望是几百次迭代），这是一个简单但不是最好的方法
图 25

欧拉证明了 $Z_p^*$ 是一个循环群(p是素数)，也就是 $\exist g\in (Z_p)^*$ 使得 $ {1,g,g^2,g3,…,g^{p-2}}=(Z_p)*$
图 26

有限子群的阶必然整除有限群的阶
图 27

欧拉定理，费马小定理的直接推广，适用于合数
图 28

模高次方程

图 29
图 30
图 31

0也是二次剩余，所以有(p-1)/2+1
图 32
图 33

《信息安全数学基础》P146，证明当p是形如4k+3的素数时，解的形式如下。这里Dan讲了p不是这种形式的素数时仍然是有有效的随机算法来求解
图 34
图 35

当模数是合数时且指数大于1时，同余式的解并不好找
图 36

一些算法

分组用32位表示是为了乘法不溢出
图 37
图 38
图 39
图 40

指数运算非常慢
图 41

模运算的一些难题

图 42

质数模的难题

图 43
图 44
图 45
图 46

合数模的难题

$Z_{(2)}(n)$ 表示两个位数相同的质数乘积的集合
图 47
图 48

基于陷门置换的公钥加密

图 1
公钥密码两个作用，一是会话建立（即对称密钥交换），二是非交互式应用
图 2
图 3
图 4
图 5
图 6
图 7

选择密文攻击（CCA）下的安全，有时可以缩写成选择密文攻击下的不可区分性（IND-CCA）

当攻击者可以篡改密文时，将以优势1赢下这个CCA游戏
图 8

构建CCA安全的公钥加密系统

陷门函数特点是单向的，只有私钥持有人才能做逆向计算
图 9
图 10
图 11

单向陷门函数只加密一个随机值，随机值用来生成对称密钥，单向陷门函数的私钥持有人可以恢复随机值进而恢复密钥
图 12
图 13

不能直接用单向陷门函数加解密明文，因为算法是确定的，就不可能是语义安全的，也会存在许多类型的攻击
图 14

构建一个陷门函数

本节构建一个经典的陷门函数叫做RSA
图 1

随机选取 $Z_N$ 中的随机元素，这个元素很可能也在 $Z_N^*$ 中，即该元素很可能是可逆的
图 2
图 1
图 2
（虽然x大概率是可逆的，但是如果不可逆怎么办？）
图 3

单向陷门函数是安全的，对称密码可以提供认证加密，H是random oracle，即H是某个从 $Z_N$ 映射到密钥空间的随机函数。那么这个公钥系统就可以抵抗选择密文攻击
图 4

不要直接用RSA来加密明文！！！因为RSA是确定性的函数，因此不可能是语义安全的
图 5
图 6
~~（直接用RSA加密密钥会被破解，但是ISO标准是用RSA加密密钥的哈希函数原项，破解出原项再hash一下就得到了密钥，这不是一样的吗？）~~ 对称密钥的空间大小远远小于RSA的明文空间

PKCS1

ISO标准不是RSA在实际中的应用。实际使用是将对称密钥扩展然后用RSA加密
图 7
图 8
图 9
图 10

解决方法是，服务器解密后发现开头不是02，就认为明文只是个随机值而不是包含密钥的明文，继续协议就会发现密钥不一致从而结束会话（最常用的PKCS1）
图 11

图 12
图 13
图 14
图 15

RSA的安全性

如果已经知道N的因式分解，那么可以用中国剩余定理求解x
图 16

计算e次根一定要因式分解吗？如果没有其它方法就说明了一个reduction（规约）：
任何有效的计算模N的e次根的算法都是有效的因式分解算法
图 17
图 18
图 19
图 20

实际应用中的RSA

最小的公钥e是3，可以但推荐还是65537。
RSA-CRT（带中国剩余定理的RSA）。RSA的加密很快但是解密很慢
图 21
图 22

RSA数学上是正确的，但是如果没有较好实现，会出现各种旁道攻击
图 23
图 24

防火墙刚启动时种子数量少导致伪随机数生成器重复生成p，导致网络上许多设备的p相同
图 25
图 26

ElGamal

前一节讲了基于陷门置换函数的公钥加密系统，这节讲基于Diffle-Hellman协议的公钥加密系统
图 27
图 28
图 29
图 30
图 31
图 32
图 33
图 34
图 35

ElGamal如果不做预计算，加密会比解密慢，但是因为g是固定的，意味着加密可以做预计算，当内存足够时加密是比解密快的。但是内存不够，不能预计算时，RSA更快，因为只做一次指数运算
图 36

ElGamal安全性

这个计算Diffle-Hellman假设对于分析ElGamal系统的安全性并不理想
图 37
我们引入更强的哈希Diffle-Hellman假设，更强假设的意思是，攻击者的能力更强，但是我们提出的某个论断仍然成立
图 38
图 39
图 40
图 41
语义安全是不够的，我们真正想要的是选择密文安全。
为了证明选择密文安全，我们引入一个更强的假设叫做交互Diffle-Hellman假设
图 42