Step through the RSA algorithm: choose two primes, compute n and φ(n), find public exponent e and private exponent d, then encrypt and decrypt a message with the resulting keypair.
RSA security relies on the difficulty of factoring large numbers. Given n = p·q, computing φ(n) = (p−1)(q−1) is easy if p and q are known, but practically impossible if only n is given. The extended Euclidean algorithm computes d = e⁻¹ mod φ(n).
Choose two primes p and q. The system computes n, φ(n), public key e, and private key d. Enter a message to encrypt with the public key and decrypt with the private key. See each modular exponentiation step.
RSA was published in 1977 by Rivest, Shamir and Adleman. The same algorithm was independently discovered in 1973 by Clifford Cocks at GCHQ but remained classified until 1997. Modern RSA uses 2048+ bit keys.
This simulation walks through the RSA public-key cryptosystem step by step. You pick two distinct primes p and q, and it computes the modulus n = p×q and Euler's totient φ(n) = (p−1)(q−1). It then lists valid public exponents e that are coprime to φ(n), derives the private exponent d as the modular inverse e−¹ mod φ(n) using the extended Euclidean algorithm, and lets you encrypt and decrypt a number.
The p and q dropdowns choose primes (from 2 to 97), the Compute Keys button regenerates everything, and the e pills let you select a valid public exponent. Encryption uses C = Me mod n and decryption M = Cd mod n, both via fast modular exponentiation. RSA underpins HTTPS, digital signatures and secure email, with real keys using primes hundreds of digits long.
What does this simulation show?
It demonstrates the complete RSA workflow on small, readable numbers: key generation from two primes, selecting a public exponent, deriving the private exponent, and then encrypting and decrypting a message. Every formula and intermediate value is shown so the maths stays transparent.
How are the keys actually generated?
From your chosen primes p and q it computes n = p×q and φ(n) = (p−1)(q−1). You pick a public exponent e that is coprime to φ(n), and the simulator finds the private exponent d satisfying d×e ≡ 1 (mod φ(n)) using the extended Euclidean algorithm.
What do the controls do?
The p and q dropdowns set the two primes from a list spanning 2 to 97, and Compute Keys recalculates the modulus, totient and exponents. The e pills let you switch between valid public exponents, and the message box lets you enter an integer M to encrypt and decrypt.
Encryption computes the ciphertext as C = M^e mod n, where M is the message, e the public exponent and n the modulus. Decryption reverses it with M = C^d mod n, using the private exponent d. Both use modular exponentiation, implemented here with BigInt to avoid overflow.
The public exponent e must satisfy gcd(e, φ(n)) = 1 so that a modular inverse d exists. Without coprimality there is no unique d, and decryption would fail. The simulation only offers values of e that meet this condition.
RSA works in arithmetic modulo n, so any message must be an integer in the range 0 ≤ M < n to be uniquely recoverable. If M were equal to or larger than n, the modulo operation would map distinct messages onto the same value and decryption would not return the original.
The algorithm is genuine RSA: the same key-generation, encryption and decryption equations used in production. The only simplification is scale. Real RSA uses primes of hundreds of digits (2048-bit keys or larger), whereas here tiny primes keep every step legible.
Its security rests on the difficulty of factoring n back into p and q. Computing φ(n), and hence d, is easy if you know the primes but believed to be infeasible if you only know n. With large enough keys no known classical algorithm can factor n in practical time.
Because d is the modular inverse of e, raising the ciphertext to the power d undoes raising the message to the power e. By Euler's theorem, M^(e×d) ≡ M (mod n), so (M^e)^d mod n recovers M exactly. The simulation verifies this match for you.
RSA secures HTTPS connections, signs software and certificates, protects email with standards like PGP, and underpins many key-exchange and authentication protocols. It is often used to exchange a symmetric session key, which then encrypts the bulk of the data more efficiently.
In principle yes. Shor's algorithm can factor large integers efficiently on a sufficiently powerful quantum computer, which would break RSA. This is why researchers are developing post-quantum cryptography, though no quantum machine today is large enough to threaten real keys.