《A Graduate Coursse in Applied Cryptography》chapter 3 Stream ciphers （1）

2024-03-25 16:35:16

《A Graduate Coursse in Applied Cryptography》chapter 3 Stream ciphers （1）

原文教材：

Boneh D, Shoup V. A Graduate Course in Applied Cryptography[J].

该书项目地址（可以免费获取）：http://toc.cryptobook.us/

系列博客为对该教材的学习笔记（只包括我认为重要的东西）。

3.1 Pseudo-random generators

引言：由之前的一次一密加密方案，我们知道一次一密是能够实现完美保密的，但是缺点也很明显，每次需要存储与明文相等长度的秘钥。但是，在实际的应用中我们往往着重研究语义安全（完美保密的弱化概念）方案。允许秘钥长度小于明文的长度，然而，问题来了。符合语义安全的秘钥该如何生成？

问题：如何生成一个合适的短秘钥？或者说与一次一密中随机数秘钥相类似安全的的秘钥？

解决方案：伪随机数生成器（Pseudo-random generator）是一种生成随机数的工具，该工具以一个随机种子信息seed为输入，输出一个指定长度的随机数，即将随机种子信息S映射到随机空间L上。

形式化定义：

伪随机数生成器，将种子空间S映射到输出空间R。S 和 R 在此处是可预测长度的。一般情况下，我们对随机数生成器随机数的输入输出长度是预先控制的。如果伪随机数生成器G（S）输出的随机数与真正的随机数是计算不可区分的，那么我们就认为该随机数生成器是良好的、安全的。

安全性描述：（所有密码学工具都需要有安全性描述，数学困难问题原语一般不这么说）

凡是密码学工具都有其安全性模型与定义，而安全模型与定义的描述一般通过某种（类）敌手的攻击行为来描述，实际上安全模型是各类敌手恶意行为的抽象，此处该书定义PRG的安全模型（攻击游戏）为：

与前文定义的语义安全模型类似，设计两个实验，随着b = 0 或者1 ,敌手与不同的挑战者交互。定义W0事件为当运行的是实验0时输出1的概率，定义W1事件为当运行的是实验1时输出1的概率。显然，W0 我们可以认为是敌手失败的概率，W1我们可以认为是敌手成功的概率。那么，敌手的优势即为|W0 - W1|的概率。为什么？因为对于敌手而言，不论与这两个挑战者哪一个进行交互，其成功概率直觉上是1/2，如果敌手掌握了相关的秘密信息能够有效的区分两个实验的挑战者，那么其优势|W0-W1|一定是一个不可忽略的值。【这里有一个问题，为什么要这么定义W1与W0？为甚不定义W0为敌手在b=0时输出0的概率？此时该概率描述的是敌手在实验0下成功猜测的概率，W1为敌手在实验1下成功猜测的概率。如果这么定义W0与W1，而我们知道，实验1等价一次一密，敌手的优势为0。那么|W0-W1|描述的是敌手攻击可能有优势方案的概率减去无优势方案的概率，也是描述敌手成功概率的一种方式？此时其成功概率与比特猜测版本的语义安全定义类似。】

安全定义：

3.2 Stream cipher: encryption with a PRG

引言：当我们具有一个安全的伪随机数发生器后，我们就可以稳定的生成安全的秘钥了，然后就可以使用该秘钥实现加密了。

加密方案：

加密方选择种子s,使用秘钥生成器G(s)，生成秘钥然后运行一次一密算法，得到密文。解密方同样有相同的种子s,使用秘钥生成器G(s),生成秘钥然后解密，描述如下：

安全模型：

如果G是一个安全的PRG，那么流密码方案就是语义安全的。问题来了，如何证明该定理是成立的？

首先，我们要注意一个问题，我们的终极目的是证明该加密协议是安全的，由于该协议比较简单，直觉上我们知道该协议是从一次一密方案修改过来的，那么这个方案最可能与一次一密方案区别的地方就是秘钥的产生。如果这个秘钥生成器是安全的，那么我们就可以认为该方案也是安全的。这个安全定理的核心在于证明：敌手A攻击该加密方案的优势与存在一个敌手B攻击PRG的优势相同，即为下式：

那么，如何证明这个等式成立？或者说我们如何将这两个优势（概率）联系起来，并证明相等？这就是安全证明的核心内容。

直觉上，如何联系敌手A和敌手B，最为常用或者可能的方式就是，通过调用的方式，也就是常说的安全规约，如何构建这个过程是比较困难的。

构造证明第一步：

我们已经有了证明的目标，证明这两个概率相等就行了。此时，我们忘记安全规约等以前具备的可证明安全知识，我们就仅仅从一种比较自然的思路来考虑这个安全证明的过程。

考虑等式的左边，敌手A 对该具体的加密方案进行攻击，我们已经获得了关于语义安全的基本定义，语义安全定义如下：

上图只是一个标准的语义安全的游戏描述，但是具体的方案应该还有修改和变化。我们的方案与这个原始的语义安全定义还有一定的区别，最大的区别是我们这个流密码的加密方案

使用了伪随机数生成器G。所以我们得到两个不同的游戏Game0 和 Game1。在Game0中使用伪随机数生成器G，在Game1中使用一个真随机数。在Game0中，有效的刻画了敌手的行为，其攻击优势即为敌手的优势。在Game1中使用一个真随机数，很显然此处的方案就是一个一次一密方案，敌手此时不具备任何的优势（如果我们能证明敌手不能区分这两个游戏，那么该加密方案与一次一密不可区分，其实也能证明方案是安全的）。不过我们此时的目的是，证明该方案是语义安全的。

此时，我们已经将我们的方案与语义安全敌手A联系了起来。

构造证明第二步：

此时，我们考虑的右边部分，即为敌手B攻击我们加密方案PRG的过程。并且考虑到我们的最终安全证明目标，如果能用敌手B来调用敌手A，并利用敌手A和其自身的能力来攻击该加密方案，那么这个安全证明过程就很顺利了。如果敌手B能够借助敌手A去攻击该流密码加密方案，如果B不能成功，这也就意味着流密码加密方案是可以抵抗语义安全敌手的。至此逻辑闭环，证明逻辑闭合。但是，这里有一些细节问题，敌手B要能够准确、正确的调用A来攻击该流密码加密方案。

构造证明第三步：

综合构造证明的第一步与第二步，我们得到如下的证明结构：