Cryptographie basée sur les codes, méthodes de cryptanalyse algébrique

Historiquement les codes correcteurs d'erreur ont été introduits afin d'améliorer la qualité d'une communication via un canal bruité. C'est à la fin des années 70, peu de temps après la découverte de la cryptographie à clé publique et de RSA que R.J. McEliece propose d'utiliser les codes correcteurs d'erreur pour faire du chiffrement à clé publique.

Longtemps considérée comme inapplicable en pratique du fait de la taille conséquente des clés publiques nécessaires, la cryptographie à base de codes connait depuis peu un regain d'intérêt significatif. La principale raison de ce changement vient de ce que les schémas cryptographiques basés sur les codes font partie du petit nombre de schémas pouvant résister aux attaques d'un futur ordinateur quantique. Un récent appel à candidatures du NIST(1) pour définir des standards en cryptographie post-quantique a d'ailleurs renforcé la nécessité d'étudier ce type d'alternatives aux schémas cryptographiques usuels, et sujets à des attaques quantiques, tels que RSA.

Dans cet exposé, je développerai cette problématique et donnerai une introduction à la cryptographie basée sur les codes. J'aborderai ensuite différentes variantes du schéma originel de McEliece ainsi que des exemples d'attaques sur certaines de ces variantes.

(1) l'institut américain pour les standards technologiques