elliptic curve et le problème du logarithm discret: ECDSA et ECDH

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut, je suis entrain de lire : cette série d’article
je crois avoir compris à peut près tout malgré mon maigre niveau en algèbre, mais dans le troisième article de la série, il arrive à l’algo pour l’elliptic curve diffie hellman (ECDH)

  • The private key is a random integer d chosen from {1,…,n−1} (where n is the order of the subgroup).
  • The public key is the point H=dG (where G is the base point of the subgroup).

You see? If we know d and G (along with the other domain parameters), finding H is "easy". But if we know H and G, finding the private key d is "hard", because it requires us to solve the discrete logarithm problem.

source

En effet, trouver H=dGH = dG est pas compliqué on a la lois pour multiplier un point G par un scalaire d
pour trouver dd on doit résoudre HG1H\cdot G^{-1}

Et apparemment là ça se complique, on tombe sur le problème du logarithme discret.

Considérons Eve, qqun qui connait, HH et GG
Eve calcule G+G+...+GG+G+...+G et regarde à chaque fois si c’est équivalent à HH on travail dans un cors finis, la lois d’addition est la suivante (pour G+G...G+G...): Capture d’écran 2019-07-25 à 23.47.43.png

Je comprends pas ce qui est dure avec H connus et G connut on addition G avec G jusque à trouver H, et il y a pas de calcules compliqué la dedans

j’ai aussi imaginé faire HG=(HxGx;HyGy)=(d;d)\frac{H}{G} = (\frac{H_x}{G_x};\frac{H_y}{G_y}) = (d;d) mais le problème vient que HG+G+...+GdH \equiv \underbrace{G+G+...+G}_d puisque la somme des G utilise la règle d’addition des corps fini et donc un modulo il se peut que que HxH_x soit petit que GxG_x et donc d<0d<0 alors que
d{1,...,n1}d \in \{1,...,n-1\}

En résumé :
1. HG=d\frac{H}{G} = d fonctionne pas a cause du modulo sur H
2. Pourquoi faire G+G+...+G=?HG + G +...+G=^{?} H En utilisant la règle d’addition du corps fini ne donne pas le bon dd ?

EDIT: lien réparé merci @ache

Édité par d3m0t3p

conseil: le thé est meilleur avec un zeste de citron

+0 -0

Bonjour,

Plus loin dans l’article, du moins avec le lien qu’a mis ache, tu as des exemples de valeurs utilisées en pratique pour les paramètres. Je t’invite à essayer de mettre en œuvre tes attaques avec ces valeurs-là pour bien comprendre pourquoi ça ne marche pas en pratique. Par exemple, tester toutes les valeurs possibles pour d marcherait en théorie, mais en pratique n est choisi très très grand, de l’ordre de 2^256 soit 10^77 si tu prends l’exemple dans l’article. Donc en pratique chaque essai au hasard a une chance sur 10^77 de réussir, avec e essais différents tu auras e * 10^-77 chances de réussir, donc pour avoir une chance sur un million de réussir (par exemple) il faudrait 10^71 essais. Admettons qu’on répartisse ce boulot sur k processeurs capables d’effectuer 10^11 essais par seconde (une sur-approximation des processeurs ayant 8 cœurs à 5 GHz, par exemple), que l’on fait tourner pendant 10^10 secondes soit 317 ans. Dans ce cas, il faudrait un nombre improbable de processeurs k=10^50 pour atteindre une chance sur un million de trouver la bonne solution, et même avec des processeurs plus performants ou un temps de calcul beaucoup plus long ce nombre reste aberrant.

+0 -0

Crypto <3

pour trouver dd on doit résoudre HG1H \cdot G^{-1}

Hmmm oui mais justement dans les groupes de façon générale (comme par exemple les courbes elliptiques), il n’existe pas de division. Là on est dans un groupe additif, donc l’opération classique est G+HG + H, par exemple, donc G1G^{-1} ne veut rien dire. On implémente la multiplication par un scalaire de façon immédiate, en additionnant plein de fois le tout, d’où le dG=G+G+...+GddG = \underbrace{G+G+...+G}_d. Par contre on ne dispose d’aucun moyen efficace de faire une division, c’est le problème du logarithme discret (transposé sur un groupe additif).

Du coup :

En résumé :
1. HG=d\frac{H}{G} = d fonctionne pas a cause du modulo sur H

Non, c’est parce qu’il n’existe pas de division dans un groupe.

  1. Pourquoi faire G+G+...+G=?HG + G +...+G=^{?} H En utilisant la règle d’addition du corps fini ne donne pas le bon dd ?
d3m0t3p

ça marche, mais c’est extrêmement long, comme le pointe mon VDD.

Édité par melepe

+0 -0
Auteur du sujet

Re, merci pour vos réponses, merci ache pour le bon lien

Par exemple, tester toutes les valeurs possibles pour d marcherait en théorie, mais en pratique n est choisi très très grand, de l’ordre de 2^256 soit 10^77 si tu prends l’exemple dans l’article. Donc en pratique chaque essai au hasard a une chance sur 10^77 de réussir, avec e essais différents tu auras e * 10^-77 chances de réussir, donc pour avoir une chance sur un million de réussir (par exemple) il faudrait 10^71 essais. Admettons qu’on répartisse ce boulot sur k processeurs capables d’effectuer 10^11 essais par seconde (une sur-approximation des processeurs ayant 8 cœurs à 5 GHz, par exemple), que l’on fait tourner pendant 10^10 secondes soit 317 ans. Dans ce cas, il faudrait un nombre improbable de processeurs k=10^50 pour atteindre une chance sur un million de trouver la bonne solution, et même avec des processeurs plus performants ou un temps de calcul beaucoup plus long ce nombre reste aberrant.

dentuk

Si je comprends bien G+G+...+Gd=?H\underbrace{G+G+...+G}_d =^? H prend beaucoup de temps même si calculer G+...+Gd=H\underbrace{G+...+G}_d = H est rapidement faisable car il faut calculer n1077n \approx 10^{77} somme de GG être sûre de trouver dd

et HG=d\frac{H}{G} = d ne fonctionne pas car la division n’est pas défini sur un groupe,
à ce propos, mon exemple suffirait-il à prouver que la division n’a pas de sens ? puisque   H<G    d<1\exists \; H < G \implies d<1 mais comme d>1Nd>1 \in \N on arrive à une contradiction prouvant que H/GH/G n’existe pas

conseil: le thé est meilleur avec un zeste de citron

+0 -0

Cette réponse a aidé l’auteur du sujet

Si je comprends bien G+G+...+Gd=?H\underbrace{G+G+...+G}_d =^? H prend beaucoup de temps même si calculer G+...+Gd=H\underbrace{G+...+G}_d = H est rapidement faisable car il faut calculer n1077n \approx 10^{77} somme de GG être sûre de trouver dd

C’est ça. Pour trouver dd, il faut regarder si G=HG = H. Si c’est pas le cas, on regarde si 2G=H2G = H. Si c’est pas le cas, on regarde si 3G=H3G = H. etc. jusqu’à trouver la bonne valeur, ce qui arrive au bout de 225510772^{255} \approx 10^{77} essais en moyenne.
Dans la pratique, les attaquants disposent de moyens plus efficaces que l’attaque par force brute, mais qui restent très lents. Pour reprendre l’exemple de 22562^{256}, l’attaque réussit au bout de 212810392^{128} \approx 10^{39} essais, ça reste lent.

et HG=d\frac{H}{G} = d ne fonctionne pas car la division n’est pas défini sur un groupe,

oui

à ce propos, mon exemple suffirait-il à prouver que la division n’a pas de sens ? puisque   H<G    d<1\exists \; H < G \implies d<1 mais comme d>1Nd>1 \in \N on arrive à une contradiction prouvant que H/GH/G n’existe pas

d3m0t3p

Non. Déjà, parce qu’il n’y a pas de relation d’ordre sur les éléments d’une courbe elliptique (on pourrait en définir une, mais tout le monde s’en fout), donc tu ne peux pas écrire H<GH < G sans définir ce que << veut dire dans le cadre d’une courbe elliptique : ça veut dire quoi, qu’un point d’une courbe est plus petit qu’un autre point de la même courbe ?

Ensuite, si tu écris plus précisément ton raisonnement, tu utilises des résultats qui ne sont vrais que sur R\mathbb R. Or là on n’est pas sur le corps des réels, mais dans un groupe défini sur une courbe elliptique.

Enfin, la division n’a pas de sens tout simplement parce qu’il n’y a pas de multiplication dans un groupe additif. :) Si tu relis le premier article, on parle d’addition, et de multiplication scalaire. La multiplication scalaire n’est qu’une addition déguisée, ce n’est pas une multiplication !

La multiplication scalaire, c’est quand on additionne un point GG avec lui-même dd fois, et on note ça dGdG. Attention, ça n’est qu’une notation ! D’ailleurs, certains notent plutôt ça [d]G[d]G. C’est donc une opération qui prend comme paramètres un entier (dd) et un point d’une courbe elliptique (GG).

La multiplication (interne), ce serait une opération entre deux points de la courbe, par exemple G×HG \times H, où on aurait défini une opération ×\times. La multiplication devrait en outre vérifier des propriétés dont je te fais grâce. On ne peut pas définir de multiplication sur les courbes elliptiques, c’est d’ailleurs pour ça qu’on s’en sert en crypto.

Dans un groupe additif, on peut définir une multiplication scalaire sans souci. Mais on ne peut pas définir de multiplication dans le cas général. Comme il n’existe pas de multiplication, il n’existe pas de division.

Mais une question qu’on peut se poser, c’est s’il existe une opération inverse à la multiplication scalaire. C’est-à-dire, j’ai H=dGH = dG, je connais GG, est-ce que je peux retrouver dd ? On peut, et cette opération inverse s’appelle le logarithme discret. Mais il est dur à calculer.

Édité par melepe

+0 -0
Auteur du sujet

okok,
Merci pour ton temps c’est désormais clair pour moi
Dans ma tête j’avais intuitivement définis H<G    [Hx<Gx]  &  [Hy<Gy]H < G \implies [H_x <G_x] \; \& \; [H_y < G_y]
merci beaucoup :-)

conseil: le thé est meilleur avec un zeste de citron

+0 -0

C’est effectivement une relation d’ordre (même si pas totale), mais pour le plaisir de pinailler, il faudrait définir ce que ça donne pour le point à l’infini qui n’a pas de coordonnées xx et yy à proprement parler. :)

merci beaucoup :-)

Au plaisir !

Édité par melepe

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte