Exo7

Cryptographie

Vidéo ■ partie 1. Le chiffrement de César

Vidéo ■ partie 2. Le chiffrement de Vigenère
Vidéo ■ partie 3. La machine Enigma et les clés secrètes
Vidéo ■ partie 4. La cryptographie à clé publique
Vidéo ■ partie 5. L'arithmétique pour RSA
Vidéo ■ partie 6. Le chiffrement RSA

1. Le chiffrement de César

1.1. César a dit...

Jules César a-t-il vraiment prononcé la célèbre phrase :

DOHD MDFWD HVW
ou bien comme le disent deux célèbres Gaulois : « Ils sont fous ces romains ! ».
En fait César, pour ses communications importantes à son armée, cryptait ses messages. Ce que
l’on appelle le chiffrement de César est un décalage des lettres : pour crypter un message, A
devient D, B devient E, C devient F,...

A 7−→ D B 7−→ E C 7−→ F ... W 7−→ Z X 7−→ A Y 7−→ B Z 7−→ C

Voici une figure avec l’alphabet d’origine en haut et en rouge, en correspondance avec l’alphabet
pour le chiffrement en-dessous et en vert.

Nous adopterons la convention suivante, en vert c’est la partie du message à laquelle tout le
monde a accès (ou qui pourrait être intercepté), c’est donc le message crypté. Alors qu’en rouge
c’est la partie du message confidentiel, c’est le message en clair.
Pour prendre en compte aussi les dernières lettres de l’alphabet, il est plus judicieux de représenté
l’alphabet sur un anneau. Ce décalage est un décalage circulaire sur les lettres de l’alphabet.

1
 2

Pour déchiffrer le message de César, il suffit de décaler les lettres dans l’autre sens, D se déchiffre
en A, E en B,...
Et la célèbre phrase de César est :
ALEA JACTA EST
qui traduite du latin donne « Les dés sont jetés ».

1.2. Des chiffres et des lettres

Il est plus facile de manipuler des nombres que des lettres, aussi nous passons à une formulation
mathématique. Nous associons à chacune des 26 lettres de A à Z un nombre de 0 à 25. En termes
mathématiques, nous définissons une bijection :
© ª © ª
f : A, B, C, . . . , Z −→ 0, 1, 2, . . . , 25

par
A 7−→ 0 B 7−→ 1 C 7−→ 2 ... Z 7−→ 25

Ainsi "A L E A" devient "0 11 4 0".

Le chiffrement de César est un cas particulier de chiffrement mono-alphabétique, c’est-à-dire
un chiffrement lettre à lettre.
Quel est l’intérêt ? Nous allons voir que le chiffrement de César correspond à une opération mathé-
matique très simple. Pour cela, rappelons la notion de congruence et l’ensemble Z/26Z.

1.3. Modulo
Soit n Ê 2 un entier fixé.
Définition 1

On dit que a est congru à b modulo n, si n divise b − a. On note alors

a ≡ b (mod n).

Pour nous n = 26. Ce qui fait que 28 ≡ 2 (mod 26), car 28 − 2 est bien divisible par 26. De même
85 = 3 × 26 + 7 donc 85 ≡ 7 (mod 26).
On note Z/26Z l’ensemble de tous les éléments de Z modulo 26. Cet ensemble peut par exemple
être représenté par les 26 éléments {0, 1, 2, . . . , 25}. En effet, puisqu’on compte modulo 26 :

0, 1, 2, . . . , 25, puis 26 ≡ 0, 27 ≡ 1, 28 ≡ 2, . . . , 52 ≡ 0, 53 ≡ 1, . . .

et de même −1 ≡ 25, −2 ≡ 24,...

 3

Plus généralement Z/nZ contient n éléments. Pour un entier a ∈ Z quelconque, son représentant
dans {0, 1, 2, . . . , n − 1} s’obtient comme le reste k de la division euclidienne de a par n : a = bn + k.
De sorte que a ≡ k (mod n) et 0 É k < n.

De façon naturelle l’addition et la multiplication d’entiers se transposent dans Z/nZ.

Pour a, b ∈ Z/nZ, on associe a + b ∈ Z/nZ.

Par exemple dans Z/26Z, 15 + 13 égale 2. En effet 15 + 13 = 28 ≡ 2 (mod 26). Autre exemple : que
vaut 133 + 64 ? 133 + 64 = 197 = 7 × 26 + 15 ≡ 15 (mod 26). Mais on pourrait procéder différemment :
tout d’abord 133 = 5 × 26 + 3 ≡ 3 (mod 26) et 64 = 2 × 26 + 12 ≡ 12 (mod 26). Et maintenant sans
calculs : 133 + 64 ≡ 3 + 12 ≡ 15 (mod 26).

On fait de même pour la multiplication : pour a, b ∈ Z/nZ, on associe a × b ∈ Z/nZ.

Par exemple 3 × 12 donne 10 modulo 26, car 3 × 12 = 36 = 1 × 26 + 10 ≡ 10 (mod 26). De même :
3 × 27 = 81 = 3 × 26 + 3 ≡ 3 (mod 26). Une autre façon de voir la même opération est d’écrire d’abord
27 = 1 (mod 26) puis 3 × 27 ≡ 3 × 1 ≡ 3 (mod 26).

1.4. Chiffrer et déchiffrer

