RSA calculator

Type four whole numbers separated by spaces: two different primes p and q, a public exponent e, and a message number m smaller than p × q. The output is the ciphertext, the rows give both keys and the message decrypted again, and the steps show every calculation, including the extended Euclidean algorithm that finds d.

The sample, 61 53 17 65, is the example many textbooks use: n = 3233, d = 2753, and 65 encrypts to 2790.

Multiply the primes to get n. Work out φ(n) = (p − 1)(q − 1), which counts the numbers below n that share no factor with it. Choose e between 1 and φ(n) sharing no factor with φ(n); 65537 is the usual choice for real keys. Find d so that e × d leaves remainder 1 when divided by φ(n). The public key is (n, e); the private key is d.

To encrypt, c = mᵉ mod n. To decrypt, m = cᵈ mod n. It works because of Euler's theorem: raising to e and then to d comes back round to the start.

Everything rests on n being too hard to factor. With p and q under 100,000, as here, anyone can factor n in a moment and work out d. Real keys use primes hundreds of digits long, and real systems also pad the message with random bytes before encrypting, so the same message never gives the same ciphertext. Use a proper library for anything secret.