← Back to the reading view
Slides · 13 slides
RSA & public-key cryptography
The same module told visually, ready to present. Speaker notes carry the full explanation.
Public-key
RSA & public-key cryptography
Two linked keys solve the problem symmetric crypto can't: sharing a secret with a stranger
RSA & public-key cryptography · Classical Crypto Today1 / 13
The bootstrapping problem
How do you share the first key?
RSA & public-key cryptography · Classical Crypto Today2 / 13
The asymmetry
Multiplying is easy, factoring is hard
Public (n, e) · private (n, d) · e·d ≡ 1 mod φ(n)
RSA & public-key cryptography · Classical Crypto Today3 / 13
Worked example
RSA with small numbers
RSA & public-key cryptography · Classical Crypto Today4 / 13
Engineering choice
Why e = 65537
RSA & public-key cryptography · Classical Crypto Today5 / 13
Same math, roles reversed
RSA signatures
Real RSA signs a padded hash (RSA-PSS), never a raw message
RSA & public-key cryptography · Classical Crypto Today6 / 13
Getting n right
Exactly two large primes
RSA & public-key cryptography · Classical Crypto Today7 / 13
No factoring required
Classic implementation attacks
RSA & public-key cryptography · Classical Crypto Today8 / 13
The whole game
The factoring record
The best classical method, GNFS, is sub-exponential; Shor's algorithm is not limited by it
RSA & public-key cryptography · Classical Crypto Today9 / 13
Advanced · tiny factors
Trial division: 979
RSA & public-key cryptography · Classical Crypto Today10 / 13
Advanced · no padding
When Mᵉ never wraps around
RSA & public-key cryptography · Classical Crypto Today11 / 13
Advanced · close primes
Fermat factorization
RSA & public-key cryptography · Classical Crypto Today12 / 13
Advanced · Wiener
d must never be small
RSA & public-key cryptography · Classical Crypto Today13 / 13
1 / 13
Keys: ← → move, F full screen, G all slides, N notes