第九章可证明安全性理论

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理论知道，要达到完理论知道，要达到完 美安全性，密钥必须和明文一样长并且相同美安全性，密钥必须和明文一样长并且相同 的密钥不能使用两次。然而，在公钥密码体的密钥不能使用两次。然而，在公钥密码体 制中，我们假设加密密钥可以用来加密很多制中，我们假设加密密钥可以用来加密很多 消息并且通常是很短的。因此，完美安全性消息并且通常是很短的。因此，完美安全性 对于公钥密码体制来说是不现实的。对于公钥密

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

5、难显示一个加密体制具有语义安全我们很难显示一个加密体制具有语义安全 性，然而，我们却可以比较容易显示一个性，然而，我们却可以比较容易显示一个 加密体制具有多项式安全性。多项式安全加密体制具有多项式安全性。多项式安全 性也称为密文不可区分性。幸运的是，如性也称为密文不可区分性。幸运的是，如 果一个加密体制具有多项式安全性，那么果一个加密体制具有多项式安全性，那么 我们可以显示该体制也具有语义安全性。我们可以显示该体制也具有语义安全性。 因此，为了显示一个加密体制是语义安全因此，为了显示一个加密体制是语义安全 的，我们只需要显示该体制是多项式安全的，我们只需要显示该体制是多项式安全 的。的。 n如

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

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

