Silver–Pohlig–Hellman algorithm

Imaginez une horloge sur laquelle avancer de 2 en 2 finit toujours par revenir au départ. On connaît le point d’arrivée, mais pas le nombre de pas effectués : retrouver ce nombre est un logarithme discret. L’algorithme de Silver-Pohlig-Hellman découpe cette recherche selon les petits facteurs premiers du nombre de positions. Il résout ces recherches réduites, puis assemble leurs réponses comme les pièces compatibles d’un même numéro de tour.

L’algorithme de Silver-Pohlig-Hellman résout un logarithme discret dans un groupe cyclique fini. Soit un groupe engendré par un élément g, d’ordre n, et un élément h appartenant à ce groupe. Le problème consiste à trouver l’entier x, déterminé modulo n, tel que $g^x=hg^x=h$.

On factorise l’ordre en puissances de nombres premiers : $n={\prod }_i{p}_i^{e_i}n=\backslash prod\_i\; p\_i^\{e\_i\}$. Pour chaque facteur $p_i^{e_i}p\_i^\{e\_i\}$, des exponentiations dans le groupe ramènent le calcul de x modulo cette puissance à une suite de logarithmes discrets dans un sous-groupe d’ordre premier p. Les chiffres de x en base p sont ainsi déterminés successivement.

Les résidus obtenus modulo les puissances premières sont enfin réunis par le théorème des restes chinois. La méthode est particulièrement efficace lorsque n est friable, c’est-à-dire lorsque son plus grand facteur premier est petit. Son coût dépend surtout de ce plus grand facteur, et non du seul nombre d’éléments du groupe.

Dans un groupe cyclique fini engendré par g, on connaît l’ordre n, sa factorisation $n={\prod }_i{p}_i^{e_i}n=\backslash prod\_i\; p\_i^\{e\_i\}$ et un élément h. Pour trouver x tel que $g^x=hg^x=h$, on calcule séparément x modulo chaque puissance $p_i^{e_i}p\_i^\{e\_i\}$, chiffre après chiffre en base p. On arrête cette levée après e chiffres pour le facteur $p^{e}p^e$. Le théorème des restes chinois fournit alors l’unique classe de x modulo n compatible avec tous ces résidus.

La méthode demande un groupe cyclique fini, un générateur g, l’ordre n de ce générateur et la factorisation de n. L’élément cible h doit appartenir au sous-groupe engendré par g ; alors le logarithme existe et sa classe modulo n est unique. Son intérêt pratique est maximal lorsque tous les facteurs premiers de n sont assez petits pour que les sous-problèmes soient abordables.

Si l’ordre contient un très grand facteur premier, la décomposition laisse un logarithme discret presque aussi difficile dans le sous-groupe correspondant. Silver-Pohlig-Hellman ne supprime pas cet obstacle : il faut alors employer, pour ce sous-problème, une méthode générique comme pas de bébé-pas de géant ou rho de Pollard. Si h n’appartient pas au sous-groupe de g, aucun exposant recherché n’existe.

Dans le groupe multiplicatif modulo 29, l’élément g = 2 est d’ordre n = 28 = 4 × 7. Pour la cible h = 18, on cherche l’exposant x tel que 2^x ≡ 18 (modulo 29).

1. Pour 4 = 2², on cherche les deux chiffres binaires de x. Puisque 18¹⁴ ≡ −1 ≡ 2¹⁴ (modulo 29), le premier vaut 1. Ensuite, (18 × 2⁻¹)⁷ ≡ 9⁷ ≡ −1 : le second vaut 1. Ainsi x ≡ 1 + 2 = 3 (modulo 4).

2. Pour le facteur 7, on élève à la puissance 28 ÷ 7 = 4. La base réduite vaut 2⁴ ≡ 16 et 18⁴ ≡ 25. Comme 16⁴ ≡ 25 (modulo 29), x ≡ 4 (modulo 7).

3. Il reste à résoudre simultanément les deux congruences :

Le théorème des restes chinois donne x ≡ 11 (modulo 28). Contrôle : 2¹¹ = 2 048 = 29 × 70 + 18, donc 2¹¹ ≡ 18 (modulo 29). La décomposition 28 = 4 × 7 fait apparaître les deux branches et leur réunion.

En cryptanalyse, on commence par factoriser l’ordre du sous-groupe utilisé. S’il est friable, Silver-Pohlig-Hellman transforme une attaque globale en petits calculs et révèle que le choix du groupe est fragile.

Pour concevoir un système à logarithme discret, on vérifie au contraire que le sous-groupe choisi possède un grand facteur premier. Un ordre seulement élevé ne suffit pas : une factorisation faite de petits nombres premiers rend précisément cette méthode avantageuse.

Dans un calcul effectif, chaque logarithme d’ordre premier peut être confié à une méthode adaptée. Une table exhaustive convient aux très petits facteurs ; pas de bébé-pas de géant ou rho de Pollard devient préférable lorsque l’un d’eux grossit.

Avec l’algorithme de Diffie-Hellman. Diffie-Hellman est un protocole d’accord de clé fondé sur la difficulté du logarithme discret ; Silver-Pohlig-Hellman est un algorithme qui cherche ce logarithme. Si deux participants établissent un secret, il s’agit du protocole ; si l’on retrouve l’exposant secret à partir de g et h, il s’agit du calcul étudié ici.

Avec le théorème des restes chinois. Ce théorème recombine des congruences dont les modules sont premiers entre eux, mais il ne calcule pas les résidus de l’exposant. Dans l’exemple, Silver-Pohlig-Hellman produit x ≡ 3 modulo 4 et x ≡ 4 modulo 7 ; le théorème les réunit en x ≡ 11 modulo 28.

Avec l’algorithme baby-step giant-step. Cette méthode générique cherche un logarithme discret sans exiger un ordre friable. Silver-Pohlig-Hellman exploite d’abord la factorisation de l’ordre et peut ensuite utiliser baby-step giant-step à l’intérieur d’un sous-problème d’ordre premier.

Grand facteur premier. Si l’ordre vaut n et possède un facteur premier q presque aussi grand que n, la branche d’ordre q domine le coût. Le symptôme est une factorisation qui ne réduit pas réellement le plus gros sous-problème ; il faut alors traiter cette branche avec un algorithme générique, sans annoncer un gain dû à la friabilité.

Mauvais ordre. Employer l’ordre du groupe ambiant à la place de l’ordre exact de g peut produire des congruences redondantes ou incohérentes. Il faut calculer ou vérifier l’ordre du sous-groupe engendré par g avant la décomposition. Dans l’exemple, l’ordre utile est exactement 28.

Cible hors du sous-groupe. Si h n’est pas une puissance de g, le logarithme n’existe pas. Une impossibilité dans une branche ne doit pas être forcée en un résidu : on vérifie l’appartenance au sous-groupe et l’on conclut à l’absence de solution.

Facteurs premiers et puissances premières. Connaître seulement x modulo p ne suffit pas lorsque l’ordre contient $p^{e}p^e$ avec e supérieur à 1. Il faut lever successivement les e chiffres en base p ; pour le facteur 4 de l’exemple, deux chiffres binaires sont nécessaires.

Le groupe cyclique précise pourquoi un générateur code chaque élément par un exposant unique modulo son ordre.

Le théorème des restes chinois montre pourquoi les résidus obtenus pour des puissances premières se recombinent en une seule classe modulo n.