7.4 Construire de grands nombres premiers
225
p = 35324619344027701212726049781984643686711974001976
25023649303468776121253679423200058547956528088349,
q = 79258699544783330333470858414800596877379758573642
19960734330341455767872818152135381409304740185467.
La factorisation a ´ et´ e obtenue par la m´ ethode du crible g´ en´ eral des corps de nombres,
qui ´ etait encore en 2005 le meilleur algorithme de factorisation connu.
Malgr´ e toutes ces am´ eliorations, le code RSA ne semble pas encore menac´ e, mais il
faut augmenter la longueur des cl´ es. Dans l’article de Jean-Paul Delahaye [4] en 2000, il
est recommand´ e d’utiliser une cl´ e de 232 chiffres pour les donn´ ees pas trop importantes,
une cl´ e de 309 chiffres pour les usages commerciaux et une cl´ e de 617 chiffres si on veut
une garantie de protection sur une longue p´ eriode de temps.
Nombres de Carmichael Dans le code RSA ` a une cl´ e publique n = pq, le message m doit remplir la condition (m, n) = 1 pour que l’op´ eration cryptage-d´ ecryptage
fonctionne. En fait, si on fait des tests avec des messages m qui ne sont pas relativement premiers avec n, c’est-` a-dire qu’on applique ` a m l’op´ eration de cryptage suivie de
l’op´ eration de d´ ecryptage, on r´ ecup` ere souvent le message m. La question se pose donc
de savoir si la condition (m, n) = 1 est inutile. La r´ eponse est connue : la condition
est inutile si n est un nombre de Carmichael. Mais il n’existe que peu de nombres de
Carmichael, et tous ont au moins trois facteurs. Donc, quand on utilise le code RSA, on
doit continuer `
a s’assurer que (m, n) = 1.
7.4 Construire de grands nombres premiers
Nous avons affirm´ e qu’il est facile de construire de grands nombres premiers. C’est
une cons´ equence du th´ eor` eme des nombres premiers : en mots simples, ce th´ eor` eme
donne la probabilit´ e qu’un grand entier de N chiffres choisi au hasard soit premier.
Pour construire un nombre premier de 100 chiffres, on g´ en` ere au hasard des nombres
entiers de 100 chiffres et on teste s’ils sont premiers. Le th´ eor` eme des nombres premiers
assure qu’apr` es en moyenne 115 essais, on devrait obtenir un nombre premier (si on
g´ en` ere seulement des nombres impairs). Ce th´ eor` eme des nombres premiers donne la
distribution « asymptotique » des nombres premiers parmi les entiers, c’est-` a dire, pour
un grand entier N , la proportion approximative des entiers inf´ erieurs ou ´ egaux `
a N qui
sont premiers.
Th´ eor` eme 7.12 (th´ eor` eme des nombres premiers) Soit
π(N ) = #{p ≤ N | p premier}
(c’est-` a-dire que π(N ) est le nombre d’entiers inf´ erieurs ou ´ egaux `
a N qui sont premiers). Alors, si N est grand, on a
π(N ) ≈
N
ln N
.
225
p = 35324619344027701212726049781984643686711974001976
25023649303468776121253679423200058547956528088349,
q = 79258699544783330333470858414800596877379758573642
19960734330341455767872818152135381409304740185467.
La factorisation a ´ et´ e obtenue par la m´ ethode du crible g´ en´ eral des corps de nombres,
qui ´ etait encore en 2005 le meilleur algorithme de factorisation connu.
Malgr´ e toutes ces am´ eliorations, le code RSA ne semble pas encore menac´ e, mais il
faut augmenter la longueur des cl´ es. Dans l’article de Jean-Paul Delahaye [4] en 2000, il
est recommand´ e d’utiliser une cl´ e de 232 chiffres pour les donn´ ees pas trop importantes,
une cl´ e de 309 chiffres pour les usages commerciaux et une cl´ e de 617 chiffres si on veut
une garantie de protection sur une longue p´ eriode de temps.
Nombres de Carmichael Dans le code RSA ` a une cl´ e publique n = pq, le message m doit remplir la condition (m, n) = 1 pour que l’op´ eration cryptage-d´ ecryptage
fonctionne. En fait, si on fait des tests avec des messages m qui ne sont pas relativement premiers avec n, c’est-` a-dire qu’on applique ` a m l’op´ eration de cryptage suivie de
l’op´ eration de d´ ecryptage, on r´ ecup` ere souvent le message m. La question se pose donc
de savoir si la condition (m, n) = 1 est inutile. La r´ eponse est connue : la condition
est inutile si n est un nombre de Carmichael. Mais il n’existe que peu de nombres de
Carmichael, et tous ont au moins trois facteurs. Donc, quand on utilise le code RSA, on
doit continuer `
a s’assurer que (m, n) = 1.
7.4 Construire de grands nombres premiers
Nous avons affirm´ e qu’il est facile de construire de grands nombres premiers. C’est
une cons´ equence du th´ eor` eme des nombres premiers : en mots simples, ce th´ eor` eme
donne la probabilit´ e qu’un grand entier de N chiffres choisi au hasard soit premier.
Pour construire un nombre premier de 100 chiffres, on g´ en` ere au hasard des nombres
entiers de 100 chiffres et on teste s’ils sont premiers. Le th´ eor` eme des nombres premiers
assure qu’apr` es en moyenne 115 essais, on devrait obtenir un nombre premier (si on
g´ en` ere seulement des nombres impairs). Ce th´ eor` eme des nombres premiers donne la
distribution « asymptotique » des nombres premiers parmi les entiers, c’est-` a dire, pour
un grand entier N , la proportion approximative des entiers inf´ erieurs ou ´ egaux `
a N qui
sont premiers.
Th´ eor` eme 7.12 (th´ eor` eme des nombres premiers) Soit
π(N ) = #{p ≤ N | p premier}
(c’est-` a-dire que π(N ) est le nombre d’entiers inf´ erieurs ou ´ egaux `
a N qui sont premiers). Alors, si N est grand, on a
π(N ) ≈
N
ln N
.