Calcul de l'algorithme RSA
Fermé
Zarquoi
Messages postés
218
Date d'inscription
samedi 28 mars 2015
Statut
Membre
Dernière intervention
13 décembre 2016
-
Modifié par Zarquoi le 13/05/2016 à 21:42
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 - 13 mai 2016 à 23:58
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 - 13 mai 2016 à 23:58
A voir également:
- Calcul de l'algorithme RSA
- Calcul moyenne excel - Guide
- Formule de calcul excel - Guide
- Logiciel calcul plancher bois gratuit - Télécharger - Architecture & Déco
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Logiciel gratuit calcul surface m2 - Télécharger - Outils professionnels
2 réponses
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
13 mai 2016 à 21:47
13 mai 2016 à 21:47
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 φ.
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 835
13 mai 2016 à 23:14
13 mai 2016 à 23:14
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.
Zarquoi
Messages postés
218
Date d'inscription
samedi 28 mars 2015
Statut
Membre
Dernière intervention
13 décembre 2016
48
13 mai 2016 à 23:28
13 mai 2016 à 23:28
Merci, demain je vais voir ce théorème (que je ne connais absolument pas).
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 835
Modifié par fiddy le 13/05/2016 à 23:33
Modifié par fiddy le 13/05/2016 à 23:33
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
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
13 mai 2016 à 23:40
13 mai 2016 à 23:40
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]
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 835
13 mai 2016 à 23:58
13 mai 2016 à 23:58
Salut KX,
À vrai dire, je n'y avais même pas pensé.
Mais pour calculer à la main, l'algorithme d'Euclide me semble plus adapté, et plus accessible. Mais donnons lui de la lecture, il nous fera un retour d'expérience ;-).
À vrai dire, je n'y avais même pas pensé.
Mais pour calculer à la main, l'algorithme d'Euclide me semble plus adapté, et plus accessible. Mais donnons lui de la lecture, il nous fera un retour d'expérience ;-).
13 mai 2016 à 22:02
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 :)
13 mai 2016 à 22:14
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é :/
13 mai 2016 à 22:16
Ç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.
13 mai 2016 à 22:22
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 φ
Modifié par Zarquoi le 13/05/2016 à 22:40
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 !