Cryptographie basée
sur les courbes
elliptiques
Présenté par : Yasser Labchiri
Sommaire :
Equation de Weierstrass
Loi de groupe
Points d’une courbe elliptique dans un corps fini
Cryptage par les courbes elliptiques
Logarithme discret
Test des fonctions
Equation de Weierstrass:
Dans un corps de caractéristique différentes de 2 et 3 , on définit une
courbe elliptique par l’équation de Weierstrass :
oùdeux constantes de
On appel discriminant d’une courbe elliptique la quantité , pour qu’une courbe
elliptique admette une tangente en tout point, il faut que ce discriminant soit
non nul.
Si ce discriminant est négatif , alors le graphe de la courbe ne possède qu'une
seule composante, le polynôme admet une seule racine correspondant à
l’intersection de la courbe avec l’axe des abscisses (figure 1).
Si ce discriminant est positif , alors le graphe de la courbe possède deux
composantes (figure 2).
On définit un point à l’infini de la manière suivante :
Figure 1 : Courbe Figure 2 : Courbe
d’équation , de d’équation de
discriminant discriminant
Loi de groupe : Géométriquement et
coordonnées
à partir des coordonnées des points dans 𝐾. Cette loi additive
On définira dans cette partie une loi additive sur une courbe elliptique
permettra ensuite de chiffrer des messages. (On traitera ceci dans les
parties suivantes )
Soit une courbe elliptique avec , et soient deux points de la courbe.
Si on trace la droite passant par , alors cette droite est soit tangente à
la courbe , soit elle coupe en un autre point.
point qu’on note 𝑅 , alors la somme
Cas 1 : la droite coupe en un troisième
𝑃+𝑄 est le symétrique de 𝑅 par
rapport à l’axe des abscisses
Si sont les coordonnées de
respectivement , alors la droite passant
par ces deux points est la pente
de la droite , on injecte alors , en
utilisant les formules de Viète on trouve
Cas 2 : la droite est tangente à la courbe
en un point ( on la suppose tangente en P )
Alors la somme P+Q est le point
symétrique de P par rapport à l’axe des
abscisses
Même coordonnées que le Cas 1
Cliquez sur l'icône pour ajouter une image
Si maintenant P≠Q mais avec , on dit alors que la droite (D) coupe la courbe dans
le point à l’infini O , ainsi sont symétrique est aussi le point à l’infini ,et donc la
somme P+Q est égale à O
Si P=Q , alors on considère (D) comme étant la tangente de la courbe
elliptique au point P.
Cas 1 : si , alors (D) est Cas 2 : si , on dérivant , on
verticale car elle est obtient que la pente de la
l’intersection de la courbe avec droite est et , on
l’axe des abscisses , et donc déduit donc que
Conclusion :
Soit deux points de la courbe elliptique de coordonnées
respectives , on déterminera alors les coordonnées de leurs sommes
Soit de coordonnées
Si alors avec
Si alors
Si alors avec
Si , alors
Si alors
Points de la courbe et choix du
corps :
En cryptographie , on utilise les courbes elliptiques sur des corps finis
, en particulier on ce placera sur où est un nombre premier , donc on
fera tous les calculs modulo
En choisissant un corps fini , le nombre de point de la courbe
elliptique est donc fini , on peut donc définir le cardinal de qu’on
notera
Théorème de Hasse : Soit une courbe elliptique , on alors :
Ce théorème est très utile puisqu’en cryptographie on a souvent besoin
d’une estimation du nombre de points d’une courbe elliptique.
Définition :
Soit une courbe elliptique , on dit qu’elle est supersingulière si et
seulement si , de plus si le corps est , alors est supersingulière si et
seulement si
Ses courbes sont utiles car on connait exactement leurs nombres de
points , on donne ici un exemple de courbe supersingulière :
Exemple : Soit un nombre premier tq , alors la courbe est
supersingulière
démonstration : Soit tq , puisque est un groupe d’ordre qui n’est pas
multiple de 3 , donc , donc injective , donc bijective. Donc tout élément
de a exactement une racine cubique , donc en prenons comme étant
l’unique racine cubique de on a points qui appartiennent à la courbe
(car il y’a ), en ajoutant le point à l’infini on déduit que
Cryptographie basée sur les courbes
elliptiques :
Protocole d’échange de clé de Diffie-hellman :
Le but de ce protocole et de permettre l’échange sécurisé d’une clé
privée qui servira ensuite à crypter les messages envoyés. Ce protocole
d’échange et général, mais on l’abordera seulement dans le cas des
courbes elliptiques.
Alice et Bob veulent avoir une clé privée commune pour pouvoir
échanger des messages sans rencontre préalable, alors ils commencent
par choisir les coefficients A et B de la courbe elliptique de manière
publique, ils choisissent aussi un point P de la courbe tq le sous-groupe
généré par P ait un ordre assez grand, et un nombre premier q.
Ensuite, Alice choisit un nombre entier n puis calcule et l’envoie à Bob,
de même Bob choisit un entier m puis calcule et l’envoi à Alice. Par
suite, Alice calcule , et Bob calcule qui constitue leurs clé privée.
mP
Alice P , A , B et q sont connus Bob
nP
Espion
Si un espion a espionné leur échange , il dispose de . Il lui faut donc
déterminer n et m à partir de pour pouvoir connaitre la clé privée , il
s’agit du problème du logarithme discret. La sécurité de ce protocole
réside dans la difficulté de résolution de ce problème dans certains
corps tel où est un grand nombre premier.
Transmission de message d’ElGamal :
Alice et Bob veulent échanger un message M qui est un point de la
courbe, Alice envoie alors à Bob le couple .
Ensuite Bob calcule mnP puis soustrait ce point à , et puisque alors il
retrouve le message .
Si un espion à espionné la transmission du couple, il faut l’entier, et pour
le trouver il est encore confronté au problème du logarithme discret.
Problème du logarithme discret :
Définition :
Dans un groupe cyclique d’ordre n (dont on note une loi additive) , et un
soit b un générateur de . Pour un élément de , alors il existe un entiertq
, le logarithme discret et donc définit de la manière suivante :
Dans certain corps comme le logarithme discret est difficile à calculer ,
c’est-à-dire en se donnant un groupe cyclique d' ordre et de générateur
,et un élément de , il est difficile de trouver le plus petit tq .
Cependant il existe quelques cas particuliers où on peut calculer le
logarithme discret , on s’intéressera à ceux en relation avec les courbes
elliptiques.
Baby step, Giant step :
Soit E une courbe elliptique définie sur et deux points de E tq il
existe
On commence par choisir un entier . Si on ne connait pas #E il suffit
de choisir alors d’après le Théorème de Hasse on a
On calcule
On calcule , jusqu’à que l’un de ces points soit égal à l’un des
Si nous avons avec
Nous allons voir pourquoi cet algorithme marche :
Puisque ,soit la divison euclidienne de par , alors on et , alors pour
et alors on a
D’où la relation voulue.
Cet algorithme n’est efficace que pour des courbes assez petit car il
faut stocker environ données.
Algorithmes utilisé pour le code :
Inversion – Addition – multiplication – les points de la courbe et
leurs nombre – protocole d’échange de clé Diffie-Hellman –
codage d’un point de la courbe – décodage du point de la
courbe – Algorithme Babystep-Giantstep
Dans toute la suite , j’ai utilisé la courbe elliptique définie par :
, avec un nombre premier
Point de la courbe elliptique :
Addition de deux points :
Multiplication :
Protocole d’échange de clé :
Fonction de codage :
Fonction de décodage :
Baby step giant step :
