cryptographie : qu'est-ce qu'une hypothèse logarithmique discrète ? comment met-il en place des preuves sans confiance ?
Le problème du logarithme discret est un concept de cryptographie qui sous-tend la base d’une grande partie de la cryptographie moderne.
En général, le problème du logarithme discret stipule que pour l’équation
bk (mod p) = a où b, a et p sont des valeurs connues et p est premier, trouver k est difficile.
C’est difficile à cause de l’arithmétique modulaire ; pour trouver k, vous auriez besoin de le forcer brutalement. De plus, il existe une infinité de solutions car vous ne savez pas combien de fois pb^k vaut. Les valeurs b et p sont également des valeurs spécifiquement choisies qui rendent ce problème plus difficile car certaines valeurs (en particulier les valeurs inférieures et les valeurs non premières) sont faciles à résoudre (facile en ce sens que cela ne prend pas beaucoup de temps mais la complexité temporelle est toujours la même).
Bien qu’il n’y ait aucune preuve que le problème du logarithme discret soit réellement difficile, on pense qu’il est difficile car personne n’a trouvé un moyen de calculer rapidement le logarithme.
Mais Bitcoin utilise en fait une version légèrement différente de ce problème connu sous le nom de problème de logarithme discret de la courbe elliptique (ECDLP). Avec les mathématiques EC, b est en fait un point sur une courbe elliptique, il a une valeur x et y. Plutôt que d’élever b à un certain nombre k, vous effectuez en fait une multiplication scalaire EC avec un certain nombre k, il est donc
bk (mod p) = a
Cela se résume à ajouter b à lui-même k fois, et la sécurité vient du fait qu’il est difficile de comprendre ce que deux points ont été additionnés pour obtenir un troisième point.
Le processus d’ajout d’un point de courbe EC à lui-même signifie que vous trouvez une ligne tangente au point, prolongez la ligne jusqu’à l’endroit où elle croise la courbe et inversez la valeur y de ce point. Faire cela, et l’inverser, sur les nombres réels n’est pas si difficile, mais la cryptographie EC est effectuée sur un champ fini d’ordre p qui est un grand nombre premier, ce qui signifie que toutes les valeurs sont (mod p) donc, quand vous tracez un graphique la courbe, c’est partout dans votre graphique. Cela signifie que, étant donné un point sur la courbe, il est difficile de déterminer quels autres points ont été ajoutés pour arriver à ce point, il est donc difficile d’inverser ce processus.
Dans ECDLP et dans le DLP normal, k est la clé privée et la résolution de l’un ou l’autre des problèmes de journal discret vous permettrait de trouver la clé privée k.
Il existe des algorithmes tels que l’algorithme de Shors qui peuvent permettre aux ordinateurs quantiques de résoudre le problème du log discret.
Notez que ce genre de choses est difficile et que je ne suis pas un expert en cryptographie. C’est juste comme ça que j’ai compris les choses et ce n’est peut-être pas nécessairement correct ou logique.
