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

素颜马尾好姑娘i 2023-01-21 02:23 15阅读 0赞

# 《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/][http_toc.cryptobook.us]

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

### **3.1 Pseudo-random generators ** ###

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

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

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

**形式化定义**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

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

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

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

![20210514095057787.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

与前文定义的语义安全模型类似，设计两个实验，随着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|描述的是敌手攻击可能有优势方案的概率减去无优势方案的概率，也是描述敌手成功概率的一种方式？此时其成功概率与比特猜测版本的语义安全定义类似。如果想要明白这个问题的答案，还需要从本书提到的语义安全定义说起,在本书Attack Game 2.1处，类似上文提到的，使用两个实验来描述敌手的优势，此时我们需要明确，这两个实验是独立的，并且敌手是具有相同攻击能力的，并非是同一个敌手发起的攻击。那么敌手的优势直接可以用两个实验中敌手输出1的差值来表示。此时，我们不要关注到底01代表的是敌手获胜还是失败的问题，我们只需要明白，敌手在这个两个实验中输出1的概率到底是多少。如果敌手没有优势那么敌手输出1的概率就是二分之一，当敌手具有优势时其输出1的概率的差值将一定不为0，而是受其优势影响的值。】

**安全定义：**

![20210514101948651.png][]

### 3.2 Stream cipher: encryption with a PRG  ###

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

**加密方案：**

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

![20210514102823546.png][]

**安全模型：**

![20210514102910980.png][]

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

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

![2021051522353632.png][]

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

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

*构造证明第一步：*

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

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

*构造证明第二步：*

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

*构造证明第三步：*

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]  ![20210515233436342.png][]

整个证明过程描述如下:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6][]

![20210515233959140.png][]

![20210515234022944.png][]

![20210515234054742.png][]

![20210515234117953.png][]

总结一下：

目的是证明3.3成立。

1.根据语义安全的标准定义，我们得到了PRG语义安全定义及等式：

![20210515234700689.png][]

2.由语义安全定义知道B的优势此时为![20210515235027261.png][]。

3.根据实验设计我们得到 p0 = Pr\[W0\] , p1 = Pr\[W1\]。

4.由上式得到3.3式是成立的。

**开放小问题：**

是否可以直接证明Game0 和 Game1 不可区分，达到证明安全的目的？

答：从上文我用蓝色 和 红色 字体讨论的部分可知，Game0 和 Game1可以理解为独立的两个游戏，那么由敌手优势的描述SSadv = |W1 - W0| 为可忽略的值来看，这不仅仅意味着敌手的优势是可忽略的，也意味着这两个游戏不可区分。

*单词表：*

stretche: <v.n> 伸展，延长，舒展；

bias:<n> <adj><vt> 偏见；偏斜

exploit: <vt>开发，开拓； <n>英雄事迹，奇遇

geared:<adj,n> 适应

cardinality<n> 基数，优势

property<n>性质，性能，所有权

urged to: 激励，怂恿

[http_toc.cryptobook.us]: http://toc.cryptobook.us/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221021/bb7fcde09d2a450a9a782a99eb0cdcde.png
[20210514095057787.png]: /images/20221021/a7bb7c25ecdf4f938f6ad49c93c25fad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221021/d339c4c8d3844094a3838a99d0b359cf.png
[20210514101948651.png]: /images/20221021/1412c5b60112470786d770e7805e042e.png
[20210514102823546.png]: /images/20221021/ec4eed9761f74072bcd412c32113dc22.png
[20210514102910980.png]: /images/20221021/b5792e83fdbd41b3a0d914944330eb5a.png
[2021051522353632.png]: /images/20221021/d410991859ce4b5da7d7d9ebdfb9fe5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221021/d9e1c92045bd488fabe9e19e728c1f2c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221021/d7d0751cf8cb47239fc10cee2fddbe29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20221021/ee35bb0354004fb98534f281cda5c81f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210515233223448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4,size_16,color_FFFFFF,t_70
[20210515233436342.png]: /images/20221021/59980c1a1e9749e0a73a300b9d783caa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6]: /images/20221021/221876c3dbed4850b4cc5fd828888465.png
[20210515233959140.png]: /images/20221021/473d4b219e3a4c36b2dda467e9ab5bed.png
[20210515234022944.png]: /images/20221021/bdf46e14f146483f9676690d2eab1110.png
[20210515234054742.png]: /images/20221021/59e3392cda6b450aa2395871ffd1bb11.png
[20210515234117953.png]: /images/20221021/e2784bd7a6774390a94460b89dee1c34.png
[20210515234700689.png]: /images/20221021/a163c3ab12d44feaac72fe42af9e719f.png
[20210515235027261.png]: /images/20221021/9c03c03d25304862a8309d02eb46d162.png