Cryptographie

Cryptographie

Atindehou Mêton-Mêton

August 3, 2023
Plan
1. Introduction générale

2. Bases de la cryptographie

3. Cryptographie symétrique

4. Cryptographie asymétrique

5. Fonctions de hachage

6. Signature électronique

7. Générateurs de suites aléatoires

8. Logiciels de sécurité informatique

9. Cryptanalyse
Plan : 1 - Introduction générale

1.1 Objectifs du cours

1.2 Historique de la cryptographie
1.3 Présentation de la cryptographie moderne
1.4 Terminologie

2
Objectifs du cours
 Contenu du cours :
1. Introduction et historique
2. Bases de la cryptographie
3. Cryptographie symétrique
4. Cryptographie asymétrique
5. Fonctions de hachage
6. Signature électronique
7. Générateurs de suites aléatoires
8. La gestion des clefs en cryptographie
9. Cryptanalyse
10. Utilisation d’un cryptosystème libre : PGP
 Ce cours doit permettre :

De mettre en application la théorie des systèmes de

chiffrement modernes, symétriques ou asymétriques.

Histoire de la cryptographie
 ISÈRE Laboratoire de

Cry
Mathématiques
UMR 5582

pto
CNRS-UJF

de laie
lo gie
oire h
Hist tograp
Arthur Scherbius développe la machine à chiffrer
Enigma, qui sera utilisée par l'Allemagne nazie

cryp
pendant la seconde guerre mondiale Stephen Wiesner jette les bases
d'une cryptographie quantique
Dans son Traicté des 1919 en inventant le principe d'une
chiffres ou secretes manières monnaie quantique
1970
d'escrire, Blaise de Vigenère
publie la méthode de chiffrement Horst Feistel développe
de substitution polyalphabétique le chiffre Lucifer chez IBM
qui conservera son nom
Léon Battista Alberti, grand Le WEP est adopté pour le chiffrement
1999
philosophe et écrivain de la des communications wifi
César utilise plusieurs chiffres, dont un 1586
renaissance, publie De
L'atbash est utilisé dans chiffre de substitution par décalage Componendis Cyphris,
l'ancien testament, connu aujourd'hui comme le chiffre de César premier ouvrage occidental Charles Bennett et Gilles Brassard
Joseph Mauborgne
notamment le livre de de cryptographie. Il invente réalisent la première expérience de
et Gilbert Vernam
Jérémie le cadran chiffrant et, pour la cryptographie quantique
inventent le masque
-50 première fois, propose un jetable système incon- 1976
1988
-600 -404 1467 1918
chiffre de substitution ditionnellement sûr
polyalphabétique
La machine de Lorenz
Le chiffre ADFGVX est inventé est utilisée pour chiffrer Le WPA2 est la nouvelle norme pour le chiffrement
par Fritz Nebel, colonel Allemand. les communications entre des communications wifi. Il pallie les faiblesses du WEP
les hauts dirigeants 2004
Selon Plutarque, C'est un chiffre qui mêle allemands
Lysandre de Sparte Le manuel du secrétaire, substitution et transposition 1939 1945
fait usage de la scytale, Adab-al-Kuttab contient Echange de clef de
Diffie et Hellman Nouveau standard de cryptographie, AES fondé
un chiffre de transposition une partie consacrée à la
sur l'algorithme Rijndael pour pallier les faiblesses de DES
cryptographie
Les Rossignol père et fils mettent au point
le grand chiffre, au service de Louis XIV 1984 2001

-400 0
Naissance de DES, premier standard Tahar Elgamal propose
Une des plus anciennes descriptions connues
de cryptographie, fondé sur Lucifer un cryptosystème fondé
de chiffre de substitution monoalphabétique
sur l'échange de clefs de
se trouve dans le Kâmasûtra, qui recommandait
Diffie-Hellman et le
aux femmes de chiffrer leur correspondance
logarithme discret
afin de cacher leurs liaisons

1991
Au MIT, Ron Rivest, Adi Shamir et
Leonard Adleman créent le cryptosystème
10è RSA, algorithme de chiffrement à clef publique
siècle
17 è

siècle Phil Zimmerman publie PGP, un logiciel

ouvert de chiffrement grand public utilisant
les meilleurs algorithmes
1977
Ronald Rivest crée MD5, une fonction de
hachage cryptographique encore très utilisée

ses
Le lieutenant Georges Painvin
casse le chiffre allemand ADFGVX

tanaly
et contribue ainsi à la victoire française

