第九章可证明安全性理论选编课件.ppt

1、第8章 可证明安全性理论 可证明安全性可证明安全性(Provable security)n可证明安全性是指这样一种可证明安全性是指这样一种“归约归约”方法：首方法：首先确定密码体制的安全目标，例如，加密体制先确定密码体制的安全目标，例如，加密体制的安全目标是信息的机密性，签名体制的安全的安全目标是信息的机密性，签名体制的安全目标是签名的不可伪造性；然后根据敌手的能目标是签名的不可伪造性；然后根据敌手的能力构建一个形式化的安全模型，最后指出如果力构建一个形式化的安全模型，最后指出如果敌手能成功攻破密码体制，则存在一种算法在敌手能成功攻破密码体制，则存在一种算法在多项式时间内解决一个公认的数学困难

2、问题。多项式时间内解决一个公认的数学困难问题。8.1 可证明安全性理论的基本概念可证明安全性理论的基本概念 n公钥加密体制的安全性概念公钥加密体制的安全性概念n数字签名体制的安全性概念数字签名体制的安全性概念 n随机预言模型随机预言模型 1.公钥加密体制的安全性概念n（1）完美安全性）完美安全性(perfect security)n（2）语义安全性）语义安全性(Semantic security)n（3）多项式安全性）多项式安全性(polynomial security)（1）完美安全性）完美安全性n如果一个具有无限计算能力的敌手从给定的如果一个具有无限计算能力的敌手从给定的密文中不能获取明文

3、的任何有用信息，我们密文中不能获取明文的任何有用信息，我们就说这个加密体制具有完美安全性或信息论就说这个加密体制具有完美安全性或信息论安全性。根据安全性。根据Shannon理论知道，要达到完理论知道，要达到完美安全性，密钥必须和明文一样长并且相同美安全性，密钥必须和明文一样长并且相同的密钥不能使用两次。然而，在公钥密码体的密钥不能使用两次。然而，在公钥密码体制中，我们假设加密密钥可以用来加密很多制中，我们假设加密密钥可以用来加密很多消息并且通常是很短的。因此，完美安全性消息并且通常是很短的。因此，完美安全性对于公钥密码体制来说是不现实的。对于公钥密码体制来说是不现实的。（2）语义安全性）语义安

4、全性n语义安全性与完美安全性类似，只是我们语义安全性与完美安全性类似，只是我们只允许敌手具有多项式有界的计算能力。只允许敌手具有多项式有界的计算能力。从形式上说，无论敌手在多项式时间内能从形式上说，无论敌手在多项式时间内能从密文中计算出关于明文的什么信息，他从密文中计算出关于明文的什么信息，他也可以在没有密文的条件下计算出这些信也可以在没有密文的条件下计算出这些信息。换句话说，拥有密文并不能帮助敌手息。换句话说，拥有密文并不能帮助敌手找到关于明文的任何有用信息。找到关于明文的任何有用信息。（3）多项式安全性）多项式安全性n我们很难显示一个加密体制具有语义安全我们很难显示一个加密体制具有语义安全

5、性，然而，我们却可以比较容易显示一个性，然而，我们却可以比较容易显示一个加密体制具有多项式安全性。多项式安全加密体制具有多项式安全性。多项式安全性也称为密文不可区分性。幸运的是，如性也称为密文不可区分性。幸运的是，如果一个加密体制具有多项式安全性，那么果一个加密体制具有多项式安全性，那么我们可以显示该体制也具有语义安全性。我们可以显示该体制也具有语义安全性。因此，为了显示一个加密体制是语义安全因此，为了显示一个加密体制是语义安全的，我们只需要显示该体制是多项式安全的，我们只需要显示该体制是多项式安全的。的。n如果没有一个敌手能以大于一半的概率赢得以下如果没有一个敌手能以大于一半的概率赢得以下游

6、戏，我们就称这个加密体制具有密文不可区分游戏，我们就称这个加密体制具有密文不可区分性，或具有多项式安全性。这个敌手性，或具有多项式安全性。这个敌手A被告知某个被告知某个公钥公钥y及其相应的加密函数及其相应的加密函数fy。敌手。敌手A进行以下两个进行以下两个阶段：阶段：n寻找阶段：敌手寻找阶段：敌手A选择两个明文选择两个明文m0和和m1。n猜测阶段：敌手猜测阶段：敌手A被告知其中一个明文被告知其中一个明文mb的加密结的加密结果，这里的果，这里的b是保密的。敌手是保密的。敌手A的目标是以大于一的目标是以大于一半的概率猜对半的概率猜对b的值。的值。n从这个游戏可以看出，一个具有多项式安全性的从这个游

