218
7 La cryptographie ` a cl´ e publique
Un syst` eme de cryptographie ` a cl´ e publique est mis sur pied par une personne ou
une organisation (que nous appellerons le receveur) qui veut recevoir des messages de
mani` ere s´ ecuritaire. C’est elle qui construit le syst` eme et publie la m´ ethode transmission
des messages.
Premi` ere ´ etape Le receveur choisit p et q deux grands nombres premiers (plus de
100 chiffres). Il calcule n = pq. Ce nombre, la « cl´ e », a pr` es de 200 chiffres. Il est
public, alors que p et q sont gard´ es secrets. Les ordinateurs ne peuvent, en un temps
raisonnable, retrouver p et q ` a partir de n .
Deuxi` eme ´ etape
Le receveur calcule φ(n), o` u φ est la fonction d’Euler d´ efinie
comme suit : φ(n) est le nombre d’entiers dans {1, 2, . . . , n − 1} qui sont relativement
premiers avec n, pour n > 1 et φ(1) = 1. On montrera dans la proposition 7.8 que
φ(n) = (p − 1)(q − 1). Remarquons que cette formule fait appel aux facteurs inconnus p
et q de n. Calculer φ(n) sans connaˆ ıtre p et q semble aussi difficile que de factoriser n
(quoiqu’il n’y ait pas de preuve rigoureuse que les deux op´ erations soient aussi difficiles
l’une que l’autre).
Troisi` eme ´ etape : choix d’une cl´ e de cryptage Le receveur choisit e ∈ {1, . . . , n−
1} relativement premier avec φ(n). Le nombre e est la cl´ e de cryptage. Elle est publique.
L’exp´ editeur s’en sert pour encoder son message suivant les instructions publi´ ees par le
receveur.
Quatri` eme ´ etape : construction d’une cl´ e de d´ ecryptage Il existe d ∈ {1, . . . , n−
1} tel que ed ≡ 1 (mod φ(n)) (c’est-` a-dire que le reste de la division de ed par φ(n)
est 1). L’existence de d d´ ecoule du corollaire 7.6. La preuve du corollaire 7.6 et des
propositions sur lesquelles il repose, dont l’algorithme d’Euclide, donne la m´ ethode de
construction de d. Le nombre d, construit par le receveur, est la cl´ e de d´ ecryptage. Elle
est secr` ete et permet au receveur de d´ ecrypter les messages re¸ cus.
Cinqui` eme ´ etape : cryptage d’un message ` a envoyer L’exp´ editeur veut envoyer
un message qui est un nombre m appartenant `
a {1, . . . , n − 1}, relativement premier
avec n. Pour l’encoder, il calcule le reste a de la division de m
e par n. On a donc
m
e
≡ a (mod n), o` u a ∈ {1, . . . , n − 1}. Le a qu’il a calcul´ e est le message crypt´ e.
L’exp´ editeur envoie a. Nous verrons ci-dessous qu’il est facile pour un ordinateur de
calculer a, mˆ eme si m, e et n sont tr` es grands.
Sixi` eme ´ etape : d´ ecryptage du message re¸ cu Le receveur re¸ coit a. Pour d´ ecrypter,
il calcule a
d (mod n). Nous allons montrer `
a la proposition 7.10 que le reste de la division
de a
d par n est pr´ ecis´ ement le message initial m.
Avant de d´ etailler les diff´ erentes ´ etapes, regardons un exemple simple avec des petits
nombres.
Exemple 7.7 On prend p = 7 et q = 13. Alors, n = pq = 91. Quels sont les entiers
de E = {1, . . . , 90} qui ne sont pas relativement premiers avec 91 ? Ce sont 7, 13, 14,
21, 26, 28, 35, 39, 42, 49, 52, 56, 63, 65, 70, 77, 78, 84, soit 18 entiers. Il y a donc
90 − 18 = 72 entiers de E relativement premiers avec 91, ce qui donne φ(91) = 72.
Choisissons e = 29. On a bien (e, φ(n)) = 1. Appliquons l’algorithme d’Euclide pour
trouver d :
7 La cryptographie ` a cl´ e publique
Un syst` eme de cryptographie ` a cl´ e publique est mis sur pied par une personne ou
une organisation (que nous appellerons le receveur) qui veut recevoir des messages de
mani` ere s´ ecuritaire. C’est elle qui construit le syst` eme et publie la m´ ethode transmission
des messages.
Premi` ere ´ etape Le receveur choisit p et q deux grands nombres premiers (plus de
100 chiffres). Il calcule n = pq. Ce nombre, la « cl´ e », a pr` es de 200 chiffres. Il est
public, alors que p et q sont gard´ es secrets. Les ordinateurs ne peuvent, en un temps
raisonnable, retrouver p et q ` a partir de n .
Deuxi` eme ´ etape
Le receveur calcule φ(n), o` u φ est la fonction d’Euler d´ efinie
comme suit : φ(n) est le nombre d’entiers dans {1, 2, . . . , n − 1} qui sont relativement
premiers avec n, pour n > 1 et φ(1) = 1. On montrera dans la proposition 7.8 que
φ(n) = (p − 1)(q − 1). Remarquons que cette formule fait appel aux facteurs inconnus p
et q de n. Calculer φ(n) sans connaˆ ıtre p et q semble aussi difficile que de factoriser n
(quoiqu’il n’y ait pas de preuve rigoureuse que les deux op´ erations soient aussi difficiles
l’une que l’autre).
Troisi` eme ´ etape : choix d’une cl´ e de cryptage Le receveur choisit e ∈ {1, . . . , n−
1} relativement premier avec φ(n). Le nombre e est la cl´ e de cryptage. Elle est publique.
L’exp´ editeur s’en sert pour encoder son message suivant les instructions publi´ ees par le
receveur.
Quatri` eme ´ etape : construction d’une cl´ e de d´ ecryptage Il existe d ∈ {1, . . . , n−
1} tel que ed ≡ 1 (mod φ(n)) (c’est-` a-dire que le reste de la division de ed par φ(n)
est 1). L’existence de d d´ ecoule du corollaire 7.6. La preuve du corollaire 7.6 et des
propositions sur lesquelles il repose, dont l’algorithme d’Euclide, donne la m´ ethode de
construction de d. Le nombre d, construit par le receveur, est la cl´ e de d´ ecryptage. Elle
est secr` ete et permet au receveur de d´ ecrypter les messages re¸ cus.
Cinqui` eme ´ etape : cryptage d’un message ` a envoyer L’exp´ editeur veut envoyer
un message qui est un nombre m appartenant `
a {1, . . . , n − 1}, relativement premier
avec n. Pour l’encoder, il calcule le reste a de la division de m
e par n. On a donc
m
e
≡ a (mod n), o` u a ∈ {1, . . . , n − 1}. Le a qu’il a calcul´ e est le message crypt´ e.
L’exp´ editeur envoie a. Nous verrons ci-dessous qu’il est facile pour un ordinateur de
calculer a, mˆ eme si m, e et n sont tr` es grands.
Sixi` eme ´ etape : d´ ecryptage du message re¸ cu Le receveur re¸ coit a. Pour d´ ecrypter,
il calcule a
d (mod n). Nous allons montrer `
a la proposition 7.10 que le reste de la division
de a
d par n est pr´ ecis´ ement le message initial m.
Avant de d´ etailler les diff´ erentes ´ etapes, regardons un exemple simple avec des petits
nombres.
Exemple 7.7 On prend p = 7 et q = 13. Alors, n = pq = 91. Quels sont les entiers
de E = {1, . . . , 90} qui ne sont pas relativement premiers avec 91 ? Ce sont 7, 13, 14,
21, 26, 28, 35, 39, 42, 49, 52, 56, 63, 65, 70, 77, 78, 84, soit 18 entiers. Il y a donc
90 − 18 = 72 entiers de E relativement premiers avec 91, ce qui donne φ(91) = 72.
Choisissons e = 29. On a bien (e, φ(n)) = 1. Appliquons l’algorithme d’Euclide pour
trouver d :