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^{[réf. nécessaire]}.

La ressemblance entre ce problème et celui du sac à dos inquiète aussi une partie des spécialistes^{[réf. nécessaire]}.

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. Gibson[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

• Portail de la cryptologie