next up previous contents
Next: Lambda-calcul typé et langages Up: Activité scientifique des équipes Previous: Activité scientifique des équipes

Groupe de Recherche en Complexité et Cryptographie

Créé en 1988, le Groupe de Recherche en Complexité et Cryptographie (GRECC) a pour objet de contribuer au développement en France de ces deux thèmes d'étude. Il a été intégré au LIENS en janvier 1992. Depuis lors, huit thèses ont été soutenues et la notoriété internationale acquise par le groupe en fait le point de référence pour la recherche civile en cryptographie dans notre pays. Sans chercher à surestimer l'importance du domaine, on constate le rôle croissant des techniques de cryptographie dans des domaines d'applications aussi divers que la sécurisation de l'Internet, le téléphone cellulaire, la télévision à péage, les transactions bancaires, la conservation et le transfert de données médicales etc. La présence en France d'une équipe de recherche amont d'un niveau comparable à celle d'autres institutions universitaires ou industrielles telles que le MIT, ATT Research, IBM Research ou l'Institut Weizmann, présence qui n'allait pas de soi et qui est à mettre à l'actif du LIENS, semble donc un atout pour le CNRS.

Certes, la pérennité du GRECC paraît maintenant établie. Néanmoins, la structure du groupe reste fragile. Les départs successifs de Claude Crépeau et de Jean-Marc Couveignes posent un problème d'encadrement que ne résout pas complètement le recrutement comme CR1 de Serge Vaudenay. Un fonctionnement optimal requiert l'arrivée d'un autre chercheur permanent et le groupe espère donc vivement pouvoir bénéficier dans les années qui viennent d'un recrutement au titre du CNRS ou de l'ENS.

La cryptologie, dans ses aspects théoriques et pratiques forme maintenant le c tex2html_wrap5024 ur des recherches menées au GRECC. Cependant, cette recherche s'insère dans un large environnement théorique et pratique qui amène l'équipe à couvrir un domaine d'étude très ``vertical'' puisqu'il va de la théorie abstraite de la complexité et de la théorie algorithmique des nombres, à l'implantation d'algorithmes cryptographiques sur ordinateur ou sur carte à mémoire ou à la conception de solutions globales pour le micropaiement et le contrôle d'accès pour la télévision à péage.

Théorie de la complexité : Preuves Interactives et Approximation des problèmes tex2html_wrap_inline5012 -complets

Depuis une quinzaine d'années, les progrès de la théorie des algorithmes ont permis de mettre en évidence la possibilité d'établir ou de transmettre certains faits ou certaines assertions, non pas à l'aide d'une preuve au sens logique du terme, mais à travers un processus interactif de questions réponses aléatoires. Ces travaux ont entre autres choses conduit à la formulation de la notion de preuve ``zero-knowledge''.

Ces découvertes sont riches d'applications : on a ainsi pu réaliser effectivement des systèmes cryptographiques présentant des fonctionnalités entièrement nouvelles :

