Introduction to Modern Cryptography

所需积分/C币:23 2018-10-26 12:02:30 2.73MB PDF

Introduction to Modern Cryptography, Jonathan Katz and Yehuda Lindell, 2007
Preface This book presents the basic paradigms and principles of modern cryptogra- phy. It is designed to serve as a textbook for undergraduate- or graduate-level courses 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 practitioners There are numerous other cryptography textbooks available today, and the reader may rightly ask whether another book on the subject is needed. We would not have written this book if the answer to that question were anything other than al unequivocal yes. The novelty of this book-and what, in our opinion, distinguishes it from a l other books currently on the market- is that it provides a rigorous treatment of modern cryptography in an accessible manner appropriate for an introduction to the topic. To be sure the material in this book is difficult (at least in comparison to some other books in this area). Rather than shy away from this difficulty, however, we have chosen to face it head-on, to lead the reader through the demanding(yet enthralling subject matter rather than shield the readers eyes frOIn it. We hope readers (and instructors)will respond by taking up the challenge S mentioned, our focus is on modern(post-1980s) cryptography, which is distinguished froIn classical cryptography by its emphasis on definitiOn precise assumptions, and rigorous proofs of security. We briefy discuss each of these in turn(these principles are explored in greater detail in Chapter 1) The ccntral rolc of dcfinitions: A kcy intellectual contribution of modern cryptography has been the recognition that formal definitions of security are an essential first step in the design of any cryptographic primitive or protocol. The reason, in retrospect, is simple: if you dont know what it is you are trying to achieve, how can you hope to know when you have achieved it? As we will see in this book, cryptographic definitions of security are quite strong and- at first glance-may appear impossible to achieve. One of the most amazing aspects of cryp tography is that (under mild and widely-believed assumptions)efficient constructions satisfying such strong definitions can be proven to exist The importance of formal and precise assumptions: As will be explained in Chapter 2, many cryptographic constructions cannot currently be proven secure in an unconditional sense. Security often relies, instead, on some widely-believed(albeit unproven) assumption The modern cryptographic approach dictates that any such assumption must be clearly and unambi defined. This not only allows for ob jective evaluation of the assumption, but, more importantly, enables rigorous proofs of security as described next The possibility of rigorous proofs of security: The previous two ideas 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 responsible for the transformation of cryptography from an art to a science The iInportance of this idea cannot be over-eInlphasized. Historically, cryptographic schemes were designed in a largely ad-hoc fashion, and were deemed to be secure if the designers themselves could not find any attacks. In contrast, modern cryptography promotes the design of schemes with forma. l, mat, hema. tical proofs of securitv in well-defined models. Such schemes are guaranteed to be secure unless the underly ing assumption is false(or the security definition did not appropriately model the real-world security concerns). By relying on long-standing assumptions(e. g, the assumption that "factoring is hard"), it is thus possiblc to obtain schemas that arc extrcmcly unlikely to bc broken A unified approach. The above contributions of modern cryptography are felt not only within the"theory of cryptography"community. The importance of precise definitions is, by now, widely understood and appreciated by those in the security community(as well as those who use cryptographic tools to build secure systems), and rigorous proofs of security have become one of the requirements for cryptographic schemes to be standardized. As such, we do not scparatc“ applicd cryptography”from“ provable sccurity”; rather,wo present practical and widely-used constructions along with precise statements (and, most, of the time, a proof) of what definition of security is achieved Guide to Using this Book This guide is intended primarily for instructors seeking to adopt this book for their course, though the student picking up this book on his or her own may also find it useful Required background. This book uses definitions, proofs, and mathemat- ical concepts, and therefore requires some Mathematical Imaturity. II pal ticular, the reader is assumed to have had some exposure to proofs at the college level, say in an upper-level mathematics course or a course on discrete mathematics, algorithms, or computability theory. Ilaving said this, we have made a significant effort to simplify the presentation and make it generally accessible. It is our belief that this book is not more difficult than analogous textbooks that are less rigorous. On the contrary, we believe that(to take one example) once security goals are clearly formulated, it often becomes easier to understand the design choices made in a particular construction We have structured the book so that the only formal prerequisites are a course in algorithms and a course in discrete mathematics. Even here we rely on very little Inaterial: specilically, we assune soine familiarity with basic probability and big-O notation, modular arithmetic, and the idea of equating cfficicnt algorithms with thosc running in polynomial timc. Thesc concepts are reviewed in Appendix A and/or when first used in the book Suggestions for course organization. The core material of this book. which we strongly recommend should be covered in any introductory course on cryptography, consists of the following (starred sections are excluded in what 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 (both private-key encryption and message authentication) Chapter 7, introducing concrete mathematical problems believed to be hard, providing the number-theoretic background needed to under- stand RSA, Diffie-Hellman, and El Gamal, and giving a favor of how number-theoretic assumptions are used in cryptography Chapters 9 and 10, motivating the public-key setting and discussing public-key encryption(including RSA-based schemes and El Gamal) Chapter 12, describing digital signature schemes Sections 13. 1 and 13.3, introducing the random oracle model and the RSA-FDH signature scheme We believe that this core material- possibly omitting some of the more in-depth discussion and some proofs- can be covered in a 30-35-hour under graduate course. Instructors with more time available could proceed at a more leisurely pace, e.g, giving details of all proofs and going more slowly when introducing the underlying group theory and number-theoretic background Alternately, additional topics could be incorporated as discussed next Those wishing to cover additional material, in either a longer course or a faster-paced graduate course, will find that the book has been structured to allow flexible incorporation of other topics as time permits(and depending on the iustructor's interests). Specifically, sOinle of the chapters and sections are starred(). These sections are not less important in any way, but arguably do not constitute "core material"for an introductory course in cryptograp As made evident by the course outline just given(which does not include any starred material), starred chapters and sections may be skipped-or covered at any point subsequent to their appearance in the book- without affecting he How of the course. In particular, we have taken care to ensure that none of the later un-starred material depends on any starred material. For the most part, the starred chapters also do not depend on each other (and in the rare cases when they do, this dependence is explicitly noted) We suggest the following from among the starred topics for those wishing to give their course a particular fla Theorg: A more theoretically-inclined course could include material from Sections 4.8 and 4.9(dealing with stronger notions of security for private-key encryption); Chapter 6(introducing one-way functions and hard-core bits, and constructing pseudorandom generators and pseu dorandom functions/permutations starting from any one-way permuta- tion); Section 10.7(constructing public-key encryption from trapdoor permutations); Chapter 11(describing the Goldwasser-Micali, Rabin and Paillier encryption schemes): and Section 12.6 (showing a signature scheme that does not rely on random oracles) Application.s: An inst ructor wanting to emphasize practica. I aspects of cryptography is highly encouraged to cover Section 4.7(describing HMAC); Chapter 5(discussing modern block ciphers and techniques used in their design); and all of Chapter 13(giving cryptographic con structions in the random oracle model) Mathematics: A course directed at students with a strong mathematics background - or taught by someone who enjoys this aspect of cryp- tography- could incorporate material from Chapter 5(see above)as well as Section 7.3. 4(elliptic-curve groups ); Chapter 8(algorithms for factoring alld cOMputing discrete logarithMS); and Chapter 11(describ ing the Goldwasser-Micali, Rabin, and Paillier encryption schemes along with all the necessary number-theoretic background) Comments and errata Our goal in writing this book was to make modern cryptography accessible to a wide audience outside the"theoretical computer science"community. We hope you will let us know whether we have succeeded. In particular, we are always 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 are no errors or typos in the book; if you do find any, however, we would greatly appreciate it if you let us know.(A list of known errata will be maintained athttp://www.cs.umd.Edu/jkatz/imc.html.)Youcanemailyourcom- ments and errata to jkatz@cs umd. edu and lindell@cs. biu ac il; please put "Introduction to Modern Cryptography" in the subject line Acknowledgements Jonathan Katz is deeply indebted to Zvi Galil, Moti Yung, and Rafail o trovsky for their help, guidance, and support throughout his career. This book would never have come to be without their contributions to his development and he thanks them for that. He would also like to thank his colleagues with whom he has had numerous discussions on the "right approach to writing a cryptography textbook and in particular Victor Shoup Yehuda lindell wishes to first and foremost thank oded Goldreich and moili Naor for introducing him to the world of cryptography. Their influence is felt until today and will undoubtedly continue to be felt in the future. There are many, many other people who have also had considerable influence over the years and instead of mentioning them all, he will just say thank you- you now who you are. Both authors would like to extend their gratitude to those who read and commented on earlier drafts of this book. We thank Salil Vadhan and alon Rosen who experimented with this text in an introductory course on cryp tography at Harvard and provided us with valuable fccdback. Wc also thank all of the following for their many comments and corrections: Adam bender Yair Dombb, William Glenn, s. Dov Gordon, Ca.. Hazay, Avivit. Levy Matthew Mah. Jason Rogers, Rui Xue, Dicky Yan, and Hila zarosim. We are very grateful to all those who encouraged us to write this book and concurred with our feeling that a book of this nature is badly needed Finally, we thank our (respective wives and children for all their support and understanding during the many hours, days, and months that we have spent On this project Contents Preface I Introduction and Classical Cryptograph 1 Introduction and Classical Ciphers 1.2 The Sctting of Privatc-KCy Encryptio 1.1 Cryptography and Modern Cryptograph i13349 1.3 Historical Ciphers alld Their Cryptalladlysis 1.4 The Basic Principles of Modern Cryptography 1.4.1 Principle 1 Formulation of Exact Definitions 18 1.4.2 Principle 2- Reliance on Precise Assumptions 24 1.4.3 Principle 3- Rigorous Proofs of Security Rcfcrcnces and Additional reading Exercises 2 Perfectly-Secret Encryption 29 2.1 Dcfinitions and Basic Propertics 29 2.2 The One-Tiine Pad(Verlalnl's Cipher) 34 2.3 Limitations of Perfect Secrecy 37 2.4 Shannon's Theorem 2.5 Summary References and Additional Reading 41 Exercises II Private-Key(Symmetric) Cryptography 45 3 Private-Key Encryption and Pseudorandomness 47 3.1 A Computational Approach to Cryptography 3. 1.1 The Basic Idea of CoInlputatiollal Security 3.1.2 Efficient Algorithms and Negligible Success 54 3.1.3 Proofs by rcduction 3.2 A Definition of ColnlputatiOmally-Secure EllcryptiOI 59 3.2.1 A Definition of Security for Encryption 60 3.2.2 Properties of the Definition 64 3.3 Pseudorandomness 3.4 Constructing Secure Encryption Schemes 72 3.4.1 A Secure Fixed-Length Encryption Scheme 72 3.4.2 Handling Variable-Length Messages 75 3.4.3 Stream Ciphers and Multiple Encryptions 76 3.5 Security under Chosen-Plaintext Attacks(CPA) 81 3.6 Constructing CPA-Secure Encryption Schemes 85 3.6.2 CPA-Secure Encryption Schemes from Pseudorandom ds 3.6.1 Pseudorandom functions unctions 3.6.3 PseudoraldoIn Permutations anld Block Ciphers 3.6.4 Modes of Operation 3.7 Security Against Chosen-Ciphertext Attacks(CCA 100 References and Additional reading 102 Exercises 4 Message Authentication Codes and Collision-Resistant Hash Functions 107 4.1 Secure Communication and Message Integrity 107 4.2 Encryption and Message Authentication 108 4.3 Message Authentication Codes Definitions 10 4.4 Constructing Secure Message Authentication Codes 113 4.5 CBC-MAC 4.6 Collision-Resistant Hash Functions 121 4.6.1 Defining Collision Resistance 122 4.6.2 Weaker Notions of security for hash Functions 124 4.6.3 A Generic“ Birthday” Attack. 125 4.6.4 The Merkle-Damgard Transform 127 4.6.5 Collision-Resistant Hash Functions in Practice 129 4.7 NMAC and HMac 132 4.7.1 Nested MAC(NMAC) 132 4.7.2 HMAC 135 4. 8 x Achieving Chosen-Ciphertext Secure Encryption 137 4.9 Obta Privacy and m Authenticate 141 References and Additional reading ⅹ excises 5 Pseudorandom objects in Practice: Block Ciphers 151 5.1 Substitution-Permutation Networks 154 5.2 Feistel networks 160 5. 3 DES- The Data Encryption Standard 162 5.3.1 The Design of DES 5.3.2 Attacks on Reduced-Round Variants of DEo 162 165 5.3. 3 The Security of DEs 168 4 Increasing the Key Size for Block Ci 170 5.5 AES- The Advanced Encryption Standard 173 5.6 Differential and Linear Cryptanalysis- A Brief look 176 5.7 Stream Ciphers from Block ciphers 177


关注 私信 TA的资源