PICSI

Cryptographie à bas coût: les principaux algorithmes à clé publique

    Contrairement à la cryptographie à clé secrète, la cryptographie à clé publique (dite aussi cryptographie asymétrique) ne peut guère -on s'en doute- s'accommoder d'algorithmes secrets. Trois approches, foncièrement différentes, ont été tentées.

     La première consiste à conserver les problèmes mathématiques sur lesquels la plupart des systèmes existants reposent (factorisation, logarithme discret), et à accélérer ces derniers soit en y apportant  une amélioration substantielle, soit en les utilisant dans des modes opératoires particuliers. Les systèmes d'authentification GQ (1987) et GQ2 (1998) relèvent de la première catégorie. Reposant sur la factorisation, ils permettent à une carte à microprocesseur standard d'être rapidement authentifiée auprès d'un lecteur, avec une sécurité équivalente à celle de RSA. A l'inverse, les protocoles zero-knowledge fondés sur le logarithme discret, notamment Schnorr (1989) et GPS (1991), ne deviennent particulièrement performants que si on les utilise en mode dit "à coupons". Ce mode consiste à calculer antérieurement à la session d'authentification tout ce qui peut l'être, laissant un minimum d'opérations à effectuer pendant la session proprement dite. Cette première approche a pour avantage de continuer à faire reposer la sécurité sur des problèmes bien établis.

    Une deuxième approche consiste à exploiter des problèmes mathématiques de nature totalement différente. Elle est plus novatrice mais aussi plus risquée, car la sécurité des systèmes qui en sont issus est souvent mal comprise. Les trois (familles) de problèmes les plus prometteuses sont les suivantes. La plus ancienne, mais qui connaît actuellement un regain d'intérêt, provient de la théorie des codes correcteurs d'erreurs. En 1978, Mc Eliece a ouvert la voie en proposant un système de chiffrement fondé sur les codes de Goppa et, en 1993, Stern a spécifié le protocole d'authentification SD (du nom du problème sur lequel sa sécurité est fondée : Syndrome Decoding), qui est de type zero-knowledge. Ces schémas souffrent d'utiliser des paramètres publics de grande taille, mais des recherches très récentes visent à corriger ce défaut. Une deuxième famille est celle de ladite cryptologie multivariable, qui repose sur la difficulté de résoudre des systèmes d'équations quadratiques à coefficients dans un petit corps fini. Initiée par Matsumoto et Imaï, mais popularisée par Patarin, elle est actuellement l'objet de recherches intensives. En particulier, elle a fourni en 1999 le système de signature numérique SFLASH, qui, malgré sa clé publique longue, possède les principales caractéristiques d'un algorithme à  bas coût. Malheureusement, il a été cassé sept ans plus tard. Enfin, les réseaux euclidiens (ou lattices), qui ont longtemps été l'outil exclusif des cryptanalystes avec l'algorithme LLL, ont vers la fin des années 90 donné lieu à un nombre, très restreint il est vrai, de systèmes cryptographiques. Ainsi le système de chiffrement NTRU, dont il n'est pas exclu qu'il puisse être implanté dans une logique câblée, a-t-il fait l'effet en 1996 d'une petite révolution.
     Un autre avantage de cette deuxième  approche est de fournir des alternatives pour le jour, certes a priori lointain, où les ordinateurs quantiques existeront et rendront ipso facto faciles les problèmes de la factorisation et du logarithme discret.

    Enfin, il existe une dernière approche, intermédiaire entre les deux précédentes. Elle consiste à transposer des algorithmes anciens sur des structures mathématiques nouvelles, afin de gagner sur un terrain ou sur un autre. Elle est illustrée de manière spectaculaire par les courbes elliptiques. A priori, tout algorithme reposant sur la difficulté du logarithme discret dans un corps fini peut être "transporté" tel quel sur une courbe elliptique, car cette dernière jouit également d'une structure de groupe (la seule indispensable pour pouvoir énoncer le problème du logarithme discret). A titre d'exemple, il suffit de remplacer toutes les exponentielles dans le corps premier de base par des exponentielles dans une courbe elliptique pour que le DSA devienne l'EC-DSA. L'intérêt est de raccourcir notablement certains paramètres du  système, et en tout premier lieu la clé publique. Cela est possible car les algorithmes de calcul de logarithme discret s'essoufflent beaucoup plus vite sur les courbes elliptiques que sur les corps finis. Plus récemment, le système XTR a été annoncé, qui utilise un groupe multiplicatif particulier d'un corps fini dont le cardinal est une puissance sixième de sa caractéristique. Il offre des avantages analogues aux courbes elliptiques, tout en évitant de rentrer dans les complexités de la géométrie algébrique.