Courbes elliptiques sur un anneau et applications cryptographiques

210740 C?????∫ ????⎷?????∫ ∫?? ?\ ?\\??? ?? ?⎷⎷???????\∫ ????? ?????T? ???? ???∫ ???∫??\¬

Submitted on 3 Jul 2009

HALis a multi-disciplinary open access

archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.L"archive ouverte pluridisciplinaireHAL, est destin´ee au d´epˆot et `a la diffusion de documents scientifiques de niveau recherche, publi´es ou non, ´emanant des ´etablissements d"enseignement et de recherche fran¸cais ou ´etrangers, des laboratoires

A ma mère,

à Heïkel,

à Bruno,

à Marc Birebent,

à mon grand-père,

iii

on les appelle les gens de l'ombre et on les remercie à la n du show. En vérité, leur pouvoir est

immense; leur comportement et leurs compétences peuvent rendre les choses tellement plus simples. Merci à Rosalba, Jeanine, Bernard, Jean-Marc, Isabelle, Jean-Louis, Marie-Claude, Jean-Paul, Claudine, Fernande, Marie-France, Valérie, Julien, votre bienveillance soue de l'air frais.

Les chefs d'orchestre eux aussi ont su me soutenir : Michel Miniconi, Frédéric Poupaud, Charles

Walter, Philippe Maisonobe et Michel Merle. Merci d'avoir laissé vos portes ouvertes.

Enn, il y a ceux qui sont dans les bureaux d'à côté, ou de franchement plus loin. Mais à l'ère

de la mondialisation, tous les bureaux sont à côté. La machine à chercher est à la fois gigantesque et microcosmique, et ils sont très nombreux

dans les bureaux d'à côté. Au l des jours, certains d'entre eux vont devenir importants à vos

yeux. Le critère de sélection reste alors l'échange humain. Dans cette catégorie, la vie m'a bien

servie : les locaux, Fabien, Maëlle, Guillaume, Delphine, JP, Pierre, Patrick, Xavier, Nicolas,

Christine, Julianna, Olivier, Frédérique, Marco, Francesca, Magali, Erwann, Joachim, Régine,

Katia, Alain, Daniel, Stéphane, Michel, sans oublier l'équipe du café; et les plus loin Fabien,

Damien, Damien, Inam, René, Carla, Pascal, Mireille, Pierrick, David. Pour nir, il y a ceux qui ne liront probablement jamais ces lignes et qui ont ensoleillé ma vie.

Certains ne savent pas lire, ou pas encore lire; d'autres ne sont plus là pour lire ces lignes; et

une grande majorité d'entre eux n'ont aucune raison de poser leurs yeux sur un tel document, à part pour me faire plaisir l'espace d'une minute.

J'ai commencé à faire la liste de ces personnes, mais elle est bien trop longue. S'ils lisent tout

de même ces lignes, ils se reconnaîtront : ils m'ont accueillie chez eux; nous avons eu beaucoup

de dicultés à nous voir parfois car nos vies sont trop pleines; nous avons partagé du temps,

des expériences, du plaisir, des repas et des apéros, de la déception et des larmes parfois, des

discussions, des embrassades, des sourires; et puis des tours de manivelle, des balles et des foulards, des massues et des ammes, des baudriers, des bleus, des pas et des notes. Nous avons refait le monde et pas que sur le papier. Merci à vous de mettre des couleurs partout... J'avais dit un peu de contenance, alors trêve de remerciements, passons aux choses sérieuses. 5

1.1.1 Courbe elliptique sur un corps . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.2 L'anneauFq[ε]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

7

1.2 Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3 Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.3.1 Modélisation d'un algorithme : machine de Turing . . . . . . . . . . . .

13

1.3.2 Le choix du codage : ensemble eectif . . . . . . . . . . . . . . . . . . .

14

1.3.3 Temps d'exécution : complexité . . . . . . . . . . . . . . . . . . . . . . .

17

1.3.4 Algorithme probabiliste polynomial . . . . . . . . . . . . . . . . . . . . .

20

1.3.5 Les algorithmes pour résoudre un problème calculatoire . . . . . . . . .

22

1.3.6 Les distingueurs pour résoudre un problème décisionnel . . . . . . . . .

29

1.4 Cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

1.4.1 Cryptographie à clef publique . . . . . . . . . . . . . . . . . . . . . . . .

33

1.4.2 Critères de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

1.5 Preuves de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40
43

2.2 Le cas de l'anneau des nombres duaux . . . . . . . . . . . . . . . . . . . . . . .

46

2.2.1 Les applications fondamentales . . . . . . . . . . . . . . . . . . . . . . .

47
48
51

2.2.4 Quandp??????N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

52

2.3 Loi d'addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52
59

3.1.1 Groupe eectif - Cas particuliers . . . . . . . . . . . . . . . . . . . . . .

59

3.1.2 L'algorithme d'exponentiation rapide . . . . . . . . . . . . . . . . . . . .