Les cryp
Une faille est découverte dans MD5
1918
1996

es
célèbr
Scott Fluhrer, Itsik Mantin et
Adi Shamir démontrent la faiblesse du WEP
9è
siècle 1586 1893 1942 2001

Al Kindi publie le premier ouvrage connu Procès du Complot de Babington. Francis Etienne de Bazeries Le chiffrement de Lorenz est cassé par les
de cryptanalyse, Manuscrit sur le déchiffrement Walsingham, chef de l'espionnage anglais sous cryptanalyse le cryptanalystes de Bletchley Park, avec l'aide
des messages cryptographiques, qui présente Elisabeth I parvient à décrypter les messages grand chiffre du Colossus, le premier ordinateur électronique
l'analyse des fréquences échangés entre Marie Stuart, reine d'Ecosse, numérique
et les comploteurs, prouvant ainsi sa 1939 1945 Lars Lydersen, Carlos Wiechers, Christoffer Wittmann,
culpabilité. Elle fut décapitée Dominique Elser, Johannes Skaar et Vadim Makarov
La Electronic Frontier Foundation parviennent à craquer les détecteurs commerciaux utilisés
Babbage, puis Kasiski cassent le chiffre de Vigenère casse DES par force brute en 2 jours pour la cryptographie quantique.

0 lan Turing et Dilly Knox améliorent

le fonctionnement des machines
polonaises, puis Turing attaque 1998 2010
l'Enigma navale

1854
1863

Les mathématiciens polonais

Marian Rejewski, Jerzy Różycki
et Henryk Zygalski attaquent
avec succès une première
version d'Enigma, et créent la
première bombe cryptologique

1933

te
Contex 9è 15è
18è siècle 19è siècle
1939 1945
1947

-400
siècle siècle

Développement du télégraphe Seconde

Invention du transistor
Apogée de la civilisation arabo-musulmane Renaissance optique, puis électrique, Guerre
Guerres entre les grecs et les perses mondiale
sous la dynastie des Abbassides en Europe puis sans fil (la TSF)
1914 1918 Premier ordinateur IBM

1953
Première Guerre
mondiale

APPLIC
ATIONS

SECURITE
www
LOG

Graphisme : Fanny BASTIEN (CNRS)

€€
€€

https://www-fourier.ujf-grenoble.fr/∼rossigno/Vulgarisation/vulg_files/poster_fds2012.pdf
Quelques étapes historiques
Le scytale grec (-400) : bâton de diamètre déterminé autour duquel
s’enroule une bande de cuir
Le code de César (-100) : substitution mono-alphabétique
le premier manuscrit de cryptanalyse du savant arabe Al-Kindi (900)
Les bombes électromécaniques d’Alan Turing
Le code Navajo : protection des échange radio Américain lors de la
guerre contre le Japon
Les travaux fondateurs de la cryptographie moderne de Claude
Shannon en 1945 : Objectifs de la cryptographie
▶ Secret
▶ Authentification
Voir également :
https://fr.wikipedia.org/wiki/Histoire_de_la_cryptologie
https://www.maths.univ-evry.fr/pages_perso/bayad/Enseignement/Polycopie_crypto-
2008.pdf
http://david.carella.free.fr/fr/cryptographie/principes-de-base.html

8
Présentation de la cryptographie “moderne”
Définition

La cryptographie est la science qui permet d’assurer la con-

fidentialité de communications transmises sur un canal
public où est potentiellement présent des adversaires.

Confidentialité : moyen de garantir la non accessibilité du contenu

d’une communication aux tiers
Adversaires : Passif (écoute) ou actif (écoute, altère)

Elle doit donc également permettre d’assurer

Intégrité : moyen de garantir que le contenu d’un fichier n’a pas été
altéré
Authenticité : moyen de garantir l’origine d’une communication ou
d’un fichier
Non-répudiation : moyen de garantir que le signataire ne peut pas
renier sa signature

Source : https://www.irisa.fr/prive/sgambs/intro.pdf 10
Utilité pour sécuriser la transmission de données

Au moins quatre1 grandes familles

1. Signature asymétrique
2. Chiffrement asymétrique
3. Contrôle d’intégrité par hachage
4. Chiffrement symétrique
(Nous les verrons plus en détails dans la suite du cours)

1 Mensuel La Recherche N°420 de juin 2008, www.larecherche.fr

11
Signature asymétrique

