ISSAT SOUSSE 3 LSI

Département informatique Sécurité informatique

AU : 2021/2022 Dr. WALA ZAABOUB

Chapitre 5 : La cryptographie

Définitions
La cryptologie : est une science des messages secret, elle comporte deux branches : la cryptographie
et la cryptanalyse.
La cryptographie : est l’étude des méthodes de chiffrement.
La cryptanalyse : est l’étude des procédés de décryptage/déchiffrement sans connaître la méthode
cryptographique et/ou ses paramètres.
Le Chiffrement : consiste à transformer une donnée (texte, message, ...) à l'aide d'une clé pour la
rendre incompréhensible afin de la protéger.
Le déchiffrement : est une fonction permettant de retrouver le texte clair à partir du texte chiffré.
Texte chiffré (cryptogramme) : est le résultat de l’application d’un chiffrement à un texte clair.
Clef : Il s’agit du paramètre impliqué et autorisant des opérations de chiffrement et/ou
déchiffrement.
Crypto-système : est l’ensemble des clés possibles (espace de clés), des textes clairs et chiffrés
possibles associés à un algorithme donné.

Il y a deux catégories de chiffrement : chiffrement symétrique et asymétrique.

Le chiffrement symétrique est un chiffrement à clef secrète : Clef de chiffrement = clef de
déchiffrement.
Par contre, le chiffrement asymétrique est un chiffrement à deux clefs (l'une secrète et l'autre
publique): la clef de chiffrement est différente à la clef de déchiffrement.

1. Chiffrement symétrique :
Il y a deux types de chiffrement:
- Chiffrement en flux continu (Stream cypher) : il agit sur le texte en clair par bit ou par caractère
(octet) lors de cryptage ou décryptage. Exemple : RC4, SEAL.
- Chiffrement par bloc (Block cypher) : il agit sur le texte en clair par groupes de bits appelés blocs.
Exemple: ECB (electronic code book), CBC (cypher block chaining, DES (data encryption standard, AES
(advanced encryption standard).
La cryptographie symétrique repose sur deux principes : substitution et transposition
◦ Substitution : consiste à remplacer les caractères du texte clair par d’autres caractères (lettres,
chiffres ou autres caractères).
◦ Transposition : utilise le principe mathématique des permutations. Toutes les lettres du message
sont présentes, mais dans un ordre différent.

1/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

- Chiffrement par transposition

◦ Transposition simple de colonnes
◦ Transposition complexe de colonnes
- Chiffrement par substitution
◦ Mono-alphabétique: exp. César
◦ Poly-alphabétique: exp. Vigenère

1.1. Chiffrement par transposition simple de colonnes

Exemple :
M = CECI EST UN TEXTE À CHIFFRER DE LA PLUS HAUTE IMPORTANCE

Le texte chiffré : CNHEARETILUTCEFATAIXFPENETRLICSEEUMETÀRSPØUCDHOØ

Le chiffrement consiste à écrire en lignes le message dans une matrice 6x8 puis à lire les colonnes les
unes à la suite des autres.
Le déchiffrement consiste à écrire en colonnes le message chiffré dans une matrice 6x8 puis à lire les
lignes les unes à la suite des autres.

1.2. Chiffrement par transposition complexe de colonnes

Il s’agit de complexer davantage la transposition de colonnes en lisant les colonnes dans un ordre
différent. Il faut d’abord changer l’ordre des colonnes puis les lire de gauche à droite.
Exemple :

Le texte chiffré : ETRLICETILUTIXFPENCNHEAR…

2/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

1.3. Chiffrement de César

On place les 26 lettres de l’alphabet dans l’ordre habituel et le message codé est obtenu en décalant
circulairement (après z en reprend en a) chaque lettre de message clair de 3 positions (k=3). Le
chiffrement de César peut être généralisé en utilisant une clé quelconque.

p : lettre en clair, k : clé, C : lettre chiffré, E : fonction de chiffrement, D : fonction de déchiffrement

Pour le chiffrement :
C = E(p) = (p + k) mod 26
Pour le déchiffrement :
p = D(C) = (C − k) mod 26

Exemple :
texte = ABCD, Clé k= 10
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Décalage de 10 vers la droite, A est remplacé par K
Décalage de 10 vers la droite, B est remplacé par L
Décalage de 10 vers la droite, C est remplacé par M
Décalage de 10 vers la droite, D est remplacé par N
Texte chiffré : KLMN

Autre dérivé de chiffrement César, l’alphabet substituant ne résulte plus d’un simple décalage mais
d’une permutation aléatoire.

Si le texte est suffisamment long, il est possible de trouver la substitution en analysant la fréquence
des lettres.

Exercice :
1. Ecrire une fonction Crypt() prenant en paramètre un caractère (chaine d’un seul caractère) et la
clé, et affiche le caractère crypté.
2. Ecrire une fonction CesarCrypt() prenant en paramètre une chaine de caractères (le message à
crypté) et la clé, et affiche le message crypté.
3. Ecrire une fonction CesarDecrypt() qui prend 2 paramètres, un texte crypté et la clé et affiche le
texte décrypté.

3/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

Correction :
1)

2)

