Methode RSA

[Electrique17]

Bonjour,

Je bloque sur l'exercice de Maths suivant sur la méthode RSA. Pouvez-vous m'aider à le résoudre svp :

Je souhaite vous communiquer le numéro de la rue de votre futur appartement sous forme cryptée, `a l’aide de la méthode RSA. Pour cela, vous m’avez communiqué votre clé publique : (29, 91).

1. Malheureusement, vous avez oublié votre clé privée. Saurez-vous la retrouver malgré tout ?
2. Voici le numéro de la rue sous forme cryptée : 76. Quelle est donc votre numéro de rue ?

Merci d'avance pour tout piste.
-----

[eudea-panjclinne]

La méthode RSA est très technique, vous avez vraisemblablement un cours la-dessus. Pourquoi ne le reprendriez-vous pas pour le comprendre et faire votre exercice !

[sylvainc2]

1) il faut factoriser le modulo public 91=pq où p et q sont des nombres premiers. Ensuite il faut calculer d = 29^-1 mod (p-1)(q-1). On peut aussi faire d = 29^-1 mod ppcm(p-1,q-1). Il n'y a pas qu'une seule valeur de d qui va marcher modulo 91, les autres sont de la forme d + k*ppcm(p-1,q-1) mod 91.

2) tu calcules 76^d mod 91.

[Electrique17]

Merci beaucoup Sylvainc2. J'essaie d'appliquer ta démarche.

[A voir en vidéo sur Futura]

[Electrique17]

Bonjour de nouveau,

@Sylvainc2, j'ai une question.
D'habitude la clé publique est notée (n,e). Donc, dans mon exercice: n=29 et e=91.
Ma question : pourquoi dans ta réponse, tu considères que n=91 (puisque tu as mis que 91=p.q) et e=29.

Merci d'avance de toute réponse.

[Electrique17]

Bonjour,

J'ai compris le raisonnement et la logique. Je dois faire les calculs maintenant.

Pouvez-vous me donner une indication sur comment faire pour factoriser le modulo public 91=pq où p et q sont des nombres premiers (voir le message de Sylvainc2 ci-dessus). En effet, je dois trouver p et q pour pouvoir passer à l'étape suivante mais je ne vois pas trop comment. J'ai essayé le petit théorème de Fermat mais je ne suis pas sûr que c'es la bonne méthode.

Désolée, je débute avec les Maths....

Merci d'avance

[gg0]

Bonjour.

Une méthode évidente pour factoriser est d'essayer de diviser par 2, puis 3, puis 5 ...le premier diviseur sera automatiquement premier. Le quotient aussi puisque 91 est le produit de 2 premiers.

Cordialement.

[Electrique17]

Merci beaucoup de votre aide. J'ai suivi vos indications et j'ai résolu l'exercice (après 3 heures de bataille...!). Ainsi en réponses aux deux questions, j'ai trouvé :

1. p= 7, q=13, Clé privé = 76

2. numéro de la rue (ou message déchiffré) : 20

N'hésitez pas à me demander les calculs si vous voulez.

Bonne journée à tous.