LOGARITHME DISCRET
Le logarithme discret est un problème mathématique qui est utilisé dans certains algorithmes cryptographiques à clé publique. Dans un groupe cyclique d’ordre \(q\), avec un générateur \(g\), si l’on a une équation de la forme \(g^x = h\), alors \(x\) est appelé le logarithme discret de \(h\) par rapport à la base \(g\), modulo \(q\). En termes simples, il s’agit de déterminer l’exposant \(x\) lorsqu’on connaît \(g\), \(h\), et \(q\). Le logarithme discret est donc la réciproque de l’exponentielle dans un groupe cyclique fini. Cependant, pour de grandes valeurs de \(q\), résoudre le problème du logarithme discret est considéré comme algorithmiquement difficile. Cette propriété est exploitée pour assurer la sécurité de nombreux protocoles cryptographiques, tels que le protocole de Diffie-Hellman pour l’échange de clés.
Le logarithme discret est aussi utilisé dans la cryptographie à courbes elliptiques (ECC), entre autres dans l’algorithme ECDSA (Elliptic Curve Digital Signature Algorithm). Dans le contexte des courbes elliptiques, le problème du logarithme discret s’étend à la recherche d’un scalaire \(k\) tel que \(k \cdot G = K\), où \(G\) et \(K\) sont des points sur la courbe, et \(\cdot\) représente l’opération de multiplication de points. Dans le contexte de Bitcoin, les scripts peuvent utiliser soit ECDSA, soit le protocole de Schnorr, afin de bloquer des UTXOs. Ils reposent tous deux sur l’impossibilité de calculer le logarithme discret.