Chiffre de Rabin (2) Chiffre de Rabin (2)Chapitre: |
XV. Cryptographie moderne | Prérequis: |
Chiffre de Rabin |
| 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, 1.11.01 |
  |