Faculté des Sciences de Bizerte

Cours Sécurité Informatique

Chapitre 3: Cryptologie classique

Présenté par :

Dr. Olfa DRIDI :

[email protected]

Année Universitaire: 2015 -2016

Plan

Introduction

2. Chiffrements monoalphabétiques

3. Chiffrements polyalphabétiques

4. Conclusion

24/10/2015

Introduction: Cryptographie à clé secrète

(cid:1) Les deux acteurs s‘échangent une clé secrète (mot de passe).

(cid:1) La sécurité du chiffrement dépend de la non divulgation de cette clé.

Chiffrement classique

(cid:1) Chiffrement par transposition

(cid:1) Chiffrement par substitution

(cid:1) Substitution monoalphabétique

(cid:1) Substitution polyalphabétiques

24/10/2015

Introduction: Deux grandes catégories

(cid:1) Chiffrement par bloc

(cid:1) M (message) est traité par blocs de données (ex: 64 bits ou 128 bits)

(cid:1) Algorithmes : DES, AES, IDEA, RC6, BLOWFISH, …

(cid:1) Chiffrement par flot

(cid:1) M est traité bit par bit

(cid:1) Algorithmes :RC4, Bluetooth E0/1, GSMA5/1,

Chiffrements par transposition

24/10/2015

Chiffrement par transposition

(cid:1) Les méthodes de chiffrement par

réarranger (permuter) les données à chiffrer de telle façon à

les rendre incompréhensibles.

transposition consistent

(cid:1) Transposer = opérer une permutation des symboles d’un message en

clair : remplacer chaque symbole par un autre symbole du message.

(cid:1) Chiffrement de type anagramme:

(cid:1) Les lettres du messages sont déplacées

Chiffrement par transposition

(cid:1) Elles consistent, par définition, à changer l’ordre des lettres. C’est un

système simple, mais peu sûre pour de très brefs messages car il y a

peu de variantes. Ainsi, un mot de trois lettres ne pourra être

transposé que dans 6 (=3!) positions différentes. Par exemple, "col"

ne peut se transformer qu’en "col", "clo", "ocl", "olc", "lco" et

"loc".

(cid:1) Lorsque le nombre de lettres croît, il devient de plus en plus difficile

de retrouver le texte original.

(cid:1) Une phrase de 35 lettres peut être disposée de 35! = 1040 manières

différentes.

(cid:1) Problèmes

(cid:1) Pas robuste pour des messages courts

24/10/2015

Exemple de transposition ancien

(cid:1) Un cylindre sur lequel une ceinture est enroulée.

(cid:1) On écrit le message sur la ceinture selon une génératrice du

cylindre.

(cid:1) Lorsqu’on déroule la ceinture le message en clair est rendu obscur.

Exemple de transposition moderne

(cid:1) Utilisation moderne: transposition basée sur un tableau => qui

définit l’ordre des symboles du texte en clair dans le texte chiffré.

(cid:1) On écrit le texte en clair en ligne dans un tableau.

(cid:1) On se donne une clé pour déterminer l’ordre d’utilisation des colonnes

dans le texte chiffré. Exemple de clé : ‘Permutations’ avec ses chiffres

(cid:1) 16;5;18;13;21;20;1;8;15;14;19 (écrite la première ligne).

(cid:1) On réordonne la clé 1;5;8;13;14;15;16;18;19;20 (ordre total la lettre

répétée T est ôtée)

(cid:1) On transmet en colonnes dans l’ordre de la clé => Message chiffré:

.OCURNAS NALTNXIUNTOTA BI MPEA SVE.

24/10/2015

Chiffrements monoalphabétiques

Substitution monoalphabétique

(cid:1) On appelle chiffrement monoalphabétique ou substitution

simple, un chiffre où chaque lettre est remplacée par une autre

lettre ou symbole.

(cid:1) Remplacer chaque lettre de l'alphabet par une autre

