RSA & Public-Key Cryptography
You'll learn to
- -Explain the public/private key pair model and why it solves a problem symmetric keys cannot
- -Implement modular exponentiation, the core operation behind RSA
- -Explain why RSA's security rests on the difficulty of factoring large numbers
The Caesar cipher and SHA-256 both use a single piece of information (a shift amount, or nothing at all) that both sides already need identically. Level 34 introduces something structurally different: a key pair where one half is public and the other stays private, and where encrypting with one half only decrypts with the other. That is RSA, the algorithm underpinning HTTPS key exchange, SSH, and code signing.
The Problem Public-Key Cryptography Solves
With a shared-secret (symmetric) cipher, both sides need the same key before they can talk securely - but how do you get that key to the other side in the first place, over a channel someone might be listening on? Public-key cryptography sidesteps this: everyone can publish their public key openly, it is fine if an attacker has it, while only the matching private key can decrypt what was encrypted with the public key - or, used the other way, only the private key can produce a signature that the public key can verify. No secret ever has to cross the wire.
The Core Operation: Modular Exponentiation
RSA encryption and decryption are both just pow(message, exponent, modulus) - raise a number to a power, then take the result mod n. Python's built-in three-argument pow() computes this efficiently via repeated squaring rather than literally computing the huge power first, which matters because RSA's numbers are hundreds of digits long in production. In toy form, key generation picks two large primes p and q, computes n = p * q and phi = (p-1)*(q-1), then picks a public exponent e (commonly 65537 in real systems, since it is a small, efficient value that is coprime with most phi values) and derives a private exponent d such that e * d is congruent to 1 mod phi. Encrypting is ciphertext = pow(message, e, n); decrypting is plaintext = pow(ciphertext, d, n).
Why This Is Actually Hard to Break
n = p * q is public, but recovering p and q from n alone - factoring a huge number back into its two prime factors - has no known efficient algorithm for numbers with hundreds of digits, even though multiplying p * q in the first place takes microseconds. That asymmetry, easy to multiply but computationally infeasible to factor back, is the entire security foundation of RSA: without p and q you cannot compute phi, and without phi you cannot derive the private exponent d from the public exponent e, even though d and e are mathematically linked.
The pattern to remember: symmetric ciphers need a shared secret both sides already have; public-key ciphers let one side publish a key openly because encryption and decryption use two different, mathematically-linked keys, only one of which needs to stay secret.
Why is RSA considered secure even though the public key and the modulus n are both, well, public?
"Because it's encrypted with a strong algorithm."
"Because deriving the private key from public information requires factoring n back into its two large prime factors, and there's no known efficient algorithm for factoring numbers that large - even though computing n = p times q in the first place is trivial. That one-way difficulty, easy to multiply but computationally infeasible to factor, is what RSA's security rests on, not secrecy of the algorithm itself."
What problem does public-key (asymmetric) cryptography solve that a shared-secret (symmetric) cipher cannot?
Level 34: RSA Reckoning has you implement the core RSA operations - modular exponentiation for encrypt and decrypt, and the key-generation math linking a public exponent to a private one through two primes - the same mechanics as the toy example above, at a scale where trying every possible private key is not an option.