63
C?????∫ ????⎷?????∫ ∫?? ?\ ?\\??? ?? ?⎷⎷???????\∫ ????? ?????T? ???? ???∫ ???∫??\¬

Submitted on 3 Jul 2009

HALis a multi-disciplinary open access

archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.L"archive ouverte pluridisciplinaireHAL, est destin´ee au d´epˆot et `a la diffusion de documents scientifiques de niveau recherche, publi´es ou non, ´emanant des ´etablissements d"enseignement et de recherche fran¸cais ou ´etrangers, des laboratoires

A ma mère,

à Heïkel,

à Bruno,

à Marc Birebent,

à mon grand-père,

iii

on les appelle les gens de l'ombre et on les remercie à la n du show. En vérité, leur pouvoir est

immense; leur comportement et leurs compétences peuvent rendre les choses tellement plus simples. Merci à Rosalba, Jeanine, Bernard, Jean-Marc, Isabelle, Jean-Louis, Marie-Claude, Jean-Paul, Claudine, Fernande, Marie-France, Valérie, Julien, votre bienveillance soue de l'air frais.

Les chefs d'orchestre eux aussi ont su me soutenir : Michel Miniconi, Frédéric Poupaud, Charles

Walter, Philippe Maisonobe et Michel Merle. Merci d'avoir laissé vos portes ouvertes.

Enn, il y a ceux qui sont dans les bureaux d'à côté, ou de franchement plus loin. Mais à l'ère

de la mondialisation, tous les bureaux sont à côté. La machine à chercher est à la fois gigantesque et microcosmique, et ils sont très nombreux

dans les bureaux d'à côté. Au l des jours, certains d'entre eux vont devenir importants à vos

yeux. Le critère de sélection reste alors l'échange humain. Dans cette catégorie, la vie m'a bien

servie : les locaux, Fabien, Maëlle, Guillaume, Delphine, JP, Pierre, Patrick, Xavier, Nicolas,

Christine, Julianna, Olivier, Frédérique, Marco, Francesca, Magali, Erwann, Joachim, Régine,

Katia, Alain, Daniel, Stéphane, Michel, sans oublier l'équipe du café; et les plus loin Fabien,

Damien, Damien, Inam, René, Carla, Pascal, Mireille, Pierrick, David. Pour nir, il y a ceux qui ne liront probablement jamais ces lignes et qui ont ensoleillé ma vie.

Certains ne savent pas lire, ou pas encore lire; d'autres ne sont plus là pour lire ces lignes; et

une grande majorité d'entre eux n'ont aucune raison de poser leurs yeux sur un tel document, à part pour me faire plaisir l'espace d'une minute.

J'ai commencé à faire la liste de ces personnes, mais elle est bien trop longue. S'ils lisent tout

de même ces lignes, ils se reconnaîtront : ils m'ont accueillie chez eux; nous avons eu beaucoup

de dicultés à nous voir parfois car nos vies sont trop pleines; nous avons partagé du temps,

des expériences, du plaisir, des repas et des apéros, de la déception et des larmes parfois, des

discussions, des embrassades, des sourires; et puis des tours de manivelle, des balles et des foulards, des massues et des ammes, des baudriers, des bleus, des pas et des notes. Nous avons refait le monde et pas que sur le papier. Merci à vous de mettre des couleurs partout... J'avais dit un peu de contenance, alors trêve de remerciements, passons aux choses sérieuses. 5

1.1.1 Courbe elliptique sur un corps . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.2 L'anneauFq[ε]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

7

1.2 Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3 Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.3.1 Modélisation d'un algorithme : machine de Turing . . . . . . . . . . . .

13

1.3.2 Le choix du codage : ensemble eectif . . . . . . . . . . . . . . . . . . .

14

1.3.3 Temps d'exécution : complexité . . . . . . . . . . . . . . . . . . . . . . .

17

1.3.4 Algorithme probabiliste polynomial . . . . . . . . . . . . . . . . . . . . .

20

1.3.5 Les algorithmes pour résoudre un problème calculatoire . . . . . . . . .

22

1.3.6 Les distingueurs pour résoudre un problème décisionnel . . . . . . . . .

29

1.4 Cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

1.4.1 Cryptographie à clef publique . . . . . . . . . . . . . . . . . . . . . . . .

33

1.4.2 Critères de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

1.5 Preuves de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40
43

2.2 Le cas de l'anneau des nombres duaux . . . . . . . . . . . . . . . . . . . . . . .

46

2.2.1 Les applications fondamentales . . . . . . . . . . . . . . . . . . . . . . .

47
48
51

2.2.4 Quandp??????N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

52

2.3 Loi d'addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52
59

3.1.1 Groupe eectif - Cas particuliers . . . . . . . . . . . . . . . . . . . . . .

59

3.1.2 L'algorithme d'exponentiation rapide . . . . . . . . . . . . . . . . . . . .

63