(cid:1) Dresser une table de substitution des caractères.

A B C D E F G H I J K L M N O P Q R S T UV W XY Z

QW E R TY U I O P A S D F G H J K L Z X C V B N M

Substitution monoalphabétique

(cid:1) quelques grands noms : Al-Kindi (801-873), Alberti (1404-

1472), Porta (1535-1615), Babbage (1792-1872), Kerckhoffs

(1835-1903),Turing (1912-1954).

Avantage:

(cid:1) Plus sécuritaire que « l’algorithme de transposition », surtout

pour les messages courts.

Inconvénients:

(cid:1) Il faut se souvenir de la table de substitution

(cid:1) Peut être briser par des outils tels que l'analyse fréquentielle

Substitution monoalphabétique

(cid:1) Grand nombre de clés

(cid:1) Mais toujours pas de diffusion

(cid:1) Même si l'algorithme est connu, il est impossible d'essayer les

26! - 1 clés possibles (403291461126605635583999999)

(cid:1) Faire la substitution de chaque caractère du message par le

caractère correspondant de la table.

Il est difficile de briser ce message

Os tlz royyoeost rt wkoltk et mtllqut

24/10/2015

Chiffrement de César

(cid:1) Jules César : chiffrement d'un message par décalage des lettres dans

l'alphabet.

(cid:1) Algorithme: Décaler chaque lettre de X positions.

(cid:1) Clé: X = +3

(cid:1) A(cid:1)d,

(cid:1) B(cid:1)e,

(cid:1) C(cid:1)f, …

(cid:1) Exemple: Bonjour voici votre premier cryptogramme

Erqmrxu yrlfl yrwuh suhplhu fubswrjudpph

(cid:1) Problème: Lorsque l’algorithme est connu, il est facile d’essayer

toutes les 25 clés possibles.

L’algorithme de Jules César

Avantage

(cid:1) algorithme simple

(cid:1) clé simple

(cid:1) rapide et simple pour les deux opérations

Inconvénients

(cid:1) facile à briser

Critique de la substitution

monoalphabétique

(cid:1) Les deux méthodes précédentes appartiennent aux systèmes de

substitution monoalphabétique. Dans un texte en clair, une

lettre est toujours substituée par la même lettre.

(cid:1) Si le texte est suffisamment long, il est possible de trouver la

substitution en analysant la fréquence des lettres. Donc, le texte

en clair peut être retrouvé à partir du cryptogramme seul.

(cid:1) Ce sont les Arabes qui ont réussi à briser ce code.

Occurrence des lettres

En français

Dans le cryptogramme

____ 19.3 LLLL 4.7 HHHH 0.8

EEEE 13.9 OOOO 4.1 GGGG 0.8

DDDD 2.9 BBBB 0.6

AAAA 6.7

PPPP 2.5 XXXX 0.4

SSSS 6.3

CCCC 2.4 YYYY 0.3

IIII 6.1

MMMM 2.1 JJJJ 0.3

TTTT 6.1

VVVV 1.3 ZZZZ 0.1

NNNN 5.6

QQQQ 1.3 KKKK 0.0

RRRR 5.3

FFFF 0.9 WWWW 0.0

UUUU 5.2

PPPP 14.3 DDDD 4.6 WWWW 1.0

KKKK 12.8 LLLL 4.1 UUUU 1.0

VVVV 3.1 TTTT 1.0

SSSS 9.2

ZZZZ 2.6 ____ 0.5

JJJJ 9.2

GGGG 2.6 OOOO 0.0

XXXX 5.6

CCCC 2.6 MMMM 0.0

QQQQ 5.6

EEEE 2.0 FFFF 0.0

NNNN 5.6

RRRR 1.5 AAAA 0.0

BBBB 5.1

HHHH 1.5 YYYY 0.0

IIII 4.6

24/10/2015

Occurrence des lettres

(cid:1) Cependant, il existe également des cas où cette analyse ne fonctionne

pas, comme le montre l’exemple ci-dessous.

(cid:1) Exemple : De Zanzibar à la Zambie et au Zaïre, des zones d’ozone

font courir les zèbres en zigzags zinzins.

(cid:1) Pour éviter ce type d’attaque sur un texte chiffré, il existe différents

moyens :

(cid:2)On peut par exemple chiffrer le message par digrammes, trigrammes,

etc.

Substitution+

(cid:1) Au lieu de faire la substitution mono-alphabétique,

on peut rendre le code plus difficile à briser en

faisant une substitution de mots. Chaque mot est

remplacé par un nombre, d’où la nécessité d’un

dictionnaire. On peut utiliser des synonymes.

(cid:1) Cette technique n’est pas vraiment pratique. La

construction du dictionnaire est fastidieuse.

Il faut

se déplacer avec le dictionnaire qui pourrait être

intercepté. Il est difficile de changer le code.

24/10/2015

Chiffrements polyalphabétiques

Chiffrement polyalphabétique

(cid:1) Un chiffrement polyalphabétique peut remplacer une lettre par une

autre lettre qui n’est pas toujours la même.

BlaiseVigenère 1523-1596

(cid:1) Le chiffre de Vigenère appartient aux systèmes de substitution

polyalphabétique. Dans un texte en clair, une lettre est

substituée par une autre lettre dépendant de sa position dans le

texte.

(cid:1) Principe : Additionner à chaque lettre la lettre de la clé.

(cid:1) Clé = suite de lettres de longueur k (ex : « abcd », k=4)

24/10/2015

Vigenère

Tableau de Vigenère

Tableau de

Vigenère

Tableau de

paire,

chaque

Pour

caractère de la clé choisit une

ligne du tableau de Vigenère

le caractère du message

choisit la colonne.

L’algorithme de codage est

basé sur la formule suivante:

Ci = (Ti + Ki) mod N

: Exemple

Vigenère: Exemple

Chiffrement de Vigenère

Chiffrement de

: Exemple

Vigenère

Chiffrement de

Texte clair :

b o n j o u r v o i c i v o t

r e t e x t e c l a i

Clé:

a b c d a b c d a b c d a b c d a b c d a b c d a b c

1 1

9 1

8 2 8 2

4 1

4 2

4 2 1

0 8 1

0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2

1 1

9 4 1

4 2

6 2

5 4 1

0 9 1

Cryptogramme:

b p p m o v t z o j e l v p v u e u g a t

f e o a j

24/10/2015

Le chiffre de Vigenère est-il

indéchiffrable?

Les cryptanalystes furent déjoués pendant près

de 3 siècles par le chiffre de Vigenère.

Au 19ième siècle, Charles Babbage réussit à le

briser.

La technique est relativement simple.

Vigenère

Chiffrement de Vigenère

Chiffrement de

Vigenère

Chiffrement de

(cid:1) Si le texte est suffisamment long, il est possible de trouver les

substitutions en découpant le texte selon la longueur présumée de la

clé puis en analysant les fréquences des lettres.

(cid:1) Donc, le texte en clair peut être retrouvé à partir du cryptogramme

seul.

(cid:1) Même si le nombre de clés est grand, cette méthode n’est pas

acceptable.

Vigenère

Cryptanalyse du chiffrement de Vigenère

Cryptanalyse du chiffrement de

Vigenère

Cryptanalyse du chiffrement de

Méthode en trois étapes :

1. Trouver la longueur l de la clé

2. Découper le message M en l messages m0...ml-1

(cid:1) mi contient l'ensemble des lettres dont la position dans le texte modulo l

est égal à i

(cid:1) Exemple : si l'on aligne M sur l colonnes, mi est la ieme colonne (cf.

tableau)

(cid:1) Toutes les lettres d'un mi sont chiffrées avec le même décalage

3. Analyse fréquentielle sur chacun des mi

(cid:1) Déterminer le décalage de chaque colonne

