Recherche

Mon domaine de recherche se rattache à la cryptologie, à l'intersection des mathématiques et de l'informatique.

Thèmes de recherche : cryptanalyse, cryptographie à clef publique, logarithme discret, corps finis, crible par corps de nombres, signatures à l'aide de courbes elliptiques (ECDSA), attaque par canaux cachés, problème de décodage borné (BDD), génération d'aléa, Blockchain...

Logarithmes discrets

La cryptologie consiste en l'étude des techniques utilisées par deux entités pour communiquer en secret en présence d'une personne adverse. Ces techniques, ou cryptosystèmes, qui détaillent comment chiffrer et déchiffrer les messages, sont conçues autours de problèmes calculatoires réputés difficiles. Les propriétés mathématiques sous-jacentes à ces problèmes garantissent que l'attaque de tels algorithmes reste infaisable en pratique par un adversaire malveillant, même si celui-ci dispose de la totalité de la puissance de calcul informatique de la planète. Ainsi, les protocoles mis en jeu s'appuient sur diverses hypothèses provenant souvent de la théorie des nombres, comme la difficulté présumée de factoriser de grands entiers ou de calculer le logarithme discret d'un élément aléatoire dans certains groupes. Mon sujet de thèse porte sur l'étude du problème du logarithme discret dans les corps finis. Le lecteur non averti peut suivre un article de survol large des questions soulevées par les logarithmes discrets, et des réponses actuellement proposées.

Moyenne et grande caractéristiques

Les initiés trouveront dans le Crible Spécial par Corps de Nombres (SNFS) un algorithme de résolution du problème pour les corps finis liés à la cryptographie à base de couplage et dont la caractéristique est de taille moyenne ou grande. Le Crible Multiple par Corps de Nombres (MNFS) s'applique quant à lui sur tous les corps finis de moyenne et grande caractéristiques. Un nouveau crible par corps de nombres proposé par des collègues, avec méthode de sélection polynomiale par conjugaison, améliore la complexité asymptotique en caractéristique moyenne. Combinant ces deux variantes, le Criple Multiple par Corps de Nombres et Méthode de Conjugaison (MNFS-Conj) est actuellement l'algorithme le plus performant asymptotiquement pour tous les corps finis de moyenne caractéristique.

Petite caractéristique

L'année 2014 a été le théâtre de nombreux changements pour les corps finis de petite caractéristique, en témoigne le passage d'une complexité en L(1/3) à L(1/4) dans un premier temps, puis la découverte d'un algorithme quasi-polynomial. L' algorithme simplifié par représentation de Frobenius s'inscrit dans cette lignée, en présentant une manière d'abaisser la complexité des phases polynomiales de calcul des logarithmes discrets de la base de lissité (et de la base de lissité étendue). Bien que négligeables asymptotiquement, ces phases constituent, en pratique, le frein majeur à la résolution du problème du logarithme discret. Nous avons illustré la dégradation de la complexité de O(q^7) à O(q^6) dans le cas général par un record de calcul en caractéristique 3. Le corps fini en question est l'extension de degré 479 construite au dessus du corps de base à 3^5 éléments. Sa cardinalité est donc un entier de 3796 bits - à comparer avec le précédent record dans la même caractéristique, proposé sur un corps fini de 1551 bits.

À la frontière entre petite et moyenne caractéristique

Les corps finis utilisés dans les cryptosystèmes basés sur les couplages vivent asymptotiquement dans ce cas intermédiaire. Le problème du logarithme discret y est très particulier, car il se situe à la frontière entre toutes les familles d'algorithmes pertinentes : les algorithmes quasipolynomiaux, leur ancêtre le crible par corps de fonctions (FFS), ainsi que le crible par corps de nombre (NFS) et toutes ses variantes. Dans une étude du comportement asymptotique du logarithme discret pour les corps finis rattachés aux protocoles de couplage, nous adaptons FFS au cas particulier des extensions composées en montrant comment baisser la complexité des algorithmes en travaillant dans un corps translaté. L'étude générale de tous ces algorithmes nous permet d'évaluer la sécurité des couplages et de donner des valeurs précises de caractéristiques qui permettent d'atteindre les sécurités les plus fortes pour les protocoles sousjacents. De manière innattendue, certaines caractéristiques dites spéciales ou creuses (comme pour les courbes BN par exemple) sont aussi sûres que des caractéristiques de même taille sans forme particulière.

Algèbre linéaire

