Introduction à la cryptographie

2024
Vincent Itier
Partie 1
Notions et éléments de base
Partie 1 : Notions et éléments de base :

Principes de sécurités 4

Confidentialité : Linformation nest accessible quà ceux dont

laccès est autorisé
Authentification : Chaque personne est bien celui quelle
prétend être (légitimité)
Intégrité : Le message envoyé na pas été altéré de manière
volontaire ou involontaire
Non-répudiation : Aucune des deux parties ne pourra assurer
ne pas être lauteur du message
Disponibilité : Laccès à un service ou à des ressources est
garanti

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Principes de sécurités 5

De nombreux axes :
Tatouage
Stéganographie
Digital forensics (détection de manipulations, identification de
capteurs)
Biométrie
Cryptographie

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Principes de sécurités 6

CNIL
Introduction à la cryptographie Vincent Itier
Partie 1 : Notions et éléments de base :

Rappels de Mathématique 7

Anneau Z/nZ : Anneau correspondant au calcul modulaire

sur les restes de entiers dans la division par n.
Congruence : Soit n ≥ 2 un entier fixé, on dit que a est
congru à b modulo n, si n divise b − a.
On note alors : a ≡ b (mod n).
Propriétés algébriques :
Si a1 ≡ b1 (mod n) et a2 ≡ b2 (mod n), alors
a1 + a2 ≡ b1 + b2 (mod n) et a1 a2 ≡ b1 b2 (mod n).
a ≡ b (mod n), alors ac ≡ bc (mod n) pour tout entier c et
aq ≡ bq (mod n) pour tout entier q > 0.

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Rappels de Mathématique 8

+ 0 1 2 3 4 5 × 0 1 2 3 4 5
0 0 1 2 3 4 5 0 0 0 0 0 0 0
1 1 2 3 4 5 0 1 0 1 2 3 4 5
2 2 3 4 5 0 1 2 0 2 4 0 2 4
3 3 4 5 0 1 2 3 0 3 0 3 0 3
4 4 5 0 1 2 3 4 0 4 2 0 4 2
5 5 0 1 2 3 4 5 0 5 4 3 2 1
Table d’addition de Z/6Z. Table de multiplication de Z/6Z.

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Terminologie 9

Cryptologie : Science mathématique comportant deux

branches : la cryptographie et la cryptanalyse.
Cryptographie : Étude des méthodes donnant la possibilité
denvoyer des données de manière confidentielle.
Chiffrement : Transformation à laide dune clef dun message
en clair en message chiffré (ou cryptogramme) pour le rendre
incompréhensible.
Déchiffrement : Action qui permet de reconstruire le
message en clair à partir du message chiffré.
Cryptanalyse : Etude des procédés cryptographiques dans le
but de trouver des faiblesses, et en particulier, réussir à
déchiffrer un message chiffré sans connaître la clef de
chiffrement et/ou retrouver la clef de chiffrement.

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Cryptosystème 10

Les opérations de chiffrement/déchiffrement sont basées sur

deux éléments fondamentaux :
Un algorithme cryptographique qui est une fonction
mathématique réalisant ces deux opérations.
Une clef secrète.
Ces éléments sont appliqués au message à transformer.
Un cryptosystème est défini comme lensemble :

Des clefs possibles (espace

de clefs).
Des messages clairs associés à un algorithme donné
possibles.
Des messages chiffrés
possibles.

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Cryptosystème 11

Message en clair Message chiffré

n bits m bits

k bits

Clef

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Principe de Kerckhoffs 12

Aucun secret ne doit résider dans lalgorithme cryptographique

utilisé : tout réside dans la clef !
"La sécurité ne doit pas dépendre de tout ce qui ne peut pas
être facilement changé."
Pour un algorithme : secret 6= robustesse.
Sans la clef, il doit être impossible de retrouver le message
clair à partir du chiffré.
Si on connaît la clef, on doit pouvoir déchiffrer le chiffré sans
problème.
Auguste Kerckhoffs, La cryptographie militaire, Journal des sciences militaires, vol. IX, pp. 538, jan. 1883,
pp. 161191, févr. 1883.

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Algorithme publié vs secret 13

Algorithme publié Algorithme secret

Possible dévaluer la sécurité La cryptanalyse doit inclure
de manière fiable. la récupération de
Empêche les backdoors lalgorithme.
cachées par les concepteurs. Petit nombre dutilisateurs =
Grand nombre dutilisateurs Plus petite motivation à
= Prix réduit + essayer de casser
performance élevée. lalgorithme.
Pas besoin de protection Indisponible pour un autre
contre le reverse engineering. pays.
Implémentations logicielles.
Standardisation locale et
internationale.
Introduction à la cryptographie Vincent Itier
Partie 1 : Notions et éléments de base :

Entropie 14

Entropie dordre zéro : Si X est une variable aléatoire

discrète, lentropie de X est définie par :
X
H(X) = − P (X = x)log(P (X = x)).
x

Entropie conditionnelle : Incertitude qui reste sur X quand

on connaît déjà Y :
X
H(X|Y ) = − P (X = x, Y = y)log(P (X = x|Y = y))
x,y

avec P (X = x, Y = y) = P (X = x|Y = y)P (y).

Entropie jointe : H(X, Y ) = H(Y ) + H(X|Y )
Lien entre les entropies : H(X, Y ) ≤ H(X) + H(Y ).
Si X et Y sont indépendantes : H(X, Y ) = H(X) + H(Y ).
Claude E. Shannon, A mathematical theory of communication, Bell System Technical Journal, vol. 27, p.
379-423 and 623-656, 1948.
Introduction à la cryptographie Vincent Itier
Partie 1 : Notions et éléments de base :

Entropie et cryptographie 15

L’incertitude liée à un système est H(M ) : besoin de H(M )

bits d’information pour retrouver le message.
Pour qu’un système cryptographique soit sûr, il faut et il suffit
que :
H(M |C) = H(M )
Exercice : Démontrez-le.

Introduction à la cryptographie Vincent Itier

Partie 1 : Notions et éléments de base :

Entropie et cryptographie 16

Un système est sûr si la connaissance de C (sans la clef) napporte

aucune information sur M :

H(M |C) = H(M ) ⇐⇒ H(M |C) + H(C) = H(M ) + H(C)

⇐⇒ H(M, C) = H(M ) + H(C)
⇐⇒ M et C sont indépendants
⇐⇒ P (M |C) = P (M )

