Des codes correcteurs pour sécuriser l’information numérique

Par où commencer ?

Avant de rentrer dans le vif du sujet, je souhaite prendre un peu de recul afin notamment de pouvoir motiver mes travaux. On discutera par la suite de codes correcteurs, essentiellement, mais encore de cryptographie. Des mots qui parlent bien peu au grand public et qui me sont aujourd’hui familiers. Ces domaines appartiennent à ce que certains appellent les sciences du numérique. On considère en effet depuis peu que l’informatique est une science. J’encourage le lecteur intéressé à consulter l’article suivant [DB09] pour une discussion plus détaillée du sujet en compagnie de Gilles Dowek et Gérard Berry. L’informatique est aussi un domaine jeune et en plein essor comme chacun sait. C’est un domaine déjà vaste et les codes correcteurs et la cryptographie en sont des branches. Ces branches sont reliées à celle d’un autre arbre, beaucoup plus vaste celui-là, l’arbre des mathématiques. Codes correcteurs et cryptographie reposent bien souvent sur de l’algèbre, de l’arithmétique, de la géométrie et la liste ne se veut pas exhaustive. Nous sommes donc à la frontière entre informatique et mathématiques. Je n’ai pas connaissance de statistiques sur le sujet mais on sait que la majorité des utilisateurs de l’informatique ignore le fonctionnement basique d’un ordinateur. L’utilisateur lambda ignore bien souvent ce que l’on peut considérer comme le minimum requis. Les préoccupations de l’utilisateur sont différentes. De ce fait, l’utilisateur est « déconnecté » et ne comprend ni comment ça marche ni ce que les chercheurs cherchent. La cryptographie et la théorie des codes sont des domaines distincts mais il existe des liens puissants entre ces deux sciences [MS86]. L’objectif de la cryptographie est de « sécuriser » les données numériques contre des « ennemis » . L’objectif des codes est également de « sécuriser » les données numériques contre des « ennemis » . L’absence de contexte rend ces définitions vagues et impropres mais elle met en évidence des similitudes fortes entre les deux domaines. La différence entre eux provient du contexte et du sens que l’on donne aux mots « sécuriser » et « ennemis » . Les codes correcteurs sont utilisés notamment dans les télécommunications ou pour le stockage d’informations. Ils permettent alors de détecter et de corriger des erreurs. On entend par le terme « erreur » , une altération ou une perte partielle ou totale de l’information. Ces erreurs sont l’ennemi du codeur. Des causes multiples peuvent être à l’origine de ces erreurs. Des poussières ou des rayures peuvent dégrader les données contenues sur un disque Blu-ray ou un DVD. Des perturbations électromagnétiques peuvent détériorier les données dans les communications satellitaires ou téléphoniques. Les codes correcteurs sont encore utilisés dans diverses technologies de communication (ADSL, fibre optique et USB entre autres). Leur histoire remonte à la fin des années 50 et fait intervenir des chercheurs tels que Richard Hamming, Marcel Golay et Claude Shannon. Le lecteur peut consulter [Tho83] pour de plus amples informations sur ce sujet ainsi que [Moo05, page 44] pour avoir une vision synthétique d’événements charnières qui ont jalonné cette histoire.

Une notion fondamentale des codes correcteurs est la redondance. Plaçons nous dans le contexte des télécommunications. Les messages transmis contiennent une information qui peut être altérée. Afin de conserver l’information, ils sont préalablements transformés. On parle de codage de l’information. Le codage peut être schématisé comme étant une suite d’opérations mathématiques inversibles. Le codage modifie le message et le rallonge. Le message codé ne contient plus seulement l’information brute mais aussi de la redondance. Cette redondance peut permettre (ou non) au destinataire de reconstituer l’information en cas de dégradation. En contrepartie, la transmission des messages codés prend davantage de temps puisqu’il y a plus de données à transmettre. Cette capacité de pouvoir corriger ou non des erreurs dépend des propriétes du code.

