Introduction to modern cryptography

Title:

Personal Author:

Katz, Jonathan, 1974- author

Series:

Chapman & hall/crc cryptography and network security series

Edition:

Second edition

Publication Information:

Boca Raton : CRC Press/Taylor & Francis, 2015

Physical Description:

xx, 583 pages : illustrations ; 25 cm.

ISBN:

9781466570269

Subject Term:

Computer security

Cryptography

Added Author:

Lindell, Yehuda,

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010344143	QA76.9.A25 K38 2015	Open Access Book	Book	Searching... Unknown

Cryptography is ubiquitous and plays a key role in ensuring data secrecy and integrity as well as in securing computer systems more broadly. Introduction to Modern Cryptography provides a rigorous yet accessible treatment of this fascinating subject.

The authors introduce the core principles of modern cryptography, with an emphasis on formal definitions, clear assumptions, and rigorous proofs of security. The book begins by focusing on private-key cryptography, including an extensive treatment of private-key encryption, message authentication codes, and hash functions. The authors also present design principles for widely used stream ciphers and block ciphers including RC4, DES, and AES, plus provide provable constructions of stream ciphers and block ciphers from lower-level primitives. The second half of the book covers public-key cryptography, beginning with a self-contained introduction to the number theory needed to understand the RSA, Diffie-Hellman, and El Gamal cryptosystems (and others), followed by a thorough treatment of several standardized public-key encryption and digital signature schemes.

Integrating a more practical perspective without sacrificing rigor, this widely anticipated Second Edition offers improved treatment of:

Stream ciphers and block ciphers, including modes of operation and design principles Authenticated encryption and secure communication sessions Hash functions, including hash-function applications and design principles Attacks on poorly implemented cryptography, including attacks on chained-CBC encryption, padding-oracle attacks, and timing attacks The random-oracle model and its application to several standardized, widely used public-key encryption and signature schemes Elliptic-curve cryptography and associated standards such as DSA/ECDSA and DHIES/ECIES

Containing updated exercises and worked examples, Introduction to Modern Cryptography, Second Edition can serve as a textbook for undergraduate- or graduate-level courses in cryptography, a valuable reference for researchers and practitioners, or a general introduction suitable for self-study.

Author Notes

Jonathan Katz is a professor of computer science at the University of Maryland, and director of the Maryland Cybersecurity Center. He has published over 100 articles on cryptography, and serves as an editor of the Journal of Cryptology , the premier journal of the field. Prof. Katz has been invited to give introductory lectures on cryptography for audiences in academia, industry, and government, as well as an on-line cryptography course through Coursera.

Yehuda Lindell is a professor of computer science at Bar-Ilan University. He has published more than 90 articles on cryptography and four books, and has considerable industry experience in deploying cryptographic schemes. Professor Lindell lectures widely in both academic and industry venues on both theoretical and applied cryptography, and has been recognized with two prestigious grants from the European Research Council.