7、戏可以看出，一个具有多项式安全性的加密体制一定是一个概率性加密体制。否则，敌加密体制一定是一个概率性加密体制。否则，敌手手A在猜测阶段就可以计算：在猜测阶段就可以计算：c1=fy(m1)n并测试是否有并测试是否有c1=cb成立。如果成立，敌手成立。如果成立，敌手A就可就可以成功推断以成功推断b=1，否则，否则b=0。既然敌手。既然敌手A总能简单总能简单地猜测地猜测b的值，敌手的值，敌手A的优势定义为：的优势定义为：n如果：如果：n我们就称这个加密体制是多项式安全的，其中我们就称这个加密体制是多项式安全的，其中p(k)是一个多项式函数，是一个多项式函数，k是一个足够大的安全参数。是一个足够大的安

8、全参数。011Pr(,)2AbAdvA cy m mb1()AAdvp k三种基本的攻击模型三种基本的攻击模型 n选择明文攻击（选择明文攻击（Chosen Plaintext Attack,CPA），），n选择密文攻击（选择密文攻击（Chosen Ciphertext Attack,CCA）n适应性选择密文攻击（适应性选择密文攻击（Adaptive Chosen Ciphertext Attack,CCA2）。）。选择明文攻击选择明文攻击n在选择明文攻击中，敌手被告知各种各样在选择明文攻击中，敌手被告知各种各样的密文。敌手可以访问一个黑盒，这个黑的密文。敌手可以访问一个黑盒，这个黑盒只能执行加

9、密，不能进行解密。既然在盒只能执行加密，不能进行解密。既然在公钥密码体制中任何人都可以访问加密函公钥密码体制中任何人都可以访问加密函数，即任何人都可自己产生一些明文密文数，即任何人都可自己产生一些明文密文对，选择明文攻击模拟了一种非常弱的攻对，选择明文攻击模拟了一种非常弱的攻击模型。击模型。选择密文攻击选择密文攻击n选择密文攻击也称为午餐攻击，是一种比选择选择密文攻击也称为午餐攻击，是一种比选择明文攻击稍强的攻击模型。在选择密文攻击中，明文攻击稍强的攻击模型。在选择密文攻击中，敌手可以访问一个黑盒，这个黑盒能进行解密。敌手可以访问一个黑盒，这个黑盒能进行解密。在午餐时间，敌手可以选择多项式个密

10、文来询在午餐时间，敌手可以选择多项式个密文来询问解密盒，解密盒把解密后的明文发送给敌手。问解密盒，解密盒把解密后的明文发送给敌手。在下午时间，敌手被告知一个目标密文，要求在下午时间，敌手被告知一个目标密文，要求敌手在没有解密盒帮助的情况下解密目标密文，敌手在没有解密盒帮助的情况下解密目标密文，或者找到关于明文的有用信息。或者找到关于明文的有用信息。n在上面给出的多项式安全性的攻击游戏中，选在上面给出的多项式安全性的攻击游戏中，选择密文攻击允许敌手在寻找阶段询问解密盒，择密文攻击允许敌手在寻找阶段询问解密盒，但是在猜测阶段不能询问解密盒。但是在猜测阶段不能询问解密盒。适应性选择密文攻击适应性选择

11、密文攻击n适应性选择密文攻击是一种非常强的攻击适应性选择密文攻击是一种非常强的攻击模型。除了目标密文外，敌手可以选择任模型。除了目标密文外，敌手可以选择任何密文对解密盒进行询问。目前普遍认为，何密文对解密盒进行询问。目前普遍认为，任何新提出的公钥加密算法都应该在适应任何新提出的公钥加密算法都应该在适应性选择密文攻击下达到多项式安全性。性选择密文攻击下达到多项式安全性。语义安全语义安全n定义定义1 如果一个公钥加密体制在适应性选如果一个公钥加密体制在适应性选择密文攻击（择密文攻击（adaptive chosen ciphertext attacks）下是语义安全的，我们就说该体）下是语义安全的，

12、我们就说该体制是安全的。制是安全的。n定义定义2 如果一个公钥加密体制在适应性选如果一个公钥加密体制在适应性选择密文攻击下是多项式安全的，我们就说择密文攻击下是多项式安全的，我们就说该体制是安全的该体制是安全的。引理引理1 一个可展（一个可展（Malleability）的加密）的加密体制在适应性选择密文攻击下是不安全体制在适应性选择密文攻击下是不安全的。的。n证明：假设一个加密体制是可展的，当给证明：假设一个加密体制是可展的，当给定一个目标密文定一个目标密文cb时，我们可以把它修改成时，我们可以把它修改成一个相关的密文一个相关的密文cb*。这种相关的关系也应。这种相关的关系也应该存在于和该存在

