Soutenance mémoire
Transmission d’un signal
La théorie des communications étudie les moyens de transmettre un message depuis une source jusqu’à un destinataire, via un canal. La source peut être une voix (onde acoustique), une onde électromagnétique, une onde lumineuse (dans une fibre optique), un signal numérique (représenté en langage binaire)… Le canal peut être une ligne téléphonique, une liaison radio, un support (bande magnétique, DVD…) Lors de la transmission par le canal, le signal est susceptible d’être dégradé ou modifié par un bruit (perturbations électriques parasitaires, rayures…). Le codage du signal représente l’ensemble des opérations effectuées entre la sortie de la source et la transmission par le canal. On peut séparer le codage en deux parties : le codage de source et le codage de canal. Le codage de source consiste à représenter le signal en sortie de la source en un format adapté au canal, et ceci de la façon la plus économique possible. Le codage de canal consiste à modifier le signal de façon à ce qu’il soit transmis le plus fidèlement possible malgré le passage à travers le canal bruité. C’est au codage de canal que l’on s’intéresse dans la théorie des codes correcteurs. Pour diminuer au maximum la probabilité de mauvaise transmission, l’idée fondamentale est d’ajouter de la redondance au message, du contenu supplémentaire qui n’ajoute aucune information, ne servant à rien d’autre que retrouver le message de départ. Enfin, le décodage du signal consiste à restituer le plus fidèlement possible le signal de départ à partir du signal à la sortie du canal.
Cryptosystèmes symétriques, cryptosystèmes asymétriques
Les cryptosystèmes symétriques sont les plus anciens. Dans un cryptosystème symétrique, la clé de chiffrement et la clé de déchiffrement sont identiques. Pour qu’un système symétrique soit inconditionnellement sûr il faut que la taille de la clé soit égale à la taille du message. Ainsi, le cryptosystèmes symétriques ne sont dans la pratique jamais utilisés seuls. On les utilise dans des systèmes hybrides, pour transmettre des clés privées de cryptosystèmes asymétriques : En 1976 Diffie et Hellman introduisent les algorithmes de chiffrement et de déchiffrement asymétriques : la clé de chiffrement est différente de la clé de déchiffrement, et la connaissance de la première ne permet pas de retrouver la seconde. La clé de chiffrement peut ainsi être connue de tous ; on parle de clé publique pour la clé de chiffrement et de clé privée pour la clé de déchiffrement. Les algorithmes asymétriques sont basés sur des problèmes complexes c’est à dire dont il n’existe pas de méthode suffisamment rapide pour les résoudre, les exemples les plus courants étant la factorisation de grands nombres ou la détermination de la réciproque de certaines fonctions dans un anneau quotient. Les algorithmes asymétriques sont plus lents et nécessitent des clés de grande taille mais ne nécessitent pas que l’émetteur et le destinataire partagent le secret de la clé.
Sécurité d’un cryptosystème
En essayant de manière exhaustive toutes les combinaisons possibles, il est théoriquement possible pour un attaquant de trouver la clé de déchiffrement, d’autant plus que pour garantir de bonnes performances aux algorithmes on essaie de limiter la taille des clés. Pour qu’un procédé de chiffrement soit sûr il est donc nécessaire qu’une attaque exhaustive ne puisse pas être faite dans un temps « raisonnable ». Nous allons préciser ce point dans le paragraphe suivant. Nous considèrerons notamment lorsque nous présenterons les cryptosystème LRPC qu’un cryptosystème est sûr lorsqu’une attaque exhaustive nécessite un nombre d’opérations de l’ordre de 280. La puissance de calcul des ordinateurs évoluant avec le temps ce nombre est évidemment appelé à augmenter. Cependant, il est toujours possible qu’un attaquant trouve un autre algorithme de décryptage plus efficace lui permettant de décrypter le message (c’est à dire d’en déterminer le contenu sans avoir au préalable la clé de déchiffrement). On considère qu’un cryptosystème est viable lorsque la complexité du décryptage croît exponentiellement en fonction de la taille des paramètres alors que la complexité du chiffrage et du déchiffrage croît polynomialement.
Sécurité du cryptosystème de McEliece
Un attaquant a deux approches pour tenter de décrypter le système : soit il essaie de décoder directement le mot du code (en tentant par exemple une attaque par ensemble d’information), ce qui est difficile si le code est indiscernable d’un code aléatoire, soit il essaie de trouver une décomposition valide de la clé publique (attaque structurelle), ce qui est difficile si la structure du code est difficile à déterminer. La sécurité de ce cryptosystème dépend donc de la famille de codes utilisée. Les codes de Goppa [CFS] sont supposés indiscernables de codes aléatoires et représentent donc naturellement de bons candidats. Cependant la capacité de correction t des codes de Goppa est très basse et l’utilisation de la métrique de Hamming rend alors le système vulnérable aux attaques par ensemble d’information à moins de choisir une clé publique de grande taille importante ce qui est déjà, on va le voir, le principal point faible des cryptosystèmes de McEliece. Les codes de Reed-Solomon, au contraire des codes de Goppa, sont optimaux, et constituent théoriquement de bons candidats pour le cryptosystème de McEliece : pour une clé publique de taille relativement faible, on peut introduire des erreurs de poids plus importants, ce qui augmente la résistance aux attaques par ensemble d’information. Cependant ces codes sont tellement structurés qu’il est possible d’effectuer une attaque structurelle en temps polynomial [SiSh] ce qui les rend inutilisables en pratique.
Avantages et inconvénients de la cryptographie basée sur les codes correcteurs
Le cryptosystème de McEliece est très peu utilisé en pratique pour plusieurs raisons, principalement à cause de sa clé publique qui est une matrice dont la taille est de n k log2 (qm). Cette taille est beaucoup trop importante par rapport aux tailles des clés publiques d’autres systèmes asymétriques : pour une sécurité de 2128 bits, par exemple, le cryptosystème classique RSA nécessite une clé publique (représentant un grand nombre) de quelques milliers de bits alors que l’on dépasse le million de bits pour un cryptosystème de McEliece. Cependant le cryptosystème de McEliece présente plusieurs avantages. On peut notamment mentionner que les opérations de chiffrement et de déchiffrement, correspondant à des opérations d’encodage et de décodage, peuvent être faites de manière très rapide. Mais surtout, comme il est basé sur un problème difficile lié au codes linéaires, il est résistant aux attaques effectuées à l’aide d’ordinateurs quantiques permettant d’attaquer facilement des cryptosystèmes basés sur les nombres premiers ou le logarithme discret.
|
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
Télécharger le rapport complet
