Cryptographie
Introduction
1
Définitions
⚫ Crypto-système : mécanisme permettant de camoufler des messages
⚫ le rendre incompréhensible pour quiconque n’est pas autorisé
⚫ Cryptographie : art de créer et utiliser des crypto-systèmes
⚫ Cryptanalyse : art de “casser” des crypto-systèmes
⚫ Cryptologie : étude de la cryptographie + cryptanalyse
⚫ À PROSCRIRE : cryptage, encryptage, chiffrage, chiffration !!!!!
Convention secrète
chiffrement
Texte en Texte chiffré
clair
(cryptogramme)
déchiffrement
2 cryptanalyse
Sécurité des réseaux et des systèmes (espions)
Chiffrement à clé secrète
⚫ Chiffrements à clé secrète :
⚫ Symétrique : utilisation de la même clé
⚫ Secrète : clé échangée entre (connue seulement) les communicants légitimes
⚫ Fonctionnement : block ciphers ou stream ciphers
⚫ Principes de base
⚫ Substitution
⚫ Transposition
Clé secrète
Texte chiffré
3 Sécurité des réseaux et des systèmes
Le principe de la Transposition
⚫ Utilise le principe mathématique des permutations (ordre différent)
⚫ Toutes les lettres du message sont présentes
⚫ Seul l’ordre est changé
⚫ Techniques:
● Réarranger données à chiffrer de façon à les rendre incompréhensibles.
⚫ Transposition simple: Anagramme
⚫ Transposition par clé: Les permutations sont décrites par une clé secrète
Transposition simple
BONJOUR JOBOURN
4 Sécurité des réseaux et des systèmes
Exemple de Transposition:
Transposition simple par colonnes
⚫ Chiffrement (Carré de César):
⚫ Message écrit horizontalement dans une matrice prédéfinie, et
⚫ Message chiffré en lisant la grille verticalement.
⚫ Déchiffrement
⚫ Procédé inverse
⚫ Taille matrice
⚫ Exemple
⚫ Message à envoyer : VIVE LA SECU
⚫ Message Chiffré : VLCIAUVSEE
5 Sécurité des réseaux et des systèmes
Exemple de Transposition:
Transposition Asyrienne (600 av J.C)
⚫ Chiffrement
⚫ Enrouler une bande de papyrus sur un cylindre appelé scytale ;
⚫ Ecrire le texte longitudinalement sur la bandelette ainsi enroulée
⚫ Déchiffrement
⚫ Utiliser cylindre de même diamètre.
⚫ Cryptanalyse (statistique) :
⚫ Essayer cylindres de diamètre différents
6 Sécurité des réseaux et des systèmes
Le principe de la substitution
⚫ On remplace une lettre par autre chose.
A donne D, B donne E...
BONJOUR ERQMRXU
⚫ Simple mono-alphabétique:
⚫ Remplacer une lettre par une autre
⚫ Synonymique
⚫ Une lettre peut être remplacée par plusieurs signes
⚫ exemple : A donne % ou µ ou $
⚫ Polyalphabétique
⚫ Différents décalages suivant une clé
⚫ exemples : Vigenère, WordPerfect, … plus élaboré : RC4
7 Sécurité des réseaux et des systèmes
Exemple de substitution:
Substitution Mono-alphabétique (60~50 av. J.C)
⚫ Principe:
⚫ Ajout d'une valeur constante à l'ensemble des caractères du message
⚫ Décaler les caractères (mod. 26) d'un certain nombre de positions
⚫ substituer chaque lettre par une autre
⚫ Clé
⚫ Valeur que l'on ajoute au message (décalage) pour effectuer le chiffrement
⚫ Exemple
⚫ "CA MARCHE" avec Clé = 3 (ou C) ==> "FD PDUFKH"
⚫ Inconvénient
⚫ Totalement symétrique
⚫ Calculer fréquences d'apparition lettres dans message codé ...
8 Sécurité des réseaux et des systèmes
Exemple de substitution:
Substitution Mono-alphabétique (suite)
⚫ Technique:
⚫ Chaque caractère du texte en clair est remplacé par un caractère
correspondant dans le texte chiffré.
⚫ Les exemples les plus célèbres sont les algorithmes cesar, morse, …
⚫ Exemple ?
ABCDEFGH I J KLMNOPQRS T UVWXYZ
DE FGHI J KLMNOP Q RSTUVWXYZ ABC
⚫ Clair : LANCE LES MISSILES
⚫ Chiffré : ODQFH OHV PLVVLHV
⚫ Mais : cryptanalyse statistique (Fréquence des lettres)
9 Sécurité des réseaux et des systèmes
Le Chiffrement de Hill
⚫ Idée:
⚫ Ne plus coder lettres par lettres, mais de coder simultanément des groupes de m lettres!
⚫ Plus m est grand, plus les analyses statistiques deviennent difficiles !
⚫ Technique:
⚫ Remplacer chaque lettre par son ordre dans l'alphabet-1 :
⚫ A devient 0, B devient 1, C devient 2, …
⚫ Grouper les nombres ainsi obtenus par m (prenons par exemple m=2).
⚫ Pour chaque bloc de m nombres à coder x1x2...xm, on calcule le texte codé en effectuant des
combinaisons linéaires (ici m=2) :
y1=ax1+bx2
y2=cx1+dx2
⚫ Le choix de la clé correspond ici au choix d'un nombre m, et au choix des combinaisons
linéaires à effectuer (ce sont toujours les mêmes de blocs en blocs).
10 Sécurité des réseaux et des systèmes
Le Chiffrement de Hill (Suite)
❖coder le mot ELECTION avec le chiffre de Hill
● Clé : a=3, b=5, c=1 et d=2.
● Etape 1 : Découpage en blocs de 2 : EL | EC | TI | ON
● Etape 2 : remplacer lettres par leur nombre associé : 4-11 | 4-2 | 19-8 | 14-13
● Etape 3 : combinaisons linéaires pour chaque bloc.
● E.g., pour le 1er bloc (x1=4, x2=11)
A B C D E F G H I J K L M
Y1= 3×4 + 5×11 = 67 = 15 [26] 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
Y2= 1×4 + 2×11 = 26 = 0 [26]
13 14 15 16 17 18 19 20 21 22 23 24 25
De même, y3=22, y4=8, y5=97, y6=35, y7=107, y8=40.
● Etape 4 : restes mod [26]: z1=15, z2=0, z3=22, z4=8, z5=19, z6=9, z7=3, z8=14.
● Etape 5 : On reconvertit en lettres ==> Chiffré : PAWITJDO.
11 Sécurité des réseaux et des systèmes
Le Chiffrement de Hill (Suite)
⚫ Remarques :
⚫ Le premier E de ELECTION est transformé en P,
⚫ Le second est transformé en W.
⚫ Le critère des chiffrements polyalphabétique est bien respecté :
⚫ Les analyses statistiques directes sur la fréquence des lettres sont
impossibles.
⚫ Déchiffrement
⚫ Découper message en blocs de m lettres,
⚫ Inverser relations données par les combinaisons linéaires : si un
système donne y1 et y2 en fonction de x1 et x2, il faut pouvoir l'inverser
et exprimer y1 et y2 en fonction de x1 et x2.
⚫ Utiliser la matrice inverse.
12 Sécurité des réseaux et des systèmes
Rappel Calcul Matriciel
⚫
13
Le Déchiffrement
⚫
14
Détermination exhaustive
⚫ On peut utiliser la manière exhaustive :
⚫ Exemple: Pour Det(H) = 3, on vérifie 3 x k = 1 [26]
3 x 1 = 3 [26] 3 x 2 = 6 [26] 3 x 3 = 9 [26]
3 x 4 = 12 [26] 3 x 5 = 15 [26] 3 x 6 = 18 [26]
3 x 7 = 21 [26] 3 x 8 = 24 [26] 3 x 9 = 27 = 1 [26]
⚫ L’inverse de 3 dans un système modulo 26 est donc 9.
15
Algorithme d’Euclide étendu
⚫ On veut retrouver k l’inverse de 3 dans un système modulo 26:
26 26
8x 3 1
=26-8x3=2 =26-8x1=18
16
Algorithme d’Euclide étendu
⚫ On veut retrouver k l’inverse de 3 dans un système modulo 26:
26 26
8x 3 1
1x 2 18
3-2x1=1 1-1x18=-17=9
17
Algorithme d’Euclide étendu
⚫ On veut retrouver k l’inverse de 3 dans un système modulo 26:
26 26
8x 3 1
1x 2 18
1 k=9
18
Algorithme d’Euclide étendu
⚫ On veut retrouver k l’inverse de 7 dans un système modulo 26:
26 26
3x 7 1
=26-3x7=5 =26-1x3=23
19
Algorithme d’Euclide étendu
⚫ On veut retrouver k l’inverse de 7 dans un système modulo 26:
26 26
3x 7 1
1x 5 23
7-1x5=2 1-1x23=-22=4
20
Algorithme d’Euclide étendu
⚫ On veut retrouver k l’inverse de 7 dans un système modulo 26:
26 26
3x 7 1
1x 5 23
2x 2 4
5-2x2=1 23-2x4=15
21
Algorithme d’Euclide étendu
⚫ On veut retrouver k l’inverse de 7 dans un système
modulo 26:
26 26
3x 7 1
1x 5 23
2x 2 4
1 k =15
Vérification : 7 x 15 = 105 [26] = 1 [26]
22
Exercice
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
23
Correction
⚫
24
Modes opératoires
Le mode dictionnaire ou mode ECB (Electronic
CodeBook) réalise une substitution simple. Le
message est découpé en blocs de même taille et
tous les blocs sont chiffrés de manière identique,
indépendamment les uns des autres en
appliquant sur chacun d’entre eux la fonction de
calcul sur un bloc.
Ce mode présente l’inconvénient de chiffrer de la
même façon les blocs identiques du message en
clair.
25