En 1992, on a assisté à un spectaculaire ``retour'' des études de cryptographie puisque des concepts issus de cette discipline appliquée (celui d'interaction en particulier) ont permis de faire des progrès spectaculaires sur la question de l'approximation des problèmes tex2html_wrap_inline5012 -complets. Le GRECC a participé à ce mouvement d'idées en montrant l'impossibilité de définir des algorithmes d'approximation pour certains problèmes d'optimisation concernant les codes correcteurs d'erreur ou les réseaux à coordonnées entières ([27, 4]).

Un autre travail de l'équipe relevant de la théorie de la complexité, quoique motivé par une recherche par l'étude de mécanismes d'authentification nécessitant peu de ressources de calcul, recherche menée en liaison avec un partenaire industriel, a conduit à prouver le caractère rapidement transitif d'un système formé par des permutations aléatoires agissant sur des tableaux de taille fixe (voir [14, 49]).

Théorie algorithmique des nombres et théorie des codes correcteurs d'erreurs

Factorisation des nombres entiers

Outre la théorie de la complexité algorithmique, la cryptographie s'appuie sur la théorie des nombres, en particulier sur les questions liées à la factorisation des nombres entiers. Depuis longtemps, le groupe suit de très près les développements dans ce domaine qui conditionnent la sécurité de nombreux algorithmes cryptographiques. Il a participé, en collaboration avec des chercheurs étrangers, à l'élaboration de diverses techniques de pointe, en particulier à l'accélération du crible algébrique (Number Field Sieve), méthode de factorisation des entiers naturels proposée par Lenstra et Pollard en 1990. Cette méthode se heurte à des difficultés pratiques telles que la manipulation de nombres entiers gigantesques (plusieurs millions de décimales). Un des chercheurs du groupe ([3]) a développé des techniques modulaires qui permettent d'éviter ces manipulations trop coûteuses et qui de plus, facilitent la parallélisation. Une version de l'algorithme NFS, utilisant, entre autres éléments, ces améliorations, a conduit au dernier record du monde dans ce domaine, établi par Arjen Lenstra.

Plus récemment, l'équipe a décidé de se doter, elle-aussi, d'une implantation complète et indépendante de NFS. Son choix s'est porté sur une variante de NFS développée par Montgomery. Un assez long travail de programmation fine a été nécessaire, auquel un des chercheurs du groupe s'est consacré à temps plein. Ce travail a inclus le crible proprement dit et les deux phases dites ``extraction de la racine carrée'' et ``calculs matriciels''.

Les résultats sont encourageants et ont permis d'obtenir la factorisation complète du nombre : tex2html_wrap_inline5032 , pour lequel il restait à décomposer un facteur tex2html_wrap_inline5034 de cent chiffres. On a utilisé pour le criblage 32 stations ayant 24 Mo de RAM et cadencées à 80Mhz pendant pendant environ trois semaines. L'algèbre linéaire a pu être implantée en 29 jours de calculs sur Sparc 20 à 75Mhz avec ``seulement'' 288 Mo de RAM.

Algorithmique sur les réseaux à coordonnés entières

Un réseau est un Z-module discret de R tex2html_wrap_inline5036 . Réduire un réseau, c'est trouver une bonne base du réseau, formée de vecteurs assez courts et assez orthogonaux. C'est un problème largement étudié mais les solutions classiques - sauf en petite dimension- ne sont jamais constructives. Lenstra, Lenstra, Lovàsz, en 1983, ont obtenu un algorithme polynomial, appelé LLL, qui trouve une assez bonne base du réseau. En particulier, le premier vecteur de cette base est suffisamment court pour jouer le même rôle que le plus court vecteur du réseau.

L'algorithme LLL, qui utilise l'arithmétique rationnelle pour manipuler de très grands nombres est extrêmement inefficace. Son implantation pratique nécessite la substitution à l'arithmétique rationnelle de l'arithmétique flottante de la machine. Le contrôle de cette substitution est très délicat, tant du point de vue théorique que pratique. Le GRECC maintient une version finement optimisée qui a été développée il y a quelque temps déjà([82, 9]). Il est ainsi en mesure de valider tout nouveau résultat dans le domaine. Tout récemment, il a proposé une nouvelle méthode heuristique permettant d'utiliser LLL. Cette heuristique, dite du bidual, applique la réduction au dual tex2html_wrap_inline5038 d'un réseau L, puis au dual du réseau obtenu en ``oubliant'' les derniers vecteurs de la base réduite (voir [88]). Celle-ci a permis des progrès en cryptanalyse qui seront détaillés un peu plus loin.

Calculs explicites d'objets mathématiques complexes

L'algorithme LLL, décrit ci-dessus permet également d'obtenir efficacement la description exacte d'un nombre algébrique dont on ne connaît qu'une représentation approchée. On peut ainsi utiliser des méthodes numériques pour certains problèmes du calcul formel.

Le groupe a mis en tex2html_wrap5024 uvre ces idées pour calculer explicitement des objets mathématiques complexes : les revêtements de la sphère ramifiés au dessus de trois points seulement, appelés aussi Dessins d'Enfants à cause de leur représentation géométrique ([2]). L'étude de ces objets remonte au siècle dernier mais ils ont été remis au goût du jour par ``l'esquisse d'un programme'' rédigée il y a quelques années par Alexandre Grothendieck. Le GRECC a ainsi obtenu des résultats sur les propriétés de rationalité de ces revêtements ([80]).

A partir des dessins, il est possible de construire explicitement des objets mathématiques ayant certaines propriétés particulièrement intéressantes. Par exemple on peut ainsi tenter de résoudre certaines instances du problème de Galois inverse. C'est ainsi que le GRECC a pu réaliser la construction et le calcul explicite d'un dessin correspondant à une extension régulière de Q(T) de groupe de Galois tex2html_wrap_inline5044 ([15]). On connaissait l'existence d'une telle extension sans en avoir la description. Cela prouve l'intérêt des techniques de calcul de dessins.

Calculs du nombre de points d'une courbe elliptique

C'est René Schoof qui a proposé en 1985 le premier algorithme polynomial pour le calcul du nombre de points rationnels sur une courbe elliptique définie sur un corps fini. Malheureusement sa méthode restait impraticable et ce sont des idées d'Elkies et d'Atkin qui on permis d'aboutir à des calculs explicites au moins dans le cas où le corps est primitif ( tex2html_wrap_inline5048 ) ou du moins de caractéristique assez grande. L'application de ces méthodes au calcul de la cardinalité d'une courbe elliptique sur un corps de type tex2html_wrap_inline5050 est restée un problème ouvert pendant quelques années. Or le cas de la caractéristique 2 est le plus utile dans les applications pratiques (cryptographie en particulier).

Ce problème à été résolu au sein du GRECC en utilisant la géométrie des groupes formels attachés aux courbes elliptiques et la notion de tex2html_wrap_inline5054 -torsion ([42]). Contre toute attente, ces objets jouissent de propriétés algorithmiques remarquables qui en font des auxiliaires précieux pour le calcul. Une implémentation réalisée en collaboration avec le laboratoire de l'École Polytechnique a démontré l'efficacité de cette méthode.

Théorie des codes

À plusieurs reprises, un lien s'est établi entre les recherches du GRECC et la théorie des codes. C'est ainsi que les chercheurs du GRECC ont été amenés à étudier divers problèmes de codes. On se bornera à mentionner deux de ces ``points de contact''.

  1. La recherche de familles de codes correcteurs d'erreurs constructibles en temps polynomial ayant des propriétés particulières (par exemple telles que les vecteurs non nuls aient tous presque le même poids). De façon inattendue, ces familles fournit les meilleurs bornes asymptotiques pour les solutions effectives du ``kissing number problem''(Placer autant de boules de rayon un que possible au contact d'une boule donnée). ([18]).
  2. La construction de mécanismes réalisant l'amplification de secrets partagés ([32]) ou de protocoles basés sur les phénomènes quantiques [34, 44, 45] . On y reviendra plus loin.

