Primeros años de universidadApplied MathematicsLección disponible
Cryptography
The mathematics of modern cryptography: symmetric and public-key systems, RSA, Diffie–Hellman key exchange, discrete logarithms, digital signatures, and the unproved hardness assumptions on which security rests.
math.applied.cryptography
Se basa en
Requisitos previos obligatorios, hasta el fondo: 20
Aprenderás a
- 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.
Definición
- 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.
Teorema
- 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.
Errores frecuentes
- 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.
Descubrimientos opcionales
- 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
- ← Arithmetic geometry and elliptic curves
Lecturas complementarias
- Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, An Introduction to Mathematical Cryptography (2008)
- Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography (2007)