Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Système RSA

Posté par
Miguel56
22-06-20 à 18:03

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

Posté par
Miguel56
re : Système RSA 22-06-20 à 23:25

Quelqu'un pourrait-il y jeter un œil ?

Posté par
fenamat84
re : Système RSA 23-06-20 à 10:23

Bonjour,

1) et 2) Normalement, les clés publiques et privées du codage RSA sont des couples et non des triplets...
Ici la clé publique est (n,e) avec (n=pq appelé module de chiffrement et e l'exposant de chiffrement). Donc la clé publique d'Alice est (583,3).
De même, la clé privée est (n,d) avec d appelé exposant de déchiffrement tel que ed1[(n)] (avec (n)=(p-1)(q-1) = 520).
Donc la clé privée d'Alice est (583,387), ce qui est ok.

3) Chiffrement du message de Bob :
Une erreur de calcul...

Citation :
3 442 951≡36[583]
Je ne trouve pas 36...
Sinon le reste est ok.

Je regarde si ton déchiffrement est correct... même si ton résultat JEVOUMRIME me paraît plutôt bizarre comme message...

Posté par
Miguel56
re : Système RSA 23-06-20 à 13:19

D'accord, parfait ! Merci pour votre aide en tout cas.
Pour le déchiffrage, on trouve normalement JEVOUSAIME avec e=7 (il me semble). Or, notre prof a changé cette valeur de e et lui a attribué la valeur de 3... Je trouve donc JEVOUMRIME

Posté par
Miguel56
re : Système RSA 23-06-20 à 13:22

Ah oui autant pour moi, je trouve 3 442 951=336[583]. Erreur bête de ma part

Posté par
Miguel56
re : Système RSA 23-06-20 à 13:25

Pour la clé publique, je l'avais écrite de cette manière car dans la méthode donnée par notre prof, elle est présentée ainsi.

Voici la méthode donnée :

Alice choisit deux nombres premiers 𝑝 et 𝑞 . Puis elle calcule 𝑛 = 𝑝 × 𝑞.
Elle choisit un entier naturel 𝑒 tel que PGCD(𝑒, (𝑝 − 1)(𝑞 − 1)) = 1 avec 1 < 𝑒 < (𝑝 − 1)(𝑞 − 1).
Elle publie sa clé : (RSA,𝒏, 𝒆), c'est la clé publique d'Alice.
Elle détermine sa clé privée, 𝒅, l'unique entier tel que 𝑒 × 𝑑 ≡ 1[(𝑝 − 1)(𝑞 − 1)] avec 1 < 𝑑 < (𝑝 − 1)(𝑞 − 1).
Bob veut envoyer un message à Alice, il va dans l'annuaire et constate que la clé publique d'Alice est (RSA, 𝑛, 𝑒).
IL code chaque nombre 𝑎 de son message de la façon suivante : 𝑎𝑒[𝑛]. Et il envoie à Alice.
Alice reçoit le message de Bob, elle décode chaque nombre 𝑏 du message de la façon suivante : 𝑏𝑑[𝑛]

Posté par
Miguel56
re : Système RSA 23-06-20 à 13:27

Pardon, c'est a^e[n] et b^d[n].

Posté par
Miguel56
re : Système RSA 23-06-20 à 15:28

Avez-vous pu vérifier le décodage ?

Posté par
Miguel56
re : Système RSA 23-06-20 à 18:48

?

Posté par
Miguel56
re : Système RSA 24-06-20 à 09:57

Bon...

Posté par
fenamat84
re : Système RSA 24-06-20 à 10:20

Oui, désolé, j'étais occupé ces temps ci.

Oui, du coup, tes calculs de congruences sont justes. Même si le message d'arrivée est plutôt bizarre... JEVOUMRIME...

Posté par
Miguel56
re : Système RSA 24-06-20 à 11:01

D'accord ! Parfait merci beaucoup !
A bientôt !
Miguel

Posté par
flight
re : Système RSA 24-06-20 à 13:38

salut

plutot  Alice recevra comme séquence de nombres : 008 336 489 399 138.

Posté par
flight
re : Système RSA 24-06-20 à 13:52

et il manque un bloc dans ton decryptage , celui en gras 417 105 557 052 318 335 347.

Posté par
flight
re : Système RSA 24-06-20 à 14:06

finalement non , le bloc 318 est bien traité  , par contre dans la sequence , 417 105 557 052 318 335 347  il doit y avoir une erreur , si bob  avait anvoyé à Alice "je vous aime"
on partirait de la séquence 10 05 22 15 21 19 01 09 13 05 puis regroupé par bloc de 3  depuis la droite cela donnerai :  010  052  215 211 901 091 305  puis ensuite crypté qui donne finalement 417  105  557  052  318  335  347

Posté par
Miguel56
re : Système RSA 24-06-20 à 14:19

Bonjour, oui après avoir corrigé mon erreur signalée plus haut, je trouve bien comme séquence : 008 336 489 399 138 pour la 3).

Par contre pour la dernière question, on part bien de 417 105 557 052 318 335 347... Je viens de vérifier l'énoncé. En fait, si nous avions utilisé e=7 au lieu de e=3, cette séquence donnerait bien 'JEVOUSAIME'... Il me semble que le soucis provient de là. En effet, notre avait changé la valeur de e et lui a donné comme valeur 3 par rapport à l'énoncé initial.

Posté par
Miguel56
re : Système RSA 24-06-20 à 14:22

Et puis je viens de vérifier : si on part de 10 05 22 15 21 13 18 09 13 05 (résultat obtenu suite au décryptage), qu'on les regroupe par la droite on obtient 010 052 215 211 318 091 305 et une fois cryptés on retombe bien sur 417 105 557 052 318 335 347, la séquence de l'énoncé.

Posté par
fenamat84
re : Système RSA 24-06-20 à 18:51

Oui, bien sûr si la valeur de e change, la séquence de décryptage n'est plus la même...

Après que ce soit avec e=7 ou e=3, la méthode de calcul de congruences reste semblable.

Finalement, avec e=7, on arrive déjà à un message qui semble plus cohérent !   

Posté par
Miguel56
re : Système RSA 24-06-20 à 19:54

Donc ce que j'ai fait est bon ?
Merci encore.

Posté par
Miguel56
re : Système RSA 24-06-20 à 19:56

Sachant que e=3 d'après l'énoncé ?

Posté par
fenamat84
re : Système RSA 24-06-20 à 20:23

Après il se peut qu'il y ait eu une erreur d'énoncé.
Ce serait e=7 au lieu de e=3...
Après tes calculs pour e=3 sont justes, il n'y a rien à dire.

Posté par
Miguel56
re : Système RSA 24-06-20 à 20:48

D'accord. Merci beaucoup !
Miguel



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !