Disclaimer: this tool is for educational purposes only and is not suited for security.
If you want hex, octal, or binary input, prefix with
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).
Choose two distinct prime numbers
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.
Choose any number
1 < e < tot(n) and
e is coprime to
Common choices are 3, 17, and 65537 (these are Fermat primes).
d, the modular multiplicative inverse of
That's it for key generation!
The public key is
(n, e) and the private key is
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
The public modulus
n is equal to a prime number
times a prime number
If you know
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).
n (perhaps 50-100 decimal digits) can be factored.
The following tool can do just that:
Alpertron's integer factorization calculator
If the same message
m is encrypted with
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.
The RSA decryption function is
c = m^e (mod n), so
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, so the modular multiplicative inverse
must exist such that
Ni * ui = 1 (mod ni).
Find each inverse
M ≡ c1*N1*u1 + c2*N2*u2 + c3*N3*u3 (mod N):
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)
You are given the public key
e, a ciphertext
and an oracle that will decrypt anything except for the given ciphertext.
Compute a new ciphertext
c' = (c * 2^e) mod n.
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
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