Google Groups

Re: si rsa tombe


Francois Grieu Jul 9, 2004 4:10 AM
Posted in group: fr.misc.cryptologie
Roland <x-k...@hotmail.com> demande:

> Avez vous une estimation du besoin CPU (en MIPS par exemple)
> pour factoriser un nombre de n bits ?

L'état de l'art est 576 bits en 2003, mais la puissance de
calcul utilisée n'est pas publiée pour l'instant, que je sache.
<http://www.loria.fr/~zimmerma/records/rsa576>

La référence précédente est 512 bits en 1999
<http://db.cwi.nl/rapporten/abstract.php?abstractnr=690>
S'il faut résumer l'effort en quelques chiffres
8400 MIPS.an; 36 CPU.an (criblage)
224 CPU.h, 2 Go de mémoire sur Cray C916 (système linéaire)

> Au moins une idée de la progression : double-t-elle quand
> on ajoute quelques bits, quand on double la longueur n, etc.

Le coût pour factoriser n par cette méthode (GNFS)
évolue sensiblement en
     e^(k*(Log(n)^(1/3))*(Log(Log(n))^(2/3)))
avec k = (64/9)^(1/3)                  = 1,923..
et il y a une piste pour descendre à
     k = ((92+26*(13^(1/2)))/27)^(1/3) = 1,902..

La progression entre la taille en bit et la difficulté
est moins qu'exponentielle, mais pas tant que ça.
La formule (avec le k le plus prudent) prédit que
 passer de 512 à  576 bits multiple l'effort par 10,6
 passer de 576 à  640 bits multiple l'effort par  9,1
 passer de 640 à  704 bits multiple l'effort par  8,0
 passer de 704 à  768 bits multiple l'effort par  7,2
 passer de 768 à  832 bits multiple l'effort par  6,5
 passer de 832 à  896 bits multiple l'effort par  6,0
 passer de 896 à  960 bits multiple l'effort par  5,6
 passer de 960 à 1024 bits multiple l'effort par  5,2

Historiquement la progression de l'effort en MIPS.an
pour les records de factorisation est bien moindre que
ne le donne cette formule, du fait de progrès théoriques.

Très à la hache, le progrès prévisible dans les 10 ans
à venir est selon moi de l'ordre de 32 bits par an,
progrès techniques et théoriques confondus, sans prendre
de marge de sécurité.

Note: cette hypothèse est fondée sur la conjecture que les
progrès techniques et théoriques ralentissent un peu, ce qui
est une opinion personelle et mal étayée.

Note: Ne pas utiliser cette hypothèse pour choisir une
taille de clé: se reporter à [1] quand le contexte le permet.

Malgré ces réserves, à 50/50, je parie cependant pour
l'hypothèse que d'ici à 2016, la plus grande clé RSA
dont la factorisation sera effectuée dans un contexte
académique l'année A portera sur un nombre d'au plus
(A-2000)*32+512 bits.


  François Grieu

[1] Arjen K. Lenstra, Eric R. Verheul: "Selecting Cryptographic
Key Sizes", Public Key Cryptography, LNCS 1751, Springer-Verlag.
<http://citeseer.ist.psu.edu/287428.html>