Logarithme discret

Définition

Si \(A\in G=\langle g\rangle\), avec \(g\) d’ordre \(n\), on note \(\Log(A,g)\) l’unique \(a\in\Z/n\Z\) tel que \(A=g^a\).

Le calcul de \(\Log(A,g)\) est difficile. Par énumération il nécessite \(O(a)=O(n)\) multiplications jusqu’à trouver \(a\).

Si vous suivez...

Est-ce que vous avez un terminal gp ouvert ?

Si vous suivez...

Quel est le plus petit générateur de \(\F_{1009}^\times\) ?

    1. 4

    1. 5

    1. 7

    1. 11

Baby-step Giant-step

Au lieu de chercher un élément fixé dans une grande liste d’éléments, on cherche un élément commun à deux listes plus petites (stratégie meet in the middle, déjà vue dans l’attaque double DES).

On pose \(B=\ceil{\sqrt{n}}\), alors par décomposition en base \(B\), il existe \(0\leq x_0, x_1<B\) tels que

\[a = x_0+x_1B\]

dans ce cas

\[A = g^a \Leftrightarrow g^{x_0} = A(g^{-B})^{x_1}\]

de sorte qu’il suffit de trouver une collision en \(x_0,x_1\).

L’algorithme est le suivant

  • calculer la liste \(L\) des \(g^{x_0}\) pour \(0\leq x_0<B\)

  • poser \(G=g^{-B}\)

  • pour \(0\leq x_1<B\), dès que \(AG^{x_1}\) est dans \(L\) et vaut \(g^{x_0}\), rendre \(a=x_0+x_1B\).

Pour rendre la recherche rapide, il faut remplacer la liste par une structure qui rende l’insertion et le test d’appartenance rapides

  • une table de hachage (arbre), l’insertion et la recherche sont en log

  • une liste que l’on trie, ce qui permet des recherches dichotomiques en log.

Dans tous les cas, pour \(B\approx\sqrt n\) la complexité est de \(O(\sqrt n\log n)\) opérations et \(O(\sqrt n)\) en espace de stockage d’éléments.

dlp_bsgs(A,g,n) = {
  if(A==1,return(0));
  B = sqrtint(n)+1;
  bs = g; gs = 1;
  \\ baby steps
  baby = vector(B); baby[1] = lift(g);
  for(i=2,B, baby[i] = lift(baby[i-1]*g));
  order = vecsort(baby,,1);
  baby = vector(B,i,baby[order[i]]);
  \\ giant steps
  gs = baby[B]^-1;
  for(j=0,B-1,
    i = vecsearch(baby,lift(A));
    if(i, return( order[i]+B*j ));
    A = A * gs;
    );
  return([]);
}

Méthode \(\rho\) de Pollard

Pour éviter le stockage de la méthode Baby-step Giant-step, on peut adapter la méthode \(\rho\) au logarithme discret, voir TP.

Décomposition de Pohlig-Hellman

Dès que l’ordre du groupe n’est pas premier, on peut décomposer un problème de logarithme de la manière suivante

Lemme

Soit \(G=\langle g\rangle\) un groupe d’ordre \(n=dm\). Alors pour tout \(A=g^a\) dans \(G\), on a

\[a \equiv \Log_{g^d}(A^d)\bmod m.\]

De plus, si l’on a calculé \(a_0=\Log_{g^d}(A^d)\in\Z/m\Z\) et que l’on écrit \(a=a_0+ma_1\), alors

\[a_1=\Log_{g^m}(Ag^{-a_0})\in\Z/d\Z.\]

Démonstration

On écrit \(a=a_0+ma_1\) et \(A^d = g^{da_0 + na_1}=(g^d)^{a_0}\).

On va utiliser ce lemme récursivement pour casser un problème de logarithme discret jusqu’à des instances de logarithmes discrets dans des groupes de cardinal premier. Il est commode de décomposer d’abord selon les premiers distincts pour utiliser la première partie du lemme et un relèvement par le lemme chinois.

Lemme chinois sur l’ordre du groupe

Si \(d\mid n\), \(\Z/n\Z\) a un unique sous-groupe d’ordre \(d\) qui est engendré par \(\frac nd\) (et isomorphe à \(\Z/d\Z\)).

Proposition

Soit \(G=\langle g\rangle\) un groupe d’ordre \(n=\prod m_i\) où les \(m_i\) sont deux à deux premiers entre eux.

Alors pour tout \(A\in G\), si l’on pose \(M_i=\frac{n}{m_i}\) on a

\[\Log(A,g) \equiv \Log(A^{M_i},g^{M_i}) \bmod m_i\]

où chacun des logarithmes discrets à droite se situe dans un sous-groupe \(\langle g^{M_i}\rangle\) d’ordre \(m_i\).

Ainsi,

\[\Log(A,g) = \sum_i u_i\frac{n}{m_i} \Log(A^{M_i},g^{M_i})\]

\(u_i=M_i^{-1}\bmod m_i\).

