Le logarithme discret dans les corps finis

Alan Turing ou la cryptographie moderne

   Jusqu’à la Æn du XIXe siècle la cryptographie s’attache principalement à décrire des procédés de chirement, c’est-à-dire à convertir un message brut et clair en un texte illisible auquel seul un petit nombre d’élus sont en mesure de rendre le sens initial. L’idée naïve consiste par exemple à changer chaque lettre par une autre, ou à réarranger l’ordre de celles-ci. Parallèlement, les premières cryptanalyses ne se font pas attendre : à chaque nouvelle méthode de chirement employée, les adversaires reprennent leurs illégitimes tentatives d’en briser le code. Ce n’est qu’avec l’avènement de la radio en 1903 et les enjeux de la première guerre mondiale que la cryptographie marque son premier tournant. L’électricité et l’automatisation permettent un chirement progressivement plus travaillé, complexiÆant celui qu’un soldat ou qu’un o-cier sur le champ de bataille ne parvenait à eectuer seul jusqu’à lors. En plus de la conÆdentialité des messages – l’information n’est accessible qu’à ceux auxquels l’accès est autorisé – on cherche, sans succès d’abord, à garantir leur authenticité – l’identité de celui qui nous écrit est certiÆée – tout comme leur intégrité – une vériÆcation atteste que les données n’ont pas été altérées pendant la transmission du message. EnÆn, l’horreur de la seconde guerre mondiale et la nécessité de ramener la paix lèvent le jour sur le premier des cryptographes modernes : Alan Turing. En achevant la cryptanalyse de la machine Enigma utilisée par les allemands, Turing crée non seulement de toutes pièces ce que l’on considère comme le premier des ordinateurs, mais ouvre par ailleurs le champ d’une cryptographie nouvelle, portée par l’électronique. L’informatique balbutie. La cryptographie quitte l’enfance. Un souci majeur contrarie pourtant son développement pendant trois décennies successives. Pour être honnête, bien qu’entrée dans l’ère moderne, la cryptographie bute encore sur un obstacle de longue date. Pour mieux saisir cette contrariété, nous reprenons l’image classique du core et du cadenas : admettons que le chirement corresponde à la dissimulation d’un message dans un core, suivi du verrouillage de celui-ci par une clef donnée. Le déchirement doit alors permettre à tout détenteur de cette même clef, après voyage du core, de l’ouvrir pour révéler son contenu. La transmission du core-message peut prétendre aux plus hautes mesures de sécurité, qu’en estil du voyage de la clef ? En eet, loin de l’objet matériel, celle-ci revêt très tôt une réalité plus abstraite. Qu’il s’agisse d’une correspondance de symboles, d’un mot, ou dorénavant d’un nombre plus ou moins grand d’octets, le souci de son transfert repose alors sur l’existence de méthodes permettant de faire circuler en amont du protocole cette information par des voies non sécurisées… Ce qui est précisément le problème initial, qui, en un sens, n’est donc toujours pas résolu !

Où trouve-t-on des logarithmes discrets ?

   L’histoire du logarithme discret en théorie des nombres précède largement la découverte du protocole de Die et Hellman. De fait, le calcul de ces logarithmes attire déjà l’attention de Kraïtchik [Kra22, Chap. V] au début du siècle dernier. Hommage posthume, le nom de la méthode sur laquelle nous nous appuierons tout au long de ce manuscrit – la méthode du calcul d’indice– tire son nom de ce premier ouvrage. Pour Kraïtchik, l’indice de gx dans le groupe engendré par g désigne ainsi exactement celui que nous appelons aujourd’hui le logarithme discret de gx, c’est-à-dire l’entier x. Autrement dit, de manière amusante, nous avons assisté à un lent glissement de la sémantique du terme : si un calcul d’indice ne représentait rien d’autre il y a un siècle qu’un calcul de logarithme discret, actuellement la méthode du calcul d’indice couvre certes une vaste famille destinée à calculer ces logarithmes, mais non la totalité des algorithmes de résolution du problème. Néanmoins, la plus ancienne apparition dont on trouve trace précède le manuscrit de Kraïtchik. Dès 1849 certains de nos logarithmes discrets se dissimulent déjà sous les logarithmes de Zech dont la déÆnition est la suivante :
