224
7 La cryptographie ` a cl´ e publique
Discussion de la valeur du code RSA Le code RSA a ´ et´ e introduit en 1978.
Il a incit´ e les chercheurs `
a trouver de meilleurs algorithmes pour factoriser de grands
nombres entiers, mais sans grand succ` es : la m´ ethode tient toujours si l’entier n est assez
grand. En fait, on ne sait mˆ eme pas si toute m´ ethode de d´ ecryptage de RSA ne serait
pas aussi complexe que la factorisation de n. Les efforts pour d´ ecrypter le code par une
m´ ethode plus simple (pour un ordinateur) que la factorisation de n se sont av´ er´ es vains
jusqu’` a pr´ esent.
En 1978, l’article original [7] ´ evaluait ` a 74 ans le temps requis pour factoriser un
nombre de 100 chiffres, `
a 3,8 × 10
9 ann´ ees le temps n´ ecessaire pour factoriser un nombre
de 200 chiffres et ` a 4,2×10
25 ann´ ees le temps qu’il faudrait pour factoriser un nombre de
500 chiffres. O` u en est-on par rapport aux ´ evaluations de 1978 ? ´
Etant donn´ e l’augmentation de la puissance des ordinateurs, une cl´ e de 100 chiffres est totalement d´ econseill´ ee.
Une cl´ e de 200 chiffres ne tenait d´ ej` a plus le coup en 2005 face ` a des professionnels du
d´ ecryptage ´ equip´ es d’ordinateurs puissants (voir ci-dessous). Les am´ eliorations sont de
deux ordres : la puissance des ordinateurs et l’efficacit´ e des algorithmes. La « loi » de
Moore (du nom de Gordon Moore, cofondateur d’Intel) pr´ edisait en 1965 que la densit´ e
des transistors doublerait tous les 18-24 mois et s’est r´ ev´ el´ ee ´ etonnamment exacte. Quel
rapport avec la vitesse de calcul ? Les pr´ ecisions suivantes viennent de Paul Rousseau,
qui travaille chez TSMC : la vitesse des transistors augmente d’un facteur de 1,4 tous
les deux ` a trois ans. Mˆ eme si les compagnies annoncent que la vitesse de l’horloge d’un
circuit est multipli´ ee par deux, le circuit fait moins de travail par cycle, et ce facteur
est donc artificiel. La vraie mesure est la capacit´ e de faire du « vrai travail ». Pour
un algorithme de factorisation permettant le travail en parall` ele, l’augmentation de la
capacit´ e de travail est de l’ordre de 2,8, soit 1,4 par transistor et un facteur 2 dˆ u `
a
l’augmentation du nombre de transistors. En 2005, 27 ans avaient pass´ e depuis 1978. Si
l’on prend des g´ en´ erations ayant en moyenne 2,5 ann´ ees, cela donne 10,8 g´ en´ erations,
soit un facteur de 67 500 qui est inf´ erieur ` a 10
5 .
L’am´ elioration des algorithmes n’est pas moins spectaculaire. D´ ej` a, Gauss au XIX
e
si` ecle avait qualifi´ e le probl` eme pratique de la factorisation de grands nombres de
probl` eme fondamental en th´ eorie des nombres. Les algorithmes les plus importants sont
• le crible quadratique de Pomerance,
• la m´ ethode des courbes elliptiques de Lenstra,
• le crible g´ en´ eral des corps de nombres de Pollard, Adleman, Buhler, Lenstra et
Pomerance.
Un bon article sur le sujet est l’article de Carl Pomerance [6].
En 1996, on factorisait des nombres de 130 chiffres et en 1999, des nombres de
155 chiffres. En 2005, F. Bahr, M. Boehm, J. Franke et T. Kleinjung annoncent la
factorisation d’un nombre de 200 chiffres,
n = 2799783391122132787082946763872260162107044678695542853756000992932
6128400107609345671052955360856061822351910951365788637105954482006
576775098580557613579098734950144178863178946295187237869221823983,
qui est produit des deux nombres premiers p et q donn´ es par
7 La cryptographie ` a cl´ e publique
Discussion de la valeur du code RSA Le code RSA a ´ et´ e introduit en 1978.
Il a incit´ e les chercheurs `
a trouver de meilleurs algorithmes pour factoriser de grands
nombres entiers, mais sans grand succ` es : la m´ ethode tient toujours si l’entier n est assez
grand. En fait, on ne sait mˆ eme pas si toute m´ ethode de d´ ecryptage de RSA ne serait
pas aussi complexe que la factorisation de n. Les efforts pour d´ ecrypter le code par une
m´ ethode plus simple (pour un ordinateur) que la factorisation de n se sont av´ er´ es vains
jusqu’` a pr´ esent.
En 1978, l’article original [7] ´ evaluait ` a 74 ans le temps requis pour factoriser un
nombre de 100 chiffres, `
a 3,8 × 10
9 ann´ ees le temps n´ ecessaire pour factoriser un nombre
de 200 chiffres et ` a 4,2×10
25 ann´ ees le temps qu’il faudrait pour factoriser un nombre de
500 chiffres. O` u en est-on par rapport aux ´ evaluations de 1978 ? ´
Etant donn´ e l’augmentation de la puissance des ordinateurs, une cl´ e de 100 chiffres est totalement d´ econseill´ ee.
Une cl´ e de 200 chiffres ne tenait d´ ej` a plus le coup en 2005 face ` a des professionnels du
d´ ecryptage ´ equip´ es d’ordinateurs puissants (voir ci-dessous). Les am´ eliorations sont de
deux ordres : la puissance des ordinateurs et l’efficacit´ e des algorithmes. La « loi » de
Moore (du nom de Gordon Moore, cofondateur d’Intel) pr´ edisait en 1965 que la densit´ e
des transistors doublerait tous les 18-24 mois et s’est r´ ev´ el´ ee ´ etonnamment exacte. Quel
rapport avec la vitesse de calcul ? Les pr´ ecisions suivantes viennent de Paul Rousseau,
qui travaille chez TSMC : la vitesse des transistors augmente d’un facteur de 1,4 tous
les deux ` a trois ans. Mˆ eme si les compagnies annoncent que la vitesse de l’horloge d’un
circuit est multipli´ ee par deux, le circuit fait moins de travail par cycle, et ce facteur
est donc artificiel. La vraie mesure est la capacit´ e de faire du « vrai travail ». Pour
un algorithme de factorisation permettant le travail en parall` ele, l’augmentation de la
capacit´ e de travail est de l’ordre de 2,8, soit 1,4 par transistor et un facteur 2 dˆ u `
a
l’augmentation du nombre de transistors. En 2005, 27 ans avaient pass´ e depuis 1978. Si
l’on prend des g´ en´ erations ayant en moyenne 2,5 ann´ ees, cela donne 10,8 g´ en´ erations,
soit un facteur de 67 500 qui est inf´ erieur ` a 10
5 .
L’am´ elioration des algorithmes n’est pas moins spectaculaire. D´ ej` a, Gauss au XIX
e
si` ecle avait qualifi´ e le probl` eme pratique de la factorisation de grands nombres de
probl` eme fondamental en th´ eorie des nombres. Les algorithmes les plus importants sont
• le crible quadratique de Pomerance,
• la m´ ethode des courbes elliptiques de Lenstra,
• le crible g´ en´ eral des corps de nombres de Pollard, Adleman, Buhler, Lenstra et
Pomerance.
Un bon article sur le sujet est l’article de Carl Pomerance [6].
En 1996, on factorisait des nombres de 130 chiffres et en 1999, des nombres de
155 chiffres. En 2005, F. Bahr, M. Boehm, J. Franke et T. Kleinjung annoncent la
factorisation d’un nombre de 200 chiffres,
n = 2799783391122132787082946763872260162107044678695542853756000992932
6128400107609345671052955360856061822351910951365788637105954482006
576775098580557613579098734950144178863178946295187237869221823983,
qui est produit des deux nombres premiers p et q donn´ es par