Démonstration

On applique pour chaque \(i\) le lemme en écrivant \(n=m_iM_i\), puis on remonte par le lemme chinois.

Décomposition en base \(p\) sur la composante \(p\)-primaire

Proposition

Soit \(G=\langle g\rangle\) un groupe cyclique d’ordre \(n=p^e\) et \(A\in G\). Alors en décomposant selon la base \(p\)

\[\Log(A,g) = \sum_{i=0}^{e-1} a_i p^i\]

on a

\[a_0 = \Log(A^{p^{e-1}},g^{p^{e-1}})\]

puis pour \(0\leq i\leq e-2\), en posant \(A_i = g^{a_0+\dots a_ip^i}\) on a récursivement

\[a_{i+1} = \Log( (AA_i^{-1} )^{p^{e-i-2}} , g^{p^{e-1}} )\]

Démonstration

On applique le lemme avec \(p^e=p\times p^{e-1}\) en écrivant \(a = a_0+p\tilde a_1\). On a bien la formule pour \(a_0\), et \(\tilde a_1 = \Log((AA_0^{-1})^p,g^p)\) est calculé dans \(\langle g^p\rangle\) d’ordre \(p^{e-1}\).

On réapplique le lemme en posant \(\tilde a_1=a_1+p\tilde a_2\), etc.

Remarquons que tous les logarithmes sont calculés dans le même sous-groupe d’ordre \(p\) \(G_p=\langle g^{p^{e-1}}\rangle\), de sorte que si l’on fait du Baby-steps giant steps on peut conserver la table des pas de bébé d’une fois sur l’autre.

Calcul d’indice

Cette méthode permet de calculer des logarithmes discrets dans \(\F_p^\times\).

On présente cette méthode à travers l’exemple suivant : soit \(p=101\), \(\F_p^\times=\langle g\rangle\) pour \(g=11\). On veut calculer \(\Log(A,g)\) pour \(A=34\).

Première étape

On calcule les premières puissances de \(g\), et on essaie de les décomposer en produit de petits facteurs premiers

\[\begin{aligned} g^2 &= 2^2\times 5 \bmod 101\\ g^3 &= 2\times 3^2\bmod 101\\ g^4 &= -2^2\bmod 101 \end{aligned}\]

Arrivé à ce stade, on peut prendre le logarithme de chaque ligne. En posant \(x_2=\Log(2,g)\), \(x_3=\Log(3,g)\) et \(x_5=\log(5,g)\) on obtient le système (on utilise que \(-1=g^{50}\))

\[\begin{aligned} 2 &= 2x_2+x_5 \bmod 100 \\ 3 &= x_2+2x_3 \bmod 100 \\ 4 &= 50 + 2x_2 \bmod 100 \end{aligned}\]

On a 3 équations et 3 inconnues, d’où les valeurs

\[\begin{aligned} x_2&=-23\\ x_3&=13 \\ x_5&=48 \end{aligned}\]

Deuxième étape

On considère à présent les éléments de la forme \(Ag^k\), et on essaie de les factoriser sur les premiers \(2,3,5\) dont on connaît le logarithme

\[\begin{aligned} Ag &= 71 \bmod 101 \\ Ag^2 &= 2\times 37 \bmod 101 \\ Ag^3 &= 2\times 3 \bmod 101 \end{aligned}\]

Cette dernière relation est la bonne, on en déduit \(\Log(34,g)+3=x_2+x_3\bmod 100\), soit \(\Log(34,g)=-13\).

Algorithme

L’algorithme général est le suivant : on choisit une borne de friabilité \(B\), dans la première étape on collecte les relations qui peuvent s’écrire sous la forme \(g^k=\prod_{q<B} q^{e_q}\). Dès que l’on a plus de relations que de premiers \(q\leq B\), on peut résoudre le système linéaire

\[\bigl( k = \sum e_q \Log(q) \bigr)_k \bmod p-1\]

ce qui donne les logs des petits nombres premiers.

Ensuite, on cherche une relation friable \(Ag^k=\prod_q q^{e_q}\) de laquelle on déduit \(\Log(A)\).

Remarque

Le choix de \(B\) est crucial, trop petit on ne va pas trouver de relations fiables, trop grand il faudra trouver beaucoup de relations.

On peut estimer la probabilité qu’une valeur \(x<p\) soit \(B\) friable, qui est de l’ordre de

\[P(B) = \frac{\log(p)^{n_B}}{n_B!}prod_{q\lt B}\frac{1}{\log(q)}\]

\(n_B\) est le nombre de premiers \(q\leq B\).

Pour obtenir \(n_B\) relations, il faut compter \(O(\frac{n_B}{P(B)}F(B))\) opérations, où \(F(B)\) est le coût d’un test de \(B\)-friabilité. Ensuite on résout le système linéaire en \(O(n_B^3)\) opérations, puis on cherche une dernière relation. On choisit donc \(B\) pour minimiser \(\frac{n_B}{P(B)}F(B)+n_B^3\).