Cryptographie asymétrique et problèmes diciles

Cryptographie asymétrique et problèmes diciles 

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 !

L’avènement de la clef publique

New Directions in Cryptography bouleverse l’année 1976 [DH76]. Petite révolution dans le domaine comme son titre le laisse présager, cet article fondateur de Die et Hellman impulse un changement de paradigme en formalisant la notion de cryptosystème asymétrique, c’est-à-dire de protocole où l’expéditeur et le destinataire n’ont aucune clef commune préalable. Exit alors le souci de sa transmission. Le schéma toujours d’actualité recommande la création non plus d’une clef partagée mais de deux clefs diérentes associées ; l’une d’entre elle n’est pas secrète et peut être distribuée librement, c’est la clef publique, la seconde, privée donc, ne quitte en revanche jamais son propriétaire. Ainsi pour chirer un message il convient d’utiliser la clef publique de son destinataire, tandis que ce dernier se sert uniquement de la clef privée associée, sa clef, pour déchirer. Le cryptosystème RSA [RSA78] dessine l’année suivante une illustration exemplaire du chirement asymétrique. Témoignage de leur importance respective, ces deux résultats ont valu à leurs auteurs l’attribution du prix Turing, en 2002 pour Rivest, Shamir et Adleman, et en 2015 pour Die et Hellman.

A la recherche des problèmes diciles

Les protocoles asymétriques utilisés lorsque l’on souhaite chirer et déchirer des messages, signer un document numérique ou s’authentiÆer auprès de sa banque, sont tous construits à partir d’hypothèses calculatoires réputées diciles. Bien choisir ces hypothèses est plus délicat qu’il n’y parait : il faut disposer d’un problème dicile à résoudre pour un attaquant  alors que le déchirement doit être facile pour un utilisateur légitime muni de la bonne clef. On comprend dès lors la nécessité de disposer d’un cryptosystème pour lequel il est dicile de trouver la bonne clef, alors que par construction il est nécessairement facile de tester si une clef donnée est correcte. Du point de vue de la théorie de la complexité, cette double condition nécessaire explique pourquoi la cryptographie moderne n’a de sens que sous l’hypothèse que les deux classes bien connues NP et P soient distinctes. Rappelons que la classe P correspond aux problèmes résolubles en temps polynomial tandis que la classe NP regroupe ceux pour lesquels une solution, une fois donnée, est vériÆable en temps polynomial. En eet, notre problème est dans NP car il est facile de tester si une clef est correcte, et pour prétendre être dicile, il ne faut pas qu’il soit dans P, aÆn que la bonne clef ne puisse pas aisément être retrouvée. Or, savoir si P et NP sont deux classes égales ou distinctes est une question non résolue. Pire, elle est considérée comme le problème ouvert le plus important du domaine, importance soulignée par son appartenance aux sept problèmes à 1 million de dollars du Clay Millenium Challenge.

Par conséquent, aujourd’hui nous ne savons pas s’il existe de véritables problèmes diciles sur lesquels appuyer les fondements de la cryptographie. Faute de mieux, la communauté choisit de porter son attention sur des questions qui ont été susamment étudiées pour que l’absence de solution soit un bon indice de leur diculté. Pour cette raison, la cryptographie à clef publique, ou cryptographie asymétrique, se base généralement sur des problèmes issus des mathématiques. Comme l’essentiel des calculs se fait par ailleurs sur des ordinateurs qui préfèrent manipuler un monde d’objets discrets plutôt qu’un monde continu, c’est du vaste champ de la théorie des nombres qu’ont été sélectionnés deux candidats incontournables : le problème de la factorisation des entiers et celui du logarithme discret.

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.

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.

D’autres problèmes calculatoires ou de décision liés au problème du logarithme discret ont été introduits au Æl des années comme fondations alternatives pour diérents cryptosystèmes. Néanmoins la comparaison de ces hypothèses variées n’est pas aisée. Aussi, dans une tentative de simpliÆcation du paysage, pour comprendre les liens qui unissent tous ces problèmes et pour faciliter une vue d’ensemble plus claire, Boneh, Boyen et Goh [BBG05] ont proposé l’hypothèse Uber (Uber assumption) qui regroupe l’ensemble de ces variantes. En outre l’hypothèse Uber est prouvée sûre dans le modèle du groupe générique. Le problème du logarithme discret ou DLP (de l’anglais Discrete Logarithm Problem) reste pourtant fondamental en tant que tel. D’un point de vue mathématique il cristallise en eet une question bien plus naturelle que celles soulevées par les problèmes ci-dessus évoqués ; en pratique, aucun de ceux-ci n’a par ailleurs été résolu indépendamment du DLP.

Espion passif VS espion actif 

