密码学与访问控制理论课件-计算安全性.pptxVIP

4计算安全性 内容提要1. 基本概念2.伪随机性3.计算安全性证明4.关于计算安全性的一些结论 基本概念? 基本概念封闭性： A 和A’ 均为概率多项式时间算法，则A调用A’仍能在概率多项式时间内完成。概率多项式是确定多项式的扩充，若一个方案若能抵抗概率多项式时间算法攻击，则也能抵抗确定性多项式时间算法攻击。 基本概念? 基本概念? 基本概念? 基本概念? 基本概念? 基本概念? 伪随机性（1）真随机数投币电、热噪声空气噪声放射衰变均匀随机 伪随机性? 伪随机性? 伪随机性? 伪随机性结论2：目前尚无法真正意义上证明伪随机发生器的存在性，但倾向于它确实是存在的。如果假设单向函数存在，那么伪随机发生器是存在的。 伪随机性? 伪随机性结论3：任何标准的伪随机数发生器能够被转化成一个输出长度可变的伪随机发生器。 计算安全性证明一个基于伪随机发生器的加密 计算安全性证明一个基于伪随机发生器的加密 计算安全性证明? 计算安全性证明? 计算安全性证明? 计算安全性证明（2）分析“一次一密”加密方案用真随机发生器代替伪随机发生器，则为完善必威体育官网网址 计算安全性证明? 计算安全性证明? 计算安全性证明 计算安全性证明 计算安全性证明（1）单消息加密安全的密码方案不一定是多消息加密安全的，多消息加密的密码方案一定是单消息加密安全的。敌手A输出M0={0n, 0n}M1={0n, 1n}若用同一k加密，则密文可区分 计算安全性证明（2）多消息加密时概率加密是必要的。相同的明文和密钥要加密成不同的密文。如果密文是明文和密钥的确定函数，那么该加密方案用于多消息加密时，一定是不安全的。CBC，CFB，OFB，CTR都是概率加密的。 计算安全性证明（3）一个输出长度可变的伪随机发生器，用于多消息加密时是安全的。根据输出长度可变的伪随机发生器的定义。 计算安全性证明根据对手所掌握的信息，攻击方法分类：唯密文攻击 COA已知明文攻击KPA选择明文攻击CPA选择密文攻击CCA其中CCA中，敌手不仅能够选择明文得到相应密文，而且还能够选择密文，获取对应明文。午餐时间攻击、午夜攻击 计算安全性证明随机预言机(random oracle machine)预言机就是一个“黑盒子”，能够根据安全的要求模拟敌手可能的能力。例如：加密预言机，当A提供一个明文，并询问预言机，预言机返回一个密文。如果ENC是随机的，则预言机每次回答的时候都保证新的随机性。不能直接询问ROM所求问题的解答。 计算安全性证明 计算安全性证明（1）定义实验，合理反映安全需求（2）根据实验成功概率，严格定义安全性 计算安全性证明（1）任何在CPA条件下的不可区分加密的对称密钥加密方案，也是窃听者存在条件下的不可区分加密。（后者是前者的特殊情况，前者使用了预言机的帮助）（2）确定性的加密一定不是CPA安全的。（3）可证明，任何在CPA条件下的不可区分加密的对称密钥加密方案，也是在CPA条件下的不可区分“多次”加密方案。（相同的明文概率加密成不同的密文，和唯密文攻击条件对比） 计算安全性证明（1）确定性加密（2）不是CPA安全的（3）在窃听者存在情况下，也是不安全的。（按多次加密安全性定义）ECB 计算安全性证明（1）概率加密（2）如果IV均匀随机选择，F是伪随机置换则是CPA安全的CBC 计算安全性证明（1）概率加密（2）如果IV均匀随机选择，F是伪随机置换则是CPA安全的（3）CFB同OFBOFB 计算安全性证明（1）概率加密（2）如果ctr均匀随机选择，F是伪随机置换则是CPA安全的CTR 计算安全性证明（1）D可以适应性地方问Fk和f的随机预言机（2）伪随机函数的存在等价于伪随机数发生器的存在（3）分组密码可以看作是常用的伪随机函数 计算安全性证明 计算安全性证明 计算安全性证明 计算安全性证明 计算安全性证明不是CCA安全的：敌手在CCA条件下，改动密文C中s的一个比特，要求随机预言机解密，结果只与真实明文有一比特差别。因此可选择mo=0n,m1=1n 计算安全性证明CBC,OFB,CFB,CTR都不是CCA安全的：敌手在CCA条件下，修改c1的最后1比特，请求随机预言机解密(IV,c1’,c2,c3)，m2只与正确值相差1比特。 计算安全性证明padding oracle attack（1）修改c[0]的最后一个字节b1=b1 ⊕ g1 ⊕0x01（g1从00到FF）（2）发送(IV,c[0],c[1])给oracle解密 (3)如果oracle报告padding正确，则m[1]’=c[0]’ ⊕Dec(k,c[1])=c[0] ⊕ g ⊕0x01 ⊕Dec(k,c[1])=m[1] ⊕ g ⊕0x01 ,那么m[1]的最后一个字节和g1相同。因为0x01是正确的padding. 计算安全性