Introduction à la cryptographie Vincent Itier

Quelques systèmes simples
Partie 1 : Quelques systèmes simples :

Historique 18

Comment envoyer des messages sans que personne ne puisse

les intercepter ?

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples :

Historique 18

Comment envoyer des messages sans que personne ne puisse

les intercepter ?

Scytale (ou bâton de

Plutarque)
Tablette d’argile. Sparte 404 av. J.-C.
Irak XV I e siècle av. J.-C. Plus ancien dispositif de
Premier document chiffré cryptographie militaire
connu Chiffrement par
Suppression des consonnes transposition/permutation
Modification de lorthographe En quoi consiste la clef ?

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples : Chiffrement par permutation

Chiffrement par permutation 19

Consiste à changer l’ordre des lettres, donc à construire des

anagrammes (scytale).
La clef de chiffrement est la permutation elle-même.
Nombre de permutations pour un bloc de n caractères : n!
possibilités
Par exemple 20! = 2432902008176640000 combinaisons.
Génération de la clé :
Génération dune séquence pseudo-aléatoire à laide dun
générateur de nombre pseudo- aléatoire (PRNG).
Clef utilisée comme graine dinitialisation du PRNG.
Utilisation de la séquence pseudo-aléatoire pour les valeurs du
message.

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples : Chiffrement par substitution

Historique 20

Chiffrement de César : Décalage circulaire des lettres de

lalphabet
I er siècle av. J.-C.
Chiffrement par substitution monoalphabétique
La longueur du décalage constitue la clef de chiffrement
Généralement la clef est égale à 3 :

C[i] = E(M [i]) = M [i] + 3(mod 26)

M [i] = D(C[i]) = C[i] − 3(mod 26)

Quelle est la taille de lespace des clefs ?

Déchiffrez le message
XQHPHWKRGHSDVYUDLPHQWVHFXULVHH.

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples : Chiffrement par substitution

Un peu de math 21

Anneau Z/nZ : Anneau correspondant au calcul modulaire

sur les restes des entiers dans la division par n.
Modulo : On dit que a est congru à b modulo n, si n divise
b − a. On note alors a ≡ b(mod n).
De façon naturelle laddition et la multiplication dentiers se
transposent dans Z/nZ.

Ici n = 26, on a : Z/26Z l’ensemble de tous les éléments de Z

modulo 26.
Cet ensemble est représenté par les 26 éléments
{0, 1, 2, . . . , 25}.

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples : Chiffrement par substitution

Exemple 22

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples : Chiffrement par substitution

Chiffrement XOR 23

Génération dune séquence pseudo-aléatoire à laide dun PRNG

Clef utilisée comme graine dinitialisation du PRNG
Utilisation de la séquence pseudo-aléatoire pour modifier les
valeurs du message en clair : ou-exclusif entre le message en
clair et la séquence (substitution)

Clair 0 1 1 1 0 0 1 1
Séquence 1 0 1 0 0 1 0 1
Chiffré 1 1 0 1 0 1 1 0

Vérifiez que lopération est symétrique.

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples : Chiffrement de Vigenère

Historique 24

Chiffrement de Vigenère
XV I e siècle
Chiffrement par substitution polyalphabétique
Une même lettre, suivant sa position, peut être remplacée par
des lettres différentes.
Clef = un mot ou une phrase (à répéter)

C[i] = E(M [i]) = (M [i] + K[i])(mod 26)

M [i] = D(C[i]) = (C[i] − K[i])(mod 26)

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples : Chiffrement de Vigenère

Un peu de math 25

La fonction de chiffrement associe à un bloc de longueur k, un

autre bloc de longueur k

Z/26Z × · · · × Z/26Z 7→ Z/26Z × · · · × Z/26Z
Cn1 ,n2 ,...,nk =
(x1 , . . . , xk ) 7→ (x1 + n1 , . . . , xk + nk )

La fonction de déchiffrement est C−n1 ,−n2 ,...,−nk

Introduction à la cryptographie Vincent Itier

Partie 1 : Quelques systèmes simples : Chiffrement de Vigenère

Historique 26

Chiffrement parfait
Chiffre de Vernam (1926) ou "masque jetable"
Trois impératifs pour la clef :
Aussi longue que le message à chiffrer
Parfaitement aléatoire
Utilisée pour chiffrer un seul message, puis détruite
Modèle théorique car très difficile à mettre en place !

Introduction à la cryptographie Vincent Itier

Cryptanalyse
Partie 1 : Cryptanalyse :

Cryptanalyse 28

La cryptanalyse est la technique qui consiste à déduire un

texte en clair dun 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.

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse :

Cryptanalyse : attaques 29

Attaque sur texte chiffré seul : le cryptanalyste possède des exemplaires

chiffrés des messages, il peut faire des hypothèses sur les messages
originaux qu’il ne possède pas. La cryptanalyse est plus ardue de par le
manque d’informations à disposition.
Attaque à texte clair connu : le cryptanalyste possède des messages ou
des parties de messages en clair ainsi que les versions chiffrées. La
cryptanalyse linéaire fait partie de cette catégorie.
Attaque à texte clair choisi : le cryptanalyste possède des messages en
clair, il peut créer les versions chiffrées de ces messages avec l’algorithme
que l’on peut dès lors considérer comme une boîte noire. La cryptanalyse
différentielle est un exemple d’attaque à texte clair choisi.
Attaque à texte chiffré choisi : le cryptanalyste possède des messages
chiffrés et demande la version en clair de certains de ces messages pour
mener l’attaque.

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse :

Historique 30

Machine ENIGMA
XX e siècle Utilisée pendant la Seconde
Guerre Mondiale
Tour des rotors changement de substitution
Clef : position initiale des rotors (changée
chaque jour)
Espace des clefs très grand (de lordre de
1020 )
Cryptanalyse par Alan Turing

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse : Cryptanalyse du chiffrement affine

Cryptanalyse du chiffrement par substitution 31

En pratiques non sécurisés et non utilisés.

Facile à casser par analyse fréquentielle.

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse : Cryptanalyse du chiffrement affine

Cryptanalyse du chiffrement de César 32

Espace des clés

26 fonctions Ck différentes, k = 0, 1, . . . , 25.
k appartient à Z/26Z, par exemple les fonctions C29 et C3
sont identiques.
L’espace de clés est Z/26Z.
Attaque
Il est clair que ce chiffrement de César est dune sécurité très
faible !
Tester chacune des 26 combinaisons possibles.
Reconnaître parmi ces combinaisons laquelle donne un message
compréhensible.

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse : Cryptanalyse du chiffrement affine

