214
7 La cryptographie ` a cl´ e publique
par exemple, a est remplac´ e par d, b par e, c par f , etc. En fran¸ cais, la lettre la plus
fr´ equente est le e : en regardant les textes transmis, on finirait par d´ eduire que le e a
´ et´ e chang´ e en h, et, de proche en proche, on finirait par d´ eduire le code. La deuxi` eme
raison pour laquelle les codes secrets sont vuln´ erables est que l’exp´ editeur et le receveur
doivent se communiquer le mode de fonctionnement du code. Comme avec tout ´ echange
d’information, il est possible qu’il y ait une fuite lors de cette communication.
Dans ce chapitre, nous ´ etudions le code RSA, du nom de ses concepteurs Rivest, Shamir et Adleman. C’est un code `
a cl´ e publique. Ce qui est particuli` erement remarquable
dans ce code, c’est qu’il tient depuis 1978, mˆ eme si, depuis plus de 29 ans, les meilleurs
scientifiques savent que la c´ el´ ebrit´ e les attend s’ils r´ eussissent ` a le casser. Le fait est
d’autant plus surprenant que le mode de fonctionnement du code est compl` etement
public. Nous allons ´ etudier ci-dessous le fonctionnement de ce code et voir qu’il suffit
d’apprendre `
a un ordinateur `
a factoriser de grands nombres pour le casser. C’est donc
cette op´ eration que nous avons apprise ` a l’´ ecole, d´ ecomposer un entier en ses facteurs
premiers, qui tient en ´ echec les super-ordinateurs et les meilleurs scientifiques, pour peu
que l’entier soit assez grand !
L’ingr´ edient de base du code RSA est la th´ eorie des nombres, plus particuli` erement
l’arithm´ etique (+, .) modulo n, et on utilise le petit th´ eor` eme de Fermat g´ en´ eralis´ e par
Euler. La m´ ethode fonctionne `
a cause des trois faits suivants, bien connus des th´ eoriciens
des nombres :
• il est difficile pour un ordinateur de factoriser un grand nombre ;
• il est facile pour un ordinateur de construire de grands nombres premiers ;
• il est facile pour un ordinateur de d´ ecider si un grand nombre est premier.
Avantages d’un syst` eme ` a cl´ e publique Ils sont tr` es importants. Pour que deux
personnes communiquent avec un syst` eme cryptographique, il faut que les deux soient
en possession de la m´ ethode : c’est au moment de ce partage de la m´ ethode que le
danger d’interception est grand. Dans le cas de la cryptographie `
a cl´ e publique, ce
danger n’existe plus : le code est public ! C’est aussi le seul type de codage qui puisse
fonctionner lorsqu’il y a des millions d’utilisateurs, par exemple, lorsque vous voulez
envoyer un num´ ero de carte de cr´ edit sur Internet.
Nous verrons que le code RSA a un autre avantage : il est possible de « signer »
un message de telle sorte qu’on soit sˆ ur de sa provenance. De nos jours o` u il se fait
beaucoup d’usurpation d’identit´ e sur Internet ou dans les messageries ´ electroniques,
c’est un avantage tr` es important.
7.2 Quelques outils de th´ eorie des nombres
D´ efinition 7.1 (i) Soient a et b deux entiers. On dit que a divise b s’il existe un entier
q tel que b = aq. On note a | b. (La d´ efinition est valable aussi bien pour a, b, q ∈ N
que pour a, b, q ∈ Z.)
(ii) Le plus grand diviseur commun (PGCD) de a et b, not´ e (a, b), satisfait aux deux
propri´ et´ es suivantes :
7 La cryptographie ` a cl´ e publique
par exemple, a est remplac´ e par d, b par e, c par f , etc. En fran¸ cais, la lettre la plus
fr´ equente est le e : en regardant les textes transmis, on finirait par d´ eduire que le e a
´ et´ e chang´ e en h, et, de proche en proche, on finirait par d´ eduire le code. La deuxi` eme
raison pour laquelle les codes secrets sont vuln´ erables est que l’exp´ editeur et le receveur
doivent se communiquer le mode de fonctionnement du code. Comme avec tout ´ echange
d’information, il est possible qu’il y ait une fuite lors de cette communication.
Dans ce chapitre, nous ´ etudions le code RSA, du nom de ses concepteurs Rivest, Shamir et Adleman. C’est un code `
a cl´ e publique. Ce qui est particuli` erement remarquable
dans ce code, c’est qu’il tient depuis 1978, mˆ eme si, depuis plus de 29 ans, les meilleurs
scientifiques savent que la c´ el´ ebrit´ e les attend s’ils r´ eussissent ` a le casser. Le fait est
d’autant plus surprenant que le mode de fonctionnement du code est compl` etement
public. Nous allons ´ etudier ci-dessous le fonctionnement de ce code et voir qu’il suffit
d’apprendre `
a un ordinateur `
a factoriser de grands nombres pour le casser. C’est donc
cette op´ eration que nous avons apprise ` a l’´ ecole, d´ ecomposer un entier en ses facteurs
premiers, qui tient en ´ echec les super-ordinateurs et les meilleurs scientifiques, pour peu
que l’entier soit assez grand !
L’ingr´ edient de base du code RSA est la th´ eorie des nombres, plus particuli` erement
l’arithm´ etique (+, .) modulo n, et on utilise le petit th´ eor` eme de Fermat g´ en´ eralis´ e par
Euler. La m´ ethode fonctionne `
a cause des trois faits suivants, bien connus des th´ eoriciens
des nombres :
• il est difficile pour un ordinateur de factoriser un grand nombre ;
• il est facile pour un ordinateur de construire de grands nombres premiers ;
• il est facile pour un ordinateur de d´ ecider si un grand nombre est premier.
Avantages d’un syst` eme ` a cl´ e publique Ils sont tr` es importants. Pour que deux
personnes communiquent avec un syst` eme cryptographique, il faut que les deux soient
en possession de la m´ ethode : c’est au moment de ce partage de la m´ ethode que le
danger d’interception est grand. Dans le cas de la cryptographie `
a cl´ e publique, ce
danger n’existe plus : le code est public ! C’est aussi le seul type de codage qui puisse
fonctionner lorsqu’il y a des millions d’utilisateurs, par exemple, lorsque vous voulez
envoyer un num´ ero de carte de cr´ edit sur Internet.
Nous verrons que le code RSA a un autre avantage : il est possible de « signer »
un message de telle sorte qu’on soit sˆ ur de sa provenance. De nos jours o` u il se fait
beaucoup d’usurpation d’identit´ e sur Internet ou dans les messageries ´ electroniques,
c’est un avantage tr` es important.
7.2 Quelques outils de th´ eorie des nombres
D´ efinition 7.1 (i) Soient a et b deux entiers. On dit que a divise b s’il existe un entier
q tel que b = aq. On note a | b. (La d´ efinition est valable aussi bien pour a, b, q ∈ N
que pour a, b, q ∈ Z.)
(ii) Le plus grand diviseur commun (PGCD) de a et b, not´ e (a, b), satisfait aux deux
propri´ et´ es suivantes :