Introduction to Modern Cryptography

乔纳森•卡茨写的现代密码学，英文版，有目录结构PrefaceThis book presents the basic paradigms and principles of modern cryptogra-phy. It is designed to serve as a textbook for undergraduate- or graduate-levelcourses in cryptography (in computer science or mathematics departments)as a general introduction suitable for self-study(especially for beginning grad-uate students), and as a reference for students, researchers, and practitionersThere are numerous other cryptography textbooks available today, and thereader may rightly ask whether another book on the subject is needed. Wewould not have written this book if the answer to that question were anythingother than al unequivocal yes. The novelty of this book-and what, in ouropinion, distinguishes it from a l other books currently on the market- isthat it provides a rigorous treatment of modern cryptography in an accessiblemanner appropriate for an introduction to the topic. To be sure the materialin this book is difficult (at least in comparison to some other books in thisarea). Rather than shy away from this difficulty, however, we have chosen toface it head-on, to lead the reader through the demanding(yet enthrallingsubject matter rather than shield the readers eyes frOIn it. We hope readers(and instructors)will respond by taking up the challengeS mentioned, our focus is on modern(post-1980s) cryptography, whichis distinguished froIn classical cryptography by its emphasis on definitiOnprecise assumptions, and rigorous proofs of security. We briefy discuss eachof these in turn(these principles are explored in greater detail in Chapter 1)The ccntral rolc of dcfinitions: A kcy intellectual contribution ofmodern cryptography has been the recognition that formal definitionsof security are an essential first step in the design of any cryptographicprimitive or protocol. The reason, in retrospect, is simple: if you dontknow what it is you are trying to achieve, how can you hope to knowwhen you have achieved it? As we will see in this book, cryptographicdefinitions of security are quite strong and- at first glance-mayappear impossible to achieve. One of the most amazing aspects of cryptography is that (under mild and widely-believed assumptions)efficientconstructions satisfying such strong definitions can be proven to existThe importance of formal and precise assumptions: As willbe explained in Chapter 2, many cryptographic constructions cannotcurrently be proven secure in an unconditional sense. Security oftenrelies, instead, on some widely-believed(albeit unproven) assumptionThe modern cryptographic approach dictates that any such assumptionmust be clearly and unambidefined. This not only allows for objective evaluation of the assumption, but, more importantly, enablesrigorous proofs of security as described nextThe possibility of rigorous proofs of security: The previous twoideas lead naturally to the current one, which is the realization that cryp-logruplic constructions car be proven secure with respect to a given def-inition of security and relative to a well-defined cryptographic assump-tion. This is the essence of modern cryptography, and was responsiblefor the transformation of cryptography from an art to a scienceThe iInportance of this idea cannot be over-eInlphasized. Historically,cryptographic schemes were designed in a largely ad-hoc fashion, andwere deemed to be secure if the designers themselves could not findany attacks. In contrast, modern cryptography promotes the designof schemes with forma. l, mat, hema. tical proofs of securitv in well-definedmodels. Such schemes are guaranteed to be secure unless the underlying assumption is false(or the security definition did not appropriatelymodel the real-world security concerns). By relying on long-standingassumptions(e. g, the assumption that "factoring is hard"), it is thuspossiblc to obtain schemas that arc extrcmcly unlikely to bc brokenA unified approach. The above contributions of modern cryptography arefelt not only within the"theory of cryptography"community. The importanceof precise definitions is, by now, widely understood and appreciated by thosein the security community(as well as those who use cryptographic tools tobuild secure systems), and rigorous proofs of security have become one ofthe requirements for cryptographic schemes to be standardized. As such, wedo not scparatc“ applicd cryptography”from“ provable sccurity”; rather,wopresent practical and widely-used constructions along with precise statements(and, most, of the time, a proof) of what definition of security is achievedGuide to Using this BookThis guide is intended primarily for instructors seeking to adopt this bookfor their course, though the student picking up this book on his or her ownmay also find it usefulRequired background. This book uses definitions, proofs, and mathemat-ical concepts, and therefore requires some Mathematical Imaturity. II palticular, the reader is assumed to have had some exposure to proofs at thecollege level, say in an upper-level mathematics course or a course on discretemathematics, algorithms, or computability theory. Ilaving said this, we havemade a significant effort to simplify the presentation and make it generallyaccessible. It is our belief that this book is not more difficult than analogoustextbooks that are less rigorous. On the contrary, we believe that(to take oneexample) once security goals are clearly formulated, it often becomes easierto understand the design choices made in a particular constructionWe have structured the book so that the only formal prerequisites are acourse in algorithms and a course in discrete mathematics. Even here we relyon very little Inaterial: specilically, we assune soine familiarity with basicprobability and big-O notation, modular arithmetic, and the idea of equatingcfficicnt algorithms with thosc running in polynomial timc. Thesc conceptsare reviewed in Appendix A and/or when first used in the bookSuggestions for course organization. The core material of this book.which we strongly recommend should be covered in any introductory courseon cryptography, consists of the following (starred sections are excluded inwhat follows; see further discussion regarding starred material below)Chapters 1-4(through Section 4.6), discussing classical cryptography,modcrn cryptography, and the basics of privatc-kcy cryptography (bothprivate-key encryption and message authentication)Chapter 7, introducing concrete mathematical problems believed to behard, providing the number-theoretic background needed to under-stand RSA, Diffie-Hellman, and El Gamal, and giving a favor of hownumber-theoretic assumptions are used in cryptographyChapters 9 and 10, motivating the public-key setting and discussingpublic-key encryption(including RSA-based schemes and El Gamal)Chapter 12, describing digital signature schemesSections 13. 1 and 13.3, introducing the random oracle model and theRSA-FDH signature schemeWe believe that this core material- possibly omitting some of the morein-depth discussion and some proofs- can be covered in a 30-35-hour undergraduate course. Instructors with more time available could proceed at a moreleisurely pace, e.g, giving details of all proofs and going more slowly whenintroducing the underlying group theory and number-theoretic backgroundAlternately, additional topics could be incorporated as discussed nextThose wishing to cover additional material, in either a longer course or afaster-paced graduate course, will find that the book has been structured toallow flexible incorporation of other topics as time permits(and depending onthe iustructor's interests). Specifically, sOinle of the chapters and sections arestarred(). These sections are not less important in any way, but arguablydo not constitute "core material"for an introductory course in cryptograpAs made evident by the course outline just given(which does not include anystarred material), starred chapters and sections may be skipped-or coveredat any point subsequent to their appearance in the book- without affectinghe How of the course. In particular, we have taken care to ensure that none ofthe later un-starred material depends on any starred material. For the mostpart, the starred chapters also do not depend on each other (and in the rarecases when they do, this dependence is explicitly noted)We suggest the following from among the starred topics for those wishingto give their course a particular flaTheorg: A more theoretically-inclined course could include materialfrom Sections 4.8 and 4.9(dealing with stronger notions of security forprivate-key encryption); Chapter 6(introducing one-way functions andhard-core bits, and constructing pseudorandom generators and pseudorandom functions/permutations starting from any one-way permuta-tion); Section 10.7(constructing public-key encryption from trapdoorpermutations); Chapter 11(describing the Goldwasser-Micali, Rabinand Paillier encryption schemes): and Section 12.6 (showing a signaturescheme that does not rely on random oracles)Application.s: An inst ructor wanting to emphasize practica. I aspectsof cryptography is highly encouraged to cover Section 4.7(describingHMAC); Chapter 5(discussing modern block ciphers and techniquesused in their design); and all of Chapter 13(giving cryptographic constructions in the random oracle model)Mathematics: A course directed at students with a strong mathematicsbackground - or taught by someone who enjoys this aspect of cryp-tography- could incorporate material from Chapter 5(see above)aswell as Section 7.3. 4(elliptic-curve groups ); Chapter 8(algorithms forfactoring alld cOMputing discrete logarithMS); and Chapter 11(describing the Goldwasser-Micali, Rabin, and Paillier encryption schemes alongwith all the necessary number-theoretic background)Comments and errataOur goal in writing this book was to make modern cryptography accessibleto a wide audience outside the"theoretical computer science"community. Wehope you will let us know whether we have succeeded. In particular, we arealways Inore thall happy to r'eceive feedback ol this book, especially construc-tive comments telling us how the book can be improved. We hope there areno errors or typos in the book; if you do find any, however, we would greatlyappreciate it if you let us know.(A list of known errata will be maintainedathttp://www.cs.umd.Edu/jkatz/imc.html.)Youcanemailyourcom-ments and errata to jkatz@cs umd. edu and lindell@cs. biu ac il; pleaseput "Introduction to Modern Cryptography" in the subject lineAcknowledgementsJonathan Katz is deeply indebted to Zvi Galil, Moti Yung, and Rafail otrovsky for their help, guidance, and support throughout his career. This bookwould never have come to be without their contributions to his developmentand he thanks them for that. He would also like to thank his colleagues withwhom he has had numerous discussions on the "right approach to writing acryptography textbookand in particular Victor ShoupYehuda lindell wishes to first and foremost thank oded Goldreich and moiliNaor for introducing him to the world of cryptography. Their influence is feltuntil today and will undoubtedly continue to be felt in the future. There aremany, many other people who have also had considerable influence over theyears and instead of mentioning them all, he will just say thank you- younow who you are.Both authors would like to extend their gratitude to those who read andcommented on earlier drafts of this book. We thank Salil Vadhan and alonRosen who experimented with this text in an introductory course on cryptography at Harvard and provided us with valuable fccdback. Wc also thankall of the following for their many comments and corrections: Adam benderYair Dombb, William Glenn, s. Dov Gordon, Ca.. Hazay, Avivit. LevyMatthew Mah. Jason Rogers, Rui Xue, Dicky Yan, and Hila zarosim. We arevery grateful to all those who encouraged us to write this book and concurredwith our feeling that a book of this nature is badly neededFinally, we thank our (respective wives and children for all their supportand understanding during the many hours, days, and months that we havespent On this projectContentsPrefaceI Introduction and Classical Cryptograph1 Introduction and Classical Ciphers1.2 The Sctting of Privatc-KCy Encryptio1.1 Cryptography and Modern Cryptographi133491.3 Historical Ciphers alld Their Cryptalladlysis1.4 The Basic Principles of Modern Cryptography1.4.1 Principle 1 Formulation of Exact Definitions181.4.2 Principle 2- Reliance on Precise Assumptions241.4.3 Principle 3- Rigorous Proofs of SecurityRcfcrcnces and Additional readingExercises2 Perfectly-Secret Encryption292.1 Dcfinitions and Basic Propertics292.2 The One-Tiine Pad(Verlalnl's Cipher)342.3 Limitations of Perfect Secrecy372.4 Shannon's Theorem2.5 SummaryReferences and Additional Reading41ExercisesII Private-Key(Symmetric) Cryptography453 Private-Key Encryption and Pseudorandomness473.1 A Computational Approach to Cryptography3. 1.1 The Basic Idea of CoInlputatiollal Security3.1.2 Efficient Algorithms and Negligible Success543.1.3 Proofs by rcduction3.2 A Definition of ColnlputatiOmally-Secure EllcryptiOI593.2.1 A Definition of Security for Encryption603.2.2 Properties of the Definition643.3 Pseudorandomness3.4 Constructing Secure Encryption Schemes723.4.1 A Secure Fixed-Length Encryption Scheme723.4.2 Handling Variable-Length Messages753.4.3 Stream Ciphers and Multiple Encryptions763.5 Security under Chosen-Plaintext Attacks(CPA)813.6 Constructing CPA-Secure Encryption Schemes853.6.2 CPA-Secure Encryption Schemes from Pseudorandom ds3.6.1 Pseudorandom functionsunctions3.6.3 PseudoraldoIn Permutations anld Block Ciphers3.6.4 Modes of Operation3.7 Security Against Chosen-Ciphertext Attacks(CCA100References and Additional reading102Exercises4 Message Authentication Codes and Collision-Resistant HashFunctions1074.1 Secure Communication and Message Integrity1074.2 Encryption and Message Authentication1084.3 Message Authentication Codes Definitions104.4 Constructing Secure Message Authentication Codes1134.5 CBC-MAC4.6 Collision-Resistant Hash Functions1214.6.1 Defining Collision Resistance1224.6.2 Weaker Notions of security for hash Functions1244.6.3 A Generic“ Birthday” Attack.1254.6.4 The Merkle-Damgard Transform1274.6.5 Collision-Resistant Hash Functions in Practice1294.7 NMAC and HMac1324.7.1 Nested MAC(NMAC)1324.7.2 HMAC1354. 8 x Achieving Chosen-Ciphertext Secure Encryption1374.9 ObtaPrivacy and mAuthenticate141References and Additional readingⅹ excises5 Pseudorandom objects in Practice: Block Ciphers1515.1 Substitution-Permutation Networks1545.2 Feistel networks1605. 3 DES- The Data Encryption Standard1625.3.1 The Design of DES5.3.2 Attacks on Reduced-Round Variants of DEo1621655.3. 3 The Security of DEs1684 Increasing the Key Size for Block Ci1705.5 AES- The Advanced Encryption Standard1735.6 Differential and Linear Cryptanalysis- A Brief look1765.7 Stream Ciphers from Block ciphers177