21世纪是信息时代，信息已成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它会直接关系到国家安全、企业经营和人们的日常生活。 随着信息安全产业的快速发展，全球对信息安全人才的需求量不断增加，但我国目前信息安全人才极度匮乏，远远不能满足金融、商业、公安、军事和政府等部门的需求。要解决供需矛盾，必须加快信息安全人才的培养，以满足社会对信息安全人才的需求。为此，教育部继2001年批准在武汉大学开设信息安全本科专业之后，又批准了多所高等院校设立信息安全本科专业，而且许多高校和科研院所已设立了信息安全方向的具有硕士和博士学位授予权的学科点。
信息安全是计算机、通信、物理、数学等领域的交叉学科，对于这一新兴学科的培养模式和课程设置，各高校普遍缺乏经验，因此中国计算机学会教育专业委员会和清华大学出版社联合主办了“信息安全专业教育教学研讨会”等一系列研讨活动，并成立了“高等院校信息安全专业系列教材”编审委员会，由我国信息安全领域著名专家肖国镇教授担任编委会主任，指导“高等院校信息安全专业系列教材”的编写工作。编委会本着研究先行的指导原则，认真研讨国内外高等院校信息安全专业的教学体系和课程设置，进行了大量前瞻性的研究工作，而且这种研究工作将随着我国信息安全专业的发展不断深入。系列教材的作者都是既在本专业领域有深厚的学术造诣、又在教学*线有丰富的教学经验的学者、专家。
该系列教材是我国*套专门针对信息安全专业的教材，其特点是：
① 体系完整、结构合理、内容先进。
② 适应面广：能够满足信息安全、计算机、通信工程等相关专业对信息安全领域课程的教材要求。
③ 立体配套：除主教材外，还配有多媒体电子教案、习题与实验指导等。
④ 版本更新及时，紧跟科学技术的新发展。
在全力做好本版教材，满足学生用书的基础上，还经由专家的推荐和审定，遴选了一批国外信息安全领域优秀的教材加入到系列教材中，以进一步满足大家对外版书的需求。“高等院校信息安全专业系列教材”已于2006年年初正式列入普通高等教育“十一五”*教材规划。
2007年6月，教育部高等学校信息安全类专业教学指导委员会成立大会暨*次会议在北京胜利召开。本次会议由教育部高等学校信息安全类专业教学指导委员会主任单位北京工业大学和北京电子科技学院主办，清华大学出版社协办。教育部高等学校信息安全类专业教学指导委员会的成立对我国信息安全专业的发展起到重要的指导和推动作用。2006年教育部给武汉大学下达了“信息安全专业指导性专业规范研制”的教学科研项目。2007年起该项目由教育部高等学校信息安全类专业教学指导委员会组织实施。在高教司和教指委的指导下，项目组团结一致，努力工作，克服困难，历时5年，制定出我国*个信息安全专业指导性专业规范，于2012年年底通过经教育部高等教育司理工科教育处授权组织的专家组评审，并且已经得到武汉大学等许多高校的实际使用。2013年，新一届“教育部高等学校信息安全专业教学指导委员会”成立。经组织审查和研究决定，2014年以“教育部高等学校信息安全专业教学指导委员会”的名义正式发布《高等学校信息安全专业指导性专业规范》（由清华大学出版社正式出版）。
密码学中的可证明安全性出版说明2015年6月，国务院学位委员会、教育部出台增设“网络空间安全”为一级学科的决定，将高校培养网络空间安全人才提到新的高度。2016年6月，中央网络安全和信息化领导小组办公室（下文简称中央网信办）、国家发展和改革委员会、教育部、科学技术部、工业和信息化部及人力资源和社会保障部六大部门联合发布《关于加强网络安全学科建设和人才培养的意见》（中网办发文\[2016\]4号）。为贯彻落实《关于加强网络安全学科建设和人才培养的意见》，进一步深化高等教育教学改革，促进网络安全学科专业建设和人才培养，促进网络空间安全相关核心课程和教材建设，在教育部高等学校信息安全专业教学指导委员会和中央网信办资助的网络空间安全教材建设课题组的指导下，启动了“网络空间安全重点规划丛书”的工作，由教育部高等学校信息安全专业教学指导委员会秘书长封化民校长担任编委会主任。本规划丛书基于“高等院校信息安全专业系列教材”坚实的工作基础和成果、阵容强大的编审委员会和优秀的作者队伍，目前已经有多本图书获得教育部和中央网信办等机构评选的“普通高等教育本科*规划教材”“普通高等教育精品教材”“中国大学出版社图书奖”和“国家网络安全优秀教材奖”等多个奖项。
“网络空间安全重点规划丛书”将根据《高等学校信息安全专业指导性专业规范》（及后续版本）和相关教材建设课题组的研究成果不断更新和扩展，进一步体现科学性、系统性和新颖性，及时反映教学改革和课程建设的新成果，并随着我国网络空间安全学科的发展不断完善，力争为我国网络空间安全相关学科专业的本科和研究生教材建设、学术出版与人才培养做出更大的贡献。
我们的E.mail地址是： zhangm@tup.tsinghua.edu.cn，联系人： 张民。
“网络空间安全重点规划丛书”编审委员会信息安全是一个综合、交叉的学科领域，涉及数学、电子、信息、通信、计算机等诸多学科的长期知识积累和*新发展成果，密码学是信息安全的核心技术，密码技术中的加密方法包括单钥密码体制和公钥密码体制。刻画公钥密码体制的安全性包括两部分: 首先是刻画敌手的模型，说明敌手访问系统的方式和计算能力；其次是刻画安全性概念，说明敌手攻破了方案的安全性意味着什么。公钥加密方案语义安全的概念由Goldwasser和Micali于1984年提出，它以一种思维实验的模型刻画了敌手通过密文得不到明文的任何部分信息，即使是1比特的信息。这一概念的提出开创了可证明安全性领域的先河，将密码学建立在了计算复杂性理论之上，奠定了现代密码学理论的数学基础，从而将密码学从一门艺术变为一门科学。所以说可证明安全性是密码学和计算复杂性理论的天作之合。
本书全面介绍可证明安全性的发展历史及研究成果，共5章。第1章介绍可证明安全性用到的一些数学知识和基本工具，包括密码学中一些常用的数论知识和代数知识、计算复杂性、陷门置换、零知识证明、张成方案与秘密分割方案、归约。第2章介绍语义安全的公钥密码体制的定义，包括公钥加密方案在选择明文攻击下的不可区分性，公钥加密方案在选择密文攻击下的不可区分性，公钥加密方案在适应性选择密文攻击下的不可区分性。第3章介绍几类常用的语义安全的公钥机密体制，包括语义安全的RSA加密方案、Paillier公钥密码系统、Cramer.Shoup密码系统、RSA.FDH签名方案、BLS短签名方案、抗密钥泄露的公钥加密系统。第4章介绍基于身份的密码体制，包括基于身份的密码体制定义和安全模型，随机谕言机模型下的基于身份的密码体制，无随机谕言机模型的选定身份安全的IBE，无随机谕言机模型下的完全安全的IBE，密文长度固定的分层次IBE，基于对偶系统加密的完全安全的IBE和HIBE、从选择明文安全到选择密文安全。第5章介绍基于属性的密码体制，包括基于属性的密码体制的一般概念，基于模糊身份的加密方案，基于密钥策略的属性加密方案，基于密文策略的属性加密方案，基于对偶系统加密的完全安全的属性加密，非单调访问结构的属性加密方案，函数加密。本书在编写过程中得到了课题组成员的大力支持和帮助，他们是4位博士后: 王涛博士、王鑫博士、来齐齐博士、张丽娜博士，5位博士生: 程灏、乜国雷、侯红霞、周彦伟、赵一，5位硕士生: 武朵朵、马晓敏、李士强、孟茹、赵艳琪，在此一并表示感谢。另外，本书的编写得到国家自然科学基金项目（批准号: 61272436, 61572303）的资助，还得到陕西师范大学优秀著作出版基金和陕西师范大学重点学科建设项目的资助，在此表示感谢。
由于作者水平有限，书中不足在所难免，恳请读者批评指正。
密码学中的可证明安全性前言
作者2017年1月
杨波，北京大学学士，西安电子科技大学硕士、博士，陕西师范大学计算机科学学院教授、博士生导师，陕西省百人计划特聘教授，中国密码学会理事，中国密码学会密码算法专业委员会委员，《密码学报》编委。曾任华南农业大学信息学院、软件学院院长。2011年起在陕西师范大学计算机科学学院工作。2005年担任第四届中国信息和通信安全学术会议程序委员会主席，2009年担任中国密码学会年会副主席，2010年起担任The Joint Workshop on Information Security (JWIS ) Co-General Chair。主持多项国家自然科学基金、863计划、国家密码发展基金、国防科技重点实验室基金、陕西省自然科学基金项目。
第1章一些基本概念和工具1
1.1密码学中一些常用的数学知识1
1.1.1群、环、域1
1.1.2素数和互素数3
1.1.3模运算4
1.1.4模指数运算6
1.1.5费马定理、欧拉定理和卡米歇尔定理7
1.1.6欧几里得算法10
1.1.7中国剩余定理13
1.1.8离散对数16
1.1.9二次剩余17
1.1.10循环群20
1.1.11循环群的选取20
1.1.12双线性映射22
1.2计算复杂性22
1.3陷门置换25
1.3.1陷门置换的定义25
1.3.2单向陷门置换26
1.3.3陷门置换的简化定义27
1.4零知识证明27
1.4.1交互证明系统27
1.4.2交互证明系统的定义28
1.4.3交互证明系统的零知识性29
1.4.4非交互式证明系统31
1.4.5适应性安全的非交互式零知识证明31
1.5张成方案与秘密分割方案33
1.5.1秘密分割方案33
1.5.2线性秘密分割方案34密码学中的可证明安全性目录
1.5.3张成方案35
1.5.4由张成方案建立秘密分割方案35
1.6归约36
第1章参考文献38第2章语义安全的公钥密码体制的定义39
2.1公钥密码体制的基本概念39
2.1.1公钥加密方案39
2.1.2选择明文攻击下的不可区分性定义40
2.1.3基于陷门置换的语义安全的公钥加密方案构造41
2.1.4群上的离散对数问题43
2.1.5判定性Diffie\|Hellman(DDH)假设44
2.2公钥加密方案在选择密文攻击下的不可区分性46
2.3公钥加密方案在适应性选择密文攻击下的不可区分性55
第2章参考文献61
第3章几类语义安全的公钥密码体制63
3.1语义安全的RSA加密方案63
3.1.1RSA加密算法63
3.1.2RSA问题和RSA假设64
3.1.3选择明文安全的RSA加密64
3.1.4选择密文安全的RSA加密67
3.2Paillier公钥密码系统69
3.2.1合数幂剩余类的判定70
3.2.2合数幂剩余类的计算71
3.2.3基于合数幂剩余类问题的概率加密方案73
3.2.4基于合数幂剩余类问题的单向陷门置换74
3.2.5Paillier密码系统的性质75
3.3CramerShoup密码系统76
3.3.1CramerShoup密码系统的基本机制76
3.3.2CramerShoup密码系统的安全性证明77
3.4RSAFDH签名方案79
3.4.1RSA签名方案79
3.4.2RSAFDH签名方案的描述80
3.4.3RSAFDH签名方案的改进83
3.5BLS短签名方案84
3.5.1BLS短签名方案所基于的安全性假设84
3.5.2BLS短签名方案描述84
3.5.3BLS短签名方案的改进一86
3.5.4BLS短签名方案的改进二86
3.6抗密钥泄露的公钥加密系统87
3.6.1抗泄露密码体制介绍87
3.6.2密钥泄露攻击模型92
3.6.3基于哈希证明系统的抗泄露攻击的公钥加密方案94
3.6.4基于推广的DDH假设的抗泄露攻击的公钥加密方案97
3.6.5抗选择密文的密钥泄露攻击99
3.6.6抗弱密钥泄露攻击109
第3章参考文献111
第4章基于身份的密码体制113
4.1基于身份的密码体制定义和安全模型113
4.1.1基于身份的密码体制简介113
4.1.2选择明文安全的IBE114
4.1.3选择密文安全的IBE方案115
4.1.4选定身份攻击下的IBE方案116
4.1.5分层次的IBE系统117
4.2随机谕言机模型下的基于身份的密码体制118
4.2.1BF方案所基于的困难问题118
4.2.2BF方案描述119
4.2.3BF方案的安全性120
4.2.4选择密文安全的BF方案124
4.3无随机谕言机模型的选定身份安全的IBE128
4.3.1双线性DiffieHellman求逆假设128
4.3.2基于判定性BDH假设的IBE和HIBE方案129
4.3.3基于判定性BDHI假设的IBE和HIBE方案131
4.4无随机谕言机模型下的基于身份的密码体制134
4.4.1判定性双线性DiffieHellman假设134
4.4.2无随机谕言机模型下的IBE构造134
4.5密文长度固定的分层次IBE143
4.5.1弱双线性DiffieHellman求逆假设143
4.5.2一个密文长度固定的HIBE系统144
第3章几类语义安全的公钥密码体制
3.1语义安全的RSA加密方案3.1.1RSA加密算法 RSA算法是1978年由Rivest、Shamir和Adleman提出的一种用数论构造的，也是迄今理论上*为成熟完善的公钥密码体制，该体制已得到广泛的应用。它作为陷门置换在1.3.1节中有过介绍，下面是算法的详细描述。 设GenPrime是大素数产生算法。 密钥产生过程: GenRSA(): p,q←GenPrime(); n=pq,φ(n)=(p－1)(q－1); 选e,满足1计算d,满足d·e≡1 mod φ(n) pk=(n,e),sk=(n,d). 加密（其中Mpk(M): CT=Me mod n. 解密: sk(CT): M=CTd mod n. 下面证明RSA算法中解密过程的正确性。 证明: 由加密过程知CT≡Me mod n，所以 CTd mod n≡Med mod n≡Mkφ(n)+1 mod n 下面分两种情况:
（1） M与n互素。由欧拉定理: Mφ(n)≡1 mod n，Mkφ(n)≡1 mod n，Mkφ(n)+1≡M mod n 即CTd mod n≡M。密码学中的可证明安全性第3章几类语义安全的公钥密码体制
（2） (M,n)≠1。先看(M,n)=1的含义，由于n=pq，所以(M,n)=1意味着M不是p的倍数也不是q的倍数。因此(M,n)≠1意味着M是p的倍数或q的倍数，不妨设M=tp，其中t为正整数。此时必有(M,q)=1，否则M也是q的倍数，从而是pq的倍数，与M由(M,q)=1及欧拉定理得Mφ(q)≡1 mod q，所以Mkφ(q)≡1 mod q，Mkφ(q)φ(p)≡1 mod q，Mkφ(n)≡1 mod q，因此存在一个整数r，使得Mkφ(n)=1+rq，两边同乘以M=tp得Mkφ(n)+1=M+rtpq=M+rtn，即Mkφ(n)+1≡M mod n，所以CTd mod n≡M。 （证毕） 如果消息M是Z*n中均匀随机的，用公开钥(n,e)对M加密，则敌手不能恢复M。然而如果敌手发起选择密文攻击，以上性质不再成立。比如敌手截获密文CT≡Me mod n后，选择随机数r←RZ*n，计算密文CT′≡re·CT mod n，将CT′给挑战者，获得CT′的明文M′后，可由M≡M′r－1 mod n恢复M，这是因为 M′r－1≡CT′dr－1≡reMedr－1≡redMedr－1≡rMr－1≡M mod n 为使RSA加密方案可抵抗敌手的选择明文攻击和选择密文攻击，需对其加以修改。
3.1.2RSA问题和RSA假设 RSA问题: 已知大整数n,e,y∈Zn，满足1RSA假定: 没有概率多项式时间的算法解决RSA问题。 3.1.3选择明文安全的RSA加密 设GenRSA是RSA加密方案的密钥产生算法，它的输入为，输出为模数n（为2个比特素数的乘积）、整数e、d满足ed≡1 mod φ(n)。又设H:0,12→0,1()是一个哈希函数，其中()是一个任意的多项式。 加密方案Π（称为RSACPA方案）如下: (1) 密钥产生过程: KeyGen(): n,e,d←GenRSA(); pk=(n,e),sk=n,d. (2) 加密过程（其中M∈0,1()）: pk(M): r←RZ*n; 输出re mod n,H(r)M. (3) 解密过程: skC1,C2: r=Cd1 mod n; 输出H(r)C2. 解密过程的正确性显然。 在对方案进行安全性分析时，将其中的哈希函数视为随机谕言机。随机谕言机（random oracle）是一个魔盒，对用户（包括敌手）来说，魔盒内部的工作原理及状态都是未知的。用户能够与这个魔盒交互，方式是向魔盒输入一个比特串x，魔盒输出比特串y（对用户来说y是均匀分布的）。
这一过程称为用户向随机谕言机的询问。 因为这种哈希函数工作原理及内部状态是未知的，因此不能用通常的公开哈希函数。在安全性的归约证明中（见图17），敌手需要哈希函数值时，只能由敌手为他产生。之所以以这种方式使用哈希函数，是因为要把欲攻击的困难问题嵌入到哈希函数值中。这种安全性称为随机谕言机模型下的。如果不把哈希函数当作随机谕言机，则安全性称为标准模型下的，如3.2节的Paillier公钥密码系统和3.3节的CramerShoup密码系统。 定理31设H是一个随机谕言机，如果与GenRSA相关的RSA问题是困难的，则RSACPA方案Π是INDCPA安全的。 具体来说，假设存在一个INDCPA敌手以()的优势攻破RSACPA方案Π，那么一定存在一个敌手至少以 AdvRSA()≥2() 的优势解决RSA问题。 证明: Π的INDCPA游戏如下。 ExpRSACPAΠ,() n,e,d←GenRSA(); pk=(n,e),sk=n,d; H←RH:0,12→0,1(); M0,M1←sk(·),H(·)(pk)，其中M0=M1=(); β←R0,1,r←RZ*n,C=re mod n,H(r)Mβ; β′←sk,≠C(·),H(·)(pk,C); 如果β′=β，则返回1；否则返回0. 其中H:0,12→0,1()表示0,12到0,1()的哈希函数族,sk,≠C(·)表示敌手不能对C访问sk(·)。敌手的优势定义为安全参数的函数: AdvRSACPAΠ,()=PrExpRSACPAΠ,()=1－12 下面证明RSACPA方案可归约到RSA假设。 敌手已知(n,e,c^1)，以（攻击RSACPA方案）作为子程序，进行如下过程（图31），目标是计算r^≡(c^1)1/e mod n。 图31RSACPA方案到RSA的归约
（1） 选取一个随机串h^←R{0,1}()，作为对H(r^)的猜测值（但是实际上并不知道r^）。将公开钥(n,e)给。
（2） H询问: 建立一个表Hlist(初始为空)，元素类型xi,hi，在任何时候都能发出对Hlist的询问，做如下应答（设询问为x）: 如果x已经在Hlist，则以x,h中的h应答。 如果xe≡c^1 mod n，以h^应答，将(x,h^)存入表中，并记下r^=x。 否则随机选择h←R{0,1}()，以h应答，并将(x,h)存入表中。
（3） 挑战。输出两个要挑战的消息M0和M1，随机选择β←R{0,1}，并令c^2=h^Mβ，将c^1,c^2给作为密文。
（4） 在执行结束后（在输出其猜测β′之后），输出第（2）步记下的r^=x。 设表示事件: 在模拟中发出H(r^)询问，即H(r^)出现在Hlist中。 断言31在以上模拟过程中，的模拟是完备的。 证明： 在以上模拟中，的视图与其在真实攻击中的视图是同分布的。这是因为 (1) 的H询问中的每一个都是用随机值来回答的。而在对Π的真实攻击中，得到的是H的函数值，由于假定H是随机谕言机，所以得到的H的函数值是均匀的。 (2) 对来说，h^Mβ为h^对Mβ做一次一密加密。由h^的随机性，h^Mβ对来说是随机的。 所以两种视图不可区分。 （断言31证毕） 断言32在上述模拟攻击中Pr≥2。 证明: 显然有PrExpRSACPAΠ,()=1=12。又由在真实攻击中的定义知的优势大于等于，得在模拟攻击中的优势也为 Pr［ExpRSACPAΠ,()=1］－12≥ PrExpRSACPAΠ,()=1=PrExpRSACPAΠ,()=1|Pr +PrExpRSACPAΠ,()=1|Pr ≤PrExpRSACPAΠ,()=1|Pr+Pr =12Pr+Pr=12(1－Pr)+Pr =12+12Pr 又知: PrExpRSACPAΠ,()=1≥PrExpRSACPAΠ,()=1Pr =12(1－Pr) =12－12Pr 所以≤PrExpCPAΠ,()=1－12≤12Pr，即模拟攻击中Pr≥2。 （断言32证毕） 由以上两个断言，在上述模拟过程中r^以至少2的概率出现在Hlist。若发生，则在第（2）步可找到x满足xe=c^1 mod n，即x≡r^≡(c^1)1/e mod n。所以成功的概率与发生的概率相同。 （定理31证毕） 定理31已证明Π是INDCPA安全的，然而它不是INDCCA安全的。敌手已知密文CT=C1,C2，构造CT′=C1,C2M′，给解密谕言机，收到解密结果为M″=MM′，再由M″M′即获得CT对应的明文M。
3.1.4选择密文安全的RSA加密 因为选择密文安全的单钥加密方案的构造较容易，本节利用选择密文安全的单钥加密方案构造选择密文安全的公钥加密方案。 单钥加密方案Π=(PrivGen,Enc,Dec)的选择密文安全性由以下INDCCA游戏来刻画。 ExpPrivCCAΠ,()： kpriv←PrivGen(); M0,M1←Enckpriv(·),Deckpriv(·),其中M0=M1=(); β←R0,1,C=Enckpriv(Mβ); β′←Enckpriv(·),Deckpriv,≠C(·)(C); 如果β′=β，则返回1；否则返回0. 其中Deckpriv,≠C(·)表示敌手不能对C访问Deckpriv(·)。敌手的优势可定义为安全参数的函数: AdvPrivCCAΠ,()=PrExpPrivCCAΠ,()=1－12 单钥加密方案Π的安全性定义与定义22、定义26、定义27类似。 设GenRSA及H如前，Π=(PrivGen,Enc,Dec)是一个密钥长度为，消息长度为()的INDCCA安全的单钥加密方案。 选择密文安全的RSA加密方案Π′=(KeyGen,,)（称为RSACCA方案）构造如下。
(1) 密钥产生过程: KeyGen(): n,e,d←GenRSA(); pk=(n,e),sk=n,d.
(2) 加密过程（其中M∈0,1()）: pk(M): r←RZ*n; h=H(r); 输出re mod n,Ench(M).
(3) 解密过程: skC1,C2: r=Cd1 mod n; h=H(r); 输出Dech(C2). 定理32设H是随机谕言机，如果与GenRSA相关的RSA问题是困难的，且Π是INDCCA安全的，则RSACCA方案Π′是INDCCA安全的。 具体来说，假设存在一个INDCCA敌手以()的优势攻破RSACCA方案Π′，那么一定存在一个敌手至少以 AdvRSA()≥2() ……
新书资讯