Corps finis

Les différentes études précédentes ont montré la nécessité de disposer de librairies de calcul dans les corps finis de caractéristique 2 Des librairies semblables dans Z/pZ ont par ailleurs été développées à l'École Polytechnique par Morain et Lercier. Ces travaux ont été unifiés pour obtenir une librairie unique de calcul optimisé dans toute extension définie sur un anneau primitif. Baptisée zen, elle se veut à la fois simple d'emploi et efficace. Les premiers résultats expérimentaux d'implantation prouvent que cette librairie répond à ces objectifs [85].

Cryptographie à clé publique

L'invention de la cryptographie à clé publique remonte en 1976 avec l'article fondateur de Diffie et Hellman. L'idée, 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, par exemple :

Chiffrement à clé publique

La question des alternatives à RSA est évidemment un défi essentiel auquel fait face la cryptographie moderne. Récemment, en collaboration avec David Naccache, nous avons conçu deux cryptosystèmes différents de RSA mais reposant sur des propriétés arithmétiques ([56, 86]). Le premier est une version multiplicative du sac à dos a malheureusement des performances qui ne sont pas comparables à celles du RSA (en terme de temps de calcul). Le second est plus prometteur : il est basé sur le problème du calcul des logarithmes ``discrets'' (c'est-à-dire modulo un entier), alors que RSA est fondé sur la difficulté de factoriser les entiers. Ce nouveau système pourrait rivaliser avec le RSA, après avoir naturellement été examiné par la communauté...

Signature

Au delà de la signature de base, il existe de nombreuses variantes assurant diverses fonctionnalités. Citons par exemple, sans souci d'exhaustivité :

En collaboration avec des collègues allemands, le groupe a entrepris récemment un effort de classification de différents concepts de schémas de signature électronique, permettant de les ranger en plusieurs classes orthogonales([57]) mais combinables entre elles. Il a également proposé de nouveaux schémas de signatures avec vérifieurs multiples([58]), pour lesquels la fraude d'un vérifieur est détectable par les autres vérifieurs ainsi qu'un nouveau schéma de signature de groupe avec signeur anonyme, qui est plus efficace que les propositions connues ([91])

Le GRECC s'est également intéressé à la question de la certification des clés publiques, qui est l'un des principaux problèmes à résoudre pour que le commerce électronique se développe sur l'Internet. Nous avons pu étendre le concept de clefs publiques basées sur l'identité introduit par Marc Girault en 1991 et mettre au point diverses applications( [89]).

Enfin, l'équipe s'est penchée sur la question du temps de calcul : en effet, les deux principaux schémas de signature à clé publique, le RSA et le DSS, obligent l'entité qui le signe à 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 existants 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 sûres, tant pour le RSA ([29, 31]) que pour le DSS ([30]).

Procédés d'identification

Les systèmes ``zero-knowledge'' ont été évoqués ci-dessus dans le paragraphe relatif à la théorie de la complexité. Fiat et Shamir ont donné en 1986 une application de ce concept 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 mis au point toute une série de protocoles d'identification simples :

    =1000 =2000
  1. l'un fondé sur la mise en tex2html_wrap5024 uvre de codes correcteurs d'erreurs.
  2. un autre reposant sur le problème du 3-couplage [101].
  3. un autre encore basé sur un nouveau problème tex2html_wrap_inline5012 -complet, inspiré de la théorie des réseaux de neurones ([78]).
  4. un autre enfin, utilisant un problème original d'équations linéaires contraintes ([68]). Ce dernier protocole a l'avantage de n'utiliser que des clés de taille comparable à celles de la cryptographie conventionnelle (64 à 80 bits), ce qui apporte une réponse à un problème posé depuis longtemps en cryptographie à clé publique.

Plus récemment nous sommes passés à l'étude fine de la sécurité des problèmes combinatoires sous-jacents ainsi qu'à l'analyse des performances dans la pratique. Pour la proposition 2 ci-dessus, nous avons malheureusement constaté qu'elle est inutilisable sur carte à puce car les tailles de problèmes implantables sur ces cartes sont à la portée d'attaques que nous avons imaginées, en des temps de quelques heures sur SparcStation 10.

En revanche, l'étude des autres protocoles a conduit à des conclusions prometteuses. Nous avons pu réaliser l'implémentation sur une carte à microprocesseur de faible capacité du protocole mentionné ci-dessus en 3. Nous avons également mené dans [21] une analyse de sécurité ``réaliste'' du protocole 4 ainsi que du protocole PKP de Shamir. Par réaliste, on veut dire qu'on ne se contente pas d'estimations asymptotiques sur les attaques potentielles mais qu'on évalue aussi, par extrapolation, la performance de ces attaques avec une implémentation pratique. Cette méthode permet de déterminer les paramètres qui assurent une utilisation sûre.

Preuves de sécurité

La recherche de ``preuves de sécurité'' est tendance significative de la recherche la plus récente en cryptographie. Le simple fait qu'un algorithme cryptographique ait résisté durant plusieurs années aux attaques des cryptanalystes a constitué pendant longtemps la seule forme possible de validation. Un paradigme totalement distinct provient du concept de ``sécurité prouvée''. Cette approche propose des preuves relatives qui ramènent la sécurité du schéma proposé à celle d'un problème classique tel que la factorisation des entiers ou le problème du logarithme discret, déjà cités. Bien entendu, tout comme dans d'autres sciences, on fait, le cas échéant appel à une certaine idéalisation des objets qu'on manipule. A ce prix, on obtient parfois des ``preuves'' qui ne sont, au plan méthodologique, qu'une autre technique de détection des erreurs mais qui contribuent fortement à la confiance.

Dans les dernières années, le GRECC a fait des preuves de sécurité un de ses axes de recherche majeurs. En utilisant des outils de théorie de la complexité, nous avons pu prouver la sécurité - relativement au problème du logarithme discret - d'une modification mineure du schéma de signature maintenant classique de ElGamal (voir [61]).

Nous nous sommes ensuite tournés vers le difficile problème de la sécurité des signatures en blanc. Comme on l'a dit plus haut, il s'agit d'un mécanisme destiné à reproduire sous une forme purement numérique les principales caractéristiques de l'argent liquide, y compris l'anonymat des transactions. Le problème suivant dit de la ``conservation du flux'' semble naïf : prouver qu'après avoir reçu n pièces de monnaie électroniques, un utilisateur ne peut en générer n+1, mais la question restait, depuis quinze ans, d'ordre conjectural. En systématisant la méthode que nous avions utilisée pour les signatures El Gamal, nous avons pu proposer un schéma de signature en blanc de sécurité prouvée relativement au logarithme discret [60]. Nous avons ensuite proposé un schéma analogue prouvé sûr relativement à la factorisation [62].

Nous avons enfin essayé d'appliquer nos idées à la sécurité du standard DSS. Nous avons tout d'abord mis en évidence des faiblesses potentielles [74], puis donné une preuve de sécurité d'une variante proche [98].

La question des preuves de sécurité peut sembler théorique : selon nous, il n'en est rien. Il s'agit de recherche appliquée : dans sa conférence invitée au congrès CRYPTO 96, Ernie Brickell, passé récemment de Sandia Labs à Banker's Trust, a cité nos travaux sur les signatures en blanc comme des éléments qui contribuent à la confiance requise pour la mise en tex2html_wrap5024 uvre systématique des paiements sécurisés sur l'Internet.

Génération déterministe d'aléas

Le GRECC a fourni un travail de préparation considérable dans l'étude de ce sujet difficile et qui a donné lieu récemment à des résultats profonds liant les fonctions à sens unique de la cryptographie et les générateurs de pseudo-aléa. Ce travail a bénéficié de la visite en juin 95 de Mike Luby (ICSI, Berkeley), expert reconnu du domaine.

Ce travail nous a permis d'attaquer avec succès la question du rendement : chaque bit d'aléa produit par un générateur a un coût en terme de complexité algorithmique. Ce coût est mesuré en fonction d'un paramètre de sécurité qui mesure la taille des nombres manipulés. En substituant à la théorie des nombres la théorie des codes, comme nous l'avons fait pour l'identification, nous avons pu dans [48] proposer un générateur pseudo-aléatoire extrêmement simple, de rendement linéaire et dont la sécurité est aussi prouvée au sens du paragraphe précédent.

Analyse cryptographique

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). En utilisant son implantation performante de LLL, le groupe a pu mener à bien plusieurs ``cryptanalyses'' nouvelles :

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 [100, 37, 77] Un travail analogue pour le procédé de Stern a aussi été mené. Dans le même ordre d'idées, une cryptanalyse réaliste du schéma d'authentification de K. Chen a été proposée [35]. Cette cryptanalyse s'appuie sur un algorithme original de décodage général à distance minimale de Gabidulin des codes linéaires.

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 ([39, 8]). Notre cryptanalyse utilise des méthodes empruntées à la théorie de Galois et, là encore, permet des calculs explicites.