Cryptanalyse du chiffrement affine 33

Le chiffrement affine est un chiffrement par substitution

monoalphabétique.
Soit la formule générale pour chiffrer une lettre est :

c=a×m+b

où :
c est le caractère chiffré,
m est le caractère en clair (numérique),
a et b sont des clés.
Le déchiffrement :

m = a−1 × (c − b)

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse : Cryptanalyse du chiffrement affine

Injection de faute 34

Soit un système de chiffrement affine avec a et b secret.

1 En connaissant la faute
m = 1 → c = 5, sans faute,
m = 2 → c = 12, avec faute +2 sur a.
2 En ne connaissant pas la faute
m = 2 → c = 7, sans faute,
m = 2 → c = 13, avec faute sur a,
m = 1 → c = 8, avec la même faute sur a.

Trouver a et b dans ces deux cas ?

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse : Cryptanalyse du chiffrement de Vigenère

Chiffrement de Vigenère 35

Espace des clés

Il y a 26k choix possibles de clés.
Attaques
Pour le chiffrement par substitution polyalphabétique il est
nécessaire de connaître la longueur de la clef :
Si deux lettres sont situées à la même position dans deux
blocs différents alors elles seront cryptées par la même lettre.
Attaque statistique (indice de coïncidence).
Analyse fréquentielle

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse : Cryptanalyse du chiffrement par permutation

Cryptanalyse du chiffrement par permutation 36

Un chiffrement par transposition ne résiste pas à une attaque

à texte clair connu (un couple clair-chiffré de la taille de la
permutation utilisée donne immédiatement celle-ci).
Ne modifie pas la fréquence des lettres du texte clair.
Ne modifie pas l’indice de coïncidence.

Introduction à la cryptographie Vincent Itier

Partie 1 : Cryptanalyse : Cryptanalyse du chiffrement par permutation

Cryptanalyse du chiffrement par permutation 37

Exemple : message intercepté le 12 mars 1942 par le service de

renseignement radio de la FCC américaine.

Message chiffré : CARTM IELHX YEERX DEXUE VCCXP EXEEM OEUNM

CMIRL XRTFO CXQYX EXISV NXMAH GRSML ZPEMS NQXXX ETNIX
AAEXV UXURA FOEAH XUEUT AFXEH EHTEN NMFXA XNZOR ECSEI
OAINE MRCFX SENSD PELXA HPRE

Clé de transposition : 8 4 9 14 1 2 16 10 3 17 15 19 11 5 20 6 7 12 13 18

08 04 09 14 01 02 16 10 03 17 15 19 11 05 20 06 07 12 13 18
S P R U C H x S E C H S N U L L x V O N
V E S T A x A N x S T E I N x x Q U E E
N x M A R Y x Q U E E N x M A R Y x A M
x E L F T E N x E I N S A C H T x U H R
M E Z x M E Z x V O N D A M P F E R x C
A M P E I R O x C A M P E I R O x A U F
H O E H E x R E C I F E x R E C I F E x
G E M E L D E T x . . . . . . . . . . .

Introduction à la cryptographie Vincent Itier

Partie 2
Approfondissement
Partie 2 : Approfondissement : Cryptographie symétrique

Cryptographie Symétrique 40

La cryptographie symétrique, également dite à clef secrète

permet à la fois de chiffrer et de déchiffrer des messages à
l’aide dune même clef secrète.
Deux catégories de méthodes :
Chiffrement par flot : traitement des données de longueur
quelconque, sans besoin de les découper
Chiffrement par bloc : découpage des données à chiffrer en
blocs de taille généralement fixe

Introduction à la cryptographie Vincent Itier

Partie 2 : Approfondissement : Cryptographie symétrique

Cryptographie Symétrique 41

Principe : Algorithmes basés sur des opérations de

transposition/permutation et de substitution des bits du texte
clair, en fonction de la clef.
Taille des clefs : (standard) 128 bits minimum.
Performances : Très rapide.
Distribution des clefs :
Très critique
Doit seffectuer de manière sécurisée

Introduction à la cryptographie Vincent Itier

Partie 2 : Approfondissement : Cryptographie symétrique

Modes de chiffrement 42

Généralement défini pour le chiffrement par bloc, 5 modes de

chiffrement principaux :
ECB ("Electronic CodeBook" - Dictionnaire de codes)
CBC ("Cipher Block Chaining" - Enchaînement de blocs)
CFB ("Cipher FeedBack" - Chiffrement à rétroaction)
OFB ("Output FeedBack" - Chiffrement à rétroaction de
sortie)
CTR ("CounTeR" - Chiffrement basé sur un compteur)

Introduction à la cryptographie Vincent Itier

Partie 2 : Approfondissement : Cryptographie symétrique

ECB ("Electronic CodeBook") 43

Introduction à la cryptographie Vincent Itier

Partie 2 : Approfondissement : Cryptographie symétrique

CBC ("Cipher Block Chaining") 44

Introduction à la cryptographie Vincent Itier

Partie 2 : Approfondissement : Cryptographie symétrique

CFB ("Cipher FeedBack") 45

Introduction à la cryptographie Vincent Itier

Partie 2 : Approfondissement : Cryptographie symétrique

OFB ("Output FeedBack") 46

Introduction à la cryptographie Vincent Itier

Partie 2 : Approfondissement : Cryptographie symétrique

CTR ("CounTeR") 47

Introduction à la cryptographie Vincent Itier

Le standard de chiffrement de données
Partie 2 : Le standard de chiffrement de données : Protocole DES

Data Encryption Standard (DES) 49

64 bits

Algorithme de chiffrement Permutation initiale DES

symétrique, par blocs.

Générateur de clefs de tour

Publié en 1975 par IBM. Ke1
Tour 1
48 bits
Aujourd’hui : considéré
Ke2 Clef K
comme non-sécurisé. Tour 2
48 bits
Caractéristiques techniques : Kei 56 bits
...
48 bits
Ke16
Taille de la clef : 56 bits Tour 16
48 bits
(+ 8 bits de parité)
Taille des blocs : 64 bits Permutation finale
Nombre de tours : 16
64 bits

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : DES en pratique et mode d’utilisation

Data Encryption Standard (DES) 50

