Code-based cryptosystems and cryptanalysis implementation
Mise en œuvre de cryptosystèmes basés sur les codes correcteurs d’erreurs et de leurs cryptanalyses
Résumé
This thesis is about algorithmic problems arising when someone wants to imple-
ment a cryptosystem based on error correcting codes or a cryptanalysis of such a
system. The benefits of these systems come from their excellent algorithmic com-
plexity, better of several orders than the classical public key schemes. They also bring
a credible alternative to the current systems that for most of them rely on number
theory and on the problems of factorisation and discrete logarithm. P.Shor showed
that these two problems could be solved in polynomial time in the quantum computer
model. This computer is far from being operational but we will need alternatives we
can trust and that have efficient implementations.
After an introductive section bringing required notions in cryptography and error
correcting codes theory, this thesis presents in a first part an implementation of the
CFS signature scheme, scheme proposed in 2001 by N. Courtois, M. Finiasz and N.
Sendrier. This scheme is based on the Niederreiter cryptosystem and relies on the
syndrome decoding problem and the indistinguishability of binary Goppa codes. The
cumbersome aspect of this scheme (very big public key) may be the reason that slowed
the studies of the problems linked to its implementation. This part tries to show that,
despite the drawbacks, the scheme can be used in practice. An implementation is
proposed and manage to generate a signature in about 1 second.
In a second part, an implementation of several algorithms from the Information
Set Decoding family is presented. This family is used to decode a linear code in a
generic way, that is without using the potential structure underlying in the code. Most
of the code based systems rely their security on the difficulty of this problem. It is
important to find the most efficient algorithms solving it in order to size the systems
correctly. This part presents an implementation of two algorithms of this family (it
could be extending to some others) and shows the result of the application of this
implementation on cryptographic challenges proposed by D. Bernstein, T. Lange and
C. Peters in 2011 together with a cryptanalysis of a encryption scheme based on
convolutional codes proposed by C. Löndahl and T. Johansson in 2012.
Cette thèse porte sur les problèmes algorithmiques qui apparaissent lorsque l’on
souhaite mettre en œuvre un cryptosystème basé sur un code correcteur d’erreur ou
bien une cryptanalyse d’un tel système. L’intérêt de ces système provient de leur
excellente complexité algorithmique, meilleure de plusieurs ordres de grandeurs en
termes de complexité que les schémas à clé publique traditionnels. Ils fournissent éga-
lement une alternative crédible aux systèmes actuels qui pour la plupart se repose
sur la théorie des nombres et sur le problème de la factorisation et celui du loga-
rithme discret. Outre l’absence de preuve mathématique de la réelle difficulté de ces
problèmes, P. Shor a montré que ces deux problèmes pouvaient être résolus en temps
polynomial dans le modèle de l’ordinateur quantique. Cet ordinateur quantique est
encore loin d’être fonctionnel mais il faudra, le jour venu, disposer d’alternatives de
confiance et disposant de mises en œuvre performantes.
Après une section introductive apportant les notions de cryptographie et de théorie
des codes correcteurs requises, cette thèse présente dans une première partie une mise
en œuvre du schéma de signature CFS, schéma proposé en 2001 par N. Courtois, M.
Finiasz et N. Sendrier. Ce schéma est basé sur le cryptosystème de Niederreiter et
s’appuie sur le problème du décodage par syndrome ainsi que sur l’indistinguabilité
des codes de Goppa binaires. L’aspect encombrant de ce schéma (clé publique de
grande taille) est peut-être ce qui a freiné l’étude des problèmes liés à sa mise en
œuvre. Cette partie s’efforce de montrer que malgré cela, le schéma peut être utilisé
en pratique en proposant en mise en œuvre générant une signature en un temps de
l’ordre de la seconde.
Dans une deuxième partie est présentée une mise en œuvre de plusieurs algo-
rithmes de la famille appelée Information Set Decoding. Cette famille d’algorithme
est utilisée pour décoder un code linéaire de façon générique c’est-à-dire sans utiliser
la potentielle structure du code. La plupart des cryptosystèmes basés sur les codes
reposent leur sécurité sur la difficulté de résoudre ce problème. Il est important de
trouver les algorithmes permettant de le résoudre le plus efficacement possible afin de
dimensionner les cryptosystèmes. Cette partie présente une mise en œuvre de deux
algorithmes de cette famille (pouvant être étendue à d’autres) et montre les résultats
de ces algorithmes appliqués à des challenges cryptographiques proposés par D. Bern-
stein, T. Lange et C. Peters en 2011 ainsi que leur application lors de la cryptanalyse
d’un schéma de chiffrement proposé par C. Löndahl et T. Johansson en 2012.
Loading...