8、称这个加密体制是多项式安全的，其中p(k) 是一个多项式函数，是一个多项式函数，k是一个足够大的安全参数。是一个足够大的安全参数。 01 1 Pr( (, ,) 2 Ab AdvA cy m mb 1 ( ) A Adv p k 三种基本的攻击模型三种基本的攻击模型 n选择明文攻击（选择明文攻击（Chosen Plaintext Attack, CPA），）， n选择密文攻击（选择密文攻击（Chosen Ciphertext Attack, CCA） n适应性选择密文攻击（适应性选择密文攻击（Adaptive Chosen Ciphertext Attack, CCA2）。）。 选择明文攻击选

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

10、攻击模型。在选择密文攻击中，明文攻击稍强的攻击模型。在选择密文攻击中， 敌手可以访问一个黑盒，这个黑盒能进行解密。敌手可以访问一个黑盒，这个黑盒能进行解密。 在午餐时间，敌手可以选择多项式个密文来询在午餐时间，敌手可以选择多项式个密文来询 问解密盒，解密盒把解密后的明文发送给敌手。问解密盒，解密盒把解密后的明文发送给敌手。 在下午时间，敌手被告知一个目标密文，要求在下午时间，敌手被告知一个目标密文，要求 敌手在没有解密盒帮助的情况下解密目标密文，敌手在没有解密盒帮助的情况下解密目标密文， 或者找到关于明文的有用信息。或者找到关于明文的有用信息。 n在上面给出的多项式安全性的攻击游戏中，选在上面

11、给出的多项式安全性的攻击游戏中，选 择密文攻击允许敌手在寻找阶段询问解密盒，择密文攻击允许敌手在寻找阶段询问解密盒， 但是在猜测阶段不能询问解密盒。但是在猜测阶段不能询问解密盒。 适应性选择密文攻击适应性选择密文攻击 n适应性选择密文攻击是一种非常强的攻击适应性选择密文攻击是一种非常强的攻击 模型。除了目标密文外，敌手可以选择任模型。除了目标密文外，敌手可以选择任 何密文对解密盒进行询问。目前普遍认为，何密文对解密盒进行询问。目前普遍认为， 任何新提出的公钥加密算法都应该在适应任何新提出的公钥加密算法都应该在适应 性选择密文攻击下达到多项式安全性。性选择密文攻击下达到多项式安全性。 语义安全语

12、义安全 n定义定义1 如果一个公钥加密体制在适应性选如果一个公钥加密体制在适应性选 择密文攻击（择密文攻击（adaptive chosen ciphertext attacks）下是语义安全的，我们就说该体）下是语义安全的，我们就说该体 制是安全的。制是安全的。 n定义定义2 如果一个公钥加密体制在适应性选如果一个公钥加密体制在适应性选 择密文攻击下是多项式安全的，我们就说择密文攻击下是多项式安全的，我们就说 该体制是安全的该体制是安全的。 引理引理1 一个可展（一个可展（Malleability）的加密）的加密 体制在适应性选择密文攻击下是不安全体制在适应性选择密文攻击下是不安全 的。的。

13、n证明：假设一个加密体制是可展的，当给证明：假设一个加密体制是可展的，当给 定一个目标密文定一个目标密文cb时，我们可以把它修改成时，我们可以把它修改成 一个相关的密文一个相关的密文cb *。这种相关的关系也应。这种相关的关系也应 该存在于和该存在于和mb和和mb*。然后敌手利用解密预。然后敌手利用解密预 言机（解密盒）来获得言机（解密盒）来获得cb *的明文。最后敌的明文。最后敌 手根据手根据mb*来恢复来恢复mb。 2数字签名体制的安全性概念数字签名体制的安全性概念 n对于数字签名体制，存在以下几种伪造类对于数字签名体制，存在以下几种伪造类 型：型： n（1）完全攻破）完全攻破:敌手能够产

14、生与私钥持有者敌手能够产生与私钥持有者 相同的签名，这相当于恢复出了私钥。相同的签名，这相当于恢复出了私钥。 n（2）选择性伪造）选择性伪造:敌手能够伪造一个他选择敌手能够伪造一个他选择 的消息的签名。的消息的签名。 n（3）存在性伪造）存在性伪造:敌手能够伪造一个消息的敌手能够伪造一个消息的 签名，这个消息可能仅仅是一个随机比特签名，这个消息可能仅仅是一个随机比特 串串 攻击模型攻击模型 n 被动攻击被动攻击 在被动攻击中，敌手被告知一个公钥，要求产在被动攻击中，敌手被告知一个公钥，要求产 生一个选择性伪造或存在性伪造。这是一种比生一个选择性伪造或存在性伪造。这是一种比 较弱的攻击模型。较弱

15、的攻击模型。 n 积极攻击积极攻击 积极攻击中最强的攻击是适应性选择消息攻击积极攻击中最强的攻击是适应性选择消息攻击 （adaptive chosen messages attacks），即），即 敌手可以访问一个签名预言机，它能够产生合敌手可以访问一个签名预言机，它能够产生合 法的签名。敌手的目标是产生一个消息的签名，法的签名。敌手的目标是产生一个消息的签名， 当然这个消息不能是已经询问过签名预言机的当然这个消息不能是已经询问过签名预言机的 消息。消息。 n定义定义3 如果一个数字签名体制在适应性选如果一个数字签名体制在适应性选 择消息攻击下能够抵抗存在性伪造，我们择消息攻击下能够抵抗存在性

16、伪造，我们 就说该体制是安全的。就说该体制是安全的。 3随机预言模型随机预言模型 n显示一个密码协议安全的现代方法是可证显示一个密码协议安全的现代方法是可证 明安全性。可证明安全性的目的在于证明：明安全性。可证明安全性的目的在于证明： 如果一个敌手能够攻破一个密码体制的某如果一个敌手能够攻破一个密码体制的某 个安全概念，那么我们就可以利用该敌手个安全概念，那么我们就可以利用该敌手 做一些认为不可能的事情。做一些认为不可能的事情。 n我们假设一个敌手（一个概率算法）能够我们假设一个敌手（一个概率算法）能够 以一个不可忽略的概率攻破以一个不可忽略的概率攻破RSA的某个安的某个安 全概念（比方说语义

17、安全性）。对于一个全概念（比方说语义安全性）。对于一个 安全参数安全参数(安全参数用于测量密钥长度的大安全参数用于测量密钥长度的大 小，比如在小，比如在RSA中，安全参数可能是模数中，安全参数可能是模数n 的比特数的比特数)为为k的密码体制，如果敌手成功的密码体制，如果敌手成功 的概率大于的概率大于1/p（k），我们就说这个敌手），我们就说这个敌手 以一个不可忽略的概率成功，这里的以一个不可忽略的概率成功，这里的p是一是一 个以个以k为变量的多项式。为变量的多项式。 n我们假设敌手我们假设敌手A是一个被动攻击敌手，即对是一个被动攻击敌手，即对 于于RSA加密，他不进行解密询问。我们现加密，他不

18、进行解密询问。我们现 在希望能够构造一个新算法在希望能够构造一个新算法BA，它能够在，它能够在 输入一个整数输入一个整数n和调用多项式次敌手和调用多项式次敌手A的情的情 况下，以一个不可忽略的概率输出况下，以一个不可忽略的概率输出n的因子。的因子。 算法算法BA说明了如果存在敌手说明了如果存在敌手A，就存在一个，就存在一个 多项式时间因子分解算法，能够以一个不多项式时间因子分解算法，能够以一个不 可忽略的概率解决因子分解问题。既然我可忽略的概率解决因子分解问题。既然我 们目前并不相信存在这样的因子分解算法，们目前并不相信存在这样的因子分解算法， 我们也可以断定这样的敌手我们也可以断定这样的敌手

19、A是不存在的。是不存在的。 可证明安全的思想可证明安全的思想 n可证明安全的思想就是给定一个算法可证明安全的思想就是给定一个算法A，我们提出一，我们提出一 个新算法个新算法BA，BA把把A作为子程序。输入给作为子程序。输入给BA的是我的是我 们希望解决的困难问题，输入给们希望解决的困难问题，输入给A的是某个密码算法。的是某个密码算法。 然而，如果然而，如果A是一个积极攻击敌手，即是一个积极攻击敌手，即A可以对输入可以对输入 的公钥进行解密预言询问或签名预言询问。算法的公钥进行解密预言询问或签名预言询问。算法BA 要想使用要想使用A作为子程序，就需对作为子程序，就需对A的询问提供回答。的询问提供

20、回答。 算法算法BA需要应对以下几个问题：需要应对以下几个问题： n它的回答应该看起来是合法的。因为加密应该能够它的回答应该看起来是合法的。因为加密应该能够 解密，签名应该能够被验证，否则，算法解密，签名应该能够被验证，否则，算法A就知道它就知道它 的预言机在撒谎。算法的预言机在撒谎。算法BA就不能再确保算法就不能再确保算法A是以一是以一 个不可忽略的概率成功。个不可忽略的概率成功。 n它的回答应该与如果预言机是真正的解密它的回答应该与如果预言机是真正的解密/加密预言加密预言 机时机时A期望的回答具有相同的概率分布。期望的回答具有相同的概率分布。 n自始至终，预言机的回答应该是一致的。自始至终

21、，预言机的回答应该是一致的。 n算法算法BA需要在不知道私钥的情况下提供这些回答。需要在不知道私钥的情况下提供这些回答。 随机预言模型随机预言模型 n我们必须让我们必须让BA在不知道私钥的情况下能够在不知道私钥的情况下能够 解密或者签名，但既然我们的体制是安全解密或者签名，但既然我们的体制是安全 的，这一点意味着是不可能的。的，这一点意味着是不可能的。 随机预言模型随机预言模型 n为了回避这个问题，我们通常使用随机预言模型。为了回避这个问题，我们通常使用随机预言模型。 n随机预言是一个理想的随机预言是一个理想的Hash函数。对于每一个新函数。对于每一个新 的询问，随机预言产生一个随机值作为回答

22、，如的询问，随机预言产生一个随机值作为回答，如 果进行两次相同的询问，回答一定相同。在随机果进行两次相同的询问，回答一定相同。在随机 预言模型中，我们假设敌手并不使用密码算法中预言模型中，我们假设敌手并不使用密码算法中 定义的那个定义的那个Hash函数，也就是说，即使我们将随函数，也就是说，即使我们将随 机预言换成真实的机预言换成真实的Hash函数时，敌手函数时，敌手A也是成功也是成功 的。的。 n对于对于A的解密预言询问和签名预言询问，算法的解密预言询问和签名预言询问，算法BA 是通过欺骗随机预言的回答来适合自己的需要的。是通过欺骗随机预言的回答来适合自己的需要的。 8.2 可证明安全的公钥

23、密码体制可证明安全的公钥密码体制 RSA的安全性 n引理引理2 RSA不是多项式安全的。不是多项式安全的。 n证明：假设敌手知道用户只加密了证明：假设敌手知道用户只加密了m1和和m2中的一中的一 个消息。敌手还知道用户的公钥，即个消息。敌手还知道用户的公钥，即e和和n。当敌。当敌 手被告知一个密文手被告知一个密文c，要求判断，要求判断c对应的明文对应的明文m是是 m1还是还是m2时，敌手只需要计算：时，敌手只需要计算： n如果如果 ，则敌手知道，则敌手知道m = m1。否则敌手知道。否则敌手知道m = m2。 n除了以上的攻击外，除了以上的攻击外，RSA在适应性选择密文攻击在适应性选择密文攻击

24、 下也是不安全的，这主要是因为下也是不安全的，这主要是因为RSA具有同态性具有同态性 质。质。 1 mod e cmn cc RSA的安全性 n定义4 给定m1和m2的加密，如果能在不知 道m1或m2的条件下确定m1m2的加密结果， 我们就说该加密体制具有同态性质 （homomorphic property）。 n根据以下方程知，RSA具有同态性质： 1212 () mod(mod )(mod )mod eee mmnmn mnn RSA的安全性 n引理引理3 RSA不是不是CCA2安全的。安全的。 n证明：假设敌手想解密证明：假设敌手想解密 ： n敌手首先生成一个相关的密文敌手首先生成一个相

25、关的密文 并询问解密并询问解密 预言机。敌手得到预言机。敌手得到c 的明文的明文m 。然后敌手计算：。然后敌手计算： n因此，敌手获得了密文因此，敌手获得了密文c对应的明文对应的明文m。 mod e cmn 2ecc (2)22 22222 dededd mcccm m ElGamal的安全性 n引理引理4 如果如果DDH问题是困难的，那么问题是困难的，那么ElGamal加密加密 体制在选择明文攻击下是多项式安全的。体制在选择明文攻击下是多项式安全的。 n 证明：为了显示证明：为了显示ElGamal是多项式安全的，我们首是多项式安全的，我们首 先假设存在一个能够攻破先假设存在一个能够攻破ElG

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

27、安全性的安全性 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”。 n下面解释为什么算法下面解释为什

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

29、出等的概率输出“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敌手首先生成一个

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

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

32、语义安全的。适应性选择密文攻击下是语义安全的。 OAEP n设设f是任何是任何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

33、看成是两轮看成是两轮Feistel网络，网络， 01 0,10,1 kn k G : 01 0,10,1k n k H : 11 ( )( |0( )|( |0( ) kk E mf mGRRH mGR 1 |0( ) k mG R 1 (|0( ) k RH mG R 1 |0( ) k mG R 1 |0km R R G H n为了解密E(m)，我们可以计算 11 |( )|0( )|(|0( ) kk ATRH TmG RRH mG R RSA-OAEP n定理定理1 在随机预言模型中，我们将在随机预言模型中，我们将G和和H模模 拟成随机预言机。假设拟成随机预言机。假设RSA问题是一个困

34、问题是一个困 难问题，难问题，RSA-OAEP加密方案在适应性选加密方案在适应性选 择密文攻击下是语义安全的。择密文攻击下是语义安全的。 n证明：我们首先将证明：我们首先将RSA函数函数f写成：写成： n然后将然后将RSA-OAEP定义为：定义为： 01 * 0,10,1(/) ( , )( | ) mod kn k e Z NZ f s ts tN : 1 (|0 )( ), ( ) k smG rtrH s n我们可以证明我们可以证明RSA问题与函数问题与函数f的单向性是的单向性是 等价的，且从等价的，且从f(s, t)恢复出恢复出s与从与从f(s, t)恢复出恢复出 (s, t)是同样困

35、难的。接下来的任务就是如何是同样困难的。接下来的任务就是如何 利用攻破利用攻破RSA-OAEP的敌手的敌手A来构造一个能来构造一个能 够解决够解决RSA函数单向性的算法函数单向性的算法BA，即对于，即对于 固定的固定的RSA模数模数N，给定，给定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

36、=1。同时，算法。同时，算法BA必须回答必须回答 A的询问，包括的询问，包括Hash函数函数G的询问，的询问，Hash函数函数H 的询问和解密预言询问。为了保持一致性，的询问和解密预言询问。为了保持一致性，BA维维 护两个列表护两个列表L1和和L2。这两个列表开始都为空，。这两个列表开始都为空，L1 用于跟踪用于跟踪A对预言机对预言机G的询问，的询问，L2用于跟踪用于跟踪A对预对预 言机言机H的询问。下面详细解释的询问。下面详细解释BA是如何回答这些是如何回答这些 询问的。询问的。 nG()询问：对于列表询问：对于列表L2中的任何询问中的任何询问，BA检查是检查是 否有下式成立：否有下式成立：

37、 n如果上式成立，我们就已经完成了对如果上式成立，我们就已经完成了对f在在c*求逆的求逆的 任务，我们仍然可以继续模拟任务，我们仍然可以继续模拟G并设置：并设置： n如果对于任何的如果对于任何的上式都不成立，上式都不成立，BA在在G的值域上的值域上 随机选择一个数来回答随机选择一个数来回答A并将该数记录到列表并将该数记录到列表L1 中。中。 * ( ,( )cfH 1 ( )(| 0 ) k b Gm nH()询问：询问：BA在在H的值域上随机选择一个数的值域上随机选择一个数 来回答来回答A并将该数记录到列表并将该数记录到列表L2中。对于列中。对于列 表表L1中的任何询问中的任何询问，BA检查

38、是否有下式成检查是否有下式成 立：立： n如果上式成立，我们同样完成了对如果上式成立，我们同样完成了对f在在c*求求 逆的任务。逆的任务。 * ( ,( )cfH n解密询问：给定一个密文解密询问：给定一个密文c，BA查找列表查找列表L1 和和L2使其满足：对于一对使其满足：对于一对和和，如果设：，如果设： n那么那么c = f (, )且且的尾部至少有的尾部至少有k1个比特为个比特为 0。如果上述情况成立，。如果上述情况成立，BA返回返回的首部的的首部的n 个比特，否则个比特，否则BA返回该密文是不合法的。返回该密文是不合法的。 n如果一个按照正确方式产生的密文能够通如果一个按照正确方式产生

39、的密文能够通 过上述的解密预言机，我们肯定能够获得过上述的解密预言机，我们肯定能够获得 原始的明文原始的明文 ,( ),( )HG n们需要显示上述的解密预言机能够们需要显示上述的解密预言机能够“欺骗欺骗” 敌手敌手A。如果敌手。如果敌手A能够以一个不可忽略的能够以一个不可忽略的 优势攻破优势攻破RSA-OAEP的语义安全性，算法的语义安全性，算法 BA就能够以一个不可忽略的概率对就能够以一个不可忽略的概率对f求逆。求逆。 n我们知道，我们知道，BA已经假设了已经假设了c*= f (s*, t*)是是mb 的加密密文。因此，这里应该存在一个的加密密文。因此，这里应该存在一个r* 满足：满足：

40、n我们首先要显示模拟解密预言失败的概率我们首先要显示模拟解密预言失败的概率 是可以忽略的，然后显示只要敌手是可以忽略的，然后显示只要敌手A能够以能够以 一个不可忽略的概率猜对一个不可忽略的概率猜对b，那么，那么s*被提交被提交 给给H预言机进行询问的概率就是不可忽略的。预言机进行询问的概率就是不可忽略的。 只要只要s*被提交给被提交给H预言机进行了询问，我们预言机进行了询问，我们 就可以攻破就可以攻破f的单向性的单向性。 * ()rH st 1 * ()(|0 ) k b G rsm 将将CPA体制变成体制变成CCA2体制体制 n假设我们有一个在选择明文攻击下是语义假设我们有一个在选择明文攻击

41、下是语义 安全的公钥加密体制，如安全的公钥加密体制，如ElGamal。这样的。这样的 体制应该是非确定性的。我们可以将加密体制应该是非确定性的。我们可以将加密 函数写为：函数写为： E(m, r) n其中，其中，m是需要加密的消息，是需要加密的消息，r是输入的随是输入的随 机数。解密函数用机数。解密函数用D(c)表示。对于表示。对于ElGamal 加密体制来说，我们有：加密体制来说，我们有： E(m, r)=(gr, myr) 将将CPA体制变成体制变成CCA2体制体制 nFujisaki和Okamoto显示了如何将在选择明文攻击 下是语义安全的体制转变成在适应性选择密文攻 击下是语义安全的体

42、制。他们的结论只适用于随 机预言模型。 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这个算法的效率比原始算法要稍低一些。这个算法的效率比原始算法要稍低一些。 (| )(| ) (,(| ) H m rH m r gm r y BF方案加密 对于明文对于明文m0,1n，首先随机选取一个整数，首先随

43、机选取一个整数 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 H4(R)， 设设r=H3(R, m)， 测试时候有测试时候有U=r

44、P，如果成立，输出，如果成立，输出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签名，签名者执行如下步骤：签名，签名者执行如下步骤： n签名者

45、产生一个承诺签名者产生一个承诺 。 n签名者计算签名者计算 。 n签名者计算签名者计算 ，它是关于，它是关于 和和u的的“签名签名”。 n签名算法的输出为签名算法的输出为 。 n在在DSA中，中， ， ， ，这，这 里，里，r = (gk mod p) mod q。 1 1 (|)uhm 2 1 112 (, (|),)hm 1 ( )uh m 1 2 ( ,()mod )r kuxrq n在在Schnorr签名方案中签名方案中 1 k g 1 (|)uhm 2 ()modxukq n在随机预言模型中，假设敌手在随机预言模型中，假设敌手A能以一个不能以一个不 可忽略的概率产生一个存在性伪造，即

46、敌可忽略的概率产生一个存在性伪造，即敌 手手A输出输出 。我们假设敌手。我们假设敌手A进行了进行了 这个关键的这个关键的Hash询问，否则，我们可以替敌询问，否则，我们可以替敌 手手A进行这个询问。进行这个询问。 12 ( , ,)mu 1 (|)uhm n算法算法BA使用相同的随机磁带和稍微不同的随机预使用相同的随机磁带和稍微不同的随机预 言运行敌手言运行敌手A两次。敌手两次。敌手A运行多项式时间并且进运行多项式时间并且进 行多项式次行多项式次Hash询问。如果前后两次对所有的询问。如果前后两次对所有的 Hash询问都给予相同的回答，敌手询问都给予相同的回答，敌手A将输出相同将输出相同 的签

47、名。然而，算法的签名。然而，算法BA在前后两次对随机预言都在前后两次对随机预言都 给予相同的回答，只是对一个随机的给予相同的回答，只是对一个随机的Hash询问给询问给 予不同的回答。这个予不同的回答。这个Hash询问将以一个不可忽略询问将以一个不可忽略 的概率等于这个关键的的概率等于这个关键的Hash询问，即算法询问，即算法BA将以将以 一个不可忽略的概率获得一个消息一个不可忽略的概率获得一个消息m的两个签名，的两个签名， 这个消息这个消息m具有不同的具有不同的Hash询问回答。换句话说，询问回答。换句话说， 我们获得：我们获得： 1212 ( , ,) ( ,)mumu 和 n我们试图利用敌

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

49、k mguxukqmguxukq 和 1 (|)uhm 1 (|)uhm n算法算法BA的目标是恢复出的目标是恢复出x。既然我们有。既然我们有 ， 我们一定有我们一定有 。所以我们有：。所以我们有： n既然既然 ，则，则A0。算法。算法BA就能够通过下就能够通过下 式求解要求的离散对数问题。式求解要求的离散对数问题。 11 k k modAxBq ()modAuuq 22 ()modBq u u 1 modxA Bq 下面显示下面显示Schnorr签名方案在积极攻签名方案在积极攻 击下也是安全的。击下也是安全的。 n为了能够在积极攻击下提供证明，我们需为了能够在积极攻击下提供证明，我们需 要显

50、示算法要显示算法BA是如何回答算法是如何回答算法A的签名询问的签名询问 的。为了做到这一点，我们利用随机预言的。为了做到这一点，我们利用随机预言 模型。我们利用算法模型。我们利用算法BA能够选择能够选择Hash函数函数 输出的能力。输出的能力。 n在没有私钥的情况下，算法在没有私钥的情况下，算法BA给出签名的给出签名的 过程称为签名询问的模拟。签名询问的模过程称为签名询问的模拟。签名询问的模 拟说明了在随机预言模型中积极攻击并不拟说明了在随机预言模型中积极攻击并不 比被动攻击更具有威力。任何积极攻击都比被动攻击更具有威力。任何积极攻击都 可以通过模拟签名询问来转变为被动攻击。可以通过模拟签名询问来转变为被动攻击。 n下面给出在下面给出在Schnorr签名方案中签名询问的模