Toute la description précédente repose sur une hypothèse extrêmement importante quoiqu’implicite : l’attaquant, passif, ne peut qu’écouter les communications qui transitent entre Alice et Bob. Dans le cas d’un espion actif la sécurité s’écroule en revanche. C’est le cas si l’on tente de monter une attaque de l’homme au milieu, c’est-à-dire lorsqu’une tierce personne malveillante feint d’être Bob lorsqu’elle communique avec Alice, et d’être Alice lorsqu’elle communique avec Bob. Plus précisément, elle commencera par échanger dans une phase initiale deux clefs indépendantes, l’une avec Alice, l’autre avec Bob. Elle transmettra ensuite tous les messages reçus à leur destinataire légitime après les avoir chirés de nouveau avec la clef de celui-ci. Cette manière de procéder lui permet alors de déchirer la totalité des communications ayant cours, sans être détectée. Un point crucial lors de la conception de cryptosystèmes basés sur les logarithmes discrets consiste donc à réØéchir à la mise en place de mesures de sécurité allant à l’encontre de telles incursions.

OÙ TROUVE-T-ON DES LOGARITHMES DISCRETS ?

Cryptosystèmes basés sur les couplages

Les années 80 soulèvent progressivement une question naturelle, suite à l’échange de clef de Die-Hellman : existe-t-il un protocole de création de clef, en un tour seulement, qui permettrait d’accorder trois entités distinctes, et non plus deux, tout en résistant aux écoutes d’une personne extérieure ? C’est l’introduction en 2000 par Joux [Jou04] d’une méthode simple basée sur les couplages bilinéaires qui permet de répondre pour la première fois par l’armative à cette question ouverte. En eet, la création d’une clef commune entre plus de deux entités nécessitait jusqu’ici au moins deux tours d’interactions entre les participants ; le protocole de Burmester-Desmedt [BD94] illustre ainsi une solution classique employée à l’époque pour un nombre arbitrairement grand d’utilisateurs.

Hypothèses de diculté 

Nous avons vu que la sécurité des protocoles basés sur l’idée de Die et Hellman reposait le plus souvent sur la diculté des problèmes CDH et DDH. De manière analogue, la sécurité des protocoles qui s’appuient sur les couplages dépendent de la diculté à calculer e(P,P) abc étant donnés P, aP, bP et cP. Ce problème est répertorié sous le nom de problème de DieHellman bilinéaire calculatoire ou CBDH (de l’anglais Computational Bilinear Die-Hellman problem) aussi parfois simplement BDH, qui existe aussi sous sa forme décisionnelle. On parle alors du problème DBDH.

Réduction du DLP dans G1 au DLP dans G2 

Une conséquence directe de l’existence de ce couplage bilinéaire réside par ailleurs dans la réduction ecace du problème du logarithme discret dans G1 au problème du logarithme discret dans G2. En eet, supposons que Q soit un élément de G1 tel que Q = xP, alors nous obtenons l’égalité e(P,Q) = e(P,xP) = e(P,P) x. Ainsi, calculer le logarithme de e(P,Q) dans G2 nous permet de retrouver la valeur de l’entier x. Cette réduction a été décrite pour la première fois par Menezes, Okamoto, et Vanstone [MOV93] pour démontrer que les courbes elliptiques supersingulières étaient bien plus faibles que leurs homologues aléatoires, puisque le problème du logarithme discret peut être transféré d’une courbe supersingulière vers un corps Æni relativement petit à l’aide d’un couplage.

A la suite du protocole tri-parties et de la publication du résultat de Menezes, Okamoto, et Vanstone, la communauté cryptographique s’est intéressée de plus près à diverses applications de ces mêmes couplages. A ce sujet, deux protocoles remarquables se distinguent : le schéma de chirement basé sur l’identité (IBE comme identity-based encryption scheme en anglais) de Boneh et Franklin [BF03] et celui de signature courte de Boneh, Lynn et Shacham [BLS04]. Dès lors, une recherche accrue s’est manifestée aussi bien pour le design et l’implémentation que pour l’analyse des protocoles cryptographiques reposant sur des couplages bilinéaires, dont l’ensemble de départ  n’est autre qu’un sous-groupe d’une courbe elliptique. Notons qu’une part non négligeable des travaux actuels se préoccupe aussi des couplages bilinéaires de variétés abéliennes plus générales, comme les courbes hyperelliptiques. En pratique, la plupart de ces protocoles utilisent un corps Æni comme ensemble d’arrivée du couplage sous-jacent, ce qui présente donc un cas concret aecté par la résolution du problème étudié dans cette thèse.

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
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 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.2.3 Analyse de complexité
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Æé 99
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
Conclusion

Télécharger le rapport complet