Partage

[RSA] Comment calculer "d" ?

Sujet résolu
Le 21 novembre 2010 à 17:29:34

Bonjour,

J'ai déja lu tout ce qui concerne le RSA sur Wikipédia mais je bloque pour la création de la clé privée, car je ne sais pas calculer d (faut utiliser des congruences et je fais pas spé maths)...

Je viens bien de trouver ce tutoriel qui me permettrait de calculer d grâce à un programme fourni, mais je n'arrive pas à le lancer depuis la console Windows comme l'auteur l'explique :/

Pouvez-vous m'aider :
  • En m'expliquant comment calculer d (j'ai e qui vaut 157 et \(\varphi(n)\) qui vaut 1487932939512561873535776)
  • Ou en me disant quoi taper dans la console pour réussir à faire fonctionner le programme :-° (Là je tape C:\Users\MonNom\Desktop\Bezout.exe et ça fonctionne pas, j'ai aussi essayé sans l'extension et avec des /, mais ça ne fonctionne toujours pas...)
Merci de votre aide.
Publicité
Le 21 novembre 2010 à 17:29:34
Le 21 novembre 2010 à 17:45:21

Je suis désolé de ne pas répondre à ce topic pour t'aider, mais je me pose une question simple.

Pourquoi essaies-tu d'implémenter le codage RSA ?

Si tu voulais seulement utiliser la cryptographie asymétrique pour des besoins personnels, il existe de nombreuses implémentations qui font très bien ça toutes seules (par exemple GnuPG).

Si tu essaies juste de comprendre comment ça marche, et ne cherche pas à obtenir un résultat utilisable, il me semble qu'il vaudrait mieux que tu commences par comprendre les bases mathématiques, et donc les congruences. Ici il s'agit de comprendre la décomposition de Bezout, tu peux le faire même si tu n'as pas fait spé maths (mais il faut faire des efforts). Je pense que chercher "algorithme de bezout" sur internet fournit de nombreuses explications.


Pour moi le tutoriel que tu montres est quasiment sans intérêt, car ce n'est pas vraiment un tutoriel qui explique les principes des chiffrements symétriques et asymétriques (ce qui est utile), mais ce n'est pas non plus un tutoriel qui explique en détail le fonctionnement du chiffrage RSA (ce qui est moins utile, mais qui peut en intéresser certain), et qui est assez faible sur les détails techniques (par exemple les méthodes de calcul proposées ne sont pas utilisables en pratique).
Le 21 novembre 2010 à 17:50:53

Un "simple" défi de cryptanalyse provenant de ce site : http://www.newbiecontest.org/ ^^

Ils me donnent un texte crypté grâce à RSA, n, e et je dois le décrypter

Je suis donc remonté à p et q, et je dois maintenant trouver d de manière à avoir la clé privée, après je pense que je pourrais me débrouiller.
Le 21 novembre 2010 à 18:03:17

C'est généralement très mal vu de demander de l'aide sur les épreuves de newbiecontest sur des forums externes, il y en a un prévu spécialement à cet effet.

De plus, l'épreuve étant vraiment pas compliqué, il suffit de se documenter un peu comme l'a dit bluestorm, et ne pas vouloir obtenir la réponse sans effort comme ça a l'air d'être le cas ici.
Le 21 novembre 2010 à 18:06:44

Je pense que tu as mal compris la situation ThunderLord, Thiht a visiblement fait des efforts pour comprendre l'algorithme RSA, il demande des explications sur une petite partie de l'algorithme qu'il ne connaissait visiblement pas avant. S'il voulait tout avoir sans faire d'effort, il irait sans doute chercher la solution directement sur internet, au lieu de même lire la page wikipédia sur RSA.
Le 21 novembre 2010 à 18:07:59

Je demande pas d'aide sur l'épreuve en elle-même, mais sur les moyens de faire un calcul... comme je l'ai dit, simplement m'expliquer comment faire fonctionner le soft fourni dans le tuto que j'ai donné me suffirait, même après des recherches je trouve pas comment faire pour les chemins dans la console Windows...

(Merci pour le soutien bluestorm)

