Mise en oeuvre de cryptosystèmes basés sur les codes correcteurs d’erreurs et de leurs cryptanalyses

Cryptographie 

Depuis l’antiquité, l’homme a cherché à communiquer des informations de façon confidentielle malgré l’exposition potentielle à des regards indiscrets. L’essor des télécommunications a accru le besoin d’outils assurant la confidentialité, l’authenticité et l’intégrité des informations. Des secrets d’États à la protection de la vie privé, en passant par la sécurité des transactions commerciales, la cryptographie a aujourd’hui de nombreux usages. Jusqu’aux années 1970, les systèmes de chiffrement se basaient sur une information secrète, partagée entre les deux interlocuteurs. Ces systèmes, dits à clé secrète, ont pour avantage un débit élevé mais leur utilisation implique un partage antérieur de cette information secrète. Ce scénario est envisageable à petite échelle pour des besoins ponctuels mais ne l’est pas dans le monde actuel où chacun communique quotidiennement avec des centaines d’entités distinctes potentiellement inconnues (via courrier électronique, navigateur web, téléphonie mobile, matériel réseau, . . .).

En 1976, Diffie et Hellman [25] publient ce qui deviendra la base de la cryptographie à clé publique. Ils énoncent les propriétés nécessaires à de tels systèmes et donnent un protocole permettant à deux interlocuteurs de se partager une information secrète uniquement à partir de données publiques. En pratique, les systèmes respectant ce protocole, dits à clé publique, ont souvent des débits faibles; ils sont donc souvent utilisé afin de démarrer une communication protégée par un chiffrement à clé secrète. Ce procédé est connu sous le nom de cryptographie hybride. En 1977 naît l’algorithme RSA de Rivest, Shamir et Adelman [63], le premier cryptosystème à clé publique .

Depuis ce jour, la recherche sur ce sujet n’a eu de cesse de proposer de nouveaux systèmes et d’affaiblir les existants. Cryptographes et cryptanalystes s’affrontent afin de concevoir et d’évaluer des systèmes à la fois rapides et dignes de confiance. Ces systèmes sont constitués des éléments suivants :
– Une fonction de génération de clé qui génère un couple (Ksec, Kpub) aléatoirement.
– Une fonction de chiffrement Enc qui, en utilisant la clé publique Kpub, associe à un message clair m un message chiffré c.

c = Enc(Kpub, m)

– Une fonction de déchiffrement Dec qui, en utilisant la clé secrète Ksec, calcule le message clair m associé à un message chiffré c.

m = Dec(Ksec, c)

Il existe actuellement trois familles de cryptosystèmes à clé publique se basant sur trois domaines différents : la théorie des nombres, les réseaux euclidiens et les codes correcteurs d’erreurs. Les systèmes les plus répandus aujourd’hui sont basés sur la théorie des nombres et reposent sur deux problèmes supposés difficiles, le problème de la factorisation et celui du logarithme discret. Ce quasi-monopole est inquiétant car il n’existe aucune preuve mathématique de la réelle difficulté de ces problème si ce n’est la non-existence de preuve opposée. Autre faille de ces systèmes, Shor [66] a montré que ces deux problèmes pouvaient être résolus en temps polynomial dans le modèle de l’ordinateur quantique. Certes, celui ci est loin d’être opérationnel mais la menace est bien réelle et il faudra, le jour venu, disposé d’alternatives crédibles afin de ne pas se retrouver dépourvu. Voilà pourquoi depuis plusieurs années la recherche examine les systèmes basés sur les réseaux euclidiens et les codes correcteurs d’erreur. Cette thèse s’insère dans le contexte de l’évaluation des cryptosystèmes basés sur les codes correcteurs d’erreurs.

