Chiffre de Rabin Chiffre de RabinChapitre: |
XV. Cryptographie moderne | Prérequis: |
Arithmétique modulo m, algorithme d'Euclide étendu, théorème des restes chinois |
Le chiffre de Rabin offre une sécurité calculatoire équivalente au problème de la factorisation de n=pq. C'est un cryptosystème à clefs publiques.
Soit n le produit de deux nombres premiers distincts p et q tels que p et q soient congrus à 3 modulo 4 (nous verrons plus loin le pourquoi de cette condition). Soit le nombre B compris entre 0 et n-1. Le nombre chiffré y (compris entre 0 et n-1) s'obtient à partir du nombre clair x (compris entre 0 et n-1) par la formule:
 |
Inversement, le nombre clair x s'obtient à partir du nombre chiffré y par la formule:
 |
On notera que les opérations arithmétiques sont effectuées dans Zn, et que la division par 2 ou 4 est en fait la multiplication par 2-1 et 4-1 modulo n, respectivement.
Cette fonction de chiffrement n'est pas injective. Il existe en effet quatre nombres clairs qui peuvent se chiffrer en le même nombre chiffré. Le destinataire du message n'a aucun moyen pour distinguer le bon nombre parmi les quatre qu'il trouvera. On verra dans un exemple complet comment remédier à ce problème.
 |
 |
(en effet, d'après l'algorithme d'Euclide étendu, 4-1 mod 77 = 58 et 92·58 mod 77 = 1. De même, 2-1 mod 77 = 39 et 9·39 mod 77 = 43).
Calcul des quatre racines
Supposons que Bob (le destinataire) souhaite déchiffrer le message y = 22. Il faut donc trouver la racine carrée de 23 modulo 77, ce qui revient, comme le dit le théorème des restes chinois, au même que trouver la racine carrée de 23 modulo 7 et la racine carrée de 23 modulo 11. C'est ici qu'intervient le fait que p et q doivent être congrus à 3 modulo 4. En effet, dans ce cas, il existe une formule simple:
| Si p mod 4 = 3, alors la solution de
|
On va donc calculer:
Il ne reste qu'à résoudre le système d'équations ci-dessous avec le théorème des restes chinois:
On calcule successivement:
67 est donc la première des 4 racines carrées de 23 modulo 77. Les trois autres racines carrées se trouvent en résolvant le système (*) avec respectivement a1 = -4 et a2 = 1, a1 = 4 et a2 = -1, et enfin a1 = -4 et a2 = -1. Vous pourrez vérifier en exercice qu'elles valent respectivement 45, 32 et 10.
Finalement, les quatre nombres clairs possibles sont :
Vérifiez en exercice que ces quatre nombres se chiffrent en 22.
Vous trouverez sur la page suivant un exemple complet de chiffrement et déchiffrement.
 Didier Müller, 1.11.01 |
  |