Preuves de sécurité et problèmes difficiles en cryptologie : études de cas
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Provable security enables to formalize what is expected from a cryptographic primitive, and to prove that some mechanisms actually meet these expectations. Security proofs neverthe-less rely on the hypothesis that some reference algorithmic problems are hard to solve. These hardness hypotheses are primarily justified by the lack of efficient algorithms to solve the corre-sponding problems. In the first part of this thesis, we study some authenticated key exchange protocols. After a close look to the security model involved, we prove the security of two classical protocols, MTI/CO and MQV, which was up to now only studied empirically. Then, we show how to extend the adversarial model to include active compromises. Neither MQV, nor HMQV, which is a proved variant of MQV, withstand these attacks. We propose a new protocol that solves this problem with a round and computational complexity similar to the one of MQV. In the second part of this thesis, we turn our attention to solving Systems of multivariate equations on a finite field. Several public key cryptosystems rely on the difficulty of this problem, for different families of Systems of equations. On the one hand, we cryptanalyze such a cryptosystem, TRMC. On the other hand, we improve a generic resolution algorithm, XL. The performance of the resulting algorithm is on par with the best currently known methods
Abstract FR:
La sécurité prouvée permet de formaliser ce que l'on attend d'un mécanisme cryptographique, et de prouver que certaines constructions répondent à ces attentes. Les preuves de sécurité reposent cependant sur des hypothèses de difficulté algorithmique de certains problèmes de référence. Ces hypothèses sont principalement fondées sur l'absence d'algorithme efficace pour résoudre les problèmes correspondants. Dans une première partie, nous étudions quelques protocoles d'échange de clé authentifié. Après un examen approfondi du modèle utilisé, nous effectuons la preuve de la sécurité de deux protocoles classiques, MTI/CO et MQV, qui n'était jusqu'à présent évaluée que de façon empirique. Nous montrons ensuite que la modélisation de l'adversaire peut être étendue pour inclure des compromissions actives. Ni MQV, ni HMQV qui en est une variante prouvée sûre, ne résistent à ces formes d'attaques. Nous proposons un nouveau protocole qui comble ces défauts avec une complexité de mise en œuvre similaire à MQV. Dans la seconde partie de cette thèse, nous nous intéressons à la résolution de systèmes d'équations polynomiales à plusieurs variables sur un corps fini. De nombreux cryptosystèmes à clé publique reposent sur la difficulté de ce problème, les systèmes à résoudre appartenant à des familles particulières. Notre travail porte d'une part sur une cryptanalyse d'un tel cryptosystème, TRMC, et d'autre part, sur l'amélioration d'un algorithme générique de résolution de systèmes, XL. Les performances de l'algorithme obtenu sont comparables à celles des meilleurs algorithmes actuels.