Introduction to Modern Cryptography

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 graduatelevel courses in cryptography (in computer science or mathematics departments) as a general introduction suitable for selfstudy(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 bookand 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 headon, 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(post1980s) 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 glancemay appear impossible to achieve. One of the most amazing aspects of cryp tography is that (under mild and widelybelieved 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 widelybelieved(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 welldefined 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 overeInlphasized. Historically, cryptographic schemes were designed in a largely adhoc 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 welldefined models. Such schemes are guaranteed to be secure unless the underly ing assumption is false(or the security definition did not appropriately model the realworld security concerns). By relying on longstanding 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 widelyused 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 upperlevel 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 bigO 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 14(through Section 4.6), discussing classical cryptography, modcrn cryptography, and the basics of privatckcy cryptography (both privatekey encryption and message authentication) Chapter 7, introducing concrete mathematical problems believed to be hard, providing the numbertheoretic background needed to under stand RSA, DiffieHellman, and El Gamal, and giving a favor of how numbertheoretic assumptions are used in cryptography Chapters 9 and 10, motivating the publickey setting and discussing publickey encryption(including RSAbased schemes and El Gamal) Chapter 12, describing digital signature schemes Sections 13. 1 and 13.3, introducing the random oracle model and the RSAFDH signature scheme We believe that this core material possibly omitting some of the more indepth discussion and some proofs can be covered in a 3035hour 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 numbertheoretic background Alternately, additional topics could be incorporated as discussed next Those wishing to cover additional material, in either a longer course or a fasterpaced 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 skippedor 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 unstarred 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 theoreticallyinclined course could include material from Sections 4.8 and 4.9(dealing with stronger notions of security for privatekey encryption); Chapter 6(introducing oneway functions and hardcore bits, and constructing pseudorandom generators and pseu dorandom functions/permutations starting from any oneway permuta tion); Section 10.7(constructing publickey encryption from trapdoor permutations); Chapter 11(describing the GoldwasserMicali, 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(ellipticcurve groups ); Chapter 8(algorithms for factoring alld cOMputing discrete logarithMS); and Chapter 11(describ ing the GoldwasserMicali, Rabin, and Paillier encryption schemes along with all the necessary numbertheoretic 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 PrivatcKCy 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 PerfectlySecret Encryption 29 2.1 Dcfinitions and Basic Propertics 29 2.2 The OneTiine 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 PrivateKey(Symmetric) Cryptography 45 3 PrivateKey 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 ColnlputatiOmallySecure 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 FixedLength Encryption Scheme 72 3.4.2 Handling VariableLength Messages 75 3.4.3 Stream Ciphers and Multiple Encryptions 76 3.5 Security under ChosenPlaintext Attacks(CPA) 81 3.6 Constructing CPASecure Encryption Schemes 85 3.6.2 CPASecure 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 ChosenCiphertext Attacks(CCA 100 References and Additional reading 102 Exercises 4 Message Authentication Codes and CollisionResistant 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 CBCMAC 4.6 CollisionResistant 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 MerkleDamgard Transform 127 4.6.5 CollisionResistant 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 ChosenCiphertext 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 SubstitutionPermutation 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 ReducedRound 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
 8.67MB
Introduction to Modern Cryptography 2nd
20171025Introduction to Modern Cryptography 第二版 英文原版 代书签 高清PDF
 10.72MB
introduction to modern cryptography.pdf
20190628This book contains information obtained from authentic and highly regarded sources. Reasonable effor
 998KB
Modern Cryptography PDF课件
20160107详细介绍了现代加密方式，包括对称加密，非对称加密，数字签名，0知识验证，哈西函数生成方式等，在实际应用层加密实现中有着广泛的应用。
introduction to modern cryptography.pdf下载_course
20200705This book contains information obtained from authentic and highly regarded sources. Reasonable effor
 37.72MB
Introduction to Modern Cryptography.pdf
20170314《Introduction to Modern Cryptography.pdf》是《现代密码学——原理与协议》（任伟译）的英文版
 1.90MB
密码学介绍中文第二版（An Introduction to Cryptography）
20100128本书翻译原文来自美国PGP安全软件公司的产品PGP Desktop 9.9.0软件包中的Jon Callas在 2006年所著《An Introduction to Cryptography（Intr
 2.63MB
Introduction to Modern Cryptography  Jonathan Katz & Yehuda Lindell
20150305Introduction to Modern Cryptography  Jonathan Katz & Yehuda Lindell
 8.57MB
Introduction to Modern Cryptography 2ed  by Jonathan Katz and Yehuda Lindell
20151008Introduction to Modern Cryptography 2ed  by Jonathan Katz and Yehuda Lindell 第二版 清晰 非扫描版 需要的下载吧

学院
信息系统项目管理师通关教程第3阶段选择题2015下
信息系统项目管理师通关教程第3阶段选择题2015下

博客
dp与px相互转换
dp与px相互转换

下载
基于ZigBee技术的飞行保障工具管理系统
基于ZigBee技术的飞行保障工具管理系统

博客
day03 java中的运算符与键盘录入
day03 java中的运算符与键盘录入

学院
企业十大应用zabbix运维监控
企业十大应用zabbix运维监控

博客
【MyBatis01】MyBatis框架入门和简单使用
【MyBatis01】MyBatis框架入门和简单使用

学院
一学即懂的计算机视觉深度学习篇
一学即懂的计算机视觉深度学习篇

下载
射频功率放大器实时检测的实现
射频功率放大器实时检测的实现

下载
非接触式CPU卡的空中传输协议的软硬件设计
非接触式CPU卡的空中传输协议的软硬件设计

学院
Lucky带你玩转JQuery
Lucky带你玩转JQuery

博客
LeetCode39——组合总和（回溯法）
LeetCode39——组合总和（回溯法）

博客
Maven项目搭建
Maven项目搭建

博客
系列：多线程（一）Thread
系列：多线程（一）Thread

学院
从新手小白入门Qt编程(Windows 10)
从新手小白入门Qt编程(Windows 10)

博客
Python记录（一）数据结构之 列表结构
Python记录（一）数据结构之 列表结构

博客
程序的动态链接（3）：延迟绑定
程序的动态链接（3）：延迟绑定

博客
jsjsonp跨域
jsjsonp跨域

下载
STMP、POP3实现收发邮件
STMP、POP3实现收发邮件

博客
java 之 if的使用
java 之 if的使用

博客
Redis学习（十二）缓存穿透、击穿和雪崩
Redis学习（十二）缓存穿透、击穿和雪崩

博客
LeetCode187. 重复的DNA序列
LeetCode187. 重复的DNA序列

下载
NSObject源码.zip
NSObject源码.zip

博客
Python学习六：面向对象编程（上）
Python学习六：面向对象编程（上）

下载
红外线电视伴音转发器
红外线电视伴音转发器

学院
Linux运维与云计算实战指南2020版零起点基础篇
Linux运维与云计算实战指南2020版零起点基础篇

学院
KVM 开源虚拟化技术（为 Openstack安装奠定基础）
KVM 开源虚拟化技术（为 Openstack安装奠定基础）

下载
QXDM nv参数大全.docx
QXDM nv参数大全.docx

学院
第三章：YOLO系列目标检测
第三章：YOLO系列目标检测

下载
基于STM32和SIM900A的无线通信模块设计与实现
基于STM32和SIM900A的无线通信模块设计与实现

下载
sqlitetoolswin32x863320300.zip
sqlitetoolswin32x863320300.zip