4/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

3)

CesarDecrypt(S,k)= CesarCrypt(S,-k)

5/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

1.4. Chiffrement de Vigenère

C’est une amélioration du chiffrement de César. Sa force réside dans l’utilisation non pas de 1, mais
de 26 alphabets décalés pour chiffrer un message.
Le chiffrement de Vigenère utilise le Carré de Vigenère : une table composée de 26 alphabets, écrit
dans l’ordre, mais décalée de ligne en ligne d’un caractère. On écrit encore en haut un alphabet
complet, pour la clé, et à gauche verticalement un autre alphabet pour le texte à coder.
Pour coder un message, on choisit une clé qui sera un mot de longueur arbitraire. On écrit ensuite
cette clé sous le message à coder, en la répétant aussi souvent que nécessaire pour que sous chaque
lettre du message à coder on trouve une lettre de la clé. Pour coder, on regarde dans le tableau
l’intersection de la ligne de la lettre à coder avec la colonne de la lettre de la clé.

Exemple :
Chiffrer le texte "CHIFFRE DE VIGENERE" avec la clef "BACHELIER" (cette clef est éventuellement
répétée plusieurs fois pour être aussi longue que le texte clair)

La grande force du chiffre de Vigenère est que la même lettre sera chiffrée de différentes manières
d’où perte de la fréquence des lettres, ce qui rend inutilisable l’analyse de fréquence classique.

6/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

Exercice :
1. Ecrire une fonction de cryptage void vigenereCrypt(const char text[], const char key[], char *
ciphertext)
2. Ecrire une fonction de déchiffrement void vigenereDec(const char * ciphertext, const char * key,
char * text), en utilisant la fonction précédente.

Correction :
1)

7/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

2)

8/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

2. Chiffrement asymétrique : Chiffrement RSA

Le chiffrement asymétrique est appelé aussi chiffrement à clé publique. Les clefs de chiffrement et
déchiffrement sont distinctes et ne peuvent se déduire l’une de l’autre.
Si la clé publique sert au chiffrement, tout le monde peut chiffrer un message, que seul le
propriétaire de la clé privée pourra déchiffrer.
Exemples : RSA, EL-Gamal.
L’algorithme RSA a été inventé par Rivest, Shamir et Adleman. Il est utilisé dans les sites web
commerciaux, les cartes à puce, les banques...
La puissance du cryptage RSA est en effet basée sur la difficulté de trouver deux grands nombres
premiers p et q à partir de leur produit n.
C'est pour cela que l'on choisit n très grand, pour rendre la factorisation hors de portée, même des
meilleurs ordinateurs.

2.1. Principes :
Génération des clés :
1. choisir au hasard deux grands nombres p et q premiers
2. calculer n=p*q et z=(p-1)*(q-1)
3. sélectionner e tel que: e et z soient premiers entre eux (PGCD (e, z)=1) avec 1 < e < z
4. calculer d tel que : e*d= 1 (modulo z ) (e et d sont inverses l’un de l’autre modulo z)
Clé publique : (e,n) ou tout simplement e
Clé secrète (privé) : (d,n) ou tout simplement d

Chiffrement :
1. Obtenir la clé publique (e,n) du destinataire
2. Représenter le message comme un entier m tel que 1 < m < n
3. Calculer le texte chiffré C = me mod n

Déchiffrement :
A l’aide de la clé privé d, calculer m = Cd mod n

2.2. Exemples
Exemple 1: Chiffrer (nombre) /Déchiffré
Supposons qu’on a : p = 3, q =11, n = p*q= 33, z=(p-1)*(q-1) = 20, e = 3 et d = 7.

1. Chiffrer le message M représenté par le nombre 29 :

Le message crypté C = 293 mod 33=2

2. Déchiffrer le nombre 2:
Le message en clair M= 27 mod 33=29

Remarque: dans la pratique, soit M le message binaire à crypter, on découpe M en blocs de k bits tel
que2k -1<n.

9/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

Exemple 2 : Générer les clés/ Chiffrer (chaine de caractères) /Déchiffré

