How RSA Key Generation and Encryption Work
RSA is a public-key cryptosystem built on the fact that multiplying two large prime numbers is fast, but factoring their product back into those primes is computationally hard. This calculator walks through the textbook RSA key-generation steps — choosing primes p and q, computing the modulus n and Euler's totient φ(n), and deriving the private exponent d from a public exponent e — and can optionally encrypt and decrypt a sample message so you can see the math work end to end.
Generating the key pair
Start with two distinct prime numbers, p and q (61 and 53, for example — the classic textbook values). Multiply them to get the modulus n = p × q = 3233. Compute Euler's totient φ(n) = (p − 1)(q − 1) = 3120, which counts how many integers between 1 and n share no common factor with n. Next choose a public exponent e with 1 < e < φ(n) and gcd(e, φ(n)) = 1; common real-world choices are 3, 17, or 65537, though any coprime value works for learning purposes (17 is used here). Finally, find the private exponent d — the modular multiplicative inverse of e modulo φ(n), i.e. the value satisfying e × d ≡ 1 (mod φ(n)). This calculator finds d with the extended Euclidean algorithm. The public key is the pair (n, e); the private key is the pair (n, d), and only d needs to stay secret.
Encrypting and decrypting a message
To encrypt a message M (represented as an integer smaller than n), compute the ciphertext C ≡ Me (mod n) using the public key. To decrypt, the holder of the private key computes M ≡ Cd (mod n), recovering the original message. This works because raising to the e-th power and then the d-th power modulo n is equivalent to raising to the e×d power, and e × d ≡ 1 (mod φ(n)) — a consequence of Euler's theorem — which returns M unchanged modulo n. This calculator performs both steps automatically when you supply a message, so you can confirm the recovered value matches your input.
Common mistakes when choosing p, q, and e
- Reusing p or q, or setting p = q: n = p² is trivially factorable by taking a square root, which breaks the encryption entirely.
- Picking e that shares a factor with φ(n): no modular inverse d exists, so a private key cannot be computed and decryption is impossible.
- Encrypting a message M ≥ n: modular arithmetic wraps around, so decryption returns M mod n instead of your original message.
- Using tiny textbook primes for real security: primes like 61 and 53 only illustrate the math — real RSA keys use primes hundreds of digits long.
Why RSA is considered secure
RSA's security rests on the integer factorization problem: given n, finding its prime factors p and q is believed to be computationally infeasible for large enough n (typically 2048 bits or more in modern practice), even though computing n from p and q is trivial. Anyone can use the public key (n, e) to encrypt, but only someone who knows the private exponent d — which requires knowing φ(n), which requires knowing p and q — can decrypt. This calculator uses small demonstration primes so results compute instantly and remain easy to verify by hand; it is a teaching and homework-checking tool, not a substitute for a vetted cryptography library.