a blog

RSA calculator

Disclaimer: this tool is for educational purposes only and is not suited for security.

Note: this tool uses JavaScript BigInts. If you want hex, octal, or binary input, prefix with 0x, 0o, or 0b respectively. For hex, octal, or binary output, select:

Further reading: RSA (cryptosystem) on Wikipedia

Need more flexibility? Python has arbitrary-precision integer support (preferably use version 3.8 or later).


Key generation

Choose two distinct prime numbers p and q.



Calculate n = p * q.


Compute the Carmichael's totient function tot(n) = λ(n) = lcm(p - 1, q - 1). (Note that Euler's totient function tot(n) = φ(n) = (p - 1) * (q - 1) could be used instead. See StackExchange.)


Choose any number e where 1 < e < tot(n) and e is coprime to tot(n). Common choices are 3, 17, and 65537 (these are Fermat primes).


Compute d, the modular multiplicative inverse of e (mod tot(n)).


That's it for key generation! The public key is (n, e) and the private key is (n, d)

Encryption and decryption

Encryption is done with c(m) = m^e mod n where c is the ciphertext and m is the message. Note that both of these values must be integers 1 < m < n and 1 < c < n.

Decryption is done with m(c) = c^d mod n.




Factoring the public modulus n

The public modulus n is equal to a prime number p times a prime number q. If you know p and q (and e from the public key), you can determine the private key, thus breaking the encryption. However, factoring a large n is very difficult (effectively impossible). A small-ish n (perhaps 50-100 decimal digits) can be factored. The following tool can do just that:

Alpertron's integer factorization calculator

Broadcast attack

If the same message m is encrypted with e different public keys, then the original message can be recovered without the private key. This is Håstad's broadcast attack. It's most useful when e is 3, since only 3 messages are needed; this calculator is meant for that case. This attack applies primarily to textbook RSA where there is no padding; modern padding schemes mitigate it.

e: 3

n1: c1:

n2: c2:

n3: c3:

The RSA decryption function is c = m^e (mod n), so suppose that e=3 and M = m^3. We must now solve this system of equations:

M ≡ c1 (mod n1)
M ≡ c2 (mod n2)
M ≡ c3 (mod n3)

Assuming all three ns are coprime, the Chinese Remainder Theorem indicates that there is a solution for the system exists. If the moduli were not coprime, then one or more could be factored.

To find this solution, first find:

N = n1*n2*n3
N1 = N / n1
N2 = N / n2
N3 = N / n3




gcd(Ni, ni) = 1 for each pair Ni and ni, so the modular multiplicative inverse ui must exist such that Ni * ui = 1 (mod ni). Find each inverse u1, u2, and u3.




Now, calculate M ≡ c1*N1*u1 + c2*N2*u2 + c3*N3*u3 (mod N):


Since m < n for each message, m^3 < n1*n2*n3 and M = m^3. Find the cube root of M to recover the original message.


Further reading: Attacking RSA for fun and CTF points – part 2 (BitsDeep)

Oracle attack

You are given the public key n and e, a ciphertext c, and an oracle that will decrypt anything except for the given ciphertext.




Compute a new ciphertext c' = (c * 2^e) mod n.


When c' is decrypted using the oracle, you get back m' = 2m mod n. Decrypt and put the result here (it should be significantly smaller than n, assuming the message is not padded).


For the unpadded messages found in this sort of textbook RSA implementation, simply divide by 2 to recover the original message.


Further reading: StackExchange