13、于和mb和和mb*。然后敌手利用解密预。然后敌手利用解密预言机（解密盒）来获得言机（解密盒）来获得cb*的明文。最后敌的明文。最后敌手根据手根据mb*来恢复来恢复mb。2数字签名体制的安全性概念数字签名体制的安全性概念 n对于数字签名体制，存在以下几种伪造类对于数字签名体制，存在以下几种伪造类型：型：n（1）完全攻破）完全攻破:敌手能够产生与私钥持有者敌手能够产生与私钥持有者相同的签名，这相当于恢复出了私钥。相同的签名，这相当于恢复出了私钥。n（2）选择性伪造）选择性伪造:敌手能够伪造一个他选择敌手能够伪造一个他选择的消息的签名。的消息的签名。n（3）存在性伪造）存在性伪造:敌手能够伪造一个消

14、息的敌手能够伪造一个消息的签名，这个消息可能仅仅是一个随机比特签名，这个消息可能仅仅是一个随机比特串串 攻击模型攻击模型n 被动攻击被动攻击 在被动攻击中，敌手被告知一个公钥，要求产在被动攻击中，敌手被告知一个公钥，要求产生一个选择性伪造或存在性伪造。这是一种比生一个选择性伪造或存在性伪造。这是一种比较弱的攻击模型。较弱的攻击模型。n 积极攻击积极攻击 积极攻击中最强的攻击是适应性选择消息攻击积极攻击中最强的攻击是适应性选择消息攻击（adaptive chosen messages attacks），即），即敌手可以访问一个签名预言机，它能够产生合敌手可以访问一个签名预言机，它能够产生合法的签

15、名。敌手的目标是产生一个消息的签名，法的签名。敌手的目标是产生一个消息的签名，当然这个消息不能是已经询问过签名预言机的当然这个消息不能是已经询问过签名预言机的消息。消息。n定义定义3 如果一个数字签名体制在适应性选如果一个数字签名体制在适应性选择消息攻击下能够抵抗存在性伪造，我们择消息攻击下能够抵抗存在性伪造，我们就说该体制是安全的。就说该体制是安全的。3随机预言模型随机预言模型 n显示一个密码协议安全的现代方法是可证显示一个密码协议安全的现代方法是可证明安全性。可证明安全性的目的在于证明：明安全性。可证明安全性的目的在于证明：如果一个敌手能够攻破一个密码体制的某如果一个敌手能够攻破一个密码体

16、制的某个安全概念，那么我们就可以利用该敌手个安全概念，那么我们就可以利用该敌手做一些认为不可能的事情。做一些认为不可能的事情。n我们假设一个敌手（一个概率算法）能够我们假设一个敌手（一个概率算法）能够以一个不可忽略的概率攻破以一个不可忽略的概率攻破RSA的某个安的某个安全概念（比方说语义安全性）。对于一个全概念（比方说语义安全性）。对于一个安全参数安全参数(安全参数用于测量密钥长度的大安全参数用于测量密钥长度的大小，比如在小，比如在RSA中，安全参数可能是模数中，安全参数可能是模数n的比特数的比特数)为为k的密码体制，如果敌手成功的密码体制，如果敌手成功的概率大于的概率大于1/p（k），我们就

17、说这个敌手），我们就说这个敌手以一个不可忽略的概率成功，这里的以一个不可忽略的概率成功，这里的p是一是一个以个以k为变量的多项式。为变量的多项式。n我们假设敌手我们假设敌手A是一个被动攻击敌手，即对是一个被动攻击敌手，即对于于RSA加密，他不进行解密询问。我们现加密，他不进行解密询问。我们现在希望能够构造一个新算法在希望能够构造一个新算法BA，它能够在，它能够在输入一个整数输入一个整数n和调用多项式次敌手和调用多项式次敌手A的情的情况下，以一个不可忽略的概率输出况下，以一个不可忽略的概率输出n的因子。的因子。算法算法BA说明了如果存在敌手说明了如果存在敌手A，就存在一个，就存在一个多项式时间因

18、子分解算法，能够以一个不多项式时间因子分解算法，能够以一个不可忽略的概率解决因子分解问题。既然我可忽略的概率解决因子分解问题。既然我们目前并不相信存在这样的因子分解算法，们目前并不相信存在这样的因子分解算法，我们也可以断定这样的敌手我们也可以断定这样的敌手A是不存在的。是不存在的。可证明安全的思想可证明安全的思想n可证明安全的思想就是给定一个算法可证明安全的思想就是给定一个算法A，我们提出一，我们提出一个新算法个新算法BA，BA把把A作为子程序。输入给作为子程序。输入给BA的是我的是我们希望解决的困难问题，输入给们希望解决的困难问题，输入给A的是某个密码算法。的是某个密码算法。然而，如果然而，

19、如果A是一个积极攻击敌手，即是一个积极攻击敌手，即A可以对输入可以对输入的公钥进行解密预言询问或签名预言询问。算法的公钥进行解密预言询问或签名预言询问。算法BA要想使用要想使用A作为子程序，就需对作为子程序，就需对A的询问提供回答。的询问提供回答。算法算法BA需要应对以下几个问题：需要应对以下几个问题：n它的回答应该看起来是合法的。因为加密应该能够它的回答应该看起来是合法的。因为加密应该能够解密，签名应该能够被验证，否则，算法解密，签名应该能够被验证，否则，算法A就知道它就知道它的预言机在撒谎。算法的预言机在撒谎。算法BA就不能再确保算法就不能再确保算法A是以一是以一个不可忽略的概率成功。个不

20、可忽略的概率成功。n它的回答应该与如果预言机是真正的解密它的回答应该与如果预言机是真正的解密/加密预言加密预言机时机时A期望的回答具有相同的概率分布。期望的回答具有相同的概率分布。n自始至终，预言机的回答应该是一致的。自始至终，预言机的回答应该是一致的。n算法算法BA需要在不知道私钥的情况下提供这些回答。需要在不知道私钥的情况下提供这些回答。随机预言模型随机预言模型 n我们必须让我们必须让BA在不知道私钥的情况下能够在不知道私钥的情况下能够解密或者签名，但既然我们的体制是安全解密或者签名，但既然我们的体制是安全的，这一点意味着是不可能的。的，这一点意味着是不可能的。随机预言模型随机预言模型 n

21、为了回避这个问题，我们通常使用随机预言模型。为了回避这个问题，我们通常使用随机预言模型。n随机预言是一个理想的随机预言是一个理想的Hash函数。对于每一个新函数。对于每一个新的询问，随机预言产生一个随机值作为回答，如的询问，随机预言产生一个随机值作为回答，如果进行两次相同的询问，回答一定相同。在随机果进行两次相同的询问，回答一定相同。在随机预言模型中，我们假设敌手并不使用密码算法中预言模型中，我们假设敌手并不使用密码算法中定义的那个定义的那个Hash函数，也就是说，即使我们将随函数，也就是说，即使我们将随机预言换成真实的机预言换成真实的Hash函数时，敌手函数时，敌手A也是成功也是成功的。的。

22、n对于对于A的解密预言询问和签名预言询问，算法的解密预言询问和签名预言询问，算法BA是通过欺骗随机预言的回答来适合自己的需要的。是通过欺骗随机预言的回答来适合自己的需要的。8.2 可证明安全的公钥密码体制可证明安全的公钥密码体制RSA的安全性 n引理引理2 RSA不是多项式安全的。不是多项式安全的。n证明：假设敌手知道用户只加密了证明：假设敌手知道用户只加密了m1和和m2中的一中的一个消息。敌手还知道用户的公钥，即个消息。敌手还知道用户的公钥，即e和和n。当敌。当敌手被告知一个密文手被告知一个密文c，要求判断，要求判断c对应的明文对应的明文m是是m1还是还是m2时，敌手只需要计算：时，敌手只需

23、要计算：n如果如果 ，则敌手知道，则敌手知道m=m1。否则敌手知道。否则敌手知道m=m2。n除了以上的攻击外，除了以上的攻击外，RSA在适应性选择密文攻击在适应性选择密文攻击下也是不安全的，这主要是因为下也是不安全的，这主要是因为RSA具有同态性具有同态性质。质。1modecmn cc RSA的安全性 n定义4 给定m1和m2的加密，如果能在不知道m1或m2的条件下确定m1m2的加密结果，我们就说该加密体制具有同态性质（homomorphic property）。n根据以下方程知，RSA具有同态性质：1212()mod(mod)(mod)modeeemmnmn mnnRSA的安全性 n引理引理

24、3 RSA不是不是CCA2安全的。安全的。n证明：假设敌手想解密证明：假设敌手想解密 ：n敌手首先生成一个相关的密文敌手首先生成一个相关的密文 并询问解密并询问解密预言机。敌手得到预言机。敌手得到c 的明文的明文m。然后敌手计算：。然后敌手计算：n因此，敌手获得了密文因此，敌手获得了密文c对应的明文对应的明文m。modecmn2ecc(2)2222222dededdmcccmmElGamal的安全性n引理引理4 如果如果DDH问题是困难的，那么问题是困难的，那么ElGamal加密加密体制在选择明文攻击下是多项式安全的。体制在选择明文攻击下是多项式安全的。n 证明：为了显示证明：为了显示ElGa

25、mal是多项式安全的，我们首是多项式安全的，我们首先假设存在一个能够攻破先假设存在一个能够攻破ElGamal多项式安全性的多项式安全性的多项式时间算法多项式时间算法A，然后我们给出一个使用算法，然后我们给出一个使用算法A作作为子程序的算法为子程序的算法B来解决来解决DDH问题。问题。n我们首先来回忆多项式安全性的攻击游戏：我们首先来回忆多项式安全性的攻击游戏：n在寻找阶段，输入一个公钥，输出两个消息和一些状态信息。在寻找阶段，输入一个公钥，输出两个消息和一些状态信息。n在猜测阶段，输入一个挑战密文、一个公钥、两个消息和一在猜测阶段，输入一个挑战密文、一个公钥、两个消息和一些状态信息，猜测挑战密

