Etude d'outils algébriques et combinatoires pour la
cryptographie à clef publique
Ludovic Perret
Ludovic.Perret@inria.fr
Thèse de Doctorat, Université de Marne-la-Vallée,
17 Octobre 2005, 170 pages.
Ph.D. Thesis of Marne-la-Vallée
university, defended october 17th, 2005, 170 pages.
Résumé
Cette thèse, dont le sujet est l'étude d'outils algébriques et
combinatoires pour la cryptographie à clef publique, se place dans le
contexte général de l'analyse de problèmes alternatifs aux problèmes de la
théorie des nombres. Ici, nous avons étudié
deux types de problèmes : ceux liés à des équivalences de polynômes et
ceux reliés à la combinatoire des mots.
Les problèmes d'Équivalence de Polynômes
La cryptographie multivariée, c'est-à-dire la cryptographie utilisant des
polynômes à plusieurs variables, offre un éventail relativement
large de problèmes difficiles. C'est à un type de problèmes de cette
famille qu'appartiennent les problèmes d'Équivalence de Polynômes.
Dans la première partie de cette thèse, nous étudions deux aspects
complémentaires de ces problèmes : à savoir leurs difficulté
théorique et leurs résolution pratique:
- D'un point de vue complexité théorique, nous montrons notamment que ces
problèmes sont en général au moins aussi difficiles que le
problème de l'Isomorphisme de Graphes. D'autre part, une vision unifiée de
ces problèmes nous permet de donner une preuve
originale que ces problèmes ne sont pas NP-durs.
- D'un point de vue pratique, nous étudions un problème d'Équivalence de
Polynômes particulier. Nous avons appelé ce problème Équivalence
Linéaire de Polynômes (PLE). Brièvement, celui-ci consiste à retrouver un
changement de variables linéaire entre deux ensembles de
polynômes multivariés. Notons que la difficulté de ce problème garantit la
sécurité d'un schéma d'authentification (resp. de signature).
Nous présentons pour ce problème deux types d'algorithmes : le premier
utilisant une approche géométrique de ce problème, et le second
reposant sur une caractérisation différentielle de l'Équivalence Linéaire
de Polynômes.
Sur la sécurité de systèmes basés sur les mots
Dans la deuxième partie de cette thèse, nous présentons le travail réalisé
sur deux systèmes de chiffrement basés sur les mots.
Concernant le premier schéma, celui de P.J. Abisha, D.G. Thomas et K.G.
Subramanian, nous présentons deux algorithmes permettant de
résoudre le problème sur lequel repose la sécurité de ce système. Dans le
contexte d'une attaque à chiffré choisi, nous montrons en outre
comment construire efficacement une clef équivalente à la clef secrète.
Finalement nous montrons que le schéma de L. Siromoney et
R. Mathew est également vulnérable à une attaque à chiffré choisi. Nos
résultats prouvent ainsi la faiblesse de ces deux schémas.