DéÆnition 0.2.1. Si ↵ est l’élément primitif d’un corps Æni, le logarithme de Zech de n en base ↵ est déÆni comme l’entier log↵(n) tel que ↵log↵(n) = 1+↵n.
Le logarithme de Zech d’un entier est donc le logarithme discret d’un élément particulier du corps Æni. L’intérêt des logarithmes de Zech réside dans la traduction des additions dans le corps en question par une simple exponentiation. En eet, l’addition ↵m + ↵n qui est égale à ↵m(1 + ↵mn) =↵m+log↵(nm) peut ainsi se réécrire comme ↵m à la puissance log↵(n m). Le calcul préalable de tables de logarithmes de Zech permettait l’exécution plus rapide d’opérations arithmétiques dans des corps Ænis. En cryptographie, l’intérêt que l’on accorde à ce problème remonte lui aussi quelques années avant les avancées de Die et Hellman. Par exemple, la sécurité des cryptosystèmes à clefs secrètes qui impliquent des registres à décalage à rétroaction linéaire (ou LFSR, de l’anglais linear feedback-shift registers) est étroitement liée aux calculs de logarithmes discrets dans des corps Ænis binaires. Plus précisément, localiser la position d’une sous-séquence donnée au sein de la sortie d’un LFSR peut se traduire par un problème de calcul de logarithme discret dans le corps Æni déÆni par le polynôme de feedback – sous réserve que celui-ci soit bien entendu irréductible, ce qui est souvent le cas. Sans surprise, l’utilisation la plus classique du problème du logarithme discret remonte en 1976, à la présentation du protocole de Die et Hellman [DH76]. Cette découverte justiÆe à elle seule une longue parenthèse ; aussi nous repoussons les détails au paragraphe 0.2.1. Plus tard, en 2000, l’introduction des couplages au sein de la discipline (versions journal [Jou04, BF03]) ravive encore l’attention apportée au même problème, bien que cette fois-ci les groupes dans lequels les logarithmes sont recherchés présentent une structure atypique. Il s’agit par exemple de certains corps Ænis comportant un degré d’extension composé ou une caractéristique de taille moyenne.

Avantages techniques

   Réduction des tailles de clefs. L’intérêt principal provient du fait que la complexité des algorithmes actuels pour résoudre le problème du logarithme discret sur une courbe elliptique générale (ECDLP) est bien plus élevée que celle pour la factorisation d’un entier de taille comparable. Par conséquent, les cryptosystèmes se référant à des courbes elliptiques proposent actuellement la possibilité d’utiliser des clefs de tailles bien plus petites que celles requises par RSA, ou le logarithme discret sur les corps Ænis, pour un niveau de sécurité similaire. Par exemple, pour atteindre un niveau de sécurité équivalent au choix d’un module RSA de taille 2048 bits, l’Agence nationale de la sécurité des systèmes d’information (ANSSI) recommande le choix d’un corps Æni Fp d’ordre premier p de 2048 bits, alors que l’emploi d’un sous-groupe d’une courbe elliptique d’ordre premier de taille 256 bits sut [ANS14]. En plus d’autoriser une forte réduction des tailles de clef pour les protocoles asymétriques, le problème du logarithme discret sur courbe elliptique […] permet d’obtenir, pour des tailles de paramètres réduites, une sécurité comparable à celle exigée pour des primitives symétriques. A l’heure actuelle, on considère de ce fait que les systèmes basés sur les courbes elliptiques surpassent les systèmes plus classiques. Néanmoins, le débat est relancé par les prises de positions récentes des agences américaines : la NSA (National Security Agency) conseille par exemple l’abandon de la cryptographie basée sur les courbes elliptiques. ConÆdentialité persistante. Lorsque l’on utilise RSA en vue de procéder à un échange de clef, l’approche habituelle consiste à ce que l’une des deux parties choisisse une clef secrète aléatoire, la chire avec la clef publique RSA de son correspondant, puis l’envoie par un canal non sécurisé. Un adversaire qui enregistre toutes les communications pourra donc décrypter tous les échanges passés s’il prend possession un jour de la clef privée associée à celle utilisée pour le transfert de la clef commune. S’appuyer sur le problème du logarithme discret permet en revanche de contourner cet écueil, en facilitant la création de schémas de conÆdentialité persistante parfaite (perfect forward secrecy en anglais), pour lesquels la révélation de secrets de long terme ne permet pas de rendre intelligibles des échanges passés [DOW92]. Par exemple, dans l’échange de Die-Hellman, les secrets a et b d’Alice et Bob sont éphémères, tout comme le secret commun gab qu’ils utilisent pour créer leur clef de session partagée. Comme celleci est temporaire, si un adversaire parvient à intercepter ultérieurement l’une d’entre elle, il ne pourra cependant décrypter que le message correspondant. Ainsi, un intrus qui pénétrerait l’ordinateur d’Alice ou celui de Bob ne serait pas capable de reconstituer les clefs des communications précédentes, et donc de décrypter les échanges passés. En pratique, il est aussi possible de combiner des secrets éphémères et à longs termes, c’est-à-dire des clefs privées, pour fournir des schémas orant simultanément une conÆdentialité persistante parfaite, et de la vériÆcation d’identité.

