Lecture Notes on Cryptography - University of California ...

1 Lecture Notes on Cryptography Shafi Goldwasser1 Mihir Bellare2. July 2008. 1. MIT Computer Science and Artificial Intelligence Laboratory, The Stata Center, Building 32, 32 Vassar Street, Cambridge, MA 02139, USA. E-mail: ; Web page: shafi 2. Department of Computer Science and Engineering, Mail Code 0404, University of California at San Diego, 9500 Gilman Drive, La Jolla, CA 92093, USA. E-mail: ; Web page: Foreword This is a set of Lecture Notes on Cryptography compiled for , a one week long course on Cryptography taught at MIT by Shafi Goldwasser and Mihir Bellare in the summers of 1996 2002, 2004, 2005 and 2008. Cryptography is of course a vast subject. The thread followed by these Notes is to develop and explain the notion of provable security and its usage for the design of secure protocols. Much of the material in Chapters 2, 3 and 7 is a result of scribe Notes , originally taken by MIT graduate students who attended Professor Goldwasser's Cryptography and Cryptanalysis course over the years, and later edited by Frank D'Ippolito who was a teaching assistant for the course in 1991.

2 Frank also contributed much of the advanced number theoretic material in the Appendix. Some of the material in Chapter 3 is from the chapter on Cryptography , by R. Rivest, in the Handbook of Theoretical Computer Science. Chapters 4, 5, 6, 8, 9 and 11, and Sections and , are from the Introduction to Modern Cryptography Notes by Bellare and Rogaway [23], and we thank Phillip Rogaway for permission to include this material. Rosario Gennaro (as Teaching Assistant for the course in 1996) contributed Section , Section , Section , and Appendix D. to the Notes , and also compiled, from various sources, some of the problems in Appendix E. All rights reserved. Shafi Goldwasser and Mihir Bellare Cambridge, Massachusetts, July 2008. 2. Table of Contents 1 Introduction to Modern Cryptography 11. Encryption: Historical Glance .. 11. Modern Encryption: A Computational Complexity Based Theory .. 12. A Short List of Candidate One Way Functions .. 13. Security Definitions.

3 14. The Model of Adversary .. 15. Road map to Encryption .. 15. 2 One-way and trapdoor functions 16. One-Way Functions: Motivation .. 16. One-Way Functions: Definitions .. 17. (Strong) One Way Functions .. 17. Weak One-Way Functions .. 18. Non-Uniform One-Way Functions .. 19. Collections Of One Way Functions .. 20. Trapdoor Functions and Collections .. 21. In Search of Examples .. 22. The Discrete Logarithm Function .. 23. The RSA function .. 26. Connection Between The Factorization Problem And Inverting RSA .. 28. The Squaring Trapdoor Function Candidate by Rabin .. 29. A Squaring Permutation as Hard to Invert as Factoring .. 32. Hard-core Predicate of a One Way Function .. 33. Hard Core Predicates for General One-Way Functions .. 34. Bit Security Of The Discrete Logarithm Function .. 35. Bit Security of RSA and SQUARING functions .. 36. One-Way and Trapdoor Predicates .. 36. Examples of Sets of Trapdoor Predicates .. 37. 3 Pseudo-random bit generators 39.

4 Generating Truly Random bit Sequences .. 39. Generating Pseudo-Random Bit or Number Sequences .. 40. 3. 4 Goldwasser and Bellare Provably Secure Pseudo-Random Generators: Brief overview .. 41. Definitions .. 41. The Existence Of A Pseudo-Random Generator .. 42. Next Bit Tests .. 45. Examples of Pseudo-Random Generators .. 47. Blum/Blum/Shub Pseudo-Random Generator .. 47. 4 Block ciphers 48. What is a block cipher? .. 48. Data Encryption Standard (DES) .. 49. A brief history .. 49. Construction .. 49. Speed .. 51. Key recovery attacks on block ciphers .. 52. Iterated-DES and DESX .. 55. Double-DES .. 55. Triple-DES .. 56. DESX .. 57. Why a new cipher? .. 57. Advanced Encryption Standard (AES) .. 57. Limitations of key-recovery based security .. 61. Problems .. 61. 5 Pseudo-random functions 63. Function families .. 63. Random functions and permutations .. 64. Random functions .. 64. Random permutations .. 66. Pseudorandom functions .. 68. Pseudorandom permutations.

5 70. PRP under CPA .. 70. PRP under CCA .. 71. Relations between the notions .. 72. Modeling block ciphers .. 72. Example Attacks .. 73. Security against key recovery .. 75. The birthday attack .. 78. The PRP/PRF switching lemma .. 80. Sequences of families of PRFs and PRPs .. 80. Some applications of PRFs .. 81. Cryptographically Strong Hashing .. 81. Prediction .. 81. Learning .. 82. Identify Friend or Foe .. 82. Private-Key Encryption .. 82. Historical Notes .. 82. Problems .. 83. Cryptography : Lecture Notes 5. 6 Private-key encryption 85. Symmetric encryption schemes .. 85. Some symmetric encryption schemes .. 86. The one-time-pad encryption scheme .. 87. Some modes of operation .. 87. Issues in privacy .. 90. Indistinguishability under chosen-plaintext attack .. 92. Definition .. 92. Alternative interpretation .. 95. Why is this a good definition? .. 96. Example chosen-plaintext attacks .. 96. Attack on ECB .. 96. Any deterministic, stateless schemes is insecure.

