2007_cryptanalyse_clef_publique.pdf

(3493 KB) Pobierz
´
UNIVERSITE PARIS 7 – DENIS DIDEROT
UFR D’INFORMATIQUE
Th´orie et Pratique de la
e
Cryptanalyse ` Clef Publique
a
´
MEMOIRE
pr´sent´ et soutenu publiquement le 23 novembre 2007
e
e
pour l’obtention du
Diplˆme d’Habilitation ` Diriger des Recherches
o
a
(Sp´cialit´ Informatique)
e
e
par
˜
ˆ
NGUYEN Phong Quang
Composition du jury
Rapporteurs :
Christian Choffrut
Arjen K. Lenstra
Nigel P. Smart
Antoine Joux
Jean-Fran¸ois Mestre
c
Adi Shamir
Jean Vuillemin
Jacques Stern
Brigitte Vall´e
e
Examinateurs :
Directeur de recherche :
Pr´sidente :
e
´
Recherches effectu´es au Laboratoire d’Informatique de l’Ecole Normale Sup´rieure — UMR 8548
e
e
Avant-Propos
Ce document constitue le dossier en vue de l’obtention du diplˆme d’habilitation ` diriger des
o
a
recherches, soumis ` l’Universit´ de Paris 7 – Denis Diderot. Il est compos´ de trois parties :
a
e
e
1. Une synth`se sur le th`me principal de mes travaux effectu´s au cours de ces derni`res an-
e
e
e
e
n´es :
Th´orie et pratique de la cryptanalyse ` clef publique.
Cette synth`se se compose de trois
e
e
a
e
chapitres visant ` pr´ciser le contexte dans lequel s’inscrivent mes contributions : un premier
a e
chapitre introduisant la cryptologie ; un second chapitre pr´sentant la cryptanalyse ` clef pu-
e
a
blique ; et un troisi`me chapitre consacr´ ` la g´om´trie des nombres algorithmique, qui est
e
e a
e e
peut-ˆtre l’outil le plus populaire en cryptanalyse ` clef publique ;
e
a
2. Un curriculum vitæ et une liste compl`te de mes publications ;
e
3. Une annexe regroupant une s´lection de mes articles depuis ma th`se de doctorat, soit dans leur
e
e
version originale, soit dans leur version compl`te. Ces articles illustrent les diff´rents aspects de
e
e
la cryptanalyse moderne des syst`mes ` clef publique :
e
a
– L’algorithmique, notamment celle des r´seaux euclidiens (page 95). De nombreux algorithmes
e
sont particuli`rement utiles en cryptanalyse.
e
– L’´tude du probl`me calculatoire sous-jacent, par exemple via des r´ductions efficaces `
e
e
e
a
d’autres probl`mes mieux connus (page 207).
e
– L’exploitation de failles de conception (page 241).
– L’exploitation de failles d’impl´mentation (page 299).
e
Bien que ce document traite essentiellement de la cryptanalyse des syst`mes ` clef publique, la liste
e
a
compl`te de mes publications montre que mes contributions ne se limitent pas ` ce seul domaine.
e
a
J’ai en effet travaill´ sur plusieurs autres sujets, dont :
e
– La conception et l’analyse de s´curit´ de syst`mes ` clef publique ;
e
e
e
a
– La cryptanalyse de syst`mes ` clef secr`te : codes d’authentification ` base de fonction de
e
a
e
a
hachage, et chiffrement par flot.
i
Avant-Propos
ii
Table des mati`res
e
Partie I
Th´orie et pratique de la cryptanalyse ` clef publique
e
a
Chapitre 1
La Cryptologie Moderne : Fondements et Perspectives
1.1
1.2
1
2
3
3
3
4
4
4
5
6
6
7
7
8
9
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Qu’est ce que la cryptologie ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1
1.2.2
1.2.3
Quelques d´finitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
e
Rep`res historiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
e
Qu’est-ce que l’impossible ? . . . . . . . . . . . . . . . . . . . . . . . . . . .
Fonction ` sens unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a
Fonction de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
G´n´rateur d’al´a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
e e
e
Chiffrement et d´chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . .
e
D´cryptement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
e
Chiffrement par bloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chiffrement par flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3
La cryptographie sans secret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1
1.3.2
1.3.3
1.4
La cryptographie sym´trique ou ` clef secr`te . . . . . . . . . . . . . . . . . . . . .
e
a
e
1.4.1
1.4.2
1.4.3
1.4.4
1.4.5
Codes d’authentification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Chiffrement asym´trique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
e
Signature num´rique
e
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Preuve de connaissance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Quelle s´curit´ ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
e
e
iii
1.5
La cryptographie asym´trique ou ` clef publique . . . . . . . . . . . . . . . . . . . 10
e
a
1.5.1
1.5.2
1.5.3
1.5.4

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin