Bonjour à toi, tout d'abord merci de prendre le temps de me lire car j'ai vraiment besoins d'aide. J'ai eu besoins de chiffrer un message important afin de l'envoyer à un destinataire récurrent, et c'est là que j'ai commencé à m’intéresser au chiffrement RSA. Sans te mentir, j'ai passé une bonne partie de mon après-midi à faire un calcul qui est fait en 2 secondes dans le cours OpenClassrooms .. J'ai réussi l'ensemble des étapes du cours sauf une, et pas des moindres, déterminer "d". Le cours nous donne une formule 'toute simple' qui permet de le déterminer, sauf que lorsque je la réalise, je trouve absolument pas le même résultat que l'auteur du cours (son résultat étant le bon et moi le faux car le miens ne fonctionne pas.) Voilà la formule :
Avec e=565 et φn=282124 (pour ceux qui ce demande '%' signifie 'modulo', c'est une opération qui permet de calculer le reste d'une division euclidienne)
Le fait étant que lorsque je fait le calcul, je trouve :
d=0,00176991150442477876106194690265
Comme dit précédemment, le résultat qui me permet d'avancer est celui du cours (d=140313) et le mien ne fonctionne pas, je ne trouve vraiment pas mon erreur ..
En me baladant sur d'autre site j'ai trouvé une équation qui apparemment me permettrait de déterminer 'd', sauf que cette fois-ci elle utilise les congruences, et j'ai beau savoir ce que c'est, je n'arrive pas à la résoudre non plus :
Voilà tout, si quelqu'un à compris mon erreur de calcul, sait comment résoudre l'équation ci-dessus ou encore connait une méthode afin de trouver 'd', je vous écoute
Hello, Tu as calculé littéralement : 1÷565 Or le calcul doit être réalisé modulo 282124. Ce qui veut dire : - on cherche un nombre entier, pas décimal - on cherche d tel que d*565 = 1 [282124] (en français : d fois 565 est congru à 1 modulo 282124), c'est-à-dire qu'il existe un entier k tel que : d*565 = 1 + k*282124.
Je ne suis pas calé niveau RSA, donc je ne sais pas comment ce d se calcule en pratique. Mais au moins, tu devrais avoir compris ton erreur
Merci pour ta réponse rapide, ce que tu dis me rappelle effectivement les cours de congruence modulo, mais ça ne change pas le problème que 'd' reste un inconnu
A partir de là comment je fait pour trouver 'd' ?
J'en profite pour poster un autre calcul que je n'arrive pas à comprendre, celui là est plus simple ; lorsque je réalise le calcul de mon côtés je ne trouve pas du tout le même résultat ...
Dans le cours, ils trouvent ça : 80488140313 % 283189 = 72
Et avec ma calculatrice, je trouve ça : 80488140313 % 283189 = 162 733
Si il y a des personnes qui sont coincée sur l'histoire de la formule pour déterminer 'd', en attendant, j'ai trouvé ce site qui exécute le calcul de lui-même lorsque vous rentré les autre infos, mais j'aimerais bien comprendre pourquoi quand je fait le calcul de mon côté ça ne fonctionne pas
ce que tu dis me rappelle effectivement les cours de congruence modulo, mais ça ne change pas le problème que 'd' reste un inconnu
Edité par Lucas_Tami il y a environ 12 heures
tu as dû sauter le chapitre sur l'algorithme d'Euclide étendu ! à la base de la recherche de nombres vérifiant la relation de Bezout \(au+bv =PGCD(a,b)\) donc 1 si \((a,b)\) sont premiers entre eux. Donc ici "l'inconnue" \(d\) vérifie cette relation \(du+nv =1\) et on trouve bien \(d= 140313\)
Pour essayer de comprendre le contenu du chapitre du tuto ici, il faut lire à mon avis la suite y compris l'annexe maths , si on a un peu oublier l'arithmétique modulaire '(mais les rappels du tuto me semblent inexistants pour l' algorithme de recherche des coefficients de Bezout .Le plus efficace est d'exprimer la succession des divisions euclidiennes sous forme matricielle et une relation de Bezout "tombe comme un fruit mûr" par produit matriciel !
\(a=bq+r\)
\(b=rq1+r1\)
\(r=r1q2 +r2\)
etc.. on poursuit jusqu'à un reste nul ( la suite des r étant strictement décroissante, on arrive nécessairement à un reste nul ; le dernier reste non nul est le PGCD, qui vaut 1 si les nombres de départ sont premiers entre eux)
Si on écrit matriciellement la suite de divisions avec la matrice \([0,1;1,-q]\) reliant deux couples successifs , q quotient de chaque division, on peut montrer que la deuxième ligne du produit de ces matrices 2*2 successives donne les coefficients de Bezout, d'où \(d\).
Pour ce qui est des divisions modulo que tu ne comprends pas , c'est effectivement incompréhensible si on ne sait pas que les congruences de l'algo RSA portent sur des puissances modulaires ! et non sur les entiers bruts affichés ici . Je m'explique:
Lorsque on veut chiffrer , selon un exemple du tuto, le code ASCII c=072 avec e=565 , le tuto écrit 072565 % 283189 =80488 ; 80488 n'est évidemment pas le reste de la division des deux nombres considérés.
En fait dans le chiffrage 80488 n'est pas le modulo de 072565. mais celui de \(c^e\) . Ce sont des exponentielles modulaires qu'il faut considérer . Je n'ai pas lu le tuto en détail, mais cela ne semble dit nulle part, ce qui me parait un peu gros si c'est bien le cas ! Il faut se rendre à l'annexe maths( "sous une frite" !) ou dans le code Python pour voir que ce sont bien des puissances qui interviennent :
# On chiffre la lettre ou plutôt son code ASCII
lettre_crypt = pow(ascii,e)%n
les nombres sont astronomiques mais avec ma calculette , cela passe encore avec l'exposant 565 et on trouve bien 80488 comme chiffrage de 72 !
Même problème pour le déchiffrage:dans l'opération inverse 80488140313 représente la juxtaposition de \( c_{crypt}\) et de \(d\) et évidemment le déchiffrage doit nous redonner 72 qui est en fait le résultat de 72 = pow(lettre_crypt ,d)%n. pow(lettre_crypt ,d) est astronomique et le calcul coince avec une simple calculette ! A mon avis, une façon de s'en sortir est d'utiliser l’exponentiation modulaire où on convertit l'exposant en binaire Voir https://fr.wikipedia.org/wiki/Exponentiation_modulaire ( j'ignore si le module traitant les grands nombres de Python suffit, en tout cas le tuto n' a pas l'air de se préoccuper du calcul modulaire de ces grandes puissances )
on peut trouver des explications complémentaires sur l’arithmétique du RSA dans la version anglaise de wiki plus complète que la française.
ce que tu dis me rappelle effectivement les cours de congruence modulo, mais ça ne change pas le problème que 'd' reste un inconnu
Edité par Lucas_Tami il y a environ 12 heures
tu as dû sauter le chapitre sur l'algorithme d'Euclide étendu ! à la base de la recherche de nombres vérifiant la relation de Bezout \(au+bv =PGCD(a,b)\) donc 1 si \((a,b)\) sont premiers entre eux. Donc ici "l'inconnue" \(d\) vérifie cette relation \(du+nv =1\) et on trouve bien \(d= 140313\)
Pour essayer de comprendre le contenu du chapitre du tuto ici, il faut lire à mon avis la suite y compris l'annexe maths , si on a un peu oublier l'arithmétique modulaire '(mais les rappels du tuto me semblent inexistants pour l' algorithme de recherche des coefficients de Bezout .Le plus efficace est d'exprimer la succession des divisions euclidiennes sous forme matricielle et une relation de Bezout "tombe comme un fruit mûr" par produit matriciel !
\(a=bq+r\)
\(b=rq1+r1\)
\(r=r1q2 +r2\)
etc.. on poursuit jusqu'à un reste nul ( la suite des r étant strictement décroissante, on arrive nécessairement à un reste nul ; le dernier reste non nul est le PGCD, qui vaut 1 si les nombres de départ sont premiers entre eux)
Si on écrit matriciellement la suite de divisions avec la matrice \([0,1;1,-q]\) reliant deux couples successifs , q quotient de chaque division, on peut montrer que la deuxième ligne du produit de ces matrices 2*2 successives donne les coefficients de Bezout, d'où \(d\).
Pour ce qui est des divisions modulo que tu ne comprends pas , c'est effectivement incompréhensible si on ne sait pas que les congruences de l'algo RSA portent sur des puissances modulaires ! et non sur les entiers bruts affichés ici . Je m'explique:
Lorsque on veut chiffrer , selon un exemple du tuto, le code ASCII c=072 avec e=565 , le tuto écrit 072565 % 283189 =80488 ; 80488 n'est évidemment pas le reste de la division des deux nombres considérés.
En fait dans le chiffrage 80488 n'est pas le modulo de 072565. mais celui de \(c^e\) . Ce sont des exponentielles modulaires qu'il faut considérer . Je n'ai pas lu le tuto en détail, mais cela ne semble dit nulle part, ce qui me parait un peu gros si c'est bien le cas ! Il faut se rendre à l'annexe maths( "sous une frite" !) ou dans le code Python pour voir que ce sont bien des puissances qui interviennent :
# On chiffre la lettre ou plutôt son code ASCII
lettre_crypt = pow(ascii,e)%n
les nombres sont astronomiques mais avec ma calculette , cela passe encore avec l'exposant 565 et on trouve bien 80488 comme chiffrage de 72 !
Même problème pour le déchiffrage:dans l'opération inverse 80488140313 représente la juxtaposition de \( c_{crypt}\) et de \(d\) et évidemment le déchiffrage doit nous redonner 72 qui est en fait le résultat de 72 = pow(lettre_crypt ,d)%n. pow(lettre_crypt ,d) est astronomique et le calcul coince avec une simple calculette ! A mon avis, une façon de s'en sortir est d'utiliser l’exponentiation modulaire où on convertit l'exposant en binaire Voir https://fr.wikipedia.org/wiki/Exponentiation_modulaire ( j'ignore si le module traitant les grands nombres de Python suffit, en tout cas le tuto n' a pas l'air de se préoccuper du calcul modulaire de ces grandes puissances )
on peut trouver des explications complémentaires sur l’arithmétique du RSA dans la version anglaise de wiki plus complète que la française.
Merci beaucoup pour ta réponse, cela fait une bonne heure maintenant que je me renseigne sur tout ces nouveaux nom mathématiques et globalement, j'ai compris (je crois?)
Pour ce qui est du chiffrement je l'ai pas notifié dans mon message mais j'avais effectivement vue que l'auteur du cours avait fait une erreur similaire, mais en fouillant sur d'autre sites, j'ai trouvé la formule que tu a rédigé. Par contre pour le décodage .. Effectivement la formule est colossale et ne peut être calculé dans un temps raisonnable, je me suis donc intéressé à cette méthode d'exponentiation modulaire (merci wikipédia) et en gros, ce que j'ai compris, c'est que l'exponentiation modulaire est une méthode qui me permet de résoudre un calcul sous forme 'pow(lettre_crypt ,d)%n' plus rapidement, or, la forme du calcul que tu as écrit plus haut a un 'n' qui est juxtaposé à 'pow(lettre_crypt ,d)'
La formule que je souhaite utilisé [pow(lettre_crypt ,d)%n. pow(lettre_crypt ,d)] n'a donc pas la même forme que 'pow(lettre_crypt ,d)%n' qui me permettrait d'utiliser l'exponentiation modulaire
Je pense avoir, encore une fois , avoir loupé un truc ..
Je pense que mon erreur viens de là : Pour moi, [pow(lettre_crypt ,d)%n. pow(lettre_crypt ,d)] signifie (si on remplace par les données du cours) 80488^140313%28318980488^140313. Peut être que j'ai mal compris ta formule ?
Encore merci de bien vouloir m'aider car je galère sévère
Même problème pour le déchiffrage:dans l'opération inverse 80488140313 représente la juxtaposition de \( c_{crypt}\) et de \(d\) et évidemment le déchiffrage doit nous redonner 72 qui est en fait le résultat de 72 = pow(lettre_crypt ,d)%n. pow(lettre_crypt ,d) est astronomique et le calcul coince avec une simple calculette ! A mon avis, une façon de s'en sortir est d'utiliser l’exponentiation modulaire où on convertit l'exposant en binaire Voir https://fr.wikipedia.org/wiki/Exponentiation_modulaire
euh,...il me semble qu'il y a un gros malentendu sur ce que j'ai écrit: 72 = pow(lettre_crypt ,d)%n . pow(lettre_crypt ,d) n'est pas une même formule Le point . n'est pas multiplicatif mais un séparateur de deux phrases !! et la formule à considérer pour le déchiffrage est bien simplement 72 = pow(lettre_crypt ,d)%n , si c'est ton interrogation ( ... bizarre quand même si c'est seulement cela, il ne me semble pas qu'il y ait une grosse ambiguïté, sauf à mal comprendre la démonstration qui fait intervenir la puissance de \(e\) ou de \(d\).
)
L'exemple numérique détaillée de la version anglaise de Wiki est clair, il me semble.
- Edité par Sennacherib 28 juillet 2019 à 12:46:58
tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
Même problème pour le déchiffrage:dans l'opération inverse 80488140313 représente la juxtaposition de \( c_{crypt}\) et de \(d\) et évidemment le déchiffrage doit nous redonner 72 qui est en fait le résultat de 72 = pow(lettre_crypt ,d)%n. pow(lettre_crypt ,d) est astronomique et le calcul coince avec une simple calculette ! A mon avis, une façon de s'en sortir est d'utiliser l’exponentiation modulaire où on convertit l'exposant en binaire Voir https://fr.wikipedia.org/wiki/Exponentiation_modulaire
euh,...il me semble qu'il y a un gros malentendu sur ce que j'ai écrit: 72 = pow(lettre_crypt ,d)%n . pow(lettre_crypt ,d) n'est pas une même formule Le point . n'est pas multiplicatif mais un séparateur de deux phrases !! et la formule à considérer pour le déchiffrage est bien simplement 72 = pow(lettre_crypt ,d)%n , si c'est ton interrogation ( ... bizarre quand même si c'est seulement cela, il ne me semble pas qu'il y ait une grosse ambiguïté, sauf à mal comprendre la démonstration qui fait intervenir la puissance de \(e\) ou de \(d\).
)
L'exemple numérique détaillée de la version anglaise de Wiki est clair, il me semble.
- Edité par Sennacherib il y a environ 4 heures
Effectivement j'avais pas pris en compte le point pour résumer, la formule est pow(lettre_crypt ,d)%n ; Mais lorsque j'augmenterais la sécurité, il sera difficile d'effectuer le calcul avec une calculatrice classique, pour cela je dois utilisés une méthode. En me baladant sur le wiki anglais de RSA, j'ai trouvé cette ensemble de formule :
To decrypt c = 2790, we calculate
{\displaystyle m=2790^{413}{\bmod {3}}233=65}
Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real-life situations the primes selected would be much larger; in our example it would be trivial to factor n, 3233 (obtained from the freely available public key) back to the primes p and q. e, also from the public key, is then inverted to get d, thus acquiring the private key.
Practical implementations use the Chinese remainder theorem to speed up the calculation using modulus of factors (mod pq using mod p and mod q).
The values dp, dq and qinv, which are part of the private key are computed as follows:
Si j'ai bien compris, étant donner que le calcul est trop important, la page nous recommande de se servir du "Chinese remainder theorem", j'ai commencer à le réaliser sauf que une fois de plus, un calcul est faux (d'après moi). Le problème est à cette ligne : "qinv = pow (q, -1) mod p = pow(53, -1) mod 61 = 38"
Je vous laisse effectuer le calcul "pow(53, -1) mod 61" ; Personellement je trouve 1/53, ce qui n'a rien a voir avec 38 ..
Alors, cette fois-ci c'est encore une erreur de ma part ou c'est le wiki qui est mal écrit ?
Si la formule ne fonctionne pas ou quoi, est ce que quelqu'un peut me trouver un moyen pour passer de 80488 à 72 avec une calculatrice scientifique en prenant en compte le fait que je possède la clé privée
Je vous laisse effectuer le calcul "pow(53, -1) mod 61" ; Personellement je trouve 1/53, ce qui n'a rien a voir avec 38 ..
Alors, cette fois-ci c'est encore une erreur de ma part ou c'est le wiki qui est mal écrit ?
Il semble que c'est la même erreur que dans le premier post.
Ce qu'il faut calculer c'est l'inverse modulaire et non l'inverse arithmétique \(\frac{1}{53}\)! Je suis quand même un peu surpris. Tu t'attaques à des choses (relativement ) compliquées et tu sembles bloquer sur des calculs assez élémentaires d'arithmétique modulaire. Et je ne vois pas trop comment tu peux maîtriser le théorème des restes chinois si tu ne sais pas calculer un inverse modulaire.
Et l'inverse modulaire (modulo 61) de 53, c'est bien 38 comme l'indique Wiki. On peut vérifier que 53x38= 2014 et que 2014 est bien congru à 1 (modulo 61).
rappel: l'inverse modulaire de 53 est le nombre \(a\) qui vérifie \( 53.a \equiv 1 [mod(61)]\)
Pour trouver cet inverse modulaire, soit on recherche les coefficients de Bezout selon la méthode que j'ai esquissée dans un post précédent .
Ici la relation de Bezout est 38x53 -34x61 =1 , soit on utilise le théorème d'Euler entre deux nombres premiers entre eux a,n qui nous dit que : \(a^{\varphi(n)}\equiv 1 mod[n]\), \(\varphi(n)\) étant l'indicatrice d'Euler. Donc \(a^{-1}\equiv a^{\varphi(n)-1} mod[n]\),
\(n=61\) étant premier , on a simplement \(\varphi(n)=n-1\) d'où \(a^{-1}\equiv a^{n-2} mod[n]\),
Donc l'inverse modulaire est \( 53^{59} mod[61]\),qui vaut bien 38.
- Edité par Sennacherib 29 juillet 2019 à 15:41:36
tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
J'ai l'impression que mon énoncé est faux ...
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Mon portfolio photo : https://www.instagram.com/charlievanaret_photo/