L'algèbre linéaire, comme une brique scientifique à la base des différentes constructions rationnelles, se retrouve aussi bien dans les fondations les plus élémentaires des mathématiques que de l'informatique. La cryptographie, qui n'échappe pas à cette règle, introduit cependant quelques spécificités, comme la particularité de prendre en compte des systèmes d'équations linéaires dont la majorité des entrées sont nulles, et qui sont alors qualifiés de systèmes creux. Nous proposons d'élargir cette vision aux matrices presque creuses, caractérisées par la concaténation d'une matrice creuse et d'un plus ou moins grand nombre de colonnes denses, et de développer un algorithme dédié à ce type de problèmes. Motivée par le calcul de logarithmes discrets dans les corps finis de moyenne et grande caractéristiques, l' Algèbre linéaire presque creuse trace ainsi un pont entre les problèmes classiques d'algèbre linéaire dense et ceux d'algèbre linéaire creuse, pour lesquels des méthodes particulières ont déjà été établies. Notre algorithme s'applique en particulier à la résolution d'une des trois phases du crible par corps de nombres qui consiste précisement en la recherche d'un élément non trivial du noyau d'une matrice presque creuse.

Réseaux Euclidiens, un outil efficace

Attaque par canaux cachés sur ECDSA

ECDSA est un protocole de signature basée sur les courbes elliptiques très couramment déployé dans l'industrie. La plupart des attaques connues par canaux cachés s'appuient sur les failles éventuelles de l'implémentation de la multiplication scalaire. Lorsque celle-ci utilise une représentation en wNAF, les attaques se font en deux étapes : d'une part la récolte d'informations via des canaux auxiliaires (typiquement des mesures de temps d'accès à la mémoire cache), d'autre part, le traitement de ces informations grâce à des méthodes basées sur les réseaux euclidiens. En étudiant l'une de ces méthodes (EHNP comme Extended Hidden Number Problem) nous sommes parvenus à retrouver la clef secrète d'un utilisateur de ECDSA à partir de seulement 3 signatures. Il s'agissait d'une borne théorique connue mais jamais atteinte en pratique. Notre méthode est plus rapide et présente une meilleure probabilité de succès que la plupart des attaques existantes, sur les mêmes implémentations. En particulier la construction de réseau que nous proposons permet de retrouver la clef secrète même en présence d'un petit nombre d'erreurs de lecture (2% des bits mal lus) lors de la récupération des traces pendant la première phase d'attaque par canaux cachées.

Réseaux de logarithmes discrets, BDD, et borne de Minkowski

Trouver la manière la plus efficace pour empacter des sphères de même taille qui ne peuvent se chevaucher, par exemple des oranges, est un problème de longue date. Les arranger de telle sorte que leur centre forme un réseau euclidien aide à donner de bonnes solutions. En particulier, quand la norme et la dimension sont arbitraires, savoir construire des réseaux denses permet de trouver des bons candidats à ce problème. Cependant la densité des réseaux ne peut être plus grande qu'une certaine borne (qui dépend de la norme et de la dimension) : la borne de Minkowski. Un problème analogue, le problème de décodage borné (BDD en anglais) consiste, étant donné t un vecteur de l'espace, dont on sait qu'il est issu d'un vecteur v d'un réseau auquel s'est rajouté une erreur e (c'est-à-dire t=v+e), à retrouver ce vecteur du réseau dont il est issu. Dans ce conteste la borne de Minkowski permet de dire qu'on ne peut décoder au delà d'une certaine borne, quelque soit le réseau. Pour autant cela ne signifie pas que l'on connaisse d'algorithme capable de le faire, que ce soit de manière générale, ou pour des réseaux bien particuliers. Nous proposons une famille concrète de réseaux denses de dimension arbitraire n pour lesquels BDD peut être résolu de manière détéerministique et en temps polynomial. Notre construction provient d'une adaptation du cryptosystème de Chor-Rivest. En ce qui concerne la construction de ces réseaux, nous avons besoin de calculer des logarithmes discrets dans des corps finis, ce qui peut être fait en temps polynomial pour des paramètres bien choisis. Chacun des réseaux que nous proposons s'accompagne d'un algorithme de décodage capable de décoder jusqu'à de très larges rayons. Pour les normes l1 et l2 nous décodons ainsi des rayons de taille proche (O(log n)) de la borne de Minkowski.

Génération d'aléa et Bitcoin

La génération de nombres aléatoires publics et fiables est nécessaire à de nombreux protocoles de cryptographie. Il a notamment été suggéré de s'appuyer sur l'imprédictabilité inhérente des chaines de blocs pour bâtir une source publique d'aléa. C'est ici qu'interviennent les monnaies électroniques décentralisées, comme le Bitcoin. En effet l'entropie de la chaine du registre public sousjacent au Bitcoin a par exemple été utilisée pour créer des loteries, puis proposée par la suite pour d'autres applications variant de la rédaction de contrats intelligents à l'audit d'éléctions. La malléabilité de l'entropie des chaines de blocs montre cependant qu'un adversaire peut manipuler ces nombres aléatoires, même si celui-ci est tenu par des contraintes financières étroites et qu'il ne dispose que d'une puissance de calcul limitée.
En passant, cette analyse propose une nouvelle illustration des mots de Dyck tout en suscitant une généralisation de ceux-ci.