Introduction au chiffrement asymétrique RSA

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Clé publique (n, e) avec n = pq ; clé privée d telle que ed 1 (p - 1)(q - 1). • Chiffrement : C M^e n ; déchiffrement : M C^d n, avec 0 M < n. • d s'obtient par l'algorithme d'Euclide étendu appliqué à e et (p - 1)(q - 1). • La sécurité repose sur la difficulté de factoriser n quand p et q sont très grands.

Le cours

1. Principe du chiffrement asymétrique Dans le protocole RSA, chacun publie une clé publique (n, e) qui sert à chiffrer, et garde une clé privée d qui sert à déchiffrer. La sécurité repose sur la difficulté de factoriser n = pq lorsque p et q sont de très grands nombres premiers. 2. Fabrication des clés 1. Choisir deux nombres premiers distincts p et q ; calculer n = pq et (n) = (p - 1)(q - 1). 2. Choisir un exposant public e tel que PGCD(e, (n)) = 1. 3. Calculer la clé privée d, inverse de e modulo (n) : ed 1 (n), grâce à l'algorithme d'Euclide étendu (Bézout). 3. Chiffrer et déchiffrer C M^e n M C^d n (0 M Idée de la preuve : ed = 1 + k(n). Le petit théorème de Fermat donne M^ed M modulo p et modulo q ; comme p et q sont premiers entre eux, pq = n divise M^ed - M. 4. Attention La clé privée d est un inverse modulo (n), pas modulo n. Et (n) doit rester secret : connaître n et (n) permet de retrouver p + q = n - (n) + 1, donc p et q.

Dans ce chapitre