La soutenance de Gabrielle De Micheli (CARAMBA), intitulée “Cryptanalyses de logarithmes discrets : crible algébrique et réseaux pour attaques par canaux auxiliaires”, se déroulera le Mardi 25 Mai 2021 à 13h. En raison de la situation sanitaire, la soutenance se fera en anglais par visioconférence.
Résumé :
Les cryptosystèmes dits à clé publique sont construits à l’aide de fonctions à sens unique qui assurent à la fois la sécurité et l’efficacité des cryptosystèmes. L’un des deux principaux candidats envisagés à l’origine pour construire de tels cryptosystèmes est l’exponentiation modulaire avec son opération inverse, le calcul de logarithmes discrets. Dans cette thèse, nous étudions la sécurité de protocoles qui utilisent des exponentiations modulaires où l’exposant est un secret du protocole. Afin d’évaluer la sécurité de tels protocoles, on peut d’une part estimer la difficulté de résoudre directement le problème du logarithme discret (DLP) dans les groupes considérés par les protocoles, ou examiner les vulnérabilités issues de l’implémentation des algorithmes d’exponentiation rapide.
Une première façon d’estimer la sécurité des protocoles basés sur la difficulté du problème du logarithme discret est d’étudier directement la complexité des algorithmes qui résolvent ce dernier. Dans cette thèse, nous étudions la complexité asymptotique des algorithmes qui résolvent le DLP sur des corps finis Fpn précisément de la forme où les couplages prennent leurs valeurs.
Nous proposons également une première implémentation et un calcul record d’un logarithme discret dans un corps fini de 521 bits en utilisant l’algorithme Tower Number Field Sieve, une variante de NFS dont la complexité asymptotique est meilleure. Cette variante n’avait jamais été implémentée auparavant en raison de la difficulté du crible algébrique dans des dimensions supérieures à deux.
Enfin, la sécurité des protocoles déployés ne repose pas seulement sur la difficulté du problème mathématique sous-jacent, mais aussi sur l’implémentation des algorithmes considérés. De nombreux algorithmes d’exponentiation modulaire rapide se sont accumulés au fil des ans et certaines implémentations ont fait apparaître des vulnérabilités exploitables par des attaques par canaux auxiliaires. Un second aspect de cette thèse considère donc les principales méthodes pour reconstituer une clé secrète lorsque des informations partielles sont récupérées à partir d’un canal auxiliaire.
Composition du jury :
Rapporteurs :
Martin Albrecht, Royal Holloway, University of London, Royaume-Uni
Frederik Vercauteren, KU Leuven, Belgique
Examinateurs :
Robert Granger, University of Surrey, Royaume-Uni
Steve Kremer, Inria, Nancy, France
Tanja Lange, Technische Universiteit, Eindhoven, Pays-Bas
Palash Sarkar, Indian Statistical Institute, Inde
Directeurs de thèse :
Pierrick Gaudry, CNRS, Nancy, France
Cécile Pierrot, Inria, Nancy, France