26、文对应的明文是哪个消息。些状态信息，猜测挑战密文对应的明文是哪个消息。ElGamal的安全性的安全性 ElGamal密文为：密文为：(gk,mhk)其中其中k是一个随机整数，是一个随机整数，h是公钥。是公钥。给定给定gx、gy和和gz，解决，解决DDH问题的算法问题的算法B执行如下步骤：执行如下步骤：令令h=gx。（m0,m1,s）=A（寻找阶段（寻找阶段,h）。）。设置设置c1=gy。从从0,1中随机选择一个数中随机选择一个数b。设置设置c2=mbgz。b=A（猜测阶段（猜测阶段,(c1,c2),h,m0,m1,s）。）。如果如果b=b，输出，输出“TRUE”，否则输出，否则输出“FALSE

27、”。n下面解释为什么算法下面解释为什么算法B解决了解决了DDH问题。问题。n当当z=xy，在猜测阶段输入给算法，在猜测阶段输入给算法A的将是的将是mb的一的一个合法加密。如果算法个合法加密。如果算法A真正能够攻破真正能够攻破ElGamal的的语义安全性，那么输出的语义安全性，那么输出的b 将是正确的，算法将是正确的，算法B将将输出输出“TRUE”。n当当z xy时，在猜测阶段输入给算法时，在猜测阶段输入给算法A的几乎不可能的几乎不可能是合法的密文，即不是是合法的密文，即不是m0或或m1的加密，在猜测阶的加密，在猜测阶段输出的段输出的b 与与b将是独立的。因此，算法将是独立的。因此，算法B将以相

28、将以相等的概率输出等的概率输出“TRUE”或或“FALSE”。ElGamal的安全性n引理引理5 ElGamal加密体制是可展的。加密体制是可展的。证明：给定密文：证明：给定密文：(c1,c2)=(gk,mhk)敌手可以在不知道敌手可以在不知道m、随机数、随机数k、私钥、私钥x的情的情况下产生消息况下产生消息2m的合法密文：的合法密文：(c1,2c2)=(gk,2mhk)ElGamal的安全性的安全性n引理引理6 ElGamal加密体制不是加密体制不是CCA2安全的。安全的。n证明：假设敌手想解密：证明：假设敌手想解密：c=(c1,c2)=(gk,mhk)n敌手首先生成一个相关的密文敌手首先生

29、成一个相关的密文c=(c1,2c2)并并询问解密预言机。敌手得到询问解密预言机。敌手得到c 的明文的明文m。然。然后敌手计算：后敌手计算：2 1222222222xkxkxkxkc cmmh gmg gmmRSA-OAEPn即使对于被动攻击敌手，即使对于被动攻击敌手，RSA也不能提供也不能提供一个语义安全的加密体制。为了使一个系一个语义安全的加密体制。为了使一个系统安全，我们需要在加密前对明文增加冗统安全，我们需要在加密前对明文增加冗余信息，或者是对密文增加冗余信息。这余信息，或者是对密文增加冗余信息。这里的填充应该是随机性的，以便产生一个里的填充应该是随机性的，以便产生一个非确定性加密算法。

30、非确定性加密算法。RSA-OAEPn目前使用最多的填充方法是由目前使用最多的填充方法是由Bellare和和Rogaway提出的最优非对称加密填充提出的最优非对称加密填充（Optimized Asymmetric Encryption Padding，OAEP）方法。）方法。OAEP可以用于可以用于任何陷门单向置换函数，尤其是任何陷门单向置换函数，尤其是RSA函数。函数。OAEP用于用于RSA时称为时称为RSA-OAEP。在随机。在随机预言模型中，我们可以显示预言模型中，我们可以显示RSA-OAEP在在适应性选择密文攻击下是语义安全的。适应性选择密文攻击下是语义安全的。OAEPn设设f是任何是任

31、何k比特到比特到k比特的陷门单向置换函数。比如说，比特的陷门单向置换函数。比如说，k=1024时，时，f可以是可以是RSA函数函数c=me。n设设k0和和k1表示两个数（比如表示两个数（比如k0,k1128）。设）。设n=k k0 k1和两个和两个Hash函数为函数为n设设m是是n比特的消息，我们使用下面的函数来加密消息比特的消息，我们使用下面的函数来加密消息m。n其中表示其中表示k1个个0跟随着跟随着m，R是长度为是长度为k0的随机比特串，的随机比特串，|表示连接。我们可以把表示连接。我们可以把OAEP看成是两轮看成是两轮Feistel网络，网络，010,10,1kn kG:010,10,1

