# RSA

## Encryption

**Alice** first generates primes $$p$$ and $$q$$ and $$N$$ such that $$N=pq$$. This is half of the public key, with the other half being the **public exponent** $$e$$, which should be **coprime** to $$\phi (N)$$ (meaning $$gcd(\phi (N), e) = 1$$). These two values are then made public.

If **Bob** wants to send a message $$M$$ to Alice using RSA, he calculates:

$$
c = M^e \mod N
$$

Where $$c$$ is now the ciphertext and is sent to **Alice**.

## Decryption

Alice calculates $$\phi (N) = (p-1)(q-1)$$ and then calculates the [**modular multiplicative inverse**](/notes/cryptography/number-theory-fundamentals/modular-arithmetic.md#modular-multiplicative-inverses) $$d$$ of $$e \mod \phi (N)$$. $$d$$ is the **private key** used for the decryption which is known only to **Alice**.

To decrypt, the Alice calculates $$M$$ again:

$$
M = c^d \mod N
$$

The proof for this is based on [Euler's Formula](/notes/cryptography/number-theory-fundamentals/rings-fields-and-eulers-totient-function.md#eulers-formula). Because we calculated $$d$$ such that $$de \equiv 1 \mod \phi (N)$$, then we know that there is an integer $$k$$ such that $$de = k\phi (N) + 1$$. Also note that $$c^d \equiv (M^e)^d \equiv M^{de}$$:

$$
M^{de} \equiv M ^ {k\phi (N) + 1} \equiv M^{k\phi (N)} \times M \equiv (M^{\phi (N)})^k \times M \equiv 1^k \times M \equiv M \mod N
$$

## Attacks on RSA

Attacks on RSA generally fall into several categories, including weak public exponent or a poor choice of $$p,q$$ which results in a value of $$N$$ which can be factorised or attacked in another way. Remember that the trapdoor function in RSA is the difficulty of factoring $$N$$ into the primes that make it up so only Alice is able to compute $$\phi(N)$$ efficiently!


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ir0nstone.gitbook.io/notes/cryptography/overview.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.