Le chiffrement de César est simplement une addition dans Z/26Z ! Fixons un entier k qui est
le décalage (par exemple k = 3 dans l’exemple de César ci-dessus) et définissons la fonction de
chiffrement de César de décalage k qui va de l’ensemble Z/26Z dans lui-même :
(
Z/26Z −→ Z/26Z
Ck :
x 7−→ x+ k

Par exemple, pour k = 3 : C 3 (0) = 3, C 3 (1) = 4. . .

Pour déchiffrer, rien de plus simple ! Il suffit d’aller dans l’autre sens, c’est-à-dire ici de soustraire.
La fonction de déchiffrement de César de décalage k est
(
Z/26Z −→ Z/26Z
Dk :
x 7−→ x− k

En effet, si 1 a été chiffré en 4, par la fonction C 3 alors D 3 (4) = 4 − 3 = 1. On retrouve le nombre

original. Mathématiquement, D k est la bijection réciproque de C k , ce qui implique que pour tout
x ∈ Z/26Z :
¡ ¢
D k C k (x) = x

En d’autres termes, si x est un nombre, on applique la fonction de chiffrement pour obtenir le

nombre crypté y = C k (x) ; ensuite la fonction de déchiffrement fait bien ce que l’on attend d’elle
D k (y) = x, on retrouve le nombre original x.

Ck

Z/26Z Z/26Z

Dk
 4

Une autre façon de voir la fonction de déchiffrement est de remarquer que D k (x) = C −k (x). Par
exemple C −3 (x) = x + (−3) ≡ x + 23 (mod 26).

Voici le principe du chiffrement : Alice veut envoyer des messages secrets à Bruno. Ils se sont
d’abord mis d’accord sur une clé secrète k, par exemple k = 11. Alice veut envoyer le message
"COUCOU" à Bruno. Elle transforme "COUCOU" en "2 14 20 2 14 20". Elle applique la fonction
de chiffrement C 11 (x) = x + 11 à chacun des nombres : "13 25 5 13 25 5" ce qui correspond au mot
crypté "NZFNZF". Elle transmet le mot crypté à Bruno, qui selon le même principe applique la
fonction de déchiffrement D 11 (x) = x − 11.

ALICE BRUNO

COUCOU NZFNZF NZFNZF COUCOU

Ck Dk

2 14 20 2 14 20 13 25 5 13 25 5 13 25 5 13 25 5 2 14 20 2 14 20

Exemple 1

Un exemple classique est le "rot13" (pour rotation par un décalage de 13) :

C 13 (x) = x + 13

et comme −13 ≡ 13 (mod 26) alors D 13 (x) = x + 13. La fonction de déchiffrement est la même
que la fonction de chiffrement !
Exemple : déchiffrez le mot "PRFNE".

Notons ici deux points importants pour la suite : tout d’abord nous avons naturellement considéré
un mot comme une succession de lettres, et chaque opération de chiffrement et déchiffrement
s’effectue sur un bloc d’une seule lettre. Ensuite nous avons vu que chiffrer un message est une
opération mathématique (certes sur un ensemble un peu spécial).

1.5. Espace des clés et attaque

Combien existe-t-il de possibilités de chiffrement par la méthode de César ? Il y a 26 fonctions C k
différentes, k = 0, 1, . . . , 25. Encore une fois, k appartient à Z/26Z, car par exemple les fonctions C 29
et C 3 sont identiques. Le décalage k s’appelle la clé de chiffrement, c’est l’information nécessaire
pour crypter le message. Il y a donc 26 clés différentes et l’espace des clés est Z/26Z.

Il est clair que ce chiffrement de César est d’une sécurité très faible. Si Alice envoie un message
secret à Bruno et que Chloé intercepte ce message, il sera facile pour Chloé de le décrypter même
si elle ne connaît pas la clé secrète k. L’attaque la plus simple pour Chloé est de tester ce que
donne chacune des 26 combinaisons possibles et de reconnaître parmi ces combinaisons laquelle
donne un message compréhensible.

1.6. Algorithmes
Les ordinateurs ont révolutionné la cryptographie et surtout le décryptage d’un message intercepté.
Nous montrons ici, à l’aide du langage Python comment programmer et attaquer le chiffrement de
César. Tout d’abord la fonction de chiffrement se programme en une seule ligne :
 5

Algorithme . [Link] (1)

def cesar_chiffre_nb(x,k):
return (x+k)%26

Ici x est un nombre de {0, 1, . . . , 25} et k est le décalage. (x+k)%26 renvoie le reste modulo 26 de la
somme (x+k). Pour le décryptage, c’est aussi simple :
Algorithme . [Link] (2)

def cesar_dechiffre_nb(x,k):
return (x-k)%26

Pour chiffrer un mot ou un phrase, il n’y a pas de problèmes théoriques, mais seulement des
difficultés techniques :
– Un mot ou une phrase est une chaîne de caractères, qui en fait se comporte comme une liste.
Si mot est une chaîne alors mot[0] est la première lettre, mot[1] la deuxième lettre... et la
boucle for lettre in mot: permet de parcourir chacune des lettres.
– Pour transformer une lettre en un nombre, on utilise le code Ascii qui à chaque caractère
associe un nombre, ord(A) vaut 65, ord(B) vaut 66... Ainsi (ord(lettre) - 65) renvoie le
rang de la lettre entre 0 et 25 comme nous l’avons fixé dès le départ.
– La transformation inverse se fait par la fonction char : char(65) renvoie le caractère A,
char(66) renvoie B...
– Pour ajouter une lettre à une liste, faites [Link](lettre). Enfin pour transformer
une liste de caractères en une chaîne, faites "".join(maliste).
Ce qui donne :
Algorithme . [Link] (3)

def cesar_chiffre_mot(mot,k):
message_code = [] # Liste vide
for lettre in mot: # Pour chaque lettre
nb = ord(lettre)-65 # Lettre devient nb de 0 à 25
nb_crypte = cesar_chiffre(nb,k) # Chiffrement de César
lettre_crypte = chr(nb_crypte+65) # Retour aux lettres
message_code.append(lettre_crypte) # Ajoute lettre au message
message_code = "".join(message_code) # Revient à chaine caractères
return(message_code)

Pour l’attaque on parcourt l’intégralité de l’espace des clés : k varie de 0 à 25. Noter que pour
décrypter les messages on utilise ici simplement la fonction de César avec la clé − k.
 6

Algorithme . [Link] (4)

def cesar_attaque(mot):
for k in range(26):
print(cesar_chiffre_mot(mot,-k))
return None

2. Le chiffrement de Vigenère

2.1. Chiffrement mono-alphabétique

Principe

Nous avons vu que le chiffrement de César présente une sécurité très faible, la principale raison
est que l’espace des clés est trop petit : il y a seulement 26 clés possibles, et on peut attaquer un
message chiffré en testant toutes les clés à la main.
Au lieu de faire correspondre circulairement les lettres, on associe maintenant à chaque lettre une
autre lettre (sans ordre fixe ou règle générale).
Par exemple :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
F Q B M X I T E P A L W H S D O Z K V G R C N Y J U

Pour crypter le message

ETRE OU NE PAS ETRE TELLE EST LA QUESTION
on regarde la correspondance et on remplace la lettre E par la lettre X, puis la lettre T par la lettre
G, puis la lettre R par la lettre K...
Le message crypté est alors :
XGKX DR SX OFV XGKX GXWWX XVG WF ZRXVGPDS
Pour le décrypter, en connaissant les substitutions, on fait l’opération inverse.

Avantage : nous allons voir que l’espace des clés est gigantesque et qu’il n’est plus question d’énu-
mérer toutes les possibilités.
Inconvénients : la clé à retenir est beaucoup plus longue, puisqu’il faut partager la clé consti-
tuée des 26 lettres "FQBMX...". Mais surtout, nous allons voir que finalement ce protocole de
chiffrement est assez simple à « craquer ».

Espace des clés

© ª
Mathématiquement, le choix d’une clé revient au choix d’une bijection de l’ensemble A, B, . . . , Z
© ª
vers le même ensemble A, B, . . . , Z . Il y a 26! choix possibles. En effet pour la lettre A de l’ensemble
de départ, il y a 26 choix possibles (nous avions choisi F), pour B il reste 25 choix possibles (tout
sauf F qui est déjà choisi), pour C il reste 24 choix... enfin pour Z il ne reste qu’une seule possibilité,
la seule lettre non encore choisie. Au final il y a : 26 × 25 × 24 × · · · × 2 × 1 soit 26! choix de clés. Ce
qui fait environ 4 × 1026 clés. Il y a plus de clés différentes que de grains de sable sur Terre ! Si un
ordinateur pouvait tester 1 000 000 de clés par seconde, il lui faudrait alors 12 millions d’années
pour tout énumérer.
 7

Attaque statistique

La principale faiblesse du chiffrement mono-alphabétique est qu’une même lettre est toujours
chiffrée de la même façon. Par exemple, ici E devient X. Dans les textes longs, les lettres n’ap-
paraissent pas avec la même fréquence. Ces fréquences varient suivant la langue utilisée. En
français, les lettres les plus rencontrées sont dans l’ordre :
ESAINTRULODCPMVQGFHBXJYZKW
avec les fréquences (souvent proches et dépendant de l’échantillon utilisé) :

E S A I N T R U L O D
14.69% 8.01% 7.54% 7.18% 6.89% 6.88% 6.49% 6.12% 5.63% 5.29% 3.66%

Voici la méthode d’attaque : dans le texte crypté, on cherche la lettre qui apparaît le plus, et si
le texte est assez long cela devrait être le chiffrement du E, la lettre qui apparaît ensuite dans
l’étude des fréquences devrait être le chiffrement du S, puis le chiffrement du A... On obtient
des morceaux de texte clair sous la forme d’une texte à trous et il faut ensuite deviner les lettres
manquantes.

Par exemple, déchiffrons la phrase :

LHLZ HFQ BC HFFPZ WH YOUPFH MUPZH
On compte les apparitions des lettres :
H:6 F:4 P:3 Z:3
On suppose donc que le H crypte la lettre E, le F la lettre S, ce qui donne
*E** ES* ** ESS** *E ***SE ****E
D’après les statistiques P et Z devraient se décrypter en A et I (ou I et A). Le quatrième mot
"HFFPZ", pour l’instant décrypté en "ESS**", se complète donc en "ESSAI" ou "ESSIA". La
première solution semble correcte ! Ainsi P crypte A, et Z crypte I. La phrase est maintenant :
*E*I ES* ** ESSAI *E ***ASE **AIE
En réfléchissant un petit peu, on décrypte le message :
CECI EST UN ESSAI DE PHRASE VRAIE

2.2. Le chiffrement de Vigenère

Blocs

L’espace des clés du chiffrement mono-alphabétique est immense, mais le fait qu’une lettre soit
toujours cryptée de la même façon représente une trop grande faiblesse. Le chiffrement de Vigenère
remédie à ce problème. On regroupe les lettres de notre texte par blocs, par exemple ici par blocs
de longueur 4 :
CETTE PHRASE NE VEUT RIEN DIRE
devient
CETT EPHR ASEN EVEU TRIE NDIR E
(les espaces sont purement indicatifs, dans la première phrase ils séparent les mots, dans la
seconde ils séparent les blocs).
Si k est la longueur d’un bloc, alors on choisit une clé constituée de k nombres de 0 à 25 :
(n 1 , n 2 , . . . , n k ). Le chiffrement consiste à effectuer un chiffrement de César, dont le décalage dépend
du rang de la lettre dans le bloc :
– un décalage de n 1 pour la première lettre de chaque bloc,
– un décalage de n 2 pour la deuxième lettre de chaque bloc,
– ...
– un décalage de n k pour la k-ème et dernière lettre de chaque bloc.
 8

Pour notre exemple, si on choisit comme clé (3, 1, 5, 2) alors pour le premier bloc "CETT" :
– un décalage de 3 pour C donne F,
– un décalage de 1 pour E donne F,
– un décalage de 5 pour le premier T donne Y,
– un décalage de 2 pour le deuxième T donne V.
Ainsi "CETT" de vient "FFYV". Vous remarquez que les deux lettres T ne sont pas cryptées par
la même lettre et que les deux F ne cryptent pas la même lettre. On continue ensuite avec le
deuxième bloc...

Mathématiques

L’élément de base n’est plus une lettre mais un bloc, c’est-à-dire un regroupement de lettres. La
fonction de chiffrement associe à un bloc de longueur k, un autre bloc de longueur k, ce qui donne
en mathématisant les choses :
(
Z/26Z × Z/26Z × · · · × Z/26Z −→ Z/26Z × Z/26Z × · · · × Z/26Z
C n1 ,n2 ,...,n k :
(x1 , x2 , . . . , xk ) 7−→ (x1 + n 1 , x2 + n 2 , . . . , xk + n k )

Chacune des composantes de cette fonction est un chiffrement de César. La fonction de déchiffre-
ment est juste C −n1 ,−n2 ,...,−n k .

Espace des clés et attaque

Il y a 26k choix possibles de clés, lorsque les blocs sont de longueur k. Pour des blocs de longueur
k = 4 cela en donne déjà 456 976, et même si un ordinateur teste toutes les combinaisons possibles
sans problème, il n’est pas question de parcourir cette liste pour trouver le message en clair, c’est-
à-dire celui qui est compréhensible !
Il persiste tout de même une faiblesse du même ordre que celle rencontrée dans le chiffrement
mono-alphabétique : la lettre A n’est pas toujours cryptée par la même lettre, mais si deux lettres
A sont situées à la même position dans deux blocs différents (comme par exemple "ALPH ABET")
alors elles seront cryptées par la même lettre.
Une attaque possible est donc la suivante : on découpe notre message en plusieurs listes, les
premières lettres de chaque bloc, les deuxièmes lettres de chaque bloc... et on fait une attaque
statistique sur chacun de ces regroupements. Ce type d’attaque n’est possible que si la taille des
blocs est petite devant la longueur du texte.

2.3. Algorithmes
Voici un petit algorithme qui calcule la fréquence de chaque lettre d’une phrase.
Algorithme . [Link]

def statistiques(phrase):
liste_stat = [0 for x in range(26)] # Une liste avec des 0
for lettre in phrase: # On parcourt la phrase
i = ord(lettre)-65
if 0 <= i < 26: # Si c'est une vraie lettre
liste_stat[i] = liste_stat[i] + 1
return(liste_stat)
 9

Et voici le chiffrement de Vigenère.

Algorithme . [Link]

def vigenere(mot,cle): # Clé est du type [n_1,...,n_k]

message_code = []
k = len(cle) # Longueur de la clé
i = 0 # Rang dans le bloc
for lettre in mot: # Pour chaque lettre
nomb = ord(lettre)-65 # Lettre devient nb de 0 à 25
nomb_code = (nomb+cle[i]) % 26 # Vigenère : on ajoute n_i
lettre_code = chr(nomb_code+65) # On repasse aux lettres
i=(i+1) % k # On passe au rang suivant
message_code.append(lettre_code) # Ajoute lettre au message
message_code = "".join(message_code) # Revient à chaine caractères
return(message_code)

3. La machine Enigma et les clés secrètes

3.1. Un secret parfait

L’inconvénient des chiffrements précédents est qu’une même lettre est régulièrement chiffrée de
la même façon, car la correspondance d’un alphabet à un ou plusieurs autres est fixée une fois
pour toutes, ce qui fait qu’une attaque statistique est toujours possible. Nous allons voir qu’en
changeant la correspondance à chaque lettre, il est possible de créer un chiffrement parfait !
Expliquons d’abord le principe à l’aide d’une analogie : j’ai choisi deux entiers m et c tels que
m + c = 100. Que vaut m ? C’est bien sûr impossible de répondre car il y a plusieurs possibilités :
0 + 100, 1 + 99, 2 + 98,... Par contre, si je vous donne aussi c alors vous trouvez m immédiatement
m = 100 − c.

Voici le principe du chiffrement : Alice veut envoyer à Bruno le message secret M suivant :
ATTAQUE LE CHATEAU
Alice a d’abord choisi une clé secrète C qu’elle a transmise à Bruno. Cette clé secrète est de la
même longueur que le message (les espaces ne comptent pas) et composée d’entiers de 0 à 25, tirés
au hasard. Par exemple C :
[4, 18, 2, 0, 21, 12, 18, 13, 7, 11, 23, 22, 19, 2, 16, 9]
Elle crypte la première lettre par un décalage de César donné par le premier entier : A est décalé
de 4 lettres et devient donc E. La seconde lettre est décalée du second entier : le premier T devient
L. Le second T est lui décalé de 2 lettres, il devient V. Le A suivant est décalé de 0 lettre, il reste
A... Alice obtient un message chiffré X qu’elle transmet à Bruno :
ELVALGW YL NEWMGQD
Pour le décrypter, Bruno, qui connaît la clé, n’a qu’à faire le décalage dans l’autre sens.
Notez que deux lettres identiques (par exemples les T) n’ont aucune raison d’être cryptées de la
même façon. Par exemple, les T du message initial sont cryptés dans l’ordre par un L, un V et un
M.

Formalisons un peu cette opération. On identifie A avec 0, B avec 1, ..., Z avec 25. Alors le message
crypté X est juste la "somme" du message M avec la clé secrète C, la somme s’effectuant lettre à
10

lettre, terme à terme, modulo 26.

Notons cette opération M ⊕ C = X .

A T T A Q U E L E C H A T E A U
0 19 19 0 16 20 4 11 4 2 7 0 19 4 0 20
⊕
4 18 2 0 21 12 18 13 7 11 23 22 19 2 16 9

= 4 11 21 0 11 6 22 24 11 13 4 22 12 6 16 3
E L V A L G W Y L N E W M G Q D

Bruno reçoit X et connaît C, il effectue donc X ª C = M.

Pourquoi ce système est-il inviolable ? Pour chacune des lettres, c’est exactement le même problème
que trouver m, sachant que m + c = x (où x = 100), mais sans connaître c. Toutes les possibilités
pour m pourraient être juste. Et bien sûr, dès que l’on connaît c, la solution est triviale : m = x − c.
Il y a trois principes à respecter pour que ce système reste inviolable :

1. La longueur de la clé est égale à la longueur du message.

2. La clé est choisie au hasard.
3. La clé ne sert qu’une seule fois.

Ce système appelé "masque jetable" ou chiffrement de Vernam est parfait en théorie, mais sa
mise en œuvre n’est pas pratique du tout ! Tout d’abord il faut que la clé soit aussi longue que le
message. Pour un message court cela ne pose pas de problème, mais pour envoyer une image par
exemple cela devient très lourd. Ensuite, il faut trouver un moyen sûr d’envoyer la clé secrète à
son interlocuteur avant de lui faire parvenir le message. Et il faut recommencer cette opération à
chaque message, ou bien se mettre d’accord dès le départ sur un carnet de clés : une longue liste
de clés secrètes.
Pour justifier que ce système est vraiment inviolable voici une expérience amusante : Alice veut
envoyer le message M ="ATTAQUE LE CHATEAU" à Bruno, elle choisit la clé secrète C=[4, 18,
2, 0,...] comme ci-dessus et obtient le message chiffré X ="ELVA..." qu’elle transmet à Bruno.
Alice se fait kidnapper par Chloé, qui veut l’obliger à déchiffrer son message. Heureusement, Alice
a anticipé les soucis : elle a détruit le message M, la clé secrète C et a créé un faux message M 0 et
une fausse clé secrète C 0 . Alice fournit cette fausse clé secrète C 0 à Chloé, qui déchiffre le message
par l’opération X ª C 0 et elle trouve le message bien inoffensif M 0 :
RECETTE DE CUISINE
Alice est innocentée !
Comment est-ce possible ? Alice avait au préalable préparé un message neutre M 0 de même lon-
gueur que M et calculé la fausse clé secrète C 0 = X ª M 0 . Chloé a obtenu (par la contrainte) X et
C 0 , elle déchiffre le message ainsi

X ª C 0 = X ª (X ª M 0 ) = (X ª X ) ⊕ M 0 = M 0

Chloé trouve donc le faux message.

Ici la fausse clé C 0 est :
[13, 7, 19, 22, 18, 13, 18, 21, 7, 11, 10, 14, 20, 24, 3, 25]
La première lettre du message chiffré est un E, en reculant de 13 lettres dans l’alphabet, elle se
déchiffre en R...
 11

3.2. La machine Enigma

Afin de s’approcher de ce protocole de chiffrement parfait, il faut trouver un moyen de générer

facilement de longues clés, comme si elles avaient été générées au hasard. Nous allons étudier
deux exemples utilisés en pratique à la fin du siècle dernier, une méthode électro-mécanique : la
machine Enigma et une méthode numérique : le D E S .

La machine Enigma est une machine électro-mécanique qui ressemble à une machine à écrire.
Lorsque qu’une touche est enfoncée, des disques internes sont actionnés et le caractère crypté
s’allume. Cette machine, qui sert aussi au déchiffrement, était utilisée pour les communications
de l’armée allemande durant la seconde guerre mondiale. Ce que les Allemands ne savaient pas,
c’est que les services secrets polonais et britanniques avaient réussi à percer les secrets de cette
machine et étaient capables de déchiffrer les messages transmis par les allemands. Ce long travail
d’études et de recherches a nécessité tout le génie d’Alan Turing et l’invention de l’ancêtre de
l’ordinateur.

Nous symbolisons l’élément de base de la machine Enigma par deux anneaux :

– Un anneau extérieur contenant l’alphabet "ABCDE..." symbolisant le clavier de saisie des

messages. Cet anneau est fixe.
– Un anneau intérieur contenant un alphabet dans le désordre (sur la figure "GWQRU...").
Cet anneau est mobile et effectue une rotation à chaque touche tapée au clavier. Il représente
la clé secrète.

Voici, dans ce cas, le processus de chiffrement du mot "BAC", avec la clé de chiffrement "G" :

1. Position initiale. L’opérateur tourne l’anneau intérieur de sorte que le A extérieur et fixe
soit en face du G intérieur (et donc B en face de W).
12

2. Première lettre. L’opérateur tape la première lettre du message : B, la machine affiche la

correspondance W.
3. Rotation. L’anneau intérieur tourne de 1/26ème de tour, maintenant le A extérieur et fixe
est en face du W, le B en face du Q,...

4. Deuxième lettre. L’opérateur tape la deuxième lettre du message A, la machine affiche la

correspondance, c’est de nouveau W.
5. Rotation. L’anneau intérieur tourne de 1/26ème de tour, maintenant le A extérieur et fixe
est en face du Q, le B en face du R, le C en face du U,...

6. Troisième lettre. L’opérateur tape la troisième lettre du message C, la machine affiche la

correspondance U.
7. Rotation. L’anneau intérieur effectue sa rotation.
8. Message chiffré. Le message crypté est donc "WWU"
Cette méthode de chiffrement est identique à un chiffrement de type Vigenère pour une clé de
longueur 26. Il y a 26 clés différents à disposition avec un seul anneau intérieur et identifiées par
lettre de la position initiale : G, W, Q... T correspondant aux alphabets : "GWQ...PT", "WQR...TG",
"QRU...GW"...
En fait, la machine Enigma était beaucoup plus sophistiquée, il n’y avait pas un mais plusieurs
anneaux intérieurs. Par exemple pour deux anneaux intérieurs comme sur la figure : B s’envoie sur
W, qui s’envoie sur A ; la lettre B est cryptée en A. Ensuite l’anneau intérieur numéro 1 effectue
1/26ème de tour. La lettre A s’envoie sur W, qui s’envoie sur A ; la lettre A est cryptée en A. Lorsque
 13

l’anneau intérieur numéro 1 a fait une rotation complète (26 lettres ont été tapées) alors l’anneau
intérieur numéro 2 effectue 1/26ème de tour. C’est comme sur un compteur kilométrique, lorsque
le chiffre des kilomètres parcourt 0, 1, 2, 3, ..., 9, alors au kilomètre suivant, le chiffre des kilomètres
est 0 et celui des dizaines de kilomètres est augmenté d’une unité.

S’il y a trois anneaux, lorsque l’anneau intérieur 2 a fait une rotation complète, l’anneau intérieur
3 tourne de 1/26ème de tour. Il y a alors 263 clés différentes facilement identifiables par les trois
lettres des positions initiales des anneaux.
Il fallait donc pour utiliser cette machine, d’abord choisir les disques (nos anneaux intérieurs) les
placer dans un certain ordre, fixer la position initiale de chaque disque. Ce système était rendu
largement plus complexe avec l’ajout de correspondances par fichage entre les lettres du clavier
(voir photo). Le nombre de clés possibles dépassait plusieurs milliards de milliards !

3.3. La ronde des chiffres : DES

La machine Enigma génère mécaniquement un alphabet différent à chaque caractère crypté,
tentant de se rapprocher d’un chiffrement parfait. Nous allons voir une autre méthode, cette fois
numérique : le DES. Le DES (Data Encryption Standard) est un protocole de chiffrement par blocs.
Il a été, entre 1977 et 2001, le standard de chiffrement pour les organisations du gouvernement
des États-Unis et par extension pour un grand nombre de pays dans le monde.

Commençons par rappeler que l’objectif est de générer une clé aléatoire de grande longueur. Pour
ne pas avoir à retenir l’intégralité de cette longue clé, on va la générer de façon pseudo-aléatoire à
partir d’une petite clé.
Voyons un exemple élémentaire de suite pseudo-aléatoire.
Soit (u n ) la suite définie par la donnée de (a, b) et de u 0 et la relation de récurrence

u n+1 ≡ a × u n + b (mod 26).

Par exemple pour a = 2, b = 5 et u 0 = 6, alors les premiers termes de la suites sont :

6 17 13 5 15 9 23 25 3 11 1 7 19 17 13 5
14

Les trois nombres (a, b, u 0 ) représentent la clé principale et la suite des (u n )n∈N les clés secondaires.
Avantages : à partir d’une clé principale on a généré une longue liste de clés secondaires. Inconvé-
nients : la liste n’est pas si aléatoire que cela, elle se répète ici avec une période de longueur 12 :
17, 13, 5, ..., 17, 13, 5, ...

Le système DES est une version sophistiquée de ce processus : à partir d’une clé courte et d’opéra-
tions élémentaires on crypte un message. Comme lors de l’étude de la machine Enigma, nous allons
présenter une version très simplifiée de ce protocole afin d’en expliquer les étapes élémentaires.
Pour changer, nous allons travailler modulo 10. Lorsque l’on travaille par blocs, les additions se
font bit par bit. Par exemple : [1 2 3 4] ⊕ [7 8 9 0] = [8 0 2 4] car (1 + 7 ≡ 8 (mod 10), 2 + 8 ≡ 0
(mod 10),...)
Notre message est coupé en blocs, pour nos explications ce seront des blocs de longueur 8. La clé
est de longueur 4.
Voici le message (un seul bloc) : M = [1 2 3 4 5 6 7 8] et voici la clé : C = [3 1 3 2].

Étape 0. Initialisation. On note M0 = M et on découpe M en une partie gauche et une partie

droite
M0 = [G 0 k D 0 ] = [1 2 3 4 k 5 6 7 8]

Étape 1. Premier tour. On pose

M1 = [D 0 k C ⊕ σ(G 0 )]

où σ est une permutation circulaire.

On effectue donc trois opérations pour passer de M0 à M1 :
1. On échange la partie droite et la partie gauche de M0 :

M0 7−→ [5 6 7 8 k 1 2 3 4]

2. Sur la nouvelle partie droite, on permute circulairement les nombres :

7−→ [5 6 7 8 k 2 3 4 1]

3. Puis on ajoute la clé secrète C à droite (ici C = [3 1 3 2]) :

7−→ [5 6 7 8 k 5 4 7 3] = M1

On va recommencer le même processus. Cela revient à appliquer la formule de récurrence, qui

partant de M i = [G i k D i ], définit

M i+1 = [D i k C ⊕ σ(G i )]

Étape 2. Deuxième tour. On part de M1 = [5 6 7 8 k 5 4 7 3].

1. On échange la partie droite et la partie gauche de M0 :

M0 7−→ [5 4 7 3 k 5 6 7 8]

2. Sur la nouvelle partie droite, on permute circulairement les nombres.

7−→ [5 4 7 3 k 6 7 8 5]
 15

3. Puis on ajoute la clé secrète C à droite.

7−→ [5 4 7 3 k 9 8 1 7] = M2

On peut décider de s’arrêter après ce tour et renvoyer le message crypté X = M2 = [5 4 7 3 9 8 1 7].

Comme chaque opération élémentaire est inversible, on applique un protocole inverse pour déchif-
frer.
Dans le vrai protocole du DES, la clé principale est de taille 64 bits, il y a plus de manipulations
sur le message et les étapes mentionnées ci-dessus sont effectuées 16 fois (on parle de tours). À
chaque tour, une clé différente est utilisée. Il existe donc un préambule à ce protocole : générer 16
clés secondaires (de longueur 48 bits) à partir de la clé principale, ce qui se fait selon le principe
de la suite pseudo-aléatoire (u n ) expliquée plus haut.

4. La cryptographie à clé publique

Les Grecs pour envoyer des messages secrets rasaient la tête du messager, tatouaient le message
sur son crâne et attendaient que les cheveux repoussent avant d’envoyer le messager effectuer sa
mission !
Il est clair que ce principe repose uniquement sur le secret de la méthode.

4.1. Le principe de Kerckhoffs

Cette méthode rudimentaire va à l’encontre du principe de Kerckhoffs. Le principe de Kerckhoffs
s’énonce ainsi :
«La sécurité d’un système de chiffrement ne doit reposer que sur la clé.»

Cela se résume aussi par :

«L’ennemi peut avoir connaissance du système de chiffrement.»

Voici le texte original d’Auguste Kerckhoffs de 1883 «La cryptographie militaire» paru dans le
Journal des sciences militaires.
Il traite notamment des enjeux de sécurité lors des correspondances :
«Il faut distinguer entre un système d’écriture chiffré, imaginé pour un échange
momentané de lettres entre quelques personnes isolées, et une méthode de cryptogra-
phie destinée à régler pour un temps illimité la correspondance des différents chefs
d’armée entre eux.»
Le principe fondamental est le suivant :
«Dans le second cas, [. . . ] il faut que le système n’exige pas le secret, et qu’il
puisse sans inconvénient tomber entre les mains de l’ennemi.»
Ce principe est novateur dans la mesure où intuitivement il semble opportun de dissimuler le maxi-
mum de choses possibles : clé et système de chiffrement utilisés. Mais l’objectif visé par Kerckhoffs
est plus académique, il pense qu’un système dépendant d’un secret mais dont le mécanisme est
connu de tous sera testé, attaqué, étudié, et finalement utilisé s’il s’avère intéressant et robuste.

4.2. Factorisations des entiers

Quels outils mathématiques répondent au principe de Kerckoffs ?
Un premier exemple est la toute simple multiplication ! En effet si je vous demande combien font
5 × 7, vous répondez 35. Si je vous demande de factoriser 35 vous répondez 5 × 7. Cependant ces
 16

deux questions ne sont pas du même ordre de difficulté. Si je vous demande de factoriser 1591,
vous aller devoir faire plusieurs tentatives, alors que si je vous avais directement demandé de
calculer 37 × 43 cela ne pose pas de problème.
Pour des entiers de plusieurs centaines de chiffres le problème de factorisation ne peut être résolu
en un temps raisonnable, même pour un ordinateur. C’est ce problème asymétrique qui est à la
base de la cryptographie RSA (que nous détaillerons plus tard) : connaître p et q apporte plus
d’information utilisable que p × q. Même si en théorie à partir de p × q on peut retrouver p et q,
en pratique ce sera impossible.

Formalisons ceci avec la notion de complexité. La complexité est le temps de calculs (ou le nombre
d’opérations élémentaires) nécessaire pour effectuer une opération.
Commençons par la complexité de l’addition : disons que calculer la somme de deux chiffres (par
exemple 6 + 8) soit de complexité 1 (par exemple 1 seconde pour un humain, 1 milliseconde pour
un ordinateur). Pour calculer la somme de deux entiers à n chiffres, la complexité est d’ordre
n (exemple : 1234 + 2323, il faut faire 4 additions de chiffres, donc environ 4 secondes pour un
humain).
La multiplication de deux entiers à n chiffres est de complexité d’ordre n2 . Par exemple pour
multiplier 1234 par 2323 il faut faire 16 multiplications de chiffres (chaque chiffre de 1234 est à
multiplier par chaque chiffre de 2323).
1
Par contre la meilleure méthode de factorisation connue est de complexité d’ordre exp(4n 3 ) (c’est
moins que exp(n), mais plus que n d pour tout d, lorsque n tend vers +∞).
Voici un tableau pour avoir une idée de la difficulté croissante pour multiplier et factoriser des
nombres à n chiffres :

n multiplication factorisation
3 9 320
4 16 572
5 25 934
10 100 5 528
50 2 500 2 510 835
100 10 000 115 681 968
200 40 000 14 423 748 780

4.3. Fonctions à sens unique

Il existe bien d’autres situations mathématiques asymétriques : les fonctions à sens unique. En
d’autres termes, étant donnée une fonction f , il est possible connaissant x de calculer «facilement»
f (x) ; mais connaissant un élément de l’ensemble image de f , il est «difficile» ou impossible de
trouver son antécédent.
Dans le cadre de la cryptographie, posséder une fonction à sens unique qui joue le rôle de chif-
frement n’a que peu de sens. En effet, il est indispensable de trouver un moyen efficace afin de
pouvoir déchiffrer les messages chiffrés. On parle alors de fonction à sens unique avec trappe
secrète.

Prenons par exemple le cas de la fonction f suivante :

f : x 7−→ x3 (mod 100).

– Connaissant x, trouver y = f (x) est facile, cela nécessite deux multiplications et deux divi-
sions.
 17

– Connaissant y image par f d’un élément x (y = f (x)), retrouver x est difficile.

Tentons de résoudre le problème suivant : trouver x tel que x3 ≡ 11 (mod 100).

On peut pour cela :
– soit faire une recherche exhaustive, c’est-à-dire essayer successivement 1, 2, 3, ..., 99, on
trouve alors :
713 = 357 911 ≡ 11 (mod 100),

– soit utiliser la trappe secrète : y 7−→ y7 (mod 100) qui fournit directement le résultat !

117 = 19 487 171 ≡ 71 (mod 100).

La morale est la suivante : le problème est dur à résoudre, sauf pour ceux qui connaissent la trappe
secrète. (Attention, dans le cas de cet exemple, la fonction f n’est pas bijective.)

4.4. Chiffrement à clé privée

Petit retour en arrière. Les protocoles étudiés dans les chapitres précédents étaient des chif-
frements à clé privée. De façon imagée, tout se passe comme si Bruno pouvaient déposer son
message dans un coffre fort pour Alice, Alice et Bruno étant les seuls à posséder la clé du coffre.

BRUNO

ALICE

En effet, jusqu’ici, les deux interlocuteurs se partageaient une même clé qui servait à chiffrer (et
déchiffrer) les messages. Cela pose bien sûr un problème majeur : Alice et Bruno doivent d’abord
se communiquer la clé.

BRUNO ALICE

Message M Clé C Message M

Message crypté X
Chiffrement C Déchiffrement D

4.5. Chiffrement à clé publique

Les fonctions à sens unique à trappe donnent naissance à des protocoles de chiffrement à clé
publique. L’association «clé» et «publique» peut paraître incongrue, mais il signifie que le principe
de chiffrement est accessible à tous mais que le déchiffrement nécessite une clé qu’il faut bien sûr
garder secrète.
 18

BRUNO

ALICE

De façon imagée, si Bruno veut envoyer un message à Alice, il dépose son message dans la boîte
aux lettres d’Alice, seule Alice pourra ouvrir sa boîte et consulter le message. Ici la clé publique
est symbolisée par la boîte aux lettre, tout le monde peut y déposer un message, la clé qui ouvre la
boîte aux lettres est la clé privée d’Alice, que Alice doit conserver à l’abri.
BRUNO ALICE
Clé publique
Message M Clé privée Message M

Message crypté X
Chiffrement C Déchiffrement D

En prenant appui sur l’exemple précédent, si le message initial est 71 et que la fonction f de
chiffrement est connue de tous, le message transmis est 11 et le déchiffrement sera rapide si la
trappe secrète 7 est connue du destinataire.
Les paramètres d’un protocole de chiffrement à clé publique sont donc :
– les fonctions de chiffrement et de déchiffrement : C et D ,
– la clé publique du destinataire qui va permettre de paramétrer la fonction C ,
– la clé privée du destinataire qui va permettre de paramétrer la fonction D .
Dans le cadre de notre exemple Bruno souhaite envoyer un message à Alice, ces éléments sont :
– C : x 7−→ x? (mod 100) et D : x 7−→ x? (mod 100),
– 3 : la clé publique d’Alice qui permet de définir complètement la fonction de chiffrement :

C : x 7−→ x3 (mod 100),

– 7 : la clé privée d’Alice qui permet de définir complètement la fonction de déchiffrement :

D : x 7−→ x7 (mod 100).

Dans la pratique, un chiffrement à clé publique nécessite plus de calculs et est donc assez lent,
plus lent qu’un chiffrement à clé privée. Afin de gagner en rapidité, un protocole hybride peut être
mis en place de la façon suivante :
– à l’aide d’un protocole de chiffrement à clé publique, Alice et Bruno échangent une clé,
– Alice et Bruno utilise cette clé dans un protocole de chiffrement à clé privée.

5. L’arithmétique pour RSA

Pour un entier n, sachant qu’il est le produit de deux nombres premiers, il est difficile de retrouver
les facteurs p et q tels que n = pq. Le principe du chiffrement RSA, chiffrement à clé publique,
repose sur cette difficulté.
Dans cette partie nous mettons en place les outils mathématiques nécessaires pour le calcul des
clés publique et privée ainsi que les procédés de chiffrement et déchiffrement RSA.
 19

5.1. Le petit théorème de Fermat amélioré

Nous connaissons le petit théorème de Fermat

Théorème 1. Petit théorème de Fermat

Si p est un nombre premier et a ∈ Z alors

a p ≡ a (mod p)

et sa variante :

Corollaire 1

Si p ne divise pas a alors

a p−1 ≡ 1 (mod p)

Nous allons voir une version améliorée de ce théorème dans le cas qui nous intéresse :

Théorème 2. Petit théorème de Fermat amélioré

Soient p et q deux nombres premiers distincts et soit n = pq. Pour tout a ∈ Z tel que
pgcd(a, n) = 1 alors :

a( p−1)( q−1) ≡ 1 (mod n)

On note ϕ(n) = (p − 1)(q − 1), la fonction d’Euler. L’hypothèse pgcd(a, n) = 1 équivaut ici à ce que
a ne soit divisible ni par p, ni par q. Par exemple pour p = 5, q = 7, n = 35 et ϕ(n) = 4 · 6 = 24. Alors
pour a = 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, ... on a bien a24 ≡ 1 (mod 35).
Démonstration

Notons c = a( p−1)( q−1) . Calculons c modulo p :

c ≡ a( p−1)( q−1) ≡ (a( p−1) ) q−1 ≡ 1 q−1 ≡ 1 (mod p)

où l’on appliquer le petit théorème de Fermat : a p−1 ≡ 1 (mod p), car p ne divise pas a.
Calculons ce même c mais cette fois modulo q :

c ≡ a( p−1)( q−1) ≡ (a( q−1) ) p−1 ≡ 1 p−1 ≡ 1 (mod q)

où l’on appliquer le petit théorème de Fermat : a q−1 ≡ 1 (mod q), car q ne divise pas a.
Conclusion partielle : c ≡ 1 (mod p) et c ≡ 1 (mod q).

Nous allons en déduire que c ≡ 1 (mod pq).

Comme c ≡ 1 (mod p) alors il existe α ∈ Z tel que c = 1 + α p ; comme c ≡ 1 (mod q) alors il existe β ∈ Z
tel que c = 1 + β q. Donc c − 1 = α p = β q. De l’égalité α p = β q, on tire que p|β q.
Comme p et q sont premiers entre eux (car ce sont des nombres premiers distincts) alors par le lemme
de Gauss on en déduit que p|β. Il existe donc β0 ∈ Z tel que β = β0 p.
Ainsi c = 1 + β q = 1 + β0 pq. Ce qui fait que c ≡ 1 (mod pq), c’est exactement dire a( p−1)( q−1) ≡ 1 (mod n).
 20

5.2. L’algorithme d’Euclide étendu

Nous avons déjà étudié l’algorithme d’Euclide qui repose sur le principe que pgcd(a, b) = pgcd(b, a
(mod b)).
Voici sa mise en œuvre informatique.
Algorithme . [Link] (1)

def euclide(a,b):
while b !=0 :
a , b = b , a % b
return a

On profite que Python assure les affectations simultanées, ce qui pour nous correspond aux suites
(
a i+1 = b i
b i+1 ≡ a i (mod b i )

initialisée par a 0 = a, b 0 = b.
Nous avons vu aussi comment « remonter » l’algorithme d’Euclide à la main pour obtenir les
coefficients de Bézout u, v tels que au + bv = pgcd(a, b). Cependant il nous faut une méthode plus
automatique pour obtenir ces coefficients, c’est l’algorithme d’Euclide étendu.
On définit deux suites (x i ), (yi ) qui vont aboutir aux coefficients de Bézout.
L’initialisation est :
x0 = 1 x1 = 0 y0 = 0 y1 = 1

et la formule de récurrence pour i Ê 1 :

x i+1 = x i−1 − q i x i yi+1 = yi−1 − q i yi

où q i est le quotient de la division euclidienne de a i par b i .

Algorithme . [Link] (2)

def euclide_etendu(a,b):
x = 1 ; xx = 0
y = 0 ; yy = 1
while b != 0 :
q = a // b
a , b = b , a % b
xx , x = x - q*xx , xx
yy , y = y - q*yy , yy
return (a,x,y)

Cet algorithme renvoie d’abord le pgcd, puis les coefficients u, v tels que au + bv = pgcd(a, b).

5.3. Inverse modulo n

Soit a ∈ Z, on dit que x ∈ Z est un inverse de a modulo n si ax ≡ 1 (mod n).
Trouver un inverse de a modulo n est donc un cas particulier de l’équation ax ≡ b (mod n).
 21

Proposition 1

– a admet un inverse modulo n si et seulement si a et n sont premiers entre eux.

– Si au + nv = 1 alors u est un inverse de a modulo n.

En d’autres termes, trouver un inverse de a modulo n revient à calculer les coefficients de Bézout
associés à la paire (a, n).
Démonstration

La preuve est essentiellement une reformulation du théorème de Bézout :

pgcd(a, n) = 1 ⇐⇒ ∃ u, v ∈ Z au + nv = 1
⇐⇒ ∃u ∈ Z au ≡ 1 (mod n)

Voici le code :
Algorithme . [Link] (3)

def inverse(a,n):
c,u,v = euclide_etendu(a,n) # pgcd et coeff. de Bézout
if c != 1 : # Si pgcd différent de 1 renvoie 0
return 0
else :
return u % n # Renvoie l'inverse

5.4. L’exponentiation rapide

Nous aurons besoin de calculer rapidement des puissances modulo n. Pour cela il existe une
méthode beaucoup plus efficace que de calculer d’abord a k puis de le réduire modulo n. Il faut
garder à l’esprit que les entiers que l’on va manipuler ont des dizaines voir des centaines de
chiffres.
Voyons la technique sur l’exemple de 511 (mod 14). L’idée est de seulement calculer 5, 52 , 54 , 58 ...
et de réduire modulo n à chaque fois. Pour cela on remarque que 11 = 8 + 2 + 1 donc

511 = 58 × 52 × 51 .

i
Calculons donc les 52 (mod 14) :

5 ≡ 5 (mod 14)
52 ≡ 25 ≡ 11 (mod 14)
54 ≡ 52 × 52 ≡ 11 × 11 ≡ 121 ≡ 9 (mod 14)
58 ≡ 54 × 54 ≡ 9 × 9 ≡ 81 ≡ 11 (mod 14)

à chaque étape est effectuée une multiplication modulaire. Conséquence :

511 ≡ 58 × 52 × 51 ≡ 11 × 11 × 5 ≡ 11 × 55 ≡ 11 × 13 ≡ 143 ≡ 3 (mod 14).

Nous obtenons donc un calcul de 511 (mod 14) en 5 opérations au lieu de 10 si on avait fait
5×5×5···.
 22

Voici une formulation générale de la méthode. On écrit le développement de l’exposant k en base

2 : (k ` , . . . , k 2 , k 1 , k 0 ) avec k i ∈ {0, 1} de sorte que

k i 2i .
X̀
k=
i =0

On obtient alors
P` i i
xk = x i =0 k i 2 (x2 )k i .
Ỳ
=
i =0
Par exemple 11 en base 2 s’écrit (1, 0, 1, 1), donc, comme on l’a vu :
3 2 1 0
511 = (52 )1 × (52 )0 × (52 )1 × (52 )1 .

Voici un autre exemple : calculons 17154 (mod 100). Tout d’abord on décompose l’exposant k = 154
en base 2 : 154 = 128 + 16 + 8 + 2 = 27 + 24 + 23 + 21 , il s’écrit donc en base 2 : (1, 0, 0, 1, 1, 0, 1, 0).
Ensuite on calcule 17, 172 , 174 , 178 , ..., 17128 modulo 100.

17 ≡ 17 (mod 100)
172 ≡ 17 × 17 ≡ 289 ≡ 89 (mod 100)
174 ≡ 172 × 172 ≡ 89 × 89 ≡ 7921 ≡ 21 (mod 100)
178 ≡ 174 × 174 ≡ 21 × 21 ≡ 441 ≡ 41 (mod 100)
1716 ≡ 178 × 178 ≡ 41 × 41 ≡ 1681 ≡ 81 (mod 100)
1732 ≡ 1716 × 1716 ≡ 81 × 81 ≡ 6561 ≡ 61 (mod 100)
1764 ≡ 1732 × 1732 ≡ 61 × 61 ≡ 3721 ≡ 21 (mod 100)
17128 ≡ 1764 × 1764 ≡ 21 × 21 ≡ 441 ≡ 41 (mod 100)

Il ne reste qu’à rassembler :

17154 ≡ 17128 × 1716 × 178 × 172 ≡ 41 × 81 × 41 × 89 ≡ 3321 × 3649 ≡ 21 × 49 ≡ 1029 ≡ 29 (mod 100)

On en déduit un algorithme pour le calcul rapide des puissances.

Algorithme . [Link]

def puissance(x,k,n):
puiss = 1 # Résultat
while (k>0):
if k % 2 != 0 : # Si k est impair (i.e. k_i=1)
puiss = (puiss*x) % n
x = x*x % n # Vaut x, x^2, x^4,...
k = k // 2
return(puiss)

En fait Python sait faire l’exponentiation rapide : pow(x,k,n) pour le calcul de a k modulo n, il
faut donc éviter (x ** k) % n qui n’est pas adapté.

6. Le chiffrement RSA
Voici le but ultime de ce cours : la chiffrement RSA. Il est temps de relire l’introduction du chapitre
« Arithmétique » pour s’apercevoir que nous sommes prêts !
 23

Pour crypter un message on commence par le transformer en un –ou plusieurs–

nombres. Les processus de chiffrement et déchiffrement font appel à plusieurs
notions :
– On choisit deux nombres premiers p et q que l’on garde secrets et on
pose n = p × q. Le principe étant que même connaissant n il est très difficile
de retrouver p et q (qui sont des nombres ayant des centaines de chiffres).
– La clé secrète et la clé publique se calculent à l’aide de l’algorithme
d’Euclide et des coefficients de Bézout.
– Les calculs de cryptage se feront modulo n.
– Le déchiffrement fonctionne grâce à une variante du petit théorème de
Fermat.

Dans cette section, c’est Bruno qui veut envoyer un message secret à Alice. La processus se décom-
pose ainsi :
1. Alice prépare une clé publique et une clé privée,
2. Bruno utilise la clé publique d’Alice pour crypter son message,
3. Alice reçoit le message crypté et le déchiffre grâce à sa clé privée.

6.1. Calcul de la clé publique et de la clé privée

Choix de deux nombres premiers

Alice effectue, une fois pour toute, les opérations suivantes (en secret) :
– elle choisit deux nombres premiers distincts p et q (dans la pratique ce sont de très grand
nombres, jusqu’à des centaines de chiffres),
– Elle calcule n = p × q,
– Elle calcule ϕ(n) = (p − 1) × (q − 1).

Exemple 1.
– p = 5 et q = 17
– n = p × q = 85
– ϕ(n) = (p − 1) × (q − 1) = 64
Vous noterez que le calcul de ϕ(n) n’est possible que si la décomposition de n sous la forme p × q
est connue. D’où le caractère secret de ϕ(n) même si n est connu de tous.

Exemple 2.
– p = 101 et q = 103
– n = p × q = 10 403
– ϕ(n) = (p − 1) × (q − 1) = 10 200

Choix d’un exposant et calcul de son inverse

Alice continue :
– elle choisit un exposant e tel que pgcd(e, ϕ(n)) = 1,
– elle calcule l’inverse d de e module ϕ(n) : d × e ≡ 1 (mod ϕ(n)). Ce calcul se fait par l’algo-
rithme d’Euclide étendu.

Exemple 1.
– Alice choisit par exemple e = 5 et on a bien pgcd(e, ϕ(n)) = pgcd(5, 64) = 1,
 24

– Alice applique l’algorithme d’Euclide étendu pour calculer les coefficients de Bézout corres-
pondant à pgcd(e, ϕ(n)) = 1. Elle trouve 5 × 13 + 64 × (−1) = 1. Donc 5 × 13 ≡ 1 (mod 64) et
l’inverse de e modulo ϕ(n) est d = 13.

Exemple 2.
– Alice choisit par exemple e = 7 et on a bien pgcd(e, ϕ(n)) = pgcd(7, 10 200) = 1,
– L’algorithme d’Euclide étendu pour pgcd(e, ϕ(n)) = 1 donne 7 × (−1457) + 10 200 × 1 = 1. Mais
−1457 ≡ 8743 (mod ϕ(n)), donc pour d = 8743 on a d × e ≡ 1 (mod ϕ(n)).

Clé publique

La clé publique d’Alice est constituée des deux nombres :

n et e

Et comme son nom l’indique Alice communique sa clé publique au monde entier.

Exemple 1. n = 85 et e = 5

Exemple 2. n = 10 403 et e = 7

Clé privée

Alice garde pour elle sa clé privée :

Alice détruit en secret p, q et ϕ(n) qui ne sont plus utiles. Elle conserve secrètement sa clé privée.

Exemple 1. d = 13

Exemple 2. d = 8743

6.2. Chiffrement du message

Bruno veut envoyer un message secret à Alice. Il se débrouille pour que son message soit un entier
(quitte à découper son texte en bloc et à transformer chaque bloc en un entier).

Message

Le message est un entier m, tel que 0 É m < n.

Exemple 1. Bruno veut envoyer le message m = 10.

Exemple 2. Bruno veut envoyer le message m = 1234.

 25

Message chiffré

Bruno récupère la clé publique d’Alice : n et e avec laquelle il calcule, à l’aide de l’algorithme
d’exponentiation rapide, le message chiffré :

x ≡ m e (mod n)

Il transmet ce message x à Alice

Exemple 1. m = 10, n = 85 et e = 5 donc

x ≡ me (mod n) ≡ 105 (mod 85)

On peut ici faire les calculs à la main :

102 ≡ 100 ≡ 15 (mod 85)

104 ≡ (102 )2 ≡ 152 ≡ 225 ≡ 55 (mod 85)
x ≡ 105 ≡ 104 × 10 ≡ 55 × 10 ≡ 550 ≡ 40 (mod 85)

Le message chiffré est donc x = 40.

Exemple 2. m = 1234, n = 10 403 et e = 7 donc

x ≡ me (mod n) ≡ 12347 (mod 10 403)

On utilise l’ordinateur pour obtenir que x = 10 378.

6.3. Déchiffrement du message

Alice reçoit le message x chiffré par Bruno, elle le décrypte à l’aide de sa clé privée d, par l’opéra-
tion :

m ≡ x d (mod n)

qui utilise également l’algorithme d’exponentiation rapide.

Nous allons prouver dans le lemme 1, que par cette opération Alice retrouve bien le message
original m de Bruno.

Exemple 1. c = 40, d = 13, n = 85 donc

x d ≡ (40)13 (mod 85).

Calculons à la main 4013 ≡ (mod 85) on note que 13 = 8 + 4 + 1, donc 4013 = 408 × 404 × 40.

402 ≡ 1600 ≡ 70 (mod 85)

404 ≡ (402 )2 ≡ 702 ≡ 4900 ≡ 55 (mod 85)
408 ≡ (404 )2 ≡ 552 ≡ 3025 ≡ 50 (mod 85)
Donc
x d ≡ 4013 ≡ 408 × 404 × 40 ≡ 50 × 55 × 40 ≡ 10 (mod 85)

qui est bien le message m de Bruno.

Exemple 2. c = 10 378, d = 8743, n = 10 403. On calcule par ordinateur x d ≡ (10 378)8743

(mod 10 403) qui vaut exactement le message original de Bruno m = 1234.
 26

n, e d

? x ≡ m e (mod n) ?
m - C - D - m ≡ x d (mod n)

Bruno Alice

6.4. Schéma

Clés d’Alice :
– publique : n, e
– privée : d

6.5. Lemme de déchiffrement

Le principe de déchiffrement repose sur le petit théorème de Fermat amélioré.

Lemme 1

Soit d l’inverse de e modulo ϕ(n).

Si x ≡ m e (mod n) alors m ≡ x d (mod n).

Ce lemme prouve bien que le message original m de Bruno, chiffré par clé publique d’Alice (e, n)
en le message x, peut-être retrouvé par Alice à l’aide de sa clé secrète d.
Démonstration

– Que d soit l’inverse de e modulo ϕ( n) signifie d · e ≡ 1 (mod ϕ( n)). Autrement dit, il existe k ∈ Z
tel que d · e = 1 + k · ϕ( n).
– On rappelle que par le petit théorème de Fermat généralisé : lorsque m et n sont premiers entre
eux
mϕ(n) ≡ m( p−1)( q−1) ≡ 1 (mod n)

– Premier cas pgcd( m, n) = 1.

Notons c ≡ m e (mod n) et calculons x d :

x d ≡ ( m e )d ≡ m e·d ≡ m1+k·ϕ(n) ≡ m · m k·ϕ(n) ≡ m · ( mϕ(n) )k ≡ m · (1)k ≡ m (mod n)

– Deuxième cas pgcd( m, n) 6= 1.

Comme n est le produit des deux nombres premiers p et q et que m est strictement plus petit que
n alors si m et n ne sont pas premiers entre eux cela implique que p divise m ou bien q divise
m (mais pas les deux en même temps). Faisons l’hypothèse pgcd( m, n) = p et pgcd( m, q) = 1, le
cas pgcd( m, n) = q et pgcd( m, p) = 1 se traiterait de la même manière.
Étudions ( m e )d à la fois modulo p et modulo q à l’image de ce que nous avons fait dans la preuve
du théorème de Fermat amélioré.
– modulo p : m ≡ 0 (mod p) et ( m e )d ≡ 0 (mod p) donc ( m e )d ≡ m (mod p),
– modulo q : ( m e )d ≡ m ×( mϕ(n) )k ≡ m ×( m q−1 )( p−1)k ≡ m (mod q).
Comme p et q sont deux nombres premiers distincts, ils sont premiers entre eux et on peut écrire
comme dans la preuve du petit théorème de Fermat amélioré que

( m e )d ≡ m (mod n)
 27

6.6. Algorithmes
La mise en œuvre est maintenant très simple. Alice choisit deux nombres premiers p et q et un
exposant e.
Voici le calcul de la clé secrète :
Algorithme . [Link] (1)

def cle_privee(p,q,e) :
n = p * q
phi = (p-1)*(q-1)
c,d,dd = euclide_etendu(e,phi) # Pgcd et coeff de Bézout
return(d % phi) # Bon représentant

Le chiffrement d’un message m est possible par tout le monde, connaissant la clé publique (n, e).
Algorithme . [Link] (2)

def codage_rsa(m,n,e):
return pow(m,e,n)

Seule Alice peut déchiffrer le message crypté x, à l’aide de sa clé privée d.

Algorithme . [Link] (3)

def decodage_rsa(x,n,d):
return pow(x,d,n)

Pour continuer...
Bibliographie commentée :
1. Histoire des codes secrets de Simon Singh, Le livre de Poche.
Les codes secrets racontés comme un roman policier. Passionnant. Idéal pour les plus litté-
raires.
2. Comprendre les codes secrets de Pierre Vigoureux, édition Ellipses.
Un petit livre très clair et très bien écrit, qui présente un panorama complet de la cryptogra-
phie sans rentrer dans les détails mathématiques. Idéal pour les esprits logiques.
3. Codage et cryptographie de Joan Gómez, édition Le Monde – Images des mathématiques.
Un autre petit livre très clair et très bien, un peu de maths, des explications claires et des
encarts historiques intéressants.
4. Introduction à la cryptographie de Johannes Buchmann, édition Dunod.
Un livre d’un niveau avancé (troisième année de licence) pour comprendre les méthodes
mathématiques de la cryptographie moderne. Idéal pour unifier les points de vue des mathé-
matiques avec l’informatique.
5. Algèbre - Première année de Liret et Martinais, édition Dunod.
Livre qui recouvre tout le programme d’algèbre de la première année, très bien adapté aux
étudiants des l’université. Pas de cryptographie.
28

Auteurs

Arnaud Bodin
François Recher