Logarithme Discret

Le logarithme discret est un problème mathématique central en cryptographie. Il s'agit de trouver un entier $ x $ tel que :

$$ g^x \equiv y \pmod{n} $$

avec

— $ g $ est un générateur d'un groupe cyclique fini (souvent $ \mathbb{Z}_n^* $),

— $ y $ est un élément de ce groupe,

— $ n $ est un nombre premier (ou un entier définissant l'ordre du groupe).

C'est l'équivalent discret du logarithme classique, où est recherché l'exposant $ x $ qui transforme $ g $ en $ y $ dans un espace fini.

Ses applications principales sont en cryptographie. C'est le fondement d'algorithmes comme Diffie-Hellman (échange de clés) et ElGamal (chiffrement/signature).

Il est aussi utilisé en Preuve à divulgation nulle de connaissance pour les protocoles d'authentification sans divulgation de secret.

Le DLP (Discrete Logarithm Problem) consiste à trouver $ x $ dans l'équation : $$ g^x \equiv y \pmod{n} $$ avec $ g, y, n $ connus.

Ce problème est considéré comme difficile pour des groupes bien choisis, ce qui en fait un pilier de la cryptographie asymétrique.

Pour de petits $ n $, utiliser :

— Recherche exhaustive par force brute : Tester $ x $ de 1 à $ n-1 $

— Algorithme Baby-step Giant-step :

1. Calculer $ g^j $ pour $ j = 0 $ à $ m-1 $ (baby-steps)

2. Calculer $ y \cdot g^{-km} $ pour $ k = 0 $ à $ m-1 $ (giant-steps)

3. Chercher une collision

De nombreux chercheurs ont tenté de trouver des méthodes pour résoudre rapidement le problème du logarithme discret. Quelques algorithmes peuvent être efficaces dans certains cas :

— Baby-step Giant-step : Algorithme générique en $ O(\sqrt{n}) $

— Index Calculus : Efficace dans $ (\mathbb{Z}/n\mathbb{Z})^* $, mais pas dans les courbes elliptiques.

— Algorithme de Pohlig-Hellman : Exploite la factorisation de $ n $ (ordre du groupe)

— Attaques par calcul quantique : L'algorithme de Shor résout le DLP en temps polynomial sur un ordinateur quantique.

Pour $ (\mathbb{Z}/n\mathbb{Z})^* $ :

— Choisir un grand premier $ n $ (ex. : 2048 bits).

— Vérifier que $ n-1 $ a un grand facteur premier.

— Sélectionner un générateur $ g $ d'ordre premier.

Pour les courbes elliptiques :

— Utiliser des courbes standardisées (ex. : NIST P-256, Curve25519)

— Éviter les courbes avec des propriétés spéciales (ex. : courbes supersingulières)