Introduction to Cryptography: Principles and Applications (Information Security and Cryptography)

The first part of this book covers the key concepts of cryptography on an undergraduate level, from encryption and digital signatures to cryptographic protocols. Essential techniques are demonstrated in protocols for key exchange, user identification, electronic elections and digital cash. In the second part, more advanced topics are addressed, such as the bit security of one-way functions and computationally perfect pseudorandom bit generators. The security of cryptographic schemes is a central topic. Typical examples of provably secure encryption and signature schemes and their security proofs are given. Though particular attention is given to the mathematical foundations, no special background in mathematics is presumed. The necessary algebra, number theory and probability theory are included in the appendix. Each chapter closes with a collection of exercises. In the second edition the authors added a complete description of the AES, an extended section on cryptographic hash functions, and new sections on random oracle proofs and public-key encryption schemes that are provably secure against adaptively-chosen-ciphertext attacks. The third edition is a further substantive extension, with new topics added, including: elliptic curve cryptography; Paillier encryption; quantum cryptography; the new SHA-3 standard for cryptographic hash functions; a considerably extended section on electronic elections and Internet voting; mix nets; and zero-knowledge proofs of shuffles. The book is appropriate for undergraduate and graduate students in computer science, mathematics, and engineering. Preface to the Third, Extended Edition......Page 6 Preface to the Second, Extended Edition......Page 8 Preface......Page 10 Contents......Page 14 Notation......Page 20 Encryption and Secrecy......Page 22 The Objectives of Cryptography......Page 23 Attacks......Page 25 Cryptographic Protocols......Page 26 Provable Security......Page 27 Symmetric-Key Encryption......Page 32 Stream Ciphers......Page 33 Block Ciphers......Page 36 DES......Page 37 AES......Page 40 Modes of Operation......Page 46 Security Requirements for Hash Functions......Page 51 Construction of Hash Functions......Page 53 Data Integrity and Message Authentication......Page 63 Hash Functions as Random Functions......Page 65 The Concept of Public-Key Cryptography......Page 70 The Integers......Page 72 The Integers Modulo n......Page 74 Key Generation and Encryption......Page 79 Attacks Against RSA Encryption......Page 83 Probabilistic RSA Encryption......Page 88 Digital Signatures — The Basic Scheme......Page 91 Signatures with Hash Functions......Page 92 ElGamal Encryption......Page 98 ElGamal Signatures......Page 99 Digital Signature Algorithm......Page 101 ElGamal Encryption in a Prime-Order Subgroup......Page 103 Rabin's Encryption......Page 106 Rabin's Signature Scheme......Page 107 ElGamal Encryption......Page 108 Paillier Encryption......Page 109 Re-encryption of Ciphertexts......Page 110 Elliptic Curve Cryptography......Page 111 Selecting the Curve and the Base Point......Page 114 Diffie–Hellman Key Exchange......Page 119 ElGamal Encryption......Page 121 Elliptic Curve Digital Signature Algorithm......Page 123 Key Exchange and Entity Authentication......Page 128 Kerberos......Page 129 Diffie–Hellman Key Agreement......Page 132 Key Exchange and Mutual Authentication......Page 133 Station-to-Station Protocol......Page 135 Public-Key Management Techniques......Page 136 Interactive Proof Systems......Page 138 Simplified Fiat–Shamir Identification Scheme......Page 140 Zero-Knowledge......Page 142 Fiat–Shamir Identification Scheme......Page 144 Fiat–Shamir Signature Scheme......Page 146 Commitment Schemes......Page 147 A Commitment Scheme Based on Quadratic Residues......Page 148 A Commitment Scheme Based on Discrete Logarithms......Page 149 Homomorphic Commitments......Page 150 Secret Sharing......Page 151 Verifiable Electronic Elections......Page 154 A Multi-authority Election Scheme......Page 156 Proofs of Knowledge......Page 159 Non-interactive Proofs of Knowledge......Page 163 Extension to Multi-way Elections......Page 164 Eliminating the Trusted Center......Page 165 Mix Nets and Shuffles......Page 167 Decryption Mix Nets......Page 168 Re-encryption Mix Nets......Page 171 Proving Knowledge of the Plaintext......Page 174 Zero-Knowledge Proofs of Shuffles......Page 175 Receipt-Free and Coercion-Resistant Elections......Page 189 Receipt-Freeness by Randomized Re-encryption......Page 190 A Coercion-Resistant Protocol......Page 197 Digital Cash......Page 205 Blindly Issued Proofs......Page 207 A Fair Electronic Cash System......Page 213 Underlying Problems......Page 218 Coin-Tossing Algorithms......Page 224 Monte Carlo and Las Vegas Algorithms......Page 229 One-Way Functions and the Basic Assumptions......Page 236 A Notation for Probabilities......Page 237 Discrete Exponential Function......Page 238 Uniform Sampling Algorithms......Page 244 Modular Powers......Page 247 Modular Squaring......Page 250 Quadratic Residuosity Property......Page 251 Formal Definition of One-Way Functions......Page 252 Hard-Core Predicates......Page 256 Bit Security of the Exp Family......Page 264 Bit Security of the RSA Family......Page 271 Bit Security of the Square Family......Page 279 Computationally Perfect Pseudorandom Bit Generators......Page 288 Yao's Theorem......Page 296 Provably Secure Encryption......Page 304 Classical Information-Theoretic Security......Page 305 Perfect Secrecy and Probabilistic Attacks......Page 309 Public-Key One-Time Pads......Page 313 Passive Eavesdroppers......Page 315 Chosen-Ciphertext Attacks......Page 322 A Security Proof in the Random Oracle Model......Page 325 Security Under Standard Assumptions......Page 334 Unconditional Security of Cryptosystems......Page 342 The Bounded Storage Model......Page 343 The Noisy Channel Model......Page 353 Almost Universal Classes of Hash Functions......Page 354 Message Authentication with Universal Hash Families......Page 356 Authenticating Multiple Messages......Page 357 Collision Entropy and Privacy Amplification......Page 358 Rényi Entropy......Page 359 Privacy Amplification......Page 361 Extraction of a Secret Key......Page 362 Quantum Key Distribution......Page 364 Quantum Bits and Quantum Measurements......Page 365 The BB84 Protocol......Page 371 Estimation of the Error Rate......Page 374 Intercept-and-Resend Attacks......Page 375 Information Reconciliation......Page 383 Exchanging a Secure Key – An Example......Page 388 General Attacks and Security Proofs......Page 389 Attacks and Levels of Security......Page 394 Claw-Free Pairs and Collision-Resistant Hash Functions......Page 397 Authentication-Tree-Based Signatures......Page 400 A State-Free Signature Scheme......Page 402 The Integers......Page 418 Residues......Page 424 The Chinese Remainder Theorem......Page 428 Primitive Roots and the Discrete Logarithm......Page 430 The Ring of Polynomials......Page 434 Residue Class Rings......Page 436 Finite Fields......Page 438 Solving Quadratic Equations in Binary Fields......Page 440 Quadratic Residues......Page 442 Modular Square Roots......Page 447 The Group Zn2*......Page 451 Primes and Primality Tests......Page 453 Elliptic Curves......Page 458 Plane Curves......Page 459 Normal Forms of Elliptic Curves......Page 467 Point Addition on Elliptic Curves......Page 470 Group Order and Group Structure of Elliptic Curves......Page 476 Finite Probability Spaces and Random Variables......Page 480 Some Useful and Important Inequalities......Page 488 The Weak Law of Large Numbers......Page 491 Distance Measures......Page 493 Basic Concepts of Information Theory......Page 497 References......Page 504 Index......Page 522 Due to the rapid growth of digital communication and electronic data exchange, information security has become a crucial issue in industry, business, and administration. Modern cryptography provides essential techniques for securing information and protecting data. In the first part, this book covers the key concepts of cryptography on an undergraduate level, from encryption and digital signatures to cryptographic protocols. Essential techniques are demonstrated in protocols for key exchange, user identification, electronic elections and digital cash. In the second part, more advanced topics are addressed, such as the bit security of one-way functions and computationally perfect pseudorandom bit generators. The security of cryptographic schemes is a central topic. Typical examples of provably secure encryption and signature schemes and their security proofs are given. Though particular attention is given to the mathematical foundations, no special background in mathematics is presumed. The necessary algebra, number theory and probability theory are included in the appendix. Each chapter closes with a collection of exercises. The second edition contains corrections, revisions and new material, including a complete description of the AES, an extended section on cryptographic hash functions, a new section on random oracle proofs, and a new section on public-key encryption schemes that are provably secure against adaptively-chosen-ciphertext attacks.