Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 09-03-2007 00:54:56
- aitim
- Membre
- Inscription : 09-03-2007
- Messages : 3
Je ne suis pas un matheu: probleme avec RSA.
Bonjour a tous, je ne sais pas si vous pourrez m'aider, mais ca fait 4 jours que je cherche sur le net, et je ne trouve pas de solution.
Voila:
- Je dois decrypter un message en utilisant RSA (enfin, je crois).
- Pour cela, on m'a fournis:
* c (le message crypté).
* N (N=pq).
* e (e appartient a Z/phi(N)Z).
- On me demande de retrouver:
* d, p, q et le message (d est tel que: ed=1[phi(N)]).
Je n'y comprend rien, ca ressemble pour moi au fait de "casser" le RSA, mais c'est tres dur (impossible?) selon moi.
Je ne trouve rien sur le net, a part des fonctions mathematiques, et je suis plutot litteraire...
Si quelqu'un pouvait me fournir un lien pour trouver d,p,q a partir de e et N... Ca me tirerais d'un mauvais pas!
(je dois realiser un programme en java pour decrypter le message, mais pour le decrypter il me faut d,p,q... Mais un algo me suffirait largement. Ou meme un texte parlant de ca.)
Hors ligne
#2 09-03-2007 01:19:49
Re : Je ne suis pas un matheu: probleme avec RSA.
Bonsoir,
Effectivement, ce que tu sembles vouloir faire est bien de casser un RSA.
Son impossibilité est empirique car elle suppose qu'on ne peut pas factoriser en produit de nombres premiers un tres grand nombre.
Cependant si dans votre exemple, le nombre N n'est pas "tres grand", un algorithme de recherche peut tout a fait etre appliqué et permettrait de retrouver p, q et d par la suite.
J'ai moi même, avec mon petit ordi réussi à casser un algorithme chiffré avec une clef de 60 bits, c'est à dire un nombre assez grand.
Pour cela il suffit d'appliquer l'algorithme suivant (qui peut etre optimisé) :
On connait N.
Pour i variant de 1 à racine de N
faire :
si i est premier
alors
si N/i est un entier naturel
alors
retourner i et N/i
fin de si
fin de si
fin de pour
Pour retrouver d, il suffit ensuite de calculer phi=(p-1)(q-1) et de retrouver l'inverse de e modulo phi (de nombreuses pages expliquent comment faire).
Si tu as besoin des algorithmes dans un langage spécial, n'hézite pas demander, de même si tu as d'autres questions ou si tu ne comprends pas un point particulier.
A++
Hors ligne
#3 10-03-2007 03:54:19
- aitim
- Membre
- Inscription : 09-03-2007
- Messages : 3
Re : Je ne suis pas un matheu: probleme avec RSA.
Pour i variant de 1 à racine de N
faire :
si i est premier
alors
si N/i est un entier naturel
alors
retourner i et N/i
fin de si
fin de si
fin de pour
Bonsoir, et... Merci beaucoup pour ta reponse :)))
Tout d'abord, je ne sais pas combien de bits fait mon N, mais je sais qu'il se compose de 617 chiffres.
(non, j'ai pas compte ,-) )
Alors, j'ai fait pas mal de recherche entre deux, et je vais tester l'algo que tu me proposes, il me semble bien.
Juste une question: Cette fonction va retourner deux nombres qui sont p et q, mais si j'ai bien compris, il faut peut etre que:
si N/i est un entier naturel
soit remplacé par:
si N/i est un entier naturel et si N/i est premier
car p comme q doivent etre premiers, non?
Dans tous les cas, j'essaye et je te dis encore merci!
Hors ligne
#4 10-03-2007 12:27:00
Re : Je ne suis pas un matheu: probleme avec RSA.
Bonjour,
Si N/i est entier naturel, alors il est necessairement premier car N n'a que 2 diviseurs, puiqu'a la base produit de 2 nombres premiers.
Le nombre de chiffre est quand meme élevé, j'espère que tu as un ordinateur puissant...
A++
Hors ligne
#5 11-03-2007 19:47:53
- aitim
- Membre
- Inscription : 09-03-2007
- Messages : 3
Re : Je ne suis pas un matheu: probleme avec RSA.
oki, merci pour cette explication, comme je l'ai précisé, je suis nul en math.
Mais tu as raison la solution doit être ailleurs car... c'est un peu long (ca ne fini pas d'ailleurs)
Au cas ou, voila mon code java de ton algo, je dois voir quelqu'un qui a peut-être la solution, si c'est le cas, je la posterais ici.
(Des fois que ca serve a quelqu'un un jour)
public static BigInteger trouverP(BigInteger n){ //Pas sur que ca marche
BigInteger i = BigInteger.ONE;
while(i.compareTo(sqrt(n)) < 0){
if(i.isProbablePrime(5)){
System.out.println("i:"+i+".Reste: "+n.remainder(i));
if(n.remainder(i)==BigInteger.ZERO){
return i;
}
}
i = i.add(BigInteger.ONE);
}
return BigInteger.ZERO;
}
Hors ligne
#6 12-03-2007 23:47:40
- pascal
- Membre
- Inscription : 27-01-2007
- Messages : 56
Re : Je ne suis pas un matheu: probleme avec RSA.
pour factoriser des grands nombres, il vaut mieux utiliser des algorithmes de factorisation déjà éprouvés. Le logiciel PARI/GP dispose d'une fonction factor très puissante. Maxima est aussi assez efficace dans son genre. Avec le premier, on peut factoriser des nombres de plus de 300 bits assez rapidement.
Hors ligne
#7 19-04-2007 11:13:37
- Rainbow
- Membre
- Inscription : 19-04-2007
- Messages : 3
Re : Je ne suis pas un matheu: probleme avec RSA.
bonjour,
je sais que ce fil est vieux, mais je viens de découvrir ce forum ;-)
Une petite chose me choc, tu dis que ton N fait 617 chiffres, donc N vaut environ 10^600, or si on fait l'approximation 10^3=2^10, on obtient que N vaut environ 2^2000, donc ton N ferais 2000bits... Qu'est-ce que c'est que ce code que tu veux casser???!!! Tu veux pirater la NSA ou quoi?? A moins que ton N ait un facteur "évident" (disons inférieur à un million), tu peux laisser tomber tes recherches, il te faudrait laisser tourner ton algo pendant plusieurs semaines avant de trouver une solution (voire plusieurs années...)
Peut-etre aurait-il été plus simple d'ailleur que tu nous donne dès le début ton N ?
Hors ligne
#8 19-04-2007 14:03:49
Re : Je ne suis pas un matheu: probleme avec RSA.
Bonjour,
Effectivement, très bonne remarque Rainbow...
Si aitim repasse par la, il pourra nous dire ce qu'il en retournait.
A titre indicatif les clef de 2048 bits sont autorisées uniquement dans les commerces de grande envergure (genre banque).
Sinon la loi francaise n'autorise (n'autorisait??) pas les clef supérieur a 1024 bits jusqu'a il y a au moins quelques temps.
A++
Hors ligne