Table des matières
Introduction
1 Contexte d’étude
2 Travaux précédents
2.1 En théorie de la complexité
2.2 En cryptographie basée sur les codes correcteurs (depuis les travaux de Gabidulin)
3 Notre contribution
4 Plan
Première partie : Généralités
Chapitre I : Notions essentielles en théorie des codes ; Applications à la cryptographie
1 Théorie de l’information
1.1 Transmission d’un signal
1.2 Codage de canal
2 Théorie des codes correcteurs d’erreurs
2.1 Code et principales caractéristiques d’un code
2.2 Structure d’espace métrique sur C
2.3 Décodage
2.4 Codes linéaires
2.4.1 Généralités
2.4.2 Bornes sur les paramètres d’un code
2.4.3 Matrice génératrice, matrice de contrôle de parité
2.4.4 Code dual
2.4.5 Exemples d’algorithmes de calcul pour la matrice de parité
2.5 Aspects algorithmiques du décodage ; exemples
2.5.1 Décodage d’un code linéaire par syndrome
2.5.2 Le problème du décodage par syndrome et sa complexité
2.5.3 Décodage d’un code linéaire par ensemble d’information
2.6 Codes cycliques
3 Utilisation des codes correcteurs dans un contexte cryptographique
3.1 Notion de cryptosystème
3.1.1 Définition
3.1.2 Cryptosystèmes symétriques, cryptosystèmes asymétriques
3.1.3 Sécurité d’un cryptosystème
3.1.4 Notion de problème difficile
3.2 Application des codes correcteurs à la cryptographie : le cryptosystème de McEliece
3.2.1 Présentation du cryptosystème
3.2.2 Sécurité du cryptosystème de McEliece
3.2.3 Avantages et inconvénients de la cryptographie basée sur les codes correcteurs
4 Conclusion
Chapitre II : Construction des corps finis
1 Idée de base : quotient d’un anneau de polynômes par un polynôme irréductible
2 Cardinal d’un corps fini
3 Groupe multiplicatif d’un corps fini
4 Unicité d’un corps fini à isomorphisme près
5 Construction effective
6 Cas particulier important : construction d’un corps par adjonction d’un élément primitif à son sous-corps premier
7 Implémentation
Deuxième partie : Polynômes de Ore, q-polynômes et applications
Chapitre III : Polynômes de Ore et q-polynômes
1 Automorphismes des corps finis
2 Polynômes de Ore
2.1 Définition
2.2 Sous-corps des éléments commutatifs pour la multiplication
2.3 Exemples de calculs
2.4 Degré d’un polynôme de Ore
2.5 Division euclidienne à droite
2.6 Division euclidienne à gauche
2.7 Evaluation d’un élément par un polynôme de Ore
2.8 Racine d’un polynôme de Ore
3 Anneaux de q-polynômes (ou polynômes linéarisés)
3.1 Définitions et premières propriétés
3.2 Produit de q-polynômes
3.3 Les q-polynômes vus comme des cas particuliers des polynômes de Ore
3.3.1 Bijection entre un anneau de Ore et un anneau de q-polynômes . .
3.3.2 Conséquences
3.4 Complexité des opérations arithmétiques dans Fqm[Xq, θ]
3.5 Racines de q-polynômes
3.5.1 Structure de l’ensemble des racines d’un q-polynôme
3.5.2 Polynôme associé à un espace vectoriel
3.5.3 Complexité
3.5.4 Structure des racines du RGCD, du RLCM de deux q-polynômes
3.6 Application : utilisation des q-polynômes pour déterminer l’intersection de deux sousespaces vectoriels
Chapitre IV : Matrice de multiplication à droite pour des q-polynômes et applications
1 Résultants et sous-résultants sur un anneau commutatif
1.1 Résultant de deux polynômes
1.1.1 Définition à partir de la matrice de Sylvester et propriétés
1.1.2 Matrice de multiplication et application au calcul du résultant
1.2 Suites des sous-résultants
1.3 Lien entre sous-résultants et PGCD
2 Calcul des coefficients sous-résultants à partir d’une matrice extraite de la matrice de multiplication
2.1 Polynôme déterminantal et application au calcul des sous-résultants
2.2 Utilisation de la matrice de multiplication
3 Résultant de deux polynômes de Ore
3.1 Utilisation de la matrice de multiplication à droite
3.1.1 Idée générale
3.1.2 Matrice de multiplication à droite et nouvelle définition du résultant
3.2 Propriétés du résultant de deux polynômes de Ore
4 Application : algorithme de recherche du PGCD de deux polynômes de Ore
4.1 Algorithme de recherche du PGCD
4.2 Etude de la complexité
5 Sous-résultants de deux polynômes de Ore
5.1 Opérateurs de Ore
5.2 Sous-résultants de deux polynômes de Ore
6 Calcul des coefficients sous-résultants de deux polynômes de Ore à partir d’une matrice de multiplication
6.1 Liens entre les deux points de vue sur les polynômes de Ore
6.2 Généralisation de la formule vue dans le cas commutatif
Troisième partie : Métrique rang et cryptosystème LRPC
Chapitre V : Codes correcteurs en métrique rang, applications à la cryptographie
1 Définitions
2 Codes en métrique rang
2.1 Définitions
2.2 Bornes sur les codes en métrique rang
2.2.1 Borne de Singleton
2.2.2 Borne de Gilbert-Varshamov
3 Décodage en métrique rang
3.1 Problèmes liés au décodage en métrique rang
3.1.1 Problème du décodage par syndrome en métrique rang
3.1.2 L’algorithme d’Ourivski-Johanson
3.1.3 Un nouvel algorithme
3.2 Importance de la complexité algorithmique du décodage des codes en métrique rang
4 Un exemple fondamental : les codes de Gabidulin
4.1 Définition
4.2 Propriétés
4.3 Décodage des codes de Gabidulin
5 Cryptographie en métrique rang
5.1 Introduction
5.2 Le cryptosystème GPT
5.3 Attaque structurelle
6 Conclusion
Chapitre VI : Codes LRPC ; cryptosystème LRPC
1 Généralités
2 Résultats sur le produit de deux sous-espaces
3 Low Rank Parity Check Codes
3.1 Contexte d’utilisation et définitions
3.2 Cas particulier important : les codes DC-LRPC (Double Circulant Low Rank Parity Check)
3.2.1 Matrices circulantes ; matrices coublement circulantes
3.2.2 Codes DC-LRPC
3.3 Création d’une matrice de décodage à coefficients dans le corps de base Fq à partir de la matrice de parité
4 Algorithme de décodage pour les codes LRPC
4.1 Idée générale
4.2 Présentation de l’algorithme de décodage
4.3 Preuve de la validité de l’algorithme
4.4 Probabilité d’échec
4.5 Complexité du décodage
4.6 Bilan
4.7 Exemple
5 Application à la cryptographie : le cryptosystème LRPC
5.1 Le cryptosystème LRPC
5.2 Paramètres du cryptosystème LRPC
6 Sécurité du cryptosystème LRPC
6.1 Sécurité sémantique
6.2 Sécurité pratique
6.2.1 Attaque du message
6.2.2 Attaque par clé contrefaite (Spurious key)
6.2.3 Attaque sur la clé secrète par repliement du code
6.2.4 Une première remarque
6.2.5 Code replié
6.2.6 Amélioration de l’attaque grâce à un repliement du code
6.2.7 Protection contre cette attaque
7 Exemples de paramètres et comparaison avec les MDPC
7.1 Exemples de paramètres
7.1.1 Premiers exemples
7.1.2 Nouveaux paramètres résistants à l’attaque par repliement
7.2 Comparaison avec le cryptosystème MDPC
8 Implémentation et temps d’exécution
9 Pistes de recherche
10 Conclusion
Appendice : Démonstrations des résultats du paragraphe 2
Conclusion et pistes de recherche
1 Concernant les q-polynômes
2 Concernant la cryptographie sur les codes correcteurs en métrique rang
Bibliographie
