LectureNotesonCryptography(麻省理工学院密码学讲义)

Cryptography

需积分: 10 190 浏览量更新于2023-03-16 评论收藏 1.64MB PDF 举报

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

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Lecture Notes on Cryptography

Shafi Goldwasser

Mihir Bellare

August 2001

MIT Laboratory of Computer Science, 545 Technology Square, Cambridge, MA 02139, USA. E-

mail: shafi@theory.lcs.mit.edu ; Web page: http://theory.lcs.mit.edu/ shafi

Department of Computer Science and Engineering, Mail Code 0114, University of California

at San Diego, 9500 Gilman Drive, La Jolla, CA 92093, USA. E-mail: mihir@cs.ucsd.edu ; Web

page: http://www-cse.ucsd.edu/users/mihir

Table of Contents

1 Introduction to Modern Cryptography 11

1.1 Encryption: Historical Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 Modern Encryption: A Computational Complexity Based Theory . . . . . . . . . . . . . . . . 12

1.3 A Short List of Candidate One Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4 Security Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5 The Model of Adversary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.6 Road map to Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 One-way and trapdoor functions 17

2.1 One-Way Functions: Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 One-Way Functions: Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1 (Strong) One Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.2 Weak One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.3 Non-Uniform One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.4 Collections Of One Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.5 Trapdoor Functions and Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 In Search of Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.1 The Discrete Logarithm Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3.2 The RSA function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.3 Connection Between The Factorization Problem And Inverting RSA . . . . . . . . . . 30

2.3.4 The Squaring Trapdoor Function Candidate by Rabin . . . . . . . . . . . . . . . . . . 30

2.3.5 A Squaring Permutation as Hard to Invert as Factoring . . . . . . . . . . . . . . . . . 34

2.4 Hard-core Predicate of a One Way Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4.1 Hard Core Predicates for General One-Way Functions . . . . . . . . . . . . . . . . . . 35

2.4.2 Bit Security Of The Discrete Logarithm Function . . . . . . . . . . . . . . . . . . . . . 36

2.4.3 Bit Security of RSA and SQUARING functions . . . . . . . . . . . . . . . . . . . . . . 38

2.5 One-Way and Trapdoor Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.5.1 Examples of Sets of Trapdoor Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3 Pseudo-random bit generators 41

3.0.2 Generating Truly Random bit Sequences . . . . . . . . . . . . . . . . . . . . . . . . . 41

4 Goldwasser and Bellare

3.0.3 Generating Pseudo-Random Bit or Number Sequences . . . . . . . . . . . . . . . . . . 42

3.0.4 Provably Secure Pseudo-Random Generators: Brief overview . . . . . . . . . . . . . . 43

3.1 Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2 The Existence Of A Pseudo-Random Generator . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3 Next Bit Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.4 Examples of Pseudo-Random Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.4.1 Blum/Blum/Shub Pseudo-Random Generator . . . . . . . . . . . . . . . . . . . . . . . 49

4 Block ciphers and modes of operation 51

4.1 What is a block cipher? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.2 Data Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.2.1 A brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.2.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.2.3 Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.3 Advanced Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.4 Some Modes of operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4.1 Electronic codebook mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4.2 Cipher-block chaining mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4.3 Counter mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.5 Key recovery attacks on block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.6 Limitations of key-recovery based security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.7 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5 Pseudo-random functions 58

5.1 Function families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.2 Random functions and permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.3 Pseudorandom functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.4 Pseudorandom permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.4.1 PRP under CPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.4.2 PRP under CCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.4.3 Relations between the notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.5 Sequences of families of PRFs and PRPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.6 Usage of PRFs and PRPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.6.1 The shared random function model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.6.2 Modeling block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.7 Example Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.8 Security against key-recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.9 The birthday attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.10 PRFs versus PRPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

5.11 Constructions of PRF families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.11.1 Extending the domain size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.12 Some applications of PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.12.1 Cryptographically Strong Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.12.2 Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.12.3 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.12.4 Identify Friend or Foe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.12.5 Private-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