Log Range Decision appartient à NP\co-NP

   Rappelons qu’un problème est dans NP s’il peut être décidé sur une machine de Turing non-déterministe en temps polynomial par rapport à la taille de l’entrée, c’est-à-dire qu’il existe un témoin qui permet de décider en temps polynomial si une solution donnée par exemple par un oracle convient à ce problème. La classe co-NP représente la classe complémentaire de la classe NP, au sens de la théorie de la complexité. Dit autrement, un problème est dans co-NP s’il existe un certiÆcat qui permet de vériÆer en temps polynomial qu’une instance qui ne répond pas au problème donnera la réponse NON. Pour montrer que le problème est dans NP, supposons qu’il existe un entier x 2 J0,BK tel que h = gx, alors cet entier x lui-même est un témoin de ce fait, qui se teste facilement en temps polynomial. Par ailleurs, lorsque g est un générateur de G et que le groupe en question est d’ordre connu, donner un logarithme discret de h en base g est aussi un témoin satisfaisant pour prouver que la réponse est NON. Dans ce cas particulier, le problème appartient donc à la classe co-NP. La situation est cependant plus complexe dans le cas général. En eet, pour poursuivre, nous avons besoin d’un générateur g0 de G, ainsi que de la connaissance de l’ordre |G| du groupe, et de sa factorisation. Au demeurant, puisqu’il y a ‘(|G|) générateurs de G, c’est à dire un grand nombre, g0 se trouve aisément par test de candidats pris aléatoirement dans l’ensemble. Ce générateur g0 étant connu, la connaissance du logarithme discret de g et celui de h en base g0 sut alors à déterminer si h appartient au sous-groupe généré par g ou non, et, au besoin, à montrer qu’aucun des logarithmes discrets de h en base g n’appartient à l’intervalle J0,··· ,BK. Nous en déduisons que le problème Log Range Decision se situe bien dans co-NP, même dans le cas général où g n’est pas un générateur du groupe.

Table des matières

