Cryptosystème de McEliece

Le cryptosystème de McEliece est un schéma de chiffrement asymétrique, inventé en 1978 par Robert McEliece^[1]. Ce système, reposant sur un problème difficile de la théorie des codes, n'a pas rencontré de véritable soutien dans la communauté cryptographique^{[réf. nécessaire]}, entre autres car la clé de chiffrement est particulièrement grande et que le message chiffré est deux fois plus long que l'original. Pourtant, le cryptosystème de McEliece possède des propriétés intéressantes : la sécurité croît beaucoup plus rapidement avec la taille des clés que pour le système RSA, et le chiffrement est plus rapide.

Un autre avantage est de reposer sur un problème très différent des algorithmes asymétriques usuels. Cela signifie qu'une percée théorique dans le domaine de la factorisation, réalisable par des algorithmes quantiques, qui ruinerait RSA, n'affecterait en rien ce système. Cet avantage lui permet d'être sélectionné par le NIST comme candidat à la standardisation des algorithmes de chiffrement post-quantique^[2].

Des attaques efficaces ont été publiées contre le cryptosystème de McEliece, ainsi que contre de nombreuses variantes. Cependant, des améliorations ont été proposées afin d'éviter ces attaques. Il est rarement utilisé en pratique du fait de la grande taille des clefs, mais a été utilisé pour le chiffrement dans Entropy, une alternative à Freenet.

Principe[modifier | modifier le code]

Un code correcteur d'erreurs permet de corriger une information qui se serait altérée lors de sa transmission via un canal (réseau, CD-ROM, temps, etc). Pour ce faire, un mot (une suite de symboles) est transformé en un mot du code en rajoutant de l'information (appelée redondance). À la sortie du canal, la redondance est utilisée pour corriger les erreurs et ainsi retrouver le mot de code transmis en entrée. Ce mot est alors retransformé pour fournir le mot original.

L'idée de McEliece est de masquer le mot de code correspondant au message en lui ajoutant autant d'erreurs que possible tout en gardant la possibilité de corriger celles-ci. Si la méthode de correction est gardée secrète, alors seul le destinataire sera en mesure de retrouver le message original. La méthode d'encodage peut, quant à elle, être laissée publique tant qu'elle ne révèle pas d'information sur le décodage.

Le cryptosystème de McEliece utilise les codes de Goppa. Les codes de Goppa sont faciles à décoder, mais une fois leur structure masquée par permutation, il est difficile de les distinguer des codes linéaires. De plus, il est difficile de décoder un code linéaire aléatoire. La sécurité du système repose donc sur deux problèmes distincts : l'indistingabilité d'un code de Goppa permuté d'une part et le problème du décodage borné d'autre part.

En 1986, Harald Niederreiter a proposé un autre cryptosystème fondé sur la théorie des codes^[3]. Le cryptosystème de Niederreiter a été prouvé équivalent à celui de McEliece en 1994 par Y.X. Li, R.H. Deng et X.M. Wang^[4].

Description du schéma[modifier | modifier le code]

Le cryptosystème de McEliece consiste en trois algorithmes: un algorithme probabiliste de génération des clefs qui produit une clef secrète et une clef publique, un algorithme (probabiliste) de chiffrement et un algorithme (déterministe) de déchiffrement. Tous les utilisateurs partagent des paramètres de sécurité : $n,k,t$ .

Génération des clefs[modifier | modifier le code]

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

Chiffrement[modifier | modifier le code]

Pour chiffrer une suite binaire $m$ de longueur $k$ :

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

Déchiffrement[modifier | modifier le code]

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

Critiques[modifier | modifier le code]

Positives[modifier | modifier le code]

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

Négatives[modifier | modifier le code]

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 $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].

Notes et références[modifier | modifier le code]

↑ McEliece 1978.
↑ (en-US) Information Technology Laboratory Computer Security Division, « Round 3 Submissions - Post-Quantum Cryptography | CSRC | CSRC », sur CSRC | NIST, 3 janvier 2017 (consulté le 19 novembre 2021)
↑ Niederreiter 1986.
↑ Li, Deng et Wang 1994.
↑ Gabidulin, Paramonov et Tretjakov 1991.
↑ Gibson 1995, Version journal parue en 1995, une version préliminaire est parue à 4^e édition de la conférence IMA Conference on Cryptography and Coding de 1993.

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

[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)

Articles connexes[modifier | modifier le code]

Portail de la cryptologie

[McEliece1978-1] McEliece 1978.

[2] (en-US) Information Technology Laboratory Computer Security Division, « Round 3 Submissions - Post-Quantum Cryptography | CSRC | CSRC », sur CSRC | NIST, 3 janvier 2017 (consulté le 19 novembre 2021)

[Niederreiter1986-3] Niederreiter 1986.

[LiDengWang1994-4] Li, Deng et Wang 1994.

[GabidulinParamonovTretjakov1991-5] Gabidulin, Paramonov et Tretjakov 1991.

[Gibson1995[[publication_scientifique|Version_journal]]_parue_en_1995,_une_version_préliminaire_est_parue_à_<abbr_class="abbr"_title="Quatrième">4<sup>e</sup></abbr>&nbsp;édition_de_la_conférence_''IMA_Conference_on_Cryptography_and_Coding''_de_1993-6] Gibson 1995, Version journal parue en 1995, une version préliminaire est parue à 4^e édition de la conférence IMA Conference on Cryptography and Coding de 1993.

[1]

[2]

[3]

[4]

[5]

[6]