RSA & Public-Key Cryptography

Every secret message needs a key, and that creates a chicken-and-egg problem. If you and a website want to talk privately, you both need the same secret key first, but you cannot send that key over the network, because anyone might be listening. Public-key cryptography solves this by giving each person two keys instead of one. RSA, named after Rivest, Shamir and Adleman, is the best-known version. It protects the key exchange behind HTTPS and SSH, and it signs software so you can trust where it came from.

Imagine you make a thousand identical open padlocks and hand them out to anyone who asks. Anyone can snap one shut around a box, but only you own the key that opens it. A stranger can send you a locked box without ever having met you, and you never had to send anyone a key.

• -The open padlock you hand out is your public key.
• -Snapping the padlock shut is encrypting.
• -Your own key, which never leaves your pocket, is the private key.
• -Opening the box is decrypting.
• -Doing it the other way round, locking with your private key so that anyone can check with your public one, is a digital signature. It proves a message really came from you.

The difference is that RSA's padlock is made of arithmetic. The next sections show that arithmetic with numbers small enough to check by hand.

RSA is built on remainders, the same operation as Python's % operator. A 12-hour clock is the picture to keep in mind: 9 o'clock plus 5 hours is 2 o'clock, because 14 divided by 12 leaves a remainder of 2. We write that as 14 mod 12 = 2. RSA works on a far bigger clock, one with n hours on its face, where n is an enormous number.

• -Pick two prime numbers and keep them secret: p = 61 and q = 53. Multiply them to get the modulus n = 61 x 53 = 3233. This is the number of hours on the clock face, and it is published.
• -Compute phi = (61 - 1) x (53 - 1) = 3120. Only someone who knows p and q can compute this number, so it stays secret.
• -Choose a public exponent e that shares no factor with 3120 except 1. The textbook choice is e = 17. The public key is the pair (17, 3233).
• -Find the private exponent d: the number for which 17 x d leaves remainder 1 when divided by 3120. Here d = 2753, because 17 x 2753 = 46,801 = 15 x 3120 + 1. The private key is (2753, 3233).

To encrypt a message m, a number smaller than n, you raise it to the power e on the n-hour clock: ciphertext = m^e mod n. To decrypt, you raise the ciphertext to the power d: m = ciphertext^d mod n. The link between e and d, that their product leaves remainder 1 modulo phi, is exactly what makes the second step undo the first. That guarantee comes from a theorem of Euler, which you can take on trust for now.

Take the message m = 65. Encrypting means computing 65^17 mod 3233. The plain power 65^17 is 6,599,743,590,836,592,050,933,837,890,625, a 31-digit number, and dividing it by 3233 leaves a remainder of 2790. So the ciphertext is 2790. To decrypt, the receiver computes 2790^2753 mod 3233 and gets 65 back. But 2790^2753 has about 9,486 digits, a huge number to build only to throw nearly all of it away.

That is why Python's three-argument `pow(base, exponent, modulus)` matters. It uses repeated squaring and takes the remainder after every step, so no number ever grows beyond the size of n. A 2048-bit exponent needs only a couple of thousand squarings and multiplications, not 2 to the power 2048 of them. Run the whole example below and compare each printed line with the numbers above.

The first lines print the two keys, then the message 65 becomes 2790 and comes back as 65. The last lines show why tiny primes are useless for real security: n = 3233 is cracked in 52 guesses.

An attacker sees the public key, e and n. To work out d they need phi, and to get phi they need p and q, which means factoring n. Multiplying two primes takes a computer microseconds, but going back has no known fast method. A real key uses a 2048-bit n, a number of about 617 digits whose two prime factors have about 300 digits each. Trial division, the method used on 3233 above, would need around 10^308 guesses. The best known factoring methods are much faster than that, but still far out of reach.

That gap, easy to multiply and infeasible to factor, is the entire security of RSA.