Contents
嚜澧ontents
Preface
I
xv
Introduction and Classical Cryptography
1 Introduction
1.1 Cryptography and Modern Cryptography . . . . .
1.2 The Setting of Private-Key Encryption . . . . . .
1.3 Historical Ciphers and Their Cryptanalysis . . . .
1.4 Principles of Modern Cryptography . . . . . . . .
1.4.1 Principle 1 每 Formal Definitions . . . . . .
1.4.2 Principle 2 每 Precise Assumptions . . . . .
1.4.3 Principle 3 每 Proofs of Security . . . . . . .
1.4.4 Provable Security and Real-World Security
References and Additional Reading . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
4
8
16
17
20
22
22
23
24
2 Perfectly Secret Encryption
2.1 Definitions . . . . . . . . . .
2.2 The One-Time Pad . . . . .
2.3 Limitations of Perfect Secrecy
2.4 *Shannon*s Theorem . . . .
References and Additional Reading
Exercises . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
26
32
35
36
37
38
3 Private-Key Encryption
3.1 Computational Security . . . . . . . . . . . . . . . . .
3.1.1 The Concrete Approach . . . . . . . . . . . . .
3.1.2 The Asymptotic Approach . . . . . . . . . . .
3.2 Defining Computationally Secure Encryption . . . . .
3.2.1 The Basic Definition of Security . . . . . . . .
3.2.2 *Semantic Security . . . . . . . . . . . . . . . .
3.3 Constructing Secure Encryption Schemes . . . . . . .
3.3.1 Pseudorandom Generators and Stream Ciphers
3.3.2 Proofs by Reduction . . . . . . . . . . . . . . .
3.3.3 A Secure Fixed-Length Encryption Scheme . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
43
44
45
52
53
56
60
60
65
66
II
. . .
. . .
. .
. . .
. .
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Private-Key (Symmetric) Cryptography
vii
viii
3.4
Stronger Security Notions . . . . . . . . . . . . . . . . . . . .
71
3.4.1 Security for Multiple Encryptions . . . . . . . . . . . .
71
3.4.2 Chosen-Plaintext Attacks and CPA-Security . . . . . .
73
3.5 Constructing CPA-Secure Encryption Schemes . . . . . . . .
77
3.5.1 Pseudorandom Functions and Block Ciphers . . . . .
77
3.5.2 CPA-Secure Encryption from Pseudorandom Functions 82
3.6 Modes of Operation . . . . . . . . . . . . . . . . . . . . . . .
86
3.6.1 Stream-Cipher Modes of Operation . . . . . . . . . . .
86
3.6.2 Block-Cipher Modes of Operation . . . . . . . . . . .
88
3.7 Chosen-Ciphertext Attacks . . . . . . . . . . . . . . . . . . .
96
3.7.1 Defining CCA-Security . . . . . . . . . . . . . . . . . .
96
3.7.2 Padding-Oracle Attacks . . . . . . . . . . . . . . . . .
98
References and Additional Reading . . . . . . . . . . . . . . . . . 101
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4 Message Authentication Codes
4.1 Message Integrity . . . . . . . . . . . . . . . . . . .
4.1.1 Secrecy vs. Integrity . . . . . . . . . . . . . .
4.1.2 Encryption vs. Message Authentication . . .
4.2 Message Authentication Codes 每 Definitions . . . .
4.3 Constructing Secure Message Authentication Codes
4.3.1 A Fixed-Length MAC . . . . . . . . . . . . .
4.3.2 Domain Extension for MACs . . . . . . . . .
4.4 CBC-MAC . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 The Basic Construction . . . . . . . . . . . .
4.4.2 *Proof of Security . . . . . . . . . . . . . . .
4.5 Authenticated Encryption . . . . . . . . . . . . . .
4.5.1 Definitions . . . . . . . . . . . . . . . . . . .
4.5.2 Generic Constructions . . . . . . . . . . . . .
4.5.3 Secure Communication Sessions . . . . . . . .
4.5.4 CCA-Secure Encryption . . . . . . . . . . . .
4.6 *Information-Theoretic MACs . . . . . . . . . . . .
4.6.1 Constructing Information-Theoretic MACs .
4.6.2 Limitations on Information-Theoretic MACs
References and Additional Reading . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
107
107
107
108
110
116
116
118
122
123
125
131
131
132
140
141
142
143
145
146
147
5 Hash Functions and Applications
5.1 Definitions . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Collision Resistance . . . . . . . . . . . . . .
5.1.2 Weaker Notions of Security . . . . . . . . . .
5.2 Domain Extension: The Merkle每Damga?rd Transform
5.3 Message Authentication Using Hash Functions . . .
5.3.1 Hash-and-MAC . . . . . . . . . . . . . . . . .
5.3.2 HMAC . . . . . . . . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . .
. . . .
. . . .
. . . .
.
.
.
.
.
.
.
153
153
154
156
156
158
159
161
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ix
5.4
Generic Attacks on Hash Functions . . . . . . . . . .
5.4.1 Birthday Attacks for Finding Collisions . . . .
5.4.2 Small-Space Birthday Attacks . . . . . . . . . .
5.4.3 *Time/Space Tradeoffs for Inverting Functions
5.5 The Random-Oracle Model . . . . . . . . . . . . . . .
5.5.1 The Random-Oracle Model in Detail . . . . . .
5.5.2 Is the Random-Oracle Methodology Sound? . .
5.6 Additional Applications of Hash Functions . . . . . .
5.6.1 Fingerprinting and Deduplication . . . . . . . .
5.6.2 Merkle Trees . . . . . . . . . . . . . . . . . . .
5.6.3 Password Hashing . . . . . . . . . . . . . . . .
5.6.4 Key Derivation . . . . . . . . . . . . . . . . . .
5.6.5 Commitment Schemes . . . . . . . . . . . . . .
References and Additional Reading . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
164
164
166
168
174
175
179
182
182
183
184
186
187
189
189
6 Practical Constructions of Symmetric-Key Primitives
6.1 Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Linear-Feedback Shift Registers . . . . . . . . . . . .
6.1.2 Adding Nonlinearity . . . . . . . . . . . . . . . . . .
6.1.3 Trivium . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.4 RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Substitution-Permutation Networks . . . . . . . . .
6.2.2 Feistel Networks . . . . . . . . . . . . . . . . . . . .
6.2.3 DES 每 The Data Encryption Standard . . . . . . . .
6.2.4 3DES: Increasing the Key Length of a Block Cipher
6.2.5 AES 每 The Advanced Encryption Standard . . . . .
6.2.6 *Differential and Linear Cryptanalysis . . . . . . . .
6.3 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Hash Functions from Block Ciphers . . . . . . . . .
6.3.2 MD5 . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.3 SHA-0, SHA-1, and SHA-2 . . . . . . . . . . . . . .
6.3.4 SHA-3 (Keccak) . . . . . . . . . . . . . . . . . . . .
References and Additional Reading . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
193
194
195
197
198
199
202
204
211
212
220
223
225
231
232
234
234
235
236
237
7 *Theoretical Constructions of Symmetric-Key Primitives
7.1 One-Way Functions . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . .
7.1.2 Candidate One-Way Functions . . . . . . . . . . . . .
7.1.3 Hard-Core Predicates . . . . . . . . . . . . . . . . . .
7.2 From One-Way Functions to Pseudorandomness . . . . . . .
7.3 Hard-Core Predicates from One-Way Functions . . . . . . .
7.3.1 A Simple Case . . . . . . . . . . . . . . . . . . . . . .
241
242
242
245
246
248
250
250
x
7.3.2 A More Involved Case . . . . . . . . . . . . . . . . .
7.3.3 The Full Proof . . . . . . . . . . . . . . . . . . . . .
7.4 Constructing Pseudorandom Generators . . . . . . . . . . .
7.4.1 Pseudorandom Generators with Minimal Expansion
7.4.2 Increasing the Expansion Factor . . . . . . . . . . .
7.5 Constructing Pseudorandom Functions . . . . . . . . . . .
7.6 Constructing (Strong) Pseudorandom Permutations . . . .
7.7 Assumptions for Private-Key Cryptography . . . . . . . . .
7.8 Computational Indistinguishability . . . . . . . . . . . . .
References and Additional Reading . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
III
.
.
.
.
.
.
.
.
.
.
.
251
254
257
258
259
265
269
273
276
278
279
Public-Key (Asymmetric) Cryptography
8 Number Theory and Cryptographic Hardness Assumptions
8.1 Preliminaries and Basic Group Theory . . . . . . . . . . . .
8.1.1 Primes and Divisibility . . . . . . . . . . . . . . . . . .
8.1.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . .
8.1.3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.4 The Group Z?N . . . . . . . . . . . . . . . . . . . . . .
8.1.5 *Isomorphisms and the Chinese Remainder Theorem .
8.2 Primes, Factoring, and RSA . . . . . . . . . . . . . . . . . .
8.2.1 Generating Random Primes . . . . . . . . . . . . . . .
8.2.2 *Primality Testing . . . . . . . . . . . . . . . . . . . .
8.2.3 The Factoring Assumption . . . . . . . . . . . . . . .
8.2.4 The RSA Assumption . . . . . . . . . . . . . . . . . .
8.2.5 *Relating the RSA and Factoring Assumptions . . . .
8.3 Cryptographic Assumptions in Cyclic Groups . . . . . . . . .
8.3.1 Cyclic Groups and Generators . . . . . . . . . . . . .
8.3.2 The Discrete-Logarithm/Diffie每Hellman Assumptions
8.3.3 Working in (Subgroups of) Z?p . . . . . . . . . . . . .
8.3.4 Elliptic Curves . . . . . . . . . . . . . . . . . . . . . .
8.4 *Cryptographic Applications . . . . . . . . . . . . . . . . . .
8.4.1 One-Way Functions and Permutations . . . . . . . . .
8.4.2 Constructing Collision-Resistant Hash Functions . . .
References and Additional Reading . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
285
287
287
289
291
295
297
302
303
306
311
312
314
316
316
319
322
325
332
332
335
337
338
9 *Algorithms for Factoring and Computing Discrete
rithms
9.1 Algorithms for Factoring . . . . . . . . . . . . . . . . .
9.1.1 Pollard*s p ? 1 Algorithm . . . . . . . . . . . . .
9.1.2 Pollard*s Rho Algorithm . . . . . . . . . . . . . .
9.1.3 The Quadratic Sieve Algorithm . . . . . . . . . .
9.2 Algorithms for Computing Discrete Logarithms . . . .
341
342
343
344
345
348
Loga.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xi
9.2.1 The Pohlig每Hellman Algorithm . . . .
9.2.2 The Baby-Step/Giant-Step Algorithm
9.2.3 Discrete Logarithms from Collisions .
9.2.4 The Index Calculus Algorithm . . . .
9.3 Recommended Key Lengths . . . . . . . . .
References and Additional Reading . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
350
352
353
354
356
357
358
10 Key Management and the Public-Key Revolution
10.1 Key Distribution and Key Management . . . . . . .
10.2 A Partial Solution: Key-Distribution Centers . . . .
10.3 Key Exchange and the Diffie每Hellman Protocol . .
10.4 The Public-Key Revolution . . . . . . . . . . . . . .
References and Additional Reading . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
359
359
361
363
370
372
373
11 Public-Key Encryption
11.1 Public-Key Encryption 每 An Overview . . . . . . . . . . .
11.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.2.1 Security against Chosen-Plaintext Attacks . . . . . .
11.2.2 Multiple Encryptions . . . . . . . . . . . . . . . . . .
11.2.3 Security against Chosen-Ciphertext Attacks . . . . .
11.3 Hybrid Encryption and the KEM/DEM Paradigm . . . . .
11.3.1 CPA-Security . . . . . . . . . . . . . . . . . . . . . .
11.3.2 CCA-Security . . . . . . . . . . . . . . . . . . . . . .
11.4 CDH/DDH-Based Encryption . . . . . . . . . . . . . . . .
11.4.1 El Gamal Encryption . . . . . . . . . . . . . . . . .
11.4.2 DDH-Based Key Encapsulation . . . . . . . . . . . .
11.4.3 *A CDH-Based KEM in the Random-Oracle Model
11.4.4 Chosen-Ciphertext Security and DHIES/ECIES . . .
11.5 RSA Encryption . . . . . . . . . . . . . . . . . . . . . . . .
11.5.1 Plain RSA . . . . . . . . . . . . . . . . . . . . . . .
11.5.2 Padded RSA and PKCS #1 v1.5 . . . . . . . . . . .
11.5.3 *CPA-Secure Encryption without Random Oracles .
11.5.4 OAEP and RSA PKCS #1 v2.0 . . . . . . . . . . .
11.5.5 *A CCA-Secure KEM in the Random-Oracle Model
11.5.6 RSA Implementation Issues and Pitfalls . . . . . . .
References and Additional Reading . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
375
375
378
379
381
387
389
393
398
399
400
404
406
408
410
410
415
417
421
425
429
432
433
12 Digital Signature Schemes
12.1 Digital Signatures 每 An Overview . .
12.2 Definitions . . . . . . . . . . . . . . .
12.3 The Hash-and-Sign Paradigm . . . . .
12.4 RSA Signatures . . . . . . . . . . . .
.
.
.
.
439
439
441
443
444
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- thule ridealong mini
- e2 travel management service user guide
- dormer product selector
- aruba instant 6 4 3 4 4 2 1 user guide
- route lab guide boson
- comptia security sy0 601 exam cram 6 e
- brigade administration support system bass
- 5 2 wire and cable markers
- setup opal rad workstation for viewing internet explorer 11
- 501 famous personalities
Related searches
- home contents inventory worksheet
- insurance contents list sample
- powershell list contents folder
- excel vba copy cell contents to clipboard
- contents of zambian bill 10
- contents of iv fluids
- powershell clear contents of file
- who buys contents of home
- get folder contents powershell
- copy folder and contents cmd
- copy all contents of directory cmd
- copy contents of directory cmd