Preface	p. xv
I Introduction and Classical Cryptography
1 Introduction	p. 3
1.1 Cryptography and Modern Cryptography	p. 3
1.2 The Setting of Private-Key Encryption	p. 4
1.3 Historical Ciphers and Their Cryptanalysis	p. 8
1.4 Principles of Modern Cryptography	p. 16
1.4.1 Principle 1 - Formal Definitions	p. 17
1.4.2 Principle 2 - Precise Assumptions	p. 20
1.4.3 Principle 3 - Proofs of Security	p. 22
1.4.4 Provable Security and Real-World Security	p. 22
References and Additional Reading	p. 23
Exercises	p. 24
2 Perfectly Secret Encryption	p. 25
2.1 Definitions	p. 26
2.2 The One-Time Pad	p. 32
2.3 Limitations of Perfect Secrecy	p. 35
2.4 *Shannon's Theorem	p. 36
References and Additional Reading	p. 37
Exercises	p. 38
II Private-Key (Symmetric) Cryptography
3 Private-Key Encryption	p. 43
3.1 Computational Security	p. 43
3.1.1 The Concrete Approach	p. 44
3.1.2 The Asymptotic Approach	p. 45
3.2 Defining Computationally Secure Encryption	p. 52
3.2.1 The Basic Definition of Security	p. 53
3.2.2 *Semantic Security	p. 56
3.3 Constructing Secure Encryption Schemes	p. 60
3.3.1 Pseudorandom Generators and Stream Ciphers	p. 60
3.3.2 Proofs by Reduction	p. 65
3.3.3 A Secure Fixed-Length Encryption Scheme	p. 66
3.4 Stronger Security Notions	p. 71
3.4.1 Security for Multiple Encryptions	p. 71
3.4.2 Chosen-Plaintext Attacks and CPA-Security	p. 73
3.5 Constructing CPA-Secure Encryption Schemes	p. 77
3.5.1 Pseudorandom Functions and Block Ciphers	p. 77
3.5.2 CPA-Secure Encryption from Pseudorandom Functions	p. 82
3.6 Modes of Operation	p. 86
3.6.1 Stream-Cipher Modes of Operation	p. 86
3.6.2 Block-Cipher Modes of Operation	p. 88
3.7 Chosen-Cipher text Attacks	p. 96
3.7.1 Defining CCA-Security	p. 96
3.7.2 Padding-Oracle Attacks	p. 98
References and Additional Reading	p. 101
Exercises	p. 102
4 Message Authentication Codes	p. 107
4.1 Message Integrity	p. 107
4.1.1 Secrecy vs. Integrity	p. 107
4.1.2 Encryption vs. Message Authentication	p. 108
4.2 Message Authentication Codes - Definitions	p. 110
4.3 Constructing Secure Message Authentication Codes	p. 116
4.3.1 A Fixed-Length MAC	p. 116
4.3.2 Domain Extension for MACs	p. 118
4.4 CBC-MAC	p. 122
4.4.1 The Basic Construction	p. 123
4.4.2 *Proof of Security	p. 125
4.5 Authenticated Encryption	p. 131
4.5.1 Definitions	p. 131
4.5.2 Generic Constructions	p. 132
4.5.3 Secure Communication Sessions	p. 140
4.5.4 CCA-Secure Encryption	p. 141
4.6 *Information-Theoretic MACs	p. 142
4.6.1 Constructing Information-Theoretic MACs	p. 143
4.6.2 Limitations on Information-Theoretic MACs	p. 145
References and Additional Reading	p. 146
Exercises	p. 147
5 Hash Functions and Applications	p. 153
5.1 Definitions	p. 153
5.1.1 Collision Resistance	p. 154
5.1.2 Weaker Notions of Security	p. 156
5.2 Domain Extension: The Merkle-Damgård Transform	p. 156
5.3 Message Authentication Using Hash Functions	p. 158
5.3.1 Hash-and-MAC	p. 159
5.3.2 HMAC	p. 161
5.4 Generic Attacks on Hash Functions	p. 164
5.4.1 Birthday Attacks for Finding Collisions	p. 164
5.4.2 Small-Space Birthday Attacks	p. 166
5.4.3 *Time/Space Tradeoffs for Inverting Functions	p. 168
5.5 The Random-Oracle Model	p. 174
5.5.1 The Random-Oracle Model in Detail	p. 175
5.5.2 Is the Random-Oracle Methodology Sound?	p. 179
5.6 Additional Applications of Hash Functions	p. 182
5.6.1 Fingerprinting and Deduplication	p. 182
5.6.2 Merkle Trees	p. 183
5.6.3 Password Hashing	p. 184
5.6.4 Key Derivation	p. 186
5.6.5 Commitment Schemes	p. 187
References and Additional Reading	p. 189
Exercises	p. 189
6 Practical Constructions of Symmetric-Key Primitives	p. 193
6.1 Stream Ciphers	p. 194
6.1.1 Linear-Feedback Shift Registers	p. 195
6.1.2 Adding Nonlinearity	p. 197
6.1.3 Trivium	p. 198
6.1.4 RC4	p. 199
6.2 Block Ciphers	p. 202
6.2.1 Substitution-Permutation Networks	p. 204
6.2.2 Feistel Networks	p. 211
6.2.3 DES - The Data Encryption Standard	p. 212
6.2.4 3DES: Increasing the Key Length of a Block Cipher	p. 220
6.2.5 AES - The Advanced Encryption Standard	p. 223
6.2.6 *Differential and Linear Crypt analysis	p. 225
6.3 Hash Functions	p. 231
6.3.1 Flash Functions from Block Ciphers	p. 232
6.3.2 MD5	p. 234
6.3.3 SHA-0, SHA-1, and SHA-2	p. 234
6.3.4 SHA-3 (Keccak)	p. 235
References and Additional Reading	p. 236
Exercises	p. 237
7 *Theoretical Constructions of Symmetric-Key Primitives	p. 241
7.1 One-Way Functions	p. 242
7.1.1 Definitions	p. 242
7.1.2 Candidate One-Way Functions	p. 245
7.1.3 Hard-Core Predicates	p. 246
7.2 From One-Way Functions to Pseudorandonmess	p. 248
7.3 Hard-Core Predicates from One-Way Functions	p. 250
7.3.1 A Simple Case	p. 250
7.3.2 A More Involved Case	p. 251
7.3.3 The Full Proof	p. 254
7.4 Constructing Pseudorandom Generators	p. 257
7.4.1 Pseudorandom Generators with Minimal Expansion	p. 258
7.4.2 Increasing the Expansion Factor	p. 259
7.5 Constructing Pseudorandom Functions	p. 265
7.6 Constructing (Strong) Pseudorandom Permutations	p. 269
7.7 Assumptions for Private-Key Cryptography	p. 273
7.8 Computational Indistinguishability	p. 276
References and Additional Reading	p. 278
Exercises	p. 279
III Public-Key (Asymmetric) Cryptography
8 Number Theory and Cryptographic Hardness Assumptions	p. 285
8.1 Preliminaries and Basic Group Theory	p. 287
8.1.1 Primes and Divisibility	p. 287
8.1.2 Modular Arithmetic	p. 289
8.1.3 Groups	p. 291
8.1.4 The Group Z* N	p. 295
8.1.5 *Isomorphisms and the Chinese Remainder Theorem	p. 297
8.2 Primes, Factoring, and RSA	p. 302
8.2.1 Generating Random Primes	p. 303
8.2.2 *Primality Testing	p. 306
8.2.3 The Factoring Assumption	p. 311
8.2.4 The RSA Assumption	p. 312
8.2.5 *Relating the RSA and Factoring Assumptions	p. 314
8.3 Cryptographic Assumptions in Cyclic Groups	p. 316
8.3.1 Cyclic Groups and Generators	p. 316
8.3.2 The Discrete-Logarithm/Diffie-Hellman Assumptions	p. 319
8.3.3 Working in (Subgroups of) Z* P	p. 322
8.3.1 Elliptic Curves	p. 325
8.4 *Cryptographic Applications	p. 332
8.4.1 One-Way Functions and Permutations	p. 332
8.4.2 Constructing Collision-Resist ant Hash Functions	p. 335
References and Additional Reading	p. 337
Exercises	p. 338
9 *Algorithms for Factoring and Computing Discrete Logarithms	p. 341
9.1 Algorithms for Factoring	p. 342
9.1.1 Pollards p - 1 Algorithm	p. 343
9.1.2 Pollard's Rho Algorithm	p. 344
9.1.3 The Quadratic Sieve Algorithm	p. 345
9.2 Algorithms for Computing Discrete Logarithms	p. 348
9.2.1 The Pohlig-Hellman Algorithm	p. 350
9.2.2 The Baby-Step/Giant-Step Algorithm	p. 352
9.2.3 Discrete Logarithms from Collisions	p. 353
9.2.4 The Index Calculus Algorithm	p. 354
9.3 Recommended Key Lengths	p. 356
References and Additional Reading	p. 357
Exercises	p. 358
10 Key Management and the Public-Key Revolution	p. 359
10.1 Key Distribution and Key Management	p. 359
10.2 A Partial Solution: Key-Distribution Centers	p. 361
10.3 Key Exchange and the Diffie-Hellman Protocol	p. 363
10.4 The Public-Key Revolution	p. 370
References and Additional Reading	p. 372
Exercises	p. 373
11 Public-Key Encryption	p. 375
11.1 Public-Key Encryption - An Overview	p. 375
11.2 Definitions	p. 378
11.2.1 Security against Chosen-Plaintext Attacks	p. 379
11.2.2 Multiple Encryptions	p. 381
11.2.3 Security against Chosen-Ciphertext Attacks	p. 387
11.3 Hybrid Encryption and the KEM/DEM Paradigm	p. 389
11.3.1 CPA-Security	p. 393
11.3.2 CCA-Security	p. 398
11.4 CDH/DDH-Based Encryption	p. 399
11.4.1 El Gamal Encryption	p. 400
11.4.2 DDH-Based Key Encapsulation	p. 404
11.4.3 *A CDH-Based KEM in the Random-Oracle Model	p. 406
11.4.4 Chosen-Ciphertext Security and DHIES/ECIES	p. 408
11.5 RSA Encryption	p. 410
11.5.1 Plain RSA	p. 410
11.5.2 Padded RSA and PKCS #1 v1.5	p. 415
11.5.3 *CPA-Secure Encryption without Random Oracles	p. 417
11.5.4 OAEP and RSA PKCS #1 v2.0	p. 421
11.5.5 *A CCA-Secure KEM in the Random-Oracle Model	p. 425
11.5.6 RSA Implementation Issues and Pitfalls	p. 429
References and Additional Reading	p. 432
Exercises	p. 433
12 Digital Signature Schemes	p. 439
12.1 Digital Signatures - An Overview	p. 439
12.2 Definitions	p. 441
12.3 The Hash-and-Sign Paradigm	p. 443
12.4 RSA Signatures	p. 444
12.4.1 Plain RSA	p. 444
12.4.2 RSA-FDH and PKCS #1 v2.1	p. 446
12.5 Signatures from the Discrete-Logarithm Problem	p. 451
12.5.1 The Schnorr Signature Scheme	p. 451
12.5.2 DSA and ECDSA	p. 459
12.6 *Signatures from Hash Functions	p. 461
12.6.1 Lamport's Signature Scheme	p. 461
12.6.2 Chain-Based Signatures	p. 465
12.6.3 Tree-Based Signatures	p. 468
12.7 *Certificates and Public-Key Infrastructures	p. 473
12.8 Putting It All Together - SSL/TLS	p. 479
12.9 *Signcryption	p. 481
References and Additional Reading	p. 483
Exercises	p. 484
13 *Advanced Topics in Public-Key Encryption	p. 487
13.1 Public-Key Encryption from Trapdoor Permutations	p. 487
13.1.1 Trapdoor Permutations	p. 488
13.1.2 Public-Key Encryption from Trapdoor Permutations	p. 489
13.2 The Paillier Encryption Scheme	p. 491
13.2.1 The Structure of Z* N 2	p. 492
13.2.2 The Paillier Encryption Scheme	p. 494
13.2.3 Homomorphic Encryption	p. 499
13.3 Secret Sharing and Threshold Encryption	p. 501
13.3.1 Secret Sharing	p. 501
13.3.2 Verifiable Secret Sharing	p. 503
13.3.3 Threshold Encryption and Electronic Voting	p. 505
13.4 The Goldwasser-Micali Encryption Scheme	p. 507
13.4.1 Quadratic Residues Modulo a Prime	p. 507
13.4.2 Quadratic Residues Modulo a Composite	p. 510
13.4.3 The Quadratic Residuosity Assumption	p. 514
13.4.4 The Goldwasser-Micali Encryption Scheme	p. 515
13.5 The Rabin Encryption Scheme	p. 518
13.5.1 Computing Modular Square Roots	p. 518
13.5.2 A Trapdoor Permutation Based on Factoring	p. 523
13.5.3 The Rabin Encryption Scheme	p. 527
References and Additional Reading	p. 528
Exercises	p. 529
Index of Common Notation	p. 533
Appendix A Mathematical Background	p. 537
A.1 Identities and Inequalities	p. 537
A.2 Asymptotic Notation	p. 537
A.3 Basic Probability	p. 538
A.4 The "Birthday" Problem	p. 542
A.5 *Finite Fields	p. 544
Appendix B Basic Algorithmic Number Theory	p. 547
B.1 Integer Arithmetic	p. 549
B.1.1 Basic Operations	p. 549
B.1.2 The Euclidean and Extended Euclidean Algorithms	p. 550
B.2 Modular Arithmetic	p. 552
B.2.1 Basic Operations	p. 552
B.2.2 Computing Modular Inverses	p. 552
B.2.3 Modular Exponentiation	p. 553
B.2.4 *Montgomery Multiplication	p. 556
B.2.5 Choosing a Uniform Group Element	p. 557
B.3 *Finding a Generator of a Cyclic Group	p. 559
B.3.1 Group-Theoretic Background	p. 559
B.3.2 Efficient Algorithms	p. 561
References and Additional Reading	p. 562
Exercises	p. 562
References	p. 563
Index	p. 577

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents