Logarithme discret dans Z/pZ*

Pierrick Gaudry

gaudry@lix.polytechnique.fr

La cryptographie à clef publique est en plein essor depuis quelques années. Certains protocoles utilisés sont basés sur des opérations dans un groupe abélien fini (l'exemple le plus célèbre est le protocole d'échange de clef de Diffie-Hellman). La sécurité de tels protocoles est basée sur le fait que dans les groupes qu'on utilise, le problème du logarithme discret est difficile à résoudre en temps raisonnable (nous définissons ce problème ci-dessous). Ainsi les groupes doivent être choisis suffisamment grands pour qu'une recherche exhaustive ne permette pas de trouver le logarithme discret.

Nous proposons ici d'implanter deux algorithmes qui sont plus rapides qu'une approche naïve pour calculer des logarithmes discrets dans le groupe multiplicatif de Z/pZ. Ces algorithmes démontrent que les groupes utilisés en cryptographie doivent être deux fois plus grands que ce que l'on pourrait croire en première approche pour garantir une sécurité suffisante.

Ces deux algorithmes ayant la même complexité théorique, il est naturel de les implanter tous les deux afin de comparer leur temps réel d'exécution.

1   Le problème du logarithme discret

Soit p un nombre premier, et soit g un élément du groupe multiplicatif de Z/pZ. On note n l'ordre de g. Comme le groupe multiplicatif est d'ordre p-1, on aura toujours n|p-1. En général, on choisira g de telle manière que n est premier.

Pour tout entier l, l'élément h=glmod p peut être calculé rapidement. En effet, au lieu d'effectuer l multiplications, on peut remarquer que si l est pair, gl=(gl/2)2, et sinon, gl=g(g(l-1)/2)2. On est donc ramené au même problème, mais pour une valeur de l deux fois plus petite. On se convainc facilement qu'une implantation récursive résoud le problème initial en O(log l) opérations.

Réciproquement, on suppose que l'on se donne un élément h dans le sous-groupe engendré par g. Le problème du logarithme discret est le suivant: retrouver un entier l entre 0 et n-1 tel que
h=g
l
 
mod p.

Il n'y a pas d'algorithme connu qui résolve ce problème en temps polynomial en log n. La méthode naïve qui consiste à essayer successivement toutes les valeurs de l conduit à une complexité de O(n) multiplications. Les algorithmes proposés ici permettent d'abaisser la complexité à O((n)1/2) opérations.

2   Pas de bébé, pas de géant

Le principe général de l'algorithme ``Baby steps, giant steps'', dû à Shanks, est le suivant: on se fixe un entier w plus petit que n, et l'on écrit
l=l0+wl1,
où 0£ l0<w et 0£ l1< n/w. La relation h=gl que l'on cherche se récrit donc
g
l0
 
=h.g
-wl1
 
.     (1)
L'algorithme consiste à précalculer et à stocker tous les gl0 pour l0 allant de 1 à w (ce sont les pas de bébés). Puis on calcule succéssivement tous les g-w l1 (ce sont les pas de géant), en vérifiant à chaque étape si l'équation 2 n'est pas vérifiée pour l1=l1, et pour un l0=l0, grâce à une recherche dans la table des pas de bébé.

Pour une valeur de l1 inférieure à n/w, l'équation sera effectivement vérifiée, et le logarithme discret en découlera.

Le coût de cet algorithme est O(w) opérations pour la première phase, et O(n/w) pour la seconde. En choisissant w de l'ordre de (n)1/2, on obtient la complexité annoncée O((n)1/2).

3   Méthode Rho

Cet algorithme est dû à Pollard. Il consiste à se promener au hasard dans le groupe, jusqu'à ce que l'on retombe sur un élément qu'on a déjà rencontré. On garde suffisamment d'informations lors de cette marche aléatoire afin de retrouver le logarithme discret lorsque cela se produit.


Fonction pseudo-aléatoire. Soit r un entier inférieur à 1000. On précalcule r ``multiplicateurs'' de la manière suivante: on prend 2r entiers ni et µi au hasard dans [0,n-1], et on calcule
Ti=g
ni
 
h
µi
 
