密码学中的可证明安全性

本书由*高等学校信息安全专业教学指导委员会、中国计算机学会教育专业委员会共同指导，符合《高等学校信息安全专业指导性专业规范》。本书全面介绍可证明安全性的发展历史及研究成果。全书共5章，第1章介绍可证明安全性涉及的数学知识和基本工具，第2章介绍语义安全的公钥密码体制的定义，第3章介绍几类常用的语义安全的公钥机密体制，第4章介绍基于身份的密码体制，第5章介绍基于属性的密码体制。    本书取材新颖，不仅包括可证明安全性的基础理论和实用算法，同时也涵盖了可证明安全性的密码学的*研究成果，力求使读者通过本书的学习了解本学科*的发展方向。    本书特别适合作为高等院校信息安全、计算机工程和信息对抗等专业的本科生和网络空间安全学科研究生教材，也可作为通信工程师和计算机网络工程师的参考读物。 

本书全面介绍可证明安全性的发展历史及研究成果。全书共5章，第1章介绍可证明安全性涉及的数学知识和基本工具，第2章介绍语义安全的公钥密码体制的定义，第3章介绍几类常用的语义安全的公钥机密体制，第4章介绍基于身份的密码体制，第5章介绍基于属性的密码体制。
本书取材新颖，结构合理，不仅包括可证明安全性的基础理论和实用算法，同时也涵盖了可证明安全性的密码学的*研究成果，力求使读者通过本书的学习了解本学科*的发展方向。
本书适合作为高等院校信息安全、网络空间安全、计算机工程、密码学和信息对抗等相关专业的本科生高年级和研究生教材，也可作为通信工程师和计算机网络工程师的参考读物。

杨波，北京大学学士，西安电子科技大学硕士、博士，陕西师范大学计算机科学学院教授、博士生导师，陕西省百人计划特聘教授，中国密码学会理事，中国密码学会密码算法专业委员会委员，《密码学报》编委。曾任华南农业大学信息学院、软件学院院长。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.3CramerShoup密码系统76

3.3.1CramerShoup密码系统的基本机制76

3.3.2CramerShoup密码系统的安全性证明77

3.4RSAFDH签名方案79

3.4.1RSA签名方案79

3.4.2RSAFDH签名方案的描述80

3.4.3RSAFDH签名方案的改进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双线性DiffieHellman求逆假设128

4.3.2基于判定性BDH假设的IBE和HIBE方案129

4.3.3基于判定性BDHI假设的IBE和HIBE方案131

4.4无随机谕言机模型下的基于身份的密码体制134

4.4.1判定性双线性DiffieHellman假设134

4.4.2无随机谕言机模型下的IBE构造134

4.5密文长度固定的分层次IBE143

4.5.1弱双线性DiffieHellman求逆假设143

4.5.2一个密文长度固定的HIBE系统144

4.5.3具有短秘密钥的HIBE系统147

4.6基于对偶系统加密的完全安全的IBE和HIBE152

4.6.1对偶系统加密的概念152

4.6.2合数阶双线性群154

4.6.3基于对偶系统加密的IBE方案155

4.6.4基于对偶系统加密的HIBE方案160

4.7从选择明文安全到选择密文安全164

4.7.1选择明文安全到选择密文安全的方法介绍164

4.7.2CHK方法164

4.7.3CCA安全的二叉树加密167

第4章参考文献170

 

第5章基于属性的密码体制172

5.1基于属性的密码体制的一般概念172

5.2基于模糊身份的加密方案175

5.2.1Fuzzy IBE的安全模型及困难性假设175

5.2.2基于模糊身份的加密方案176

5.2.3大属性集上的基于模糊身份的加密方案179

5.3一种基于密钥策略的属性加密方案181

5.3.1访问树结构181

5.3.2KPABE方案构造183

5.3.3大属性集的KP|ABE方案构造186

5.3.4秘密钥的委托189

5.3.5KP|ABE的应用191

5.4一种基于密文策略的属性加密方案191

5.4.1判定性并行双线性Diffie|Hellman指数假设192

5.4.2基于密文策略的属性加密方案构造192

5.5基于对偶系统加密的完全安全的属性加密195

5.6非单调访问结构的ABE200

5.6.1从单调访问结构到非单调访问结构201

5.6.2非单调访问结构ABE的实现方案201

5.7函数加密205

5.7.1函数加密简介205

5.7.2函数加密的定义206

5.7.3函数加密的分类207

5.7.4基于游戏的安全性定义209

5.7.5基于模拟的安全性定义210

第5章参考文献215

