Sujet 16: Le problème du logarithme discret et attaques I

Soient \(G\) un groupe et \(a, b \in G\) avec \(a^k=b\) pour un entier \(k\). Le problème du logarithme discret est le nom donné au calcul de \(k\).

C'est un problème central en cryptographie et la sécurité de certains systèmes repose sur la difficulté à trouver ce \(k\).

Dans les groupes finis

Si l'on s'intéresse aux groupes \( G=\mathbb{Z}_{p} \), il est alors clair de part la cyclicité que pour toute paire de points \(a, b \in G\), il y a un certain \(k\) tel que \(a^k\equiv b\) et le problème du logarithme discret existe donc tout le temps.

Dans les courbes elliptiques

De façon similaire, si l'on considère l'ensemble des points se trouvant sur une courbe elliptique \(E\) sur un corps fini en posant \(G=E(\mathbb{F}_{p})\), le problème du logarithme discret revient à trouver \(k\) tel que \(ka=b\) pour \(a,b \in E\) des points sur la courbe.

Puisque l'objectif du problème du logarithme discret est d'être difficile à résoudre, nous allons maintenant essayer de l'attaquer. Une façon triviale d'aborder le problème est de faire prendre à \(k\) toutes les valeurs possibles et de regarder si une valeur correspond. C'est bien entendu beaucoup trop long dès que le groupe \(G\) a beaucoup d'éléments. La première méthode que nous allons voir est l'algorithme du calcul d'indice qui peut être utilisé pour attaquer un logarithme discret sur un groupe fini du type \( G=\mathbb{F}_{p}^\times \).

Calcul d'indice [Modifier]

Soit \(p\) un nombre premier. L'ordre de \(a\) mod \(p\) est le plus petit entier \(k>0\) tel que \(a^k\equiv 1 \) (mod \(p\)). L'ordre de \(a\) mod \(p\) divise \(p-1\).

Une racine primitive modulo p est un entier \(g\) tel que l'ordre de \(g\) mod \(p\) soit égal à \(p-1\). Dans ce cas, tous les entiers sont congruents mod \(p\) à 0 ou à une puissance de \(g\) et \(g\) génère par conséquent \( \mathbb{Z}_{p}^\times \).

Soient \( G=\mathbb{F}_{p}^\times \) et \(g\) une racine primitive modulo \(p\), \(g\) est donc un générateur de \(G\). Soit \(h \in G\). Dans le problème du logarithme discret \(g^k\equiv h \) (mod \(p\)) , posons \(k=L(h)\) (qui dépend donc de \(g\) et de \(p\)) et on obtient donc :

\(g^{L(h)}\equiv h \) (mod \(p\)).

Soient \(h_1, h_2 \in G\). On a :

\(g^{L(h_1h_2)}\equiv h_1h_2 \equiv g^{L(h_1)+L(h_2)} \) (mod \(p\)) dont l'on déduit que \(L(h_1h_2)\equiv L(h_1) + L(h_2) \) (mod \(p-1\)).

On remarque donc que \(L(h)\) se comporte comme un logarithme classique. L'idée pour résoudre \(g^k\equiv h \) (mod \(p\)) est la suivante :

Choisir une base \(B\) de petits nombres premiers (ne dépendant pas de \(h\))
Calculer \(L(i)\) \(\forall i \in B\)
- Générer des équations du type \(g^{i} \equiv \pm\) un certain produit d'éléments de \(B\) (mod \(p\)) où \(i\in B\)
- Transformer les équations de sorte à faire apparaître les \(L(i)\)
- Résoudre le système pour obtenir les valeurs des \(L(i)\)
Calculer \(g^j\cdot h\) (mod \(p\)) pour des valeurs aléatoires de \(j\) jusqu'à obtenir un entier qui peut être factorisé en un produit d'éléments de \(B\)
Transformer l'équation pour faire apparaître les \(L(i)\) et ainsi obtenir \(k=L(h)\)

Exemple

Soient \(p = 23\) et \(g=17\). On veut résoudre \(17^k=12\) (mod 23).

