Cryptosystème de McEliece

1. Sélectionner aléatoirement un ${\displaystyle (n,k)}$-code linéaire ${\displaystyle C}$ capable de corriger ${\displaystyle t}$ erreurs. Ce code doit posséder un algorithme de décodage efficace.
2. Alice génère une matrice génératrice ${\displaystyle G}$ pour le code ${\displaystyle C}$ (matrice ${\displaystyle k\times n}$).
3. Sélectionner aléatoirement une matrice binaire ${\displaystyle k\times k}$ non singulière ${\displaystyle S}$.
4. Sélectionner aléatoirement une matrice de permutation ${\displaystyle P}$ ${\displaystyle n\times n}$.
5. Calculer la matrice ${\displaystyle {\hat {G}}=SGP}$. Celle-ci est une matrice ${\displaystyle k\times n}$.
6. La clef publique est ${\displaystyle ({\hat {G}},t)}$; la clef privée est ${\displaystyle (S,G,P)}$.

Pour chiffrer une suite binaire ${\displaystyle m}$ de longueur ${\displaystyle k}$ :

1. Calculer le vecteur ${\displaystyle c^{\prime }=m{\hat {G}}}$.
2. Générer un vecteur d'erreur ${\displaystyle e}$ de poids ${\displaystyle t}$ (une suite binaire de longueur ${\displaystyle n}$ contenant ${\displaystyle t}$ 1 et ${\displaystyle n-t}$ 0).
3. calculer le chiffré ${\displaystyle c=c^{\prime }+e}$.

1. Calculer ${\displaystyle {\hat {c}}=cP^{-1}}$.
2. Utiliser l'algorithme de décodage de ${\displaystyle C}$ pour décoder ${\displaystyle {\hat {c}}}$ en un mot ${\displaystyle {\hat {m}}}$.
3. Calculer ${\displaystyle m={\hat {m}}S^{-1}}$

Généralement, les codes de Goppa sont considérés comme de « bons » codes linéaires puisqu'ils permettent de corriger jusqu'à ${\displaystyle {n^{k}} \choose {\log _{2}n}}$ erreurs ; ils se décodent efficacement, par les algorithmes d'Euclide et de Berlekamp-Massey, en particulier.

Les clés publique et privée sont de grandes matrices, ce qui constitue un des plus grands désavantages de ce chiffre. Par exemple, la clé publique est de ${\displaystyle 2^{19}}$ bits (64 Kio).

Il y a eu des tentatives de cryptanalyse sur l'algorithme de McEliece, mais des changements ont permis de les rendre inopérantes. Néanmoins, cet algorithme n'est pas utilisé en pratique, d'une part à cause de la taille importante de ses clés, mais aussi parce que la taille du texte chiffré est de deux fois celle du texte d'origine.

La ressemblance entre ce problème et celui du sac à dos inquiète aussi une partie des spécialistes.

En 1991, E.M. Gabidulin et al. ont proposé une amélioration[5] , qui, deux ans après, sera prouvée sans avantage par J.K. Gibson4^e édition_de_la_conférence_''IMA_Conference_on_Cryptography_and_Coding''_de_1993_6-0">[6].

• [McEliece 1978] (en) Robert J. McEliece, « A Public-Key Cryptosystem Based on Algebraic Coding Theory », Jet Propulsion Laboratory DSN Progress Report,‎ 1978, p. 42–44 (lire en ligne)
• [Niederreiter 1986] Harald Niederreiter, « Knapsack-type Cryptosystems and Algebraic Coding Theory », Problems of Control and Information Theory 15, vol. 1, n^o 6,‎ 1986, p. 159–166
• [Li, Deng et Wang 1994] Yuan Xing Li, Robert H. Deng et Xin Mei Wang, « On the equivalence of McEliece's and Niederreiter's public-key cryptosystems », IEEE Transactions on Information Theory, vol. 40, n^o 1,‎ 1994, p. 271–273
• [Gabidulin, Paramonov et Tretjakov 1991] E.M. Gabidulin, A.V. Paramonov et O.V. Tretjakov, « Ideals over a non-commutative ring and their application in cryptology », Eurocrypt, Springer-Verlag,‎ 1991, p. 482-489 (DOI 10.1007/3-540-46416-6_41)
• [Gibson 1995] J.K. Gibson, « Severely denting the Gabidulin version of the McEliece public key cryptosystem », Design, Codes and Crypto, vol. 6,‎ 1995, p. 37—45 (ISSN 1573-7586, DOI 10.1007/BF01390769)

• Code correcteur
• Cryptographie post-quantique
• Cryptographie asymétrique