Encodage d’un code linéaire – Matrice génératrice

Encodage d’un code linéaire – Matrice génératrice

Le code à répétitions

Ce code est la forme la plus simple de code par blocs : chaque bit à transmettre est simplement répété d fois dans le message transmis. Ainsi pour d = 3 sur F2 le message 1101 devient 111111000111. Ce code peut aussi être défini sur n’importe quel autre corps et sa matrice génératrice est toujours la matrice 1 × d remplie de 1. Cette construction donne une distance minimale de d mais une dimension de 1 pour une longueur d aussi. On construit donc des codes de la forme [d, 1, d]. Le décodage est ensuite très simple puisqu’il suffit de garder le bit majoritaire dans chaque bloc. La capacité de correction ainsi obtenue est donc de [d−1] . Le principal problème est qu’avec ce code le taux de transmission est de 1d ce qui est très peu. On peut toutefois noter que ce code est parfait quand on choisit d impair.

Les codes de Reed-Solomon

Les codes de Reed-Solomon ont été développés par Reed et Solomon dans les années 50  mais avaient déjà été construits par Bush  un peu avant, dans un autre contexte. Ces codes sont certainement les codes par blocs les plus utilisés pour la correction d’erreurs en étant présents dans les CD, les DVD et la plupart des support de données numériques. Ils sont très utilisés car ils sont extrêmaux du point de vue de la capacité de correction.
Construction
La façon la plus simple de voir ces codes est en tant que code d’évaluation : chaque élément du support du code est associé à un élément du corps Fq sur lequel est défini le code et chaque mot de code est l’évaluation d’une fonction f ∈ F sur le support.
Pour les Reed-Solomon on prend Fq = F2m et F l’ensemble des polynômes de degré strictement inférieur à k sur F2m. Ainsi on a bien un code linéaire de longueur n ≤ 2m et de dimension k.

Les codes aléatoires

Cette dernière catégorie n’est pas vraiment une famille de codes puisqu’il s’agit en fait de tous les codes construits sans structures particulières. Pour obtenir un code aléatoire il suffit de tirer une matrice génératrice aléatoire et de chercher son image. Bien sûr, une fois choisi, le code n’est plus aléatoire, mais de façon générale, un code construit de cette façon aura de bonnes propriétés en moyenne : il a en général une bonne distance minimale.
Malheureusement pour un tel code il n’existe pas d’algorithme de décodage polynomial. Afin d’être plus complet, il pourrait être judicieux de parler un peu des autres variétés de codes utilisées de nos jours. En effet les codes par blocs sont faciles à analyser et sont, historiquement, les codes les plus utilisés. Cependant, ils tendent à être souvent remplacés par des codes comme les turbo codes, LDPC ou autre codes convolutifs ayant de meilleures capacités de correction ou des algorithmes de décodage plus efficaces. Ils sont en général conçus pour effectuer du décodage souple, c’est-à-dire quand on associe à chaque bit reçu une probabilité d’erreur propre.
Ces codes sont cependant beaucoup plus difficiles à analyser, et il est même en général assez difficile de connaître leur exacte capacité de correction. Ils ont pourtant quand même déjà des applications en cryptographie, pour des attaques sur des chiffrements à flots  par exemple. Il faudra par contre certainement encore attendre un peu avant de voir apparaître les premiers cryptosystèmes les utilisant.

Les codes de Goppa

Introduits en 1970, les codes de Goppa  sont des codes linéaires sur un corps fini Fp. Ils ont été beaucoup étudiés dans un premier temps pour leurs propriétés en tant que codes correcteurs d’erreurs et des algorithmes de décodage efficaces qui ont été mis au point . Ensuite, avec l’apparition du cryptosystème de McEliece ils ont été étudiés pour leurs propriétés cryptographiques. Notons que le terme de code de Goppa désigne aussi parfois des codes appartenant à la famille des codes géométriques . Ces dernieres ont aussi de très bonnes propriétés et de multiples applications. Le terme de code de Goppa étudiés dans ce qui suit désignera les codes de Goppa classiques.

Cryptographie à clef publique

La cryptographie est l’ensemble des techniques permettant d’écrire un message de façon brouillée afin que seul son destinataire légitime soit capable de comprendre la teneur du message.
En dépit de l’évolution des moyens de communication depuis l’antiquité, il a toujours été difficile de garantir la sécurité du canal par lequel transite un message. Un cavalier transportant un rapport sur la position d’une armée peut être intercepté par des éclaireurs ennemis ; un employé du télégraphe transmettant des consignes d’investissements boursiers peut être à la solde d’un actionnaire concurrent ; un ordre militaire transmis par les ondes radios peut être capté par n’importe quel récepteur réglé sur la bonne fréquence ; un courriel qui transite sur Internet peut être lu par n’importe quel ordinateur sur la chaîne reliant l’expéditeur au destinataire. Aussi, la problématique d’établir des communications sécurisées en utilisant un médium non sécurisé a toujours été d’importance en vue d’applications militaires, financières, ou simplement du respect de la vie privée.
Le chiffrement est la fabrication du message chiffré à partir du clair et de la clé de chiffrement.
Le déchiffrement est l’extraction du message clair à partir du chiffré en utilisant la clé de déchiffrement.
Le décryptage ou l’attaque est l’extraction du message clair à partir du chiffré sans connaître la clé de déchiffrement.
La cryptanalyse est l’étude théorique d’un système de chiffrement en vue de mettre au point des algorithmes de décryptage.

