Algorithme de Chiffrement basé sur les codes de correcteurs d’erreurs

Le premier cryptosystème basé sur les codes est le cryptosystème de McEliece [66], qui proposait d’utiliser des codes de Goppa. Suite à cela, plusieurs familles de code ont été suggérées pour remplacer les codes de Goppa dans ce schéma : les codes de Reed–Solomon généralisés (GRS) [67] ou bien des sous-codes de ces derniers , des codes de Reed–Muller , des codes algébriques géométriques , des codes LDPC , des codes MDPC ou plus récemment des codes convolutifs. Certains de ces schémas permettent d’obtenir des clés publiques plus petites que celle du système original tout en vraisemblablement conservant le même ni- veau de sécurité contre les algorithmes de décodage génériques. Cependant, pour plusieurs des schémas susmentionnés, il a été montré qu’une description du code sous-jacent aidant au décodage peut être obtenue, cassant par là-même le schéma. Cela s’est produit pour les codes de Reed–Solomon généralisés (GRS) dans [68] et pour leurs sous-codes dans [69]. Dans ce cas, l’attaque retrouve entièrement et en temps polynomial la structure du code à partir de la clé publique. Les codes de Reed–Muller ont également été attaqué, mais cette fois, l’algorithme trouvant la description du code permuté a une complexité sous-exponentielle , ce qui est suffisant pour casser les paramètres proposés dans [67] mais qui ne casse pas com- plètement le schéma. Les systèmes basés sur les codes de géométrie algébrique sont également cassé en temps polynomial mais uniquement pour les courbes hyperelliptiques de faible genre [31]. Un schéma basé sur des codes LDPC [3] a été attaqué dans [57] (le nouveau schéma présenté dans [2] semble insensible à ce genre d’attaque). Deux variantes [1] du schéma basé sur les GRS supposées résister à l’attaque de [68] ont été cassées (respectivement [34] et [24]) par une approche liée au distingueur des codes de Goppa proposé dans [28]. Le crypto- système de McEliece d’origine reste lui intact. Une modification a été apporté dans [9, 53], utilisant les versions quasi-cycliques ou quasidyadiques des codes deGoppa (ou plus généralement des codes alternant dans [9]) afin de réduire signi- ficativement la taille de la clé publique. Cependant, il a été montré dans [30, 70] que la structure de ces codes permet de réduire radicalement le nombre d’incon- nus de l’attaque algébrique. La plupart des schémas proposés dans [9, 53] ont été cassés par cette approche. Ce genre d’attaque a une complexité exponentielle et peut être contrecarré en choisissant de petits blocs cycliques ou dyadiques afin d’augmenter le nombre d’inconnues du système algébrique. Lorsque le rendement du code de Goppa est proche de 1 (tel que dans le schéma de signature CFS [22]), il a été montré dans [29] qu’il était possible de distinguer la clé publique d’une clé aléatoire. Cela invalide les preuves de sécurité des schémas utilisant des codes de rendement proche de 1 puisque tous reposent sur l’hypothèse d’indistinguabilité des codes de Goppa.

Codes de Goppa et difficulté algorithmique

Nous avons vu section 3.3 que la difficulté algorithmique des problémes de déco- dage sur un code aléatoire est, dans le cas général, bien établie. Pour un code de longueur n, de dimension k et de matrice de parité G aléatoire , si les paramètres n et k sont correctement choisis, la fonction f → mG + e où e ← Wn,t est donc à sens unique.Cependant, pour un usage dans le cadre d’un schéma de chiffrement il est nécessaire d’introduire une trappe permettant au destinataire de décoder f(m) afin de recouvrer l’information transmise m, ce qui est impossible en utilisant un code aléatoire. Les codes de Goppa permettent d’atteindre cet objectif.Les codes de Goppa ont été introduits par V. D. Goppa en 1970 [70]. Initialement étudiés pour leurs propriétés de codes correcteurs d’erreurs ce qui permit l’appa- rition d’algorithmes de décodage efficaces.Ils ont été ensuite étudiés pour leurs propriétés cryptographiques avec l’apparition du cryptosystème de McEliece.Les codes de Goppa sont des codes linéaires sur un corps fini Fq, mais leur construction passe par une extension F qLes codes de Goppa binaires correspondent au cas particulier où l’on choisit q = 2. La matrice de parité H du code est alors une matrice binaire de taille mt × n construite comme ci-dessus. Par rapport au cas général, les codes de Goppa binaires présentent l’avantage, si on ajoute la contrainte supplémentaire sur g de ne pas posséder de facteur multiple, d’avoir une distance minimale égale à 2t + 1, doublant ainsi sa capacité de correction.

Problèmes difficiles

En considérant l’objectif de construire une fonction à sens unique fondée sur la théorie des codes correcteurs d’erreurs, les codes de Goppa binaires sont par- ticulièrement intéressants.En effet, il est calculatoirement difficile de distinguer un code de Goppa binaire de rendement proche de 12 dont on ne connait ni lesupport ni le polynome générateur, ne sera pas fondamentalement différente deLe premier, McEliece eut l’idée, en 1978, d’utiliser la théorie des codes correcteurs d’erreurs à des fins cryptographiques, et plus précisément pour un algorithme de chiffrement asymétrique. Le principe du protocole qu’il décrivit consiste à faire envoyer par Alice un message contenant un grand nombre d’erreurs, erreurs que seul Bob sait détecter et corriger.

En réalité, la clef publique du système n’est autre qu’une matrice génératrice d’un autre code linéaire, C’ équivalent au code C .Ce nouveau code est donc éga- lement un code de distance minimale d. En effet, effectuer le produit G’=SGP revient simplement à modifier la base choisie pour représenter le code sous forme d’une matrice génératrice (combinaison linéaire des lignes par la matrice S) et à permuter les coordonnées du code (permutations des colonnes par la matrice P). Je désignerai par la suite ce code C’ par le terme code public, par opposition au code secret, C. Un message chiffré par le système, c s’écrit donc sous la forme d’un mot du code public dont t positions sont erronées. Retrouver le texte clair, ou de façon équivalente le vecteur d’erreurs e, revient alors à décoder c relativement au code public jusqu’à la distance t, i.e. résoudre, pour w = t, le problème suivant : Problème du décodage jusqu’à la distance .