imaginons que la clef fasse k bits, pour factoriser le nombre en force brute il faut 2^(k/2) divisions. Il faut donc un pouvoir faire 2^(k/2) divisions de grands entiers par secondes par exemple, pour être capable de factoriser un nombre de k bits en une seconde.
Maintenant, si on ajoute deux bits à la taille de la clef : k -> k + 2, avec 2^(k/2) divisions par seconde il faut maintenant 2 secondes pour factoriser le nombre. Autrement dit, le temps de calcul a été multiplié par 2 en simplement ajoutant 2 bits à la clef !
Donc quand on ajoute 100 bits à la clef (1024 bits -> 1124 bits), le temps de calcul est multiplié par 2^100.
Et encore, le calcul suppose qu'on sache faire des divisions sur des entiers de taille moitié de celle de la clef même quand on en augmente la taille.
Conclusion :
Pour le cryptographe :
Il faut avoir une idée d'un temps de calcul minimal pour une division, et adapter la taille de clef en conséquence (en étant farouchement paranoïaque, voir paragraphe suivant). Mais la progression exponentielle assure qu'on pourra garder des clefs de taille raisonnable (mais déjà augmenter leur taille peut-être pénible si il utilise aussi du matériel dédié. Qui a dit cartes à puces ? :-). De plus, il faut espérer que l'adversaire n'utilise pas de technique plus évoluée.
Pour le cryptanalyste :
Ça marchera très bien pour casser des clefs trop petites, par exemple sur des documents anciens dont les clefs étaient trop petite par rapport aux capacités actuelles (bon, il faut aussi que le document en vaille la peine, s'il est trop vieux, il n'est pas forcément intéressant).
Il faut trouver des algorithmes qui marchent plus vite (supprimer la croissance exponentielle du temps de calcul par rapport à la longueur de la clef), et recycler l'idée de l'ASIC là où les nouveaux algorithmes de factorisation prennent le plus de temps si exécutés sur un ordinateur normal.
En pratique, le goulot d'étranglement dans la plupart des algorithmes de factorisation est dans une phase d'algèbre linéaire (trouver des relations entre des vecteurs), non aisément parallélisable.
[^] # Re: FLOPS ?
Posté par khivapia . En réponse à la dépêche Un top 500 sous le signe du pétaflops. Évalué à 8.
Maintenant, si on ajoute deux bits à la taille de la clef : k -> k + 2, avec 2^(k/2) divisions par seconde il faut maintenant 2 secondes pour factoriser le nombre. Autrement dit, le temps de calcul a été multiplié par 2 en simplement ajoutant 2 bits à la clef !
Donc quand on ajoute 100 bits à la clef (1024 bits -> 1124 bits), le temps de calcul est multiplié par 2^100.
Et encore, le calcul suppose qu'on sache faire des divisions sur des entiers de taille moitié de celle de la clef même quand on en augmente la taille.
Conclusion :
Pour le cryptographe :
Il faut avoir une idée d'un temps de calcul minimal pour une division, et adapter la taille de clef en conséquence (en étant farouchement paranoïaque, voir paragraphe suivant). Mais la progression exponentielle assure qu'on pourra garder des clefs de taille raisonnable (mais déjà augmenter leur taille peut-être pénible si il utilise aussi du matériel dédié. Qui a dit cartes à puces ? :-). De plus, il faut espérer que l'adversaire n'utilise pas de technique plus évoluée.
Pour le cryptanalyste :
Ça marchera très bien pour casser des clefs trop petites, par exemple sur des documents anciens dont les clefs étaient trop petite par rapport aux capacités actuelles (bon, il faut aussi que le document en vaille la peine, s'il est trop vieux, il n'est pas forcément intéressant).
Il faut trouver des algorithmes qui marchent plus vite (supprimer la croissance exponentielle du temps de calcul par rapport à la longueur de la clef), et recycler l'idée de l'ASIC là où les nouveaux algorithmes de factorisation prennent le plus de temps si exécutés sur un ordinateur normal.
En pratique, le goulot d'étranglement dans la plupart des algorithmes de factorisation est dans une phase d'algèbre linéaire (trouver des relations entre des vecteurs), non aisément parallélisable.