Université Paris Diderot Paris

-

Documents
279 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur, Doctorat, Bac+8
Université Paris Diderot (Paris 7) Université du Luxembourg Thèse de doctorat Hachage vers les courbes elliptiques et cryptanalyse de schémas RSA. Spécialité : informatique présentée et soutenue publiquement le 23 septembre 2011 par Mehdi Tibouchi pour obtenir le grade de Docteur de l'Université Paris Diderot et de l'Université du Luxembourg devant le jury composé de Directeurs de thèse : Jean-Sébastien Coron (Université du Luxembourg, Luxembourg) David Naccache (Université Paris II & ENS, France) Rapporteurs : Pierrick Gaudry (CNRS & LORIA, France) Igor Shparlinski (Macquarie University, Australie) Examinateurs : Pierre-Alain Fouque (ENS, France) Jean-François Mestre (Université Paris 7, France) Tatsuaki Okamoto (NTT, Japon) Jacques Stern (ENS, France)

  • chercheurs de l'équipe

  • thèse de doctorat

  • sasaki-san

  • côté tête

  • équipe de cryptologie de l'ens

  • discussion scientifique

  • ronnement scientifique idéal


Sujets

Informations

Publié par
Publié le 01 septembre 2011
Nombre de visites sur la page 94
Langue Français
Signaler un problème

