Forum de mathématiques - Bibm@th.net

jeavieve

Membre

Inscription : 08-01-2008

Messages : 14

calcul RSA avec exposant de déchiffrage négatif

Bonjour,
En faisant une petite application manuelle, 'pour voir ', je bloque sur le calcul du déchiffrage RSA lorsque l'exposant de déchiffrage est négatif. Par exemple avec n=25 e=3 et n=25 d=-5 si mon message M est 4 ,  le message codé est C= 14  et  avec  14exp-5 mod25 je décode M=24. j'utilise pour le calcul l'inverse de 14 mod25 qui est, sauf erreur, 9 que j'élève à la puissance 5 mod25. Même résultat si j'inverse 14exp5mod25.
Je n'ai pas rencontré de difficulté avec les exposants positifs.
Je fais donc une erreur en calculant l'exponentielle modulaire négative, mais où? je n'ai pas trouvé d'exemple de calcul manuel sur le web pour savoir comment faire. Pourriez vous me donner un exemple?
Merci de votre aide.
Bonne Année à toutes et tous.

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : calcul RSA avec exposant de déchiffrage négatif

Salut,

A moins que tu utilises une application qui fait du calcul dans les anneaux Z/nZ, le problème que tu rencontres est assez logique.
En effet, j'imagine que tu fais tes calculs dans Z puis que tu prend le modulo. Mais alors, 14^(-5) .. c'est plus dans Z, ça ne peut pas marcher.
La solution consiste à toujours te ramener à un exposant positif "équivalent" (c'est à dire qui te donnera les mêmes résultats)
Et cet exposant est un réprésentant positif de d mod (p-1)(q-1)  (ce que te donne l'instruction "mod" de n'importe quel langage de programation).

Dans ton exemple  : n=25, donc p=q=5
il suffit de prendre à la place de d=-5 la valeur suivante : d = -5 mod 16 = 11
Tu obtiendras normalement les mêmes résultats théoriques, (tu peux vérifier qu'on a toujours : d*e = 1 (mod 16))
mais surtout, les bons résultats pratiques.

Cordialement
++

Dernière modification par Barbichu (08-01-2008 18:13:45)

---

Barbichu

jeavieve

Membre

Inscription : 08-01-2008

Messages : 14

Re : calcul RSA avec exposant de déchiffrage négatif

Merci Barbichu,
C'était là effectivement mon erreur. Tout va bien maintenant!
Cordialement

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : calcul RSA avec exposant de déchiffrage négatif

Désolé,
en relisant ton message (ce que je n'avais pas fait en entier, c'est très mal) je m'appeçois que j'ai répondu complètement à coté de la plaque !!
Je ne sais pas pourquoi, j'ai pensé que tu faisais un programme, bref ... n'importe quoi ...

Et j'ai raconté n'importe quoi. Bref, le problème est que p=q !
On a alors phi(n) = p² - p = 25-5 = 20 et non (p-1)(q-1)=16 !
L'algo de RSA ne marche alors plus (je me demande comment ça peut marcher avec les exposants positifs :-/)

En le modifiant pour prendre d*e=1 mod (p²-p) ça marcherait. Que l'exposant soit positif ou négatif !

Désolé
++

---

Barbichu

jeavieve

Membre

Inscription : 08-01-2008

Messages : 14

Re : calcul RSA avec exposant de déchiffrage négatif

Mea culpa,  je n'aurai pas dû dire que ça marchait.
Avec d*e=1 mod 20 pour e=3 on a d=7. Le calcul de C exp7 mod25 de l'exemple soit 14 exp7 mod25 me redonne bien 4, le message de départ.
Ma réponse précédente était suite à un calcul de C exp 11mod25 soit 14exp11 mod25 qui me redonnait 14! (aurai-je encore fait une erreur de calcul?) que j'ai trop rapidement lu pour 4....en confondant M et C! dans ma précipitation.
Mais, si le RSA "tout fait" ne donne que n,e et n, d négatif , sans p,q ???
Cela veut-il dire qu'il faut en redemander un autre jusqu'à avoir un d positif pour pouvoir déchiffrer? c'est ce je crois comprendre maintenant. Je pensais a priori que la connaissance de n et d positif ou négatif suffisait, c'est pour ça que je m'étais lancé dans ce petit exercice.
Encore merci pour ton attention.
A+

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : calcul RSA avec exposant de déchiffrage négatif

Salut,
excuse moi, je n'ai pas été clair : la méthode que tu as utilisée pour calculer avec un d négatif marche très bien (c'était juste que j'avais mal compris ton problème et je te donnais une autre méthode), le problème était ailleurs.
Si ton "problme RSA" te fournit n,e,d. Alors en général n sera le produit de deux nombres premiers p et q distincts (donc aucun problème).
Mais si n=p², alors on voit tout de suite que n est un carré et le problème du décodage devient absurde (car on retrouve p facilement en prenant la racine carrée de n et on casse donc la clé de chiffrement)
J'espère que je ne t'ai pas embrouillé.
++

---

Barbichu

jeavieve

Membre

Inscription : 08-01-2008

Messages : 14

Re : calcul RSA avec exposant de déchiffrage négatif

Bonjour,
et bravo, oui bravo , j'ai mis le doigt sur un problème et tu as trouvé ce qui n'allait pas. Tout cela provient de l'applet Java RSA du sujet Cryptographie du site (chap. Méthodes modernes). Je viens de le vérifier. Pour une clé 7 bits on peut obtenir n=49, e=5 et...d=-7! évidement calculé avec le mauvais Phi. Avec Phi=p²-p d=17 et on déchiffre correctement.  Grâce à toi elle va pouvoir être corrigée. Je signale ce défaut aux administrateurs.

En tout cas, tu ne m'as pas embrouillé et j'étais aussi arrivé à la conclusion qu'il ne faut pas prendre n=p² qui aurait été une faiblesse.
Il faut dire que le petit défaut trouvé n'enlève rien à la qualité des sujets traités sur le site et à leurs outils pédagogiques que je découvre depuis peu.

Encore merci

Mllellll@

Invité

Re : calcul RSA avec exposant de déchiffrage négatif

J'ai la clé publique 17,3 ,8
Et le message M=3
Ma question c'est comment retrouver le message d'origine  s'il vous plait

Mllellll@

Invité

Re : calcul RSA avec exposant de déchiffrage négatif

J'ai la clé publique 119, 33
Et le message code M=3  il est question de décoder à l'aide de d qui est l'inverse de 33 dans z/96z sauf que 96 et 33 ne sont pas premiers entre eux donc comment faire

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 16 988

Re : calcul RSA avec exposant de déchiffrage négatif

Re,

La réponse que tu avais obtenue a été supprimée pendant que je la lisais...
A part son auteur, l'admin du site et moi-même personne ne peut le faire.

Il ressortait de son message que l'énoncé était incorrect...
Si son auteur l'a supprimé, il repassera sûrement la re-rédiger et compléter.

Patience.

     Yoshi
- Modérateur -

---

Arx Tarpeia Capitoli proxima...

Chrispaul

Membre

Inscription : 04-04-2020

Messages : 45

Re : calcul RSA avec exposant de déchiffrage négatif

Bonjour,

Un peu tardivement et avec mes excuses, voici une réponse à la question de Mlle llll@ :

Dans un chiffrement RSA, l’exposant public doit être premier avec p-1 et q-1. Il me paraît impossible d’avoir pour clé publique N= 119 et e = 33, puisque dans ce cas N = 7*17 et φ (N) = 6*16 = 96. Or 33 et 96 ont un facteur commun. Il y a donc une erreur d’énoncé.

Notons par ailleurs que  le choix de e est totalement libre, pourvu qu'il soit premier avec p-1 et q-1.
Mais il existe des standards et des choix qui accélèrent le chiffrement. Ce sont les valeurs de la forme 2^k + 1. Ces valeurs ne nécessitent qu'une multiplication en plus des élévations au carré pour calculer m^e. Les valeurs standard de la norme EMV (Europay Mastercard Visa) par exemple sont e = 3 ou e = 65 537 = 2^16 + 1.

Cordialement à tous.

Dernière modification par Chrispaul (27-11-2023 15:48:38)

Chrispaul

Membre

Inscription : 04-04-2020

Messages : 45

Re : calcul RSA avec exposant de déchiffrage négatif

Bonjour,

Pour compléter la publication précédente, précisons que l’on peut également déterminer d, l’exposant privé, en prenant le plus petit multiple commun à p-1 et q-1, au lieu d’utiliser φ(N) = (p-1) (q-1).

Exemple :

Soit les clés publiques N = 55 et e = 3. On a donc p = 5 et q = 11, soit p – 1 = 4 et q-1 = 10. Le ppcm de 4 et 10 est  20.

1) si l’on effectue l’inversion modulaire de e avec φ(N) = 40, on a : 3*d ≡  1 mod(40) ce qui donne d = 27

2) mais si l’on calcule avec le ppcm de 4 et 10, c’est à dire 20, on a : 3*d ≡  1 mod(20) ce qui donne d = 7

On constate que d, l’exposant de déchiffrement, est passé de 27 à 7, ce qui est logique puisque l’on travaille en modulo 20.

Vérification :

Supposons que l’on souhaite chiffrer M = 23.

Dans le 1er cas, on chiffre : 23³ mod (55) = 12, soit C = 12, puis on déchiffre 12^27 mod (55) = 23 et on retrouve M.

Dans le second cas, on chiffre 23³ mod(55) = 12, soit C = 12, puis on déchiffre 12^7 mod (55) = 23 et on retrouve également M.

Cette inversion modulaire avec le ppcm de p-1 et q-1 permet d’obtenir un exposant privé d plus petit et peut accélérer le déchiffrement, bien que le gain soit assez peu significatif pour des grandes valeurs de N.

Cordialement à tous.

Dernière modification par Chrispaul (02-12-2023 09:09:53)