L'irruption de méthodes mathématiques sophistiquées en cryptographie remonte à l'introduction de la cryptographie à clé publique par Diffie et Hellman en 1976. Cette méthode, reposant sur une dissymétrie entre la clé de chiffrement supposée disponible pour tous et la clé de déchiffrement, réservée à l'utilisateur légitime, est encore aujourd'hui illustrée par un très petit nombre d'exemples, le principal étant le système RSA, du nom de ses auteurs Rivest, Shamir et Adleman.
Cela dit, et contrairement à une opinion répandue, la cryptographie à clé publique ne sert pas seulement, et sans doute même pas principalement, à chiffrer. Elle autorise diverses autres fonctionnalités riches d'applications
Comme on vient de le dire, les deux principaux schémas de signature à clé publique sont le RSA et le DSS. Pour ces deux schémas, le signeur doit effectuer une exponentiation modulaire. Or, en pratique, ces signatures sont souvent effectuées par des cartes à puces qui ont une puissance de calcul très limitée qui ne leur permet pas de réaliser en un temps raisonnable ces exponentiations. Une alternative à ce problème est d'utiliser la puissance de calcul d'un serveur (terminal bancaire, téléphonique, etc) en lui déléguant des calculs. Cette idée a été introduite en 1988 par Matsumoto, Kato et Imai. Mais aucun des protocoles existant n'étaient sécurisés. En collaboration avec Jean-Jacques Quisquater (Université Catholique de Louvain, Belgique), nous avons pu proposer des méthodes d'accélération plus sures, tant pour le RSA ([BQ94a,BQ95]) que pour le DSS ([BQ94b]).
Au plan pratique, Fiat et Shamir ont donné en 1986 une application de la notion de protocole zero-knowledge en imaginant un procédé d'identification fondé sur l'utilisation d'une clé secrète mais ne révélant aucune information (en particulier pas la clé, au contraire des méthodes du type mot-de-passe). Le GRECC a examiné la possibilité d'arriver à un résultat analogue en n'autorisant que des calculs très simples. Dans cet ordre d'idées, l'équipe a récemment mis au point toute une série de protocoles d'identification simples :
uvre de codes correcteurs d'erreurs ([Ste93b]).
-complet, inspiré de la théorie des réseaux de
neurones
([Poi95]).
L'analyse cryptographique est la partie de la cryptographie qui s'efforce de recouvrer la partie secrète d'un message, d'un code ou d'un outil cryptographique, à partir des éléments publics. Une méthode très efficace en ce domaine est la recherche de relations de dépendance linéaires à coefficients modérés en utilisant l'algorithme de Lenstra, Lenstra et Lovàsz (LLL), mentionné plus haut. Comme on l'a mentionné plus haut, le GRECC s'est doté d'une implantation performante de LLL qui lui permet d'expérimenter les algorithmes, issus d'une analyse théorique et de les valider. La liste des <<cryptanalyses>> les plus récentes à l'actif du groupe est le suivante :
93]) avec les équipes de Schnorr (Francfort) et
Odlyzko (Bell Labs).
En dehors des méthodes utilisant l'algorithme LLL, nous nous sommes intéressés à l'analyse de la sécurité des système basés sur la difficulté du décodage général des codes linéaires (système de Mc Eliece et, plus récemment procédé d'identification de Stern, mentionné plus haut). En utilisant des algorithmes existant et en les optimisant, il a été possible d'améliorer les performances des attaques contre le cryptosystème de McEliece. Il ne s'agit pas à proprement parler de cryptanalyse puisque le système n'est pas cassé mais les paramètres minimaux assurant la sécurité sont ainsi plus finement évalués. Un travail analogue pour le procédé de Stern a aussi été mené dans [Cha94]. De nouveaux développements ont été soumis à Eurocrypt'95 [CC].
Nous avons également, dans un travail mené avec Don Coppersmith (IBM Yorktown), montré qu'un procédé de signature introduit par Adi Shamir et basé sur les permutations birationnelles, pouvait être attaqué avec succès ([CSV94]). Notre cryptanalyse utilise des méthodes empruntées à la théorie de Galois et, là encore, permet des calculs explicites. Adi Shamir a cité notre travail comme le meilleur publié en cryptographie durant l'année 1993. Nous lui laissons bien entendu la responsabilité de cette assertion mais notons avec plaisir qu'elle montre la notoriété internationale que le GRECC a acquise en peu d'années dans le domaine de la cryptologie.