AGraduateCourseinAppliedCryptographyv0.3_基于游戏的证明

需积分: 13 118 浏览量更新于2023-05-29 评论收藏 5.11MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

A Graduate Course in Applied Cryptography

Dan Boneh and Victor Shoup

Version 0.3, December 2016

Preface

Cryptography is an indispensable to ol 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 protocols, most

notably the Transport Layer Security (TLS) protocol, making it relatively easy to incorporate

strong encryption into a wid e ran ge of applicati on s.

While extremely useful, cryptography is also highly brittle. The most secure cryptographic

system can be rendered completely insecure by a sin gl e speciﬁ cat ion or programmi ng error. No

amount of uni t test i ng will un cover a security vulnerability in a cryptosystem.

Instead, to argue that a cryptosystem is secure, we rely on mathematical modeling and proofs

to show that a particular system satisﬁes the security properties attributed to it. We often need to

introduce certain plausible assumptions to push our security arguments through.

This book is about exactly that: constructing practical cryptosystems for which we can argue

security under plausible assumptions. The book covers many const r uct i ons for di↵erent tasks in

cryptography. For each task we deﬁne a precise security goal that we aim to achieve and then

present constructions that achieve t h e required goal. To analyze the constructions, we develop a

uniﬁed framework for doi n g cryptographic proofs. A r ead er 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 studies 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 cr y p togr ap hy. We end every chapter with a fun application that appli es the

ideas in the chapter in some unex pected 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 three parts. The ﬁrst par t develops symmetric encryption which

explains how two parties, Alice and Bob, can securely exchange information when they have a

shared key unknown to the attacker. The second part develops the concepts of public-key encryption

and digital signatures, whi ch allow 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 identiﬁcation,

key ex change, and secure computation.

A beginning reader can read though the book to learn how cryptographic systems work and

why they are secure. Every security theorem in the book is followed by a proof id ea that ex p l ain s

at a high level why t he scheme is secure. On a ﬁrst read one can skip over the detailed proofs

Contents

1 Introduction 1

1.1 Historic cipher s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Terminology used through out t h e book . . . . . . . . . . . . . . . . . . . . . . . . . . 1

I Secret key cryptography 3

2 Encryption 4

2.1 Introduct ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Shannon ciphers and perf ect securi ty . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2.1 Deﬁnition of a Shannon cipher . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2.2 Perfect security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2.3 The bad n ews . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3 Computation al cipher s and semantic security . . . . . . . . . . . . . . . . . . . . . . 13

2.3.1 Deﬁnition of a computational cipher . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.2 Deﬁnition of semantic security . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3.3 Connections to weaker n ot i ons of security . . . . . . . . . . . . . . . . . . . . 18

2.3.4 Consequences of semantic security . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3.5 Bit guessing: an alternative characterization of semantic security . . . . . . . 25

2.4 Mathematical de tai l s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4.1 Negligible, super-poly, and poly-bounded functions . . . . . . . . . . . . . . . 28

2.4.2 Computational ciphers: the formalities . . . . . . . . . . . . . . . . . . . . . . 29

2.4.3 Eﬃcient adversaries and attack games . . . . . . . . . . . . . . . . . . . . . . 32

2.4.4 Semantic security: the formalities . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.5 A fun application: anonymous routing . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3 Stream ciphers 45

3.1 Pseudo-random generator s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.1.1 Deﬁnition of a pseudo-random generator . . . . . . . . . . . . . . . . . . . . . 46

3.1.2 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.2 Stream ciphers : encryption with a PRG . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.3 Stream cipher limi t at i ons: attacks on the one time pad . . . . . . . . . . . . . . . . . 52

3.3.1 The two-time p ad is insecure . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.3.2 The one-time pad is malleable . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.4 Composing PRGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.4.1 A p ar all el constr u ct ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.4.2 A seq u ential constructi on : the Blum-Micali method . . . . . . . . . . . . . . 59