Cryptography: Lecture Notes 5

5.13 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.14 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6 Private-key encryption 82

6.1 Symmetric encryption schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.2 Some encryption schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.3 Issues in security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.4 Information-theoretic security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

6.5 Indistinguishability under chosen-plaintext attack . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.5.1 Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.5.2 Alternative interpretation of advantage . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6.6 Example chosen-plaintext attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6.6.1 Attack on ECB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6.6.2 Deterministic, stateless schemes are insecure . . . . . . . . . . . . . . . . . . . . . . . 96

6.7 Security against plaintext recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.8 Security of CTR against chosen-plaintext attack . . . . . . . . . . . . . . . . . . . . . . . . . 100

6.8.1 Proof of Theorem 6.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

6.8.2 Proof of Theorem 6.18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

6.9 Security of CBC against chosen-plaintext attack . . . . . . . . . . . . . . . . . . . . . . . . . 110

6.10 Indistinguishability under chosen-ciphertext attack . . . . . . . . . . . . . . . . . . . . . . . . 111

6.11 Example chosen-ciphertext attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

6.11.1 Attack on CTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

6.11.2 Attack on CBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

6.12 Other methods for symmetric encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

6.12.1 Generic encryption with pseudorandom functions . . . . . . . . . . . . . . . . . . . . . 116

6.12.2 Encryption with pseudorandom bit generators . . . . . . . . . . . . . . . . . . . . . . 116

6.12.3 Encryption with one-way functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6.13 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6.14 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

7 Public-key encryption 120

7.1 Deﬁnition of Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

7.2 Simple Examples of PKC: The Trapdoor Function Model . . . . . . . . . . . . . . . . . . . . 122

7.2.1 Problems with the Trapdoor Function Model . . . . . . . . . . . . . . . . . . . . . . . 122

7.2.2 Problems with Deterministic Encryption in General . . . . . . . . . . . . . . . . . . . 123

7.2.3 The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

7.2.4 Rabin’s Public key Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

7.2.5 Knapsacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

7.3 Deﬁning Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

7.3.1 Deﬁnition of Security: Polynomial Indistinguishability . . . . . . . . . . . . . . . . . . 127

7.3.2 Another Deﬁnition: Semantic Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

7.4 Probabilistic Public Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

7.4.1 Encrypting Single Bits: Trapdoor Predicates . . . . . . . . . . . . . . . . . . . . . . . 128

7.4.2 Encrypting Single Bits: Hard Core Predicates . . . . . . . . . . . . . . . . . . . . . . 129

7.4.3 General Probabilistic Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

7.4.4 Eﬃcient Probabilistic Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

7.4.5 An implementation of EPE with cost equal to the cost of RSA . . . . . . . . . . . . . 133

剩余282页未读，继续阅读

艾米的爸爸

粉丝: 693
资源: 314

会员权益专享

Lecture Notes on Cryptography (麻省理工学院密码学讲义)

评论0

会员权益专享

最新资源

Lecture Notes on Cryptography (麻省理工学院密码学讲义)

评论0

Lecture Notes on Cryptography麻省理工学院密码学讲义

密码学讲义Lecture Notes on Cryptography

Lecture Notes on Static Analysis.pdf

四川大学 experiment of digital electronic technology lecture notes

信号处理python书籍推荐

1. 以二叉链表表示二叉树，建立一棵二叉树（算法5.3）；2. 输出二叉树的中序遍历结果（算法5.1或讲稿）；3. 输出二叉树的前序遍历结果（见讲稿）；4. 输出二叉树的后序遍历结果。

python scipy教程

修改（或者重建）course表，使得semester属性的值等于lecture + experiment的值

$_FILES["lecture"]["name"]代码怎么应用

UPDATE course SET semester = lecture+experiment;,这个限制怎么去掉

feyman lecture pdf

推荐一本计算几何最好的书籍

修改（或者重建）使得semester属性的值等于lecture + experiment的值

simulink经典书籍

springer-lncs有中文格式吗

ted belytshcko

会员权益专享

最新资源