RSA Crypto Explained

RSA-2048 keys secure most of the HTTPS traffic on the internet today. Factoring a 2048-bit number back into its two prime factors would take even the fastest supercomputers on Earth far longer than the age of the universe. Yet multiplying those same two primes together takes a computer a fraction of a second. That gap between easy multiplication and near-impossible factoring is the entire foundation of RSA encryption.

- How to generate an RSA public and private key from two prime numbers - What Euler's totient function is and why RSA depends on it - How modular exponentiation encrypts and decrypts a message - Why factoring a large semiprime number is computationally hard

RSA starts by picking two prime numbers, kept secret, and multiplying them to get a public modulus n. Using the classic textbook example: let p = 61 and q = 53. Then n = p times q = 61 times 53 = 3233. This n becomes part of the public key that anyone can see, but p and q themselves stay hidden. In real systems p and q are each hundreds of digits long, not two digits like this teaching example.

Next, compute Euler's totient of n, written phi(n), which counts how many numbers less than n share no common factors with n. For two primes, phi(n) = (p-1)(q-1) = 60 times 52 = 3120. Then pick a public exponent e that shares no common factors with 3120. The standard textbook choice is e = 17. The pair (e, n) = (17, 3233) is now the full public key that anyone can use to encrypt a message to you.

The private key d is the modular inverse of e with respect to phi(n), meaning the number where (e times d) mod phi(n) = 1. Using the extended Euclidean algorithm on e = 17 and phi(n) = 3120 gives d = 2753. The pair (d, n) = (2753, 3233) is the private key, and it must never be shared. Notice that d can only be found efficiently if you already know phi(n), which itself requires knowing p and q.

To encrypt a message m, compute c = m^e mod n. Using m = 65: c = 65^17 mod 3233 = 2790. To decrypt, the receiver computes m = c^d mod n = 2790^2753 mod 3233, which correctly returns 65. This works because of a result from number theory called Euler's theorem, which guarantees that raising a number to the power (e times d) mod phi(n) returns the original number, as long as e and d were chosen as inverses modulo phi(n).