3.4.3 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.5 The next bit test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.6 Case study: the Salsa and ChaCha PRGs . . . . . . . . . . . . . . . . . . . . . . . . 68

3.7 Case study: linear generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.7.1 An example cryptanalysis: linear congruential generators . . . . . . . . . . . 70

3.7.2 The subset sum generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

3.8 Case study: cryptanalysis of the DVD encryption system . . . . . . . . . . . . . . . 74

3.9 Case study: cryptanalysis of the RC4 stream cipher . . . . . . . . . . . . . . . . . . 76

3.9.1 Security of RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.10 Generating random bits in practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.11 A broader perspective: computational indistinguishability . . . . . . . . . . . . . . . 81

3.11.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.12 A fun application: coin ﬂipping and commitments . . . . . . . . . . . . . . . . . . . 87

3.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

3.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

4Blockciphers 94

4.1 Block ciphers: basi c deﬁni t i ons and pr opert i es . . . . . . . . . . . . . . . . . . . . . . 94

4.1.1 Some implications of security . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

4.1.2 Eﬃcient implementation of random permutations . . . . . . . . . . . . . . . . 99

4.1.3 Strongly secure block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.1.4 Using a bl ock cipher directl y for encrypt i on . . . . . . . . . . . . . . . . . . . 100

4.1.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4.2 Constructi ng block ciphers in practice . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.2.1 Case study: DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.2.2 Exhaustive search on DE S: the DES challenges . . . . . . . . . . . . . . . . . 110

4.2.3 Strengthening ciphers against exhaustive search: the 3E construct i on . . . . . 112

4.2.4 Case study: AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

4.3 Sophisti cat ed attacks on block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 119

4.3.1 Algorithmic attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

4.3.2 Side-channel attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

4.3.3 Fault-injection attacks on AES . . . . . . . . . . . . . . . . . . . . . . . . . . 127

4.3.4 Quantum exhaustive search at t acks . . . . . . . . . . . . . . . . . . . . . . . . 128

4.4 Pseudo-random funct i ons: basic deﬁnitions and properties . . . . . . . . . . . . . . . 129

4.4.1 Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

4.4.2 Eﬃcient implementation of random functions . . . . . . . . . . . . . . . . . . 130

4.4.3 When is a secur e block cipher a secure PRF? . . . . . . . . . . . . . . . . . . 131

4.4.4 Constructing PRGs from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 135

4.4.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

4.5 Constructi ng block ciphers from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 138

4.6 The tree constructi on: from PRGs to PRFs . . . . . . . . . . . . . . . . . . . . . . . 144

4.6.1 Variable length tree construction . . . . . . . . . . . . . . . . . . . . . . . . . 148

剩余579页未读，继续阅读

绝不原创的飞龙

粉丝: 1w+
资源: 1091

会员权益专享

A Graduate Course in Applied Cryptography v0.3

评论0

会员权益专享

最新资源

A Graduate Course in Applied Cryptography v0.3

评论0

应用密码学研究生课程A Graduate Course in Applied Cryptography

A Graduate Course in Applied Cryptography.pdf

Applied Cryptography PART1

Handbook of Applied Cryptography.pdf

Applied Cryptography

GROUP THEORY IN CRYPTOGRAPHY

《New Directions in Cryptography》的引用格式

cryptographydeprecationwarning: python 3.6 is no longer supported by the python core team. therefore, support for it is deprecated in cryptography and will be removed in a future release. from cryptography.hazmat.backends import default_backend

cryptography教程

"Post-Quantum Cryptography: A Ten-Year Survey" by Daniele Micciancio et al. 的引用格式

No module named 'cryptography'

cryptography.exceptions.UnsupportedAlgorithm: SM2 is not a supported elliptic curve

我想学习密码学，帮我推荐几本书籍

Could not find a version that satisfies the requirement cryptography (from versions: ) No matching distribution found for cryptography

import cryptography ModuleNotFoundError: No module named 'cryptography'

pycharm无法安装cryptography

会员权益专享

最新资源