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.
En effet, trouver H=dG est pas compliqué on a la lois pour multiplier un point G par un scalaire d
pour trouver d on doit résoudre H⋅G−1
Et apparemment là ça se complique, on tombe sur le problème du logarithme discret.
Considérons Eve, qqun qui connait, H et G
Eve calcule G+G+...+G et regarde à chaque fois si c’est équivalent à H
on travail dans un cors finis, la lois d’addition est la suivante (pour G+G...):
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 GH=(GxHx;GyHy)=(d;d)
mais le problème vient que H≡dG+G+...+G puisque la somme des G utilise la règle d’addition des corps fini et donc un modulo il se peut que que Hx soit petit que Gx et donc d<0 alors que d∈{1,...,n−1}
En résumé :
1. GH=d fonctionne pas a cause du modulo sur H
2. Pourquoi faire G+G+...+G=?H En utilisant la règle d’addition du corps fini ne donne pas le bon d ?
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.
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+H, par exemple, donc G−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=dG+G+...+G. 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. GH=d fonctionne pas a cause du modulo sur H
Non, c’est parce qu’il n’existe pas de division dans un groupe.
Pourquoi faire G+G+...+G=?H En utilisant la règle d’addition du corps fini ne donne pas le bon d ?
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.
Si je comprends bien dG+G+...+G=?H prend beaucoup de temps même si calculer dG+...+G=H est rapidement faisable
car il faut calculer n≈1077 somme de G être sûre de trouver d
et GH=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 mais comme d>1∈N on arrive à une contradiction prouvant que H/G n’existe pas
Si je comprends bien dG+G+...+G=?H prend beaucoup de temps même si calculer dG+...+G=H est rapidement faisable
car il faut calculer n≈1077 somme de G être sûre de trouver d
C’est ça. Pour trouver d, il faut regarder si G=H. Si c’est pas le cas, on regarde si 2G=H. Si c’est pas le cas, on regarde si 3G=H. etc. jusqu’à trouver la bonne valeur, ce qui arrive au bout de 2255≈1077 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 2256, l’attaque réussit au bout de 2128≈1039 essais, ça reste lent.
et GH=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 mais comme d>1∈N on arrive à une contradiction prouvant que H/G n’existe pas
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<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. 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 G avec lui-même d fois, et on note ça dG. Attention, ça n’est qu’une notation ! D’ailleurs, certains notent plutôt ça [d]G. C’est donc une opération qui prend comme paramètres un entier (d) et un point d’une courbe elliptique (G).
La multiplication (interne), ce serait une opération entre deux points de la courbe, par exemple G×H, où on aurait défini une opération ×. 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=dG, je connais G, est-ce que je peux retrouver d ? On peut, et cette opération inverse s’appelle le logarithme discret. Mais il est dur à calculer.
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 x et y à proprement parler.
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
Si tu relis le