Exemples :
▶ Authentification de carte de banque
▶ Authentification sur internet
▶ Mise à jour de logiciel
Algorithmes en jeu :
▶ RSA (factorisation d’entiers)
▶ Courbes elliptiques
▶ ELGamal (logarithme discret), etc

12
Chiffrement asymétrique

Exemples :
▶ Ouverture d’un canal sécurisé sur internet
▶ Chiffrement des courriers électroniques,
▶ Futur de la télévision à péage
Algorithmes en jeu :
▶ RSA
▶ Courbes elliptiques
▶ Elgamal, ...
13
Contrôle d’intégrité par hachage

Exemples :
▶ Téléchargement de logiciel
▶ Paiement par carte
▶ Téléphonie, télévision, ...
Algorithmes en jeu :
▶ Fonctions de hachage
14
Chiffrement symétrique

Exemples :
▶ Protection des communications téléphoniques
▶ Transmissions sécurisées sur internet
▶ Chiffrement des télévisions à péage, DVD, ...
Algorithmes en jeu :
▶ AES,
▶ 3DES (algorithmes de permutations et de transformations de blocs
de bits), etc

15
Terminologie
 Chiffrement transformation d’un texte clair en texte chiffré. Nécessite
l’utilisation d’une clé
Chiffre Algorithme permettant de transformer un texte clair en un
texte chiffré
Chiffrer Transformer un message de manière qu’il ne soit plus
lisible qu’à partir d’une clé
Clef Dans un système de chiffrement, donnée nécéssaire au
fonctionnement des chiffres
Cryptogramme Message chiffré ou codé
Décrypter Transformer un cryptogramme en texte clair, sans la clé
Cryptologie Cryptographie et cryptanalyse
Cryptanalyse Science de l’analyse des cryptogrammes pour les décrypter
Source :
https://www.tala-informatique.fr/wiki/images/e/eb/Cryptographie.pdf

17
Logiciels autour de la sécurité informatique
Logiciel à installer pgp :
Lien de téléchargement :
https://www.gnupg.org/%28fr%29/download/index.html
Presentation succincte :
https://mbourgeois.developpez.com/articles/securite/pgp/#LIV-A

Exercice à rendre :
Quelles fonctionnalités offrent chacun des logiciels :
aircrack-ng,
Ophcrack,
Kali Linux,
RainbowCrack
John the Ripper,
Wireshark,
tcpdump.
18
Plan : 2 - Bases de la cryptographie

2.1 Composantes d’un système cryptographique

2.2 Chiffrement avec des clés secrètes
2.3 Modèle théorique de chiffrement

19
Objectifs de la cryptographie moderne

A cause de l’utilisation d’un canal de communication non sécurisé,

La cryptographie moderne doit permettre d’assurer :
1. La confidentialité des communications
2. L’intégrité des messages
3. L’authenticité des messages
4. La non répudiation

20
Services de la cryptographie moderne
Pour sécuriser la transmission de données
Au moins quatre grandes familles
1. Signature asymétrique
2. Chiffrement asymétrique
3. Contrôle d’intégrité par hachage
4. Chiffrement symétrique

21
Composantes d’un système cryptographique
Composantes d’un système cryptographique

1. Humains (utilisation)

2. Matériel (implantation)

3. Législation (cadre juridique légal)

4. Protocoles (modèles de fonctionnement)

▶ Codes
▶ Primitives cryptographiques

23
Primitives cryptographiques

Plaintext : Message clair Cipher text : Message chiffré

Ciphers : Chiffres Block ciphers : Chiffrement par blocs
Stream ciphers : Chiffrement à flot One-way functions : Fonctions à sens unique
Encrypt : Chiffrer Encryption : Chiffrement
Decrypt : Déchiffrer Decryption : Déchiffrement
Hash functions : Fonctions de hachage Digest : Haché
24
Primitives de chiffrement

1. Chiffrement symétrique
▶ Par blocs : AES, DES, 3DES, RC5, RC6, Lucifer
▶ Par flux : RC4, A5/1, A5/2, LEVIATHAN

2. Chiffrement asymétrique
▶ Problèmes difficiles : Théorie des nombres, codes
▶ Algorithmes : RSA, ELGamal, Diffie-Hellman
▶ Protocoles : SSH, GPG, BITCOIN, TLS

25
Chiffrement avec des clés secrètes
Historiquement

Message chiffré = fonction mathématique(Message clair, clé)

fonction mathématique : gardée secrète

clé : gardée sécrète

Problèmes, que ce passe-t’il si :

La fonction mathématique est livrée à l’adversaire
Il est possible de retrouver la fonction par analyse des chiffrés