La cryptographie possède une histoire beaucoup plus riche du fait de son ancienneté. Elle existait en effet avant notre ère, bien qu’elle ait été alors fort différente de la cryptographie contemporaine. Elle est l’une des deux composantes de la cryptologie, la seconde étant la cryptanalyse. La cryptologie fut autrefois l’art du secret et elle est aujourd’hui devenue la science du secret. Il existe de nombreux ouvrages qui relatent son histoire, parmi lesquels on peut citer [Kah96, Ste98, Sin99]. La cryptographie poursuit quatre objectifs : chiffrement, authentification, intégrité et non-répudiation. La non-répudiation fournit la preuve qu’un message a été envoyé ou reçu. L’intégrité certifie que le message reçu est identique au message envoyé. L’authentification prouve l’identité des auteurs d’un message. La confidentialité assure que seuls les destinaires d’un message pourront le lire. Sa soeur, la cryptanalyse est une discipline dont le but est d’analyser la sécurité des systèmes cryptographiques. Elle permet donc de connaître leurs faiblesses et donnent du travail au cryptographe. Cela donne lieu à des échanges perpétuels entre les deux disciplines. La cryptographie s’est longtemps cantonnée au domaine militaire. Elle possède aujourd’hui de nombreuses applications dans le civil. Son utilisation nous apporte certaines garanties de sécurité essentielles. Elle ne nous apporte néanmoins pas toutes les garanties. Il faut garder à l’esprit que la sécurité informatique est un domaine vaste qui englobe la cryptographie.

Codes algébriques

Nous allons tout d’abord présenter quelques structures algébriques. Nous nous servirons de ces objets mathématiques par la suite et ce, aussi bien en théorie des codes qu’en cryptologie. Nous donnerons également un certain nombre de propriétés que possèdent ces objets. Nous allons définir certaines familles de codes linéaires en bloc avec lesquelles nous aurons à travailler. Nous nous intéresserons essentiellement aux familles des codes cycliques ainsi qu’à celles des codes alternants. Il existe bon nombre de codes linéaires, nous en recensons certains dans la Figure 2.1. Nous n’expliciterons pas tous les liens qui les relient car cela sortirait du cadre de ce document. Mais, pour commencer, nous allons devoir définir ce qu’est un code linéaire en blocs ainsi que les paramètres essentiels qui permettent de les caractériser. Nous nous intéresserons encore à certaines des propriétés de ces codes.

Définition 1 (Structure Algébrique). Un ensemble est muni d’une structure algébrique si une ou plusieurs lois de composition sont définies sur cet ensemble.
Exemple 1. De très nombreuses structures algébriques ont été étudiées. Il n’est pas question de les recenser ici. On peut néanmoins citer : les groupes, les anneaux, les corps, les espaces vectoriels.

Structures algébriques

Définition 2 (Monoïde). Un monoïde est un ensemble muni d’une loi de composition interne associative admettant un élément neutre.
Exemple 2. L’ensemble des entiers positifs muni de l’addition (N,+) forme un monoïde.
Définition 3 (Groupe). Un groupe est monoïde admettant pour chaque élément de l’ensemble, un élément symétrique.
Remarque 1. Un groupe (G, +) est dit abélien ou commutatif si a + b = b + a, ∀a, b ∈ G.
Exemple 3. L’ensemble des entiers relatifs munis de l’addition (Z,+) forme un groupe. L’ensemble Sn des permutations de J1, nK muni de la loi de composition forme le groupe symétrique d’indice n.
Notation 1. En notation additive, l’élément symétrique d’un élément x d’un groupe (G, +) est appelé l’opposé de x, on le note −x. En notation multiplicative, l’élément symétrique d’un élément x d’un groupe (G, ×) est appelé l’inverse de x, on le note x −1.

La correction d’erreurs et les codes cycliques

