Calcul de l'algorithme RSA
Zarquoi
Messages postés
217
Date d'inscription
Statut
Membre
Dernière intervention
-
fiddy Messages postés 11069 Date d'inscription Statut Contributeur Dernière intervention -
fiddy Messages postés 11069 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
Désolé si je suis hors sujet. Comme ça parle de cryptographie, je ne sais pas dans quelle section mettre (j'ai hésité avec la section réseau, car le RSA s'utilise pour sécuriser le HTTP, mais je me suis dis qu'il y aurait davantage de personnes compétentes ici en programmation pour m'aider).
Alors je m'intéresse à la cryptographie RSA et notamment à son calcul.
Je suis tombé sur ce lien : http://sebsauvage.net/comprendre/encryptage/crypto_rsa.html
Je comprends beaucoup de chose, sauf qu'à un endroit, c'est très peu détaillé.
Il est dit :
On choisit d tel que 71*d mod 1008 = 1
On trouve d = 1079
J'aimerais savoir comment a été trouvé ce fameux d ?
Je sais, c'est un exercice tout con de collège "trouver x", mais là, avec le modulo, je suis bloqué :/
Je cherche à passer du calcul 71*d mod 1008 = 1 au calcul d=.....
Pouvez-vous m'aider ?
Merci
Désolé si je suis hors sujet. Comme ça parle de cryptographie, je ne sais pas dans quelle section mettre (j'ai hésité avec la section réseau, car le RSA s'utilise pour sécuriser le HTTP, mais je me suis dis qu'il y aurait davantage de personnes compétentes ici en programmation pour m'aider).
Alors je m'intéresse à la cryptographie RSA et notamment à son calcul.
Je suis tombé sur ce lien : http://sebsauvage.net/comprendre/encryptage/crypto_rsa.html
Je comprends beaucoup de chose, sauf qu'à un endroit, c'est très peu détaillé.
Il est dit :
On choisit d tel que 71*d mod 1008 = 1
On trouve d = 1079
J'aimerais savoir comment a été trouvé ce fameux d ?
Je sais, c'est un exercice tout con de collège "trouver x", mais là, avec le modulo, je suis bloqué :/
Je cherche à passer du calcul 71*d mod 1008 = 1 au calcul d=.....
Pouvez-vous m'aider ?
Merci
A voir également:
- Calcul de l'algorithme RSA
- Calcul moyenne excel - Guide
- Calcul km marche à pied gratuit - Télécharger - Sport
- Calcul charpente bois gratuit - Télécharger - Architecture & Déco
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel gratuit calcul valeur nutritionnelle - Télécharger - Santé & Bien-être
2 réponses
Bonjour,
Voici un autre article sur RSA :
https://www.commentcamarche.net/contents/208-algorithme-de-chiffrement-rsa
Voici un autre article sur RSA :
https://www.commentcamarche.net/contents/208-algorithme-de-chiffrement-rsa
Génération des clés
- Soient deux grands nombres premiers « aléatoirement » choisis : p et q.
- Notons : n = p*q et φ = (p-1)*(q-1)
- Soient d un grand entier « aléatoirement » choisi, premier avec φ. Et e l'inverse de d modulo φ.
Je cherche à passer du calcul 71*d mod 1008 = 1 au calcul d=.....
Dis autrement, tu dois trouver d dans 71*d + k*1008 = 1
avec k nombre entier relatif.
Et pour cela, tu as le théorème de Bézout.
Dis autrement, tu dois trouver d dans 71*d + k*1008 = 1
avec k nombre entier relatif.
Et pour cela, tu as le théorème de Bézout.
Ca va te faire pas mal de lecture demain ;-).
Enfin, le théorème de Bézout t'affirme qu'il y a au moins une solution.
Si tu veux en trouver une, c'est plutôt l'algorithme d'Euclide (étendu ici) qu'il faut utiliser :
Donc tu as juste à lire :
https://fr.wikipedia.org/wiki/Algorithme_d'Euclide_%C3%A9tendu
Enfin, le théorème de Bézout t'affirme qu'il y a au moins une solution.
Si tu veux en trouver une, c'est plutôt l'algorithme d'Euclide (étendu ici) qu'il faut utiliser :
Donc tu as juste à lire :
https://fr.wikipedia.org/wiki/Algorithme_d'Euclide_%C3%A9tendu
Salut fiddy :-)
Vu qu'on a déjà φ (l'indicatrice d'Euler) ce ne serait pas plus simple d'aller directement sur le théorème d'Euler ?
d^(-1) ≡ d^(φ-1) [n]
Vu qu'on a déjà φ (l'indicatrice d'Euler) ce ne serait pas plus simple d'aller directement sur le théorème d'Euler ?
d^(-1) ≡ d^(φ-1) [n]
J'ai déjà visité ce lien mais j'avoue l'avoir mis de côté (la documentation de CCM n'est pas très accueillante pour moi ^^).
J'y ai donc porté davantage d'attention, et donc sur le site sebsauvage, on choisit e et on calcul d, et sur CCM, c'est l'inverse : on choisit d et on calcul e.
Choisir d et calculer e est + facile :D
Je vais voir si j'y arrive :D
Merci beaucoup :)
Il faut que d soit premier avec phi.
Dans mon exemple, c'est phi=1008 (enfin, c'est l'exemple du site sebsauvage ^^).
Mais quel calcul permet d'avoir le ou les nombres qui sont premiers avec 1008 ?
J'ai testé quelques nombres au hasard, mais aucun n'est premier avec 1008.
J'imagine qu'il doit bien y avoir une formule pour ça ?
D'après mes recherches, je n'ai rien trouvé :/
Ça ne change absolument rien, d et e sont les inverses l'un de l'autre.
Tu peux très bien choisir aléatoirement deux couples (d1, e1) et (d2, e2) tel qu'on aurait d1=e1 et d2=e2, ça n'empêcherait pas d'avoir des couples valides.
Remarque : en général on choisit d en premier car on veut lui imposer d'être très grand, pour rendre le déchiffrement plus compliqué, alors que si on choisit e en premier, même petit, on n'a aucune garanti que d sera suffisamment grand.
Par définition le pgcd renvoie le plus grand diviseur commun des deux nombres, donc si c'est 1 alors ils sont premiers.
Généralement ce que l'on fait c'est choisir un nombre au hasard x puis on calcules le pgcd pour x, x+1, x+2... jusqu'à en trouver un qui soit premier avec φ
Hors, j'en ai qu'un seul ^^
Il n'y a vraiment aucun calcul qui me permette de trouver A à partir de B ?
Car sinon je fais un script qui calcul le PGCD en incrément A jusqu'à ce que le PGCD soit égal à 1 (je le ferai demain car là j'suis trop naze ^^).
Mais j'aimerai éviter d'utiliser un script car ce n'est pas très mathématique.
En tout cas MERCI pour ton aide !