Cryptographie Conventionnelle

Pendant longtemps, la cryptographie conventionnelle a fait l'objet de très peu de recherches en dehors de celles de Shannon, qui, dans les années cinquante, a introduit les notions de diffusion et de confusion. De façon surprenante, le développement de la cryptographie à clé publique a amené, par ricochet, des progrès sur les méthodes conventionnelles. Il faut noter en effet que la cryptographie à clé publique n'élimine pas le recours aux procédés conventionnels, pour au moins deux raisons :

S'agissant précisément des fonctions de chiffrement symétriques (comme le DES, Data Encryption Standard) ou des fonctions de hachage, deux méthodes très générales d'évaluation et d'attaque sont apparues récemment :

Ces deux cryptanalyses appliquées à DES sont les premières à être plus rapides que la recherche exhaustive. Le GRECC participe au renouveau de la recherche sur la cryptologie conventionnelle.

Fonctions de hachage

On vient de mentionner le concept de fonction de hachage. On requiert en général que l' opération se fasse de façon qu'il soit virtuellement impossible de calculer deux messages ayant même condensé (on parle de collision). Le GRECC a ainsi étudié la fonction de hachage FFT-Hash 2 proposée par Claus Schnorr au colloque Eurocrypt'92 pour laquelle il a trouvé des collisions. Il a ensuite, en collaboration avec Claus Schnorr, proposé des variantes plus sûres de FFT-hash [23, 64].