27
Notion de clé : Desiderata de Kerckhoffs
Pour qu’un système puisse assurer en un temps illimité des
communications secrètes, il faut que :
1. Le système doit être matériellement, sinon mathématiquement
indéchiffrable ;
2. Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient
tomber entre les mains de l’ennemi ;
3. La clef doit pouvoir en être communiquée et retenue sans le secours
de notes écrites, et être changée ou modifiée au gré des
correspondants ;
4. Il faut qu’il soit applicable à la correspondance télégraphique ;
5. Il faut qu’il soit portatif, et que son maniement ou son
fonctionnement n’exige pas le concours de plusieurs personnes ;
6. Enfin, il est nécessaire, vu les circonstances qui en commandent
l’application, que le système soit d’un usage facile, ne demandant ni
tension d’esprit, ni la connaissance d’une longue série de règles à
observer.
Source : https://fr.wikipedia.org/wiki/Principe_de_Kerckhoffs
28
Interprétation des principes de Kerckhoffs

La sécurité d’un système repose sur l’utilisation de clés,

et non pas sur l’utilisation de primitives gardées secrètes

29
Limitations de la méthode

Problème de l’échange des clés :

Changer régulièrement les clés
Comment s’accorder sur des clés, sans se rencontrer
Comment assurer la confidentialité au moment d’un échange de clés

30
Protocole de Diffie-Hellman
Principe de la méthode :
Alice et Bob peuvent se mettre d’accord sur un nombre (qu’ils peuvent
utiliser comme clé pour chiffrer la conversation suivante) sans qu’un
troisième agent appelé Ève puisse découvrir le nombre, même en ayant
écouté tous leurs échanges.2

2 https://fr.wikipedia.org/wiki/Échange_de_clés_Diffie-Hellman
31
Modèle théorique de chiffrement
Comment démontrer que la méthode OTP marche ?
OTP = One -Time Pad (méthode du masque jetable)

OTP est une méthode de chiffrement théorique parfaite

Preuve : Claude Shannon en 1949

Exigences3 pour que ça marche :

1. Choisir une clef aussi longue que le texte à chiffrer,
2. Utiliser une clef formée d’une suite de caractères aléatoires,
3. Protéger votre clef,
4. Ne jamais réutiliser une clef,
5. Ecrire des textes clairs ne contenant que les lettres (sans
ponctuation et sans espaces).

Pourquoi ces exigences doivent être vérifiées ?

3 https ://www.maths.univ-

evry.fr/pages_perso/bayad/Enseignement/Polycopie_crypto-2008.pdf
33
Modèle théorique de chiffrement
Trois ensembles :
K : Ensemble des clés (keys)
M : Ensemble des messages claires
C : Ensemble des messages chiffrés

Trois fonctions principales :

Pour k ∈ K : Enck (m) = c ∈ C (∀m ∈ M)
Pour k ∈ K : Deck (c) = m ∈ M (∀c ∈ C)
Gen() = k ∈ K : fonction de génération “quasi”-aléatoire de clés

Si le modèle est correcte :

∀k ∈ K, ∀m ∈ M : Deck (Enck (m)) = m

Un schéma (théorique) de chiffrement, est la donnée d’un triplet

⟨Gen, Enc, Dec⟩
34
Modèle d’attaquants

Passif
▶ Attaque à texte clair connu
▶ Attaque à texte chiffré seulement
Actif
▶ Attaque à texte clair choisi
▶ L’attaque à texte chiffré choisi

Voir page 16 du polycopie

35
Objectifs à réaliser

Définir précisément :
Ce qu’on veux faire
Le schema à utiliser
(ie, celui pour lequel on “peut” avoir confiance)

A partir de preuves théoriques rigoureuses :

Montrer que les hypothèses intuitives sont correctes
Etablir les éléments en commun entre les schémas de chiffrement
Déterminer la robustesse des schémas aux attaques connues

36
Chiffrement parfait

Définition :
Un schema de chiffrement ⟨Gen, Enc, Dec⟩ sur un espace de messages M
est parfaitement secret, si pour toute distribution de probabilité sur M,
pour tout message clair m ∈ M, et pour tout message crypté c ∈ C :

Pr[M = m|C = c] = Pr[M = m]

ie, les distributions sur les messages et les cryptés sont indépendantes.

On peut aussi rechercher (de manière équivalente)

Pr[C = c|M = m] = Pr[C = c]
Pr[C = c|M = m0 ] = Pr[C = c|M = m1 ], pour m0 , m1 ∈ M
(Impossibilité de distinguer les cryptés de deux messages différents)