La famille des codes cycliques est une classe bien connue de codes correcteurs d’erreurs. Nous traitons des codes cycliques binaires 3-correcteurs et de leurs duaux. Soit F2m l’extension du corps à deux éléments F2 de degré m et soit n un entier impair. Considérons un code cyclique binaire C de longueur n et soit α une racine primitive n-ième de l’unité dans F2m. On peut décrire C comme un idéal principal, dans l’anneau F2[X]/(Xn − 1), avec le polynôme générateur g sur F2, où n | (2m − 1). Par conséquent, les zéros de g peuvent être utilisés pour définir C. L’ensemble de définition Z de C est l’ensemble des exposants i de l’élément primitif α tel que α i est une racine de g. Notez que si z est une racine de g, z 2 i est également une racine de g quel que soit i. En d’autres termes, Z est une union de 2 classes cyclotomiques modulo n. La plupart du temps, Z est décrit de façon concise par la liste des différents représentants de ces classes cyclotomiques. Si la longueur du code est 2 m − 1, i.e. α est un générateur de F2m, alors le code est dit primitif.

Les codes BCH forment une classe importante des codes cycliques. Un code cyclique généré par g(X) = ppcm({M(i) (X)}i∈I ) où M(i) (X) est le polynôme minimal de α i par rapport à F2 et où I est un ensemble de δ−1 entiers consécutifs, est un code BCH avec une distance construite δ. En particulier, si I = {1, 2, . . . , δ − 1}, alors le code BCH est dit au sens strict. Kasami [Kas71] a introduit certaines classes de codes cycliques primitifs binaires 3- correcteurs (i.e. leur distance minimale est 7) similaires aux codes BCH 3-correcteurs, dans le sens où leur ensemble de définition est l’union de 3 classes cyclotomiques. Ces codes ont une dimension k ≥ n − 3m. Cela signifie aussi que, ces codes ont asymptotiquement un haut taux d’information et de plus, leur distance minimale est optimale. En effet, la borne de Hamming implique que des codes cycliques longs définis par τ classes cyclotomiques distinctes ont une capacité de correction t ≤ τ . Une de ces classes est {1, 2 ℓ + 1, 2 3ℓ + 1} avec pgcd(ℓ, m) = 1 et m impair. Plus tard Bracken et Helleseth dans [BH09b] ont découvert la classe {1, 2 ℓ + 1, 2 2ℓ + 1} avec pgcd(ℓ, m) = 1.

Nous examinons la classe {1, 2i + 1, 2j + 1} pour i, j > 1, i 6= j. Nous tentons de généraliser la sous-classe {1, 2 ℓ+1, 2 3ℓ+1} et {1, 2 ℓ+1, 2 2ℓ+1} avec pgcd(ℓ, m) = 1 à la classe {1, 2 ℓ+1, 2 pℓ+1} avec pgcd(ℓ, m) = 1 et p > 1.

Une autre classe de codes cycliques 3-correcteurs avec l’ensemble de définition {1, 2ℓ−1 + 1, 2 ℓ + 1} pour m = 2ℓ + 1 a été introduite dans [MS83]. La question a été soulevée de savoir si ces codes ont la même distribution de poids que le code BCH. Plus tard, il a été prouvé que cela était vrai dans [vDV96, vDV97]. Ils ont montré que les duaux de ces codes ont la même distribution de poids que le dual des codes BCH. Cela nous a motivés à étudier la distribution de poids de la classe générale {1, 2i + 1, 2j + 1}. Par le calcul, jusqu’à m < 14, nous vérifions que le dual de tous les codes 3-correcteurs qui ont un ensemble de définition {1, 2i + 1, 2j + 1} et qui ne sont pas BCH, ont la même distribution de poids que le dual des codes BCH 3- correcteurs. Nous montrons que ce résultat reste vrai pour tout m impair en nous appuyant sur un théorème dû à Kasami [Kas69, Théorème 15 (ii)(1)].

