Introduction To Modern Cryptography, Second Edition
Computer Science/MathematicsCryptography is ubiquitous and plays a key role in ensuring data secrecy andintegrity as well as in securing computer systems more broadly. Introductionto Modern Cryptography provides a rigorous yet accessible treatment of thisfascinating subject.Integrating a more practical perspective without sacrificing rigor, this widelyanticipated Second Edition offers improved treatment of Containing updated exercises and worked examples, Introduction to ModernCryptography, Second Edition can serve as a textbook for undergraduate- orgraduate-level courses in cryptography, a valuable reference for researchersand practitioners, or a general introduction suitable for self-study.MODERNCRYPTOGRAPHYSecond EditionJonathan KatzYehuda LindellKatzLindellStream ciphers and block ciphers, including modes of operation anddesign principlesAuthenticated encryption and secure communication sessionsHash functions, including hash-function applications and designprinciplesAttacks on poorly implemented cryptography, including attacks onchained-CBC encryption, padding-oracle attacks, and timing attacksThe random-oracle model and its application to several standardized,widely used public-key encryption and signature schemesElliptic-curve cryptography and associated standards such as DSA/ECDSA and DHIES/ECIESINTRODUCTION TOINTRODUCTION TOMODERN CRYPTOGRAPHYThe authors introduce the core principles of modern cryptography, with anemphasis on formal definitions, clear assumptions, and rigorous proofs of security. The book begins by focusing on private-key cryptography, including anextensive treatment of private-key encryption, message authentication codes,and hash functions. The authors also present design principles for widely usedstream ciphers and block ciphers including RC4, DES, and AES, plus they provide provable constructions of stream ciphers and block ciphers from lowerlevel primitives. The second half of the book covers public-key cryptography,beginning with a self-contained introduction to the number theory needed tounderstand 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.SecondEditionChapman & Hall/CRCCRYPTOGRAPHY AND NETWORK SECURITYK16475w w w. c rc p r e s s . c o mK16475 cover.indd 110/3/14 9:48 AM
INTRODUCTION TOMODERNCRYPTOGRAPHYSecond EditionK16475 FM.indd 19/24/14 1:27 PM
CHAPMAN & HALL/CRCCRYPTOGRAPHY AND NETWORK SECURITYSeries EditorDouglas R. StinsonPublished TitlesLidong Chen and Guang Gong, Communication System SecurityShiu-Kai Chin and Susan Older, Access Control, Security, and Trust:A Logical ApproachM. Jason Hinek, Cryptanalysis of RSA and Its VariantsAntoine Joux, Algorithmic CryptanalysisJonathan Katz and Yehuda Lindell, Introduction to ModernCryptography, Second EditionSankar K. Pal, Alfredo Petrosino, and Lucia Maddalena, Handbook onSoft Computing for Video SurveillanceBurton Rosenberg, Handbook of Financial Cryptography and SecurityForthcoming TitlesMaria Isabel Vasco, Spyros Magliveras, and Rainer Steinwandt,Group Theoretic CryptographyK16475 FM.indd 29/24/14 1:27 PM
Chapman & Hall/CRCCRYPTOGRAPHY AND NETWORK SECURITYINTRODUCTION TOMODERNCRYPTOGRAPHYSecond EditionJonathan KatzUniversity of MarylandCollege Park, MD, USAYehuda LindellBar-Ilan UniversityRamat Gan, IsraelK16475 FM.indd 39/24/14 1:27 PM
CRC PressTaylor & Francis Group6000 Broken Sound Parkway NW, Suite 300Boca Raton, FL 33487-2742 2015 by Taylor & Francis Group, LLCCRC Press is an imprint of Taylor & Francis Group, an Informa businessNo claim to original U.S. Government worksVersion Date: 20140915International Standard Book Number-13: 978-1-4665-7027-6 (eBook - PDF)This book contains information obtained from authentic and highly regarded sources. Reasonableefforts have been made to publish reliable data and information, but the author and publisher cannotassume responsibility for the validity of all materials or the consequences of their use. The authors andpublishers have attempted to trace the copyright holders of all material reproduced in this publicationand apologize to copyright holders if permission to publish in this form has not been obtained. If anycopyright material has not been acknowledged please write and let us know so we may rectify in anyfuture reprint.Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced,transmitted, or utilized in any form by any electronic, mechanical, or other means, now known orhereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and areused only for identification and explanation without intent to infringe.Visit the Taylor & Francis Web site athttp://www.taylorandfrancis.comand the CRC Press Web site athttp://www.crcpress.com
ContentsPrefaceIxvIntroduction and Classical Cryptography1 Introduction1.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 SecurityReferences and Additional Reading . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . .3348161720222223242 Perfectly Secret Encryption2.1 Definitions . . . . . . . . . .2.2 The One-Time Pad . . . . .2.3 Limitations of Perfect Secrecy2.4 *Shannon’s Theorem . . . .References and Additional ReadingExercises . . . . . . . . . . . . . .252632353637383 Private-Key Encryption3.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 Ciphers3.3.2 Proofs by Reduction . . . . . . . . . . . . . . .3.3.3 A Secure Fixed-Length Encryption Scheme . .4343444552535660606566II. . . . . . . . . . .Private-Key (Symmetric) Cryptographyvii
viii3.4Stronger Security Notions . . . . . . . . . . . . . . . . . . . .713.4.1 Security for Multiple Encryptions . . . . . . . . . . . .713.4.2 Chosen-Plaintext Attacks and CPA-Security . . . . . .733.5 Constructing CPA-Secure Encryption Schemes . . . . . . . .773.5.1 Pseudorandom Functions and Block Ciphers . . . . .773.5.2 CPA-Secure Encryption from Pseudorandom Functions 823.6 Modes of Operation . . . . . . . . . . . . . . . . . . . . . . .863.6.1 Stream-Cipher Modes of Operation . . . . . . . . . . .863.6.2 Block-Cipher Modes of Operation . . . . . . . . . . .883.7 Chosen-Ciphertext Attacks . . . . . . . . . . . . . . . . . . .963.7.1 Defining CCA-Security . . . . . . . . . . . . . . . . . .963.7.2 Padding-Oracle Attacks . . . . . . . . . . . . . . . . .98References and Additional Reading . . . . . . . . . . . . . . . . . 101Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024 Message Authentication Codes4.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 Codes4.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 MACsReferences and Additional Reading . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 421431451461475 Hash Functions and Applications5.1 Definitions . . . . . . . . . . . . . . . . . . . . . . .5.1.1 Collision Resistance . . . . . . . . . . . . . .5.1.2 Weaker Notions of Security . . . . . . . . . .5.2 Domain Extension: The Merkle–Damgård Transform5.3 Message Authentication Using Hash Functions . . .5.3.1 Hash-and-MAC . . . . . . . . . . . . . . . . .5.3.2 HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153153154156156158159161.
ix5.4Generic 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 Functions5.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . .1641641661681741751791821821831841861871891896 Practical Constructions of Symmetric-Key Primitives6.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 Cipher6.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342352362377 *Theoretical Constructions of Symmetric-Key Primitives7.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 . . . . . . . . . . . . . . . . . . . . . .241242242245246248250250
x7.3.2 A More Involved Case . . . . . . . . . . . . . . . . .7.3.3 The Full Proof . . . . . . . . . . . . . . . . . . . . .7.4 Constructing Pseudorandom Generators . . . . . . . . . . .7.4.1 Pseudorandom Generators with Minimal Expansion7.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.251254257258259265269273276278279Public-Key (Asymmetric) Cryptography8 Number Theory and Cryptographic Hardness Assumptions8.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 Assumptions8.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223253323323353373389 *Algorithms for Factoring and Computing Discreterithms9.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 . . . .341342343344345348Loga.
xi9.2.1 The Pohlig–Hellman Algorithm . . . .9.2.2 The Baby-Step/Giant-Step Algorithm9.2.3 Discrete Logarithms from Collisions .9.2.4 The Index Calculus Algorithm . . . .9.3 Recommended Key Lengths . . . . . . . . .References and Additional Reading . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . .35035235335435635735810 Key Management and the Public-Key Revolution10.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 . . . . . . . . . . . . . . . . . . . . . . . . . . .35935936136337037237311 Public-Key Encryption11.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 Model11.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 Model11.5.6 RSA Implementation Issues and Pitfalls . . . . . . .References and Additional Reading . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1541742142542943243312 Digital Signature Schemes12.1 Digital Signatures – An Overview . .12.2 Definitions . . . . . . . . . . . . . . .12.3 The Hash-and-Sign Paradigm . . . . .12.4 RSA Signatures . . . . . . . . . . . .439439441443444.
xii12.4.1 Plain RSA . . . . . . . . . . . . . . . . .12.4.2 RSA-FDH and PKCS #1 v2.1 . . . . . .12.5 Signatures from the Discrete-Logarithm Problem12.5.1 The Schnorr Signature Scheme . . . . . .12.5.2 DSA and ECDSA . . . . . . . . . . . . .12.6 *Signatures from Hash Functions . . . . . . . .12.6.1 Lamport’s Signature Scheme . . . . . . .12.6.2 Chain-Based Signatures . . . . . . . . . .12.6.3 Tree-Based Signatures . . . . . . . . . . .12.7 *Certificates and Public-Key Infrastructures . .12.8 Putting It All Together – SSL/TLS . . . . . . .12.9 *Signcryption . . . . . . . . . . . . . . . . . . .References and Additional Reading . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . .44444645145145946146146546847347948148348413 *Advanced Topics in Public-Key Encryption13.1 Public-Key Encryption from Trapdoor Permutations . . . .13.1.1 Trapdoor Permutations . . . . . . . . . . . . . . . .13.1.2 Public-Key Encryption from Trapdoor Permutations13.2 The Paillier Encryption Scheme . . . . . . . . . . . . . . .13.2.1 The Structure of Z N 2 . . . . . . . . . . . . . . . . .13.2.2 The Paillier Encryption Scheme . . . . . . . . . . . .13.2.3 Homomorphic Encryption . . . . . . . . . . . . . . .13.3 Secret Sharing and Threshold Encryption . . . . . . . . . .13.3.1 Secret Sharing . . . . . . . . . . . . . . . . . . . . .13.3.2 Verifiable Secret Sharing . . . . . . . . . . . . . . . .13.3.3 Threshold Encryption and Electronic Voting . . . .13.4 The Goldwasser–Micali Encryption Scheme . . . . . . . . .13.4.1 Quadratic Residues Modulo a Prime . . . . . . . . .13.4.2 Quadratic Residues Modulo a Composite . . . . . .13.4.3 The Quadratic Residuosity Assumption . . . . . . .13.4.4 The Goldwasser–Micali Encryption Scheme . . . . .13.5 The Rabin Encryption Scheme . . . . . . . . . . . . . . . .13.5.1 Computing Modular Square Roots . . . . . . . . . .13.5.2 A Trapdoor Permutation Based on Factoring . . . .13.5.3 The Rabin Encryption Scheme . . . . . . . . . . . .References and Additional Reading . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15518518523527528529Index of Common Notation.533
xiiiAppendix A Mathematical BackgroundA.1 Identities and Inequalities . . . . . .A.2 Asymptotic Notation . . . . . . . .A.3 Basic Probability . . . . . . . . . .A.4 The “Birthday” Problem . . . . . .A.5 *Finite Fields . . . . . . . . . . . .537537537538542544Appendix B Basic Algorithmic Number TheoryB.1 Integer Arithmetic . . . . . . . . . . . . . . . . . . . . . . .B.1.1 Basic Operations . . . . . . . . . . . . . . . . . . . .B.1.2 The Euclidean and Extended Euclidean AlgorithmsB.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . .B.2.1 Basic Operations . . . . . . . . . . . . . . . . . . . .B.2.2 Computing Modular Inverses . . . . . . . . . . . . .B.2.3 Modular Exponentiation . . . . . . . . . . . . . . . .B.2.4 *Montgomery Multiplication . . . . . . . . . . . . .B.2.5 Choosing a Uniform Group Element . . . . . . . . .B.3 *Finding a Generator of a Cyclic Group . . . . . . . . . . .B.3.1 Group-Theoretic Background . . . . . . . . . . . . .B.3.2 Efficient Algorithms . . . . . . . . . . . . . . . . . .References and Additional Reading . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . erences563Index577
PrefaceThe goal of our book remains the same as in the first edition: to present thebasic paradigms and principles of modern cryptography to a general audiencewith a basic mathematics background. We have designed this book to serve asa textbook for undergraduate- or graduate-level courses in cryptography (incomputer science, electrical engineering, or mathematics departments), as ageneral introduction suitable for self-study (especially for beginning graduatestudents), and as a reference for students, researchers, and practitioners.There 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—nor worked on revising it for the secondedition—if the answer to that question were anything other than an unequivocal yes. What, in our opinion, distinguishes our book from other availablebooks is that it provides a rigorous treatment of modern cryptography in anaccessible manner appropriate for an introduction to the topic.Our focus is on modern (post-1980s) cryptography, which is distinguishedfrom classical cryptography by its emphasis on definitions, precise assumptions, and rigorous proofs of security. We briefly discuss each of these in turn(these principles are explored in greater detail in Chapter 1): The central role of definitions: A key 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 don’tknow 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—may appearimpossible to achieve. One of the most amazing aspects of cryptographyis that efficient constructions satisfying such strong definitions can beproven to exist (under rather mild assumptions). The importance of precise assumptions: As will be explained inChapters 2 and 3, many cryptographic constructions cannot currentlybe proven secure in an unconditional sense. Security often relies, instead, on some widely believed (though unproven) assumption(s). Themodern cryptographic approach dictates that any such assumption mustbe clearly stated and unambiguously defined. This not only allows forobjective evaluation of the assumption but, more importantly, enablesrigorous proofs of security as described next.xv
xvi The possibility of proofs of security: The previous two principlesserve as the basis for the idea that cryptographic constructions can beproven secure with respect to clearly stated definitions of security andrelative to well-defined cryptographic assumptions. This concept is theessence of modern cryptography, and is what has transformed the fieldfrom an art to a science.The importance of this idea cannot be overemphasized. 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 advocates the designof schemes with formal, mathematical proofs of security 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 thuspossible to obtain schemes that are extremely unlikely to be broken.A unified approach. The above principles of modern cryptography are relevant not only to the “theory of cryptography” community. The importanceof precise definitions is, by now, widely understood and appreciated by developers and security engineers who use cryptographic tools to build securesystems, and rigorous proofs of security have become one of the requirementsfor cryptographic schemes to be standardized.Changes in the Second EditionIn preparing the second edition, we have made a conscious effort to integratea more practical perspective (without sacrificing a rigorous approach). Thisis reflected in a number of changes and additions we have made: We have increased our coverage of stream ciphers, introducing themas a variant of pseudorandom generators in Section 3.3.1, discussingstream-cipher modes of operation in Section 3.6.1, and describing modern stream-cipher design principles and examples in Section 6.1. We have emphasized the importance of authenticated encryption (seeSection 4.5) and have added a section on secure communication sessions. We have moved our treatment of hash functions into its own chapter(Chapter 5), have included some standard applications of cryptographichash functions (Section 5.6), and have added a section on hash-functiondesign principles and widely used constructions (Section 6.3). We havealso improved our treatment of birthday attacks (covering small-spacebirthday attacks in Section 5.4.2) and have added a discussion of rainbowtables and time/space tradeoffs (Section 5.4.3).
xvii We have included several important attacks on implementations of cryptography that arise in practice, including chosen-plaintext attacks onchained-CBC encryption (Section 3.6.2), padding-oracle attacks on CBCmode encryption (Section 3.7.2), and timing attacks on MAC verification (Section 4.2). After much deliberation, we have decided to introduce the randomoracle model much earlier in the book (Section 5.5). This allows us togive a proper, integrated treatment of standardized, widely used publickey encryption and signature schemes in later chapters, instead of relegating them to second-class status in a chapter at the end of the book. We have strengthened our coverage of elliptic-curve cryptography (Section 8.3.4) and have added a discussion of its impact on recommendedkey lengths (Section 9.3). In the chapter on public-key encryption, we introduce the KEM/DEMparadigm as a form of hybrid encryption (see Section 11.3). We alsocover DHIES/ECIES in addition to the RSA PKCS #1 standards. In the chapter on digital signatures, we now describe the construction ofsignatures from identification schemes using the Fiat–Shamir transform,with the Schnorr signature scheme as a prototypical example. We havealso improved our coverage of DSA/ECDSA. We include brief discussions of SSL/TLS and signcryption, both of which serve as culminationsof everything covered up to that point. In the “advanced topics” chapter, we have amplified our treatment ofhomomorphic encryption, and have included sections on secret sharingand threshold encryption.Beyond the above, we have also edited the entire book to make extensivecorrections as well as smaller adjustments, including more worked examples,to improve the exposition. Several additional exercises have also been added.Guide to Using This BookThis section 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 a useful overview.Required background. We have structured the book so that the only formalprerequisite is a course on discrete mathematics. Even here we rely on verylittle material: we assume familiarity with basic (discrete) probability andmodular arithmetic. Students reading this book are also expected to have hadsome exposure to algorithms, mainly to be comfortable reading pseudocodeand to be familiar with big-O notation. Many of these concepts are reviewedin Appendix A and/or when first used in the book.
xviiiNotwithstanding the above, the book does use definitions, proofs, and abstract mathematical concepts, and therefore requires some mathematical maturity. In particular, the reader is assumed to have had some exposure toproofs at the college level, whether in an upper-level mathematics course or acourse on discrete mathematics, algorithms, or computability theory.Suggestions for course organization. The core material of this book,which we recommend should be covered in any introductory course on cryptography, consists of the following (in all cases, starred sections are excluded;more on this below): Introduction and Classical Cryptography: Chapters 1 and 2 discuss classical cryptography and set the stage for modern cryptography. Private-Key (Symmetric) Cryptography: Chapter 3 on private-key encryption, Chapter 4 on message authentication, and Chapter 5
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 intr
of public-key cryptography; providing hands-on experience with some of the most common encryption algorithms that are used on the internet today. Modern Cryptography Introduction Outline 1 Introduction 2 Historical Cryptography Caesar Cipher 3 Public{Key Cryptography
Cryptography with DNA binary strands and so on. In terms of DNA algorithms, there are such results as A DNA-based, bimolecular cryptography design, Public-key system using DNA as a one-way function for key distribution, DNASC cryptography system and so on. However, DNA cryptography is an
Cryptography and Java Java provides cryptographic functionality using two APIs: JCA - Java Cryptography Architecture - security framework integrated with the core Java API JCE - Java Cryptography Extension - Extensions for strong encryption (exported after 2000 US export policy)
Cryptography in Java The Java Cryptography Architecture (JCA) is a set of APIs to implement concepts of modern cryptography such as digital signatures, message digests, certificates, encryption, key generation and management, and secure random number generation, etc. Using JCA, developers c
The Basics of Cryptography 12 An Introduction to Cryptography While cryptography is the science of securing data, cryptanalysisis the science of analyzing and breaking secure communication. Classical cryptanalysis involves an intere
sensitive information. Even though both cryptography and steganography has its own advantages and disadvantages, we can combine both the techniques together. This paper presents a comparative study of both cryptography and steganography. KEYWORDS: Cryptography, Steganography, Encryptio
integrating together cryptography and Steganography through image processing. In particular, we present a system able to perform Steganography and cryptography at the same time. In this paper, both Cryptography and Steganography methods are used for data security over the network. IRIS i
American Revolution in Europe working to negotiate assistance from France, Spain, and the Netherlands. Foreign Assistance French ultimately provided critical military and financial assistance Spain and the Netherlands provided primarily financial assistance to the American cause. A comparison of the resources held by the British and by the colonies: The population of the thirteen colonies .