32、kn kH:11()(|0()|(|0()kkE mf mGRRH mGR 1|0()kmG R 1(|0()kRH mG R 1|0()kmG R 1|0km R R G H n为了解密E(m)，我们可以计算11|()|0()|(|0()kkATRH TmG RRH mG RRSA-OAEP n定理定理1 在随机预言模型中，我们将在随机预言模型中，我们将G和和H模模拟成随机预言机。假设拟成随机预言机。假设RSA问题是一个困问题是一个困难问题，难问题，RSA-OAEP加密方案在适应性选加密方案在适应性选择密文攻击下是语义安全的。择密文攻击下是语义安全的。n证明：我们首先将证明：我们首先将RSA

33、函数函数f写成：写成：n然后将然后将RSA-OAEP定义为：定义为：01*0,10,1(/)(,)(|)modkn keZ NZfs ts tN:1(|0)(),()ksmG rtrH sn我们可以证明我们可以证明RSA问题与函数问题与函数f的单向性是的单向性是等价的，且从等价的，且从f(s,t)恢复出恢复出s与从与从f(s,t)恢复出恢复出(s,t)是同样困难的。接下来的任务就是如何是同样困难的。接下来的任务就是如何利用攻破利用攻破RSA-OAEP的敌手的敌手A来构造一个能来构造一个能够解决够解决RSA函数单向性的算法函数单向性的算法BA，即对于，即对于固定的固定的RSA模数模数N，给定，给

34、定c*=f(s*,t*)，要求，要求算法算法BA计算出计算出s*。n在寻找阶段，在寻找阶段，A产生两个消息产生两个消息m0和和m1，BA选择选择b0,1并假设并假设c*是是mb的加密密文。在猜测阶段，的加密密文。在猜测阶段，BA将将c*发送给发送给A，要求，要求A猜测猜测c*是是m0的密文还是的密文还是m1的密文，即的密文，即b=0还是还是b=1。同时，算法。同时，算法BA必须回答必须回答A的询问，包括的询问，包括Hash函数函数G的询问，的询问，Hash函数函数H的询问和解密预言询问。为了保持一致性，的询问和解密预言询问。为了保持一致性，BA维维护两个列表护两个列表L1和和L2。这两个列表开

35、始都为空，。这两个列表开始都为空，L1用于跟踪用于跟踪A对预言机对预言机G的询问，的询问，L2用于跟踪用于跟踪A对预对预言机言机H的询问。下面详细解释的询问。下面详细解释BA是如何回答这些是如何回答这些询问的。询问的。nG()询问：对于列表询问：对于列表L2中的任何询问中的任何询问，BA检查是检查是否有下式成立：否有下式成立：n如果上式成立，我们就已经完成了对如果上式成立，我们就已经完成了对f在在c*求逆的求逆的任务，我们仍然可以继续模拟任务，我们仍然可以继续模拟G并设置：并设置：n如果对于任何的如果对于任何的上式都不成立，上式都不成立，BA在在G的值域上的值域上随机选择一个数来回答随机选择一

36、个数来回答A并将该数记录到列表并将该数记录到列表L1中。中。*(,()cfH 1()(|0)kbGmnH()询问：询问：BA在在H的值域上随机选择一个数的值域上随机选择一个数来回答来回答A并将该数记录到列表并将该数记录到列表L2中。对于列中。对于列表表L1中的任何询问中的任何询问，BA检查是否有下式成检查是否有下式成立：立：n如果上式成立，我们同样完成了对如果上式成立，我们同样完成了对f在在c*求求逆的任务。逆的任务。*(,()cfH n解密询问：给定一个密文解密询问：给定一个密文c，BA查找列表查找列表L1和和L2使其满足：对于一对使其满足：对于一对和和，如果设：，如果设：n那么那么c=f(

37、,)且且的尾部至少有的尾部至少有k1个比特为个比特为0。如果上述情况成立，。如果上述情况成立，BA返回返回的首部的的首部的n个比特，否则个比特，否则BA返回该密文是不合法的。返回该密文是不合法的。n如果一个按照正确方式产生的密文能够通如果一个按照正确方式产生的密文能够通过上述的解密预言机，我们肯定能够获得过上述的解密预言机，我们肯定能够获得原始的明文原始的明文,(),()HG n们需要显示上述的解密预言机能够们需要显示上述的解密预言机能够“欺骗欺骗”敌手敌手A。如果敌手。如果敌手A能够以一个不可忽略的能够以一个不可忽略的优势攻破优势攻破RSA-OAEP的语义安全性，算法的语义安全性，算法BA就

38、能够以一个不可忽略的概率对就能够以一个不可忽略的概率对f求逆。求逆。n我们知道，我们知道，BA已经假设了已经假设了c*=f(s*,t*)是是mb的加密密文。因此，这里应该存在一个的加密密文。因此，这里应该存在一个r*满足：满足：n我们首先要显示模拟解密预言失败的概率我们首先要显示模拟解密预言失败的概率是可以忽略的，然后显示只要敌手是可以忽略的，然后显示只要敌手A能够以能够以一个不可忽略的概率猜对一个不可忽略的概率猜对b，那么，那么s*被提交被提交给给H预言机进行询问的概率就是不可忽略的。预言机进行询问的概率就是不可忽略的。只要只要s*被提交给被提交给H预言机进行了询问，我们预言机进行了询问，我

39、们就可以攻破就可以攻破f的单向性的单向性。*()rH st1*()(|0)kbG rsm将将CPA体制变成体制变成CCA2体制体制 n假设我们有一个在选择明文攻击下是语义假设我们有一个在选择明文攻击下是语义安全的公钥加密体制，如安全的公钥加密体制，如ElGamal。这样的。这样的体制应该是非确定性的。我们可以将加密体制应该是非确定性的。我们可以将加密函数写为：函数写为：E(m,r)n其中，其中，m是需要加密的消息，是需要加密的消息，r是输入的随是输入的随机数。解密函数用机数。解密函数用D(c)表示。对于表示。对于ElGamal加密体制来说，我们有：加密体制来说，我们有：E(m,r)=(gr,m

40、yr)将将CPA体制变成体制变成CCA2体制体制 nFujisaki和Okamoto显示了如何将在选择明文攻击下是语义安全的体制转变成在适应性选择密文攻击下是语义安全的体制。他们的结论只适用于随机预言模型。n将上述的加密函数变为：其中H是Hash函数n解密函数变为：n我们需要检查是否有下式成立：n如果上式成立，我们恢复消息 ，否则，我们返回该密文是不合法的。(,)(|,(|)E m rE m r H m r()mD c(,()cE m H m|mm r n于于ElGamal体制来说，加密算法变为体制来说，加密算法变为n这个算法的效率比原始算法要稍低一些。这个算法的效率比原始算法要稍低一些。(|

41、)(|)(,(|)H m rH m rgm r yBF方案加密对于明文对于明文m0,1n，首先随机选取一个整数，首先随机选取一个整数r Zq*,然后计算然后计算 U=rP,V=m H2(gIDr)这里这里gID=(QID,Ppub),则密文则密文C=（U,V）。）。随机选择一个随机选择一个R 0,1n,r=H3(R,m)U=rP,V=R H2(gIDr)，W=m H4(R)密文密文C=（U,V,W）BF方案解密为了解密一个密文为了解密一个密文C=（U,V），计算：），计算：m=V H2(SID,U)为了解密一个密文为了解密一个密文C=(U,V,W),计算计算R=V H2(SID,U)，m=W

42、H4(R)，设设r=H3(R,m)，测试时候有测试时候有U=rP，如果成立，输出，如果成立，输出m，否则拒，否则拒绝这个密文绝这个密文nE.Fujisaki and T.Okamoto,Secure integration of asymmetric and symmetric encryption schemes,Proc.Crypto 1999,pp.537-554,1999.8.3 可证明安全的数字签名体制分叉引理n我们首先来介绍一下分叉引理，它适用于下面类我们首先来介绍一下分叉引理，它适用于下面类型的数字签名算法：型的数字签名算法：n为了对消息为了对消息m签名，签名者执行如下步骤：签名

43、，签名者执行如下步骤：n签名者产生一个承诺签名者产生一个承诺 。n签名者计算签名者计算 。n签名者计算签名者计算 ，它是关于，它是关于 和和u的的“签名签名”。n签名算法的输出为签名算法的输出为 。n在在DSA中，中，这，这里，里，r=(gk mod p)mod q。11(|)uhm21112(,(|),)hm1()uh m12(,()mod)r kuxrqn在在Schnorr签名方案中签名方案中1kg1(|)uhm2()modxukqn在随机预言模型中，假设敌手在随机预言模型中，假设敌手A能以一个不能以一个不可忽略的概率产生一个存在性伪造，即敌可忽略的概率产生一个存在性伪造，即敌手手A输出输

44、出 。我们假设敌手。我们假设敌手A进行了进行了 这个关键的这个关键的Hash询问，否则，我们可以替敌询问，否则，我们可以替敌手手A进行这个询问。进行这个询问。12(,)mu1(|)uhmn算法算法BA使用相同的随机磁带和稍微不同的随机预使用相同的随机磁带和稍微不同的随机预言运行敌手言运行敌手A两次。敌手两次。敌手A运行多项式时间并且进运行多项式时间并且进行多项式次行多项式次Hash询问。如果前后两次对所有的询问。如果前后两次对所有的Hash询问都给予相同的回答，敌手询问都给予相同的回答，敌手A将输出相同将输出相同的签名。然而，算法的签名。然而，算法BA在前后两次对随机预言都在前后两次对随机预言

45、都给予相同的回答，只是对一个随机的给予相同的回答，只是对一个随机的Hash询问给询问给予不同的回答。这个予不同的回答。这个Hash询问将以一个不可忽略询问将以一个不可忽略的概率等于这个关键的的概率等于这个关键的Hash询问，即算法询问，即算法BA将以将以一个不可忽略的概率获得一个消息一个不可忽略的概率获得一个消息m的两个签名，的两个签名，这个消息这个消息m具有不同的具有不同的Hash询问回答。换句话说，询问回答。换句话说，我们获得：我们获得：1212(,)(,)mumu和n我们试图利用敌手我们试图利用敌手A的两个输出解决困难问的两个输出解决困难问题，这就是算法题，这就是算法BA目标。目标。n定

46、理定理2 在随机预言模型中，假设离散对数在随机预言模型中，假设离散对数问题是一个困难问题，问题是一个困难问题，Schnorr签名方案在签名方案在被动攻击下是安全的被动攻击下是安全的。n证明：设输入给算法BA的是一个我们希望解决的离散对数问题y=gx，输入给敌手A的是一个公钥y。根据分叉引理，我们可以以一个不可忽略的概率获得两个签名：n其中 是第一次运行敌手A时的预言询问，n 是第二次运行敌手A时的预言询问。1212(,()mod)(,()mod)kkmguxukqmguxukq和1(|)uhm1(|)uhm n算法算法BA的目标是恢复出的目标是恢复出x。既然我们有。既然我们有 ，我们一定有我们

47、一定有 。所以我们有：。所以我们有：n既然既然 ，则，则A0。算法。算法BA就能够通过下就能够通过下式求解要求的离散对数问题。式求解要求的离散对数问题。11kkmodAxBq()modAuuq22()modBquu1modxA Bq下面显示下面显示Schnorr签名方案在积极攻签名方案在积极攻击下也是安全的。击下也是安全的。n为了能够在积极攻击下提供证明，我们需为了能够在积极攻击下提供证明，我们需要显示算法要显示算法BA是如何回答算法是如何回答算法A的签名询问的签名询问的。为了做到这一点，我们利用随机预言的。为了做到这一点，我们利用随机预言模型。我们利用算法模型。我们利用算法BA能够选择能够选

48、择Hash函数函数输出的能力。输出的能力。n在没有私钥的情况下，算法在没有私钥的情况下，算法BA给出签名的给出签名的过程称为签名询问的模拟。签名询问的模过程称为签名询问的模拟。签名询问的模拟说明了在随机预言模型中积极攻击并不拟说明了在随机预言模型中积极攻击并不比被动攻击更具有威力。任何积极攻击都比被动攻击更具有威力。任何积极攻击都可以通过模拟签名询问来转变为被动攻击。可以通过模拟签名询问来转变为被动攻击。n下面给出在下面给出在Schnorr签名方案中签名询问的模拟过签名方案中签名询问的模拟过程。我们假设模拟器保存一个列表程。我们假设模拟器保存一个列表L，该列表记，该列表记录以前的随机预言询问，

49、当输入一个消息录以前的随机预言询问，当输入一个消息m时，时，模拟器执行以下步骤：模拟器执行以下步骤：n选择随机数选择随机数s和和un计算计算r=gsy u。n如果如果 ，模拟器返回到步骤。，模拟器返回到步骤。n设置设置L=L(r|m,u)，即当输入，即当输入(r|m)时，时，Hash预言总是回答预言总是回答u。n输出签名输出签名(u,s)。(|,),rm uL uun以上过程确实生成了一个合法签名。也就以上过程确实生成了一个合法签名。也就是说，假设是说，假设h是一个随机预言，对于算法是一个随机预言，对于算法A来说，上述的模拟与一个真实的签名算法来说，上述的模拟与一个真实的签名算法是不可区分的。

50、因此，我们有下面的定理。是不可区分的。因此，我们有下面的定理。n定理定理3 在随机预言模型中，假设离散对数在随机预言模型中，假设离散对数问题是一个困难问题，问题是一个困难问题，Schnorr签名方案在签名方案在积极攻击下是安全的。积极攻击下是安全的。RSA-PSSnRSA数字签名方案是不安全的，一个解决数字签名方案是不安全的，一个解决办法是使用称为办法是使用称为RSA-PSS（probabilistic signature scheme）的系统。在）的系统。在RSA问题是问题是困难的假设下，困难的假设下，RSA-PSS在随机预言模型在随机预言模型中被证明是安全的。中被证明是安全的。nRSA数字