37
Formulation équivalente
L’adversaire écoute une expérience d’indiscernabilité symétrique : Symécoute
A,S
Soit
S = ⟨Gen, Enc, Dec⟩,
Un adversaire A réalisant l’expérience suivante :
1. A fourni une paire de message m0 , m1 ∈ M
2. Une clé aléatoire k ∈ K et un bit b ∈ {0, 1} sont choisis,
puis Enck (mb ) est envoyé à A
3. A fourni un bit b′
4. On a Symécoute
A,S = 1 si et seulement si b = b′
(On dit alors que A a réussi)

Définition :
S = ⟨Gen, Enc, Dec⟩ sur un espace de messages M est parfaitement
secret, si pour tout adversaire A :
  1
Pr Symécoute
A,S =1 =
2
38
One-Time Pad (méthode du masque jetable)

Algorithme :
1. Pour un entier l > 0 choisi, M = K = C = {0, 1}l
2. Gen choisi uniformément des clés sur K
3. Pour m ∈ M, Enck (m) = m ⊕ k
4. Pour c ∈ C, Deck (c) = c ⊕ k

On a :
⊕ est l’opération ou exclusif bit à bit (x ⊕ x = 0, x ⊕ 0 = x)
Deck (Enck (m)) = (m ⊕ k) ⊕ k = m ⊕ (k ⊕ k) = m

39
OTP est parfaitement secret
Preuve :

Pr[C = c|M = m] = Pr[M ⊕ K = c|M = m]

= Pr[m ⊕ K = c]
1
= Pr[K = m ⊕ c] =
2l
= Pr[C = c|M = m ] pour tout m′
′

Remarques
Les clés doivent être aussi longues que les messages
Si on utilise deux fois la même clé
▶ c1 = m1 ⊕ k et c2 = m2 ⊕ k
▶ c1 ⊕ c2 = (m1 ⊕ k) ⊕ (m2 ⊕ k) = m1 ⊕ m2
▶ Donc en sachant m1 ou m2 , on en déduit l’autre

c1 ⊕ c2 ⊕ m1 = m2

A peut donc gagner deux fois à Symécoute

A,S avec la même clé
40
Schéma non parfaitement secret

Théorème :
Tout schéma ⟨Gen, Enc, Dec⟩ pour lequel |K| < |M| n’est pas
parfaitement secret.

41
Plan : 3 - Cryptographie symétrique

3.1 Introduction
3.2 Chiffrements par blocs
3.3 Chiffrements à flux

42
Introduction

Deux grands types :

1. Chiffrements par blocs (D.E.S., A.E.S., ...)
2. Chiffrements à flux (A5/1, ...)
En générale
Les chiffrements par blocs sont plus lent, mais plus sécurisés
Les chiffrements à flux conviennent pour les protocoles léger
(téléphonie, bluethooth...)

43
Chiffrements par blocs
Principe

Pour un message clair m :

Découper m en blocs de taille identique n
Chiffrer ces blocs successivement

On peut le faire en chiffrant plusieurs fois les blocs.

45
Réseau de Feistel

46
Réseau de Feistel (suite)

Principe :
▶ on découpe l’information en deux blocs ;
▶ un bloc est codé avec une clé ou sous-clé (dérivée) ;
▶ le bloc codé est ajouté à l’autre avec un XOR ;
▶ on réitère le processus un certain nombre de tours
Chiffrement et déchiffrement ont une structure similaire
Exemples d’algorithme : DES, AES, Lucifer
Exercices à rendre : Présenter DES, AES par ces modes opératoires
(ECB et CBC).

47
Chiffrements à flots
Principle

Utilisation de OTP avec une fonction Gen pseudo-aléatoire

WEP, GSM, Bluetooth, ...
Utilisation du “keystream” (voir tableau)

49
Modes de fonctionnement

Deux modes
Mode synchronisé
Mode asynchrone
Exercice : présenter les modes de fonctionnement synchrone et
asynchrone.

50
Plan : 4 - Cryptographie asymétrique

4.1 Chiffrement à clé publique : RSA

4.2 Applications

51
A l’origine, le protocole de Diffie-Hellman: échange de clé
Alice et Bob peuvent se mettre d’accord sur un nombre (qu’ils peuvent
utiliser comme clé pour chiffrer la conversation suivante) sans qu’un
troisième agent appelé Ève puisse découvrir le nombre, même en ayant
écouté tous leurs échanges.4

