Courbes elliptiques pour les nuls

Comprendre la cryptographie sur les courbes elliptiques sans (trop) entrer dans les détails théoriques.

Notion de base de la cryptographie avec des courbes elliptiques (elliptic curve = EC).
On se donne une arithmétique dans laquelle on manipule des points et des entiers.
On a une addition entre points (point + point -> point)
On a une multiplication entre entiers et points (entier * point -> point)
Toute la sécurité est basée sur le fait que, dans cette arithmétique :
La notion de "facile/difficile" renvoie aux temps de calculs nécessaires.
Les courbes elliptiques
Une courbe elliptique E est définie par une équation de la forme y² = x³ + ax² + b.
Pour faire de la cryptographie, on se place dans le corps Z/pZ.
La courbe E est alors définie par un triplet d'entiers ( a,b,p ) tels que
- p premier
- 0 < |a| < p
- 0 < |b| < p
- 4a³ + 27b² mod p != 0
La courbe elliptique E est l'ensemble des paires d'entiers (x,y) tels que :
y² mod p == ( x³ + ax² + b ) mod p

Ensuite, on définit une addition pour les points de E.
Attention : il ne s'agit pas d'une addition "simple" !
Si P, Q et R sont 3 points de E tels que R = P + Q, alors on n'a pas Rx = Px + Qx et Ry = Py + Qy !
C'est beaucoup plus compliqué : R est l'opposé du point d'intersection entre la droite PQ et E.
beau schéma ici
Pour plus de détails mathématiques, suivre les liens indiqués plus bas.
Pourquoi définir une addition si compliquée ?
Pour se donner une arithmétique satisfaisant les critères de sécurité nécessaires à la cryptographie.
Une fois qu'on sait additionner des points sur E, on peut calculer 2P = P + P, 3P = P + 2P, nP = P + (n-1)P.
On obtient donc une multiplication entre entiers et points de E.
Sur une courbe elliptique on définit G, un "générateur" :
Que quel que soit P un point de E, il existe un entier n tel que P = nG.
Il peut exister plusieurs générateurs, mais il existe des points de E qui n'en sont pas.
Création des clés :
Pour une courbe elliptique E de générateur G, on choisit un entier k.
- la clef privée = (E,G,k)
- la clef publique = (E,G,kG)
Comme il est assez difficile de trouver E (i.e. a, b et p) et surtout G, on utilise des valeurs fournies
par la littérature => Seul k reste à choisir.
De plus, pour des raisons mathématiques qui ne seront pas développées ici, toutes les courbes elliptiques
n'apportent pas le même niveau de sécurité.
Pour faire de la cryptographie sûre, il est donc très important de choisir ces constantes dans la littérature.
Elles font partie de la clef publique et peuvent donc être exposées sans perte de sécurité.
En revanche, dans l'exemple développé ici, on s'autorise à utiliser des courbes quelconques.
Chiffrement/déchiffrement :
Le message m est chiffré avec un algo symétrique et c'est la clef qui est "transmise" en utilisant une EC :
- Chiffrement :
  On choisit un entier r dans { 1,p-1 } et on calcule S = rkG.
  A partir de S on dérive une clef de chiffrement symétrique K et on calcule m' = m chiffré par K.
  --> le message chiffré = la paire ( m' , rG )
- Déchiffrement :
  On retrouve S = k(rG) dont on dérive K avec laquelle on déchiffre m'.

Hadrien Flammang - mai 2013

Signaler un problème

paipscola

Candidat au Club

Le 24/01/2014 à 14:42

salut a tous
problème j'ai un examat sur la cryptographie avancé je cherche un code source ou bien application mobile (sumsung) qui désigne les courbe elliptique
pour vérifier les point de algamel
"" application mobile désigne les courbe elliptique

Poster un commentaire

Developpez.com décline toute responsabilité quant à l'utilisation des différents éléments téléchargés.