1. Générer les clés
Prendre 2 nombres premiers au hasard: p = 29, q = 37
Calculer n = p*q = 29 * 37 = 1073
Choisir e au hasard tel que e n'ai aucun facteur commun avec (p-1)(q-1) = 1008
On choisit e = 71
On choisit d tel que 71*d = 1 modulo 1008  d = 1079
◦ La clé publique est (e, n) = (71,1073)
◦ La clé privée est (d, n) = (1079,1073)
2. Chiffrer « HELLO »
◦ Prendre le code ASCII des caractères m = 72 69 76 76 79
◦ Découper m en blocs qui comportent moins de chiffres que n. (n comporte 4 chiffres),
Alors découper m en blocs de 3 chiffres: 726 976 767 900 (on complète avec zéros)
◦ Chiffrer chacun de ces blocs: «C = Me mod n »
726^71 mod 1073 = 436 976^71 mod 1073 = 822
767^71 mod 1073 = 825 900^71 mod 1073 = 552
Le message chiffré est 436 822 825 552.
3. Déchiffrer 436 822 825 552 (avec d) : «M = Cd mod n »
436^1079 mod 1073 = 726 822^1079 mod 1073 = 976
825^1079 mod 1073 = 767 552^1079 mod 1073 = 900
 Le message déchiffré est 726976767900.
Notre message en clair retrouvé 72 69 76 76 79 : « HELLO ».

2.3. Algorithmes
A) Génération des clés
Etape 1 : Génération de p et q
p est q doivent être deux entiers premiers.
« Un nombre est premier si et seulement s’il ne possède aucun diviseur hormis 1 et lui-même. »
Exemples : 2, 3, 5, 7, 11, 13, 17, 19, …
Pour un nombre donné, il suffit donc de calculer les restes de tous les entiers > 1 qui sont strictement
inférieurs à ce nombre. Si l’un d’eux a un reste nul, il est diviseur, et le nombre n’est pas premier.
Sinon, le nombre est premier.
Algorithme :Est premier
EstPremier (n : entier long) : booléen
DEBUT
premier : booléen
i : entier
premier  VRAI
POUR i  2 JUSQU’A i < n FAIRE
Si (n mod i = 0) ALORS
premier FAUX
INTERROMPRE
FIN SI
FIN POUR
RENVOYER premier
FIN

10/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

- Il nous suffit maintenant de choisir un nombre au hasard, et tester s’il est premier ou non. S’il ne
l’est pas, on choisit au hasard un nouveau nombre, et ainsi de suite jusqu'à en obtenir un premier.
Algorithme : Génération de p et q
DEBUT
FAIRE
FAIRE
p  ( 3+rand() ) mod PQ_MAX
TANT QUE (estPremier(p) ≠ 1)
FIN FAIRE
FAIRE
q  ( 3+rand() ) mod PQ_MAX
TANT QUE (estPremier(q) ≠ 1)
FIN FAIRE
TANT QUE (p = q) OU (p*q ≤ PQ_MAX)
FIN FAIRE
FIN
Remarques :
- Dans l’algorithme précédent, deux tests sont effectués une fois p et q trouvés :
On vérifie que p ≠ q. En effet, si p = q, le code peut être plus facile à forcer.
On vérifie que p * q > 256, afin que notre programme soit bijectif (cf. limites du RSA).
- Si l’une de ces deux conditions n’est pas remplie, on choisit deux autres nombres p et q.
De plus, les nombres premiers 1 et 2 ne conviennent pas pour p et q. En effet, si p ou q = 1, on a z =
0, et si p = 1 on a z = (q-1), ce qui est très facile à casser.

Etape 2 : Calcul de n et z
A partir de p et q, on calcule
n=p*q
et
z=(p-1)(q-1)

Etape 3 : Génération de e
La clé publique e doit être un nombre premier avec z ; c’est à dire que PGCD(e,z) = 1. La méthode la
plus simple et la plus rapide pour déterminer un PGCD est l’algorithme Euclide.
L’idée de l’algorithme : le PGCD de deux nombres n'est pas changé si on remplace le plus grand
d'entre eux par leur différence. Autrement dit, pgcd(a,b) = pgcd(b,a-b). Ainsi, comme le
remplacement de ces nombres diminue strictement le plus grand d'entre eux, on peut continuer le
processus, jusqu'à obtenir deux nombres égaux. Dans l'algorithme, on pourrait réaliser autant de
différences que l'on souhaite. Par exemple, pgcd(a,b) = pgcd(b, a-2*b).
Alors, l'algorithme d'Euclide opère ainsi : on remplace le plus grand des deux nombres par le reste de
la division euclidienne du plus grand nombre par le plus petit.
L'algorithme d'Euclide, consiste à effectuer une suite de divisions euclidiennes :
- On effectue la division euclidienne de a par b et on note r le reste.
- Ensuite, a devient b et b devient r; et on recommence: on effectue la division euclidienne de a par b
et on note r le reste.
- Et on continue ainsi de suite jusqu'à ce qu'une division donne un reste égal à 0.
Le PGCD est le dernier reste non nul.
Il peut arriver que le reste soit 1 : dans ce cas, le PGCD est 1 (le reste suivant sera forcément zéro !).