4 https://fr.wikipedia.org/wiki/Échange_de_clés_Diffie-Hellman
52
Cryptographie asymétrique en bref

Essentiel pour assurer la sécurité de nombreux systèmes (Dans l’état

actuel de nos connaissances, i.e. sans ordinateur quantique)
Caractérisé par :
▶ Utilisation d’une clé publique
▶ Simplicité de mise en oeuvre et d’utilisation
▶ Sécurité, confidentialité, préservation de l’intimité qu’il offre aux
utilisateurs (Tout le monde à le droit fondamental de préserver son
intimité numérique : Philip Zimmermann)
Créer en 1976 par Rivest, Shamir et Adleman : système RSA

53
Bases mathématiques

RSA est basé sur l’arithmétique et la théorie des nombres:

Calcul modulaire : inversion modulo N
Utilisation des générateurs de (Z/N Z)
Utilisation de l’exponentiation binaire

54
Schéma de chiffrement RSA
Les composantes ⟨Gen, Enc, Dec⟩ sont :
1. Génération des clés Gen :
1.1 Soient deux nombres premiers p et q et N = pq
1.2 Alice choisit e : 1 ≤ e < N tel que pgcd(e, (p − 1)(q − 1)) = 1
On a alors :
Clé publique Alice = (N, e)
Clé privé Alice = (p, q, d)
Avec d tel que : ed ≡ 1 mod (p − 1)(q − 1)
2. Chiffrement Enc :
▶ Pour m ∈ M, on construit la séquence ⟨m1 , m2 , · · · , mw ⟩ de Z/N Z
▶ Chaque mi est chiffré séparément avec la clé publique d’Alice

ci = mei mod N
▶ On envoie ⟨c1 , c2 , · · · , cw ⟩ à Alice
3. Déchiffrement Dec :
▶ Alice calcule pour chaque ci : m′i = cdi mod N
▶ On a alors m′ = m = ⟨m′1 , m′2 , · · · , m′w ⟩

55
Attaques

Possibles si la clé est trop courte (<2144 bits)

Plusieurs méthodes existent.

56
Applications

On peut citer :
Signature numérique
Authentification
Certification numérique

57
Plan : 5 - Fonctions de hachage

5.1 Intuitivement
5.2 Formellement
5.3 Mise en oeuvre pratique
5.4 Exemples d’applications

58
Intuitivement
Fonction de hachage cryptographique

“Un tout petit changement dans le message provoque un changement

significatif dans le haché !”

60
Intuitivement
Fonction (Hach) des messages vers les hachés (digests, fingerprints, ...)
En ayant un haché, il est “pratiquement” impossible de retrouver le
message (fonction à sens unique)
Pour tout hash = Hach(mesg), on a :
▶ Hach(mesg) est rapide à calculer
▶ Pour tout hash, impossible de retrouver Hach−1 (hash) = mesg
▶ Pour tous mesg, mesg ′ : Hach(mesg) ̸= Hach(mesg ′ )
(Il est pratiquement infaisable de determiner deux messages ayant le
même hash - On parle alors de collision)

Algorithme courant :
Secure Hash Algorithm (SHA), MD4, MD5, RIPEMD-256, ...

Voir également
https://fr.wikipedia.org/wiki/Fonction_de_hachage_cryptographique

61
Formellement
Modélisation mathématique

Objectif à réaliser pour avoir un modèle :

Tout le monde doit pouvoir calculer le haché d’un message
Un haché doit correspondre à une “empreinte digitale”

Hach(mesg) ≡ H(s, mesg) ≡ Hs (mesg)

▶ Où s est une clé rendue publique

63
Définition et propriétés fondamentales
Définition : Une fonction de hachage est une paire ⟨Gen, H⟩, telle que
Gen est un algorithme permettant de générer une clé s, suivant une
certaine loi de probabilité, en ayant une entrée sécurisée 1n
Il existe un polynôme l tel que pour
mesg ∈ {0, 1}∗ : Hs (mesg) ∈ {0, 1}l(n)

Propriétés fondamentales :
Résistante aux collisions :
Pour s donné, il est pratiquement infaisable de trouver mesg et
mesg ′ tels que Hs (mesg) = Hs (mesg ′ )
Résistante à la pré-image :
Pour s et hash donnés, il est pratiquement infaisable de trouver
mesg tel que Hs (mesg) = hash
Résistante à la seconde pré-image :
Pour tout s et mesg donnés, il est pratiquement infaisable de
trouver mesg ′ tel que Hs (mesg) = Hs (mesg ′ )

