Chapitre 2.

Cryptographie classique ou conventionnelle

Le but de ce chapitre est de revisiter quelques crypto-systèmes historiques. C’est d’abord

l’occasion de voir comment les idées de la cryptographie conventionnelle d’avant DES, AES
ou RSA ont évoluées. Il ne s’agit pas de faire de l’ « histoire » pour l’histoire, mais
simplement de présenter sur des exemples simples, certaines idées reprises dans certains
crypto-systèmes modernes. C’est le cas des notions de chiffrement par blocs, de crypto-
système produit ou de principe de confusion-diffusion. Ces idées présentes dans certains
systèmes de chiffrement classiques ont été reprises dans les systèmes symétriques et
asymétriques modernes.

1. Chiffrement par décalage (ou de César).

C’est l’un des modes de chiffrement les plus anciens que nous avons tous utilisés
(consciemment ou intuitivement) dans notre enfance. Jules César l’aurait utilisé pour ses
transmissions avec la clé k  3 et la littérature historique de cryptologie l’appelle parfois
chiffrement de César. Ici   C  K  Z 26 , i.e., n  26 si on prend l’alphabet latin pour
crypter du texte; pour crypter du texte en arabe nous prendrions Z 28 ; pour crypter des
images, on prendra Z 256 ( position dans l’image, mais aussi le niveau de gris pour une image
noir et blanc (voir figures 1 et 2 et exercice 2) ; pour une image couleur, il faudra préciser etc.

Fonction de chiffrement : y  f k ( x)  x  k mod n , x, y  Z n ( x et k connus).

Fonction de déchiffrement : x  f k1 ( y)  y  k mod n , x, y  Z n ( y et k connus).

Sécurité. Notons que cet algorithme de chiffrement est peu sûr car il n’y a que n clés
possibles seulement. Pour l’alphabet choisi en guise d’exemple dans ce document ( anglais ou
français, n  26 ), mais cet algorithme peut-être cassé par une simple recherche exhaustive. Il
en est de même pour les autres alphabets traditionnels (latin, arabe, tamazight, image ou son),
y compris dans leurs versions binaires. Dans notre cas, il faut en moyenne 26/2=13 essais
pour retrouver un caractère, et donc ( en moyenne pour un texte de longueur m.

Exemple 1: Soit à chiffrer le texte clair x  CRYPTOLOGIE avec le chiffrement de César.

A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

On commence par numériser (ou coder en numérique le message dans l’alphabet Z 26 ),

x  2 17 24 15 19 14 11 14 6 8 4 . En pratique, il n’y a pas besoin d’écrire les blancs, du
moins pour un texte littéraire. Ensuite, on chiffre avec la clé k  3.

Pour le chiffrement, on ajoute le nombre 3 à chaque caractère numérisé. Ceci donne

y  5 20 27 18 22 17 14 9 11 7. On réduit ensuite le résultat modulo 26:
y  5 20 1 18 22 17 14 9 11 7. Enfin, on convertit à nouveau en code alphabétique pour
obtenir le texte chiffré : y=FUBSWRORJLH.
12
Le déchiffrement consiste à dérouler le processus inverse. On numérise au préalable dans
l’alphabet Z 26 , on retranche 3 à chaque lettre, puis on convertit en alphabétique.

L’exercice 2 indique comment chiffrer une image avec ce mode de chiffrement et la clé
k  111 . Les figures 1 et 2 montrent l’image originale (numérisée dans une matrice) et
l’image cryptée en utilisant le décalage dans Z 256  0,1,2,...,255.

Figure 1.Image originale. Figure 2. Image cryptée avec César ( k  111).

On remarque ici que ce mode de cryptage laisse reconnaître la « forme », ce qui toutefois
montre que la « communication » a été transmise. Le code Mathematica est donné en solution
des exercices (annexe Mathematica).

2. Chiffrement par substitution (ou permutation).

2.1. Chiffrement/déchiffrement. Ce mode de chiffrement a été proposé dans le but

d’augmenter la confusion du texte clair. On prendra ici M  C  Z 26 , K  l’ensemble des
permutations des nombres 0,1,2,3,....,25. Pour   K , le chiffrement est
f ( x)   x , x  M et le déchiffrement, f 1
( y)   1  y , y  C.

2.2. Sécurité. Ce système est plus sûr que le précédent car le nombre de clés possibles
est 26! =403 291 461 126 605 635 584 000 000 , soit environ 4  10 26. La recherche
exhaustive (essayer toutes les clés possibles) est donc plus « difficile », mais facile à casser
avec d’autres méthodes. Le crypto système à décalage, peut être vu en fait comme un cas
particulier.

Exemple 2: Soit la permutation « aléatoire » ci-dessous. On a donc  ( A)  P,  B  D...

13
 x 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

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

Le message CRYPTOLOGIE chiffré avec cette clé est donc WMSLCSFSAEZ. Notons qu’ici,
il est n’est pas nécessaire de numériser le message clair.

Exemple 3. Voici l’image cryptée du chat avec une permutation aléatoire générée par le code
Mathematica donné en exercice 5.

80 80

60 60

40 40

20 20

0 0
0 20 40 60 80 100 0 20 40 60 80 100

Figure 3. Image cryptée avec maillage. Figure 4. Cryptage sans maillage.

On note bien que la confusion est plus accentuée qu’avec le décalage.

3. Chiffrement linéaire ou affine.

3.1.Chiffrement/Déchiffrement.

De nouveau, supposons que M  C  Z n . La clé ici est le couple k  (a, b)  Z n  Z n .

Cependant, K  Z n  Z n (il n’y a pas forcément égalité).

La fonction de chiffrement est y  f k x   ax  b mod n , a, b  Z n .

et celle de déchiffrement : f k1  y   ax  b1  a 1 y  a 1b mod n .

Les opérations d’inversion et d’addition et de la multiplication dans Z n s’effectuent de la

même manière que dans IR. L’inverse (l’opposé) existe toujours pour l’addition (lorsque y
parcourt Z n , il en est de même de y  b  Z n ). Par contre, l’inverse n’existe pas toujours pour
la multiplication. Pour que le chiffrement soit valide, il faut donc que l’inverse a 1 existe,
sinon la fonction de chiffrement ne serait pas injective et le chiffrement d’un message donné
pourrait ne pas être unique ou ne serait pas possible. Nous avons un critère simple pour
vérifier qu’un chiffrement est valide. Rappelons que l’équation ax  b mod n admet une
solution unique x  Z n , b  Z n , si et seulement si a et n sont premiers i.e. PGCD(a, n)  1 .
Par conséquent, l’espace des clés ici est 
K  k  (a, b)  Z n  Z n : a 1 inversible 
 k  (a, b)  Z n  Z n : PGCD(a, n)  1.

14
Exemple 4: Considérons l’alphabet M  C  Z 26 et le chiffrement f k x   ax  b mod 26 .
PGCD(a,26)  d n’est pas toujours égal à 1. Par conséquent l’espace des clés est

K  1,3,5,7,9,11,15,17,19,21,23 Z 26 .

Si maintenant la fonction de chiffrement est la suivante f k ( x)  4 x  7 mod 26 , alors ce n’est

pas un mode de chiffrement valide car PGCD(4,26)  2  1. L’équation 4 x  7  0 admet
deux solutions et le chiffrement n’est pas unique car x et x  13 seront toujours chiffrés de la
même manière. Ce n’est donc pas un cryptage valide. Par contre, le chiffrement
f ( x)  7 x  3 mod 26 est valide. Pour calculer l’inverse, on peut utiliser la table de
multiplication de Z 26 qui est bien connue :

a 1 3 5 7 9 11 15 17 19 21 23 25
a 1 1 9 21 15 3 19 7 23 11 5 17 24

L’ensemble des résidus modulo n qui sont premiers avec n (et qui sont donc inversibles) est
noté Z n* . C’est un groupe commutatif pour la multiplication, et chacun de ses éléments est
inversible. Ainsi, Z 26 *
 1,9,21,15,3,19,7,23,11,5,17,24. En pratique, l’inversion peut être
réalisée à l’aide de l’algorithme d’Euclide facile à implémenter et que l’on trouvera dans la
plupart des outils logiciels spécialisés. Nous le rappelons un peu plus loin.

3.2.Sécurité.

Rappelons que la sécurité de ce chiffrement est comprise comme étant le nombre de clés
possibles. Ici, il n’est pas difficile de voir que le chiffrement linéaire possède 12  26  312
clés possibles, ce qui en fait un chiffrement peu sûr pour la pratique.

Indiquons maintenant une méthode alternative pour évaluer le nombre de clés possibles sans
passer par le dénombrement exhaustif. Si on connaît la décomposition en facteurs premiers du
n
modulus n   piei , alors on peut définir la fonction indicatrice d’Euler
i 1
n
 (n)   ( pie  pie 1 ) qui donne le nombre d’entiers de Z n qui sont premiers avec n. Ainsi,
i i

i 1
le nombre de clés possibles est égal à n   (n) . Par exemple, n  26  2 13 et
 
 (26)  2  2 0 (13  130 ), n   (n)  26 12  312 qui est le nombre de clés possibles pour le
chiffrement linéaire évalué plus haut par dénombrement. Ce procédé peut donc être
facilement automatisé. Cette fonction sera utile par la suite pour le chiffrement RSA.

Notons enfin quelques propriétés de la fonction d’Euler :

 Si p est premier, alors Z p est un corps et  ( p)  p  1.

 Si n  p  q où p et q sont des entiers premiers distincts, alors

 (n)   ( p)   (q)  ( p  1)(q 1)  n  ( p  q)  1 .

15
  La figure ci-dessous représente les valeurs de la fonction d’Euler pour les 100
premiers entiers
naturels :

80

60

40

20

20 40 60 80 100

Figure 5. Distribution des valeurs de la fonction d’Euler.

3.3.Algorithme d’Euclide et calcul de PGCD.

Nous avons vu que a  Z n est inversible si et seulement si PGCD(a, n)  1 , c’est-à-dire si

a et n sont premiers entre eux (Cela est dû au fait que Z n muni de l’addition et la
multiplication modulaire est un anneau). Pour calculer le PGCD , on pourrait factoriser en
nombres premiers, mais la méthode n’est pas toujours efficace (algorithmiquement parlant),
surtout lorsqu’on a à faire avec des grands entiers comme c’est le cas pour les systèmes
asymétriques du chapitre 5. L’algorithme d’Euclide fournit une procédure concrète et efficace
pour calculer ce PGCD .

Soit à calculer le PGCD(a, n) ( n  a) . On peut écrire successivement

n  a  q 0  r0
a  r0  q1  r1 (car tout GCD de a et n est aussi diviseur de r0 )
r0  r1  q 2  r2
…………………..
rm2  rm1  qm  rm
rm1  rm  q m1  rm1
ri  ri 1 
L’algorithme se termine lorsque le dernier reste est nul i.e., rm1  0. Le PGCD est alors le
dernier reste non nul.

Exemple 5: Trouver le PGCD(8470,3458)  14 par l’algorithme d’Euclide.

8470  2  3458  1554
3458  2 1554  350
1554  4  350  154
350  2 154  42
154  3  42  28
42  1 28  14

16
La complexité de cet algorithme est de l’ordre de O(log n) 2 opérations binaires. En fait, cet
algorithme détermine si un élément est inversible, mais ne donne pas une méthode pratique de
calcul de cet inverse. Ceci peut être fait en se basant sur ce résultat d’arithmétique élémentaire
(qui reste en fait vrai dans des structures arithmétiques plus générales).

L’arithmétique nous fournit divers critères de primalité dont le plus simple pour notre
objectif est le suivant:

(i) a et n sont premiers ,

(ii) PGCD(a, n)  1 ,
(iii) u, v tels que au  nv  d  1 (identité de Bezout),

L’assertion (iii) reste cependant vraie, même si d  1 . Les assertions (i)-(iii) sont intéressantes
car elles fournissent un algorithme qui se termine en donnant en plus du PGCD , deux entiers
u et v tels que au  nv  d . Ceci conduit à l’algorithme suivant :

3.4. Algorithme d’Euclide Etendu calcul d’inverse dans Z n .

 Poser d  a, u  1, v  0 . Ecrire (d , u, v)  (d ,1,0).

Poser u 2  1, u1  0, v 2  0, v1  1 .
 Tant que n  0 , faire
1. q  a / n , r  a  qn, u  u 2  qu1 , v  v 2  qv1 .
2. a  n, n  r, u 2  u1 , u1  u, v 2  v1 , v1  v.
 Poser d  a, u  u 2 , v  v 2 . Ecrire d , u, v  .
 Si d  1 , l’inverse a 1 mod n n’existe pas .
 Si d  1 , l’inverse existe, et on peut le déterminer à l’aide de l’identité de Bezout
au  nv  1 i.e., a 1  u (la valeur de u obtenue à la dernière itération).

Exemple 6. Voici les étapes d’exécution de l’algorithme 3.4. sur l’exemple précédent :

q r u v a n u2 u1 v2 v1 ( d , u , v)
- - - - 8470 3458 1 0 0 1
2 1554 1 -2 3458 1554 0 1 1 -2 (3458,0,1)
2 350 -2 5 1554 350 1 -2 -2 5 (1554,1,-2)
4 154 9 -22 350 154 -2 -7 5 -22 (350,-2,5)
2 42 -20 49 154 42 9 -20 -22 49 (154,9,-22)
3 28 69 -169 42 28 -20 69 49 -169 (42,-20,69)
1 14 -89 218 28 14 69 -89 -169 218 (28,69,-169)
2 0 247 -605 14 0 -89 247 218 -605 (14,-89,218)

L’algorithme donne à la dernière étape (d , u, v)  (14,89,218) . Ici, l’inverse de

3458 mod 8470 n’existe pas. Par contre pour 35 1 mod 83  19 mod 83,

q r u v a n u2 u1 v2 v1 ( d , u , v)
- - - - 35 83 1 0 0 1
1 35 1 -1 83 35 0 1 1 -1 (83,0,-1)

17
 2 13 -2 3 35 13 1 -2 -1 3 (35,1,-1)
2 9 5 -7 13 9 -2 5 3 -7 (13,-2, 3)
1 4 -7 10 9 4 5 -7 -7 10 (9,5,-7)
2 1 19 -27 4 1 -7 19 10 -8 (4,-7,10)
4 0 0 118 1 0 19 0 -8 118 (1,19,27)

On a bien alors 35 19 mod 83  1 ou 35 1 mod 83  19 mod 83 . Ce que l’on peut vérifier à
l’aide des programmes proposés en exercices.

Exemple 7: Soit à chiffrer le texte CRYPTOLOGIE à l’aide du chiffrement linéaire. La

conversion en numérique donne {2,17,24,15,19,14,11,14,6,8,4}. On a
f 9,5 ( x)  9 x  5 mod 26 : la clé est donc a, n  9,5 . En utilisant la numérisation du mot à
chiffrer, on calcule successivement f (2)  9  2  5 mod 26  23 ,
f (17)  9 17  5 mod 26  2 , f (15)  9 15  5 mod 26  10 . Le texte chiffré est donc
XCNKUBABHZP . Pour déchiffrer, on utilise la fonction inverse

f (9,15) ( y)  9 1 y  9 1  5  3 y  3  5  3 y  15 mod 26.

Pour vérifier, prenons la première lettre codée X qui correspond en alphabet numérique à 23,
f 1 (23)  3  23  15  54 mod 26  2 qui correspond bien à la première lettre C du texte clair.
Le programme EuclideE[9,26] de l’exercice donne bien{1,3,-1}.

4.Chiffrement poly alphabétique de Vigenère .

4.1.Chiffrement/Déchiffrement.

Les chiffrements des exemples précédents étaient mono alphabétiques, au sens où chaque
caractère clair était transformé en un seul caractère codé. Dans les systèmes poly
alphabétiques, un caractère peut être codé dans le texte de différentes manières. Chaque clé
est décrite par une chaîne de caractère de longueur m appelée mot-clé. Le chiffrement poly
alphabétique traite ainsi m caractères à la fois : chaque bloc de texte clair est équivalent à m
caractères alphabétiques.

La technique la plus simple consiste à convertir les caractères de texte clairs en résidus
modulo 26, puis les grouper en blocs de m caractères. On ajoute le mot-clé modulo 26 à
chaque bloc, ce qui revient à effectuer une addition modulo 26. Le déchiffrement consiste
alors à effectuer l’opération inverse (soustraction modulo 26) avec le mot-clé .

Exemple 8: Soit à chiffrer le texte clair « il pleuvra demain » avec le mot-clé USTHB, et
donc m  5 . Le mot-clé converti en numérique donne une clé k  (20,18,19,7,1) . Le résultat
des opérations est reporté dans le tableau suivant :

I L P L E U V R A D E M A I N
8 11 15 11 4 20 21 17 0 3 4 12 0 8 13
20 18 19 7 1 20 18 19 7 1 20 18 19 7 1
2 3 8 18 5 14 13 10 7 4 24 4 19 15 14
C D I S K O N K H E Y R T P O

18
La dernière ligne ajoute le mot-clé (modulo 26) au bloc correspondant de texte codé en
alphabétique. Le texte chiffré est donc: CDISFONKHEYETPO.

Pour déchiffrer, on partage le texte codé en alphabet numérique en blocs de 5 lettres, puis on
soustrait le mot-clé bloc par bloc.

4.2.Sécurité. On remarque qu’avec cette procédure, la lettre A a été codée une fois par H et
une fois par T. On espérait augmenter ainsi la confusion du texte clair. Nous avons toutefois
défini la sécurité comme la taille de l’espace des clés. Le nombre de mots-clés possibles est en
général n m dans Z n ( 26 m dans l’alphabet latin). L’attaque brute par recherche exhaustive
demande beaucoup plus de temps que pour les chiffrements précédents, même pour m petit.
Le tableau suivant donne un ordre de grandeur

m Taille de l’espace des clés

5 11 881 376
10 1.41167  1014
100 3.14293  10141

5. Chiffrement matriciel : poly alphabétique.

5.1. Chiffrement/Déchiffrement. On l’appelle encore chiffrement de Hill. C’est encore un

chiffrement linéaire de type poly alphabétique reposant sur l’idée suivante. Chaque bloc de
texte clair à m caractères est transformé m caractères du texte chiffré par des combinaisons
linéaires. La motivation était d’exploiter les avancées scientifiques dans le domaine des
systèmes linéaires. C’est d’autre part le début du chiffrement par blocs de données.

On prend ici M  C  Z 26  , et on se donne une matrice-clé K  k ij

m
mm à éléments
kij  Z 26 .

Chiffrement : y  xK Déchiffrement : x  yK 1

Exemple 10. Fixons la taille des blocs à m  2 . Pour un bloc de texte clair x  ( x1 , x2 ) on
obtient un bloc de texte chiffré y  ( y1 , y 2 ) où y 1 et y 2 sont calculés à l’aide de
combinaisons linéaires de x1 et x 2 , par exemple y1  9 x1  5x2 , y 2  11x1  8x 2 , ou
sous forme matricielle
 9 11 2 7
( y1 , y 2 )  ( x1 , x2 )  . Dans Z 26 , on a K 1    (cf. exercice 13). Pour le vérifier,
5 8  15 25 
effectuons

 9 11  2 7   9  2  11  15 9  7  11  25   1 0 
K  K 1           
 5 8  15 25   5  2  8  15 5  7  8  25   0 1 

qui est bien la matrice unité (toutes les opérations sont réduites modulo 26).

19
Chiffrons maintenant le texte CRYPTOLOGIE avec ce chiffrement. Il faut au préalable
convertir le texte en blocs de 2 :

(C, R)  (2,17) , (Y , P)  (24,15) , (T , O)  (19,14) , ( L, O)  (11,14) , (G, I )  (6,8) ,

( E, F )  (4,5)

Lorsque le nombre de caractères n’est pas divisible par m , on peut par exemple compléter le
texte de manière arbitraire. On a
 9 11
(2,17)   (103,158)  (25,2) modulo 26 , donc CR est crypté par ZC
5 8 
 9 11
(24,15)   (291,384)  (5,20) modulo 26 , donc YP est crypté par FU
5 8 
etc. Finalement le texte crypté au moyen de ce chiffrement est ZCFUHJNZQAJG.

Le déchiffrement est l’opération inverse. Pour le premier bloc ZC, il faut calculer la matrice
2 7
inverse K 1    et enfin déchiffrer comme suit
 15 25 
2 7
(25,2)   (2,17)
15 25 

5.2. Sécurité. L’espace des clés est maintenant l’ensemble des matrices de taille m , et on
peut s’attendre à ce que ce chiffrement soit plus facile à « casser ».

5.3. Fonctionnement pratique. Le déchiffrement n’est possible avec cette méthode que si
la matrice-clé K est inversible. Il est connu que l’inversion d’une matrice à coefficients réels
est possible si le déterminant est non nul. Ce résultat n’est pas suffisant dans Z n . En fait, une
matrice K est inversible modulo n  26 si et seulement si PGCD(n, det K )  1. On vérifiera
sans peine que c’était le cas pour les exemples ci-dessus.

6. Chiffrement par permutation (ou transposition).

6.1. Chiffrement/Déchiffrement. Dans le mode de chiffrement par substitution,

tout caractère du texte clair était remplacé par un autre dans le texte chiffré. La
différence ici est de conserver les mêmes caractères en les réordonnant. Pour ce
chiffrement, M  C  Z 26  , alors que l’espace des clés K est l’espace des
m

permutations de l’ensemble 1,2,..., m. Pour toute clé   K (une permutation de K ),

on définit les fonctions de

Chiffrement : f  x   x 1, x 2  ,..., x m  

Déchiffrement : 
f 1 x   x 1 1, x 1 2  ,..., x 1 m  
Exemple 11: Chiffrer notre texte habituel CRYPTOLOGIE à l’aide de la permutation clé
d’ordre m  6 .

20
 1 2 3 4 5 6
    ,
3 5 1 6 4 2
1 2 3 4 5 6
La permutation inverse est  1   
3 6 1 5 2 4

On commence par découper le texte clair en blocs de 6 lettres : CRYPTO LOGIEF

Le symbole F a été ajouté arbitrairement, simplement pour la cohérence. Chaque bloc est
ensuite réordonné selon la permutation  . Notons que ce mode de chiffrement ne
nécessite pas de numérisation préalable.

Les deux textes de blocs chiffrés sont YOCTRP GFLEOI

Remarque. Il faut noter que le chiffrement par permutation est un cas particulier du
chiffrement matriciel. A toute permutation  , on associe la matrice clé m m,

1, i    j
K  k ij dont les éléments sont définis par k ij  
mm
 0, i    j

Dans notre exemple, on a

 0 0 1 0 0 0 0 0 1 0 0 0
   
0 0 0 0 0 1 0 0 0 0 0 1
1 0 0 0 0 0 1 0 0 0 0 0
K    et K 1  
 0 0 0 0 1 0 0 0 0 0 1 0
 0 1 0 0 0 0 0 1 0 0 0 0 
  
 0 0 0 1 0 0 0 0 0 1 0 0 
  
1
On note que l’inverse de la matrice K   K  1 .

6.2. Sécurité. Voir chiffrement matriciel.

7. Chiffrement en chaîne.

7.1. Introduction. Dans les systèmes précédents, les éléments de texte étaient
chiffrés de la même
manière avec une seule clé k : y  y1 y 2 ....  f k ( x1 ) f k ( x 2 )... Ici y représente une chaîne de
caractères chiffrés à partir de la chaîne de texte clair x1 x 2 ... Ce n’est rien d’autre que le
chiffrement par blocs.

Partant d’une clé maître k , on crée ensuite une suite de clés z i  g i (k , y1 , y 2 ,..., y i 1 ) à l’aide
d’une certaine fonction. Ainsi, chaque sous-clé est déduite de la clé maître et des caractères
chiffrés précédents. Dans ce chiffrement en chaîne, pour chiffrer le texte clair sous forme de

21
chaîne x  x1 x2 ... , on calcule successivement z1 , y1 , z 2 , y2 ,... et on applique la règle
y  y1 y2 ....  f z1 ( x1 ) f z2 ( x2 )...

Pour le déchiffrement, on calcule successivement z1 , x1 , z 2 , x 2 ,...

7.2. Exemples.

(i) Notons d’abord que le chiffrement par bloc est un cas particulier du chiffrement en
chaîne: z i  k , i  1,2,...
(ii) Un chiffrement en chaîne est périodique de période d si chaque sous-clé
z i  d  z i . Le chiffrement poly alphabétique avec mot-clé de longueur m est un
exemple de chiffrement en chaîne périodique de période m . Dans ce cas, la clé
k  k1 , k 2 ,..., k m  est telle que z i  k , i  1,2,..., m.
(iii) Le chiffrement de Vigenère et son déchiffrement sont dans ce sens équivalents à
ceux du décalage : y  f z ( x)  x  z , x  f z1 ( y)  y  z .
(iv) Les chiffrements en chaînes sont souvent décrits en alphabet binaire i.e.
M  C  Z 2 . Le chiffrement et le déchiffrement sont des additions modulo 2. Si
on se place dans l’algèbre de Boole, et qu’on code 0 par faux et 1 par vrai,
l’addition modulo 2 n’est rien d’autre que le ou-exclusif. Cela facilite la réalisation
des chiffrement et déchiffrement sur microprocesseurs et notamment sur les
systèmes embarqués.
(v) Pour produire la séquence de sous-clés on utilise parfois un registre à décalage
linéaire LSFR (Linear Feedback Shift Register) . Partant d’une clé-maître
k  k1 , k 2 ,..., k m  , on pose z i  k i , i  1,2,..., m et le reste de la suite est généré par
m 1
récurrence 1inéaire de degré m, z i  m   c j z i  j m o d2, où c0 , c1 ,..., c m1  Z 2
j 0

sont des constantes choisies à l’avance. Avec un choix judicieux des constantes (il
y en a en fait 2m : k1 , k 2 ,..., k m , c0 , c1 ,..., c m1 ) et une petite clé maître on peut
obtenir de longues périodes, ce qui permet de chiffrer ainsi des chaînes assez
longues. Il y a d’autres précautions à prendre, par exemple, éviter des valeurs
toutes nulles faute de quoi le texte chiffré coïnciderait avec le texte clair.

Exercices

La plupart des exercices sont simples et il est proposé de les résoudre manuellement afin de
comprendre le fonctionnement des algorithmes avant de les implémenter dans le langage de
votre choix. Ici, certaines solutions sont proposées en Mathematica (cf. Annexe: Ateliers
Mathematica). L’étudiant pourra alors adapter ses propres solutions.

Exercice 1 : Pour commencer considérons le chiffrement par décalage (ou de César avec
k  3 ).
(i) Ecrire les ensembles des textes clairs, codés (chiffrés) a priori dans l’alphabet
Latin. On ne tient compte ni des blancs, ni des ponctuations. Quel serait l’espace
en question si on devait prendre en compte ces spécificités?
(ii) Ecrire les fonctions de chiffrement et de déchiffrement.
(iii) Evaluer la sécurité de ce système de chiffrement i.e. le nombre de clés possibles et
le nombre moyen d’essais nécessaires pour « casser » ce crypto-système.

22
 (iv) Application : Chiffrer le texte suivant MUSIQUE dans l’alphabet Z26 avec la clé
k=3.
(v) Même question avec le texte clair FOOTBALL et la clé k  11.

Exercice 2: Chiffrer l’image chat (figure 1 chapitre 2) à l’aide du chiffrement par décalage
avec la clé k=111.

Exercice 3. Automatiser le chiffrement par décalage dans le langage de votre choix. Puis
utiliser le programme conçu pour déchiffrer les textes précédents et le suivant à l’aide d’une
recherche exhaustive:
WIGVCYHXYNYGJMFYMYNOXCUHNMXYGCFIHNCFMGCMJIOLXAWBCZZLYL
WYGYMMUAY .

Exercice 4: Coder les textes (iv) et (v) exercice 1 avec la permutation aléatoire du §2.Chap.2.
Quelle est la sécurité de ce type de cryptage?

Exercice 5 : Mêmes questions que les exercices précédents avec le texte « image du chat.

Exercice 6: Vérifier que si rm  PGCD(n, a)  PGCD(r0 , r1 ) , alors la suite récurrente

u0  0, u1  1 v0  0, v1  1
ui  ui 2  qi ui 1 , ui  2. vi  vi 2  qi vi 1 , vi  2.
r 
avec qi   i 1  , r0  n, r1  a.
 ri 
possède la propriété suivante r j  ui r0  vi r1, 0  i  m.
De plus, si rm  PGCD(n, a)  PGCD(r0 , r1 )  1 , alors cette procédure fournit
l’inverse a 1 mod n  r11 mod r0  vm mod n .
Ecrire un programme fournissant l’inverse à l’aide de cette procédure.
A .N. Vérifier votre programme en reprenant manuellement l’exemple du chapitre 2 qui
calcule 35 1 mod 83.

Exercice 7: Considérons le chiffrement linéaire (ou affine) avec M  C   26 , n  26,

f k ( x)  ax  b mod 26, x  Z 26
(i) Décrire la fonction de déchiffrement correspondante.
(ii) Quel est l’espace des clés? On indiquera pour cela l’ensemble de validité des clés
possibles. Indication: Etudier les conditions d’existence d’un inverse modulaire
dans l’alphabet Z n (en particulier Z 26 ) par rapport à la multiplication (cf. exercice
10).
(iii) Quelle est la sécurité de ce crypto système? On peut donner comme indicateur le
nombre de clés possibles.
(iv) Donner une autre méthode de calcul du nombre de clés possibles en utilisant la
fonction indicatrice d’Euler.
(v) Chiffrer le texte CRYPTOLOGIE avec la clé k  (7,3) , f ( x)  7 x  3 mod 26 .
(vi) Ecrire un programme pour automatiser ce mode de chiffrement. Utiliser les
résultats précédents pour vérifier que votre programme est correct. Chiffrer alors le
message « Sécurité informatique » dans l’alphabet français avec ponctuation.

23
Exercice 8. Chiffrer le mot ATTAQUE avec le chiffrement linéaire et la clé (2,5) puis avec
la clé (3,4).

Exercice 9: Trouver le nombre de clés possibles pour le chiffrement linéaire de modulo

(i) n  90 ; (ii) un grand modulo 50 !.

Exercice 10. Le but de l’algorithme d’Euclide est de calculer le plus grand commun diviseur
entre deux entiers a et b : d  PGCD(a, b) , mais aussi de vérifier si deux entiers a et b sont
premiers entre eux i.e. PGCD(a, b)  1. Ce type de test est continuellement présent dans de
nombreux protocoles cryptographiques (voir exercice précédent, mais aussi au chapitre 5)
avec le protocole SSL utilisant le chiffrement RSA. Cet exercice propose donc d’implémenter
cet algorithme dans le langage de votre choix.
(i) Evaluer théoriquement la complexité de l’algorithme d’Euclide. Commencer par
exemple à calculer le nombre de divisions nécessaires pour calculer le PGCD de
n et k  n .
(ii) Montrer comment adapter cet algorithme pour calculer l’inverse modulaire
(indication : algorithme d’Euclide Etendu).

Exercice 11. Ecrire un programme qui réalise l’algorithme d’Euclide Etendu. Cet algorithme,
calcule les deux entiers positifs u et v tels que PGCD(a, b)  au  bv (identité de Bezout).
Dans le cas où a et b sont premiers entre eux, au  bv  1 , on obtient en plus l’inverse de tout
entier puisqu’il existe.

Exercice 12: (i) Décrire succinctement le procédé de chiffrement de Vigenère.

(i) Quelle est ici l’innovation par rapport au décalage, affine ou substitution ?
(ii) Quelle est la sécurité de ce système ?
(iii) Application : chiffrer le texte clair CRYPTOLOGIE avec le mot-clé USTHB.
(iv) Même question avec le texte clair thissystemisnotsecure et le mot-clé CIPHER
ou en français, cesystèmenestpassur.

Exercice 13: Le déchiffrement de Hill suppose que la matrice clé est inversible.
(i) Discuter les conditions d’existence d’inverse de matrice dans Z m (et en
particulier Z 26 ).
(ii) Trouver une formule de calcul de l’inverse d’une matrice carré de Z 26 .

Exercice 14: (i) Décrire le système de chiffrement de Hill : Espaces des textes clairs et
chiffrés, espace des clés, algorithmes de chiffrement et de déchiffrement. Quelles sont les
idées qui ont conduit à proposer ce système et quelles sont ses innovations principales ?
11 8 
(i) Etudier le chiffrement avec m  2 et la matrice clé K    . Quel est
 3 7
l’algorithme de déchiffrement ?
(ii) Application : chiffrer le texte OMAR.
Exercice 15: Chiffrer le texte CRYPTOLOGIE avec le chiffrement matriciel.
Exercice 16: Décrire le chiffrement par permutation (ou transposition).
(i) Quelle est la différence avec la substitution ?
(ii) Ecrire les fonctions de chiffrement et de déchiffrement dans l’alphabet Z 26 .

24
 (iii) Application : Chiffrer le texte clair a ALI VA A L’ECOLE avec des blocs
de m  6 .
(iv) Même question avec le texte clair [33]:
shesellsseashellsbytheseashore (elle vend des coquillages sur la plage)
(v) Montrer que ce chiffrement est un cas particulier du chiffrement de Hill dont on
déterminera la matrice clé.

Exercice 17: Donner l’espace des messages clairs, l’espace des messages codés et l’espace
des clés dans le cas du chiffrement par permutation (transposition). Montrer comment chiffrer
et déchiffrer le texte clair ATTAQUE avec la clé

1 2 3 4 5 6
   
3 5 1 6 4 2

Exercice 18: Décrire le principe et le fonctionnement du chiffrement en chaîne. Quelles sont

les différences avec les autres méthodes ? Pourquoi peut-on considérer que le chiffrement par
bloc et le chiffrement de Vigenère sont des cas particuliers du chiffrement en chaîne ? Une
méthode pour produire un chiffrement en chaîne synchrone (i.e. la séquence de clés est
indépendante du texte clair, et ne dépend que de la clé k ; comme dans le générateur pseudo
aléatoires de type congruentiel: k est le germe, la semence, la racine). On part de
k  (k1 , k 2 ,...,km ) et zi  ki , 1  i  m et le reste de la suite est généré de la façon suivante par
récurrence linéaire de degré m, où c0 , c1 ,..., cm1  Z 2 sont des constantes fixées à l’avance. La
clé contient en fait 2m valeurs k1 , k2 ,..., km , c0 , c1 ,..., cm 1 . Il faut éviter les valeurs toutes nulles,
auquel cas le texte clair sera exactement le texte chiffré. Pour un choix judicieux des
constantes et une petite clé on peut avoir une longue période 2m  1 . A.N.
m  4 et zi  4  zi  zi 1 . Quelle est la suite obtenue avec une initialisation 1,0,0,0 ? Vérifier que
toute autre racine donne une séquence obtenue par permutation circulaire de celle-ci (à
l’exclusion de 0,0,0,0 ).

Exercice 19: Considérons le chiffrement asynchrone (autokey cipher) où le texte clair est
utilisé comme clé (sauf pour la clé initiale). M  C  K  Z 26 ; z1  k ; z i  xi 1 (i  2) .
f z ( x)  x  z mod 26 . f z1 ( y)  y  z mod 26
(i) Chiffrer le texte clair : « securite » avec la clé k  5. Quelle est la sécurité de ce
système ?
(ii) « rendez-vous » avec la clé k  8.

25