Permutation initiale : 12 8 25 40 58 64
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3 12 8 25 40 58 64
61 53 45 37 29 21 13 5
Quelle est la nouvelle position du
63 55 47 39 31 23 15 7 bit à la position initiale 8 ?

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : DES en pratique et mode d’utilisation

Data Encryption Standard (DES) 51

Li Ri

Structure générale des tours :

Découpage de chaque bloc en 2 L
sous-blocs. Tour 1 F
Application de la fonction F (de
Feistel) à l’un des sous-blocs.
Ou-exclusif avec l’autre L
Tour 2 F
sous-bloc :

Li+1 = Ri
Ri+1 = Li ⊕ F (Ri , Kei+1 )
L
Tour 3 F
...

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : DES en pratique et mode d’utilisation

Data Encryption Standard (DES) 52

Fonction de Feistel (F ) :
Expansion : 32 bits → 48 bits,
soit 8 × 6 bits (duplication de la
moitié des bits) 32 bits
Mélange avec la clef : XOR Kei
avec la clef de tour.
Substitution : Passage par les
Expansion
S-box, 6 bits → 4 bits (×8) (non
linéaire : garantit la sécurité du 48 bits
DES). L
Permutation : Passage par la
P-box, 32 bits réarrangés.

S1 S2 S3 S4 S5 S6 S7 S8

32 bits
Permutation

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : DES en pratique et mode d’utilisation

Data Encryption Standard (DES) 53

Confusion : Supprimer les relations entre le message en clair

et le message chiffré.
Outil : Boîtes de substitution (S-box).
Diffusion : Propager linformation relative à chaque bit du
message en clair dans le message chiffré.
Outil : Boîtes de permutation (P-box).

 
1 2 3 4 5 6 7
σ=
4 1 5 2 6 3 7
Permutation : Substitution :
2164523 → 1422653 2164523 → 1432615

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : DES en pratique et mode d’utilisation

Data Encryption Standard (DES) 54

Boîtes de substitution (S-box).

Par exemple, avec en entrée : 011011
4 bits au centre de l’entrée
S5
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 0010 1100 0100 0001 0111 1010 1011 0110 1000 0101 0011 1111 1101 0000 1110 1001
01 1110 1011 0010 1100 0100 0111 1101 0001 0101 0000 1111 1010 0011 1001 1000 0110
Bits externes
10 0100 0010 0001 1011 1010 1101 0111 1000 1111 1001 1100 0101 0110 0011 0000 1110
11 1011 1000 1100 0111 0001 1110 0010 1101 0110 1111 0000 1001 1010 0100 0101 0011

Qu’obtient-on en prenant 110101 en entrée ?

A quelle(s) entrée(s) peut correspondre la sortie 0101 ?

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : DES en pratique et mode d’utilisation

Data Encryption Standard (DES) 55

Clé
64 bits
Génération des clefs de tour
Permutation (PC1)
Permutation (PC1) : 64
bits → 56 bits, soit 2 × 28
bits (autres bits pour
rotation rotation
contrôle).
Rotation : Vers la gauche, Ke1
Permutation (PC2)
48 bits
dun ou deux bits.
rotation rotation
Permutation (PC2) : 28
bits → 24 bits, soit 48 bits. Ke2
Permutation (PC2)
48 bits
...

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : Cryptanalyse DES

Attaques DES 56

Attaque par force brute possible :

Diffie-Hellman en 1977 (US$ 20M), clef retrouvée en 1 jour :
théorique.
Wiener en 1993 (US$ 1M), clef retrouvée en 7h :théorique.
Electronic Frontier Foundation en 1998 (US$ 250k), clef
retrouvée en 2 jours : mise en pratique.
COPACOBANA (Univ. Bochum & Kiel, en Allemagne) en
2006 (US$ 10k) : mise en pratique.
Cryptanalyse différentielle :
Biham-Shamir en 1980 (CPA Attaque par 247 clairs choisis).
Cryptanalyse linéaire :
Matsui en 1994 (KPA Attaque par 243 clairs connus).
Junod en 2001 (KPA Attaque par 240 clairs connus).

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : Triple DES

Triple DES 57

Publié en 1998, dérivé de DES.

Plus grande taille des clefs pour éviter lattaque par force
brute : 168 bits possible.
Idée : Utiliser 3 clefs de 56 bits chacune

C = EK3 (DK2 (EK1 (M )))

M = DK1 (EK2 (DK3 (C)))

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : Triple DES

3DES 58

Attaque "Meet-in-the-middle" sur 2DES (idem pour 3DES) :

Attaque KPA (known-plaintext attack) : M1 , M2 , C1 , C2
connus tels que C1 = EK2 (EK1 (M1 )) et
C2 = EK2 (EK1 (M2 ))
Chiffrer une fois le message en clair revient à déchiffrer une
fois le message chiffré.
On a donc : EK1 (M ) = DK2 (C).
Calcul et stockage des 256 couples (K, EK (M1 )).
Pour chaque clef K 0 , calcul de Dk0 (M 1) et recherche de
correspondance.
Si couple de clefs candidates K1 = K et K2 = K 0 ,
vérification C2 = EK2 (EK1 (M2 )).
Nombre maximal dessais : 2 × 256 = 257 << 2112 .

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 59

Algorithme de chiffrement symétrique, par blocs.

Gagnant dun concours lancé en 1997.
Standard depuis 2001 (NIST).
Vrai nom : Rijndael : Créé par deux belges Joan Daemen et
Vincent Rijmen

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 60

Pourquoi un nouveau standard ?

DES est devenu attaquable par force brute.
Développement de systèmes dévaluation : analyse différentielle
et linéaire.
Possible davoir une méthode de chiffrement plus rapide en
utilisant des instructions processeur.
Pourquoi un concours public ?
Rassembler la communauté travaillant sur la cryptographie.
Encourager la recherche autour des systèmes sécurisés.
Prévenir les "backdoors".
Accélérer lacceptation et ladoption dun standard.

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 61

Description générale :
Nombre de tours : 10, 12 ou 14 (suivant la taille de la clef).
Chaque tour : 4 opérations.
Taille des blocs du message : 128 bits (4 colonnes de 4 octets).
Taille de la clef de chiffrement : 128, 192 ou 256 bits.

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 62

128 bits

Description générale :
1 KeyExpansion Ke0
Tour initial 128 bits
AES
Tour initial

Générateur de clefs de tour

2