Plus récemment, le GRECC a également mis en évidence certaines faiblesses de la fonction de hachage MD4 proposée par R. Rivest en obtenant des collisions pour une version simplifiée ([24]).

Chiffrement symétrique

On a parlé plus haut des deux méthodes générales de cryptanalyse (différentielle et linéaire). En utilisant une approche basée sur l'utilisation systématique de la transformée de Fourier des fonctions booléennes, le groupe a pu mettre en évidence des propriétés de dualité de ces deux cryptanalyses, et donc leur complémentarité [95, 36]. Il a aussi unifié les deux types de cryptanalyse en les isolant de leur aspect linéaire par une approche statistique [73].

Le GRECC a aussi porté son attention sur la fonction de chiffrement SAFER proposée par J. Massey et dédiée aux microprocesseurs 32 bits. ainsi que sur la fonction de chiffrement Blowfish. Il a en particulier proposé une attaque sur une variante de SAFER ([24]) montré dans [75] l'existence de clefs qui affaiblissent la sécurité de Blowfish.

Enfin le GRECC a proposé un mécanisme de chiffrement adapté aux coprocesseurs arithmétiques ([54]). Ce travail mené en collaboration avec la société GEMPLUS, permet d'optimiser la vitesse du chiffrement sur une carte à puce en utilisant les fonctions disponibles à bord, en particulier celles du coprocesseur.