(cid:1)Sortie : la clé k

Vigenère

Cryptanalyse du chiffrement de Vigenère

Cryptanalyse du chiffrement de

Vigenère

Cryptanalyse du chiffrement de

Deux étapes:

1. Trouver la longueur du mot-clé ;

Faire l'analyse fréquentielle sur chacun des alphabets.

24/10/2015

Étape 1: Recherche de la clé

(cid:1) L’indice de coïncidence:

permet de calculer la probabilité de répétitions des lettres du

message chiffré. Il est souvent couplé avec l’analyse fréquentielle.

Cela permet de savoir le type de chiffrement d’un message

(chiffrement monoalphabétique ou polyalphabétique) ainsi que la

longueur probable de la clé.

: Recherche de la clé

Étape 1111: Recherche de la clé

Étape

: Recherche de la clé

Étape

(cid:1) On recherche des séquences qui se répètent de deux ou trois lettres

et le nombre de caractères qui séparent ces répétitions :

Étape 2: Analyse des fréquences

(cid:1) Principe (Al-Kindi – 9ème siècle)

(cid:1) Toutes les lettres de la langue française n'ont pas la même

fréquence d'apparition.

(cid:1) Par analyse statistique de la fréquence des lettres de l'alphabet

chiffré, il est possible de retrouver les substitutions.

(cid:1) Particulièrement vrai si le texte chiffré est long.

langue française

Fréquences ––––langue française

Fréquences

langue française

Fréquences

Fig: Fréquences des lettres en français

24/10/2015

Limites de l’analyse des fréquences

(cid:1) Sur des textes donnant des fréquences très éloignées de celles

habituelles :

(cid:1) De Zanzibar à la Zambie et au Zaïre, des zones d ’ozone font courir les

zèbres en zigzags zinzins.

time pad

Masque jetable ––––OneOneOneOne----time pad

time pad

Masque jetable

(cid:1) Les principales faiblesses des systèmes de substitution polyalphabétique

classiques sont:

(cid:1) La taille de la clé

(cid:1) Le fait que la clé soit réutilisée.

(cid:1) Pour pallier ce problème, il «suffit» d’avoir un algorithme polyalphabétique

dont

(cid:1) la clé est aussi longue que le message à chiffrer,

(cid:1) la clé est nouvelle pour chaque nouveau message.

(cid:1) Transférer le problème de transmettre un message chiffré à celui de

transmettre une clé de façon sécurisée.

(cid:1) Avec quelle clé chiffrer la clé???

24/10/2015

Masque jetable

(cid:1) Le masque jetable est le seul algorithme de cryptage connu comme

étant indécryptable. C'est en fait un chiffre de Vigenère avec comme

caractéristique que la clef de chiffrement a la même longueur que le

message clair. Le système du masque jetable fut inventé par Gilbert

Vernam en 1917, puis perfectionné par le major Joseph O.

Mauborgne en 1918, qui inventa le concept de clef aléatoire.

Vernam

Mauborgne

Masque jetable

(cid:1) Peut-on avoir un cryptosystème ayant une confidentialité

absolue et qui soit impossible à briser?

(cid:1) Qu’arrive-t-il si on utilise le chiffre de Vigenère avec une clef

aussi longue que le message?

(cid:1) Avec une clef aléatoire, on obtient le masque jetable.

(cid:1) Pour être inconditionnellement sécuritaire, la clef doit être

choisie aléatoirement et être utilisée une seule fois.

24/10/2015

Sécurité du masque jetable

(cid:1) Si la clef est: 12,7,24,3,26,11,5,21,0,25

(cid:1) ALAIN_TAPP devient MSYLMKYVPN

(cid:1) Pour toute interprétation du message, il existe une clef la

justifiant.

(cid:1) Avec la clef: 11,4,11,2,25,22,20,22,16,14

(cid:1) BONJOUR___ devient MSYLMKYVPN