6 97. Attack on CBC encryption with counter IV .. 98. IND-CPA implies PR-CPA .. 99. Security of CTR modes .. 101. Proof of Theorem ?? .. 102. Proof of Theorem ?? .. 106. Security of CBC with a random IV .. 111. Indistinguishability under chosen-ciphertext attack .. 111. Example chosen-ciphertext attacks .. 113. Attacks on the CTR schemes .. 113. Attack on CBC$ .. 114. Other methods for symmetric encryption .. 116. Generic encryption with pseudorandom functions .. 116. Encryption with pseudorandom bit generators .. 117. Encryption with one-way functions .. 117. Historical Notes .. 118. Problems .. 118. 7 Public-key encryption 119. Definition of Public-Key Encryption .. 119. Simple Examples of PKC: The Trapdoor Function Model .. 121. Problems with the Trapdoor Function Model .. 121. Problems with Deterministic Encryption in General .. 121. The RSA Cryptosystem .. 122. Rabin's Public key Cryptosystem .. 124. Knapsacks .. 125. Defining Security.

7 125. Definition of Security: Polynomial Indistinguishability .. 125. Another Definition: Semantic Security .. 126. Probabilistic Public Key Encryption .. 127. Encrypting Single Bits: Trapdoor Predicates .. 127. Encrypting Single Bits: Hard Core Predicates .. 128. General Probabilistic Encryption .. 129. Efficient Probabilistic Encryption .. 130. An implementation of EPE with cost equal to the cost of RSA .. 131. Practical RSA based encryption .. 132. 6 Goldwasser and Bellare Enhancements .. 134. Exploring Active Adversaries .. 134. 8 Hash Functions 136. The hash function SHA1 .. 136. Collision-resistant hash functions .. 138. Collision-finding attacks .. 140. One-wayness of collision-resistant hash functions .. 142. The MD transform .. 145. Collision-resistance under hidden-key attack .. 147. Problems .. 148. 9 Message authentication 149. The setting .. 149. Privacy does not imply authenticity .. 151. Syntax of message-authentication schemes.

8 152. A definition of security for MACs .. 153. Towards a definition of security .. 153. Definition of security .. 155. Examples .. 157. The PRF-as-a-MAC paradigm .. 159. The CBC MACs .. 160. The basic CBC MAC .. 160. Birthday attack on the CBC MAC .. 161. Length Variability .. 163. MACing with cryptographic hash functions .. 164. The HMAC construction .. 164. Security of HMAC .. 165. Resistance to known attacks .. 166. Universal hash based MACs .. 166. Minimizing assumptions for MACs .. 167. Problems .. 167. 10 Digital signatures 168. The Ingredients of Digital Signatures .. 168. Digital Signatures: the Trapdoor Function Model .. 169. Defining and Proving Security for Signature Schemes .. 170. Attacks Against Digital Signatures .. 170. The RSA Digital Signature Scheme .. 171. El Gamal's Scheme .. 171. Rabin's Scheme .. 172. Probabilistic Signatures .. 173. Claw-free Trap-door Permutations .. 174. Example: Claw-free permutations exists if factoring is hard.

9 174. How to sign one bit .. 175. How to sign a message .. 176. A secure signature scheme based on claw free permutations .. 177. A secure signature scheme based on trapdoor permutations .. 180. Cryptography : Lecture Notes 7. Concrete security and Practical RSA based signatures .. 182. Digital signature schemes .. 183. A notion of security .. 184. Generation of RSA parameters .. 185. One-wayness problems .. 187. Trapdoor signatures .. 188. The hash-then-invert paradigm .. 189. The PKCS #1 scheme .. 191. The FDH scheme .. 192. PSS0: A security improvement .. 197. The Probabilistic Signature Scheme PSS .. 201. Signing with Message Recovery PSS-R .. 202. How to implement the hash functions .. 203. Comparison with other schemes .. 203. Threshold Signature Schemes .. 204. Key Generation for a Threshold Scheme .. 205. The Signature Protocol .. 205. 11 Key distribution 206. Diffie Hellman secret key exchange .. 206. The protocol .. 206. Security against eavesdropping: The DH problem.

10 206. The DH cryptosystem .. 207. Bit security of the DH key .. 207. The lack of authenticity .. 208. Session key distribution .. 208. Trust models and key distribution problems .. 209. History of session key distribution .. 210. An informal description of the problem .. 211. Issues in security .. 211. Entity authentication versus key distribution .. 212. Three party session key distribution .. 212. Authenticated key exchanges .. 214. The symmetric case .. 215. The asymmetric case .. 216. Forward secrecy .. 217. 12 Protocols 219. Some two party protocols .. 219. Oblivious transfer .. 219. Simultaneous contract signing .. 220. Bit Commitment .. 220. Coin flipping in a well .. 221. Oblivious circuit evaluation .. 221. Simultaneous Secret Exchange Protocol .. 222. Zero-Knowledge Protocols .. 222. Interactive Proof-Systems(IP) .. 223. Examples .. 223. 8 Goldwasser and Bellare Zero-Knowledge .. 225. Definitions .. 225. If there exists one way functions, then NP is in KC[0].