The keys
How d is found: the extended Euclidean algorithm
Each row divides the two rows above it. In the row with remainder 1, the last column is d (add φ(n) if it is negative).
| Quotient | Remainder | Coefficient of e |
|---|
The message
Sent over the network
| Bit | Square | Multiply by m |
|---|
Breaking the key
RSA encryption demo
RSA lets anyone lock a message with your public key while only you can open it with your private key. Behind it are a few lines of school arithmetic: two prime numbers, a multiplication, a remainder and a clever inverse. Build a key pair from primes you choose, encrypt and decrypt a message character by character, sign it so anyone can check it came from you, and then play the attacker and factor n to see why real keys need hundreds of digits. Pick two prime numbers p and q, or press New primes. The app builds the public key (e, n) and the private key d, and shows how the extended Euclidean algorithm finds d. Type a message: every character is encrypted with the public key and decrypted with the private key. Click a row to see the power computed by repeated squaring. Switch to Sign to sign with the private key instead, and press Factor n to see how quickly small keys break.
How it works
- Enter two primes p and q, or choose a size and press New primes; the app computes n, φ(n), e and d, and shows how d is found.
- Type a message and choose Encrypt or Sign. Each character is turned into a number and raised to a power mod n; click a row to see the repeated squaring.
- Press Factor n to let Eve split n into its two primes and recover the private key.
How the keys work
Multiply two primes: n = p × q. With p = 61 and q = 53, n = 3233. The number φ(n) = (p − 1)(q − 1) = 3120 counts the numbers below n that share no factor with it, and it can only be computed by someone who knows p and q. Choose e = 17, which shares no factor with 3120, and find d with e × d = 1 more than a multiple of φ(n): here d = 2753, because 17 × 2753 = 46801 = 15 × 3120 + 1. Publish (e, n) and keep d. A message m becomes c = mᵉ mod n, and Euler's theorem guarantees that cᵈ mod n gives m back.
Why it is hard to break
Everything an attacker needs is hidden in the factors of n. With n = 3233 that is no protection: trying odd divisors finds 53 after about two dozen tries. But the effort grows with the square root of n. A modulus of 2048 bits has about 617 digits, and no known method, on any computer that exists today, can factor it in a useful time. Signing runs RSA backwards: s = mᵈ mod n can only be made with the private key, and anyone can check that sᵉ mod n gives m back.
Frequently asked questions
Why can't anyone compute d from the public key?
To find d you need φ(n) = (p − 1)(q − 1), and to get φ(n) you need p and q. Recovering them from n means factoring it, and for numbers with hundreds of digits no fast method is known. The demo lets you factor toy keys in a fraction of a second, which shows exactly why real keys are so large.
Why is the message encrypted one character at a time?
Because the toy keys are small: RSA can only encrypt a number smaller than n. With n = 3233, every character code fits, but a whole sentence would not. Real RSA uses a modulus of 2048 bits or more, pads the message with random bytes so that the same message never encrypts the same way twice, and in practice encrypts only a short key for a faster cipher such as AES.
What does repeated squaring do?
It computes huge powers like m²⁷⁵³ mod n without ever writing down the huge number. Write the exponent in binary, then go through its bits: square the running result for every bit and multiply by m for every 1, taking the remainder mod n each time. An exponent of 2048 bits needs only about 2048 squarings.
What is the difference between encrypting and signing?
Encrypting uses the receiver's public key, so that only the receiver's private key can undo it. Signing uses the sender's private key, so that anyone can check it with the sender's public key and know the message came from the holder of that key and was not changed.
Is my message sent anywhere?
No. Everything is computed in your browser, and your primes and message stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor