> For the complete documentation index, see [llms.txt](https://sansong.gitbook.io/cyber/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sansong.gitbook.io/cyber/crypto/asymetrique/rsa.md).

# RSA

Fonctionnement

### Factorisation et chiffrement RSA

*Tout nombre est premier ou produit de facteurs premiers.*

{% hint style="info" %}
Il tient son nom des initiales de ses 3 inventeurs:  [Ronald Rivest](https://fr.wikipedia.org/wiki/Ronald_Rivest), [Adi Shamir](https://fr.wikipedia.org/wiki/Adi_Shamir) et [Leonard Adleman](https://fr.wikipedia.org/wiki/Leonard_Adleman).
{% endhint %}

L'idée se base sur le fait qu'il est impossible en pratique à l'heure actuelle de calculer la décomposition en nombres premiers de grands nombres.

{% hint style="success" %}
On pourrait imaginer un nombre $$n$$ comme clé publique et deux entiers $$p$$ et $$q$$ (premiers tels que $$n=p\times q$$) comme clé privée. 

→ facile pour le destinataire de choisir les 2 nombres premiers et de les multiplier MAIS impossible pour quiconque de retrouver $$p$$ et $$q$$ à partir de $$n$$.
{% endhint %}

#### Chiffrement RSA

* choisir 2 nombres premiers $$p$$ et $$q$$
* calculer $$n=p\times q$$
* choisir un entier $$e$$ premier avec $$\phi(n)=(p-1)(q-1)$$
* calculer $$d$$ l'inverse de $$e$$ modulo $$\phi(n)$$ 

→ **clé publique:** $$(n, e)$$ 

→ **clé privée:** $$(p, q, d)$$

Pour chiffrer un message $$m$$

$$\begin{aligned} c=m^e\bmod n \end{aligned}$$

Pour déchiffrer un chiffré $$c$$:

$$\begin{aligned} m=c^d\bmod n \end{aligned}$$