密码学专题| 二、伪随机生成器和安全加密方案

伪随机

伪随机是指对于任意多项式时间（PTT）的算法来说，对于一个长度为 l 的字符串，分辨出它是来自分布 \(D_l\) 的采样还是来自随机均匀分布 l 长度字符串，是不可行的。

因此可以定义出伪随机发生器：

定义一个多项式 l， G 为一个确定的多项式时间算法，满足输入一个种子 \(s \leftarrow {0,1}^n \)，输出一个长度为 l(n) 的字符串。G 是为伪随机发生器当且仅当 G 满足如下两个条件：

1. \(l(n) > n\)，否则没有伪随机可言。
2. 定义一个示性函数 D：\(D(X) = 1\) 当且仅当可以判断该随机字符串满足分布 X。并且记 \(R_m\) 表示长度为 m 的均匀随机分布。G 满足： \( | Pr[D(R_{l(n)}) = 1] - Pr[D(G(s)) = 1] | \le negl(n) \)

也就是说，伪随机数发生器是指，一个通过种子 s 生成长度为 l(n) 字符串的确定性算法，但是无法区分该字符串是否来自于l(n)长度的均匀随机分布。

伪随机数发生器在密码学中，有比较重要的意义。一个非常直观的概念就是可以将满足完美安全的一次一密算法改造成满足计算安全的实际可用的加密算法。这也是流加密算法的核心思想。试想，在计算安全的条件下，我们可以通过一个定长的随机数种子 s ，通过伪随机数发生器 G ，产生一个长度为 l(n) 的伪随机字符串，那么是不是可以直接使用这个字符串（也就是秘钥流）与明文进行按位异或，从而得到一个安全的计算安全的流加密算法。

伪随机数发生器存在的问题有：

1. 由于种子 s 的长度有限，因此实际输出的字符串空间相比均匀随机分布的空间相比是小很多的。因此s 必须足够的长。
2. 多项式时间限制，如果考虑一个计算能力无限的敌手，可以通过遍历整个 s 空间的方式来进行蛮力攻击，从而破解伪随机数发生器。也就是说，伪随机数发生器是计算安全而非完美安全的
3. 存在性存疑。除非引入一些假设，目前无法证明伪随机数发生器是存在的。当我们相信单向函数存在的时候，那么可以构造一系列伪随机数发生器。

防止已知明文攻击的计算安全加密方案

定长的计算安全加密方案

可以证明，在定长条件下，上文提到的加密方案是计算安全的。这里证明忽略：

令 G 是一个扩展因子为 l 的伪随机数发生器，则可以定义一个消息长度为 l 的定长计算安全加密方案如下：

1. Gen: 输入 \(1^n\) ，则 \( k \leftarrow \{0,1\}^n \)，也就是 k 是一个随机的秘钥。秘钥空间 \(|K| = 2^n \)
2. Enc: 输入秘钥 \( k \in \{0,1\}^n \)和明文 \( m \in \{0,1\}^{l(n)} \)，有 \( c = m \bigotimes G(k) \)
3. Dec: 输入秘钥 \( k \in \{0,1\}^n \)和密文 \( c \in \{0,1\}^{l(n)} \)，有 \( m = c \bigotimes G(k) \)

变长的计算安全加密方案

只需要引入一个可边长的伪随机数发生器即可：

G 是一个多项式时间的确定性算法，当且仅当 G 满足下面条件时，G 是一个可边长伪随机数发生器：

1. s 是一个定长字符串，l > 0 是一个整数，则 \(G(s,1^l) \) 是输出长度为 l 的字符串。
2. \( \forall s, l, l’, l \le l’, s.t. G(s,1^l) 是 G(s,1^{l’}) 的前缀\)
3. \(G_l(s) \overset{def}{=} G(s,1^{l(s)}) \)

流密码

• RC4 是一种流密码，其前面生成的比特存在偏移，应当丢弃。
• LFSR 线性反馈移位寄存器，仅使用线性反馈移位寄存器的流密码是不安全的。
• chacha20 等流密码算法 …

值得注意的是，即便是单次加密是计算安全的，也不保证使用相同秘钥进行多次加密是安全的。因此使用概率算法进行秘钥的概率生成是十分有必要的！为了防止这种攻击，可以引入初始向量 IV 。此时： \[ Enc_k(m) = IV || G(k, IV) \bigotimes m \]

