7
La cryptographie ` a cl´ e publique : le code RSA (1978)
Ce chapitre contient plus de mati` ere que ce qu’on peut traiter en une semaine. Les
rappels sur la th´ eorie des nombres autour de l’algorithme d’Euclide sont optionnels
(section 7.2) : ils d´ ependent de la pr´ eparation des ´ etudiants. Une partie de cette
pr´ eparation peut faire l’objet d’exercices. Par contre, il faut prendre le temps de
pr´ esenter bri` evement l’arithm´ etique modulo n. On traite ensuite la section 7.3 : on
pr´ esente le fonctionnement du code RSA et on fait la preuve du th´ eor` eme d’Euler,
ce qui permet de justifier compl` etement et rigoureusement le fonctionnement du code
RSA. On explique comment signer un message. Cette premi` ere partie peut se traiter
en deux heures environ, sauf s’il a fallu faire beaucoup de pr´ ealables sur la th´ eorie des
nombres. Ensuite, la derni` ere heure est consacr´ ee ` a la partie avanc´ ee. Par exemple,
on peut expliquer le principe d’un algorithme probabiliste permettant de tester si un
nombre est premier (d´ ebut de la section 7.4). Si on ne dispose que d’une heure, on n’a
pas le temps de faire tous les d´ etails du test lui-mˆ eme. On peut seulement l’illustrer
par des exemples.
Le reste du chapitre est d’un niveau nettement plus avanc´ e. Pour pouvoir le traiter
en classe, il est pr´ ef´ erable de s’adresser `
a des ´ etudiants ayant des notions de th´ eorie
des groupes. Ces notions seront utilis´ ees dans les d´ etails de l’algorithme de primalit´ e
(section 7.4) ou encore, dans ceux de l’algorithme de Shor pour la factorisation de
grands nombres entiers (section 7.5). Ces sections avanc´ ees peuvent aussi servir de
point de d´ epart ` a un projet de session.
7.1 Introduction
La cryptographie est un sujet vieux comme le monde. De tout temps, l’homme a
invent´ e des codes secrets permettant de transmettre des messages sans qu’ils puissent
ˆ etre compris par un intercepteur. L’histoire a montr´ e qu’il est tr` es difficile de trouver des
codes secrets qui r´ esistent longtemps et que des scientifiques astucieux finissent toujours
par percer les codes secrets. Prenons, par exemple, un code o` u on permuterait les lettres
de l’alphabet, chaque lettre ´ etant remplac´ ee par la lettre situ´ ee trois places plus loin :
La cryptographie ` a cl´ e publique : le code RSA (1978)
Ce chapitre contient plus de mati` ere que ce qu’on peut traiter en une semaine. Les
rappels sur la th´ eorie des nombres autour de l’algorithme d’Euclide sont optionnels
(section 7.2) : ils d´ ependent de la pr´ eparation des ´ etudiants. Une partie de cette
pr´ eparation peut faire l’objet d’exercices. Par contre, il faut prendre le temps de
pr´ esenter bri` evement l’arithm´ etique modulo n. On traite ensuite la section 7.3 : on
pr´ esente le fonctionnement du code RSA et on fait la preuve du th´ eor` eme d’Euler,
ce qui permet de justifier compl` etement et rigoureusement le fonctionnement du code
RSA. On explique comment signer un message. Cette premi` ere partie peut se traiter
en deux heures environ, sauf s’il a fallu faire beaucoup de pr´ ealables sur la th´ eorie des
nombres. Ensuite, la derni` ere heure est consacr´ ee ` a la partie avanc´ ee. Par exemple,
on peut expliquer le principe d’un algorithme probabiliste permettant de tester si un
nombre est premier (d´ ebut de la section 7.4). Si on ne dispose que d’une heure, on n’a
pas le temps de faire tous les d´ etails du test lui-mˆ eme. On peut seulement l’illustrer
par des exemples.
Le reste du chapitre est d’un niveau nettement plus avanc´ e. Pour pouvoir le traiter
en classe, il est pr´ ef´ erable de s’adresser `
a des ´ etudiants ayant des notions de th´ eorie
des groupes. Ces notions seront utilis´ ees dans les d´ etails de l’algorithme de primalit´ e
(section 7.4) ou encore, dans ceux de l’algorithme de Shor pour la factorisation de
grands nombres entiers (section 7.5). Ces sections avanc´ ees peuvent aussi servir de
point de d´ epart ` a un projet de session.
7.1 Introduction
La cryptographie est un sujet vieux comme le monde. De tout temps, l’homme a
invent´ e des codes secrets permettant de transmettre des messages sans qu’ils puissent
ˆ etre compris par un intercepteur. L’histoire a montr´ e qu’il est tr` es difficile de trouver des
codes secrets qui r´ esistent longtemps et que des scientifiques astucieux finissent toujours
par percer les codes secrets. Prenons, par exemple, un code o` u on permuterait les lettres
de l’alphabet, chaque lettre ´ etant remplac´ ee par la lettre situ´ ee trois places plus loin :