Université Paris Diderot Paris

Mehdi Tibouchi

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

• Macquarie
• Groupe Olano
• Gaudry
• Taormina
• Fouqué
• Mestre

Informations

• Publié par: profil-feym-2012
• Publié le: 01 septembre 2011
• Nombre de lectures: 70
• Langue: Français
• Poids de l'ouvrage: 12 Mo

Extrait

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é &