Chiffre de Rabin Chiffre de RabinPré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.
| Alphabet | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | * |
| Codes | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
Rappelons que 4 textes clairs correspondront au texte chiffré que recevra le destinataire. Afin qu'il puisse facilement retrouver le bon, le symbole * débutera chaque bloc de texte.
Nous utiliserons des blocs de quatre caractères et pour simplifier, nous avons choisi B = 0. Avec ces choix, le plus grand nombre possible est *ZZZ=26252525. Nous devons choisir n plus grand que cela, et, de plus, n doit être le produit de deux nombres premiers congrus à 3 modulo 4. Soient p = 6911 et q = 6947 (on peut vérifier que p et q sont deux nombres premiers de la forme 4 k + 3). Ces deux valeurs sont la clef privée et ne doivent pas être rendues publiques. On calcule ensuite que n = 6911·6947=48010717.
Les valeurs n = 48010717 et B = 0 constitue la clef publique que l'envoyeur utilisera pour chiffrer son message.
 |
Alice désire envoyer un message secret à Bob. Ce dernier lui a fait connaître ses clefs publiques et elle va les utiliser pour chiffrer le texte suivant:
Elle le décompose d'abord en blocs de trois caractères chacun,
puis elle marque chacun des blocs en ajoutant le symbole * au début de chaque bloc:
puis les caractères sont convertis en leurs équivalents numériques (les zéros sont importants):
Elle chiffre d'abord le premier bloc: C1 = 260904192 mod 48010717 = 46850914
Le deuxième bloc est chiffré comme suit: C2 = 260008122 mod 48010717 = 5842871
Et le troisième ainsi: C3 = 260410102 mod 48010717 = 12031786
Le message chiffré transmis par Alice est la suite de nombres:
 |
Bob, qui n'a communiqué à personne sa clef privée, à savoir les deux nombres p = 6911 et q = 6947, sera le seul à pouvoir déchiffrer le message (bien sûr, dans notre exemple, n = 48010717 est facilement factorisable en n=6911·6947; en réalité, nous utiliserions des tailles de blocs beaucoup plus grandes et des nombres premiers beaucoup plus grands).
Pour déchiffrer le premier bloc, Bob doit résoudre la congruence
D'après le théorème des restes chinois, résoudre l'équation ci-dessus revient à résoudre le système d'équations:
Il va donc calculer tout d'abord les racines carrées (par exemple avec la fonction Mathematica PowerMod):
Il ne lui reste plus qu'à résoudre, avec le théorème des restes chinois:
Pour cela, il calcule successivement:
Il obtient donc les quatre nombres clairs:
La bonne valeur est celle qui commence par 26, donc 26090419. Une fois décodé, ce nombre donne les lettres *JET.
En procédant de la même façon avec les deux derniers blocs, il retrouvera le message complet. Essayez!
 Didier
Müller, 27.1.21 |
  |