Université Paris Université du
Diderot Luxembourg
(Paris 7)
Thèse de doctorat
Hachage vers les courbes elliptiques
et cryptanalyse de schémas RSA.
Spécialité : informatique
présentée et soutenue publiquement le 23 septembre 2011 par
Mehdi Tibouchi
pour obtenir le grade de
Docteur de l’Université Paris Diderot et de l’Université du Luxembourg
devant le jury composé de
Directeurs de thèse : Jean-Sébastien Coron (Université du Luxembourg, Luxembourg)
David Naccacheersité Paris II & ENS, France)
Rapporteurs : Pierrick Gaudry (CNRS & LORIA, France)
Igor Shparlinski (Macquarie University, Australie)
Examinateurs : Pierre-Alain Fouque (ENS, France)
Jean-François Mestre (Université Paris 7, France)
Tatsuaki Okamoto (NTT, Japon)
Jacques Stern (ENS, France)Remerciements
Merci tout d’abord à Pierrick et Igor qui ont accepté la lourde tâche de relire ce
manuscrit, et à tous les membres du jury, qui ont bien voulu se libérer à cet horaire
inhabituel, et qui pour certains viennent de fort loin!
Merci encore à mes directeurs de thèse, David et Jean-Sébastien, qui m’ont accueilli
alors que j’étais un matheux naïf et non sans préjugés, et m’ont fait découvrir combien la
cryptographie est un domaine vaste, où l’on trouve des questions passionnantes aussi bien
théoriques que très proches des applications. Merci aussi pour nos réunions de recherches
itinérantes et toujours intéressantes, et pour leur soutien dans toutes sortes de projets,
scientifiques ou non.
Merci également à l’équipe de cryptologie de l’ENS, qui offre aussi bien un envi-
ronnement scientifique idéal où l’on jouit d’une grande liberté que la possibilité d’aller
découvrir le monde. Merci notamment à Damien, Pierre-Alain, Phong, Michel et Vadim,
tant pour nos discussions autour d’un tableau noir que pour celles, pas moins impor-
tantes, autour d’une pizza à Taormina ou des fraises au chocolat de CRYPTO. Merci à
tous les chercheurs de l’équipe, permanents, post-docs, doctorants ou plus jeunes, pour
l’ambiance toujours agréable au labo, et aux administratifs pour faire en sorte que tout
cela fonctionne (pensée particulière pour Joëlle, Valérie et Michelle, pour avoir supporté
mon côté tête-en-l’air).
Merci aussi aux collègues qui m’ont accueilli à Ingenico au début de cette thèse, en
particulier Éric, avec qui discuter de mathématiques est toujours un plaisir, et Thomas,
avec qui j’espère avoir encore l’occasion de prendre un verre sur Orchard Road ou à
Shibuya.
Merci aux collègues de NTT, auprès de qui j’ai passé six excellents mois de stage
et que j’aurai plaisir à rejoindre par la suite. Merci à Okamoto-san pour son accueil si
aimable, à Uchida-san pour sa prévenance et les discussions en français que nous avions
sur le Japon (ou inversement), à Yamamoto-san, Abe-san, Fujioka-san et bien d’autres
pour des discussions scientifiques toujours intéressantes, à Nishimaki-san et Sasaki-san
pour leur aide à la résidence de Sayamagaoka, et à Berkant et Daegun avec qui j’ai pu
partager l’expérience de la vie d’étranger au Japon.
Au cours de cette thèse, j’ai eu l’occasion de collaborer avec de nombreux co-auteurs.
Merci à tous : ce travail est le vôtre autant que le mien.
Merci à tous ceux qui ont permis que j’aie de quoi vivre pendant cette thèse : David
N., David P. et Damien, qui se sont démenés pour cela, Ingenico, NTT, l’ENS et le
iRemerciements
projet ANR PACE, ainsi que le projet européen ECRYPT II et le ministère des Affaires
étrangères qui ont pris en charge certains de mes déplacements. Merci aussi à ceux
qui m’ont encouragé à entreprendre cette thèse ou m’ont soutenu au travers de débuts
administrativement délicats : David et Damien, Philippe Clarisse et les collègues de
Saint-Louis, Johan Yebbou, Louis Vogel et Chantal Ladoux, David Madore, Yazid Sabeg
et d’autres sans doute qui sont intervenus sans que j’en aie eu connaissance.
Et parce qu’il y a une vie en dehors du labo, merci enfin à ceux qui m’ont supporté
au quotidien pendant ces trois ans : mes parents bien sûr (et ça n’a pas dû être facile!);
Chantal Ladoux; Viêt-Linh, JB et Jean-Rémy; yaforum; et mes compagnons de virées
du côté de la rue de la Michodière ou de Higashi-Ikebukuro.
ii/K >’ &P J D?I
??¿Sommaire
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Présentation des travaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
I Contributions à la cryptographie par courbes elliptiques 31
3 Hachage en temps constant vers les courbes (hyper)elliptiques . . . . . . . 37
4 Estimation de la taille de l’image des encodages en temps constant . . . . 63
5 Hachage indifférentiable vers les courbes elliptiques . . . . . . . . . . . . . 75
6 Encodages bien distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7 Hachage et encodage vers les courbes hyperelliptiques impaires . . . . . . . 115
8 Le modèle de Huff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
II Cryptanalyse de schémas fondés sur RSA 141
9 Cryptanalyse pratique des signatures ISO/IEC 9796-2 et EMV . . . . . . . 149
10 Attaques par fautes sur les EMV . . . . . . . . . . . . . . . . . 175
11 A par fautes sur le module contre les signatures RSA . . . . . . . . 191
12 Sur la sécurité du chiffrement PKCS#1 v1.5 . . . . . . . . . . . . . . . . . 209
13 Cryptanalyse de l’hypothèse RSA dans un sous-groupe . . . . . . . . . . . 229
Table des matières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Liste des figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Liste des tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
Liste des algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
vChapitre 1
Introduction
1.1 Introduction à la cryptologie
L’usage de codes secrets, principalement dans les communications diplomatiques et mili-
taires, remonte à l’Antiquité (on en trouve déjà des traces dans l’Égypte du moyen empire,
puis en Grèce antique), où il était encore artisanal. Peu à peu, une compétition s’installe
entre les utilisateurs de codes secrets et ceux qui tentent de les percer : à partir du Moyen-
Âge, plusieurs traités sont ainsi écrits sur des techniques permettant de casser les codes
secrets (notamment l’analyse de fréquence à l’encontre des chiffrements par substitution
simple). L’étude des messages secrets se constitue progressivement comme une science, la
cryptologie, rassemblant ces deux aspects apparemment antagonistes : la cryptographie
d’une part, visant à élaborer des méthodes pour sécuriser les communications, et la
cryptanalyse d’autre part, visant à déceler des faiblesses dans ces méthodes.
Depuis quelques décennies, l’essor des télécommunications et le développement et la
miniaturisation des moyens de calcul ont permis à la cryptographie de dépasser le champ
militaire et d’investir notre vie quotidienne : des dispositifs aussi variés qu’un téléphone
mobile, une carte bancaire, un passeport biométrique et un navigateur web effectuent
des calculs cryptographiques, afin de garantir diverses propriétés de sécurité de leurs
communications.
Parmi les propriétés de sécurité auxquelles s’intéresse la cryptologie, on peut citer
l’intégrité des messages (lorsque l’on veut s’assurer qu’ils n’ont pas été altérés sur le
canal de transmission : par exemple quand on télécharge un fichier), leur authenticité
(lorsque l’on veut s’assurer que l’expéditeur est bien celui qu’il prétend : par exemple
qu’une transaction bancaire est bien réalisée par une carte de paiement autorisée) ou
encore leur confidentialité (lorsque l’on veut les garder secrets en dépit des personnes
pouvant espionner la communication : par exemple lorsque l’on consulte son courrier
électronique à distance). Le cryptographe propose des algorithmes à exécuter par les
différentes parties pour satisfaire ces propriétés de sécurité, et le cryptanalyste y cherche
des faiblesses.
Si par le passé il a pu être courant de chercher à dissimuler ou garder secret les
11. Introduction
algorithmes cryptographiques afin de compliquer la tâche du cryptanalyste, on reconnaît
désormais que ce genre de secret, qu’il faut nécessairement partager avec ses correspon-
dants, est peu robuste, et que l’impression de « sécurité par l’obscurité » est largement
illusoire. Selon le principe énoncé par Kerckhoffs en 1883, il convient qu’un système
cryptographique utilise des algorithme publics, qui n’utilisent eux-mêmes qu’une petite
quantité d’information gardée secrète : la clef. Si la clef est compromise, elle peut être
remplacée sans avoir à concevoir tout un nouveau système. De plus, cela permet à l’algo-
rithme d’être évalué publiquement : si un algorithme cryptographique public a résisté
longtemps aux tentatives d’attaques des cryptanalystes, on a davantage confiance en sa
sécurité qu’en celle d’un algorithme secret qu’aucun analyste n’a eu l’occasion d’étudier.
1.2 Cryptographie moderne
1.2.1 Clef symétrique et clef publique
Jusque dans les années 1970, il était entendu que la clef cryptographique était un secret
partagé entre l’expéditeur et le destinataire : les systèmes cryptographiques étaient alors
toujours symétriques, au sens où la même clef servait au deux parties.
Pour assurer la confidentialité, par exemple, on utilisait des systèmes de chiffrement
symétriques par blocs; un tel système est la donné deux algorithmes, E et D , quik k
constituent des familles de permutations inverses l’une de l’autre des chaînes de bits
d’une certaine longueur fixée (par exemple 64 ou 128 bits), indicées par la clef symétrique
k. L’expéditeur, Alice, désirant faire parvenir à Bob, avec qui elle partage une clef secrète
k, un certain message m d’une façon qui préserve la confidentialité, envoie alors le chiffré
(ou cryptogramme) c = E (m), et Bob, à la réception, retrouve m en déchiffrant c :k
m =D (c).k
Pourvu que les algorithmes E et D aient de bonnes propriétés de sécurité, cettek k
approche fonctionne très bien et est encore d’un usage courant aujourd’hui. Cependant,
elle présente certains défauts, notamment du point de vue de la distribution de clef.
Pour limiter l’impact de la compromission d’une clef, il est important que, dans une
organisation où les individus s’échangent des messages chiffrés, chaque personne utilise
une clef différente pour communiquer avec n’importe quelle autre. En cryptographie
symétrique, cela impose d’utiliser une clef différente pour chaque paire d’individus : dans
une organisation comptant plusieurs milliers de personnes, le nombre de clef à maintenir
se compte en millions, et devient donc rapidement ingérable.
D’autre part, il y a des primitives de sécurité intéressantes qui ne sont pas réalisables
encryptographie symétrique. Par exemple,deux personnes partageant uneclef communek
peuvent s’assurer mutuellement de l’authenticité des messages qu’elle s’échangent (on peut
pour cela utiliser la primitive cryptographique appelée code d’authentification de message,
ou MAC). En revanche, elles ne peuvent pas convaincre un tiers de cette authenticité,
puisque lui-même ne dispose pas du secret k. On ne peut donc pas espérer apposer
une signature publiquement vérifiable sur un message en utilisant de la cryptographie
symétrique.
2