Les fonctions de chiffrement asymétriques se basent sur des fonctions à sens unique munis d’une trappe. Une fonction à sens unique doit être évaluable efficacement pour tout message clair, et trouver la préimage d’un élément généré par cette fonction doit être une opération difficile. La trappe permet au destinataire légitime de simplifier l’inversion et donc de déchiffrer le message. Elle doit en conséquence rester secrète pour conserver le caractère à sens unique de la fonction. Une opération sera considérée difficile lorsqu’il sera considéré déraisonnable, en termes de temps ou de moyens et tenant compte du bénéfice potentiel, par l’entité adverse de tenter d’effectuer cette opération. Un système cryptographique dispose de b bits de sécurité si un ordinateur doit effectuer au moins 2b opérations pour résoudre le plus simple des problèmes sur lequel se base le système. Étant donné l’évolution perpétuelle de la technologie, il faut régulièrement réévaluer le nombre de bits de sécurité nécessaire pour considérer une opération difficile. Il est considéré aujourd’hui qu’un minimum de 112 bits de sécurité est nécessaire pour protéger une information d’ordre gouvernementale [5].

Codes correcteurs d’erreurs 

Les codes correcteurs d’erreurs ont pour objectif de permettre la transmission d’information malgré l’ajout éventuel d’erreurs lors de la transmission. Afin d’y parvenir, les codes ajoutent une redondance au message à transmettre qui, lorsqu’un nombre suffisament faible d’élément de ce message étendu est perdu ou altéré, permettra de reconstituer le message initialement envoyé. Cette reconstitution est appellé le décodage. Je m’interesserai principalement aux codes en blocs; codes découpant le message en blocs de taille fixe, et les traitant indépendament l’un après l’autre et plus précisément aux codes linéaires.

Codes linéaires

Lors de l’envoi d’un message composé de lettres d’un alphabet A, celui-ci est découpé en bloc de k lettres auxquels sont ajoutés une redondance via une application linéaire transformant un bloc de k lettres en un bloc de n lettres (où n sera évidement choisi supérieur à k). Ce nouveau bloc est transmis à travers un canal de communication, ce qui altérera potentiellement le bloc. Puisque n est supérieur à k, le message reçu ne fera peut-être par parti de l’image de l’application linéaire appliquée (on en déduit la présence d’au moins une erreur). Le destinataire devra donc trouver l’élément de l’image qui a vraisemblablement été envoyé à l’origine. Cependant, si le nombre d’erreurs ajoutées est trop important, il se peut qu’un autre élément de l’image apparaisse plus vraisemblablement comme étant le bloc d’origine ; voire que le bloc reçu devienne un autre élément de l’image, ce qui nous empêcherait de deviner la présence d’erreurs.

Dans ce cadre, un bon code correcteur d’erreur est un code qui disperse suffisamment les mots de codes (afin de pouvoir corriger plus d’erreurs) tout en ayant un rendement, le ratio k/n , le plus haut possible (afin de limiter le surcoût du codage). Les blocs de k lettres avant transmission sont des vecteurs de k éléments de l’alphabet A et sont appelés des mots d’information. En pratique A sera un corps fini F, ce qui permet de créer l’espace vectoriel, de dimension k, des mots d’information. L’application linéaire appliquée aux mots d’information associe à chacun de ces mots un élément d’un espace vectoriel de dimension n. Puisque n est supérieur à k, l’image de l’application linéaire est un sousespace de dimension k de l’espace F n . Cette image est appelée un code linéaire. La dimension du sous espace, k, est appelée dimension du code et la dimension de l’espace d’arrivée, n, est appelée longueur du code. Les éléments d’un code linéaire sont appelés mots de code. Une matrice formée des vecteurs d’une base d’un code C est appelée matrice génératrice de C . Un mot d’information peut être codé en le multipliant par une matrice génératrice puis le mot de code obtenu peut être décodé en le multipliant par l’inverse de cette même matrice. La matrice génératrice d’un code dont les k premières colonnes  forment la matrice identité k ×k est dite sous forme systématique. Il n’existe qu’une matrice génératrice sous forme systématique pour un code linéaire donné. Un mot d’information codé via une telle matrice est simple à décoder puisqu’il suffit d’extraire les k premières coordonnées du mot de code pour retrouver le mot d’information.

Décodage

