Ouvrir cette fenêtre en pleine page
  • Imprimer
  • Partager
    • Courriel
    • Twitter
    • Facebook
    • del.icio.us
    • Viadeo
    • LinkedIn

Résultants de polynômes de Ore et Cryptosystèmes de McEliece sur des Codes Rang faiblement structurés

(Document en Français)

Accès au(x) document(s)

Modalités de diffusion de la thèse :
  • Thèse consultable sur internet, en texte intégral.
  • Accéder au(x) document(s) :
    • https://www.theses.fr/2014LIMO0061/abes
    • https://theses.hal.science/tel-01161777
    Ce document est protégé en vertu du Code de la Propriété Intellectuelle.

Informations sur les contributeurs

Auteur
Murat Gaetan
Date de soutenance
09-12-2014

Directeur(s) de thèse
Gaborit Philippe - Ruatta Olivier
Président du jury
Berger Thierry
Rapporteurs
Ulmer Felix - Tillich Jean-Pierre
Membres du jury
Gaborit Philippe - Ruatta Olivier - Otmani Ayoub

Laboratoire
XLIM - UMR CNRS 7252
Ecole doctorale
École doctorale Sciences et ingénierie pour l'information, mathématiques (Limoges ; 2009-2018)
Etablissement de soutenance
Limoges

Informations générales

Discipline
Informatique
Classification
Informatique, information, généralités

Mots-clés libres
Polynôme de Ore, Cryptosystème de McEliece, Cryptographie, Codes correcteurs d'erreurs, Métrique rang, Codes LRPC
Mots-clés
Informatique - Cryptographie
Résumé :

Les techniques de chiffrement les plus utilisées en cryptographie, basées sur des problèmes de théorie des nombres, présentent malgré leur efficacité des défauts notamment une vulnérabilité aux attaques menées à l'aide d'ordinateur quantiques. Il est donc pertinent d'étudier d'autres familles de cryptosystèmes. Nous nous intéressons ici aux cryptosystèmes basés sur les codes correcteurs, introduits par McEliece en 1978 qui, étant basés sur des problèmes difficiles de théorie des codes, ne présentent pas cette vulnérabilité. Ces cryptosystèmes présentent des inconvénients, qui font qu'ils sont peu utilisés en pratique. Selon le code choisi, ils peuvent être vulnérables aux attaques structurelles, mais surtout ils nécessitent des clés de taille très importante.Récemment une nouvelle famille de codes appelés codes MDPC a été introduite ainsi qu'un cryptosystème basé sur cette famille de codes. Les codes MDPC semblent être distinguables seulement en trouvant des mots de poids faibles dans leur dual, les affranchissant ainsi d'une éventuelle vulnérabilité aux attaques structurelles. De plus, en utilisant une des matrices quasi-cycliques, ils obtiennent des clés de taille très compacte.Nous avons pour notre part, travaillé dans le contexte de la métrique rang, une nouvelle métrique introduite en 1985 par Gabidulin qui semble bien adaptée à une utilisation en cryptographie :• Nous avons commencé par travailler autour de la notion de polynôme de Ore et le cas particulier important des q-polynômes. Ces derniers sont des combinaisons linéaires des itérés de l'automorphisme de Frobenius sur un corps fini.Ces polynômes constituent un objet d'étude important en métrique rang, de par leur utilisation dans les premiers cryptosystèmes dans cette métrique. Nous présentons sous une nouvelle forme des résultats déjà connus, et de nouveaux algorithmes pour le calcul du PGCD de deux polynômes de Ore et le calcul des résultants et sous-résultants de polynômes de Ore (ainsi que de polynômes usuels en généralisant au calcul des sous-résultants la formule déjà connue pour les résultants) en utilisant une matrice de multiplication à droite plus petite que la matrice de Sylvester utilisée habituellement.Ces résultats peuvent être réexploités indirectement dans le cryptosystème présenté par la suite bien que celui-ci ne soit pas basé sur les q-polynômes.• La partie suivante de notre travail est consacrée à l'introduction d'une nouvelle famille de codes en métrique rang appelés codes LRPC (pour Low Rank Parity Check codes). Ces codes ont la particularité d'avoir une matrice de parité de poids rang faible (et peuvent donc être vus comme une généralisation des codes LDPC ou MDPC à la métrique rang).Nous présentons le cryptosystème LRPC, un cryptosystème de type Mc Eliece en métrique rang basé sur les codes LRPC. Ces codes sont très peu structurés et sont donc vraisemblablement résistants aux attaques structurelles. La matrice de parité peut être choisie doublement circulante (on parle alors de codes DC-LRPC) ce qui diminue considérablement la taille de la clé.Ainsi, le cryptosystème DC-LRPC cumule les avantages d'offrir une bonne sécurité en étant basé sur un problème difficile (comme tous les cryptosystèmes basés sur les codes correcteurs), d'être faiblement structurés, de disposer d'une clé de taille assez petite (quelques milliers de bits au plus) et d'un algorithme de décodage efficace.Une attaque a été trouvée dans le cas du cryptosystème DC-LRPC. Cette attaque basée sur la notion de code replié permet de baisser significativement la sécurité du cryptosystème dans le cas où le polynôme X^(k-1)+X^(k-2)+⋯+1 est scindable (k désignant la dimension du code). Cependant ce n'est pas le cas pour les paramètres présentés où le cryptosystème reste valide.

Informations techniques

Type de contenu
Text
Format
PDF

Informations complémentaires

Entrepôt d'origine
STAR : dépôt national des thèses électroniques françaises
Identifiant
2014LIMO0061
Numéro national
2014LIMO0061

Pour citer cette thèse

Murat Gaetan, Résultants de polynômes de Ore et Cryptosystèmes de McEliece sur des Codes Rang faiblement structurés, thèse de doctorat, Limoges, Université de Limoges, 2014. Disponible sur https://aurore.unilim.fr/ori-oai-search/notice/view/2014LIMO0061