Introduction
0.1 Cryptographie asymétrique et problèmes diciles
0.1.1 Alan Turing ou la cryptographie moderne
0.1.2 L’avènement de la clef publique
0.1.3 A la recherche des problèmes diciles
0.2 Où trouve-t-on des logarithmes discrets ?
0.2.1 Echange de clef de Die-Hellman
0.2.2 Cryptosystèmes basés sur les couplages
0.2.3 Protocoles variés
0.3 En quoi les logarithmes discrets sont-ils bénéÆques ?
0.3.1 Avantages techniques
0.3.2 Diversité algorithmique
0.4 Contributions
0.4.1 Logarithme discret, algèbre linéaire presque creuse et malléabilité de l’entropie du Bitcoin
0.4.2 Organisation du manuscrit
I Algorithmes de calcul de logarithmes discrets 
1 Logarithme et groupes généraux 
1.1 Classes de complexité
1.1.1 Log Range Decision appartient à NP\co-NP
1.1.2 Log Range Decision appartient à BQP
1.1.3 Retrouver |G| à l’aide d’un calcul de logarithme discret
1.1.4 Diculté du cas moyen et auto-réduction aléatoire
1.2 Algorithme de Pohlig–Hellman
1.2.1 Réduction aux ordres des puissances de nombres premiers
1.2.2 Réduction aux ordres premiers
1.3 Logarithme discret en la racine de l’ordre du groupe
1.3.1 Pas de bébés – pas de géants
1.3.2 L’algorithme Rho de Pollard
1.4 Passage à l’échelle du logarithme discret
1.5 Le modèle du groupe générique
1.5.1 Une démonstration d’optimalité ?
1.5.2 Faiblesses du modèle
2 La méthode du calcul d’indice 
2.1 Description générale
2.1.1 Phase préliminaire
2.1.2 Collect des relations, ou phase de crible
2.1.3 Algèbre linéaire
2.1.4 Calcul d’un logarithme individuel, ou phase de descente
2.2 Un souci de friabilité
2.2.1 Friabilité et heuristique
2.2.2 Friabilité et complexité
2.3 Algèbre linéaire creuse
2.3.1 L’algèbre linéaire, un goulot d’étranglement
2.3.2 Algorithmes de résolutions de systèmes linéaires creux
2.4 Calcul d’indice dans les corps Ænis
2.4.1 La récolte des relations, une étape clef
2.4.2 Corps de nombres ou corps de fonctions ?
2.5 Calcul d’indice dans les courbes elliptiques
2.5.1 Courbes de grand genre
2.5.2 Courbes elliptiques particulières
II Le problème du logarithme discret dans les corps Ænis de petite caractéristique 
3 Des algorithmes sous-exponentiels aux complexités quasipolynomiales 
3.1 Préliminaires algébriques pour les corps Ænis
3.1.1 Factoriser des polynômes à coecients dans un corps Æni
3.1.2 Polynômes friables et polynômes irréductibles
3.1.3 Probabilité de factorisation des polynômes
3.1.4 Passage d’une représentation à une autre d’un même corps
3.1.5 A propos du générateur multiplicatif
3.2 L’algorithme de Hellman–Reyneri en Lqk (1/2)
3.2.1 Création des relations
3.2.2 Logarithme individuel .
3.3 L’algorithme de Coppersmith en Lqk (1/3)
3.3.1 Représentation du corps cible
3.3.2 Création des relations
3.3.3 A propos de l’algèbre linéaire
3.3.4 Logarithme individuel et naissance de la descente
3.4 Des polynômes univariés aux polynômes bivariés
3.4.1 Egalités entre polynômes univariés d’inconnues diérentes
3.4.2 Complexité asymptotique
3.5 Changement de paradigme
3.5.1 Construction et non plus recherche de polynômes friables
3.5.2 Fq est le corps de décomposition du polynôme Xq X
3.5.3 Lorsque la descente domine
4 Le Simply : un algorithme par représentation de Frobenius simpliÆé
4.1 Petits polynômes
4.1.1 Les algorithmes par représentation de Frobenius
4.1.2 Choix simpliÆé des polynômes h0 et h1
4.1.3 A la recherche d’une base de friabilité naturelle
4.2 Calculs accélérés de la base de friabilité (étendue)
4.2.1 Une base réduite au degré 2
4.2.2 Extension de la base de friabilité au degré 3
4.2.3 Logarithmes discrets des polynômes de degré 4
4.3 Complexités asymptotiques
4.3.1 Logarithmes discrets des polynômes quadratiques irréductibles
4.3.2 Logarithmes discrets des polynômes cubiques irréductibles
4.3.3 Logarithmes discrets des polynômes quartiques irréductibles
4.4 Application en caractéristique 3
4.4.1 Représentation du corps cible
4.4.2 Base de friabilité initiale
4.4.3 Base de friabilité étendue
4.4.4 L’étape de descente de nouveau dominante
4.4.5 Et voici (enÆn !) un logarithme
4.4.6 Scripts de vériÆcation
4.5 Conclusion en petite caractéristique
III Le problème du logarithme discret dans les corps Ænis de moyenne et grande caractéristiques 
5 Crible par corps de nombres multiple 
5.1 Crible par corps de nombres
5.1.1 Préliminaires et notations
5.1.2 Sélections polynomiales
5.1.3 Collecte des relations
5.1.4 Algèbre linéaire
5.1.5 Logarithme individuel
5.1.6 Complexités asymptotiques
5.1.7 NFS en pratique
5.2 Crible par corps de nombres multiple
5.2.1 Diagramme multi-branches
5.2.2 Crible symétrique
5.2.3 Crible dissymétrique
5.3 Analyses de complexité
5.3.1 MNFS-Conj en moyenne caractéristique
5.3.2 MNFS-Conj dans le cas frontière p = LQ(2/3, cp)
5.3.3 MNFS-JLSV en grande caractéristique
5.4 D’autres petites analyses pour le plaisir
5.4.1 Un crible symétrique obsolète en moyenne caractéristique
5.4.2 MNFS-GJL dans le cas frontière, obsolète
5.4.3 Une phase de descente négligeable
5.5 Un exemple jouet avec un crible symétrique
5.5.1 Sélection polynomiale
5.5.2 Construction de la base de friabilité
5.5.3 Collecte des relations
5.5.4 Construction de la matrice
5.5.5 Algèbre linéaire
5.5.6 Descente
6 Algèbre linéaire presque creuse 
6.1 A propos des matrices creuses
6.1.1 Matrices creuses et cryptographie
6.1.2 Quelques méthodes de résolutions
6.2 Des algorithmes quadratiques pour les matrices creuses
6.2.1 Pré-transformation d’une matrice creuse vers une matrice carrée
6.2.2 L’algorithme de Wiedemann
6.2.3 L’algorithme de Block Wiedemann
6.2.4 Bases minimales
6.3 Un algorithme pour les matrices presque creuses
6.3.1 Entre vacuité et densité
6.3.2 Pré-transformation pour une matrice presque creuse
6.3.3 Conditions sur les blocs V et W
6.3.4 Application de l’algorithme de Giorgi, Jeannerod et Villard
6.3.5 Rôle des blocs V et W et vériÆcation automatique
6.3.6 Quelques exigences concernant les paramètres
6.3.7 Analyse de complexité
6.3.8 Quelle limite de densité pour nos matrices presque creuses ?
6.4 Application en moyenne et grande caractéristiques
6.4.1 Applications de Schirokauer et colonnes lourdes
6.4.2 Un cas d’application optimal
Et demain ?
Bibliographie

Télécharger le rapport complet