Approche théorique de la cryptographie conventionnelle

S'inspirant des cryptanalyses dont on vient de parler dans les trois paragraphes précédents, le GRECC a entrepris d'élaborer une théorie générale des fonctions cryptographiques conventionnelles (hachage et chiffrement). Cette théorie s'est pour l'instant développée suivant deux axes

Protocoles cryptographiques

Les protocoles cryptographiques sont des algorithmes à plusieurs participants où certaines information secrètes sont traitées. On considère, par exemple, le problème général du calcul partagé d'une fonction : deux participants A et B veulent calculer une fonction f(x, y) sur données a et b, a étant connue de A et b connue de B, sans se révéler mutuellement a et b, mais seulement le résultat f(a, b). On considère également le scénario où une information secrète doit être partagée entre n participants de façon que k d'entre eux doivent contribuer leur part pour que le secret soit découvert : c'est le problème du ``partage du secret''. Sans en faire l'axe principal de ses recherches, le GRECC ne néglige pas l'étude des protocoles.

En matière de partage du secret, un problème important est d'optimiser la taille des parts : en effet, un fait bien connu dans la théorie des partages de secrets parfaits (au sens de la théorie de l'information) est que la taille des parts détenues par chaque personne doit être supérieure ou égale à celle du secret. Si l'on requiert une sécurité basée seulement sur la complexité algorithmique, on peut s'affranchir de cette contrainte comme l'a montré H. Krawczyk à Crypto'93 pour les structures d'accès seuil. En collaboration avec Antonnella Cresti (Université de Rome, Italie), nous avons pu généraliser ce résultat à toutes les structures d'accès ([28])

Cryptographie appliquée

Comme on l'a dit dès le début de ce chapitre, les applications industrielles de la cryptographie sont nombreuses. Bien entendu, le GRECC a principalement pour vocation la recherche fondamentale. Cependant, il lui paraît essentiel de ne pas perdre de vue le côté pratique de la cryptographie et c'est pourquoi, s'agissant des algorithmes, il a toujours le souci, ainsi qu'on l'a vu plus haut, de les valider par des implantations sur carte à puce ou sur machine.

Certains domaines d'applications demandent, au delà des algorithmes, la définition de solutions cryptographiques globales. À plusieurs reprises, Le GRECC a proposé de telles solutions :

Cryptographie quantique

