Informations générales

„ Laurence Herbiet
Introduction à la ‰ Institut de mathématique (B37) – 0/8
04/366.26.02
cryptographie ‰

‰ [Link]@[Link]
‰ [Link]

1 Cryptographie - 2

1 2
Organisation du cours Références
„ Organisation : „ Cryptography : Theory and practice (2e edition) –
Douglas Stinson – CRC Press, 2002 – [Stinson]
‰ Cryptographie (± 7 semaines) – L. Herbiet
‰ Systèmes d’exploitation – T.A. Banh „ Cryptography and Network Security (3e edition) –
William Stallings – Prentice Hall,2002 – [Stallings]
„ Examen :
„ Les protocoles de sécurité d’internet –
‰ Cryptographie (50%) : Une question parmi les questions
Stephane Natkin – Dunod, 2001 – [Natkin]
proposées sur le site du cours
‰ Systèmes d’exploitation (50%) : „ Applied Cryptography -
„ Soit un travail sur un sujet relatif aux O.S. (voir Mr Banh) B. Schneier- John Wiley & Sons, 1996
„ Soit une des questions parmi la liste des questions proposées sur
le site du cours „ Tutoriel simple de cryptographie : [Link]

Cryptographie - 3 Cryptographie - 4

3 4
Cryptographie Programme
„ Cryptographie :
‰ Cryptographie classique
‰ Rappels mathématiques
‰ Chiffrement symétrique/asymétrique – hashage

„ Protocoles de sécurité
‰ SSL, IPSEC, SET, PGP
‰ Systèmes sécurisés
‰ …

Cryptographie - 5 Cryptographie - 6

5 6
 Besoin en sécurité de l’information

Introduction „ Utilisation répandue du matériel informatique

→ sécurité informatique

„ Utilisation répandue des réseaux informatiques

et des systèmes distribués
→ sécurité réseau
Motivation

7 Cryptographie - 8

7 8
Menaces réseau Menaces réseau (2)

actives passives

interception Interruption Fabrication

(disponibilité) (authenticité)

Contenu de Analyse
message de traffic Modification
(intégrité)

Cryptographie - 9 Cryptographie - 10

9 10
Attaqueurs potentiels Services de sécurité attendus
Protection des données
„ Les hackers
„ Les concurrents industriels
Au repos En transit
„ Les espions
• contrôle d’accès • confidentialité
„ La presse
• identification • intégrité
„ Les agences nationales • autorisation • authentification
„ … • audit • non répudiation
• disponibilité

Cryptographie - 11 Cryptographie - 12

11 12
Identification (authentification utilisateur) Services de base
Sur base de
„ Ce que vous savez
‰ Mots de passe, PINs, …

„ Ce que vous avez

‰ Carte magnétique, carte à puces, …

„ Ce que vous êtes

‰ Empreintes digitales, voix, signatures, scanner rétinien,
…

Cryptographie - 13 Cryptographie - 14

13 14
Services de base (2) Signatures manuelles et digitales
„ Points communs

Signatures digitales Signatures manuelles

1. unique
2. Impossible à forger
3. impossible à répudier de la part de son auteur
4. facile à vérifier par un tiers
„ But principal :
‰ Identification unique 5. facile à générer
‰ preuve d'accord sur le contenu du document

Cryptographie - 15 Cryptographie - 16

15 16
Signatures manuelles et digitales Relations entre ces services
„ Différences
Signatures digitales Signatures manuelles
6. Possibilité de la stocker et de 6. associée physiquement avec le Non répudiation
l’envoyer indépendamment du document
document Authentification
7. identique pour tous les
7. fonction du document documents confidentialité Intégrité
8. couvre l’entièreté du 8. habituellement à la dernière
document page

Cryptographie - 17 Cryptographie - 18

17 18
 Vocabulaire de base
„ Cryptologie = cryptographie + cryptanalyse
„ Chiffrement, déchiffrement, décryptement

Introduction Clé de chiffrement Clé de déchiffrement

Texte en Texte chiffré ou

chiffrement chiffrement Texte en clair
clair cryptogramme

chiffrement
Vocabulaire de base
Texte en clair
et/ou clef

Cryptographie - 20

