《Introduction to modern cryptography》第10章小结

╰半夏微凉° 2023-03-01 12:34 6阅读 0赞

# 公钥密码学 #

## 公钥密码学基本定义 ##

一个公钥密码学协议由以下的三个部分组成：密钥生成，加密，解密

![20200725154451762.png][]

1. Gen 秘钥生成算法，根据输入的安全参数，输出为一对公私秘钥对（sk,pk）

2. Enc 加密算法，可以将公钥和明文作为输入，得到密文作为输出，可以直接理解为加密其实本质上是一种算法，同时加密算法应该具备算法的几个基本属性 通用性，确定性，有效性，有穷性，密码学术语中的算法都遵循这些性质。

3. Dec 解密算法，将私钥和密文作为输入，得到明文作为输出。

## CPA安全 ##

CPA（Chosen-Plaintext Attacks）选择明文攻击，也称为语义安全，这是最早提出的一种安全定义。其实可以理解为语言上的安全，即看起来的安全，看起来不可区分的安全，给定两个密文不能区分对应加密明文的不可区分安全。简而言之，就是说你无法通过语法、语言、观察判断密文与一个随机数的区别，也就意味着无法通过上述的方式判断密文和明文之间的对应关系。CPA实验形式化的描述如下：

![20200725161704373.png][]

CPA形式化描述如下：

1. 运行秘钥生成算法，得到密码学协议的公钥和私钥。

2. 敌手A 可以获得公钥PK，以及可以在明文空间选择两个不同的明文M0和M1，以及可以访问加密谕言机获得任意明文的密文。

3.随机选择b : 0 - 1 将对应的明文加密得到挑战密文CT。

4.敌手A输出一个比特b\`。

5.如果敌手猜测成功，则实验结束。

PS：值得注意的是，这里的加密不是由敌手来实现的，一般来说，我们定义这个给敌手生成挑战密文的角色为挑战者，也可称之为加密谕言机。本质上敌手完全可以自己加密，这是允许的也是现实的，因为CPA假定敌手已经掌握了公钥加密算法，公钥以及明文空间，敌手可以尝试自己加密任何他选择的明文，学习相关的知识。

### CPA不可区分安全定义 ###

![20200725162617698.png][]

CPA安全试验已经在上文描述完成，有个这个安全试验，进一步，我们可以定义CPA不可区分性安全定义，如果满足上述的定义10.3 则密码协议在CPA模型下，具有不可区分安全性。其实很简单，就是说一个PPT敌手A能够赢得这个游戏的概率小于等于二分之一 加 可忽略的函数值。这个从定义上看，也是非常好理解的。如果敌手没有任何的计算优势，那么他成功完成CPA实验的概率其实最多只有二分之一，现在要求他赢得这个实验的概率小于等于二分之一，则证明其实本质上敌手是不能完成这个实验的，另外还有一种描述方法，我们称之为优势，敌手赢得这个实验的优势，优势即为完成实验的实际概率减去二分之一，就是敌手完成实验的优势。

Tips:公钥加密无法实现完美保密这个属性，原因是非常简单的，因为存在一个可忽略的函数，即为敌手的优势，所以就无法实现完美保密：![Pr\[M=m|C=c\] = Pr\[M=m\]][Pr_M_m_C_c_ _ Pr_M_m].

Tips:所有的确定性加密均不能满足CPA安全，这是非常容易理解的，如果明文空间比较小，那么完全可以通过穷举的方式，得到任何想要的密文对应的明文。

## 多次加密协议 ##

在上节中，描述的CPA安全是对两个密文进行加密的描述，那么对于多个明文是否能够保证在窃听敌手下的安全性？

![20200725165632212.png][]

定理10.10 回答了这个问题，如果一个公钥协议在窃听敌手下是不可区分加密的，那么这个协议在多次加密协议下也是不可区分安全的，其实是对上边定理的扩展，为什么？因为在现实中，加密数据的传输往往不是一个一个的密文传输的，很可能是一组一组的密文传送，所以这个定理不但是安全的扩展，还是对现实安全情景的一种更广范围的抽象与提炼。

### 任意长度加密协议 ###

对于多次加密的描述来看，还是对于每次加密的明文长度都相同的，但是对于每次不同的密文长度又能如何计算呢？

其实比较容易，直接切分成相同长度的部分来使用即可，证明也是类似的，内容如下：

![20200725171856915.png][]

### 混合加密（Hybrid Encryption） ###

继续由上可知，公钥加密是安全可用的，但是还存在一个问题，即为公钥加密，密文往往较长，时间消耗比较大，能否存在高效的方案呢？

答案就是混合加密，同时使用对称加密与非对称加密，使用对称加密密文，然后使用公钥加密对称的秘钥。

方案形式化描述如下：

![20200725173406974.png][]

证明在《Introduction to Modern Cryptography》Katz, Lindell P332

[20200725154451762.png]: /images/20230208/fb56bf8ef5ae4d2f85f8b5c431d68acf.png
[20200725161704373.png]: /images/20230208/2cf7b667076e41509189d82a2b235b27.png
[20200725162617698.png]: /images/20230208/514ff99db8ae4f9c8f134b835193d003.png
[Pr_M_m_C_c_ _ Pr_M_m]: https://private.codecogs.com/gif.latex?Pr%5BM%3Dm%7CC%3Dc%5D%20%3D%20Pr%5BM%3Dm%5D
[20200725165632212.png]: /images/20230208/4b4fac1773b3437a990ab1a4fef85c27.png
[20200725171856915.png]: /images/20230208/73233e6dd6154a49b1baa2e9fa8e854d.png
[20200725173406974.png]: /images/20230208/fe23e690c399457faaac5abe76c5203e.png