11/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

Algorithme PGCD:
Pgcd (a : entier long, b : entier long) : entier long
DEBUT
c: entier long
c0
c  a mod b
SI c = 0 ALORS
RENVOYER b // a est multiple de b, le pgcd est donc b
SINON
TANT QUE c ≠ 0 FAIRE
ab
bc
c  a mod b
FIN FAIRE
RENVOYER b // renvoyer le pgcd
FIN SI
FIN
- Nous pouvons alors choisir un nombre e<z au hasard et déterminer si celui-ci convient
(Pgcd(e,z)=1). Si ce n’est pas le cas, on choisit un autre e jusqu'à en trouver un correspondant :
Algorithme : Génération de e
DEBUT
FAIRE
e  (3 + rand()) mod z
TANT QUE(Pgcd(e, z) ≠ 1)
FIN FAIRE
FIN

Etape 4 : Génération de d
d est l’inverse de e modulo z (d = e-1 [z]) C’est-à-dire : d ×e = 1 [z]
Algorithme : Génération de clé privée d
DEBUT
d0
TANT QUE ((d*e) mod z) ≠ 1 FAIRE
d  d+1
FIN
Nous avons généré nos clés publiques et privées et nous pouvons donc crypter un message.

B) Chiffrement
Notre programme est capable de coder n’importe quel fichier : texte, image, etc. Nous n’allons donc
pas pouvoir raisonner en termes de caractères, mais en termes d’octets. Notre programme va lire le
fichier octet par octet, coder cet octet en un nouveau nombre sur deux octets (16 bits), puis l’écrire
dans un nouveau fichier, qui sera notre fichier crypté. Il est nécessaire de coder sur 16 bits car
chaque octet du fichier d’origine va devenir un nombre compris entre 0 et n (on a n < 65535 = 2 16 -1).
La taille de notre fichier crypté sera donc multipliée par deux.
Le cryptage fonctionne avec la formule suivante :
ci = m i e mod n
avec ci le caractère crypté (sur 2 octets) et mi le caractère à crypté (sur un octet)

12/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

Algorithme : Chiffrement
cryptage(lettre : caractère, e : entier long, n : entier long) : entier long
DEBUT
i, c, m : entiers longs
m  (entier long)lettre
c1
POUR i  0 JUSQU’A i < e FAIRE // effectuer c = lettre^e mod n
cc*m
c  c mod n
FIN FAIRE
RENVOYER c // renvoyer le caractère crypté
FIN
Remarque : La fonction puissance est réalisé au moyen d’une boucle de multiplication. Toutefois, à
chaque cycle, on ne multiple que le reste modulo n de la multiplication précédente. Cela est possible
car a p [n] = a p-1 [n] ×a. Cela permet d’économiser un temps de calcul considérable et d’empêcher des
débordements de mémoire.

D) Déchiffrement
Le cryptage fonctionne avec la formule suivante :
m i = c i d mod n
avec ci le caractère crypté (sur 2 octets) et mi le caractère à crypté (sur un octet)
Algorithme : Déchiffrement
dechiffrement(lettre : entier long, d : entier long, n : entier long ,) : caractère
DEBUT
i, c : entiers longs
m : caractère
c1
POUR i  0 JUSQU’A i < d FAIRE // effectue m = lettre^d mod n
c  c * lettre
c  c mod n
FIN FAIRE
m = (caractère) c
RENVOYER m // renvoyer la lettre de texte en clair
FIN

13/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

Exercice (PROGRAMME C ):
1) Ecrire une fonction booléenne estPremier permettant de tester si un entier en paramètre est un
nombre premier afin de choisir le couples d’entiers premier (p,q)
2) Ecrire une fonction PGCD permettant de renvoyer le pgcd de deux entiers longs en paramètres,
afin de calculer la clé publique (e,n) et la clé privée (d,n) à partir de (p,q).
3) Ecrire une fonction cryptageRSA qui prend en paramètres un caractère et la clé publique (e,n) et
qui permet de crypter le caractère et renvoyer le message crypté.
4) Ecrire une fonction decryptageRSA qui prend en paramètres le message crypté et la clé privée
(d,n) et qui permet de décrypter le message et renvoyer le caractère en clair.

Correction :
1)

14/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

2)

15/16
ISSAT SOUSSE 3 LSI
Département informatique Sécurité informatique
AU : 2021/2022 Dr. WALA ZAABOUB

3)

16/16