Factorisation RSA.
Bonjour,
Est-ce que vous savez (à peu près) combien de temps il faut à un ordinateur personnel pour factoriser un petit nombre RSA, par exemple le RSA-100 ou 129, avec les algorithmes actuels ?
A l'époque ou ont été factorisés les premiers nombres il fallait plusieurs mois à des supercalculateurs pour trouver la solution. J'imagine qu'avec les progrès les choses se sont accélèrées.
Merci.
Est-ce que vous savez (à peu près) combien de temps il faut à un ordinateur personnel pour factoriser un petit nombre RSA, par exemple le RSA-100 ou 129, avec les algorithmes actuels ?
A l'époque ou ont été factorisés les premiers nombres il fallait plusieurs mois à des supercalculateurs pour trouver la solution. J'imagine qu'avec les progrès les choses se sont accélèrées.
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
En tapant benchmarks "RSA factorization algorithms" sous le moteur de recherche quasi-monopolistique, j'ai trouvé l'article joint. Il y a des tableaux de temps d'exécution page 4, peut-être cela peut-il t'aider à chercher plus loin.
Cordialement,
Denise
On dirait presque du Bill Gates.
Si tu connais un des facteurs, une poignée de millisecondes. B-)-
Pour avoir un ordre de grandeur, récemment des chercheurs de l'INRIA ont découvert une vulnérabilités dans SSL/TLS.
Ils ont notamment été capables de factoriser des clés RSA de 512 bits (environ 150 chiffres) en utilisant des serveurs EC2 http://aws.amazon.com/fr/ec2/ et cado-nfs http://cado-nfs.gforge.inria.fr/ .
Il fallait environ 7h30 pour factoriser (soit environ 104$ de location du cluster).
Sinon, pour un individu lambda avec une machine assez puissante, tu peux obtenir une factorisation d'un nombre de 100 chiffres en quelques (4 à 5) jours.
Cependant, ECM http://ecm.gforge.inria.fr/ est une méthode qui peut être intéressante voir plus rapide (voir http://www.loria.fr/~zimmerma/records/ecm/params.html .
Voilà ce sont deux méthodes pour des nombres génériques (il y a aussi QFS), mais si tu connais la forme des facteurs alors peut-être qu'il y a des attaques plus rapides comme l'a illustré Fin de partie.
++,
Foufoux
[Activation des liens. AD]
Ils n'utilisent pas des clefs plus longues? Bizarre ::o
Dans un des liens ci-dessus, il y a des comparaisons de performance (mais l'ordinateur utilisé n'est pas un PC poussif)
Par exemple:
RSA-120 43.9 heures.
RSA-130 219 heures.
RSA-155 123 jours.
l'algorithme utilisé est une déclinaison de NFS (number field sieve).
C'est toute la subtilité de cette faille : https://freakattack.com/
++,
Foufoux