Introduction au Cryptosystème RSA

Cours de Spécialité Mathématiques - Lycée

1. Principe du RSA

Le cryptosystème RSA, nommé d'après ses inventeurs Rivest, Shamir et Adleman, est l'un des premiers systèmes de cryptographie à clé publique. Il repose sur la difficulté de factoriser le produit de deux grands nombres premiers.

Fonctionnement général :

  1. Génération de clés (publique et privée)
  2. Chiffrement du message avec la clé publique
  3. Déchiffrement du message avec la clé privée
Note : La sécurité du RSA repose sur le fait qu'il est facile de multiplier deux grands nombres premiers, mais très difficile de factoriser leur produit.

2. Génération des clés

La génération des clés RSA se fait comme suit :

  1. Choisir deux grands nombres premiers distincts p et q
  2. Calculer n = p × q
  3. Calculer φ(n) = (p-1)(q-1)
  4. Choisir un entier e premier avec φ(n) tel que 1 < e < φ(n)
  5. Calculer d tel que d × e ≡ 1 (mod φ(n))

La clé publique est le couple (n, e), la clé privée est d.

3. Chiffrement et Déchiffrement

Chiffrement :

Pour un message m, le texte chiffré c est donné par :

c ≡ me (mod n)

Déchiffrement :

Pour retrouver m à partir de c, on calcule :

m ≡ cd (mod n)

Exemple simplifié :

Prenons p = 3 et q = 11 (en pratique, ces nombres sont beaucoup plus grands)

  • n = 3 × 11 = 33
  • φ(n) = (3-1)(11-1) = 2 × 10 = 20
  • Choisissons e = 7 (premier avec 20)
  • d = 3 car 3 × 7 ≡ 1 (mod 20)

Clé publique : (33, 7), Clé privée : 3

Pour chiffrer m = 2 : c ≡ 27 ≡ 29 (mod 33)

Pour déchiffrer : 293 ≡ 2 (mod 33)

4. Importance en Cryptographie

Le RSA est largement utilisé pour sécuriser les communications sur Internet, notamment pour :

Sécurité : La sécurité du RSA dépend de la taille des nombres premiers utilisés. Actuellement, des clés de 2048 bits ou plus sont recommandées pour une sécurité optimale.

5. Limites et Considérations

Exercices sur le RSA