(cid:1) C’est Shannon en 1949 qui a démontré formellement que le

masque jetable est inconditionnellement sécuritaire.

(cid:1) L’inconvénient du masque jetable est la taille nécessaire de la

clef.

à clé courte

Cryptosystème à clé courte

Cryptosystème

à clé courte

Cryptosystème

(cid:1) Principe de Kerckhoff (La cryptographie militaire 1883).

(cid:1) La sécurité d’un système de cryptographie ne doit pas dépendre de la

préservation du secret de l’algorithme. La sécurité ne repose que sur le

secret de la clef.

(cid:1) Le masque jetable n’est pas pratique.

(cid:1) Peut-on chiffrer avec une clef courte de façon sécuritaire?

24/10/2015

Enigma

(cid:1) Enigma est la machine à chiffrer et déchiffrer qu'utilisèrent les

armées allemandes du début des années trente jusqu'à la fin de

Seconde Guerre Mondiale. Elle automatise le chiffrement par

substitution. Comme on peut le voir ci-contre, cette machine

ressemble à une machine à écrire. Quand on presse sur une touche,

deux choses se passent. Premièrement, une lettre s'allume sur un

panneau lumineux: c'est

la lettre chiffrée. Deuxièmement, un

mécanisme fait tourner le rotor de droite d'un cran; toutes les 26

frappes, le deuxième rotor tourne d'un cran, toutes les 676 frappes

(26 au carré), c'est le troisième rotor qui tourne d'un cran. Certaines

Enigmas avaient 3 rotors. Ces rotors

les

connexions électriques dans la machine, ce qui fait que la touche "A"

allumera peut-être le "B" la première fois, mais le "X" la deuxième,

le "E" la troisième, etc.

tournants modifient

Enigma

24/10/2015

Enigma

Briser Enigma

Briser

Enigma

Briser

(cid:1) Le code ENIGMA fut brisé en décembre

1932 par Marian Rejewski, travaillant pour

les services de renseignement polonais. A

partir de 1933, les Polonais ont réussi a

de messages

déchiffrer

allemands.

des milliers

Marian Rejewski

Enigma

Briser Enigma

Briser

Enigma

Briser

(cid:1) La clef du succès de Marian Rejewski fut de se concentrer sur le fait que

chaque message commençait par une répétition de 3 lettres.

(cid:1) Par exemple, pour quatre messages interceptés, on pouvait obtenir les

données suivantes:

(cid:1) LOKRGM

(cid:1) MVTXZE

(cid:1) JKTMPE

(cid:1) DVYPZX

(cid:1) Chacun de ces chiffres dépend de l’agencement des

fiches et bien sûr, des

positionnement des

Examinons la première et la quatrième lettre.

(cid:1) ABCDEFGHIJKLMNOPQRSTUVWXYZ

(cid:1)

P M RX

rotors, du

trois caractères choisis.

Enigma

Briser Enigma

Briser

Enigma

Briser

(cid:1) Avec l’interception de plusieurs messages, on peut compléter le tableau.

(cid:1) ABCDEFGHIJKLMNOPQRSTUVWXYZ

(cid:1) FQHPLWOGBMVRXUYCZITNJEASDK

(cid:1) Ce tableau dépend de la clef du jour. Marian eu une intuition remarquable.

(cid:1) A-F-W-A

(cid:1) B-Q-Z-K-V-E-L-R-I-B

(cid:1) C-H-G-O-Y-D-P-C

(cid:1) J-M-X-S-T-N-U-J

(cid:1) Le même exercice peut être réalisé avec les lettres numéro 2 et 5, ainsi que

3 et 6. Marian remarqua que la longueur des chaînes changeait à chaque jour.

(cid:1) Si on change la position des fiches, les lettres des chaînes vont changer mais

pas leurs longueurs. La longueur des chaînes ne dépend que de la position

des rotors.

3 LIENS

9 LIENS

7 LIENS

Enigma

Briser Enigma