Par ailleurs, nous étudions la distance minimale des duaux des codes 3-correcteurs avec un ensemble de définition {1, 2i+1, 2j+1} sur F2 et sur F2m. Dans la littérature, de nombreuses bornes inférieures théoriques sur la distance minimale des codes cycliques sont connues (e.g. [BRC60, HT72, Roo83, vLW86, Wol89]). Elles reposent soit sur les propriétés de distributions régulières de certain motifs contenus dans l’ensemble de définition, ou sur le nombre de points rationnels des courbes algébriques sur les corps finis. Schaub [Sch88] a pris une approche algorithmique pour calculer une borne inférieure sur la distance minimale d’un code cyclique donné. Cette idée est particulièrement efficace pour les codes qui ont peu de sous codes cycliques. Nous améliorons la complexité en temps de l’algorithme de Schaub en utilisant un critère d’élagage basé sur la borne BCH afin d’être capable de gérer des codes qui possèdent davantage de sous-codes cycliques. Nous comparons la borne de Schaub avec la borne de Hartmann-Tzeng et la distance minimale des duaux des codes avec l’ensemble de définition {1, 2 i + 1, 2 j + 1}. Augot et Levy-dit Vehel [AL96] ont également appliqué l’algorithme de Schaub pour trouver une borne inférieure de la distance minimale des duaux de codes BCH et ont trouvé que cet algorithme donne de meilleurs résultats que la borne de Ross et que la borne de Weil sur ces codes. Nos résultats numériques révèlent un comportement similaire de la distance minimale des duaux des codes cycliques 3-correcteurs dans la classe {1, 2i + 1, 2 j + 1} pour i, j > 1, i ≠ j.

Table des matières

Introduction
1 Par où commencer ?
2 Codes algébriques
2.1 Structures algébriques
2.2 Notions générales en théorie des codes
2.3 Codes cycliques
2.4 Codes dérivés
2.5 Codes alternants
3 Minorer la distance minimale des codes cycliques
3.1 Bornes théoriques
3.1.1 La borne de Carlitz-Uchiyama (1957)
3.1.2 La borne BCH (1960)
3.1.3 La borne de Hartmann-Tzeng (1972)
3.1.4 Les bornes de van Lint-Wilson (1986)
3.2 Borne algorithmique
3.2.1 L’algorithme de Schaub (1988)
3.2.2 Optimisations
3.3 La distance minimale en chiffrement à flot
3.3.1 Les codes cycliques et les fonctions booléennes
3.3.2 Minorer l’immunité spectrale de fonctions booléennes
4 La classe de codes cycliques {1, 2i + 1, 2j + 1}
4.1 Caractériser les codes cycliques 3-correcteurs
4.1.1 Résultats théoriques
4.1.2 Résultats calculatoires
4.2 Calculer leurs énumérateurs des poids
4.3 La question de l’équivalence avec le BCH 3-correcteur
5 Déchiffrer les cryptosystèmes de type McEliece
5.1 Les codes de Goppa classiques (1970)
5.2 Les cryptosystèmes de McEliece et Niederreiter
5.2.1 Description du cryptosystème classique de McEliece (1978)
5.2.2 Description du cryptosystème de Niederreiter (1986)
5.3 Algorithme de décodage algébrique des codes de Goppa
5.4 Complexité théorique du déchiffrement
6 Les algorithmes de recherche de racines
6.1 La procédure de Chien (1964)
6.2 L’algorithme de la trace de Berlekamp (1971)
6.3 L’algorithme de Cantor et Zassenhaus’ (1981)
6.4 Les procédures de Zinoviev (1996)
6.4.1 Trouver les racines d’un polynôme affine
6.5 L’algorithme Berlekamp Trace – Zinoviev
6.5.1 Accélérer le déchiffrement de McEliece
6.5.2 Pseudocode de BTZ
6.5.3 Mise en œuvre
6.5.4 Comment calculer la complexité théorique ?
6.6 Résultats de simulation
Conclusion

Télécharger le rapport complet