《A Graduate Coursse in Applied Cryptography》chapter ２ Encryption （１）

心已赠人 2023-01-15 13:25 63阅读 0赞

# 《A Graduate Coursse in Applied Cryptography》chapter ２ Encryption （１） #

*原文教材：*

*        Boneh D, Shoup V. A graduate course in applied cryptography\[J\]. Recuperado de https://crypto. stanford. edu/~ dabo/cryptobook/BonehShoup\_0\_4. pdf, 2017.*

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

**2.1　Shannon ciphers and perfect security**

** 2.1.1  Definition of a Shannon cipher 香农密文的定义**

**           **Shannon cipher 香农密文的定义可以理解为一个宏观上的加密方案。

主要组成内容包括一对算法（加密算法E ；解密算法D），明文空间M，密文空间C，秘钥空间K。

两个算法满足以下的基本关系：

![20210509145100777.png][]

![2021050914511161.png][]

one-time pad: 一次一密

一次一密的方案非常容易理解，即为每次加密使用不同的秘钥，每次秘钥的长度大于等于待加密的明文长度，值得一提的是 “一次一密方案”是一种CPA安全的方案。

一次一密方案还有一些变种，例如变长度的一次一密方案等。

**2.1.2  Perfect Security**

完美保密是一种密码加密方案安全性的“金标准”，也是所有密码学方案安全性之形式化合法性的源头。

完美保密的形式化定义如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

我认为比较直观的理解方式就是通过加密明文m1 或者 明文m2 得到密文c 的概率是相同的，明文和密文之间是相互独立的关系。

该书此处给出了一个定理2.1描述了三种等价的完美保密的说法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

(1) 该方案是一个完美保密的方案； （2）对于任意的密文由明文加密得到都具有相同的概率

（3）如果随机的加密秘钥k 是均匀分布在秘钥空间上的，那么每一个对于明文随机加密的结果具有相同的分布。

对于完美保密这个重要概念而言，还发展出了一些进一步的描述方式：

（1）完美保密意味着窃听敌手不能从密文处获取任何关于明文的信息（即使是一些被精心设计的谓语或者断言），形式化描述如下：

![20210509153431209.png][]

（2）完美保密意味着从概率的角度描述，敌手即使获取了一部分密文，也不能获取关于该明文的任何信息，或者即使获取了一部分明文，也不能获取关于该明文的任何信息。

![20210509153645329.png][]

![20210509153702296.png][]

紧接着，从概率的角度观测完美保密定义。首先，我们假设秘钥的选取是均匀随机的，并且加密时对秘钥的选择不依赖明文，不将明文作为选择秘钥的参考，即秘钥和明文是相互独立的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

在k 与 m 的选择互为独立事件的条件下：

如果该方案是完美保密的，那么c 和 m 是独立的。等价的。如果c 和 m 是独立的，那么该方案是完美保密的。

证明过程在本书P12页首部。

**定理2.5 香农定理 **   如果一个加密方案是完美保密的那么，秘钥空间必须大于等于明文空间。

证明：基本假设K  < M ,目的是证明如果秘钥空间小于明文空间，则完美保密不存在。

首先我们看到完美保密的定义是：

![2021050916053942.png][]

其次，为了证明在K<M 的基础下，上式不成立，则我们证明如下两个式子成立：

![20210509161905877.png][]

首先，对于第一个式子是一定成立的，随机选一个秘钥k0，很容易得到式子2.1是成立的。

接着，我们选择另一个秘钥k1, 使用k1对密文c进行解密，得到如下内容：

![20210509162438996.png][]

由于使用秘钥k1 解密了 使用k0加密的密文，这一定导致能够获得的可能明文数量小于等于K的空间，并且小于M的空间。

此时，我们从除去S的M空间中选择一个明文m1, 如果存在某个秘钥k1，能够加密这条消息得到密文c，这将直接证明m1 是属于S的，与我们的前提条件不符合。

所以，没有任何一个秘钥加密m1能够得到密文c，所以等式2.2 满足。

**2.2 Computational ciphers and semantic security** 计算密文与语义安全

完美保密是一种非常强的安全性定义，在现实中往往难以实现，例如一次一密，总数据量膨胀的非常庞大，几乎无法实用。

针对这样的问题，只能将完美保密这个概念的安全性放宽，得到了语义安全的安全性定义，语义安全虽然不如完美保密的安全性强，但是目前来看足够实用了。

**2.2.1 Definition of a computional cipher**

计算密文的定义与香农密文定义类似，不过定义要更加具体，例如 要求秘钥，明文 ，密文均在一个有限域之中，而香农密文定义仅仅只说在空间中，其他没有需要特别注意的地方。

单词表：

take as: 把....看作是                 expressly: <adv> 清楚，明显

in advance :提前                       whatsoever: 无论怎样

tampere: 干扰，破坏                state：规定，陈述

but of course: 但当然                a couple of  : 两三个，一对

variable：可变的                      scenarios:<n> 方案，情节

substitution: <n> 替代               additive<n> 添加

elaborate<adj> 精心制作，煞费苦心的   predicate <n><v> 断言，谓语

characterizing<n> 描绘    sensible <adj,n> 明智的 合理的

conversely<adv> 相反的          lie in ：在于，睡觉，服从

occasionally<adv>偶尔，间或   convenient <v> 方便

[20210509145100777.png]: /images/20221022/241e325eade44153ac87161ba0c7e424.png
[2021050914511161.png]: /images/20221022/344e2192a0b64ad48b9e106bfee4ae23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221022/477baf4319944744b454aeadc5ddcc8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221022/c5005c82543342b39455f51ccc95af8b.png
[20210509153431209.png]: /images/20221022/78fa841996404305bbc969ed6ba4e698.png
[20210509153645329.png]: /images/20221022/c1d46f5101cc4f9b8b78331f809620e6.png
[20210509153702296.png]: /images/20221022/19261ecac17a4b3a8069f64f5e2f9237.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221022/05df6880bd6e45c583a6a1658534a63a.png
[2021050916053942.png]: /images/20221022/fb3afe8d3d3c402b9f1087ae1b69ba2e.png
[20210509161905877.png]: /images/20221022/0dfa496d8e2d421195ae26d538b8ff8a.png
[20210509162438996.png]: /images/20221022/023dfa8536d54a19be250831520ebf11.png