19 La cryptologie est une science mathématique qui comporte 2 branches : la

cryptographie et la cryptanalyse.
La cryptographie traditionnelle est l’étude des méthodes permettant de
transmettre des données de manière confidentielle. Afin de protéger un
message, on lui applique une transformation qui le rend incompréhensible;
c’est ce qu’on appelle le chiffrement, qui, à partir d’un texte clair, donne un
texte chiffré ou cryptogramme. Inversement, le déchiffrement est l’action
qui permet de reconstruire le texte en clair à partir du texte chiffré. Dans la
cryptographie moderne, les transformations en question sont des fonctions
mathématiques, appelées algorithmes cryptographiques, qui dépendent
d’un paramètre appelé clef.
La cryptanalyse, à l’inverse est l’étude des procédés cryptographiques dans
le bute de trouver des faiblesses et, en particulier, de pouvoir décrypter des
textes chiffrés. Le décryptement est l’action consistant à retrouver le texte
clair sans connaître la clef de déchiffrement.

Note : les termes « cryptage » et « crypter » sont des anglicismes, dérivés de

l’anglais to encrypt, souvent employés incorrectement à la place de
chiffrement et chiffrer.

19 20
Notation Algorithme - clé

„ M : texte clair „ Les opérations de chiffrement/déchiffrement sont

„ C : texte chiffré basées sur deux éléments fondamentaux:
‰ Un algorithme cryptographique qui est une fonction
„ K : clé mathématique réalisant ces 2 opérations.
„ E(x) : fonction de chiffrement ‰ Une Clé.

„ D(x) : fonction de déchiffrement appliqués au texte à transformer.

„ Il faut évidemment :
M = D(E(M))

Cryptographie - 21 Cryptographie - 22

21 22
 Principe de Kerckhoff Cryptosystème
„ Remarques importantes:
‰ Aucun secret ne doit résider dans l'algorithme (principe
Un cryptosystème est
de Kerckhoff)
défini comme l'ensemble
Tout le secret réside dans la clé !
des clés possibles (espace
‰ Il convient de distinguer Secret et Robustesse de de clés), des textes clairs
l'algorithme.
et chiffrés possibles
→ Sans K, impossible de retrouver M à partir de C associés à un algorithme
donné.
→ Si on connaît K, déchiffrement

Cryptographie - 23 Cryptographie - 24

Le principe de Kerckhoff :
« La sécurité d'un chiffre NE DOIT PAS dépendre
de tout ce qui ne peut pas être facilement changé »
A. Kerckhoff, 1883

23 24
Cryptosystème (définition) Algorithme publié vs secret
Algorithme publié Algorithme secret
1. La seule manière fiable 1. La cryptanalyse doit inclure la
d'évaluer la sécurité du chiffre récupération de l'algorithme
2. empêche des backdoors 2. Un plus petit nombre
cachées par les concepteurs d'utilisateurs = une plus petite
3. Grand nombre des réalisations motivation à casser
= prix réduit + performance 3. Indisponible pour autre pays
élevée
4. Aucun besoin de protection
contre le reverse-engineering
5. Implémentations logicielles
6. Standardisation locale et
internationale

Cryptographie - 25 Cryptographie - 26

25 26
Idée fondamentale de cryptographie Solution logicielle ou matérielle ?

Si un bon nombre de gens futés n'ont pas résolu

un problème, alors il ne sera probablement pas
résolu de si tôt

Cryptographie - 27 Cryptographie - 28

Hardware :
•Puce VLSI
•Carte PCMCIA
•Carte à puce
•Carte cryptographique
•dispositif cryptographique autonome

Types d’applications logicielles Types d’applications hardware :

•Accélérateurs de matériel pour des
gateways ou des routeurs
•Communication sans fil
•Carte à puce universelle pour le commerce
électronique
•Valise électronique
•Autorité de certification – centre
d’enregistrement des clés publiques
•Dispositifs militaires
•Dispositifs de haute sécurité

27 28
Croissance d’utilisation de produits Produits cryptographiques hors USA
cryptographiques

Cryptographie - 29 Cryptographie - 30

29 30
 Cryptosystèmes à clés symétriques