Le problème NP-complet

Problème de décision
Chaque problème informatique peut se réduire à un problème de décision, c’est-à-dire un problème formulé comme une question dont la réponse est Oui ou Non, plutôt que par exemple ; le problème du voyageur de commerce, qui cherche, dans un graphe, à trouver la taille du cycle le plus court passant une fois par chaque sommet, peut s’énoncer en un problème de décision ainsi : Existe-t-il un cycle passant une et une seule fois par chaque sommet tel que la somme des coûts des arcs utilisés soit inférieure à B, avec B ∈ N.
La théorie de la complexité repose sur la définition de classes de complexité qui permettent de classer les problèmes en fonction de la complexité des algorithmes qui existent pour les résoudre.
Classe L : Un problème de décision qui peut être résolu par un algorithme déterministe en espace logarithmique par rapport à la taille de l’instance est dans L.
Classe NL : Cette classe s’apparente à la précédente mais pour un algorithme non déterministe.
Classe P : Un problème de décision est dans P s’il peut être décidé par un algorithme déterministe en un temps polynomial par rapport à la taille de l’instance. On qualifie alors le problème de polynomial.
Classe NP : Un problème NP est Non-déterministe Polynomial (et non pas Non polynomial, erreur très courante).
Les problèmes dans NP sont tous les problèmes qui peuvent être résolus en énumérant l’ensemble des solutions possibles et en les testant avec un algorithme polynomial.
Par exemple, la recherche de cycle hamiltonien dans un graphe peut se faire avec deux algorithmes :
le premier génère l’ensemble des cycles (ce qui est exponentiel)
le second teste les solutions (en temps polynomial).
Classe Co-NP (Complémentaire de NP) : C’est le nom parfois donné pour l’équivalent de la classe NP, mais avec la réponse non.
Les problèmes complets les plus étudiés sont les problèmes NP-complets. La classe de complexité étant par définition réservée à des problèmes de décisions, on parlera de problème NP-difficile pour les problèmes d’optimisation sachant que, pour ces problèmes d’optimisation, on peut construire facilement un problème qui lui est associé et est dans NP et qui est donc NP-complet.

Table des matières

1.1 Introduction
1.2 Présentation
2 Codes correcteurs d’erreurs 
2.1 Définitions – Encodage
2.2 Décodage – Utilité de la redondance
2.3 Codes parfaits
2.4 Codes linéaires
2.4.1 Encodage d’un code linéaire – Matrice génératrice
2.4.2 Matrice de contrôle
2.4.3 Détermination de la distance minimum
2.4.4 Décodage des codes linéaires
2.5 Quelques exemples
2.5.1 Le code de Hamming
2.5.2 Le code à répétitions
2.5.3 Les codes de Reed-Solomon
2.5.4 Les codes de Goppa
2.5.5 Les codes cycliques, BCH, de Reed-Muller, de Golay
2.5.6 Les codes aléatoires
3 Les codes de Goppa 
3.1 Construction
3.2 Décodage d’un code de Goppa
3.2.1 L’algorithme de Patterson
3.2.2 Les codes de Goppa sont des codes alternants
3.3 Propriétés des codes de Goppa binaires
3.3.1 Une nouvelle caractérisation des éléments du code
3.3.2 Capacité de correction
3.3.3 Indistinguabilité
4 Cryptographie à clef publique 
4.1 Définitions
4.2 Fonction à sens unique
4.3 Le principe général d’un cryptosystème public
4.4 Le problème NP-complet
4.4.1 Problème de décision
4.4.2 Exemple d’un problème NP-complet
4.5 Protocole d’échange de Clé de Diffie-Hellmann
4.6 RSA
4.6.1 Une mauvaise utilisation de RSA
5 Codes correcteurs et cryptographie à clef publique
5.1 Le cryptosystème de McEliece
5.1.1 Génération de clef
5.1.2 Chiffrement
5.1.3 Déchiffrement
5.1.4 Exemples
5.2 La variante de Niederreiter
5.2.1 Génération de clef
5.2.2 Chiffrement
5.2.3 Déchiffrement
5.2.4 Exemple
5.3 Remarques générales
5.4 Sécurité
6 Fonctions de hachage 
6.1 Généralités sur les fonctions de hachage
6.2 la construction de Merkle-Damgard
6.3 Quelques fonctions connues
6.4 Une nouvelle fonction de compression
6.4.1 Utilisation du chiffrement de Niederreiter
6.4.2 Sécurité d’une telle fonction de compression

Télécharger le rapport complet