1 AddRoundKey Ke1
Tour 1
128 bits
3 Pour chaque tour suivant :
1 SubBytes Ke2 Clef K
Tour 2
2 ShiftRows 128 bits R bits
Kei
3 MixColumns ... (128,
128 bits
4 AddRoundKey 192,
Ken
Tour N 256)
4 Tour final : 128 bits
Ken+1
1 SubBytes Tour finale 128 bits
2 ShiftRows
3 AddRoundKey
128 bits

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 63

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 64

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 65

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 66

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : AES

ADVANCED ENCRYPTION STANDARD (AES) 67

KeySchedule

Introduction à la cryptographie Vincent Itier

Partie 2 : Le standard de chiffrement de données : Cryptanalyse AES

Cryptanalyse AES 68

Attaque par canal auxiliaire :

Recherche et exploitation des failles dans l’implémentation,
logicielle ou matérielle.
Ne remet pas en cause la robustesse théorique des méthodes et
procédures de sécurité.
Une sécurité "mathématique" ne garantit pas forcément une
sécurité lors de l’utilisation en "pratique".

C D
Déchiffrement

Consommation électrique
Injection de fautes Analyse
Sons acoustiques

Beaucoup dattaques publiées non faisables en pratique (2013).

Considéré sûr à ce jour.
Introduction à la cryptographie Vincent Itier
Partie 2 : Le standard de chiffrement de données : Cryptanalyse différentielle

Cryptanalyse différentielle 69

Eli Biham et Adi Shamir à la fin des années 1980.

En général dans un contexte de texte clair choisi.
La cryptanalyse repose sur des paires de textes clairs qui ont
une différence constante.
L’attaquant calcule les différences dans les textes chiffrés.
Les propriétés statistiques des différentielles dépendent de la
nature des boîtes-S.
Retrouve la clef DES avec un ordre de 247 textes clairs
choisis : plus rapide qu’une force brute.

Introduction à la cryptographie Vincent Itier

Le chiffrement RSA et la factorisation
Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Chiffrement Asymétrique 71

On veut :

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Chiffrement Asymétrique 71

On veut :
Une fonction à sens unique qui joue le rôle de chiffrement

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Chiffrement Asymétrique 71

On veut :
Une fonction à sens unique qui joue le rôle de chiffrement
avec trappe secrète !

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Chiffrement Asymétrique 71

On veut :
Une fonction à sens unique qui joue le rôle de chiffrement
avec trappe secrète !
Exemple :
Soit f : x 7→ x3 (mod 100)
Problème : trouver x tel que x3 ≡ 11(mod 100)
Solution :

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Chiffrement Asymétrique 71

On veut :
Une fonction à sens unique qui joue le rôle de chiffrement
avec trappe secrète !
Exemple :
Soit f : x 7→ x3 (mod 100)
Problème : trouver x tel que x3 ≡ 11(mod 100)
Solution :
Recherche exhaustive . . . 713 ≡ 11(mod 100)

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Chiffrement Asymétrique 71

On veut :
Une fonction à sens unique qui joue le rôle de chiffrement
avec trappe secrète !
Exemple :
Soit f : x 7→ x3 (mod 100)
Problème : trouver x tel que x3 ≡ 11(mod 100)
Solution :
Recherche exhaustive . . . 713 ≡ 11(mod 100)
Trappe secrète y 7→ y 7 (mod 100)
117 = 71(mod 100).

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Clés secrètes 72

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Cryptographie Asymétrique 73

Caractéristiques :
Une clef privée Kpriv et une clef publique Kpub .
Propriétés :
La connaissance de la clef publique Kpub ne permet pas de
déduire la clef privée Kpriv .
DKpriv (EKpub (M )) = M .
Principe : Fonction unidirectionnelle à trappe :
"Facile" à calculer dans un sens, "difficile" à inverser.
Sauf si on connaît une information secrète (la trappe).
Algorithmes basés sur des opérations d’exponentiation en
algèbre modulaire.

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Introduction aux systèmes à clef public

Cryptographie Asymétrique 74

Caractéristiques :
Génération des clefs :
A partir de grands nombres premiers Kpub = f (Kpriv ).
Calcul de Kpriv = f −1 (Kpub ) impossible
Taille des clefs : 512 bits ou 1024 bits.
Performances : 1000 fois plus lents que les algorithmes
symétriques !
Nombre de clefs : autant de paires que dentités
Distribution des clefs facilitée car pas déchange de clefs
secrètes :
Clef secrète conservée par les entités.
Clef publique échangée.

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Le chiffrement RSA

RIVEST-SHAMIR-ADLEMAN (RSA) 75

Créé en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman

Breveté par le MIT en 1983
Basé sur le problème de la factorisation des grands nombres
entiers

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Le chiffrement RSA

RIVEST-SHAMIR-ADLEMAN (RSA) 76

Génération du couple de clefs (Kpub , Kpriv )

Choisir p et q, deux nombres premiers distincts
Calculer leur produit n = pq (module de chiffrement)
Calculer ϕ(n) = (p − 1)(q − 1)
Choisir un nombre e premier avec ϕ(n) et strictement inférieur
à ce nombre (exposant de chiffrement)
Calculer l’entier naturel d, inverse de e modulo ϕ(n)
(exposant de déchiffrement)
On a : Kpub = (e, n), Kpriv = d
Quel algorithme utilise t-on pour calculer d, linverse de e
modulo ϕ(n) ?

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Le chiffrement RSA

Un peu de math 77

Algorithme d’Euclide étendu :

Idée :
d est linverse de e modulo ϕ(n), cest-à-dire ed ≡ 1
(mod ϕ(n))
D’après le théorème de Bachet-Bézout il existe deux entiers d
et k tels que ed + kϕ(n) = 1
On veut "remonter" lalgorithme dEuclide à la main pour
obtenir les coefficients u, v tels que au + bv = pgcd(a, b).
On a deux suites (ai ) et (bi ) tel que :
Initialisation : a0 = a et b0 = b
La formule de récurrence :
ai+1 = bi et bi+1 = ai (mod bi )

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Le chiffrement RSA

Un peu de math 78

Algorithme d’Euclide étendu :

On définit deux suites (xi ),(yi )
Initialisation : x0 = 1, x1 = 0, y0 = 0 et y1 = 1
Pour i ≥ 1 on a la formule de récurrence :
xi+1 = xi1 − qi xi et yi+1 = yi1 − qi xi
où qi est le quotient de la division euclidienne de ai par bi .

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Le chiffrement RSA

Un peu de math 79

