Cryptosystème de McEliece

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche à compléter concernant la cryptologie, vous pouvez partager vos connaissances en le modifiant.

Le cryptosystème de McEliece est un algorithme de chiffrement asymétrique, inventé en 1978 par Robert McEliece. 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. L'une des principales raisons de cet état de fait est la taille de la clé. Pourtant, le cryptosystème de McEliece possède des propriétés interessantes, citons notamment

la sécurité croît beaucoup plus avec la taille des clés que pour le système RSA.
la rapidité du chiffrement.

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, qui ruinerait RSA, n'affecterait en rien ce système.

Sommaire

1 Principe
2 Critiques
- 2.1 Positives
- 2.2 Négatives
3 Bibliographie

[modifier] Principe

Cet algorithme utilise les codes de Goppa, qui sont des codes correcteurs d'erreurs (voir théorie des codes). L'algorithme fait passer un code de Goppa, qui code le message, pour un code linéaire, tel que défini en général. Les codes de Goppa sont faciles à décoder, mais il est difficile de les distinguer des codes linéaires. C'est le problème difficile à résoudre de McEliece.

Plus précisément, bien qu'on puisse efficacement décoder un code de Goppa, il est difficile de décoder un code linéaire (général) sans connaître la clé secrète. Celle-ci, dans ce cas, est le codage par code de Goppa.

[modifier] Critiques

[modifier] Positives

Généralements, 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. Aussi, ils se décodent efficacement, par les algorithmes d'Euclide et de Berlekamp-Massey, en particulier.

[modifier] Négatives

Les clés publique et privée sont de grandes matrices, ce qui constitue un des plus grands désavantage de ce chiffre. Par exemple, la clé publique est de $219$ bits.

Il y a eu des tentatives de cryptanalyse sur l'algorithme de McEliece, mais nulle n'a eu de succès. Néanmoins, cet algorithme n'est pas utilisé en pratique, d'une part à cause de la grandeur des clés, mais aussi parce que la grandeur 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, qui, deux ans après, sera prouvée sans avantage par J.K. Gibson.

[modifier] Bibliographie

R.J. McEliece, A public-key cryptosystem based on algebraic coding theory, JPL DSN Progress Report 4244 (1978), 114-116.
E.M. Gabidulin, A.V. Paramonov, and O.V. Tretjakov, Ideals over a non-commutative ring and their application in cryptology, Advances in Cryptology - Eurocrypt '91, Springer-Verlag (1991), 482-489.
J.K. Gibson, Severely denting the Babidulin version of the McElience public key cryptosystem, Preproceedings of the 4th IMA Conference on Cryptography and Coding (1993).