„ Caractéristiques:
Introduction ‰ Clés identiques: KE=KD=K
‰ Clé secrète!
‰ Algorithmes standards: DES, AES, …
‰ Génération des clés: Clé choisie aléatoirement dans
l'espace de clés.
Concepts cryptographiques
Clé de chiffrement Clé de déchiffrement

Texte en Texte chiffré ou

chiffrement chiffrement Texte en clair
clair cryptogramme

31 Cryptographie - 32

Suivant la nature des clés et de l'algo, on distingue deux grandes

familles de cryptosystèmes:
•Cryptosystèmes à clés symétriques
•Cryptosystèmes à clés publiques

31 32
Cryptosystèmes à clés symétriques Distribution des clés
„ Caractéristiques (suite):
‰ Principe: Algorithmes basés sur des opérations de
transposition et de substitution des bits du texte clair, en
fonction de la clé.
‰ Taille des clés: (standard) 64 ou 128 bits.
‰ Performances: Chiffrement très rapide.
‰ Distribution des clés:
„ Opération critique.
„ Doit s'effectuer de manière sécurisée (voir manuellement).

Cryptographie - 33 Cryptographie - 34

33 34
Cryptosystèmes à clés publiques Cryptosystèmes à clés publiques
„ Caractéristiques (suite):
„ Caractéristiques:
‰ 1 Clé publique: PK ‰ Principe:
„ Fonction unidirectionnelle à trappe.
‰ 1 Clé privée: SK (secrète)
‰ "Facile" à calculer dans un sens. "Difficile" à inverser.
‰ Propriétés: ‰ Sauf si on connaît une info secrète (la trappe)
„ La connaissance de PK ne permet pas de déduire SK. „ Algorithmes basés sur des opérations d'exponentiation en algèbre
„ modulo.
‰ Algorithmes standards: RSA, DH ‰ Exemple : f := Y = f(X) = AX mod P
„ Où A et P sont constants, P est un grand nombre premier et A est un entier plus
Clé de déchiffrement petit que P
Clé de chiffrement

Texte en Texte chiffré ou

chiffrement chiffrement Texte en clair
clair cryptogramme

Cryptographie - 35 Cryptographie - 36

TRAPPES
Il existe parfois ce que l'on nomme des "trappes" dans le clés publiques et
secrètes. Ceci est du au fait que lors de la génération de la clé, qui doit se faire
aléatoirement en respectant certaines contraintes théoriques prédéfinies, le
générateur aléatoire a un défaut (parfois le défaut est volontaire de la part du
fournisseur… espionnage oblige).
Dans les clés secrètes, les trappes se situent au niveau de l'entropie de la clé,
directement liée à l'entropie du générateur aléatoire. On définit l'entropie d'un
générateur de clés par le nombre moyen optimal de questions binaires (c'est-à-
dire donnant lieu à des réponses du type oui/non) qu'il faut poser à quelqu'un
connaissant une clé produite par ce générateur, pour la déterminer. Plus
l'entropie d'un générateur de clé est élevée, plus il faut de questions pour
déterminer cette clé. A l'inverse, plus l'entropie est faible, moins il faut de
questions, de sorte que la recherche d'une clé est facilitée. L'entropie d'un
générateur de clés de n bits n'excédera donc jamais n mais pourra cependant y
être inférieure.
L'introduction de trappes dans les clés de systèmes asymétriques est beaucoup
plus difficile, puisque ce type de clé possède déjà une structure mathématique
intrinsèque: leur constructions n'est pas due au hasard, mais résulte de règles
mathématiques. Le hasard est ici dans le choix des grands nombres premiers
utilisés. Si le générateur aléatoire qui engendre ces nombres est biaisé (voir la
définition de ce terme dans la section probabilités du site), ce biais facilitera la
recherche des nombres premiers ayant servi à l'élaboration de la clé qu'un
attaquent tente de casser.