On choisit une base de petits nombres premiers. Comme c'est un exemple avec des petits nombres, il n'y a pas besoin d'aller très loin. Posons \(B = \{2,3,5\}\).
On veut calculer \(L(2), L(3), L(5)\). Pour ce faire on va générer des équations du type \(g^{i} \equiv \pm\) un certain produit d'éléments de \(B\) (mod \(23\)) :
\(\space \space \space \space 17^1\equiv 2^3 \cdot 5\) (mod \(23\))
\(\space \space \space \space 17^2\equiv 2^7\) (mod \(23\))
\(\space \space \space \space 17^2\equiv 3^5\) (mod \(23\))
Maintenant transformons ces équations pour faire apparaître les \(L(2), L(3), L(5)\) :
\(\space \space \space \space 1\equiv 3L(2)+L(5)\) (mod \(22\))
\(\space \space \space \space 2\equiv 7L(2)\) (mod \(22\))
\(\space \space \space \space 2\equiv 5L(3)\) (mod \(22\))
De la seconde équation on tire :
\(\space \space \space \space L(2)\equiv 2/7\equiv 2\cdot 19 \equiv 16\) (mod \(22\))
De la troisième on tire :
\(\space \space \space \space L(3)\equiv 2/5\equiv 2\cdot 9 \equiv 18\) (mod \(22\))
De la première on tire :
\(\space \space \space \space L(5)\equiv -47\equiv 19\) (mod \(22\))
Remarquons que trouver les \(L(2), L(3), L(5)\) ne dépend pas du second membre de \(17^k=12\) (mod 23).
On va maintenant calculer \(17^j\cdot 12\) (mod \(23\)) pour des valeurs aléatoires de \(j\) jusqu'à tomber sur une valeur se factorisant en produits de \(B\). Dans cet exemple simple, il n'y a pas besoin d'aller très loin :
\(\space \space \space \space 17^1\cdot 12 \equiv 20\equiv 2^2\cdot 5 \) (mod \(23\))
On obtient donc l'équation suivante :
\(\space \space \space \space L(17) \equiv 2L(2) + L(5) -1 \equiv 6 \) (mod \(22\))
On a donc trouvé k et on a résolu l'équation : \(17^{6}=12\) (mod 23).

Voir l'exemple 5.1 pour un calcul un peu plus complexe.

Attaque "pas de bébé, pas de géant" [Modifier]

L'attaque par calcul d'indice n'est pas utilisable pour des groupes arbitraires puisqu'elle est basée sur la décomposition d'un entier en facteurs premiers. Puisque nous nous intéressons aux courbes elliptiques, nous allons maintenant voir une attaque qui marche pour un groupe \(G\) arbitraire, en particulier un groupe de points sur une courbe elliptique.

Soit \(G=E(\mathbb{F}_{p})\). Soient \(P, Q \in G\) et on veut résoudre le problème du logarithme discret \(kP=Q\). On va supposer que :

k existe
l'ordre \(N\) de \(G\) est connu
\(P\) génère \(G\)

L'algorithme pas de bébés, pas de géants pour résoudre ce problème est le suivant :

Choisir un entier \(m \geqslant \sqrt{N}\) et calculer \(mP\)
Faire une liste des points \(iP\) pour \(0\leqslant i<m \)
Calculer les points \(Q-jmP\) pour \(j=0,1,...m-1\) jusqu'à ce qu'un de ces points soit égal à un point de la liste précédente
On obtient ainsi \(iP=Q-jmP\), ce qui implique que \(Q=kP\) avec \(k \equiv i+jm\) (mod \(N\))

Explication

On sait que \(0\leqslant k < m^2\) puisque \(m^2>N\).
Si l'on pose \(k_0 \equiv k \)(mod \(m\)) (\(0\leqslant k_0<m\)) et \(k_1=(k-k_0)/m\) (\(0\leqslant k_1<m\)), on a \(k=k_0+mk_1\)
Si \(i=k_0\) et \(j=k_1\), on a bien \(Q-l_1mP=kP-k_1mP=k_0P\)

Références [Modifier]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Sections 5.1, 5.2.1