# 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).

## RSA

### Key generation

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 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`

.

`m`

:

`c`

:

## Attacks

### 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 `n`

s 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)

### 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.

`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