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

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

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