Briser

Enigma

Briser

(cid:1) Il existe 6 x 17 576= 105 456 positionnements des rotors.

Chacun donne lieu a une liste de chaînes avec des tailles

caractéristiques. En une année, Marian réussit a construire une

table de toutes les possibilités. Pour identifier la position des

rotors, il suffisait d’intercepter quelques messages, calculer la

longueur des chaînes, et regarder dans la table.

(cid:1) Il restait maintenant à trouver la position des fiches. Une fois les

rotors bien positionnés, si on laisse le tableau des fiches vierge,

l’opération de déchiffrement donnera un message illisible mais

facile à briser. Les lettres sont simplement permutées suivant la

position des fiches. Une attaque statistique trouve facilement les

branchements.

24/10/2015

et Turing

Enigma et Turing

Enigma

et Turing

Enigma

(cid:1) Un peu avant l’invasion allemande, les Polonais ont dévoilé leurs

techniques pour briser ENIGMA aux Britanniques. La partie

n’était pas complètement gagnée. ENIGMA fut modifié durant

la guerre. Des rotors furent ajoutés et à un certain moment, les

Allemands ont cessé de répéter les trois lettres de la clef. Il y eut

donc de courtes périodes pendant lesquelles les Alliés furent

incapables de déchiffrer les messages allemands, mais des

techniques de plus en plus sophistiquées et un appareillage

électrique de plus en plus imposant leur permirent de déjouer

les cryptographes allemands.

Chiffrements par blocs

Chiffrement par blocs

(cid:1) On ne travaille plus sur des lettres de l'alphabet, mais sur un

ensemble de blocs

(cid:1) Taille des blocs : 32bits ... 256bits

(cid:1) Le message m est découpé en n blocs

(cid:1) Chaque bloc est chiffré

(cid:1) Le message chiffré m’ est la concaténation des blocs chiffrés

(cid:1) Exemples d’algorithmes : Les réseaux de Feistel, DES, AES, Etc.

(cid:1) Il existe 4 modes de chiffrement par blocs:

(cid:1) ECB: Electronic CodeBook,

(cid:1) CBC: Cipher Bloc Chaining,

(cid:1) CFB: Cypher FeedBack mode,

(cid:1) OFB: Output FeedBack.

Feistel

Réseaux de Feistel

Réseaux de

Feistel

Réseaux de

Un réseau de Feistel est défini par :

(cid:1) Une longueur de bloc l

(cid:1) Un espace de clé K

(cid:1) Un nombre de ronde r

(cid:1) Un générateur de sous-clés g, qui divise une clé k en r sous-clés

(cid:1) Une fonction de chiffrement f (f -1 doit exister)

24/10/2015

Feistel

Réseaux de Feistel

Réseaux de

Feistel

Réseaux de

Principe du mode ECB

(cid:1) Le mode ECB (Electronic Cypher Block).

(cid:1) Mode de chiffrement le plus simple.

(cid:1) Chaque bloc est chiffré tout simplement avec la clé.

24/10/2015

Principe du mode CBC

(cid:1) Le résultat du chiffrement d'un bloc m dépend de la clé et du bloc m-1.

(cid:1) Chaque bloc de texte en clair est combiné par un ou exclusif avec le bloc

chiffré précédent avant d’être chiffré. Le premier bloc du texte est

combiné avec un bloc appelé vecteur d’initialisation.

Principe du mode CBC

Avantages :

(cid:1) Le mode CBC se caractérise par une robustesse relativement plus forte que

le mode ECB.

Inconvénients :

(cid:1) Il faut se mettre d'accord sur un vecteur d'initialisation

(cid:1) Toute erreur au niveau d’un cryptogramme Ci se répercute sur tous les

cryptogrammes suivants.

Questions ?????????

24/10/2015

Cours Sécurité Informatique - Chapitre 3: Cryptologie classique

Cours Sécurité Informatique - Chapitre 3: Cryptologie classique