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).
Choose two distinct prime numbers p and q.
p:
q:
Calculate n = p * q.
n:
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.)
tot(n):
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).
e:
Compute d, the modular multiplicative inverse of e (mod tot(n)).
d:
That's it for key generation!
The public key is (n, e) and the private key is (n, d)
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.
m:
c:
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
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
N1:
N2:
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.
u1:
u2:
u3:
Now, calculate
M ≡ c1*N1*u1 + c2*N2*u2 + c3*N3*u3 (mod N):
M:
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.
m:
Further reading: Attacking RSA for fun and CTF points – part 2 (BitsDeep)
You are given the public key n and e, a ciphertext c,
and an oracle that will decrypt anything except for the given ciphertext.
n:
e:
c:
Compute a new ciphertext c' = (c * 2^e) mod n.
c':
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).
m':
For the unpadded messages found in this sort of textbook RSA implementation,
simply divide by 2 to recover the original message.
m:
Further reading: StackExchange