Thèse
La Géométrie des Nombres en Cryptologie
La cryptologie est la science millénaire du secret, dont l'importance s'est accrue avec le développement des réseaux informatiques et du commerce électronique. Elle permet notamment d'assurer la confidentialité des communications au moyen du chiffrement, et l'authentification des documents numériques grâce a la signature électronique.
La géometrie des nombres est une branche de la théorie de nombres fondée il y a un siècle par Hermann Minkowski comme un pont entre la géometrie, l'approximation diophantienne, et l'étude des formes quadratiques. Ses développements algorithmiques, marqués par l'apparition au début des années 80 de l'algorithme de Lenstra-Lenstra-Lovász (LLL), ont eu des applications spectaculaires en cryptanalyse, c'est-à-dire dans l'attaque des procédés cryptographiques. Paradoxalement, les problèmes algorithmiques de la géométrie des nombres sont à la base de nouveaux systèmes cryptographiques, suite aux avancées récentes réalisées par Miklós Ajtai en théorie de la complexité.
Cette thèse présente de nouvelles techniques issues de la géometrie des nombres, en particulier la notion de réseau orthogonal, qui permettent d'attaquer avec succès plusieurs systèmes de chiffrement et de signature électronique proposés ces dernières années. Dans une première partie, nous attaquons des systèmes de chiffrement fondés sur le problème dit du sac à dos : les cryptosystèmes de Qu-Vanstone (Certicom) et d'Itoh-Okamoto-Mambo (JAIST). Dans une deuxième partie, nous attaquons des systèmes de chiffrement à base de problèmes algorithmiques de la géometrie des nombres : les cryptosystèmes d'Ajtai-Dwork (IBM) et de Goldreich-Goldwasser-Halevi (MIT). Enfin, dans une troisième et dernière partie, nous attaquons des schémas d'accélération de signature électronique : le schéma de signature RSA assistée de Béguin-Quisquater (UCL) et le schéma d'accélération de Boyko-Peinado-Venkatesan (Microsoft et MIT) destiné aux signatures à base de logarithme discret.