Le canal le plus utilisé est le canal binaire symétrique. Il s’agit d’un canal qui transmet des éléments binaires et qui, indépendamment les uns des autres, peut modifier la valeur de chaque bit avec probabilité p. Lors de la réception d’un mot de code bruité, il faut trouver le mot de code qui est vraisemblablement celui qui a été envoyé, c’est-à-dire celui qui a le plus de coordonnées en commun avec ce premier. Dans le cas de mots binaires la distance de Hamming apportent une notion de distance entre des mots et permet donc d’exprimer la notion de « mot le plus proche ».

Exemples

Le code à répétition
Le code à répétition émet chaque bit a fois. Par exemple, pour a = 4, si l’on veut transmettre la chaîne 1011, la séquence codée correspondante est 1111000011111111. Ce code est de dimension 1 et de longueur a, chaque bit étant pris un par un et transformé en a bits. Le rendement est donc de 1/a , ce qui est très faible. La distance minimale entre deux mots de code est a. En effet, il faut changer les a répétitions d’un bit d’un mot de code pour obtenir un autre mot de code. Ce code permet de corriger jusqu’à ⌊a/2⌋ erreur et dispose d’un algorithme de décodage très simple : il suffit de prendre le bit majoritaire de chaque bloc de a bits. Si l’on reprend l’exemple a = 4 et que le mot reçu est 0100, le mot de code le plus proche est 0000 et le mot d’information qui a sûrement été envoyé est 0. On remarque que dans cet exemple si le mot reçu est 0110 alors il existe deux mots de code à distance 2 ; on détecte toujours la présence d’une erreur mais le décodage n’est plus unique, on ne sait pas si le mot envoyé est 0 ou 1. Si a est impair alors ce scénario ne peut se produire et tous les mots de l’espace peuvent être décodés de façon unique.

Table des matières

1 Introduction
1.1 Cryptographie
1.2 Codes correcteurs d’erreurs
1.2.1 Codes linéaires
1.2.2 Décodage
1.2.3 Exemples
1.2.4 Codes de Goppa
1.3 Cryptographie basée sur les codes
1.3.1 L’ordinateur quantique
1.3.2 Historique
1.3.3 McEliece et Niederreiter
1.3.4 Sécurité
I Le schéma de signature CFS
2 Introduction
3 Contexte
3.1 Codes de Goppa binaires
3.2 Décodage complet
3.3 CFS initial
3.4 Attaques
3.4.1 Décoder un parmi plusieurs (DOOM)
3.5 Parallel-CFS : une contre-mesure à DOOM
3.6 Implémentation passée
4 Sélection des paramètres
5 Décodage algébrique des codes de Goppa
5.1 Équation clé des codes de Goppa
5.2 Équation clé des codes alternants
5.3 Recherche de racines
6 Mise en œuvre
6.1 Arithmétique des corps finis
6.1.1 Bit-slicing
6.2 Décodage
6.2.1 Mise sous forme polynomial du syndrome
6.2.2 Résolution de l’équation clé
6.2.3 Recherche des racines
6.3 Rejet des instances de décodage dégénérées
6.4 Gérer les échecs de décodage
7 Performances
7.1 Génération d’une signature
7.2 Comparaisons des décodeurs
8 Conclusion
II Information Set Decoding
9 Le problème du décodage par syndrome
9.1 Décodage par paradoxe des anniversaires
9.2 Décodage par ensemble d’information
10 Le décodage par ensemble d’information
10.0.1 Cadre
10.0.2 L’outil de base : la fusion de liste
10.0.3 Les algorithmes SubISD
11 Mise en œuvre
11.1 Fusion de liste
11.1.1 Fusion par tri
11.1.2 Fusion par indexation
11.1.3 Comparaison
11.2 Analyse de la complexité et estimation des paramètres
11.2.1 Probabilité de succès d’une itération
11.2.2 Coût des algorithmes SubISD
11.3 Optimisations
12 Mise en œuvre logicielle
13 Challenges Wild McEliece
14 Conclusion

Télécharger le rapport complet