Par exemple : e = 23 et φ(n) = 120.

Dérouler l’algorithme d’Euclide pour calculer le PGCD de e et φ(n).
Utiliser les résultats obtenus pour trouver d.

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Le chiffrement RSA

Un peu de math 79

Par exemple : e = 23 et φ(n) = 120.

Dérouler l’algorithme d’Euclide pour calculer le PGCD de e et φ(n).
Utiliser les résultats obtenus pour trouver d.

120 = 1 × 120 + 0 × 23
23 = 0 × 120 + 1 × 23
5 = 120 − 5 × 23 = 1 × 120 − 5 × 23
3 = 23 − 4 × 5 = 1 × 23 − 4(1 × 120 − 5 × 23) = −4 × 120 + 21 × 23
2 = 5 − 1 × 3 = (1 × 120 − 5 × 23) − 1 × (−4 × 120 + 21 × 23) =
5 × 120 − 26 × 23
1 = 3 − 1 × 2 = (−4 × 120 + 21 × 23) − 1 × (5 × 120 − 26 × 23) =
−9 × 120 + 47 × 23
Donc d = 47 et k = −9

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Le chiffrement RSA

RIVEST-SHAMIR-ADLEMAN (RSA) 80

Algorithme de chiffrement / déchiffrement :

Alice Bruno

C = M eB (mod nB ) M = C dB (mod nB )
M = (M eB )dB (mod nB )

Kpub (A) = (eA , nA ) Kpub (B) = (eB , nB )

Kpriv (A) = dA Kpriv (B) = dB

Comment calculer efficacement l’exponentiation modulaire ?

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Le chiffrement RSA

Un peu de math 81

L’exponentiation modulaire :
Calculer rapidement des puissances modulo n.
Plus efficace que calculer xk molulo n.
On écrit le développement de lexposant k en base 2 avec k ∈ {0, 1} :
l
X
k= ki 2 i .
i=0

On peut écrire xk :

Pl l
i Y i
xk = x i=0 ki 2 = (x2 )ki .
i=0

La solution c est, par conséquent :

l
Y i
c≡ (x2 )ki (mod n).
i=0

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Cryptanalyse RSA

Taille des clés 82

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Cryptanalyse RSA

RIVEST-SHAMIR-ADLEMAN (RSA) 83

Attaque de "l’homme du milieu" :

Alice Eve Bruno
"Salut B, c’est A : Kpub (B) ?" "Salut B, c’est A : Kpub (B) ?"
Kpub (E) Kpub (B)
0
eE 0 dE
C=M (mod nE ) C =M (mod nE )

Kpub (A) = (eA , nA ) Kpub (E) = (eE , nE ) Kpub (B) = (eB , nB )

Kpriv (A) = dA Kpriv (E) = dE Kpriv (B) = dB

0
M = C dE (mod nE ) M0 = C dB
(mod nB )

Par exemple :
M = "Viens me chercher à la gare" et M 0 = "Viens me chercher au stade".

Comment remédier à ce problème ?

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Cryptanalyse RSA

Définition d’une Courbe Elliptique 84

Une courbe elliptique peut être représentée dans un plan par

une équation cubique sur le corps des nombres réels :

y 2 = x3 + ax + b

Les coefficients a et b doivent satisfaire la condition :

∆ = 4a3 + 27b2 6= 0

afin que la courbe n’ait pas de singularités (pas de point de

rebroussement ou de points doubles).
Exemples : les courbes de Weierstrass, d’Edwards, sur des
corps finis, . . .

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Cryptanalyse RSA

Opérations sur une Courbe Elliptique 85

Les courbes elliptiques permettent de définir une loi de groupe

pour des points sur la courbe.
Addition de deux points P et Q sur la courbe :

P +Q=R

où R est sur la courbe.

Multiplication scalaire d’un point P à lui-même (c’est-à-dire
P + P) :
P + P + · · · + P = n · P = R.

Introduction à la cryptographie Vincent Itier

Partie 2 : Le chiffrement RSA et la factorisation : Cryptanalyse RSA

Courbes Elliptiques en Cryptographie 86

Les courbes elliptiques sont utilisées pour la construction de

systèmes sécurisés, notamment :
ECDSA (Elliptic Curve Digital Signature Algorithm),
ECDH (Elliptic Curve Diffie-Hellman) pour l’échange de clés.
Avantage : sécurité équivalente à RSA avec des clés beaucoup
plus petites.
Exemple : pour une sécurité équivalente à RSA-2048, une clé
elliptique de 256 bits suffit.

Introduction à la cryptographie Vincent Itier

Partie 3
Fonctions de hachages
Partie 3 : Fonctions de hachages : Signatures et fonctions de hachage

Hachage 89

message M haché H(M )

M ∈ {0, 1}∗ H
H(M ) ∈ {0, 1}h

Introduction à la cryptographie Vincent Itier

Partie 3 : Fonctions de hachages : Signatures et fonctions de hachage

Hachage 90

Fonction de hachage cryptographique :

à une donnée de taille arbitraire, associe une image de taille
fixe
pratiquement impossible à inverser (fonctions à sens unique)
Propriétés d’un système idéal :
Calcul rapide de la valeur de hachage d’un message
Impossible, pour une valeur de hachage donnée, de construire
un message ayant cette valeur de hachage
Impossible de modifier un message sans changer sa valeur de
hachage
Impossible de trouver deux messages différents ayant la même
valeur de hachage

Introduction à la cryptographie Vincent Itier

Partie 3 : Fonctions de hachages : Signatures et fonctions de hachage

Hachage 91

Fonction de hachage cryptographique à clef :

une clé est utilisée pour calculer l’empreinte
Propriétés :
un même message à plusieurs empreintes en fonction de la clef
utilisée

Introduction à la cryptographie Vincent Itier

Partie 3 : Fonctions de hachages : Signatures et fonctions de hachage

Hachage en pratique 92

Vérification d’intégrité d’un fichier

Stockage de mots de passe
Génération pseudo-aléatoires et dérivation de clefs
...

Que faire si deux personnes ont le même mot de passe ?

Introduction à la cryptographie Vincent Itier

Partie 3 : Fonctions de hachages : Signatures et fonctions de hachage

Attaques 93

Types d’attaques :
Collision :
Deux messages quelconques qui ont le même haché
trouver M1 et M2 tel que H(M1 ) = H(M2 )
Secondes pré-images :
A partir d’une empreinte fabriquer un message dont le haché
soit cette empreinte :
M1 donné, trouver M2 tel que H(M1 ) = H(M2 )

