Embed Size (px)
Citation preview
Wattiau/Akoka 77
4.9. La cryptographie
Ou cryptologie ou chiffrement : art de
rendre des données secrètes, essentiellement
fondé sur l’arithmétique par codage
Décryptage ou déchiffrement
clef de chiffrement ou de déchiffrement <=>
mot de passe
cassage ou attaque = recherche de la clé
Wattiau/Akoka 102
4.10. La cryptographie
a) Histoire
Stéganographie : dissimulation des
messages (encre invisible, chimie, etc.)
Chiffrement de César : décalage de lettre
Grille de Vigénère : système de codage avec
clé secrète
Wattiau/Akoka 103
4.10 La cryptographie
b) Quelques techniques
Codage par transposition
Codage par substitution
Codage par clé unique
Codage par double clé
Codage par hachage
Wattiau/Akoka 104
Réagencement des lettres dans la phrase
Réarranger les données à crypter de façon à
les rendre incompréhensibles
Exemple 1 : message en dent de scie
Exemple 2 : technique assyrienne
4.10 La cryptographie
c) Codage par transposition
Cemfesai tiac sbos ldipeame gpu el e
Enrouler une bande de papyrus sur un cylindre
Ecrire le texte horizontalement sur la bande enroulée
Dérouler la bande
1è lettre sur la 1è ligne, 2è lettre sur la 2è ligne, etc.
C e c o d a g e
e s t s i m p l e
m a i s p e u
f i a b l e
Wattiau/Akoka 105
4.10. La cryptographie
d) Codage par substitution
Chaque lettre de l ’alphabet est remplacée par
une autre :
– par décalage : IBM devient HAL
• décalage de -1
• décalage de 3 : chiffrement de César
• décalage de 13 : ROT13
– décodage :
• faire des tests modulo tous les nombres de 1 à 26
jusqu ’à ce que le résultat ait un sens
• repérer les lettres selon leur fréquence dans la langue
Wattiau/Akoka 106
d) Codage par substitution
Chaque lettre de l ’alphabet est remplacée
par une autre selon une règle aléatoire :
Astuces : utiliser des caractères spéciaux,
coder les espaces et utiliser l ’espace
comme caractère de codage
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
v e k a h b c d j f g i w l m q p s r x y z n o t u
K ’hrx qivr ajbbjkjih v ahkmahs !
Tous sont faciles à casser grâce au
repérage de la fréquence des caractères
Wattiau/Akoka 107
d) Codage par substitution
Quelques exemples
Morse
Code de Beale :
– expéditeurs et destinataires s ’échangent un
texte secret dont chaque mot est numéroté
– chaque lettre du message est codé par le numéro
d ’un des mots du texte dont cette lettre est
l ’initiale
– quasi-impossible à décoder sans le texte secret
– chaque lettre peut avoir plusieurs codes
différents
Wattiau/Akoka 108
d) Codage par substitution
Exemple de code de BealeTexte clé :
Je prends un texte de référence qui va
1 2 3 4 5 6 7 8
me servir à coder par un chiffre toutes
9 10 11 12 13 14 15 16
les lettres de l alphabet et ce de
17 18 19 20 21 22 23 24
plusieurs façons différentes. Plus le texte est grand,
25 26 27 28 29 30 31 32
plus le codage est subtil ou secret. Il
33 34 35 36 37 38 39 40
reste de très vieux messages jamais décodés.
41 42 43 44 45 46 47
Message codé :
– 8-38-40-12-40-0-17-22-0-45-31-10-37-11-
32-36-0-23-38-5-36.
Wattiau/Akoka 109
d) Codage par substitution
Quelques exemples (suite)Grille de Vigénère
– s ’appuie sur un tableau de lettres
– utilise une clé
– le codage d ’une lettre est extrait de la table en
fonction de cette lettre et d ’une lettre de la clé
– comme le code de Beale, les mêmes signes du
texte codé ne renvoient pas toujours à la même
lettre du texte clair
– à l ’inverse (contrairement au code de Beale),
une lettre codée ne traduit pas toujours la même
lettre d ’origine
Wattiau/Akoka 110
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
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 a
c d e f g h i j k l m n o p q r s t u v w x y z a b
d e f g h i j k l m n o p q r s t u v w x y z a b c
e f g h i j k l m n o p q r s t u v w x y z a b c d
f g h i j k l m n o p q r s t u v w x y z a b c d e
g h i j k l m n o p q r s t u v w x y z a b c d e f
h i j k l m n o p q r s t u v w x y z a b c d e f g
i j k l m n o p q r s t u v w x y z a b c d e f g h
j k l m n o p q r s t u v w x y z a b c d e f g h i
k l m n o p q r s t u v w x y z a b c d e f g h i j
l m n o p q r s t u v w x y z a b c d e f g h i j k
m n o p q r s t u v w x y z a b c d e f g h i j k l
n o p q r s t u v w x y z a b c d e f g h i j k l m
o p q r s t u v w x y z a b c d e f g h i j k l m n
p q r s t u v w x y z a b c d e f g h i j k l m n o
q r s t u v w x y z a b c d e f g h i j k l m n o p
r s t u v w x y z a b c d e f g h i j k l m n o p q
s t u v w x y z a b c d e f g h i j k l m n o p q r
t u v w x y z a b c d e f g h i j k l m n o p q r s
u v w x y z a b c d e f g h i j k l m n o p q r s t
v w x y z a b c d e f g h i j k l m n o p q r s t u
w x y z a b c d e f g h i j k l m n o p q r s t u v
x y z a b c d e f g h i j k l m n o p q r s t u v w
y z a b c d e f g h i j k l m n o p q r s t u v w x
z 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
La grille de Vigénère
Wattiau/Akoka 111
t e x t e
+ c l é c l
v p b v p
Exemple de codage
Exemple de décodage
Le code de Vigénère peut être cassé
h l g k w i
- c l é c l é
f a c i l e
d) Codage par substitution
Exemple de code de Vigénère
Wattiau/Akoka 113
-
Etape 2 : Découper le texte crypté en n petits
textes tels que :
– la première lettre du texte crypté devient la
première lettre du 1er petit texte
– la deuxième lettre devient la première lettre du 2è
petit texte, etc,
– la (n+1)e lettre devient la deuxième lettre du 1er
petit texte, etc.
Etape 3 : Trouver le n-ème caractère de la clé
– faire une analyse de fréquence sur le n-ème petit
texte
– en déduire le nombre de décalages,
– en déduire le n-ième caractère de la clé :
• décalage de 2 caractères -> lettre c
Wattiau/Akoka 114
z y x y o y p i m k z y x y o y p
h y d t t r m u j o m r d t e w
Etape 1 : Trouver la longueur de la clé
– répétition de plus de 3 lettres : xyoyp
– nombre de lettres entre ces répétitions : 5
– il n ’y a pas plus court => n = 5
Etapes 2 et 3 :
– zyzytjt -> décalage de 5 caractères -> code F
– ypyptoe -> décalage de 11 caractères -> code L
– xixhrmw -> décalage de 4 caractères -> code E
– ymyymr -> décalage de 20 caractères -> code U
– okodud -> décalage de 17 caractères -> code R
Clé - > FLEUR
Wattiau/Akoka 115
e) Autres codes
On peut combiner transposition et substitution
– complique le cassage
Exemple GEDEFU 18
– Geheimschrift der Funker 18 - chiffre des
radiotélégraphistes 18
– écriture secrète des radios allemandes de 1918
– conçue pour être aisément transmise en Morse
– utilise deux clés de transposition et substitution
– n ’utilise que 5 lettres de codage A D F G X
Wattiau/Akoka 116
e) Autres codes
Exemple : GEDEFU 18
Utilise une première grille de substitution :
– 25 caractères (W inutilisé)
– clé de substitution :
• MONTECRISTO
A D F G X
A m o n t e
D c r i s a
F b d f g h
G j k l p q
X u v x y z
Utilise une deuxième grille de transposition :
– clé de transposition :
• dimanche
d i m a n c h e
3 6 7 1 8 2 5 4
Wattiau/Akoka 117
Transposition :
– clé de transposition :
• dimanche
– DDAAA GDFXG ADD
GA XXGAA XXDGX FFX
e) Autres codes
Exemple de codage avec GEDEFU 18
Texte à coder :
– « lancer l ’attaque »
– FGXDFAADXADDF
GXDGAGAXDXGAXXA
A D F G X
A m o n t e
D c r i s a
F b d f g h
G j k l p q
X u v x y z
d i m a n c h e
3 6 7 1 8 2 5 4
F G X D F A A D
X A D D F G X D
G A G A X D X G
A X X A
Wattiau/Akoka 118
– Défaire la transposition (écrire en colonnes dans
la grille de transposition selon l ’ordre des
chiffres), puis lire en lignes :
• FDFGGDXD
• DDDDFDDX
• XAFAGADF
• XAAAXDFD
• FA
– Décoder avec la grille de substitution
e) Autres codes
Décodage avec GEDEFU 18Texte à décoder :
– GDAAD DADFD XXFDX FDXDD FDDAA
AFDFA GFGX
d i m a n c h e
3 6 7 1 8 2 5 4
F D F G G D X D
D D D D F D D X
X Q F A G A D F
X Q Q A X D F D
F Q
Wattiau/Akoka 119
e) Autres codes
Autres codages par substitutions
N-gramme substitution :
– di-gramme : chaque couple de deux lettres est
codé en deux lettres grâce à une table de 26*26
couples de 2 lettres
– cassable par repérage des fréquences d ’apparition
de groupes de 2 lettres (TT, LL en français)
Wattiau/Akoka 120
e) Autres codes
Autres substitutionsPlayfair Cipher
– disposer les 25 lettres de l ’alphabet en matrice
– coder par groupe de 2 lettres, en prenant les
angles opposés du rectangle qu ’elles forment
– si elles sont sur une même ligne ou colonne,
prendre les deux lettres qui suivent
immédiatement
B Y D G Z
J S F U P
L A R K X
C O I V E
Q N M H T
C ’PY OR OAATP IZ OCO JYIYKPO
Wattiau/Akoka 121
e) Autres codes
Autres transpositions
Permutation d ’ordre d :
– le message est découpé en blocs de d lettres
auxquels on applique une transposition
– exemple :
• d=5 et on considère la matrice de transposition
suivante : 1 2 3 4 5
2 5 4 3 1
Prière de coder ce message
-> rpeiro ec ed edc re amsse g e
Wattiau/Akoka 122
f) Codage à clé unique
Principe :
– le codage et le décodage nécessitent une clé
partagée par l ’expéditeur et le destinataire
– aussi appelé codage à clé secrète ou codage
symétrique
– problème : comment transmettre la clé ?
Exemples :
– codage de César, code de Beale, grille de
Vigénère, GEDEFU18 utilisent une clé secrète
– algorithme DES
Wattiau/Akoka 123
f) Codage à clé unique
Data Encryption Standard (DES)Réponse à un appel d ’offres du National
Bureau of Standards (NBS)
Cahier des charges :
– un algorithme de cryptage,
– haut niveau de sécurité lié à une clé,
– compréhensible,
– adaptable et économique
– efficace et exportable
Résultat : IBM+National Security Agency (NSA)
Wattiau/Akoka 124
f) Codage à clé unique
Data Encryption Standard (DES)Utilisé en France aujourd ’hui par certaines
banques
réactualisé tous les cinq ans
très rapide : 1000 * RSA
principe
– combinaisons+substitutions+permutation entre
le message et la clé
– clé sur 16 bits
Cassable avec un super-calculateur
Créé en 1978 - Cassé en 1998
Wattiau/Akoka 125
f) Codage à clé unique
Data Encryption Standard (DES) Le message est partagé en blocs de 64 bits
soit L0 et R0 les moitiés gauche et droite du message
clé de longueur 56 génère 16 sous-clés k1, k2,…,k16
L1=R0 et R1=L0+f(R0,k1) - 1ère ronde
L2=R1 et R2=L1+f(R1,k2) - 2ème ronde
… L16=R15 et R16=L15+f(R15,k16) - 16ème ronde
• Remarque :
Rd=Ld-1 + f(Ld,kd)
=> Ld-1=Rd-f(Ld,kd) = Rd + f(Ld,kd)
car c ’est une addition en binaire modulo 2
où addition et soustraction sont confondues
• Intérêt : C ’est le même programme (ou carte) qui sert à
chiffrer et à déchiffrer
• f n’est pas imposée, il lui faut quelques bonnes propriétés.
Wattiau/Akoka 126
f) Codage à clé unique
IDEA International Data Encryption Algorithm
1992 => remplacer le DES
clé de 128 bits
non légal dans tous les pays
principe
– blocs de 64 bits divisés en 4 parties de 16 bits
– 8 rondes
– les sous-clés sont plus difficiles à décrypter
Wattiau/Akoka 127
f) Codage à clé unique
Modes de chiffrement par blocsValables pour DES et IDEA
définit le découpage des blocs
ECB Electronic Code BOOK :
– 8 Koctets : 1000 blocs de 8 octets=64 bits
– chaque bloc est chiffré indépendamment des
autres
– facilement contournable pour les individus
surveillant uniquement les changements dans les
informations transmises => transactions de paie
automatiques d ’un employé avec a banque
Wattiau/Akoka 128
f) Codage à clé unique
Modes de chiffrement par blocsCBC Cipher Block Chaining
– chaque bloc est additionné au résultat du
chiffrement du bloc précédent avant d ’être lui-
même chiffré
– inconvénients :
• il faut déchiffrer tout le fichier pour accéder à une
partie
• une erreur sur un bloc se répercute sur tous les suivants
– deux variantes : CFB (Cipher FeedBack et OFB
Output Feedback)
Wattiau/Akoka 129
f) Codage à clé unique
Les algorithmes à clé secrèteDES :
– le plus largement utilisé
– domaine public
3DES :
– préserve le logiciel DES mais peut utiliser 1, 2 ou
3 clés différentes
– un peu moins performant que DES, mais plus sûr
IDEA
– fonctionne aussi dans les 4 modes ECB, CBC, ..
– Breveté, requiert une licence
Wattiau/Akoka 130
f) Codage à clé unique Les algorithmes à clé secrète (suite)
Utilisés pour la confidentialité
Implémentés au niveau matériel ou logiciel
Optimisés pour chiffrer de grandes quantités
de données
Conseils :
– changer fréquemment les clés
– générer les clés de façon sécurisée
– distribuer les clés de façon sécurisée
Wattiau/Akoka 131
g) Codage par double clé
Appelé aussi cryptage asymétrique ou
cryptage par clé publique
Principe : deux clés différentes, mais
associées sont nécessaires
– une clé publique et une clé privée
– la clé publique est utilisée pour crypter
– la clé privée est utilisée pour décrypter
Si je veux recevoir des messages sécurisés, je
communique ma clé publique, je ne
communique jamais ma clé privée
Wattiau/Akoka 132
g) Codage par double clé
Si 2 personnes souhaitent communiquer de
façon sécurisée, elles doivent utiliser deux
paires de clés privée/publique
PublPrivée
1 2
1 1PublPrivée
2 2
Publ1
Publ2
Wattiau/Akoka 133
g) Codage par double clé
Version simplifiée :
– la clé publique est le produit n de deux très grands
nombres premiers p et q
– la clé privée est le couple (p,q)
Principe :
– la décomposition de très grands nombres premiers
est très longue, voire incalculable
Wattiau/Akoka 134
g) Codage par double clé
Le système RSA Créateurs : Rivest, Shamir, Adleman, 1978
Données :
– p et q 2 grands nombres premiers
– n =p*q,
– d grand et premier avec (p-1)*(q-1)
– e=inverse(d) modulo (p-1)*(q-1)
– on oublie p et q
Public : (e,n) clé publique
Chiffrement :
– si n a i chiffres, le message est découpé en paquets de (i-1) chiffres,
– chaque paquet mj est codé selon la règle : cj = mj modulo n
Décryptage :
– chaque paquet cj est décodé selon la règle : mj = cjd modulo n
Algorithme assez lent
PGP (Pretty Good Privacy): variante sur PC, diffusé gratuitement, puis
devenu payant
Wattiau/Akoka 135
g) Codage par double clé
Algorithmes à clé publiqueUtilisés à la fois pour :
– confidentialité des données :
• liée à la clé privée nécessaire pour le décryptage
– intégrité des données :
• le message ne peut être modifié par celui qui n ’a pas
la clé privée, sauf aléatoirement
– non-répudiation de l ’émetteur
• nécessite un cryptage différent
– authentification de l ’émetteur
• nécessite un cryptage différent
Wattiau/Akoka 136
g) Codage par double clé Non-répudiation et authentification par clé publique
Les 2 personnes s’échangent leurs clés
publiques
L’émetteur écrit un message et utilise sa clé
privée pour le crypter
Il envoie ses données cryptées au destinataire
A réception, le destinataire utilise la clé
publique de l’émetteur pour le décrypter
L’émetteur ne peut nier avoir envoyé lui-
même ce message, sauf si sa clé a été
compromise.
Wattiau/Akoka 137
g) Codage par double clé
Cryptage double avec clé double
Si l’on veut à la fois intégrité, confidentialité,
non-répudiation et authentification, il faut
mettre en œuvre un cryptage double :
– A crypte son message avec la clé publique de B
– A crypte une seconde fois le message avec sa clé
privée
– A est authentifié et seul B peut décrypter
Wattiau/Akoka 138
g) Codage par double clé
Algorithmes à clé publique
Moins performants
Rarement utilisés pour la confidentialité
Utilisés pour :
– l ’authentification avec signatures numériques,
– la gestion des clés
Wattiau/Akoka 139
h) Codage par hachage
Une fonction de hachage transforme un
message de longueur aléatoire en un code
longueur fixe, appelé condensé de message
Algorithme de hachage :
– cohérent (un même message doit toujours
produire un même résultat),
– unique (pas le même condensé, pour 2
messages différents),
– non réversible ou difficilement.
Wattiau/Akoka 140
h) Codage par hachage
UtilisationPour assurer l’intégrité et l’authenticité
d ’un message :
– A écrit un message et calcule sa fonction de
hachage
– A envoie le message et sa fonction de hachage,
comme empreinte à B.
Problème :
– l’empreinte peut être contrefaite : attaque par
hôte interposé (MITM-Man In The Middle)
Wattiau/Akoka 141
i) Signatures numériques
Combinent l’utilisation du cryptage à clé publique
et une fonction de hachage non réversible
Principe :
– A crée une paire de clés publique/privée
– A transmet sa clé publique à B
– A calcule le condensé C de son message
– C est crypté avec la clé privée de l ’émetteur, donnant S
signature digitale
– A envoie son message à B + sa signature S
Wattiau/Akoka 142
i) Signatures numériques
Vérification par B :
– B sépare le message de la signature
– B utilise la clé publique de A pour décrypter la
signature S et obtenir C, condensé de message original
– B soumet le message reçu à la fonction de hachage et
compare le résultat avec C
– si OK, on a assuré l ’intégrité et l ’authentification
– N’assure pas la confidentialité du contenu du message
Wattiau/Akoka 143
j) Gestion des clés
Problèmes :
– Humain : cupidité, colère ou manque de sérieux
peuvent compromettre la sécurité des clés
– Technique : fournir une méthode sûre de
création et de distribution des clés
Wattiau/Akoka 144
j) Gestion des clés
Modèle de distribution centralisée
S’appuie sur une partie tierce, le centre de
distribution de clés (CDC), qui délivre les
clés de session aux entités communicantes
Requiert que toutes les parties
communicantes disposent d’une clé secrète
partagée pour dialoguer avec le CDC ->
distribution manuelle
Wattiau/Akoka 145
j) Gestion des clés
Algorithme de création de clésDiffie-Hellman
Permet à deux parties de créer une clé
secrète partagée connue d’eux seules, même
si elle circule via une liaison non sécuriséeA transmet deux grands nombres p et q à B
A choisit au hasard un grand entier x1 et calcule
y1 = qx1 modulo p
B choisit au hasard un grand entier x2 et calcule
y2 = qx2 modulo p
A envoie y1 à B et B envoie y2 à A
A calcule Z = (y2)x1 modulo p
B calcule Z’ = (y1)x2 modulo p
Z = Z’ = qx1x2 modulo p est la clé secrète partagée
Wattiau/Akoka 146
j) Gestion des clés
Algorithme de Diffie-HellmanL’espion doit :
– trouver x1 à partir de qx1
• Calcul de logarithme discret
– factoriser de grands nombres premiers
• p et q grands nombres premiers
Associé à un algorithme de cryptage à clé publique pour :
– L’authentification
– Et l’intégrité
Wattiau/Akoka 147
Message
–signé numériquement,
–avec la clé privée d’une partie tierce de
confiance,
–confirme l’appartenance d’une clé publique
spécifique à une personne ou entité donnée,
–Standard X.509
k) Certificat numérique
Wattiau/Akoka 148
k) Certificat numérique
Autorité de certification (AC) Partie tierce de confiance qui se porte
garante de la validité de certificats
numériques
B demande à AC de lui fournir un
certificat numérique de A
AC envoie le certificat de A, que AC a
signé avec sa clé privée
B reçoit le certificat de A et vérifie la
signature de AC
Comme le certificat contient la clé publique de A, B
a de façon sûre une version authentifiée de cette clé
Wattiau/Akoka 149
l) Tiers de confiance
ou système de séquestreEntité à laquelle est confiée une clé secrète
confidentielle ou une clé privée pour
répondre en cas de :
– Perte
– Altération
De cette clé par son détenteur
