2004_preuve_cryptographique.pdf

(678 KB) Pobierz
Conception et preuves d’algorithmes
cryptographiques
Cours de magist`re M.M.F.A.I.
e
´
Ecole
normale sup´rieure
e
Jacques Stern
Louis Granboulan Phong Nguyen David Pointcheval
´
Edition 2004
2
Table des mati`res
e
1 Introduction ` la cryptologie
a
— par Jacques Stern
1.1
1.2
1.3
1.4
1.5
Qu’est ce que la cryptologie ? . . . . .
Cryptographie conventionnelle . . . . .
M´thodes statistiques de cryptanalyse .
e
Cryptographie ` cl´ publique . . . . . .
a e
Cryptographie et complexit´ . . . . . .
e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
7
10
11
13
2 Chiffrement par bloc et cryptanalyse diff´rentielle
e
— par Louis Granboulan
2.1
2.2
2.3
2.4
2.5
2.6
Modes d’op´ration . . . . . . . . . . . .
e
Principes de conception . . . . . . . . . .
´
Etude th´orique des sch´mas de Feistel .
e
e
Cryptanalyse diff´rentielle . . . . . . . .
e
Variantes de la cryptanalyse diff´rentielle
e
Autres techniques de cryptanalyse . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
18
25
29
30
34
36
3 Vingt-cinq ans d’attaques de RSA
— par Phong Nguyen
3.1
3.2
3.3
3.4
3.5
3.6
3. A
Le cryptosyst`me RSA . . . . . . . . . . .
e
RSA et la factorisation d’entiers . . . . . .
Attaques ´l´mentaires . . . . . . . . . . .
ee
Attaques sur les impl´mentations du RSA
e
Attaques simples du RSA ` petit exposant
a
Attaques ` base de g´om´trie des nombres
a
e e
L’algorithme LLL . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
44
46
47
50
51
53
65
4 La s´curit´ prouv´e en chiffrement asym´trique
e
e
e
e
— par David Pointcheval
4.1
4.2
4.3
4.4
4.5
4.6
La cryptographie asym´trique . . . . . .
e
Formalisation . . . . . . . . . . . . . . .
Les cryptosyst`mes RSA et Rabin . . . .
e
Le probl`me du logarithme discret . . . .
e
Le cryptosyst`me de El Gamal . . . . . .
e
Les attaques ` chiffr´s choisis adaptatives
a
e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
71
72
73
78
80
82
84
5 Zero-knowledge et identification
— par Jacques Stern
5.1
5.2
5.3
93
Motivation et exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Approche formelle du ZK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Preuves ZK d’identit´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
e
3
4
Chapitre 1
(2h)
Introduction ` la cryptologie
a
— par Jacques Stern
Sommaire
1.1
Qu’est ce que la cryptologie ? . . . . . . . . . .
1.1.1 Quelques d´finitions . . . . . . . . . . . . . . .
e
1.1.2 Quelques rep`res historiques . . . . . . . . . . .
e
Cryptographie conventionnelle . . . . . . . . .
1.2.1 Chiffrement et d´chiffrement . . . . . . . . . .
e
1.2.2 D´cryptement . . . . . . . . . . . . . . . . . . .
e
1.2.3 Chiffrement par bloc . . . . . . . . . . . . . . .
1.2.4 Chiffrement par flot . . . . . . . . . . . . . . .
1.2.5 Int´grit´ et authenticit´ . . . . . . . . . . . . .
e
e
e
M´thodes statistiques de cryptanalyse . . . . .
e
1.3.1 Cryptanalyse du chiffrement de Vigen`re . . .
e
1.3.2 Cryptanalyse du chiffrement de Geffe . . . . .
1.3.3 Tests d’hypoth`se . . . . . . . . . . . . . . . .
e
Cryptographie ` cl´ publique . . . . . . . . . .
a e
´e
1.4.1 El´ments de th´orie algorithmique des nombres
e
1.4.2 RSA . . . . . . . . . . . . . . . . . . . . . . . .
Cryptographie et complexit´ . . . . . . . . . . .
e
1.5.1 Machines de Turing polynomiales . . . . . . . .
1.5.2 R´duction et simulation . . . . . . . . . . . . .
e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
5
5
6
7
7
7
8
9
9
10
10
10
11
11
11
12
13
13
14
1.2
1.3
1.4
1.5
1.1
1.1.1
Qu’est ce que la cryptologie ?
Quelques d´finitions
e
La
cryptologie
est la science des messages secrets. Longtemps restreinte aux usages
diplomatiques et militaires, elle est maintenant une discipline scientifique ` part enti`re, dont
a
e
l’objet est l’´tude des m´thodes permettant d’assurer les services d’int´grit´, d’authenticit´
e
e
e
e
e
et de confidentialit´ dans les syst`mes d’information et de communication.
e
e
Un service d’int´
grit´
garantit que le contenu d’une communication ou d’un fichier n’a
e e
pas ´t´ modifi´. Par exemple, on peut souhaiter v´rifier qu’aucun changement du contenu
ee
e
e
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin