《Introduction to modern cryptography》CCA 安全小结

淡淡的烟草味﹌ 2023-03-01 12:54 27阅读 0赞

# 《Introduction to modern cryptography》CCA 安全 #

## CCA Chosen-Ciphertext Attacks ##

CCA 攻击主要是针对公钥密码学所提出的一种安全定义，对于公钥密码学而言，用户往往从多个其他想要和他通信的用户处接受密文，而对于对称密码学而言，用户往往从指定的参与者处接受密文。这就存在一个问题，公钥所面对的境况比对称密码所面对的情景就复杂不少。

对于CCA而言，我们考虑以下的情况：敌手A 获得了 S 发送给R的一段密文，那么敌手A可以选择一些密文发送给R，R则会对A所发送的密文进行解密，然后做出反应，那么A即可获得相关的信息。敌手A可以直接向R发送密文，R有可能直接会解密，那么A则会得到全部解密明文或者其他相关的内容。

以上就是CCA的动机，CCA也是抽象出来的一种捕获公钥密码安全的攻击模式，下文给出一个CCA不可区分实验的形式化描述：

![20200726124620864.png][]

1. 运行秘钥生成算法，得到公钥与私钥。

2. 敌手可以获得公钥，以及访问解密预言机的能力，输出两个长度相等的密文给挑战者。

3. 控制解密预言机的挑战者，随机选择一个比特，然后将加密的密文发送给敌手，即为挑战密文。

4. 敌手可以继续与解密谕言机进行交互，但是限制是不能询问解密谕言机。最后敌手输出一个猜测比特。

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

接着，给出在CCA模型下不可区分的形式化定义：

![20200726125134797.png][]

安全定义和之前CPA的定义类似。

## 陷门置换  Trapdoor Permutations ##

陷门置换是对于一类函数的归类，一个陷门置换族定义如下：

![20200726131427537.png][]

一组多项式时间算法被定义为一个陷门置换族。

1. Gen 参数生成算法，输入为1^n, 输出为（I, td），DI 是定义域上的一个置换f的表盒，Dtd是允许求逆的陷门信息。即为，在一个函数族中，存在编号为I的一个函数f, 则对应存在一个计算这个函数逆的陷门信息td.

2. Gen1 表示运行Gen算法，仅仅有一个输出I，这要求此时的函数组为一个单向陷门置换。

3. Samp 是一个概率性算法，由Gen生成的函数f的到一个实例。

4.lnv 是一个确定的求逆算法，使用陷门信息能够求出函数f 的逆。

陷门置换其实本质上只是一个数学的定义，在密码学中，我们应该对陷门置换的定义加以限制方可使用。密码学中的陷门置换指的是“单向陷门置换”，我们要求缺少陷门信息求逆是困难的。

例如，RSA就是一个陷门置换

1. Gen  ->  e, d, N

2. Samp -> x

3. Eval -> y = x^e mod N

4. Invert -> x = y^d mod N

## 公钥加密中的陷门置换 ##

陷门置换中要求求逆是复杂的，但是这并不意味着从中获取原像的信息就是复杂的。但是如果我们使用陷门置换构造一个公钥密码协议，那么必须考虑其中比特的提取难度，只有你的方案能尽可能的捕获所有可能的不安全因素，你才能说自己的方案是相对安全的。使用陷门置换构造公钥方案的形式化描述如下：

![20200726144456208.png][]

即，敌手从函数值中提取出相关困难比特的概率 小于等于 二分之一 加 可忽略概率。

其中，hard-core predicate 的描述如下：

![20200726152356199.png][]

![20200726152340249.png][]

一个简单的方式如下所述：

![20200726145242624.png][]

由于敌手是难以一个高的优势提取困难比特值的，使用这个困难比特 异或 明文消息，得到密文。

敌手如果想要破解这个方案，就需要求出y 的原像，才能破解这个方案。

### 使用陷门置换构造公钥方案满足CCA安全 ###

定理描述如下：

![2020072615330911.png][]

方案构造描述如下：

![20200726153853562.png][]

证明：

安全模型如下：

![20200726155632660.png][]

敌手行为如下：

![20200726155743504.png][]

概率计算如下：

![20200726155914680.png][]

![20200726155922239.png][]

![20200726155929447.png][]

[20200726124620864.png]: /images/20230208/6705d9b73475455c9fe045db1d44a385.png
[20200726125134797.png]: /images/20230208/92b8976c83cb4fbaa295f501f9a35608.png
[20200726131427537.png]: /images/20230208/ae250aced7bf435592e0d9e2f4f981b8.png
[20200726144456208.png]: /images/20230208/04929c16094d4b59a45abf3980e649ac.png
[20200726152356199.png]: /images/20230208/a0f2455287ab4abfb640a12e628da099.png
[20200726152340249.png]: /images/20230208/af8775f2c1484a439db0a82e0c1dad5a.png
[20200726145242624.png]: /images/20230208/84c01057eed94415bbcdf69df48a4238.png
[2020072615330911.png]: /images/20230208/49926cea490e404e9d6942f65ec4c782.png
[20200726153853562.png]: /images/20230208/da86b6dac1d74c5bb8d2bf4b7c50a12e.png
[20200726155632660.png]: /images/20230208/121220f0dac547a2a8127a47ebf8ee9b.png
[20200726155743504.png]: /images/20230208/4aa8a3a00a2949a8aea7a47807478dd9.png
[20200726155914680.png]: https://img-blog.csdnimg.cn/20200726155914680.png
[20200726155922239.png]: https://img-blog.csdnimg.cn/20200726155922239.png
[20200726155929447.png]: https://img-blog.csdnimg.cn/20200726155929447.png