A la suite des travaux de G. Brassard et C. Bennett, il a été proposé d'utiliser des phénomènes quantiques dans la construction de protocoles cryptographiques. Depuis quelques années, il existe aux États-Unis un prototype de transmetteur quantique démontrant le potentiel de ces idées. Le GRECC a participé à l'élaboration de la cryptographie quantique en démontrant en particulier la sécurité des solutions proposées précédemment [6] [34]. Il a également participé à des recherches de physique fondamentale sur la téléportation d'un état quantique [5].

Il a ensuite concentré ses recherches sur l'élaboration de protocoles efficaces pour des tâches cryptographiques. Une fois encore, ces protocoles nécessitent l'utilisation de la théorie des codes. C'est ainsi que nous avons mis au point avec Louis Salvail (Université de Montréal) un protocole d'identification quantique permettant à deux personnes de vérifier qu'ils possèdent un mot de passe commun sans se le révéler. ([44]).

Il faut noter que la cryptographie quantique ouvre des perspectives de coopération avec les physiciens de l'École Normale Supérieure. Un autre sujet, le calcul quantique éveille également l'intérêt de nos collègues physiciens. Il s'agit d'une approche nouvelle de théorie de la complexité qui envisage la mise en tex2html_wrap5024 uvre de machines dont l'évolution réalise des superpositions d'états quantiques. Les premiers résultats obtenus dans ce domaine sont impressionnants puisque ces machines (si elles voyaient le jour) seraient à même de réaliser des tâches au delà des limites des calculateurs actuels. Le GRECC suit de près l'évolution de cette nouvelle spécialité. Il a pu faire le point grâce aux visites successives de Gilles Brassard (Université de Montréal) en 1995 et de Andy Yao (Princeton University), en juin 96. Cependant, le départ de Claude Crépeau risque de conduire à investir moins dans ces questions.

Perspectives

Un certain nombre d'éléments prospectifs ont été déjà évoqués ci-dessus, comme par exemple la question de la généralisation de la cryptanalyse linéaire/différentielle, pour laquelle nous avons prévu la visite à l'ENS d'Eli Biham (Technion, Haïfa), pour octobre 1997.

Nous comptons également ouvrir de nouvelles perspectives de recherche selon les axes suivants :

Amélioration des procédés de signature

Comme on l'a mentionné plus haut, les procédés de signature en usage ne sont pas totalement satisfaisants pour diverses raisons
  1. ils nécessitent le calcul d'exponentielles modulaires, ce qui excède les possibilités des cartes à microprocesseur bas-coût
  2. ils ont une taille relativement élevée (512 bits pour RSA, 320 bits pour DSS), ce qui interdit par exemple la signature individuelle de messages de petite taille (comme les paquets des transmissions par paquets)
Il y a là, à l'évidence, des enjeux théoriques et économiques importants. Notre projet est d'entreprendre des recherches sur les deux questions. S'agissant de l'amélioration des performances, nous sommes convaincus qu'un compromis temps/mémoire est possible.

Recherche de nouveaux systèmes cryptographiques

Il s'agit là d'une question sur laquelle il faut avancer avec prudence puisque les meilleurs experts ont vu parfois leur propositions mises en échec. Nous pensons néanmoins pouvoir progresser sur un scénario qui n'a pas encore reçu toute l'attention souhaitable et que nous appelons échange de clés dissymétrique. Il s'agit d'autoriser un échange de clés entre deux entités cryptographiques : un serveur doté d'une puissance de calcul importante et un client aux capacités réduites (par exemple une carte à microprocesseur). Un tel système pourrait avoir des applications sur les problèmes de contrôle d'accès. Nous pensons aborder là encore le problème sous l'angle de la théorie des codes.

Étude de la sécurité de RSA pour les exposants publics petits

C'est une question qui vient de se retrouver posée nettement à la suite de trois articles parus à Eurocrypt 96 et mettant en jeu des techniques algébriques ou fondées sur l'utilisation de l'algorithme LLL. Compte tenu de notre savoir faire dans ces deux domaines, nous pensons pouvoir unifier les diverses attaques et les améliorer. Également, utilisant les méthodes de sécurité prouvée, nous pourrions proposer des contremesures adéquates.


next up previous contents
Next: Lambda-calcul typé et langages Up: Activité scientifique des équipes Previous: Activité scientifique des équipes

Louis.Granboulan@ens.fr