可证安全密码学 PDF 文档
这是 Shafi Goldwasser 和 Mihir Bellare 在 MIT 的 1996-2002, 2004,2005 和 2008 夏季课程中一周的课程注记。密码学是一个很广的课题,这些注记的编辑线索是密码学中可证安全的概念建立和密码协议上的应用。
包括 Shafi Goldwasser 的 MIT 密码和密码分析学课程注记与 Mihir Bellare 在 UCSD 的密码和网络安全课程。另外,Rosario Gennaro(1996 年的课程助教)编辑了整本书的 9.6 节、11.4 节、11.5 节和附录D,还编辑了附录 E 的一些内容。第二、三、七章中的主要材料是从 MIT 的 Goldwasser 教授的研究生在学习密码和密码分析学课程同时所记录的笔记中整理的。
随后,1991 年课程助教 Frank D’Ippolito 进行了编辑。Frank 也对附录中的先进数字理论做了一些工作。第三章的部分内容节选自是 R.Rivest 的计算机科学理论手册。第四、五、六、八、九和十一及 10.5 和 7.4.6 节是出自 UCSD 的 Bellare 和 and Rogaway[23] 教授的现代密码学介绍,并且感谢 Phillip Rogaway 允许加入这部分内容。Rosario Gennaro 对这个教案的贡献在 10.6,12.4,12.5,附录 D,并且编辑了多出文章和附录 E 的难题。
目录
可证安全密码学.1
前 言 ..2
目录 ......3
第一章 现代密码学导论....12
1.1 加密:历史回顾...12
1.2 现代密码学:基于计算复杂度理论........13
1.3 部分单向函数简介........13
1.4 安全定义.14
1.5 攻击者模型......15
1.6 加密进程.15
第二章 单向函数和陷门体制.....16
2.1 单向函数:设计动机....16
2.2 单向函数:定义...17
2.2.1 强单向函数17
2.2.2 弱单项函数18
2.2.3 非正规的单向函数..18
2.2.4 单向函数集19
2.2.5 陷门函数和集.....19
2.3 搜索的例子......20
2.3.1 离散对数函数.....21
2.3.2 RSA 函数 ...23
2.3.3 因式分解难题和 RSA 求逆之间的联系 .....25
2.3.4 Rabin 体制下的平方单向陷门函数 ....26
2.3.5 一个平方置换与求解因数分解难题等同 ...29
2.4 单向函数的核心难度谓词.29
2.4.1 一般意义下的单向函数的核心判断..30
2.4.2 离散对数函数的 Bit 安全性31
2.4.3 RSA 的比特安全和平方函数 32
2.5 单向和陷门谓词...32
2.5.1 陷门集的例子.....33
第三章 伪随机比特产生器35
3.0.2 产生一个一次一密序列(对任意密钥) ...35
3.0.3 产生伪随机比特或数列...36
3.0.4 伪随机的可证安全:概论....36
3.1 定义....37
3.2 一个伪随机发生器的存在性......38
3.3 下一比特测试..40
3.4 伪随机数产生器的例子41
3.4.1 Blum/Blum/Shub 伪随机发生器...42
第四章 分组密码的运算模式.....43
4.1 什么是分组密码...4
4.2 数据加密标准、数据加密标准..43
4.2.1 历史简介....43
4.2.2 构造.......44
4.2.3 速度.......45
4.3 分组密码的密钥恢复攻击.45
4.4 迭代 DES 和 DESX.......45
4.4.1 Double DES ......46
4.4.2 3-DES..47
4.4.3 DESX .....47
4.4.4 为什么设计新密码48
4.5 高级加密标准..48
4.5.1 电子密本工作模式..48
4.5.2 密文链接工作模式..48
4.5.3 计数模式....49
4.6 基于安全的密钥恢复限制.49
4.7 练习和难题......50
第五章 伪随机函数.......51
5.1 函数簇51
5.2 随机函数和置换...51
5.3 随机函数.53
5.4 随机置换.55
5.4.1 在 CPA 下的 PRP ....56
5.4.2 CCA 条件下的 PRP .56
5.4.3 概念间的关系.....57
5.5 分组密码的一些模型....57
5.5.1 PRFs 和 PRPs 的簇的次序 ....57
5.5.2 PRFs 和 PRPs 的用途 .......58
5.5.3 共享随机函数模型..58
5.5.4 分组密码的模型建立.......59
5.6 攻击例子.59
5.7 抗密钥恢复攻击安全....61
5.8 生日攻击.65
5.9 PRFs 与 PRPs .66
5.10 PRF 簇的构造.66
5.10.1 扩展定义域大小....67
5.11 PRFs 的一些应用 ......68
5.11.1 密码的强单向函数68
5.11.2 判断.....68
5.11.3 学习机制..68
5.11.4 朋友或敌人身份识别 .....68
5.11.5 私钥加密..69
5.12 历史注记........69
5.13 联系和问题....69
第六章 私钥加密..7
6.1 对称加密体制..70
6.2 一些加密体制..71
6.3 私密性分析......73
6.3.1 安全性分析...73
6.3.2 信息论安全...74
6.4 选择明文攻击的分辨机77
6.4.1 定义.......77
6.4.2 优势解释的选择.79
6.5 选择明文攻击的例子....80
6.5.1 ECB 攻击....80
6.5.2 稳定、固定的机制是不安全的.....81
6.6 抗明文恢复攻击的安全性.82
6.7 抗明文攻击的 CTR 安全 ...84
6.7.1 定理 6.17 的证明85
6.7.2 定理 6.18 的证明89
6.8 抗选择明文攻击的 CBC 安全....92
6.9 对选择密文攻击的不可分辨机制...92
6.10 选择密文攻击例子......93
6.10.1 CTR 攻击........94
6.10.2 对 CBC 的攻击.95
6.11 对称加密的其它方法..96
6.11.1 伪随机函数的普通加密算法 .......96
6.11.2 随机比特产生器的加密 .97
6.11.3 使用单向函数加密97
6.12 安全注记........97
6.13 练习和困难....98
第七章 公钥加密100
7.1 公钥加密的定义.100
7.2 PKC 体制的简单例子:陷门函数模型 ..101
7.2.1 陷门函数模型的难度.....101
7.2.2 使用确定加密的普通困难..102
7.2.3 RSA 加密体制102
7.2.4 Rabin 公钥体制 .104
7.2.5 背包体制..104
7.3 安全定义........105
7.3.1 安全定义:多项式不可分辨性...105
7.3.2 另一个定义:语义加密.106
7.4 公钥加密的概率.106
7.4.1 加密单比特:陷门判断.106
7.4.2 加密单比特:内核判断.107
7.4.3 普通概率加密算法108
7.4.4 有效概率加密...109
7.4.5 一个 EPE 的运行与 RSA 的消耗是相同的 ...110
7.4.6 基于加密的实践 RSA:OAEP.... 11
7.4.7 进一步讨论.......112
7.5 探测活动的攻击者......112
第八章 HASH 函数....114
8.1 HASH 函数 SHA1.....114
8.2 抗碰撞 HASH 函数.....115
8.3 碰撞发现攻击117
8.4 抗碰撞的单向 HASH 函数........119
8.5 MD 变换 121
8.6 在隐密钥条件下的抗碰撞攻击124
8.7 难题..124
第九章 消息认证125
9.1 简介..125
9.1.1 难题.....125
9.1.2 加密并不提供数据完整性..125
9.2 消息认证体制127
9.3 安全的体制....128
9.3.1 关于安全的几点....128
9.3.2 一个安全的概念....129
9.3.4 使用定义:一些例子.....130
9.4 XOR 体制 .......132
9.4.1 体制.....132
9.4.2 安全考虑..133
9.5 例子........134
XOR 体制的安全结果 ....134
9.6 随机函数构造好的 MACs ........134
9.7 CBC MAC......136
9.7.1 CBC MAC 的安全..136
9.7.2 对 CBC MAC 的生日攻击.136
9.7.3 长度可变性.......138
9.8 基于 MAC 的普通的 HASH.....138
9.8.1 几乎普通的 HASH 函数139
9.8.2 使用 UH 函数进行 MAC 运算 ....141
9.8.3 使用 XUH 函数构造 MAC .141
9.9 用密码 hash 函数的 Macing ....143
9.9.1 HMAC 构造.....143
9.9.2 HMAC 的安全...144
9.9.3 抗已知攻击.......145
9.10 MACs 的最小假设 .....145
9.11 问题和练习..145
第十章 数字签名147
10.1 数字签名的成分........147
10.2 数字签名:陷门函数模型......147
10.3 为安全签名体制定义和证明安全........148
10.3.1 数字签名的攻击方法...14
10.3.2 RSA 数字签名体制 .......149
10.3.3 El Gamal 体制149
10.3.4 Rabin 体制 ......150
10.4 概率签名......151
10.4.1 陷门置换的无缺陷.......151
10.4.2 例子:如果是因子分解难题,无缺陷置换存在 .152
10.4.3 怎样签属一比特..152
10.4.4 怎样签属一个消息.......153
10.4.5 基于无缺陷的安全签名体制.....154
10.4.6 基于陷门置换的一个安全签名体制.......157
10.5 具体安全和基于签名的 RSA 体制 ......158
10.5.1 数字签名体制.159
10.5.2 安全的一个概念..160
10.5.3 RSA 体制的密钥产生机 ....160
10.5.4 单向签名161
10.5.5 陷门签名162
10.5.6 HASH 然后求逆范式....163
10.5.7 PKCS ≠ 1 体制.164
10.5.8 FDH 体制165
10.5.9 PSS0:一个安全的提高 ....170
10.5.10 概率签名体制-PSS.....173
10.5.11 使用消息恢复 PSS-R 签名 ......174
10.5.12 怎样完成单向函数.....176
10.5.13 与其他体制的比较.....176
10.6 极限签名体制...176
10.6.1 极限密码体制的密钥产生177
10.6.2 签名协议177
第十一章 密钥分发.....178
11.1 Diffie Hellman 秘密密钥交换.178
11.1.1 协议...178
11.1.2 抗窃听安全:DH 难题 178
11.1.3 DH 加密体制 ...179
11.1.4 DH 密钥的比特安全 .....179
11.1.5 认证缺乏180
11.2 会话密钥分发...180
11.2.1 可信模型和密钥分发难题 180
11.2.2 会话密钥分布历史.......181
11.2.3 对于难题不正式的描述 ....182
11.2.4 推导安全182
11.2.5 对密钥分布的完整性确认 183
11.3 认证密钥交换...183
11.3.1 对称条件183
11.3.2 非对称条件.....184
11.4 三方会话密钥分发....185
11.5 前向保密......186
第十二章 协议..187
12.1 一些两方协议...187
12.1.1 健忘传输187
12.1.2 同时定约签名.187
12.1.3 比特承诺188
12.1.4 在一个好的条件下的随机事件.189
12.1.5 健忘电路赋值.189
12.1.6 同步秘密交换协议.......189
12.2 零知识协议..190
12.2.1 交互证明系统(IP) ...190
12.2.2 例子...191
12.2.3 零知识....192
12.2.4 定义...192
12.2.5 如果有单向函数,NP 在 KC[0]中.193
12.2.6 用户认证应用.193
12.3 多方协议......193
12.3.1 秘密共享194
12.3.2 可验证秘密共享..194
12.3.3 匿名处理195
12.3.4 多方 Ping-Pong 协议....195
12.3.5 基于多数方诚实的多方协议.....195
12.4 电子选举......195
12.4.1 Merritt 选举协议 .196
12.4.2 一个容错选举协议.......196
12.4.3 协议...197
12.4.4 非强制条件.....199
12.5 数字现金......199
12.5.1 数字现金要求的特征...200
12.5.2 第一次尝试协议..200
12.5.3 盲签名....200
12.5.4 RSA 盲签名.....201
12.5.5 固定美元数量.201
12.5.6 在线数字签名.201
12.5.7 离线数字现金.202
Bibliography ...203
附录 A:一些概率事实....213
A.1 生日难题.......213
附录 B:一些复杂性理论背景 .215
B.1 复杂度分类和标准定义 215
B.1.1 复杂度分类 P.215
B.1.2 复杂度分类 NP 215
B.1.3 复杂簇 BPP......215
B.2 概率算法.......216
B.2.1 对于概率图灵机的概念 216
B.2.2 概率算法的不同类型 ....216
B.2.3 非统一多项式时间 ........217
B.3 攻击者..217
B.3.1 假定存在 .217
B.4 从概率论得到的一些不等式 ...217
附录 C: 一些数论背景 ..218
C.1 群,基础.......218
C.2 算数:+,*,GCD ....218
C.3 模运算组.......219
C.3.1 简单运算 .219
C.3.2 主群 Zn 和 Zn* 。 219
C.3.3 求幂 ....220
C.4 中国剩余.......220
C.5 素元和 Zp* .....222
C.5.1 定义 ....222
C.5.2 群 Zp* ..222
C.5.3 查询生成元 ......223
C.6 二次剩余.......223
C.7 贾可比符号 ...224
C.8 RSA ..224
C.9 素性测试.......225
C.9.1 素性∈NP 难题225
C.9.2 Pratt’s 的素性测试225
C.9.3 概率素性测试 ..226
C.9.4 Solovay-Strassen 素性测试 .226
C.9.5 Miller-Rabin 素性测试 ..227
C.9.6 素性的多项式时间证明 228
C.9.7 对于一些素数工作的算法 .228
C.9.8 Goldwasser-Kilian 素性测试.......229
C.9.9 Goldwasser-Kilian 算法的正确性 229
C.9.10 Goldwasser-Kilian 的预期运算时间 ........230
C.9.11 几乎所有素数的期望运算时间 230
C.10 因子分解算法 ..231
C.11 椭园曲线 .....231
C.11.1 在 Zn 上的椭园曲线.....232
C.11.2 使用椭园曲线的因子分解 ........233
C.11.3 Lenstra 算法的正确性 ..234
C.11.4 运算时间分析 234
附录 D:关于 PGP ......236
D.1 认证.236
D.2 私密性..236
D.3 密钥大小.......236
D.4 E-mail 兼容性.236
D.5 一次 IDEA 密钥产生 .237
D.6 公钥管理.......237
附录 E : 问题 .238
E.1 秘密密钥加密 ....238
E.1.1 DES......238
E.1.2 在 DES 密文条件下的错误检测.238
E.1.3 对 CBC 模式的强力破解 ...238
E.1.4 E-mail ..238
E.2 口令字 ..239
E.3 数论 .239
E.3.1 数论定理 .239
E.3.2 难题之间的关系 ...240
E.3.3 概率素性测试 ..240
E.4 公钥加密 .......240
E.4.1 简单的 RSA 问题..240
E.4.2 另一些简单的 RSA 问题....240
E.4.3 导致 RSA 协议失败.......240
E4.4 RSA 的猜想 .......241
E.4.5 Diffie-Hellman 的难题...241
E.4.6 比特承诺 .241
E.4.7 完善前向保密 ..242
E.4.8 已知明文和非延展性 ....242
E.4.9 概率加密 .242
E.5 秘密加密体制 ....242
E.5.1 同步加密和认证 ...242
E.6 单向函数 .......243
E.6.1 生日攻击 .243
E.6.2 从 DES 构造单向函数...243
E.6.3 从 RSA 构造单向函数...243
E.7 伪随机 ..244
E.7.1 扩展 PRGs........244
E.7.2 从 PRG 到 PRF 244
E.8 数字签名 .......244
E.8.1 伪造表 244
E.8.2 ElGamal ....244
E.8.3 建议签名体制 ..245
E.8.4 Ong-Schnorr-Shamir........245
E.9 协议 .245
E.9.1 无条件的安全秘密共享 245
E.9.2 欺骗者的秘密共享 ........245
E.9.3 对离散对数的零知识证明 .246
E.9.4 健忘传输协议 ..246
E.9.5 电子货币 .246
E.9.6 撤消协议的原子签名 ....247
E.9.7 使用 Elgamal/DSS 进行盲签.......247
下载地址:https://www.wenjiangs.com/wp-content/uploads/2023/01/20096119382964479.zip
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论