y y
x x
(a) y 2 = x 3 − x (b) y 2 = x 3 − 2x + 2
Figure 2.2 – Courbes elliptiques sur R
Nous obtenons alors la version courte de l’équation 2.5 de Weierstrass après une division
par : E : y2 + xy = x3 + b2x2 + b6 (2.8)
Le cas de la caractéristique 3 ne sera pas détaillé dans cette thèse, mais le lecteur pourra
se référer aux livres [CFA+06, Sil09].
Nous pouvons alors définir les équations de Weierstrass courtes pour une courbe
elliptique e sur un corps K.
Définition 2.15 (Courbes elliptiques (Weierstrass courte)). L’équation courte de
Weierstrass d’une courbe elliptique E sur K est donnée par :
{
2 3
E : y =x + ax +b si car ( K ) ≠ 2 ,3
2 3 2
E : y + xy=x + a x + b si car ( K )=2
Où a,b sont des éléments de K
La Figure 2.2 représente deux exemples de courbes elliptiques définies sur R tandis que
la Figure 2.3 représente une courbe elliptique sur F 31. A ces deux représentations nous
devons ajouter le point à l’infini qui ne peut pas être représenté sur ces figures. Notons
que la grande différence entre une courbe elliptique sur R et sur F p est son nombre de
points. En effet, dans le premier cas, celui-ci est infini alors que dans le deuxième cas, il
est fini et borné par le théorème 2.20 de Hasse comme nous le verrons. Le cardinal d’une
courbe elliptique quant à lui joue un rôle primordial dans le cadre d’une application
cryptographique.
Pour une courbe elliptique E sur K, il est possible de lui lier une autre courbe Etw de telle
sorte que E et Etw sont isomorphes sur la clôture algébrique de K. Cette courbe Etw est
appelée tordue de E. La tordue d’une courbe elliptique E va contribuer à la sécurité du
protocole cryptographique utilisé. Ce point sera abordé dans la section 4.2.
Nous décrivons ci-après deux invariants nécessaires pour l’étude des courbes elliptiques.
y
Figure 2.3 – Courbe elliptique définie sur F31 avec E : y2 = x3 + x + 3 et |E| = 41
Définition 2.16 (Discriminant). Le discriminant d’une courbe elliptique E sur un corps
K est défini par :
{△ =−16 ( 4 a 34 +27 a 26) si car ( K ) ≠2 , 3
△=a6 si car ( K )=2
Définition 2.17 (j-invariant). Le j-invariant d’une courbe elliptique E définie sur un
corps K est :
{
3
1728 a 4
j= sicar ( K ) ≠ 2 ,3
△
1
j= si car ( K )=2
a6
De plus, la condition de la définition 2.14 sur les dérivées partielles d’une courbe
elliptique est équivalente à la condition que ∆ ≠ 0.
Loi de composition
Dans le but d’utiliser les courbes elliptiques dans des applications cryptographiques, on
définit une loi de composition interne entre les points de la courbe elliptique de telle sorte
à construire un groupe. Cette structure de groupe sur l’ensemble des points d’une courbe
elliptique permettra de construire des protocoles de signatures ou d´échange de clefs.
La loi de composition interne sur une courbe elliptique sera notée additivement car,
comme nous le verrons, celle-ci est abélienne. Ainsi, pour obtenir un groupe (E,+), la loi
de composition + doit vérifier les conditions rappelées dans la section
2.1, à savoir dans ce cas :
1. Associativité : ∀P,Q,R ∈ E : (P + Q) + R = P + (Q + R)
2. Elément neutre : ∃!O ∈ E : ∀P ∈ E,P + O = O + P
3. Inverse : ∀P in E,∃!Q ∈ E : P + Q = Q + P = O
4. Commutativité : ∀P,Q ∈ E : P + Q = Q + P
La construction d’une telle loi de compositions permettant de définir un groupe abélien
sur la courbe elliptique E qui peut être abordée de différentes manières. La première
approche est géométrique.
y y
P
Q
x x
(P + Q ) P
2P
(a) Calcul de P + Q (b) Calcul de 2P
Figure 2.4 – Loi de groupe d’une courbe elliptique sur R
La Figure 2.4 présente la loi de composition considérée pour construire un groupe sur
l’ensemble des points de la courbe E, on définit comme élément neutre le point à l’infini
O.
La seconde approche quant à elle est algébrique, elle nous permettra de vérifier que la loi
de groupe définie géométriquement par la figure 2.4 possède bien les propriétés relatives
aux lois de composition de groupes abéliens. Pour cela, il nous faut décrire
algébriquement cette loi de composition. Pour P = (x1,y1), Q(x2,y2) deux points distants de
la courbe E. Nous définissons P +Q = (x3,y3) de la manière suivante :
x3 = λ2 − a − x1 − x2, y3 = λ(x1 − x3) − y1 − x3
λ est définie différemment si P = Q ou si P ≠ Q.
{
y 1− y 2
λ= si P ≠ ±Q
x 1−x 2
3 x 21+ 2 a x 1− y1
λ= si P=Q
2 y1 + x 1
Dans le cas particulier, où P = −Q, la droite passant par P et Q est parallèle à l’axe des
ordonnées, nous avons dans ce cas y1 = −y2 et donc P + Q = O .
Nous avons vu précédemment que pour additionner deux points, il existe plusieurs cas
selon que P = Q, P = −Q ou P = O . Ainsi, cette loi de groupe admet de ce fait différentes
formules pour additionner et doubler des points sur E. Le point à l’infini O est un cas
particulier à traiter à part. Deux notions essentielles permettent alors de qualifier une loi
de composition sur E.
Définition 2.18 (Loi de groupe uniforme). Une loi de groupe sur une courbe elliptique
E est dite uniforme si les formules d’additions et de doublement sont identiques.
Définition 2.19 (Loi de groupe complète). Une loi de groupe sur une courbe elliptique
E est dite complète si les formules d’additions et de doublement sont valides pour tout
point de E.
Ces deux définitions nous serons utiles dans la suite de cette étude afin de qualifier les
lois de groupes de modèles alternatifs de courbes elliptiques.
Cardinal d’une courbe elliptique
Dans le cas où une courbe elliptique E est définie sur un corps fini, nous avons vu que le
cardinal de E est fini. Un moyen d’obtenir ce cardinal est de chercher, de façon
exhaustive, tous les points de E. Pour les courbes définies sur un corps fini de grand ordre
cette méthode n’est pas envisageable car elle nécessiterait un temps de calcul
considérable.
L’endomorphisme de Frobenius joue un rôle important pour compter le nombre de points
d’une courbe elliptique sur un corps fini. Il est défini pour tout point P = (x,y) de E sur le
corps F p par :
d
{
Ψ ( P )= ( x , y ) si P ≠ O
p4 p4
O si P=O
De cette définition du Frobenius en découle le théorème suivant :
Théorème 2.20 (Hasse-Weil). Soit une courbe elliptique E définie sur F p , alors :
d
|E| = pd + 1 − t et |t| ≤ 2√ p d
Où t est la trace de l’endomorphisme de Frobenius.
Par conséquent, la difficulté de compter les points d’une courbe elliptique sur un corps
fini revient à calculer la trace de l’endomorphisme de Frobenius. Il existe de nombreuses
méthodes pour calculer celle-ci qui dépendent de la caractéristique du corps sur lequel est
défini la courbe E. Des exemples sont donnés dans le chapitre 17 de [CFA +06] qui
présente plusieurs techniques dont l’algorithme de Schoof-Elkies Atkin (SEA) [Sch85,
Atk88, elk91]. Dans le cas de la caractéristique 2, la méthode de la moyenne arithmético-
géométrique (AGM) [Mes00b, Mes00a] sur les nombres p-adic est une approche
habituellement utilisée pour compter le nombre de points d’une courbe elliptique. Pour
les détails de cet algorithme et de l’arithmétique des nombres p-adic nous renvoyons le
lecteur à la section 17.3.2 du livre [CFA+06].
L’algorithme 2.4 résume les différentes étapes de la méthode AGM pour compter le
nombre de points d’une courbe elliptique E sur un corps fini de caractéristique 2.
Il existe un résultat intéressant qui lie le cardinal d’une courbe elliptique et celui de sa
tordue Etw.
Proposition 2.21. Soit E une courbe elliptique sur Fpd et Etw une tordue de E, alors :
|E| + |Etw| = 2pd + 2
Cette proposition aura un impact important dans la génération d’un nouvel ensemble de
courbes elliptiques comme nous le verrons dans le chapitre 4. Afin de choisir une courbe
elliptique destinée à des applications cryptographiques, nous devons vérifier la friabilité
de son cardinal et celui de sa tordue. Ainsi, nous avons un seul calcul de cardinal à
effectuer grâce à la propriété 2.21 ce qui nous permettra d’accélérer grandement la
génération de nouvelles courbes elliptiques sécurisées pour la cryptographie.
Algorithme 2.4 Méthode AGM pour compter le nombre de point d’une courbe elliptique
sur F2d.
Entrées Un courbe elliptique E : y2 + xy = x3 + b sur F2d
Sorties: Le nombre de points de E sur F2d
Pour i = 5 à N Faire
a+b i
a← mod 2
2
b ← √ ab mod 2
i
Fin Pour
a+b N
a0← mod 2
2
a N−1
t ← mod 2
a0
Si t > 2d+2 alors
2
t ← t − 2 N−1
Fin Si
Retourner 2d + 1 − t
2.3.2 Arithmétique des courbes elliptiques
L’implémentation cryptographique basée sur les courbes elliptiques dépend de
l’arithmétique de ces dernières et impacte sur l’efficacité du protocole cryptographique.
De façon plus détaillée, les calculs effectués sur une courbe elliptique sont basés sur
l’arithmétique des corps finis. Nous avons vu dans la section 2.2 les algorithmes
composant une arithmétique en caractéristique 2. Dans cette section, nous présenterons
les différentes opérations clefs du calcul sur une courbe elliptique que nous devons
considérer pour des applications cryptographiques.
Dans un protocole d’échange de clefs tel que l’ECDH [BCR +03] ou dans un protocole de
signature tel que l’ECDSA [Gal13], l’opération principale effectuée sur une courbe
elliptique est la multiplication scalaire. Cette opération consiste à calculer :
Où k est un entier et P un point de E.
L’arithmétique des courbes elliptiques se décompose alors en une suite d’opérations
élémentaires dans Fpd et dans la suite nous traiterons seulement le cas où p = 2.
Nous avons vu dans la section 2.2 qu’il existe une hiérarchie en termes de performance
dans les opérations sur F2d. En effet, l’inversion est l’opération la plus coûteuse, car elle
nécessite plusieurs multiplications pour être effectuée. La multiplication est aussi très
onéreuse en temps de calcul. En comparaison, l’addition et l’élévation au carré sont très
peu coûteuses même si pour le cas de l’élévation au carré, nous devons effectuer une
réduction sur le résultat obtenu. Afin de mesurer les performances des différentes
implémentations de courbes elliptiques nous les comparerons entre elles en termes
d’opérations élémentaires sur F2d. Nous utiliserons comme métrique1 qu’une inversion (I)
équivaut à 10 multiplications et que l’élévation au carré (S) et l’addition (A) sont
négligeables. Ainsi, toutes les mesures seront données en fonction de nombre de
multiplications nécessaires. Dans certains cas, nous serons malgré tout amenés à
comparer le nombre d’élévations au carré afin de départager deux systèmes de
coordonnées ayant le même coût en multiplications.
Systèmes de coordonnées
L’opération fondamentale sur une courbe elliptique E est l’addition de deux points P et
Q. Cette opération va grandement dépendre du système de coordonnées considérées pour
représenter un point sur E.
Le premier système de coordonnées que nous avons vu précédemment est la
représentation affine des points d’une courbe de Weierstrass. En analysant les formules
1 . https : //hyperelliptic.org/EFD/g12o/index.html
d’addition et de doublement de ce système de coordonnées nous obtenons que 12
multiplications sont n´nécessaires pour une addition (1I + 2M + 1S) qu’un doublement.
Dans ces conditions, les performances des coordonnées affines obtenues, sont
incompatibles pour des applications cryptographiques, dues à l’opération d’inversion qui
est très coûteuse. Ainsi, un moyen d’améliorer les performances de l’addition et du
doublement est de ne pas calculer cette inversion et de l’accumuler dans une troisième
coordonnée Z qui sera inversée à la toute fin du calcul de kP. Ce système de coordonnées
est dit projectif et représente un point P par trois coordonnées (X : Y : Z), il peut être
converti vers les coordonnées affines en appliquant la transformation suivante :
Dans ce système projectif un point P peut avoir plusieurs représentations qui
correspondent à une seule et unique représentation affine : un point P = (X : Y : Z) est
égale à un point P 0 = (λX : λY : λZ). Nous verrons qu’une telle propriété a son importance
dans la protection des protocoles cryptographiques sur courbes elliptiques face aux
attaques par canaux auxiliaires.
Finalement, l’adoption d’une telle représentation des points permet d’accélérer le
doublement, mais ralentit l’addition. L’addition dans ce cas nécessitera 14 multiplications
(14 M + 1 S) et le doublement 7 (7M + 1S). Malgré tout ce système accélère le calcul de
la multiplication scalaire, car cette opération utilise essentiellement des doublements. Les
détails des formules d’addition et de doublement sont donnés à la section 13.3.1 du livre
[CFA+06].
Il existe de nombreuses autres méthodes de représentation des points qui permettent
d’accélérer d’avantage les calculs. Nous pouvons citer les coordonnées jacobéennes ou
les coordonnées de Lopez-Dahab. Nous nous attarderons sur un système particulier celui
des coordonnées différentielles qui consiste à représenter un point uniquement par sa
coordonnée affine x. Cette forme particulière de représentation du point utilisée avec des
méthodes de calculs de kP spécifiques permet d’augmenter les performances [Sta02a]. Le
doublement ne nécessite qu’une multiplication (1M + 3S) et l’addition 5 (5M + 3S). Les
auteurs de [FLRV08a] montrent qu’un tel choix de représentation des coordonnées peut
être un vecteur d’attaque par fautes.
In fine, le tableau 2.1 compare le coût en multiplications des différents systèmes de
coordonnées sur les courbes de Weierstrass d´définie sur F2d.
Doublement Addition
Affines 12M 12 M
Projectives 7M 14 M
Jacobiennes 4M 14 M
Lopez-Dahab 3M 13 M
Différentielles 1M 5M
Table 2.1 – Coût en multiplications de l’addition et du doublement de points dans
différents systèmes de coordonnées sur les courbes de Weierstrass.
Multiplication scalaire
De l’addition de deux points sur une courbe elliptique, nous pouvons construire
l’opération de multiplication scalaire d’un point qui est essentielle pour la construction
des protocoles cryptographiques sur les courbes elliptiques. Cette dernière consiste à
effectuer le calcul kP. Les algorithmes de multiplications scalaires vont être ressemblant
de ceux de l’exponentiation, seule l’opération de base change : pour la multiplication
scalaire, on aura une addition de points sur les courbes elliptiques tandis que pour
l’exponentiation, on aura une multiplication entre des éléments d’un groupe multiplicatif.
Le premier algorithme de multiplication scalaire est celui de « double and add »,
algorithme 2.5.
Algorithme 2.5 Algorithme double and add de multiplication scalaire d’un point P sur
une courbe elliptique E
Entrées k un scalaire, P un point de E
Sorties: kP
Q←O
n = log2(k)
Pour i = n − 1 à 0 Faire
Q ← 2Q
Si ki = 1 alors
Q←Q+P
Fin Si
Fin Pour
Retourner Q = kP
Cependant, cet algorithme possède deux inconvénients majeurs.
Le premier est qu’il est très peu performant, la multiplication scalaire est effectuée en
traitant le scalaire k bit à bit. Une amélioration consiste à utiliser un algorithme à fenêtre
glissante qui permettra de parcourir plus rapidement le scalaire k en contrepartie de
quelques pré-calculs qui dépendent de la taille de la fenêtre (Algorithme 2.6). Il existe
des variantes à cet algorithme à pré-calculs tel que l’algorithme w-NAF qui va parcourir
différemment le scalaire k. Bien que ces algorithmes améliorent les performances, ils ne
résolvent pas le problème lié à la non-uniformité des segments des calculs qui dépend
de la valeur de la clef.
Le second est relatif aux opérations effectuées à chaque étape qui dépendent directement
du scalaire k. Si k est une clef privée alors cette différence d’exécution
Algorithme 2.6 Algorithme à fenêtre glissante de multiplication scalaire d’un point
P sur une courbe elliptique E
Entrées k un scalaire, P un point de E, t une taille de fenêtre
Sorties: kP
T un tableau de 2t−1 points.
Pour i = 0 à 2t−1 Faire
T[i] ← iP
Fin Pour
Q ←O
n = log2(k)
Pour i = n − 1 à 0 Faire
Si ki = 0 alors
Q ← 2Q
Sinon
Si i >= t alors
w ← extraire les t prochains bits de k
Pour j = 0 à t Faire
Q ← 2Q
Fin Pour
Q ← Q + T[w]
Sinon
Appliquer l’algorithme 2.5 sur les bits de k restant
Fin Si
Fin Si
Fin Pour
Retourner Q = kP
Pourra être exploitée au travers d’attaques par canaux auxiliaires afin d’extraire de
l’information sur la clef. Par exemple, si le bit courant est un 1 alors une opération
supplémentaire d’addition de point est réalisée, ce qui va modifier la trace de la
consommation de courant ou du rayonnement électromagnétique acquise à l’issue du
calcul. Nous verrons plus en détails cet aspect de la cryptographie sur les courbes
elliptiques dans le chapitre 3. Une première possibilité pour unifier l’algorithme 2.5, de
manière à avoir les mêmes opérations pour un bit 0 ou 1, est d’effectuer une addition
fictive lorsque le bit courant est 0. Nous obtenons alors l’algorithme de double and add
always (Algorithme 2.7). Le problème de cette approche est qu’elle impacte le problème
de performance de l’algorithme 2.5. De plus, la protection apportée est d’une utilité
limitée car dans ce cas l’algorithme 2.7 est sensible aux attaques par fautes mais aussi aux
attaques par canaux auxiliaires qui permettent de distinguer les accès au point T. Si une
faute est effectuée durant l’addition fictive un attaquant peut alors inférer que le bit
courant est nul, car le résultat final n’aura pas été modifié.
Algorithme 2.7 Algorithme double and add always de multiplication scalaire d’un point
P sur une courbe elliptique E
Entrées k un scalaire, P un point de E
Sorties: kP
Q←O
n = log2(k)
Pour i = n − 1 à 0 Faire
Si ki = 1 alors
Q ← 2Q
Q←Q+P
Sinon
Q ← 2Q
T←Q+P
Fin Si
Fin Pour
Retourner Q = kP
Ainsi, nous devons considérer un algorithme de multiplication scalaire sur les courbes
elliptiques qui devra être efficace et effectuant les mêmes opérations quel que soit l’état
du bit courant. L’algorithme de l’Echelle´ de Montgomery [ JY02], algorithme 2.8, est
une méthode de multiplication scalaire qui va effectuer les mêmes opérations
indépendamment de la valeur de la clef traitée. Contenu des critères de performance et de
sécurité, notre choix s’est porte sur cet algorithme pour la suite de nos travaux.
2.3.3 Les modèles alternatifs de Courbes Elliptiques
Comme nous l’avons vu précédemment, le modèle de Weierstrass de courbes elliptiques,
tel que présente dans la définition 2.15, muni de la loi de groupe usuelle, admet des
formules d’additions et de doublement de points différents. De plus, nous ne pouvons pas
appliquer ces formules à tous les points de la courbe car certains points, tel que le point O
, ne vérifient pas les équations d’addition et de doublement.
Algorithme 2.8 Algorithme de l’Echelle´ de Montgomery pour la multiplication scalaire
d’un point P sur une courbe elliptique E
Entrées k un scalaire, P un point de E
Sorties: kP
R0 ←O R1 ← P
n = log2(k)
Pour i = n − 1 à 0 Faire
Si ki = 0 alors
R1 ← R0 + R1
R0 ← 2R0 Sinon
R0 ← R0 + R1
R1 ← 2R1
Fin Si
Fin Pour
Retourner Q = kP
Cette particularité peut s’avérer problématique lorsque l’on considère une implémentation
de la multiplication scalaire d’un point en temps constant, i.e. pour tout point d’entrée P
et tout scalaire k, le temps d’exécution de l’algorithme calculant kP est constant. Comme
les temps de calculs pour effectuer kP sont différents, alors cela impliquent l’utilisation de
branchements conditionnels dont le temps d’exécution dépend des entrées. Ainsi, il est
commun d’utiliser des modèles alternatifs de courbes elliptiques qui admettent une loi de
groupe complète et uniforme. Notons que récemment Joost et al. [RCB16] ont construit
une loi de groupe complète pour les courbes de Weierstrass.
En pratique, considérer la nécessite d’une loi de groupe uniforme et complète pour des
applications cryptographiques des courbes elliptiques n’est pas un bon argument. En
effet, pour toutes les lois de groupe sur courbe elliptique le calcul du doublement de point
est beaucoup plus rapide que celui de l’addition, utiliser les formules d’additions pour
calculer un doublement de point n’est pas efficace et risque de grandement ralentir les
performances du calcul de kP. Dans ces conditions pour les applications réelles, nous
n’utiliserons pas l’uniformité d’une loi de groupe. De plus, la complétude de la loi de
groupe n’apporte aucune sécurité, car les points qui posent généralement problème,
comme dans le cas de la loi de groupe sur les courbes de Weierstrass, seront dans tous les
cas évités. Comme nous le verrons dans le chapitre 3, ces points peuvent être utilisés pour
mener des attaques par canaux auxiliaires [ GVY17a ].
L’utilisation de modèles alternatifs permet cependant d’accélérer les calculs sur les
courbes elliptiques, car les lois de groupe alors considérées sont plus efficaces comme
nous le verrons par la suite. Le premier exemple en ce sens est celui des courbes de
Montgomery [Mon87] qui ont été construites afin d’accélérer l’algorithme de
factorisation utilisant les courbes elliptiques [ Len 87].
Comme nous l’avons vu à la section 1.1, l’IoT que nous considérons dans cette
étude ne possède pas de bit de contrôle de la retenue. Ainsi, une implémentation basée sur
les courbes elliptiques définies sur un corps de grande caractéristique risque d’être
lourdement pénalisée en termes de performances. En effet, l’arithmétique sur Fp avec p
impair nécessite de propager la retenue tout au long du calcul d’addition ou de
multiplication. Il s’en suit, que nous privilégierons les modèles en caractéristiques 2 afin
d’éviter toutes les contraintes relatives à la propagation de la retenue. De plus, certaines
attaques par canaux auxiliaires utilisent cette propagation de la retenue afin d’inférer de
l’information sur la clef secrète k utilisée lors du calcul de kP, [DPN+16a]. Nous
présenterons brièvement les modèles alternatifs dans le cas de la caractéristique impair,
car la majeure partie des modèles alternatifs de courbes elliptiques sur les corps binaires
sont des adaptations de modèles déjà existant sur Fp.
Modèles alternatifs de courbes elliptiques sur Fp
L’un des premiers modèles alternatifs de courbes elliptiques a été introduit par
Montgomery [Mon87], il a pour avantage de pouvoir être utilisé efficacement avec
l’algorithme 2.8 de multiplication scalaire de l’Echelle´ de Montgomery. Il permet aussi
d’utiliser des formules d’additions et de doublement de points très efficaces dans le cas de
l’utilisation de l’Echelle´ de Montgomery. Une courbe de Montgomery se présente sous
la forme suivante :
EA,B : By2 = x3 + Ax2 + x (2.9)
Les travaux de Joye [JQ01], de Doche-Icart-Kohel [DIK06] et d’Edwards [ Edw 07] qui
présentent une forme alternative de courbes elliptiques admettant une loi de groupe
complète et uniforme ont permis de considérer les modèles alternatifs pour des
applications cryptographique. Le modèle d’Edwards est défini par l’équation suivante :
Ed : x2 + y2 = 1 + dxy (2.10)
Les courbes d’Edwards et de Montgomery ont l’avantage d’être birationnelles à une
courbe de Weierstrass, cette propriété est importante dans le cadre d’applications
cryptographiques. En effet, une grande partie des IoT déployés utilisent le modèle de
Weierstrass notamment au travers du standard du NIST [Gal13]. Ainsi, si nous voulons
déployer un nouveau réseau IoT utilisant un modèle alternatif de courbes elliptiques, il est
important que celui-ci puisse communiquer parfaitement avec un réseau préexistant
utilisant quant à lui les courbes de Weierstrass. Finalement, le modèle de Weierstrass peut
être considéré comme un invariant dans un écosystème IoT hétérogène, ce qui impose la
nécessite de compatibilité entre les modèles.
La figure 2.5, donne la représentation des courbes de Montgomery et d’Edwards sur R.
Les travaux de Bernstein et al. [BDL+11b, BCL14, BJL+15] ont permis d’adopter les
courbes d’Edwards sur un corps à large caractéristique pour des applications
cryptographiques. Les courbes d’Edwards Curve22519 [BDL+11b] et Curve448 [ Ham
15] font l’objet de normes RFC [LHT16, NJ16, JL17].
Il existe de nombreux modèles alternatifs de courbes elliptiques sur Fp tels que : la forme
de Doche-Icart-Kohel [DIK06], les jacobiennes quadratiques [ HWCD09], l’intersection
de jacobienne [FNW10], les hessiennes [JQ01, FJ10] et les hessiennes
(a) 3y2 = x3 + 7x2 + x (b) x2 + y2 = 1 − 30xy
Figure 2.5 – Courbe de Montgomery (A) et courbe d’Edwards (B) sur R.
Modèles Addition Doublement Différentielle
Weierstrass [OLAR13, Sta02b] 8M + 2S 3M + 4S + 2m 5M + 3S + 1 m
Edwards [BLF08, KLN14, KAK15] 13M +3S + 2m 2M + 6S + 1m 5M + 4S + 1 m
Hessienne [FJ10] 8M + 3S + 2m 6M + 3S + 1m 5M + 4S + 1 m
Huff [DJ11] 14M 6M + 2m 5M + 1 m
µ4-normale [Koh17] 9M + 2S 2M +5S + 2m 4M + 4S + 3 m
Table 2.2 – Nombres d’opérations nécessaire pour additionner et doubler un point sur les
modèles alternatifs de courbes elliptiques en caractéristique 2.
tordues [BCKL15], les courbes d’Edwards [Edw07, BL07] et les courbes d’Edwards
tordues [BBJ+08, HWCD08], les courbes de Huff [ JTV 10].