21世纪是信息时代，信息已成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它会直接关系到国家安全、企业经营和人们的日常生活。 随着信息安全产业的快速发展，全球对信息安全人才的需求量不断增加，但我国目前信息安全人才极度匮乏，远远不能满足金融、商业、公安、军事和政府等部门的需求。要解决供需矛盾，必须加快信息安全人才的培养，以满足社会对信息安全人才的需求。为此，继2001年批准在武汉大学开设信息安全本科专业之后，又批准了多所高等院校设立信息安全本科专业，而且许多高校和科研院所已设立了信息安全方向的具有硕士和博士学位授予权的学科点。信息安全是计算机、通信、物理、数学等领域的交叉学科，对于这一新兴学科的培养模式和课程设置，各高校普遍缺乏经验，因此中国计算机学会教育专业委员会和清华大学出版社联合主办了“信息安全专业教育教学研讨会”等一系列研讨活动，并成立了“高等院校信息安全专业系列教材”编审委员会，由我国信息安全领域著名专家肖国镇教授担任编委会主任，指导“高等院校信息安全专业系列教材”的编写工作。编委会本着研究先行的指导原则，认真研讨国内外高等院校信息安全专业的教学体系和课程设置，进行了大量前瞻性的研究工作，而且这种研究工作将随着我国信息安全专业的发展不断深入。系列教材的作者都是既在本专业领域有深厚的学术造诣、又在教学线有丰富的教学经验的学者、专家。该系列教材是我国套专门针对信息安全专业的教材，其特点是：① 体系完整、结构合理、内容先进。② 适应面广：能够满足信息安全、计算机、通信工程等相关专业对信息安全领域课程的教材要求。③ 立体配套：除主教材外，还配有多媒体电子教案、习题与实验指导等。④ 版本更新及时，紧跟科学技术的新发展。在全力做好本版教材，满足学生用书的基础上，还经由专家的和审定，遴选了一批国外信息安全领域优秀的教材加入到系列教材中，以进一步满足大家对外版书的需求。“高等院校信息安全专业系列教材”已于2006年年初正式列入普通高等教育“十一五”教材规划。2007年6月，高等学校信息安全类专业教学指导委员会成立大会暨次会议在北京胜利召开。本次会议由高等学校信息安全类专业教学指导委员会主任单位北京工业大学和北京电子科技学院主办，清华大学出版社协办。高等学校信息安全类专业教学指导委员会的成立对我国信息安全专业的发展起到重要的指导和推动作用。2006年给武汉大学下达了“信息安全专业指导性专业规范研制”的教学科研项目。2007年起该项目由高等学校信息安全类专业教学指导委员会组织实施。在高教司和教指委的指导下，项目组团结一致，努力工作，克服困难，历时5年，制定出我国个信息安全专业指导性专业规范，于2012年年底通过经高等教育司理工科教育处授权组织的专家组评审，并且已经得到武汉大学等许多高校的实际使用。2013年，新一届“高等学校信息安全专业教学指导委员会”成立。经组织审查和研究决定，2014年以“高等学校信息安全专业教学指导委员会”的名义正式发布《高等学校信息安全专业指导性专业规范》（由清华大学出版社正式出版）。密码学中的可证明安全性出版说明2015年6月，国务院学位委员会、出台增设“网络空间安全”为一级学科的决定，将高校培养网络空间安全人才提到新的高度。2016年6月，中央网络安全和信息化领导小组办公室（下文简称中央网信办）、国家发展和改革委员会、、科学技术部、工业和信息化部及人力资源和社会保障部六大部门联合发布《关于加强网络安全学科建设和人才培养的意见》（中网办发文[2016]4号）。为贯彻落实《关于加强网络安全学科建设和人才培养的意见》，进一步深化高等教育教学改革，促进网络安全学科专业建设和人才培养，促进网络空间安全相关核心课程和教材建设，在高等学校信息安全专业教学指导委员会和中央网信办资助的网络空间安全教材建设课题组的指导下，启动了“网络空间安全重点规划丛书”的工作，由高等学校信息安全专业教学指导委员会秘书长封化民校长担任编委会主任。本规划丛书基于“高等院校信息安全专业系列教材”坚实的工作基础和成果、阵容强大的编审委员会和优秀的作者队伍，目前已经有多本图书获得和中央网信办等机构评选的“普通高等教育本科规划教材”“普通高等教育精品教材”“中国大学出版社图书奖”和“国家网络安全优秀教材奖”等多个奖项。“网络空间安全重点规划丛书”将根据《高等学校信息安全专业指导性专业规范》（及后续版本）和相关教材建设课题组的研究成果不断更新和扩展，进一步体现科学性、系统性和新颖性，及时反映教学改革和课程建设的新成果，并随着我国网络空间安全学科的发展不断完善，力争为我国网络空间安全相关学科专业的本科和研究生教材建设、学术出版与人才培养做出更大的贡献。我们的Email地址是： [email protected]，联系人： 张民。
“网络空间安全重点规划丛书”编审委员会信息安全是一个综合、交叉的学科领域，涉及数学、电子、信息、通信、计算机等诸多学科的长期知识积累和发展成果，密码学是信息安全的核心技术，密码技术中的加密方法包括单钥密码体制和公钥密码体制。刻画公钥密码体制的安全性包括两部分: 首先是刻画敌手的模型，说明敌手访问系统的方式和计算能力；其次是刻画安全性概念，说明敌手攻破了方案的安全性意味着什么。公钥加密方案语义安全的概念由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月

评论

第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