, iÎ [0,r-1].
Ensuite à chaque élément x de Z/pZ*, on associe de manière unique un entier entre 0 et r-1 que l'on note H(x).

On définit alors une fonction pseudo-aléatoire f par
f(x)=xT
 
H(x)
.

Algorithme. On part d'un élément x0=ga0 hb0 construit en prenant a0 et b0 au hasard. Ensuite on calcule les itérés successifs par la fonction f, tout en gardant une expression de xi en termes de g et h:
xi+1:=f(xi)=xiT
 
H(xi)
=g
ai+1
 
h
bi+1
 
.
Les valeurs de ai+1 et bi+1 peuvent être calculées facilement à partir de leurs valeurs à l'étape précédente, et de plus peuvent être réduites à chaque étape modulo n (l'ordre de g).

Quand on trouve une collision, c'est-à-dire deux valeurs i et j pour lesquelles xi=xj, alors on peut en déduire le logarithme discret
l = -
ai-aj

bi-bj
mod n.
On peut montrer qu'asymptotiquement, le nombre d'itérations est en moyenne O((n)1/2). Cette analyse suppose que la fonction f est vraiment aléatoire, ce qui est heuristiquement le cas pour r assez grand.

La figure suivante illustre le déroulement de l'algorithme, et si l'on incline vers le bas le manche de la poele à frire, on comprend pourquoi cette méthode s'appelle Rho.

Extension possible. Afin de réduire le stockage, Quisquater et Delascaille ont introduit la notion de points distingués. Cela consiste à ne stocker en mémoire que les éléments xi possédant une certaine propriété arbitraire qui se produit avec une probabilité 1/t. Ainsi on réduit la taille mémoire nécessaire d'un facteur t, au prix de O(t) itérations supplémentaires. La propriété en question peut être ``avoir ses 5 premiers bits à 0'', ou ``avoir au moins 13 bits à 1'', et tout ce qu'on peut imaginer qui se calcule rapidement...

Dans la figure ci-dessous, les gros points représentent les éléments distingués. On ne détecte pas la collision xi=xj, mais dès qu'on atteint le premier point distingué du cycle, on a gagné.


4   Travail demandé

On demande d'implanter ces deux algorithmes en java (ou dans un autre langage de votre choix). Pour pouvoir réellement comparer les temps de calcul, on sera amené à faire des tests sur des exemples pour lesquels les entiers dépassent la taille d'un int. La classe BigInteger permet de travailler avec des entiers de taille arbitraire, et fournit toutes les opérations nécessaires à l'implantation.


Pas de bébé, pas de géant. Une implantation respectant la complexité annoncée nécessite de bien choisir la structure de donnée utilisée.

Une première optimisation consistera à réduire au maximum la taille mémoire.

D'autre part, il faut bien équilibrer les temps de calculs des deux phases de l'algorithme afin de minimiser le coût global. Ce réglage, qui dépend grandement de l'implantation et notamment de la structure choisie, fait partie du travail demandé.


Méthode Rho. Là encore, il faut adopter une bonne méthode pour stocker les données, de manière à ne pas perdre de temps, et à ne pas gaspiller d'espace mémoire.

Cet algorithme n'étant pas déterministe, le temps de calcul n'est pas le même à chaque exécution. On pourra faire des statistiques sur le nombre moyen d'itérations en fonction de n. La valeur de r influe aussi sur les temps de calcul. On recommande de tester plusieurs valeurs différentes (cette valeur doit rester faible, de manière à ce que l'initialisation de la marche aléatoire n'influe pas sur le temps de calcul).


Exemples pour tester votre programme. Il est conseillé de choisir des exemples pour lesquels n (l'ordre de g) est premier. D'autre part, il est plus intéressant de travailler dans un sous-groupe aussi grand que possible, donc on choisira des nombres premiers p pour lesquels (p-1)/2 est premier. Le tableau suivant donne quelques problèmes à résoudre.

p n g h
107 53 23 3
10007 5003 182 9449
1000667 500333 872052 588654
100000127 50000063 78277094 99766437
10000000259 5000000129 5430827534 2090591416
1000000000547 500000000273 654438348730 213628475138



Le jour de la soutenance, d'autres exercices seront proposés par le jury.


This document was translated from LATEX by HEVEA.