35 36
Cryptosystèmes à clés publiques Algorithmes de hashage
„ Caractéristiques (suite): „ 3ème grande famille d'algorithmes utilisés en
‰ Génération des clés: cryptographie.
„ A partir de grands nombres premiers PK = f(SK) mais le calcul de
SK = f-1(PK) est impossible. „ Principe:
‰ Taille des clés: (standard) 512 ou 1024 bits. ‰ Ces algorithmes convertissent un texte original de
‰ Performances: Chiffrement de l'ordre de 1000 fois plus longueur quelconque en un message de longueur fixe
lent que les algorithmes à clés symétriques. (en général de longueur inférieure).
‰ Nombre de clés: (si n entités) : n paires.
„ Utilisation en cryptographie.
‰ Distribution des clés:
Facilitée car pas d'échange de clés secrètes nécessaires: ‰ Le but est d'utiliser le message haché comme empreinte
- La clé secrète est conservée par les entités. digitale du message original qu'il identifie de manière
- Seule la clé publique est échangée. univoque.

Cryptographie - 37 Cryptographie - 38

37 38
Algorithmes de hashage Protocoles cryptographiques
„ A cet effet, on utilise des algorithmes de hashage: „ Dès que plusieurs entités sont impliquées dans un
‰ Unidirectionnels - Sans collisions
échange de messages sécurisés, des règles
‰ En effet, il est pratiquement impossible :
doivent déterminer l'ensemble des opérations
Etant donné De trouver cryptographiques à réaliser, leur séquence, afin de
H(m) m sécuriser la communication
H(m) et m m’ ≠ m tel que „ C'est ce que l'on appelle les protocoles
h(m’) = h(m) cryptographiques.

m’ ≠ m tel que „ Que signifie sécuriser un échange?

h(m’) = h(m) ‰ Les 3 propriétés fondamentales sont:
Confidentialité – Authentification – Intégrité

Cryptographie - 39 Cryptographie - 40

39 40
Protocoles cryptographiques Confidentialité – système symétrique
„ Confidentialité
‰ A l'aide de cryptosystèmes à clés symétriques.
„ La même clé secrète est utilisée pour E(M) et D(C) A B
„ Echange préalable et sécurisé de la clé K entre A et B. Clé de Clé de
‰ A l'aide de cryptosystèmes à clés publiques. Chiffrement Déchiffrement
K K
„ Chaque entité possède sa paire de clés PKA, SKA/ PKB, SKB.
‰ A l'aide de cryptosystèmes hybrides.
M C Confidentialité C M
„ Cryptosystème à clés publiques pour l'échange
confidentiel de la clé (de session) K. Algo. Algo.
„ Cryptosystème à clés symétriques pour l'échange
confidentiel du message.

Cryptographie - 41 Cryptographie - 42

41 42
 Confidentialité – système asymétrique Confidentialité – système hybride
A B
Génération de K
A B
Clé de PKB SKB
Clé de
Déchiffrement
Chiffrement
SKB K PKB(K) Confidentialité PKB(K) K
PKB
Algo. Algo.

M C Confidentialité C M K K
Algo. Algo.
M C Confidentialité C M
Algo. Algo.

Cryptographie - 43 Cryptographie - 44

Idée : chiffrer avec la clé publique de B ainsi seul B peut déchiffrer le Hybride : les systèmes asymétriques sont très lourds et très lents
message. même si ce sont les plus sûrs. L’idée est d’échanger une clé de
session (symétrique) par le biais d’un échange asymétrique. Ensuite,
on continue les communications avec cette clé de session.

43 44
Avantages d’un système hybride Protocoles cryptographiques
„ Intégrité du message.
logiciel matériel
‰ Vérification qu ’un message n ’a pas été altéré
durant la communication.
Vitesse de déchiffrement du 3DES ‰ A cette fin, on utilise les fonctions de hashage.
' 100 ' 1000
Vitesse de déchiffrement du RSA-1024
A B
M ENVOYE M
SEPAREMENT

Hash
M
Hash
Hash
H(M)
Hash Hash
H(M) Intégrité
H(M) ?=?

Cryptographie - 45 Cryptographie - 46

45 46
Protocoles cryptographiques Authentification des parties - symétrique
„ Authentification.
‰ Des parties de la communication. A RA
B
„ A l ’aide d’un cryptosystème à clés symétriques. Génération RA EK (RA, B)
‰ Si on suppose que A et B partagent une même clé secrète K ?=? EK (RA, B) ;
„ A l ’aide d’un cryptosystème à clés publiques. DK(EK (RA, B)) RB
Génération RB
‰ Chaque partie possède une paire de clés publique/privée
(PKA/SKA, PKB/SKB). ?=?
EK (RB, A)
EK (RB, A) DK(EK (RB, A))