Introduction à la cryptographie Vincent Itier

Partie 3 : Fonctions de hachages : Attaque des anniversaires

Paradoxe des anniversaires 94

Combien faut-il de personne pour avoir au moins 50% de

chance d’obtenir deux personnes ayant la même date de
naissance ?

Introduction à la cryptographie Vincent Itier

Partie 3 : Fonctions de hachages : Attaque des anniversaires

Paradoxe des anniversaires 94

Combien faut-il de personne pour avoir au moins 50% de

chance d’obtenir deux personnes ayant la même date de
naissance ?

23 ! (40 : 90%)

Introduction à la cryptographie Vincent Itier

Partie 3 : Fonctions de hachages : Attaque des anniversaires

Attaque des anniversaires 95

La résistance aux collisions d’une fonction de hachage est
bornée par le paradoxe des anniversaires.
Soit un haché codé sur b bits : 2b haché possibles
k messages différents
La probabilité que 2 messages aient le même haché :
    
1 2 k−1
P =1− 1− b 1 − b ... 1 −
2 2 2b

Approximation de l’égalité de Taylor :

 
 x −x
1− b ∼e 2b
2
Alors :  
−k(k−1)
1
e 2b ≤
2
Introduction à la cryptographie Vincent Itier
Partie 3 : Fonctions de hachages : Attaque des anniversaires

Attaque des anniversaires 96

Exemples :
Taille du haché (en bits) Nombre de messages à essayer
8 13
16 213
32 54562
64 9.6 × 109
128 1.5 × 1019
160 1.0 × 1024
256 2.8 × 1038
En pratique :
MD5 : 128 bits, soit une attaque avec 264 messages.
SHA-1 : 160 bits, soit une attaque avec 280 messages (25
millions de milliard de Go)

Introduction à la cryptographie Vincent Itier

Partie 3 : Fonctions de hachages : Cryptanalyse

Cryptanalyse des fonctions connues 97

MD2 : collisions, préimages

MD4 proposé par Rivest en 1990 : collisions connues
MD5 : collision connues
RIPEMD, HAVAL : collisions
SHA-0 : collision connues
SHA-1 : attaques théoriques
SHA-2 (224, 256, 384, 512) : considéré comme sûr

Introduction à la cryptographie Vincent Itier

Procédés de signature
Partie 3 : Procédés de signature : Introduction

La signature numérique 99

5 caractéristiques d’une signature :

Authentique
Infalsifiable
Non réutilisable
Inaltérable
Irrévocable

Introduction à la cryptographie Vincent Itier

Partie 3 : Procédés de signature : Introduction

La signature numérique 100

Même fonction qu’une signature manuscrite : engager la

responsabilité du signataire sur le contenu du message signé.
Cette signature ne doit pas pouvoir être reniée et doit être
vérifiable par tout le monde.
Un utilisateur peut prouver qu’il est celui qu’il prétend être ou
qu’il a le droit daccéder à un service.

Introduction à la cryptographie Vincent Itier

Partie 3 : Procédés de signature : Introduction

La signature numérique 101

Le cahier des charges d’une signature est :

elle doit être calculable par le signataire pour tout message m,
tout individu (surtout le destinataire) peut la vérifier,
elle doit être impossible à falsifier,
l’expéditeur ne doit pouvoir affirmer que sa signature a été
imitée.

Introduction à la cryptographie Vincent Itier

Partie 3 : Procédés de signature : Introduction

Crypto vs. Signatures 102

But traditionnel de la crypto : assurer la confidentialité.

Autre application : les signatures introduites par Diffie et Hellman.
But des signatures : garantir intégrité et authentification.
Signature dépend de lid. du signataire et du contenu du message.

La signature empêche deux types de fraudes :

la falsification de la signature par le destinataire,
la non-reconnaissance du message par lexpéditeur.

Introduction à la cryptographie Vincent Itier

Partie 3 : Procédés de signature : Introduction

Mécanisme des signatures 103

Une signature est composée de 3 algos :

génération de clés (sk, pk) noté gen
signature (privée) noté sig qui, pour une clé fixée sk, retourne
une signature s pour un clair m :

sigsk (m) = s

vérification (déterministe et publique) noté ver qui, à une clé

fixée pk et pour tout couple clair/signature (m, s) va vérifier
si la signature correspond bien au clair.

vrai si s = sigsk (m)
verpk (m, s) =
f aux si s 6= sigsk (m)

Introduction à la cryptographie Vincent Itier

Partie 3 : Procédés de signature : La signature EL Gamal

La signature EL Gamal 104

1985, base du standard de signature électronique : DSS.

Non déterministe.
Sa sécurité repose (on estime) sur le problème du logarithme
discret.

Introduction à la cryptographie Vincent Itier

Partie 3 : Procédés de signature : La signature EL Gamal

La signature EL Gamal 105

Soit p est un (grand) nombre premier, g est un générateur de

(Z/pZ)∗ , a est un entier tel que a ∈ [0, p − 2] et A = g a .

Alice publie p, g et A.

Pour un k ∈ (Z/(p − 1)Z)∗ la fonction de signature est :

