Opening Cryptography: Encryption
Cryptography: Encryption
- Length
- 1 h 24 min
- Level
- Undergraduate
- Recorded
- MIT2016
Chapter 1 of 12: Before the lecture
Proves RSA decryption correct with Fermat's little theorem, then shows why the Merkle-Hellman knapsack system fails.
Encryption in Devadas's session of MIT 6.046J runs from shared-key ciphers to public-key cryptosystems. Devadas opens with symmetric schemes built from reversible operations such as permutations and exclusive OR, citing Enigma. A pirate puzzle frames key exchange and leads to Diffie-Hellman, whose security rests on the discrete logarithm, then to a man-in-the-middle attack on unauthenticated exchange. RSA key generation uses the extended Euclidean algorithm, and Fermat's little theorem proves that decryption recovers the message. A closing argument separates worst-case NP-completeness from the average-case hardness cryptography needs, with the Merkle-Hellman knapsack system as the failure case.
Encryption in Devadas's session of MIT 6.046J runs from shared-key ciphers to public-key cryptosystems. Devadas opens with symmetric schemes built from reversible operations such as permutations and exclusive OR, citing Enigma. A pirate puzzle frames key exchange and leads to Diffie-Hellman, whose security rests on the discrete logarithm, then to a man-in-the-middle attack on unauthenticated exchange. RSA key generation uses the extended Euclidean algorithm, and Fermat's little theorem proves that decryption recovers the message. A closing argument separates worst-case NP-completeness from the average-case hardness cryptography needs, with the Merkle-Hellman knapsack system as the failure case.

This lecture
Lecture 25 of 27 of Design and Analysis of Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in