Cryptographie - 47 Cryptographie - 48

47 48
Authentification des parties - symétrique Protocoles cryptographiques
„ Authentification (suite).
‰ Du message.
A B „ A l’aide d’un MAC (Message Authentication Code).
Clé de ‰ Un MAC peut-être généré de deux manières:
Clé de
Déchiffrement
Chiffrement ƒ A l ’aide d ’un cryptosystème symétrique.
PKA
SKA ƒ A l ’aide d ’une fonction de hashage.

A C A C C A
Algo. Algo. ?=?
A
Authenticité

Cryptographie - 49 Cryptographie - 50

49 50
Authentification message – MAC – Sym. Authentification message – MAC – Hash
A B A B
M M
M K M K

K K
Algo. Algo. Hash Hash

C MAC M MAC
M MAC
C MAC
MAC
MAC ?=? MAC ?=?
MAC = derniers digits de C MAC

Une clé secrète K est partagée entre A et B

Authentification grâce à K + Intégrité

Authentification grâce à K + Intégrité

Cryptographie - 51 Cryptographie - 52

51 52
 Protocoles cryptographiques Signature digitales avec clé publique
„ Authentification (suite). A B
M
‰ Du message. M

„ A l ’aide d’un MAC (Message Authentication Code). Hash

Hash

„ A l ’aide d’une signature digitale. Hash

Hash
H(M)
‰ Les signatures digitales doivent posséder les propriétés suivantes: H(M)
Hash
?=?
H(M)
1. Authentique.; SKA
2. Infalsifiable;
Algo.
3. Non-réutilisable; PKA
Algo.
M Sign
4. Inaltérable; Sign.
Sign
5. Non-répudiable.

Seul A a pu composer Sign

Cryptographie - 53 Cryptographie - 54

Avec un système symétrique :

Les deux côtés correspondants ont la même information et

peuvent produire une signature

→ Il y a une possibilité pour

Le récepteur de falsifier le message
L’expéditeur de nier qu’ il/elle a envoyé le message

53 54
Protocoles cryptographiques Cryptanalyse
„ Authentification+Confidentialité
A B „ Etude des mécanismes théoriques ou techniques
M M visant à briser un algorithme de chiffrement.
SKA Hash
C’est à dire, retrouver le message M à partir de C,
Hash

H(M) sans connaître la clé K à priori.

H(M) ?=?
Algo. H(M)
„ On parle dans ce cas d’une “attaque”
M Sign Sign. M Sign
cryptanalytique.
C PKA
K C C
Algo.
K

Cryptographie - 55 Cryptographie - 56

55 56
Cryptanalyse des systèmes symétriques Cryptanalyse des systèmes symétriques
1. Attaque sur le texte chiffré uniquement 2. Attaque sur le texte clair connu
‰ Etant donné ‰ Etant donné
„ Un texte chiffré „ Un texte chiffré
‰ On recherche „ Un fragment deviné de texte clair
„ Le texte clair et/ou ‰ On recherche
„ La clé „ Le texte clair restant
‰ Technique „ Et/ou la clé
„ Analyse de fréquence des lettres dans le message ‰ Technique
(présence de ‘e’, …) „ Attaque par ‘force brute’ :
„ Ne fonctionne que pour la plupart des chiffrements classiques de on essaie toutes les clés
base

Cryptographie - 57 Cryptographie - 58

57 58
Performances Cryptanalyse des systèmes symétriques
3. Attaque sur un texte
clair sélectionné
‰ Etant donné
„ La capacité de chiffrer un
fragment de texte clair
choisi arbitrairement
‰ On recherche
„ La clé
‰ Technique
„ Cryptanalyse différentielle

Cryptographie - 59 Cryptographie - 60

59 60
Cryptanalyse des systèmes symétriques Évolution de la cryptologie
4. Attaque sur un texte
chiffré sélectionné
‰ Etant donné
„ La capacité de déchiffrer
un fragment de texte
chiffré choisi
arbitrairement
‰ On recherche
„ La clé

Cryptographie - 61 Cryptographie - 62

61 62