没有合适的资源?快使用搜索试试~ 我知道了~
首页应用密码学研究生课程A Graduate Course in Applied Cryptography
应用密码学研究生课程A Graduate Course in Applied Cryptography
需积分: 48 21 下载量 117 浏览量
更新于2023-03-03
评论 1
收藏 16.86MB PDF 举报
本书涵盖了用于密码学中不同任务的实用密码系统的许多构造。 它还提供了许多案例研究来调查已部署系统的运行方式。
资源详情
资源评论
资源推荐
AGraduateCourseinAppliedCryptography
Dan Boneh Victor Shoup
August 17, 2015
Preface
Cryptography is an in di spensable tool used to protect information in computing systems. It is
used everywhere and by billions of people worldwide on a daily basis. It is used to protect data at
rest and data in motion. Cryptographic systems are an integral part of standard prot ocols, most
notably the Transport Layer Security (TLS) protocol, making it relatively easy to incorporate
strong encryption into a wide range of app l ic at i ons .
While extremely u sef u l, cryptography is also highly bri t t l e. The most secure cryptographic
system can be rendered completely insecure by a single specification or programmi ng error. No
amount of unit testing will uncover a secu r i ty vulnerability in a cryptosystem.
Instead, to argue t h at a cry pt osy s t em is sec ur e, we rel y on mat he mat i cal modeling and proofs
to show that a particular system sat i sfi es the security properties attribut e d to it. We often need to
introduce certain plausible assumptions to push our security arguments through.
This b ook is about exactly that: constructing practical cryptosystems for which we can argue
security under plausible assumptions . The book covers many constructions for di↵erent tasks in
cryptography. For each task we define a precise security goal that we aim to achieve and then
present constructions that achieve the required goal. To analyze the constructions, we develop a
unified framework for d oi ng cryptographic proofs. A reader who masters this framework will be
capable of applying it to new constructions that may not be covered in the book.
Throughout the book we present many case st ud i es to survey how deployed systems operate.
We describe common mistakes to avoid as well as attacks on real-world systems that illustrate the
importance of rigor in cryptography. We end every chapter with a fun application that applies the
ideas in the chapter in some unexpect e d way.
Intended audience and how to use this book
The book is intended to be self contained. Some supplementary material covering basic facts from
probability theory and algebra is provided in the appendices.
The book is divided into th re e part s. The first part develops symmetric encryption which
explains how two parties, Alic e and Bob, can securely ex change information when they have a
shared key unknown to the attacker. The second part develops the concepts of public-key encry pti on
and digital signatures, which allows Alice and Bob to do the same, but without having a shared,
secret key. The third part is about cryptographic protocols, such as protocols for user identification,
key exchange, and secur e computation.
A beginnin g reader can read though the book to learn how cry pt ogr aph i c systems work and
why they are secure. Every security theor em in the book is followed by a pro of idea that explains
at a high level why the scheme is secure. On a first read one can skip over the detailed proofs
2
without losing continuity. A beginning reader may also skip over the mathematical details sections
that explore nuances of certain definitions .
An advanced reader may enjoy reading the detailed proofs t o learn how to do p r oofs in cryptog-
raphy. At t he end of every chap t er you will find many exercises that explore additional aspects of
the material covered in the chapter. Some exercises rehearse what was learned, but many exercises
expand on the material and discuss topics not covered in the chapter.
Status of the book
The current draft only contains part I. Parts II and III are forthcoming. We hope you enjoy this
write-up. Please send us comments and let us know if you find typos or mistakes.
Citations: While the current draft is mostly complete, we still do not include citations and
references to the many works on which this book is based. Those will be coming soon and will be
presented in the Notes section at the end of every chapter.
Dan Boneh and Victor Shoup
August, 2015
3
Contents
1 Introduction 15
1.1 Historic ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Termi nol ogy used throughout the book . . . . . . . . . . . . . . . . . . . . . . . . . . 15
I Secret key cryptography 17
2 Encryption 18
2.1 Introduct i on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Shannon ciphers and perfect security . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Definition of a Shannon cipher . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Perfect security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3 The bad news . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Computati onal ciphers and semantic secu r i ty . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Definition of a computational cipher . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Definition of semantic security . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.3 Connections to weaker notions of security . . . . . . . . . . . . . . . . . . . . 32
2.3.4 Consequences of semantic security . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.5 Bit guessing: an alternative characteri zat i on of semantic security . . . . . . . 39
2.4 Mathemati c al details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.1 Negligible, super-poly, an d poly-bounded functions . . . . . . . . . . . . . . . 42
2.4.2 Computational ciphers: t he formalities . . . . . . . . . . . . . . . . . . . . . . 43
2.4.3 Efficient adversaries and attack games . . . . . . . . . . . . . . . . . . . . . . 46
2.4.4 Semantic security: the formalities . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.5 A fun application: anonymous routing . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.7 Exercis es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Stream ciphers 58
3.1 Pseudo-ran dom generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.1.1 Definition of a pseudo-random generator . . . . . . . . . . . . . . . . . . . . . 59
3.1.2 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Stream ciphers: encryption with a PRG . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3 Stream cipher limitations: attacks on the one t i me pad . . . . . . . . . . . . . . . . . 65
3.3.1 The two-time pad is insecure . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4
3.3.2 The one-time pad is malleable . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4 Composing PRGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.1 A parallel construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.2 A sequential construction: the Blum-Micali method . . . . . . . . . . . . . . 72
3.4.3 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5 The next bit test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6 Case study: the Salsa and ChaCha PRGs . . . . . . . . . . . . . . . . . . . . . . . . 80
3.7 Case study: linear generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.7.1 An example cryptanalysi s : linear congruential generators . . . . . . . . . . . 83
3.7.2 The subset sum generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.8 Case study: cryptanalysis of the DVD encryption system . . . . . . . . . . . . . . . 87
3.9 Case study: cryptanalysis of the RC4 stream cipher . . . . . . . . . . . . . . . . . . 89
3.9.1 Security of RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.10 Generating random bits in practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.11 A broader perspective: c omp ut at i onal indistinguishability . . . . . . . . . . . . . . . 94
3.11.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.12 A fun application: coin flipping and commitments . . . . . . . . . . . . . . . . . . . 99
3.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4Blockciphers 107
4.1 Block ciphers: basic definitions and properties . . . . . . . . . . . . . . . . . . . . . . 107
4.1.1 Some implications of security . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.1.2 Efficient implementation of random permutations . . . . . . . . . . . . . . . . 112
4.1.3 Strongly secure block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.1.4 Using a block c i ph er directly for encryption . . . . . . . . . . . . . . . . . . . 113
4.1.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2 Construct i n g block ciphers in practice . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2.1 Case study: DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.2.2 Exhaustive search on DES : the DES challenges . . . . . . . . . . . . . . . . . 124
4.2.3 Strengthening ciphers against exhaustive search: the 3E construction . . . . . 126
4.2.4 Case study: AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.3 Sophisti c at ed attack s on block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.3.1 Algorithmic attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.3.2 Side-channel attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.3.3 Fault-injection attacks on AES . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.3.4 Quantum exhaustive search at t acks . . . . . . . . . . . . . . . . . . . . . . . . 142
4.4 Pseudo-ran dom functions: basic definitions and properties . . . . . . . . . . . . . . . 143
4.4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.4.2 Efficient implementation of random functions . . . . . . . . . . . . . . . . . . 144
4.4.3 When is a s ecu r e block cipher a secure PRF? . . . . . . . . . . . . . . . . . . 145
4.4.4 Constructing PRGs from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.4.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.5 Construct i n g block ciphers from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.6 The tree construction: from PRGs to PRFs . . . . . . . . . . . . . . . . . . . . . . . 158
4.6.1 Variable length tre e construction . . . . . . . . . . . . . . . . . . . . . . . . . 162
5
剩余399页未读,继续阅读
weixin_38744153
- 粉丝: 346
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 数据结构1800题含完整答案详解.doc
- 医疗企业薪酬系统设计与管理方案.pptx
- 界面与表面技术界面理论与表面技术要点PPT学习教案.pptx
- Java集合排序及java集合类详解(Collection、List、Map、Set)讲解.pdf
- 网页浏览器的开发 (2).pdf
- 路由器原理与设计讲稿6-交换网络.pptx
- 火电厂锅炉过热汽温控制系统设计.doc
- 企业识别CIS系统手册[收集].pdf
- 物业管理基础知识.pptx
- 第4章财务预测.pptx
- 《集成电路工艺设计及器件特性分析》——实验教学计算机仿真系.pptx
- 局域网内共享文件提示没有访问权限的问题借鉴.pdf
- 第5章网络营销策略.pptx
- 固井质量测井原理PPT教案.pptx
- 毕业实习总结6篇.doc
- UGNX建模基础篇草图模块PPT学习教案.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0