64
Mise en oeuvre pratique
Modèles de construction

Construction de Merkle-Damgårt
Construction de Miyaguchi-Preneel
Construction de Matyas-Meyer-Oseas
Construction de Davies-Meyer
Voie également : https://en.wikipedia.org/wiki/One-way_compression_function

66
Transformation de Merkle-Damgårt

IV est un vecteur d’initialisation constant

f est une fonction de compression
(entrées et sorties de tailles constantes)
Le digest d’une compression est transmis à l’étage suivant un modèle
précis (Miyaguchi-Preneel, Matyas-Meyer-Oseas, Davies-Meyer)
Schéma utilisé pour MD5, SHA-1, SHA-2, ...
67
Construction de Miyaguchi-Preneel

Architecture encore sûre (sans faille officiellement découverte)

E fonction de chiffrement (Encryption)
g : fonction qui convertir l’entrée précédente pour qu’elle soit
utilisée comme une clé
H : haché d’un étage
68
Exemples d’applications
Fonctions de hachage
Les plus courantes :
Nouvelle norme (SHA3) : Keccak
SHA2 (“presque”-dépassée)
SHA1 (dépassée)
MD5 (dépassée)

Utilisées pour :
Table de hachage comme structure de données
MAC : Message Authentification Code
Partage de clés
Signature électronique
Contrôle d’intégrité
Voir également https://fr.wikipedia.org/wiki/Fonction_de_hachage

70
Plan : 6 - Signature électronique

6.1 Intuitivement
6.2 Formellement

71
Intuitivement
Signature digitale ou électronique
Intuitivement
Alice souhaite envoyer un message à Bob en assurant son authenticité.
Ils utilisent
1. Une schéma de chiffrement asymétrique ⟨Gen, Enc, Dec⟩
▶ Gen(1n ) = (pb, pv), où pb est une clé publique et pv une clé privée
▶ Encpv (m) = c, (La clé privée est utilisée pour chiffer !!!)
▶ Decpb (c) = m

2. Une fonction de hachage ⟨GenH,H⟩

n
▶ GenH(1 )=s , la clé s est rendue publique
▶ Pour mesg ∈ {0, 1}∗ : Hs (mesg) ∈ {0, 1}l(n)

On a alors :
1. Signature du message
1.1 Hachage du message : hash = Hs (mesg)
1.2 Chiffrement du haché avec la clé privé : sign = Encpv (hash)
1.3 Transmission du message et de sa signature : ⟨mesg, sign⟩
2. Vérification de la signature
2.1 Hachage du message : hash = Hs (mesg)
2.2 Déchiffrement du signé avec la clé publique : hash′ = Decpb (sign)
2.3 Vérification si (hash == hash′ ) = true
74
Formellement
Schéma de signature électronique

Définition :
Un schéma de signature électronique est un triplet ⟨Gen, Sign, Vrfy⟩, où
Gen(1n ) = (pb, pr), où pb est une clé publique et pv une clé privée
Signpv (mesg) = sign
Vrfypb (mesg, sign) = b ∈ {0, 1}
▶ si b = 1 alors l’authentification est valide,
▶ si b = 0 alors l’authentification est invalide

Il peut arriver que Vrfypb (mesg, Signpv (mesg)) = 0

(probabilité négligeable)

76
Algorithmes couramment utilisés

