Cryptography

Builds on

Required prerequisites, all the way down: 20

You will learn to

• Implement RSA key generation, encryption and decryption, and prove correctness using Euler's theorem and the Chinese remainder theorem.
• Carry out Diffie–Hellman key exchange and explain its reliance on the hardness of discrete logarithms.
• Explain why fast modular exponentiation makes these systems practical, and why their security claims are conditional.

Definition

• In RSA, n = pq for large primes p and q, and exponents e and d satisfy ed ≡ 1 (mod φ(n)); a message m is encrypted as mᵉ mod n.
• The discrete logarithm problem asks, given g and h = gˣ in a group, to find x.
• A one-way function is easy to compute but believed to be hard to invert.

Theorem

• RSA decryption works: (mᵉ)ᵈ ≡ m (mod n) for every integer m, by Euler's theorem and the Chinese remainder theorem.
• Modular exponentiation by repeated squaring uses O(log e) multiplications.
• Shor's algorithm would factor integers and compute discrete logarithms in polynomial time on a sufficiently large quantum computer.

Common misconceptions

• Thinking RSA's security has been proved; it rests on unproved assumptions about factoring.
• Believing encryption alone guarantees authenticity; that needs signatures or message authentication codes.
• Using 'textbook' RSA without padding in practice.

Optional discoveries

• Computational complexity The existence of one-way functions would imply P ≠ NP, which remains unproved.
• Information theory Shannon proved that the one-time pad achieves perfect secrecy, and that perfect secrecy requires a key with at least as much entropy as the message.
• ← Factors, multiples and primes
• ← Secret codes
• ← Clock arithmetic: remainders and modular arithmetic
• ← Number theory
• ← Groups

Further reading

• Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, An Introduction to Mathematical Cryptography (2008)
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography (2007)