Chiffre RSA

Le chiffrement RSA est purement mathématique, tout message doit d'abord être codé par des nombres entiers (n'importe quel encodage fonctionne: ASCII, Unicode, voire A1Z26). Pour le chiffrement RSA a besoin des nombres $ n $ et $ e $ appelées les clés publiques.

Le message (numérique) est décomposé en nombres (inférieurs à $ n $), pour chaque nombre M, le message (numérique) chiffré C est $$ C \equiv M^{e}{\pmod {n}} $$

Exemple : Chiffrer le message R,S,A (encodé 82,83,65) avec la clé publique $ n = 1022117 $ et $ e = 101 $ soit $ C = 828365^{101} \mod 1022117 = 436837 $, 436837 est le message chiffré.

RSA a besoin d'une clé publique (constituée de 2 nombres $ (n, e) $) et d'une clé privée (1 seul nombre $ d $).

- Sélectionner 2 nombres premiers distincts $ p $ et $ q $ (plus ils sont grands et plus le chiffrement sera robuste)

- Calculer $ n = p \times q $

- Calculer l'indicatrice d'Euler $ \phi(n) = (p-1)(q-1) $

- Sélectionner un entier $ e \in \mathbb{N} $, premier avec $ \phi(n) $ tel que $ e < \phi(n) $

- Calculer l'inverse modulaire $ d \in \mathbb{N} $, ie. $ d \equiv e^{-1} \mod \phi(n) $ (via l'algorithme d'Euclide étendu)

Avec ces nombres, le couple $ (n,e) $ est appelée la clé publique et le nombre $ d $ est la clé privée.

Exemple : $ p = 1009 $ et $ q = 1013 $ donc $ n = pq = 1022117 $ et $ \phi(n) = 1020096 $. Les nombres $ e = 101 $ et $ \phi(n) $ sont premiers entre eux et $ d = 767597 $.

Les clés sont renouvelées régulièrement afin d'éviter tous risques de divulgation de la clé privée.

Le déchiffrement nécessite de connaitre la clé privée $ d $ et la clé publique $ n $. Pour tout message (numérique) chiffré C, le message (numérique) clair M se calcule : $$ M \equiv C^{d}{\pmod {n}} $$

Exemple : Déchiffrer le message C=436837 avec la clé publique $ n = 1022117 $ et la clé privée $ d = 767597 $, soit $ M = 436837^{767597} \mod 1022117 = 828365 $, 82,83,65 est le message clair (soit les lettres R,S,A)

Le message est entièrement numérique est normalement accompagné au moins d'une clé (numérique aussi). En pratique les clés sont affichés en hexadécimal, leur longueur dépend de la complexité du RSA mis en oeuvre (256 bits, 512, 1024 ou 2048 sont courants)

Pour retrouver la clé privée, un pirate doit être en mesure de réaliser la décomposition en facteurs premiers du nombre $ n $ pour retrouver ses 2 facteurs $ p $ et $ q $. Pour les petites valeurs (jusqu'au million ou au milliard), c'est assez rapide avec les algorithmes et les ordinateurs actuels, mais au delà, lorsque les nombres $ p $ et $ q $ ont plusieurs centaines de chiffres, la décomposition nécessite en moyenne plusieurs centaines ou milliers d'années de calcul.

Avec les nombres $ p $ et $ q $ la clé privée $ d $ peut être calculée et les messages peuvent être déchiffrés.

Ronald Rivest, Adi Shamir et Leonard Adleman ont décrit l'algorithme en 1977 puis l'ont breveté en 1983.