现代密码学第二章阅读笔记
本章大部分证明已略去，需要的读者请自行翻阅原书，或者可在评论区进行讨论。
随机数生成
现代随机数生成算法共以下两步：
- 得到一个高熵的数据池
- 处理高熵数据用以生成比特流
高熵数据池的构成需要不可预知的数据来源，如外部输入和物理现象，前者可以是网络事件的延迟、后者可以是热放射周期。
处理高熵数据以生成随机比特流的正式方式在以后讨论，此处仅简单介绍一种方法：假设数据池中有一不随机比特序列，其中 1 的出现概率为 p，0 出现的概率为 1 - p；此时我们选择当序列中出现 “01” 时输出 0、出现 “10” 时输出 1 (其余情况不输出)，便可保证输出的比特序列是均匀的。
注意，密码学中随机数生成器是有明确要求的，必须使用“为密码使用设计”的随机数生成器而不是通用随机数生成器，比如C语言中 stdlib.h 里的函数 rand( ) 并不满足密码学使用。
2.1 定义
- $\mathcal{M}$：明文空间
- $\mathcal{K}$：密钥空间。Gen 可能生成的所有密钥集合
- $\mathcal{C}$：密文空间。Enc 可能生成的所有密文集合
- Gen：密钥生成算法。根据某些分布生成密钥 k 的概率性算法
- Enc：加密算法。输入$k \in \mathcal{K}$和$m \in \mathcal{M}$生成密文 c 的概率性算法，写作 $c \leftarrow Enc_k(m)$ (当为确定性算法时写作 $c:= Enc_k(m)$)
- Dec：解密算法。输入$k \in \mathcal{K}$和$c \in \mathcal{C}$生成明文 $m \in \mathcal{M}$ 的算法。满足 perfect correctness 的 Dec 可称为确定性解密算法，同时可记作 $m \leftarrow Enc_k(c)$
- perfect correctness：对于所有 $k \in \mathcal{K}$和$m \in \mathcal{M}$ 以及任何 Enc 生成的 c，可保证 $Dec_k(c) = m$的概率为 1.
- $K$： 表示 Gen 生成密钥取值的随机变量
- $M$：表示被加密明文的随机变量，需要独立于 $K$
- $C$：表示 Enc 输出密文的随机变量
- $\mathrm{Pr}[K = k]$：Gen 生成的密钥为 k 的概率
- $\mathrm{Pr}[M = m]$：明文取值于 $m \in \mathcal{M}$ 的概率
- $\mathrm{Pr}[C=c]$：密文等于固定值 c 的概率
(1) Perfect Secrecy
假定敌手知道 $M$ 的概率分布，即敌手知道不同信息被发送的概率，同时敌手知道使用的加密方案，唯一不知道的是通信双方共享的密钥。敌手可窃听到通信双方的交流内容，即该攻击方式为仅密文攻击。
对于可实现完全保密(perfect secret)的密码方案，攻击者窃听到的密文需要对其识别明文没有任何帮助，即以被观察到的密文为条件，明文 $m \in \mathcal{M}$被发送的后验概率应该和 m 被发送的先验概率没有区别，即密文不会揭露明文的任何信息。定义一(不可溯源) —-> DEFINITION 2.3
对于明文空间 $\mathcal{M}$ 的密码方案 (Gen, Enc, Dec)，当对于 $M$ 中所有的概率分布，每个明文 $m \in \mathcal{M}$ 和每个满足 $\mathrm{Pr}[C=c] > 0$的密文 $c \in \mathcal{C}$，有：
$$
\mathrm{Pr}[M = m | C = c] = \mathrm{Pr}[M = m]
$$
则可以说该密码方案是完全保密的，其中$c \in \mathcal{C}$是为了保证条件概率基于零概率时间。定义二(不可区分)
此定义基于密文分布不依赖于明文，即对于任意两个明文 $m, m’ \in \mathcal{M}$， m 被加密时的密文分布要和 m’ 被加密的密文分布相同，公式表示如下：
$$
\mathrm{Pr}[Enc_K(m) = c] = \mathrm{Pr}[Enc_K(m’) = c]
$$
其中概率是基于 $K$ 的选择和 Enc 的随机性，同时以上概率都只基于加密方案，并不依赖于 $\mathcal{M}$的底层分布。以上情景表示密文中不包含明文相关的任意信息，即攻击者无法区分 m 和 m’ 的加密形式。
定理一 —-> LEMMA 2.5
带有明文空间 $\mathcal{M}$ 的加密方案 (Gen, Enc, Dec) 是完全保密的，当且仅当 $\mathcal{M}$ 中的每个 m, m’ 和 $\mathcal{C}$ 中的每个 c 都满足定义二中的公式。
(2) 完美不可区分性
该部分为完全保密的另一等效概念。下面介绍敌对不可区分实验 $\mathrm{PrivK}_{\mathcal{A}, \Pi }^{\mathrm{eva}}$，其中 $\mathcal{A}$ 表示敌对方，$\Pi$ = (Gen, Enc, Dec) 表示明文空间为 $\mathcal{M}$ 的密码方案：
- 敌手 $\mathcal{A}$ 生成明文对 $m_0,m_1 \in \mathcal{M}$
- 使用Gen 生成密钥 k, 同时选定比特位 $b \in {0, 1}$。计算 $c \leftarrow Enc_k(m_b)$ 并将其发送至 $\mathcal{A}$，其中 c 为挑战密文
- $\mathcal{A}$ 生成比特 b’
- 实验的输出被定义为：1，当 b’ = b; 反之为 0.当实验输出为1 时我们称 $\mathrm{PrivK}_{\mathcal{A}, \Pi }^{\mathrm{eva}} = 1$ 并称 $\mathcal{A}$ 成功
定义一(不可溯源) —-> DEFINITION 2.6
我们称明文空间 $\mathcal{M}$ 的密码方案 $\Pi$ = (Gen, Enc, Dec) 为完美不可区分的当且仅当对于每一个敌手 $\mathcal{A}$ 都有
$$
\mathrm{Pr}[\mathrm{PrivK}_{\mathcal{A}, \Pi }^{\mathrm{eva}} = 1] = \frac{1}{2}
$$定理一 —-> LEMMA 2.7
加密方案 $\Pi$ 是完全保密的当且仅当其是完美不可区分的。
2.2 一次一密
我们定义 $a \oplus b$ 表示两等长二进制串 a 和 b 的逐比特异或。在一次一密方案中，密钥是和明文等长的独立字串，密文只需明文和密钥逐比特异或便可得到。正式定义如下：
给定整数 $\mathscr{l} > 0$，明文空间 $\mathcal{M}$，密钥空间 $\mathcal{K}$ 和密文空间 $\mathcal{C}$ 都等价于 ${0, 1}^l$ (长度 $l$ 的二进制串)
- Gen: 密钥生成算法根据均匀分布从密钥空间 $\mathcal{K} = {0, 1}^l$选择一密钥
- Enc: 给定密钥 $k \in {0, 1}^l$ 和明文 $m \in {0, 1}^l$ ，加密算法的输出为密文 $c := k \oplus m$
- Dec: 给定密钥 $k \in {0, 1}^l$ 和密文 $c \in {0, 1}^l$ ，解密算法的输出为明文 $m := k \oplus c$
从正确性来看，对于每个密钥 k 和每段明文 m 都有 $Dec_k(Enc_k(m)) = k \oplus k \oplus m = m$，即一次一密是有效的密码方案。
缺点
- 密钥长度需要和明文一致
- 密钥只能使用一次
2.3 完全保密的限制
总的来说，完全保密要求密码方案的密钥空间至少和明文空间一样大。(另一限制是密钥只能使用一次)
2.4 香农的定理
该定理首先密码方案 (Gen, Enc, Dec) 要求 $|\mathcal{M}| = |\mathcal{K}| = |\mathcal{C}|$，即三个空间大小一致，在此基础上当且仅当满足以下两点才可称该方案是完全保密的：
- 每个密钥 $k \in \mathcal{K}$ 都是以 $1 / |\mathcal{K}|$ 的概率被 Gen 选中的
- 对于每个明文 $m \in \mathcal{M}$ 和每个密文 $c \in \mathcal{C}$，存在唯一的密钥 $k \in \mathcal{K}$ 使得 $\mathrm{Enc}_k(m)$ 的结果为 c