防止选择明文攻击的计算安全加密方案

CPA 攻击是指攻击者 A 在协议的任意阶段，均有能力，构造 \(m_i\) 并得到 \( c_i = Enc_k(m_i) \)。他除了 k 不知道外，将 Enc 作为一个黑盒，可以任意构造输入和输出。

一个结论是加密方案必须是任何确定性的加密方案均不能防止 CPA 攻击。

另一个结论是任何在 CPA 安全下不可取分的对称秘钥加密方案，都出在 CPA 条件下不可取分的多次安全方案。并且允许直接构造任意长度的加密方案，而不会导致安全问题。

考虑一个伪随机函数 F\( F: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n \) 。其中第一个参数是秘钥 k ，将输入 x 映射到等长的输出 F(k,x) 去。其中 |K| = |X| = |F(K,X)|。当 K 确定时，定义偏函数 \( F_k(x) = F(k,x) \)

如果存在一个多项式时间的敌手 A ，定义一个判断器 D ，以及一个长度为 n 的均匀随机分布 f ，满足： \[ | Pr[D(F_k) = 1] - Pr[D(f) = 1] | \lt negl(n) \]

称 F 为伪随机函数。

难以证明伪随机函数的存在性，但是一般认为分组密码是一个伪随机函数。此时可以构造定长的基于伪随机函数的加密机制。

定长的基于伪随机函数的加密方案

这里构成了分组加密的最基本的思想，定义一个基于伪随机函数的加密方案 \( \Pi \):

1. Gen: 输入 \(1^n\) ，均匀随机选取秘钥 \( k \leftarrow \{0,1\}^n \) 作为秘钥
2. Enc: 输入秘钥 k 和明文 \( m \in \{0,1\}^n \)， \( c = r || m \bigotimes F_k(r) \)
3. Dec: 输入秘钥 k 和密文 \( c \in \{0,1\}^n \)， \( m = c \bigotimes F_k(r) \)

可以证明该方案在 CPA 下是计算安全的加密方案。

值得注意的是直接使用 \( F_k(m) \) 本身并不是安全的方案。

变长的基于伪随机函数的加密方案

此时引入了分组密码的工作模式的概念。选取更大的分组长度，可以提供更好的安全性。

• ECB: 电码本模式，此时 \(c = F_k(m_1) || F_k(m_2) || … || F_k(m_n)\) ，因此不具有安全性。
• CBC: \(c_0 = IV, c_i = F_k(c_{i-1} \bigotimes m_i )\)
• OFB: 输出反馈模式
• CFB: 密文反馈模式
• CTR: 计数器模式，可证明，随机计数器模式（ctr 随机选取）是CPA 安全的。

防止选择密文攻击的计算安全加密方案

CCA 指敌手 A 不仅可以访问黑盒 \(Enc_k\) 还能访问黑盒 \( Dec_k \)。但是 A 不能够提交挑战密文 \(c^*\)。

CCA 要求如果敌人需要取修改一个报文，那么要么得到一个非法密文，要么是一个和原始明文没有任何关系的明文的密文。

防止 CCA 的计算安全加密方案\(\Pi\)，需要在CPA 加密方案 \(\Pi^E\) 中引入消息认证 \(\Pi^M\) 来提供完整性保护。

1. Gen： 输入参数 \(1^n\),分别运行 \(Gen_E(1^n) 和 Gen_M(1^n)\)输出加密秘钥和完整性保护秘钥 \(k1 以及 k2\)
2. Enc: \( c \leftarrow Enc_{k_1}(m), t \leftarrow M_{k_2}(c)\)，输出 c||t
3. Dec: 验证 \( Verify_{k_2}(c,t) ==1 ? \)，而后输出 \( m = Dec_{k_1}(c)\) 或者 \( \perp \)。

通常，加密和认证是有下面几种方式组合起来的：

1. 加密和认证：不足够安全，认证方案可能泄露消息信息
2. 加密后认证：不保证是 CCA 安全的
3. 认证后加密：如果加密方案满足 CPA，认证方案满足产生唯一安全认证码，在该方案是 CCA 安全的
4. 认证加密方案：将加密和认证同时进行，GCM 等 AEAD 方案目前认为是最合理的。