Bonjour,
J'ai un exercice à faire qui porte sur le système de codage RSA. Cependant, j'ai quelques doutes concernant mon travail.
Voici l'énoncé:
Alice veut créer une clé publique avec le système de codage RSA, pour cela elle choisit p=53, q=11 et e=3.
1) Déterminer la clé publique d'Alice.
2) Déterminer la clé privée d'Alice.
3) a) Bob veut lui envoyer un message, pour cela il remplace chaque lettre de l'alphabet par sa position, ainsi A est remplacé par 01, B par 02,... Ensuite il groupe les chiffres 3 par 3 en commençant par la droite, il obtient ainsi des blocs de 3 chiffres, en faisant attention que les nombres ainsi obtenus soit plus petits que n. Puis il code chaque bloc de 3 chiffres et envoie le message à Alice.
Il veut envoyer le message 'BONJOUR' à Alice, quelle séquence de nombre va-t-elle recevoir ?
b) Expliquer pourquoi il n'est pas très judicieux de faire des blocs de longueur 2 ?
4) Alice reçoit le message 417 105 557 052 318 335 347. Que veut lui dire Bob ?
Ce que j'ai fait :
1°) La clé publique d'Alice est : (RSA, n, e) avec n=p.q=583 et e=3, soit (RSA, 583, 3).
2°) On cherche d tel que 3d≡1[520], on s'aperçoit (à l'aide d'une feuille de calculs) que 3*347=1041 et 1041=2*520+1. Donc d=347 et la clé privée d'Alice est 347.
3°)
a) On attribue aux lettres suivantes leur position dans l'alphabet :
B=02
O=15
N=14
J=10
O=15
U=21
R=18
Soit 02 15 14 10 15 21 18.
Par la suite, on les regroupe en débutant par la droite: 002 151 410 152 118.
Puis :
• 2³=8[583]
• 151³=3 442 951 et 3 442 951≡36[583]
• 410³=68 921 000 et 68 921 000≡489[583]
• 152³=3 511 808 et 3 511 808≡399[583]
• 118³=1 643 032 et 1 643 032≡138[583]
Alice recevra comme séquence de nombres : 008 036 489 399 138.
b) Il n'est pas très judicieux de travailler avec des blocs de deux car le texte peut être déchiffré avec une analyse fréquentielle.
4°) Tentons de décoder le message reçu par Alice bloc par bloc :
• 417^347 : 417⁴≡122[583], (417⁴)⁵≡342[583], (417^20)⁴≡155[583], (417^80)⁴≡309[583] et comme 417^347=417^320 * 417^20 * 417⁴ * 417³ et 417³≡505[583], on en déduit 417^347≡309 * 342 * 122 * 505≡10[583].
• 105^347 : 105⁴≡372[583], (105⁴)⁵≡1[583], (105^20)⁴≡1[583], (105^80)⁴≡1[583] et comme 105^347=105^320 * 105^20 * 105⁴ * 105³ et 105³≡370[583], on en déduit 105^347≡1 * 1 * 372 * 370≡52[583].
• 557^347 : 557⁴≡487[583], (557⁴)⁵≡254[583], (557^20)⁴≡331[583], (557^80)⁴≡100[583] et comme 557^347=557^320 * 557^20 * 557⁴ * 557³ et 557³≡497[583], on en déduit 557^347≡100 * 254 * 487 * 497≡215[583].
• 52^347 : 52⁴≡213[583], (52⁴)⁵≡1[583], (52^20)⁴≡1[583], (52^80)⁴≡1[583] et comme 52^347=52^320 * 52^20 * 52⁴ * 52³ et 52³≡105[583], on en déduit 52^347≡1 * 1 * 213 * 105≡211[583].
• 318^347 : 318⁴≡265[583], (318⁴)⁵≡265[583], (318^20)⁴≡265[583], (318^80)⁴≡265[583] et comme 318^347=318^320 * 318^20 * 318⁴ * 318³ et 318³≡318[583], on en déduit 318^347≡265 * 265 * 265 * 318≡318[583].
• 335^347 : 335⁴≡152[583], (335⁴)⁵≡100[583], (335^20)⁴≡342[583], (335^80)⁴≡155[583] et comme 335^347=335^320 * 335^20 * 335⁴ * 335³ et 335³≡37[583], on en déduit 335^347≡155 * 100 * 152 * 37≡91[583].
• 347^347 : 347⁴≡526[583], (347⁴)⁵≡89[583], (347^20)⁴≡364[583], (347^80)⁴≡122[583] et comme 347^347=347^320 * 347^20 * 347⁴ * 347³ et 347³≡62[583], on en déduit 347^347≡122 * 89 * 526 * 62≡305[583].
On a donc au final: 010 052 215 211 318 091 305 , soit 10 05 22 15 21 13 18 09 13 05 , soit JEVOUMRIME.
Merci pour votre aide.
Miguel