Sinon, sur ce site : http://sebsauvage.net/comprendre/encry [...] ypto_rsa.html j'étais tombé sur un exemple, mais :

Citation : http://sebsauvage.net/comprendre/encryptage/crypto_rsa.html

On choisit d tel que 71*d mod 1008 = 1

On trouve d = 1079


Est-ce que c'est correct, car dans mon cas il suffirait alors de faire \(\varphi(n)\)+e dans mon cas, mais je trouve ça trop simple...
Le 21 novembre 2010 à 18:23:49

Bon, je vais me risquer à une réponse assez véhémente.

Citation : bluestorm

Je pense que tu as mal compris la situation ThunderLord, Thiht a visiblement fait des efforts pour comprendre l'algorithme RSA, il demande des explications sur une petite partie de l'algorithme



Citation


comme je l'ai dit, simplement m'expliquer comment faire fonctionner le soft fourni dans le tuto que j'ai donné me suffirait,



Je suis pas sûr de saisir la connivence entre les deux réponses. En fait tel qu'il le présente, il essaye juste de faire marcher un programme qui lui fera 50% du boulot à sa place, et ça ne rentre pas dans ma définition de "demande des explications sur une petite partie de l'algorithme". M'enfin je peux concevoir que j'ai encore une fois(décidément) mal compris la situation.

Pardonnez d'avance mon incompréhension de la situation, mais il me semble que l'esprit newbiecontest encourage la recherche personnelle des résultats sur les épreuves, ici par exemple au lieu de s'acharner à faire marcher un programme, pourquoi ne pas en coder un toi même ? Ta compréhension n'en sera que d'autant plus grande et tu auras surement appris plus de chose que l'épreuve demandait, ce qui est un des buts des challenges de newbiecontest.

Enfin, je réitère ma question. Pourquoi ne pas avoir posé la question dans le topic d'aide dédié à l'épreuve de newbiecontest ? J'ai déjà ma petite idée sur la réponse, mais pour éviter un paragraphe supplémentaire je m'abstiens.

Bonne chance à toi pour les épreuves suivantes.
Le 21 novembre 2010 à 18:35:43

"pourquoi ne pas en coder un toi même ?"

Car je ne saurais déja pas faire le calcul à la main, pour des petits nombres (modulos congruences, tout ça...) alors pour en faire un programme, c'est un peu mort.

"Pourquoi ne pas avoir poser la question dans le topic d'aide dédié à l'épreuve de newbiecontest ?"

Car les réponses sont parfois à moitié données sur NC, c'est pas des indices que je demande, juste une explication sur un calcul.

(tu noteras que dans mon premier post, je dis "En m'expliquant comment calculer d", demander à quelqu'un d'expliquer des calculs de congruences ou les lire directement dans un livre, pour moi les deux sont de la recherche, je ne demande pas non-plus à ce qu'on me calcule d (franchement j'aimerais autant avoir la méthode et le calculer à la main/à la calto, et c'est pourquoi j'ai demandé l'explication du soft en deuxième et pas en premier...))

Bon, je crois que ce qu'il me reste à faire c'est de me trouver un livre de spé maths demain vu que c'est pas un des profs de maths de mon lycée ni quelqu'un d'ici qui va m'expliquer.
Le 21 novembre 2010 à 19:05:08

d est l'inverse de e modulo phi(n). En d'autres termes, d vérifie l'équation :

d*e + k*phi(n) = 1

Ce qu'il te faut c'est calculer d (et k, mais tu n'en auras pas besoin ensuite) en utilisant l'algorithme de Bezout. Cet algorithme, aussi appelé "algorithme d'Euclide étendu", est simple (ne demande pas de congruences ou quoi, si tu as compris l'algorithme d'Euclide tu devrais savoir appliquer celui-là aussi), et expliqué en de nombreux endroits sur internet, par exemple sur cette page trouvée sur Google.
Le 21 novembre 2010 à 19:24:26

Parfait, je devrais pouvoir finir tout seul maintenant :)

Merci bien.

[RSA] Comment calculer "d" ?

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
  • Editeur
  • Markdown