(
K = g k [p]
sig(m) = (K, S) où .
S = (m − aK)k −1 [p − 1]
la fonction de vérification :

ver(m, K, S) = vrai ⇐⇒ AK K S = g m [p].

Preuve : dans Z/pZ on a K S = g kS = g m−aK puisque g p−1 = 1
et AK = g aK donc AK K S = g m .

Introduction à la cryptographie Vincent Itier

Partie 3 : Procédés de signature : La signature de document

La signature de document 106

Alice souhaite envoyer un document signé à Bob :
Elle génére l’empreinte du document (hachage)
Elle chiffre cette empreinte avec une clé (privée / publique ?)
Elle envoie le document et la signature à Bob.
Bob souhaite vérifier la validité du document :
Il déchiffre la signature
Si ça ne fonctionne pas document pas envoyé par Alice.
Il génère l’empreinte du document qu’il a reçu (même
hachage)
Il compare l’empreinte générée et celle issue de la signature
Empreintes identiques :
Alice a envoyé le document
Document non modifié depuis qu’Alice l’a signé
Empreintes différentes :
Document modifié depuis sa signature par Alice
Ce n’est pas ce document qu’Alice a signé
Introduction à la cryptographie Vincent Itier
Partie 3 : Procédés de signature : Procédés d’identification

Signer avec RSA 107

Bob désire envoyer un message M signé à Alice. Paramètres RSA :

Privés Publics
Alice dA nA , e A
Bob dB nB , e B

Procédé de signature :

sigsk (M ) = M dB mod nB = S

Vérification :

versk (M, S) = vrai ⇔ S eB ≡ M mod nB

Introduction à la cryptographie Vincent Itier

Partie 3 : Procédés de signature : Procédés d’identification

Procédés d’identification 108

Clé privé :
Bob veut s’assurer de l’identité d’Alice : il lui envoie un challenge à
réussir pour le prouver !

Déchiffrer un message choisi aléatoirement par Bob et ainsi

prouver qu’elle connait bien K sans le révéler.

L’écoute de la conversation ne permet pas à Eve de pouvoir se

faire passer pour Alice.

Application : utilisé par les cartes bancaires pour certaines

transactions.
Quelle précaution doit prendre Bob ?
Introduction à la cryptographie Vincent Itier
Partie 3 : Procédés de signature : Procédés d’identification

Procédés d’identification 109

Clé publique :
Le secret dAlice est sa clé privée.

Preuve en signant ou en déchiffrant une valeur aléatoire proposée

par Bob.

Identification par signature

Identification par déchiffrement

Exemple : Procédé didentification de Guillou-Quisquater.

Introduction à la cryptographie Vincent Itier
Distribution de clef et mise en accord
Partie 3 : Distribution de clef et mise en accord : Diffie-Hellman

Protocole de Diffie-Hellman (1976) 111

1) Alice et Bob choisissent un grand nombre premier p et dun entier 1 ≤ a < p

2) Alice choisit secrètement xA 2) Bob choisit secrètement xB

3) Alice calcule yA = axA (mod p) 3) Bob calcule yB = axB (mod p)

4) Alice et Bob séchangent les valeurs de yA et yB

xA xB
5) Alice calcule yB = (axB )xA 5) Bob calcule yA = (axA )xB
xB xA xA xB
=a (mod p) = K =a (mod p) = K

Sur quoi repose la sécurité de léchange des clefs ?

Introduction à la cryptographie Vincent Itier

Partie 4
Cryptographie post-quantique
Partie 4 : Cryptographie post-quantique :

Cryptographie post-quantique 114

Quelle est la sécurité de l’information face à un attaquant

disposant d’un calculateur quantique ?

En 1995, Peter Shor publie un algorithme permettant de résoudre

le problème du logarithme discret et le problème de la
factorisation des entiers en temps polynomial et espace
logarithmique.

Les algorithmes à clef publique :

reposant sur la factorisation peuvent être considérés cassés
par un attaquant quantique : RSA, . . .
reposant sur la difficulté du calcul d’un logarithme discret
peuvent être considérés cassés par un attaquant quantique :
Diffie-Hellman, ElGamal, . . .

Introduction à la cryptographie Vincent Itier

Partie 4 : Cryptographie post-quantique :

Le protocole BB84 115

Le protocole d’échange de clés BB84[1] s’appuie sur deux principes

quantiques :
on peut mesurer, sur un qubit, deux propriétés appelées des
"observables", qui ne peuvent prendre, chacune, que deux
valeurs distinctes
les deux observables doivent être incompatibles, la
connaissance précise de l’une empêche la connaissance précise
de l’autre

Pour l’exemple nous utiliserons des pulls quantiques [2]

[1] Charles Bennett et Gilles Brassart, 1984.

[2] http://images.math.cnrs.fr/A-la-decouverte-de-la-cryptographie-quantique.html

Introduction à la cryptographie Vincent Itier

Partie 4 : Cryptographie post-quantique :

Le protocole BB84 116

Les pulls quantiques observables incompatibles :

couleur : bleue ou rouge
taille : M ou L

Idée :
Alice possède deux armoires : une avec les pulls rangés par
Couleur l’autre par taille
Alice envoie un grand nombre de pulls à Bob, en déterminant
soit sa couleur, soit sa taille
Bob ne sait pas quand il reçoit quel observable est déterminé
Bob décide d’observer un des deux
Un code existe : 1 rouge et 0 bleue ; ainsi que 1 pour L et 0 pour M

Introduction à la cryptographie Vincent Itier

Partie 4 : Cryptographie post-quantique :

Le protocole BB84 117

Etape 1 :
Alice décide quels pulls envoyer à Bob.
Deux séquence aléatoires de n valeurs binaire correspondant pour
une au choix de l’observable et l’autre à la valeur :

Numéro du pull 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
C C T T T C T C T C C C T T C T C T C C
Tableau d’Alice
1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 1

Introduction à la cryptographie Vincent Itier

Partie 4 : Cryptographie post-quantique :

Le protocole BB84 118

Etape 2 :
Bob décide s’il regarde la Taille ou la Couleur de chaque pull
qu’il reçoit avec une séquence aléatoire
Bob observe la Taille ou la Couleur de chaque pull qu’il reçoit

Numéro du pull 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T C T C T T C C T T C C C T C C T T C T
Tableau de Bob
0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 1

Introduction à la cryptographie Vincent Itier

Partie 4 : Cryptographie post-quantique :

Le protocole BB84 119

Etape 3 :
Alice et Bob se communiquent la liste des C ou T
Ils ne communiquent PAS la liste des 0 ou 1

Numéro du pull 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
C C T T T C T C T C C C T T C T C T C C
Tableau d’Alice
1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 1
T C T C T T C C T T C C C T C C T T C T
Tableau de Bob
0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 1

ils savent donc tous les deux si Bob a mesuré lobservable qui était
fixée dans le pull envoyé par Alice !

La clé correspond au bits communs !

Introduction à la cryptographie Vincent Itier

Partie 4 : Cryptographie post-quantique :

Le protocole BB84 120

Attaques :
Eve intercepte l’échange des séquences de C ou T ?

Numéro du pull 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
C C T T T C T C T C C C T T C T C T C C
Tableau d’Eve
T C T C T T C C T T C C C T C C T T C T

Eve écoute aux portes ? :

elle modifie l’observation faîte par Bob
Eve fait une copie ? :
propriété quantique : théorème du non-clonage

Introduction à la cryptographie Vincent Itier

Conclusion
sion : :

Conclusions 122

Introduction aux notions et bases de cryptographie

Cryptographie multimedia
Cryptographie quantique ?

Introduction à la cryptographie Vincent Itier