Cours Courbes Elliptiques
Cours Courbes Elliptiques
Cours Courbes Elliptiques
https://fr.wikipedia.org/wiki/Courbe_elliptique
Rappel sur les protocoles asymétriques
• Dans un protocole cryptographique asymétrique, il y a deux clés : une
clé publique et une clé privée
• Confidentialité (ex : RSA)
• La clé publique sert à chiffrer, la clé privée sert à déchiffrer
• RSA étant lent, il sert davantage pour la signature (intégrité) que pour le
chiffrement
• Intégrité (ex : RSA et fonction de hachage)
• La clé privée sert à signer, la clé publique sert à vérifier la signature
• Echange de secret (ex : Diffie-Hellman)
• Les deux partenaires échangent des informations chiffrées avec la clé
publique, et calculent un secret partagé en utilisant leur clé privée
Efficacité de RSA
• En 2021, la taille des clés RSA recommandée est d’environ 2048 bits
• Pour information, le record de factorisation (au 28/02/2020) était de 829 bits,
soit un nombre à factoriser de 250 chiffres décimaux
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
• Cela signifie que toutes les opérations qui utilisent des clés RSA (ex :
chiffrement, déchiffrement, signature, etc.) se font sur 2048 bits
• C’est long… surtout pour les ordinateurs ayant peu de ressources (ex :
téléphones portables, montres connectées, objets de l’IoT, etc.)
• Pourquoi faut-il des clés aussi longues ?
• Comment concevoir un protocole plus efficace que RSA ?
Pourquoi faut-il des clés aussi longues dans
RSA ? (1/2)
• Une clé RSA valide est un produit de deux nombres premiers =>
certains nombres ne sont pas des clés valides
• Par exemple, 2021 est une clé RSA valide (2021=43*47)
• Mais, 2022 n’est pas une clé RSA valide (2022=2*3*337)
• Donc, le nombre de clés RSA valides est inférieur à 2n, avec n la taille
de la clé RSA
• Par exemple, si la clé RSA faisait 8 bits, il n’y aurait que 158 clés valides sur les
28=256 entiers. Un algorithme de cryptanalyse n’aurait qu’à tester ces 158
clés pour trouver la bonne.
• Si la clé RSA faisait 16 bits, il n’y aurait qu’à tester 31262 clés (sur les 65536
nombres)
Pourquoi faut-il des clés aussi longues dans
RSA ? (2/2)
• De plus, l’algorithme actuel le plus rapide pour factoriser un nombre n
est assez efficace
• Il s’appelle le crible généralisé du corps des nombres
• Sa complexité est
https://en.wikipedia.org/wiki/General_number_field_sieve
• Pour une clé de 1024 bits, il faut 286 opérations, donc une sécurité de 86 bits
• Pour une clé de 2048 bits, il faut 2116 opérations, donc une sécurité de 116
bits
• (Remarque : dans les algorithmes de chiffrement symétriques comme
DES ou AES, une clé de 128 bits fournit 128 bits de sécurité)
Vers un protocole plus efficace que RSA
• L’attaque principale de RSA est liée à la factorisation des entiers => il
faut trouver un nouveau protocole qui ne se base pas sur la
factorisation des nombres entiers
• Et on doit trouver une fonction qui est :
• Facile à calculer dans un sens (c’était l’exponentiation modulaire pour RSA)
• Difficile à calculer dans l’autre sens (c’était le logarithme discret pour RSA)
• Qui possède une faille (c’était la connaissance de la clé privée pour RSA, qui
permet une énorme simplification du calcul du logarithme discret)
Les courbes elliptiques
• Les courbes elliptiques sont des fonctions mathématiques
particulières
• Elles correspondent à des équations de la forme :
http://www.herongyang.com/EC-Cryptography/Algebraic-
Description-of-Elliptic-Curve-Addition.html
Addition de deux points P et Q (2/3)
• Approche géométrique
• Si la droite (PQ) est parallèle à l’axe
des ordonnées, on considère que la
troisième intersection est le point à
l’infini O
• Le symétrique de O est O
• Donc R=O
• Remarque : dans ce cas, Q est le
symétrique de P par rapport à l’axe
des abscisses, donc on note Q=-P. On
a ainsi P+(-P)=O, ce qui est cohérent
avec notre interprétation du O
comme élément neutre
https://electriccoin.co/blog/snark-explain7/
Addition de deux points P et Q (3/3)
• Approche géométrique
• Pour ajouter P à P, on trace la
tangente à la courbe en P, et on
considère que cette tangente
touche 2 fois la courbe
• On cherche la troisième
intersection, et on calcule le
symétrique
• On a donc calculé P+P
• On note P+P=2.P
https://www.embedded.com/an-introduction-to-elliptic-curve-
cryptography/
Multiplication d’un point P par un entier k
• On cherche à calculer Q=k.P
• On développe : Q=P+P+P+…+P (k fois)
• On calcule P+P=2.P, puis (2.P)+P=3.P, puis (3.P)+P.=4.P, etc., jusqu’à obtenir k.P
• Remarque :
• On peut aller plus rapidement en utilisant la multiplication rapide
• Exemple : pour calculer 9.P, on peut calculer :
• 2.P => coûte une addition
• Puis 4.P=2.P+2.P => coûte une addition
• Puis 8.P=4.P+4.P => coûte une addition
• Puis 9.P=8.P+P => coûte une addition
Signatures
• Elliptic Curve Digital Signature Algorithm (ECDSA)
• Génération des clés :
• Alice choisit une courbe elliptique (a, b, p, P, n)
• Alice choisit un entier aléatoire s entre 1 et n-1
• La clé privée est s
• La clé publique est Q=s.P
• Signature d’un message M par Alice :
• Alice choisit un nombre aléatoire k entre 1 et n-1, et calcule le point k.P=(i,j)
• Alice envoie (i [n], k-1(H(M)+s.i [n]))
• Vérification par Bob :
• Bob calcule le point (H(M).y-1 [n]).P+(x.y-1 [n]).Q=(i,j), et vérifie que x=i [n]
Echange de clés
• Elliptic Curve Diffie-Hellman (ECDH)
• Alice et Bob s’accordent sur une courbe elliptique (a, b, p, P, n)
• Alice et Bob ont chacun leur clé privée, et la clé publique de l’autre
• Ces clés peuvent être créées pour l’occasion
• La clé partagée est : privAlice.privBob.P
• Alice la calcule avec privAlice.pubBob
• Bob la calcule avec privBob.pubAlice
Complication…
• Malheureusement, ce n’est pas du tout pratique d’utiliser des
courbes elliptiques définies sur des réels…
• Et la méthode géométrique n’est pas très précise…
• On va donc utiliser des courbes elliptiques définies sur des entiers
• Et on va aussi se limiter à des entiers codés avec un nombre de bits fixe, donc
on va travailler en arithmétique modulaire
• L’équation devient :
• On va utiliser une approche analytique (plus précise)
Méthode analytique pour l’addition de deux
points (1/3)
• Entrée :
• Les valeurs de a, b et p dans :
17.P=(6,14)
6.P=(16,13)
16.P=(10,11)
12.P=(0,11) 10.P=(7,11)
11.P=(13,10)
19.P=infinity
9.P=(7,6) 8.P=(13,7)
7.P=(0,6) 3.P=(10,6)
13.P=(16,4)
2.P=(6,3)
4.P=(3,1)
1.P=(5,1) 14.P=(9,1)
Exemple de nuage de points (3/4)
9.P=(7,6)
2.P=(6,3)
Attaques sur les courbes elliptiques
• Les seules attaques connues sur les courbes elliptiques sont les
attaques sur les groupes cycliques
• Attaque baby step giant step [Shanks, 1971] : complexité O(sqrt(n)), avec n
l’ordre du groupe
• Attaque rho de Pollard [Pollard, 1978] : complexité O(sqrt(n)), avec n l’ordre
du groupe
• Pour atteindre la même sécurité avec une courbe elliptique qu’avec
RSA, on peut prendre une taille de clé plus petite
• Pour atteindre 80 bits de sécurité, il faut un groupe cyclique d’ordre n, avec n
sur 160 bits (la complexité pour cryptanalyser étant de O(sqrt(2160))=O(280),
au lieu de 1024 bits dans RSA)
Attaque baby step giant step (1/2)
• On connaît P et Q tels que Q=k.P, et on cherche k
• On pose m=ceil(sqrt(n))
• On calcule i.P pour tout 0<=i<m
• On calcule Q-j.m.P pour tout 0<=j<m
• Dès qu’on trouve une correspondance entre les i.P et les Q-j.m.P, on
déduit que k=i+j.m
• La complexité est O(sqrt(n)) en nombre d’opérations sur la courbe
elliptique (c’est-à-dire, sans la recherche de la correspondance)
Attaque baby step giant step (2/2)
• Exemple :
• On connaît P=(5,1) et Q=(7,6), et on cherche k (qui vaut 9)
• On pose m=ceil(sqrt(n))=ceil(sqrt(19))=5
• On a 0.P = infinity, 1.P=(5,1), 2.P=(6,3), 3.P=(10,6), 4.P=(3,1)
• On a Q-0.m.P=Q=(7,6)
Q-1.m.P=Q-5.P=Q+14.P=4.P=(3,1)
Q-2.m.P=Q-10.P=Q+9.P=(5,16)
Q-3.m.P=Q-15.P=(16,4)
Q-4.m.P=Q-20.P=Q-P=(13,7)
• La correspondance est entre i=4 (car 4.P=(3,1)) et j=1 (car Q-1.m.P=(3,1)), on
calcule k=4+1*5=9, ce qui est bien la valeur recherchée
Comment choisir les paramètres d’une
courbe elliptique ?
• Des courbes pré-calculées existent
• Leurs paramètres a, b et p sont calculés pour que le groupe cyclique ait un
ordre important
• Ex : Curve25519 : a=486662, b=1, p=2^252+277(…)493, fournissant 128 bits
de sécurité
• Ex : NIST P-256 : a=-3, b=410(…)291, p=2^256-2^224+2^192+2^96-1,
fournissant 128 bits de sécurité
• Pour calculer l’ordre du sous-groupe cyclique généré, on utilise d’abord
l’algorithme de Schoof, qui donne l’ordre N de la courbe elliptique. Ensuite, on
peut trouver assez facilement des sous-groupes cycliques qui ont pour ordre
un diviseur de N, ainsi que le point générateur associé.
• Les paramètres sont choisis de manière à éviter des attaques connues