Ecole Normale Superieure Universite Paris

De
Publié par

Niveau: Supérieur, Doctorat, Bac+8
Ecole Normale Superieure Universite Paris 7 Departement d'Informatique Groupe de Recherche En Complexite et Cryptographie Le partage de cles cryptographiques : Theorie et Pratique THESE presentee et soutenue publiquement le 4 Octobre 2001 pour l'obtention du Doctorat de Paris 7 par Pierre-Alain Fouque Composition du jury Rapporteurs : Rosario Gennaro (I.B.M. T.J. Watson) Marc Girault (France Telecom R&D) Moti Yung (Universite de Columbia) Examinateurs : Anca Musholl (LIAFA - Paris 7) Jacques Patarin (Schlumberger - Universite de Versailles) David Pointcheval (ENS - CNRS) Jacques Stern (ENS - Directeur de These) Departement d'Informatique de l'Ecole Normale Superieure, 45 Rue d'Ulm 75005 PARIS

  • superieure universite

  • departement d'informatique de l'ecole normale

  • anca muscholl

  • ju- lien olivain


Publié le : lundi 1 octobre 2001
Lecture(s) : 176
Source : di.ens.fr
Nombre de pages : 218
Voir plus Voir moins

´Ecole Normale Sup´erieure Universit´e Paris 7
D´epartement d’Informatique
Groupe de Recherche En Complexit´e et Cryptographie
Le partage de cl´es cryptographiques:
Th´eorie et Pratique
`THESE
pr´esent´ee et soutenue publiquement le 4 Octobre 2001
pour l’obtention du
Doctorat de Paris 7
par
Pierre-Alain Fouque
Composition du jury
Rapporteurs : Rosario Gennaro (I.B.M. T.J. Watson)
Marc Girault (France T´el´ecom R&D)
Moti Yung (Universit´e de Columbia)
Examinateurs : Anca Musholl (LIAFA - Paris 7)
Jacques Patarin (Schlumberger - Universit´e de Versailles)
David Pointcheval (ENS - CNRS)
Jacques Stern - Directeur de Th`ese)
´D´epartement d’Informatique de l’Ecole Normale Sup´erieure, 45 Rue d’Ulm 75005 PARISRemerciements
Je remercie tout d’abord vivement Jacques Stern pour son encadrement scientifique rigoureux, pour la
chance qu’il m’a offerte de faire de la recherche dans d’aussi bonnes conditions et pour son amitié. Je
remercie ensuite chaleureusement tous les membres du GRECC et plus particulièrement Guillaume et
David pour leurs nombreuses explications, leurs grandes disponibilités, les travaux effectués ensemble,
les moments passés dans le bureau ou ailleurs (piscines, ...), et finalement le travail de relecture.
L’équipe de Complexité et Cryptographie de l’ENS, son directeur Jacques Stern, ses chercheurs perma
nents David Pointcheval, Louis Granboulan, Phong Nguyen, ses anciens membres Serge Vaudenay, ses
nombreux thésards que j’ai pu cotoyer Guillaume Poupard, Thomas Pornin, Olivier Baudron, Emma
nuel Bresson, et ses stagiaires Yves Verhoeven, ... sont un milieu idéal pour faire de la recherche en
Cryptographie.
Je suis aussi redevable à l’entreprise CS Communication & Systèmes puis à sa filiale TrustyCom de
m’avoir permis de mettre en pratique la cryptographie et de travailler sur différents projets et produits
intéressants comme les PKIs, la signature électronique ou la sécurisation des protocoles réseaux. Je
remercie toutes les personnes avec qui j’ai eu le plaisir de travailler Sylvain Blonde, Jérôme Lubrez,
Jean Pierre Garnier, Moïse Moyal, Caroline Gerrebout, Pierre Tsagouria, Oualid Ammar, Jean François
Wiorek, Mustapha Allaf, Patrick Dessarps, Didier Virlogeux, Véronique Delebarre, Widad Chatraoui, Ju
lien Olivain, Jean Pierre Gauthier, ceux que j’oublie. Je remercie en particulier Marc Milan, le “mentor”
de l’activité sécurité pendant de longues années.
J’exprime ma gratitude à Rosario Gennaro, Marc Girault et Moti Yung pour avoir effectué le lourd travail
de rapporteurs et je remercie Anca Muscholl et Jacques Patarin d’avoir accepté de participer à mon jury.
Merci à Joëlle et Valérie pour leur soutien quotidien.
Enfin, j’exprime mes remerciements les plus chers à Gwenaëlle pour son attention, ses nombreux encou
ragements et conseils et pour le bonheur et la joie qu’elle me procure.
12À mes parents, Catherine et Anne, et Gwenaëlle,
34Table des matières
Table des figures 11
Notations 13
Introduction 15
1 Objectifs de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Authentification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Intégrité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Confidentialité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Disponibilité de service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6 La cryptographie et la vie réelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Partie I Introduction à la cryptologie partagée 23
Chapitre 1 Généralités de cryptographie moderne 25
1.1 Introduction à la moderne . . . . . . . . . . . . . . . . . . . . . . . 25
1.2 Rappels de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.2.1 Problèmes et langages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.2.2 Machines de Turing et algorithmes . . . . . . . . . . . . . . . . . . . . . . 27
1.2.3 Classes de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.4 Machines de Turing à oracle et réductibilité . . . . . . . . . . . . . . . . . 31
1.2.5 Fonctions à sens unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.3 Fonctions conjecturées à sens unique . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.3.1 Problèmes liés à la factorisation . . . . . . . . . . . . . . . . . . . . . . . . 35
1.3.2 liés au calcul du logarithme discret . . . . . . . . . . . . . . . . 36
1.4 Modèle de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.4.1 Hypothèses sur le canal de communication . . . . . . . . . . . . . . . . . . 37
51.4.2 Classification des adversaires . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.4.3 Arguments de sécurité dans le modèle de l’oracle aléatoire . . . . . . . . . . 37
1.4.4 Sécurité d’un système de chiffrement . . . . . . . . . . . . . . . . . . . . . 38
1.4.5 d’un schéma de signature . . . . . . . . . . . . . . . . . . . . . . 44
Chapitre 2 Généralités sur la cryptographie partagée 49
2.1 Introduction à la partagée . . . . . . . . . . . . . . . . . . . . . . . . 50
2.1.1 Cryptographie interactive . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.1.2 Classification des protocoles distribués . . . . . . . . . . . . . . . . . . . . 53
2.1.3 Quelques résultats constructifs de cryptographie interactive . . . . . . . . . 56
2.2 Outils de cryptographie partagée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2.1 Partage additif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2.2 Partage polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.2.3 Partage de secret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.2.4 Preuves interactives et zero knowledge . . . . . . . . . . . . . . . . . . . . 62
2.2.5 Partage de secret publiquement vérifiable . . . . . . . . . . . . . . . . . . . 70
2.3 Partage de fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.3.1 Propriétés des schémas cryptographiques de partage de fonction . . . . . . . 71
2.3.2 Sécurité d’un système de chiffrement partagé . . . . . . . . . . . . . . . . . 72
2.3.3 Exemple : Partage de déchiffrement El Gamal . . . . . . . . . . . . . . . . 74
2.3.4 Sécurité d’un schéma de signature . . . . . . . . . . . . . . . . . . . . . . 75
2.4 Partage proactif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.4.2 Exemples de schémas proactifs . . . . . . . . . . . . . . . . . . . . . . . . 77
Partie II Cryptographie à seuil 79
Chapitre 3 Partage du cryptosystème RSA 81
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.2 Signature RSA partagée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.2.1 Historique des schémas de partage RSA . . . . . . . . . . . . . . . . . . . 83
3.2.2 Schéma de signature RSA à seuil de Shoup . . . . . . . . . . . . . . . . . . 87
3.2.3 Preuve de sécurité du schéma de Shoup contre des adversaires passifs . . . . 88
3.2.4 Preuve de robustesse contre des adversaires actifs . . . . . . . . . . . . . . 89
3.3 Algorithme de génération partagée de clés RSA de Boneh Franklin . . . . . . . . . 91
3.3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.3.2 Preuve de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
63.4 Schéma complètement distribué de signature RSA à seuil . . . . . . . . . . . . . . 93
3.4.1 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.4.2 Modèle de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.4.3 Nouvel algorithme de génération de clé RSA . . . . . . . . . . . . . . . . . 96
3.4.4 Sécurité du schéma de signature contre un adversaire passif . . . . . . . . . 102
3.4.5 Sécurité du schéma de contre un adversaire actif . . . . . . . . . . 104
3.4.6 Paramètres pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.5 Autre solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Chapitre 4 Partages du cryptosystème de Paillier 111
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.2 Rappels sur les algorithmes de chiffrement homomorphe . . . . . . . . . . . . . . . 112
4.2.1 Le cryptosystème Goldwasser Micali . . . . . . . . . . . . . . . . . . . . . 112
4.2.2 Le de Benaloh et Fisher . . . . . . . . . . . . . . . . . . . . 113
4.2.3 Le cryptosystème Naccache Stern . . . . . . . . . . . . . . . . . . . . . . . 113
4.2.4 Le d’Okamoto Uchiyama . . . . . . . . . . . . . . . . . . . 114
4.2.5 Le cryptosystème de Paillier . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.3 Première proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.3.1 Sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.3.2 Description du cryptosystème de Paillier distribué . . . . . . . . . . . . . . 119
4.3.3 Algorithme de génération des clés . . . . . . . . . . . . . . . . . . . . . . . 119
4.3.4 Preuve de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.3.5 Partage complet du déchiffrement de Paillier . . . . . . . . . . . . . . . . . 123
4.4 Seconde proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Chapitre 5 Cryptosystèmes partagés sûrs contre les attaques à chiffrés choisis 127
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.1.1 Sécurité contre les attaques à chiffrés choisis . . . . . . . . . . . . . . . . . 128
5.1.2 Problématique du partage de cryptosystèmes IND-CCA . . . . . . . . . . . 128
5.1.3 Solutions existantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.1.4 Preuves Zero Knowledge Non Interactives . . . . . . . . . . . . . . . . . . 130
5.1.5 Proposition de schémas IND-CCA à seuil . . . . . . . . . . . . . . . . . . 131
5.2 Modèle de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.2.1 Hypothèses sur le canal de communication . . . . . . . . . . . . . . . . . . 131
5.2.2 Classification des adversaires . . . . . . . . . . . . . . . . . . . . . . . . . 132
75.2.3 Systèmes de chiffrement à seuil . . . . . . . . . . . . . . . . . . . . . . . . 132
5.2.4 Notions de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.3 Conversion générique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.3.2 Preuve Non Interactive Zero Knowledge . . . . . . . . . . . . . . . . . . . 135
5.3.3 Preuve de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.3.4 Adversaire passif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.3.5 Adversaire actif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.4 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.4.1 Cryptosystème El Gamal . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.4.2 de Paillier . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Chapitre 6 Partage d’un générateur de clés Diffie Hellman 143
6.1 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.1.1 Protocole de Pedersen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.1.2 Attaque du schéma de Pedersen . . . . . . . . . . . . . . . . . . . . . . . . 145
6.2 Nouvelle proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.2.1 Modèle et exigences de sécurité . . . . . . . . . . . . . . . . . . . . . . . . 147
6.2.2 Preuve de chiffrement équitable . . . . . . . . . . . . . . . . . . . . . . . . 148
6.2.3 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.2.4 Preuve de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.2.5 Complexité du protocole . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.2.6 Améliorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Partie III Applications 157
Chapitre 7 Application à la loterie et au vote électronique 159
7.1 Un schéma de loterie électronique . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.1.2 Exemple de réalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.2 Protocoles de vote électronique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.2.1 Exigences de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.2.2 Techniques générales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.3 Nouveau système de vote électronique . . . . . . . . . . . . . . . . . . . . . . . . 168
7.3.1 Organisation de l’élection . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
8

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.