《Introduction to Modern Cryptography》 第13章 公钥密码中的随机谕言机模型 内容总结
Public-key Cryptosystems in the Random Oracle Model
Standard model VS Random Oracle model
标准模型：一种广泛接受的安全模型，值得注意的是标准模型不一定是最为安全的模型。
随机谕言机模型：存在至少一个函数可以当做谕言机的模型，只能证明不存在“出厂硬伤”。
相同点：都是为了构造安全证明的模型，但是对各种安全风险的捕获方式不同。
不同点：设计安全规约时，调用敌手能力解决潜在困难问题的设计不同。
CPA安全的RSA方案----在随机谕言机模型下
方案构造如下：
安全定义：
证明：
构造实验如下：
注意：我们目前是要证明CPA安全，所以由标准的CPA安全模型，我们得到RSA方案的CPA实验：
1. 一个随机函数被选择。
2. 运行GenRSA算法生成系统参数，敌手获得公钥，并且敌手具有哈希请的能力。最后敌手输出两个消息m0,m1.
3. 随机选择一个比特，对上述两个明文之一进行加密，得到挑战密文，将密文发送给敌手。同样的，敌手可以继续进行哈希询问。
4. 最后敌手输出猜测的比特，如果和挑战者选择的比特相同，则实验结束。
这里有一个点很重要：哈希询问是否能帮助敌手获取攻破敌手的优势？
答案是不能，敌手能否攻破密码方案，与哈希请求几乎无关，进一步，我们尝试计算敌手成功的概率。
敌手攻破方案，看来无非两种情况，第一种是请求哈希询问后成功攻破，第二种是不请求哈希询问成功攻破。如果 那么，非常容易，成功概率仅仅取决于敌手的擦侧结果，我们得到
，
很明显敌手成功的概率小于等于二分之一。
如果不请求的概率不等于0，那么由条件概率公式得到下述表达式：
因为，敌手在不请求哈希询问的条件的概率不为0，那么对于敌手而言，计算结果是完全随机独立的，所以敌手更不可能获得关于这两条明文的任何信息，所以敌手的成功仅仅取决于自己的猜测值。所以得到：
到现在为止，我们得到引理13.3：
根据敌手攻破方案的概率如下描述：
如果我们能进一步证明请求的概率为0 或者是可以忽略的，我们就能形式化的得到敌手成功的概率小于等于二分之一。
另外，此时我们可以发现，敌手成功的概率依然是按照随机二选一来确定的，那么敌手的优势到底在哪？从计算表达式来看，如果请求的概率是不可忽略的，那么非常直观的就能看出来，敌手成功概率小于等于二分之一 + 不可忽略优势。那么敌手将能够以不可忽略的概率解决RSA中的困难问题。那么解决这个困难问题的概率恰好等于请求询问的概率。然而，困难问题是已知难解的，所以这个请求的概率也是可以忽略的。
证明如下，现在将敌手的攻击规约到解决困难问题上：
在这个规约算法中：
1. 模拟者随机的选择一个k，作为哈希函数的输出，这也是一个困难问题的实例。
2. 调用敌手作为子程序，给与公钥，建立一个哈希列表，初始为空。当敌手与模拟者进行交互时，模拟者控制随机谕言机做如下回复：
如果请求的x , 在哈希列表中存在，那么直接输出之前回复的内容。
如果x满足c1的计算方法，返回之前随机选的k.
如果x不满足C1的计算法，则返回一个随机值k.
3. 在某一个时刻，敌手输出两个明文M1和M2。
4. 模拟者随机选择一个比特，并计算C2，将挑战密文发送给敌手。
5. 模拟者完成模拟过程，如果存在某一次敌手请求的x 满足C1的计算方法，则输出该x。
PS：（1）模拟者只掌握公钥N,e ，模拟者不掌握私钥d.
(2) C1 是随机选择的，这是一个困难问题实例，对于模拟者而言，是不知道r的, 则如果敌手能够得到r, 则意味着敌手攻破了困难问题，敌手计算获得了私钥d，则能够获得r 。
（3）随机谕言机选择k作为预设，如果敌手正好询问到r = x 时，则返回随机数k作为H(x)。
模拟的不可区分性：
（1）在现实中 C1 是使用算法得到的，在模拟中时随机选择的。这个是不可区分的。
（2）在现实中H为某一个哈希函数得到，在模拟中一直设置为一个随机值。这也是不可区分的。
（3）**C2 相当于** “一次一密”难度。最后的密文选择与一次一密不可区分。
所以，在这个模拟过程中，对于敌手而言，无法区分现实协议与模拟协议，所以这个模拟是成功的。
规约是否成功？
模拟者不掌握私钥，不能从C1中获取r的值，这是一个RSA实例。但是敌手得到了r, 这就意味着敌手解决了RSA问题实例。所以就将敌手的攻击成功规约到了解决RSA问题实例上。又因为RSA问题是困难的，所以我们也得到了请求概率是可以忽略的。
CCA安全的RSA方案----在随机谕言机模型下
抵抗CCA安全的RSA方案描述如下：
这个CCA-RSA方案中用到了对称加密。
KGEN：运行秘钥生成算法，得到RSA的相关参数，和之前的方案相同。
ENC： 这里使用H(r) = k , 作为对称秘钥加密消息。
DEC： 解密则为先解出r, 进一步使用对称秘钥解出明文消息。
在证明中，和前边一样，我们依然要考虑敌手是否进行哈希请求。
如果敌手不进行哈希请求，那么敌手将不能学习到任何的关于r 的信息，则整个方案的安全可以规约到对称加密上。
如果敌手进行哈希请求，那么敌手将会以可以忽略的概率攻破方案，因为GENRSA是一个困难问题。
定理描述如下：
证明：
CCA模型描述：
1. 选择随机函数H。
2. 运行GenRSA算法获得系统参数。敌手可以获取公钥，哈希询问，解密询问。敌手最终输出两个消息m0,m1。
3. 模拟者随机选择一个比特 和 r, 给与敌手挑战密文。敌手可以继续进行询问，但是不能询问挑战密文。
4. 敌手输出一个比特。如果敌手输出的比特正确，则实验结束，输出1。
概率描述如下：
所以，定义如下：
规约算法如下：
1. 模拟者运行GenRSA 生成系统参数，随机选择r 并计算得到C1
2. 设置解密谕言机列表，如果敌手请求解密，则按照如下方式解密,输入<c1,c2>：
如果C1 = c1 , 模拟请求解密谕言机解密C2。
如果C1 ！= c1, 模拟者计算r ，然后计算k = H(r) ,然后使用这个k 解密。
计算H(r) 的方法如下：如果（r,k）在哈希列表中，则返回k，否则，选择一个随机的值为k。
3. 在某个时刻，敌手输出两个明文消息m0 m1, 模拟者随机选择比特，输出挑战密文。敌手可以继续询问预言机。
4. 当敌手输出他的猜测比特时，模拟者也输出选择的比特。
PS：
（1）模拟不可区分性：敌手在安全模型中的视图 必须和 敌手在规约算法中的视图分布相同。模拟者的视图也必须相同分布。
（2） 模拟者并不知道RSA私钥，仅可通过敌手访问解密预言机解密。
所以，我们可知规约的成功概率和安全模型中的概率关系如下：
显然，因为在安全模型中 和 规约算法中 要求了同分布。
进一步得到：
在下来的证明中，需要处理的一个复杂的点就是在模拟者不知道解密秘钥时，对密文进行解密询问，和上文描述的类似，这里使用一个三元表格来描述解密请求。
详细描述如下：
1 随机选择K ，初始化三元组，这是一个RSA实例。
2 敌手可以发起解密请求，回答方法如下：
（1）如果有询问过或者存在C1 ，则使用对应条目的k解密。
（2）否则选随机数作为K,进行解密。
当敌手请求r时，计算C1，并按照如下返回：
(1) 如果存在对应条目，则直接返回K。
（2）如果缺r 条目，则存储r,返回K。
（3）否则随机的选择K，返回K，存储整个条目。
3 在某个时刻，敌手输出两个明文消息m0,m1。模拟者选择随机的比特加密，返回对应挑战密文。
4.最后如果表中存在解决RSA实例的条目，输出R。
PS： 因为在缺少N的分解因子的情况下，是不可能解出r的，如果最后解出了r, 那么就是敌手发动了有效的攻击。
敌手在安全试验和规约算法中的视图是同分布的，所以有：
所以询问的概率是可以忽略的，解决问题的困难问题的概率是可以忽略的。