Hachage RSA,
Digital Signature Standard (DSS, NIST 1991) : DSA
(Voir https://fr.wikipedia.org/wiki/Digital_Signature_Algorithm)

77
Applications typiques

Authentification,
Certification électronique,
Vérification d’intégrité
Plan : 7 - Générateurs de suites aléatoires

7.1 Intuitivement
7.2 Algorithmes courants
7.3 Exemples d’applications à la cryptographie

79
Intuitivement
Suite aléatoire
Une suite (xn )n∈N est aléatoire, s’il n’existe pas de fonction
déterministe5 f telle que pour tout n : f (x1 , ..., xn−1 ) = xn

Une suite (xn )n∈N est pseudo-aléatoire, s’il n’existe pas de fonction
calculable en pratique f telle que pour tout n : f (x1 , ..., xn−1 ) = xn

Une suite aléatoire permet intuitivement de représenter le “hasard”.

Caractérisation théorique : complexité de Kolmogorov

Un problème à 1 million de dollar : 6

S’il existe un générateur de nombre aléatoire alors P = N P

5 Renvoie toujours le même résultat pour une entrée donnée

6 https://fr.wikipedia.org/wiki/Problèmes_du_prix_du_millénaire
81
Principe de génération de nombres aléatoires
Utiliser des phénomènes naturels ‘jugés” intrinsèquement aléatoire pour
former ces suites
Radioactivité
Gravitation
Bruits thermiques, électromagnétiques
Principe fondamentale de la dynamique
Principe de l’action et de la réaction

–> Ca marche pas : les phénomènes sont imprévisibles mais pas

aléatoires (théorie du chaos)

On se contente de série pseudo-aléatoires en pratique:

John von Neumann : “Quiconque considère des méthodes arithmétiques
pour produire des nombres aléatoires est, bien sûr, en train de commettre
un péché”
82
Algorithmes courants

Méthode de Von-Neumann
Méthode de Fibonacci
Générateurs congruentiels linéaires
Voir également :
https://fr.wikipedia.org/wiki/Générateur_de_nombres_pseudo-aléatoires

83
Exemples d’applications à la cryptographie

Blum Blum Shub (sûr mais lent)

Yarrow
Fortuna
ISAAC
Principe : accumuler de l’entropie sur l’ordinateur et utiliser MD5 ou
SHA-1
Temps d’accès sur disque
Mouvement souris,
Frappes sur clavier, ...
voir http://www.deltasight.fr/entropie-linux-generation-nombres-aleatoires/

84
Plan : 8 - Logiciels de sécurité informatique

85
PGP

OpenSSL

John the Ripper

Aircrack-ng
Plan : 9 - Cryptanalyse

9.1 Intuitivement
9.2 Méthodes de cryptanalyse

87
L’art de la cryptologie par Diffie-Hellman

“L’habileté dans la cryptanalyse a toujours été lourdement du côté des

professionnels, mais l’innovation, en particulier dans la conception des
nouveaux types de systèmes cryptographiques, est venue principalement
d’amateurs.”

C’est quoi la cryptanalyse ? :

“La cryptanalyse est la technique qui consiste à déduire un texte en clair
d’un texte chiffré sans posséder la clé de chiffrement.

Le processus par lequel on tente de comprendre un message en particulier

est appelé une attaque.”7

(Attaque se dit aussi cryptanalyse)

7 https://fr.wikipedia.org/wiki/Cryptanalyse
88
 Premier cryptanalyste connu : Al-Kindi (801-873)
Méthode d’analyse des fréquences

“La façon d’élucider un message crypté, si nous savons dans quelle

langue il est écrit, est de nous procurer un autre texte en clair dans la
même langue, de la longueur d’un feuillet environ, et de compter alors les
apparitions de chaque lettre. Ensuite, nous nous reportons au texte
chiffré que nous voulons éclaircir et relevons de même ses symboles.
Nous remplaçons le symbole le plus fréquent par la lettre première (la
plus fréquente du texte clair), le suivant par la deuxième, le suivant par la
troisième, et ainsi de suite jusqu’à ce que nous soyons venus à bout de
tous les symboles du cryptogramme à résoudre.”

89
Formes (niveaux) d’attaques
Passif
▶ Attaque à message clair connu
▶ Certaines paires (messages, chiffrés) connues
▶ Objectif : Trouver les clés utilisées pour déchiffrer d’autres chiffrés

▶ Attaque à message chiffré seulement

▶ Certains chiffrés connus
▶ Objectif : Trouver les messages clairs, déduire la clé utilisée pour
déchiffrer d’autres chiffrés

Actif
▶ Attaque à message clair choisi
▶ Les paires (messages, chiffrées) connues
▶ Dispose de la possibilité de choisir des messages
▶ Objectif : Trouver la clé
▶ L’attaque à message chiffré choisi
▶ Choisir des chiffrés et obtient les messages correspondant
▶ Objectif : Trouver la clé

90
Méthodes classiques
https://fr.wikipedia.org/wiki/Cryptanalyse

Attaque par force brute

Attaque par mot probable, dictionnaire
Analyse fréquentielle, indice de coincidence
Attaque par paradoxe des anniversaires (collisions : exemple,
probabilité d’avoir deux étudiants ayant la même date d’anniversaire)

91
Méthodes modernes

Spécifiques aux primitives cryptographiques

On attaque une partie de la primitive
L’efficacité de l’attaque se mesure par rapport à la plus grande partie
de la primitive qu’on peut attaquer
On calcule les complexité temporelle, spatiale et en mémoire
nécessaire

92