Courbes elliptiques pour les nuls
Bonjour,
Je vous propose un nouvel élément à utiliser : 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 :
- connaissant un point P et un entier n, on peut facilement calculer le point nP
- connaissant les points P et nP, il est très difficile de calculer n
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 pEnsuite, on définit une addition pour les points de E.
Attention : il ne s'agit pas d'une addition "simple" !
Si A, B et C sont 3 points de E tels que A = B + C, alors on n'a pas Ax = Bx + Cx et Ay = By + Cy !
C'est beaucoup plus compliqué : A est l'opposé du point d'intersection entre la droite BC et E.
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 ne 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'.
Qu'en pensez-vous ?
Répondre avec citation
Partager