Factorisation RSA.

fredrick · March 2015

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.

denise chemla · March 2015

Bonjour,
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

remarque · March 2015

Il ne part pas très fort cet article :

papier RSA trouvé sur internet a écrit:

[...] on the mathematical difficulty of factorization for big prime numbers.

On dirait presque du Bill Gates.

Fin de partie · March 2015

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 écrit:

Si tu connais un des facteurs, une poignée de millisecondes. B-)-

Foufoux · March 2015

Bonjour,

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]

Fin de partie · March 2015

Ils ont notamment été capables de factoriser des clés RSA de 512 bits (environ 150 chiffres) a écrit:

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).