Le problème du logarithme discret : Diffie-Hellman et ElGamal

Quelques résultats de théorie des groupes

On connaît déjà quelques exemples de groupes finis : les $({\mathbb Z}/n{\mathbb Z})^\times$, les éléments inversibles de ${\mathbb Z}/n{\mathbb Z}$, forment un groupe dont le nombre d'éléments est noté $\varphi(n)$ (indicateur d'Euler).

Le théorème de Lagrange

On appelle ordre d'un élément $g$ d'un groupe fini $G$ (noté multiplicativement, d'élement neutre 1), le plus petit entier positif $m$ tel que $g^m=1$.

Il existe : puisque $G$ est fini, la suite $g^k$ des puissances de $g$ contient forcément deux éléments égaux, et si $g^k=g^l$, ($k<l$), alors $g^{l-k}=1$.

On appelle ordre du groupe $G$ son nombre d'éléments.

Ce choix judicieux des définitions permet d'énoncer élégamment le théorème de Lagrange :

"Dans un groupe fini, l'ordre de tout élément est un diviseur de l'ordre du groupe."

En effet, prenons un élément $h$ de $G$, d'ordre $m$ dans un groupe d'ordre $n$. Alors, ou bien $m=n$, et c'est fini, ou bien $m<n$. Dans ce cas, on peut trouver un élément $g_1$ qui n'est pas dans l'ensemble $H$ des puissances de $h$. L'ensemble $g_1H=\{g_1,g_1h,\ldots,g_1h^{m-1}\}$ a lui aussi $m$ éléments distincts, dont aucun n'est dans $H$ : si on avait $g_1h^i = h^j$ alors, $g_1=h^{j-i}$ serait dans $H$. Si on ne peut pas trouver $g_2$ qui ne soit ni dans $H$, ni dans $g_1H$, alors, l'ordre $n$ de $G$ est $n=2m$, et on a fini. Sinon, on recommence avec $g_2$, et ainsi de suite, jusqu'à obtenir $G$ comme réunion disjointe d'ensembles $H,g_1H,\ldots,g_{k-1}H$ ayant tous $m$ éléments, et alors, $n=km$.

Fermat

Si $G=({\mathbb Z}/p{\mathbb Z})^\times$ avec $p$ premier, $n=p-1$, et donc tout élément vérifie $\bar a^{p-1}=\bar 1$.

Euler

Si $G=({\mathbb Z}/n{\mathbb Z})^\times$, d'ordre $\varphi(n)$, tout élément vérifie $\bar a^{\varphi(n)}=\bar 1$.

Calcul de $\varphi(n)$

Si $n=p_1^{m_1}\cdots p_r^{m_r}$ est la décomposition de $n$ en facteurs premiers, le théorème des restes chinois montre que $${\mathbb Z}/n{\mathbb Z} \simeq {\mathbb Z}/p_1^{m_1}{\mathbb Z}\times\cdots\times {\mathbb Z}/p_r^{m_r}{\mathbb Z}$$ les opérations s'effectuant composante à composante sur les $r$-uples. Donc, un élément sera inversible si et seulement si ses résidus modulo tous les $p_i^{m_i}$ le sont.

Il suffit donc de savoir calculer $\varphi(p^m)$. Les éléments non inversibles de ${\mathbb Z}/p^m{\mathbb Z}$ sont les entiers $0\le a<p^m$ qui sont divisibles par $p$, c'est à dire $0,p,2p,3p,\ldots,(p^{m-1}-1)p$. Il y en a donc $p^{m-1}$, et $\varphi(p^m)=p^m-p^{m-1}$.

Le produit de ces nombres peut s'écrire $$\varphi(n)=n\prod_{p|n}\left(1-\frac1p\right)$$ (produit sur les diviseurs premiers de $n$).

On peut exprimer cette formule grace à la fonction de Möbius $\mu$ $$\mu(n) = \begin{cases} 1 & \text{si $n=0$}\\ (-1)^r&\text{si $n=p_1\cdots p_r$ est produit de $r$ nombres premiers distincts}\\ 0 & \text{sinon} \end{cases} $$

En développant le produit, on a $$\varphi(n)=\sum_{d|n}\mu(d)\frac nd.$$

Remarquons que $\varphi(n)$ est aussi le nombre d'élements d'ordre (additif) $n$ dans ${\mathbb Z}/n{\mathbb Z}$. En effet, $kx\equiv 0\mod n\Rightarrow n|k$ si et seulement si $x\wedge n =1$. Pour un diviseur $d$ de $n$, $\varphi(d)$ est donc le nombre d'éléments d'ordre $d$ dans ${\mathbb Z}/n{\mathbb Z}$, et on a $$n = \sum_{d|n}\varphi(d).$$

L'équivalence des deux expressions est un cas particulier de la formule d'inversion de Möbius, qui relie deux fonctions $f$ et $g$ sur les entiers positifs

$$ g(n)= \sum_{d|n}f(d)\quad \Leftrightarrow \quad f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right).$$

Groupes cycliques

Un groupe formé des puissances d'un seul élément est dit cyclique (pourquoi, à votre avis ?).

Par exemple, le groupe additif $({\mathbb Z}/n{\mathbb Z},+)$ est cyclique : il est formé des "puissances additives" de $\bar 1$.

Le théorème de Lagrange entraîne que tout groupe fini d'ordre premier est cyclique.

La propriété suivant est moins évidente : Si $p$ est premier, le groupe multiplicatif $G_p=({\mathbb Z}/p{\mathbb Z})^\times$ est cyclique.

Autrement dit, il existe (au moins) un élément $g$, appelé générateur ou élément primitif dont les puissances modulo $p$ prennent toutes les valeurs de 1 à $p-1$.

Par exemple, $g=3$ est primitif modulo $p=31$ :

In [1]:
p = 31
for i in range(31): print pow(3,i,31),
1 3 9 27 19 26 16 17 20 29 25 13 8 24 10 30 28 22 4 12 5 15 14 11 2 6 18 23 7 21 1

On peut montrer que d'une manière générale, le groupe multiplicatif d'un corps fini est toujours cyclique.

Dans le cas des entiers modulo $p$, on peut le voir ainsi. Soit $d$ un diviseur de $n=p-1$. Les éléments de $G_p$ qui vérifient $x^d=1$ forment un sous-groupe : si $a^d=1$ et $b^d=1$, alors $(ab)^d=a^db^d=1$. De plus, le polynôme $x^d-1$ a exactement $d$ racines distinctes modulo $p$. En effet, d'après Fermat, $$x^{p-1}-\bar 1 = (x-\bar 1)(x-\bar 2)\cdots (x-\overline{p-1})$$ et $x^d-\bar 1$ divise ce polynome : $$x^{p-1}-\bar 1 =(x^d-\bar 1)g(x)$$ avec $g$ de degré $p-1-d$. Comme $g$ ne peut pas avoir plus de racines que son degré, il faut que $x^d-\bar 1$ en ait exactement $d$.

Ses racines sont les éléments de $G_p$ dont les ordres sont des diviseurs $c$ de $d$. Si on note $\psi(c)$ le nombre d'éléments d'ordre $c$, on a donc $$d=\sum_{c|d}\psi(c)$$ pour tout diviseur $d$ de $n$.

Par exemple, pour $p=13$, $p-1=12$ et

  • $1 = \psi(1)$, donc $\psi(1)=1$ (et 1 est l'unique élément d'ordre 1)
  • $2 = \psi(1)+\psi(2)=\psi(2)+1$, donc $\psi(2)=1$ (-1 est l'unique élément d'ordre 2)
  • $3 = \psi(1)+\psi(3)=\psi(3)+1$, donc $\psi(3)=2$
  • $4 = \psi(1)+\psi(2)+\psi(4)=\psi(4)+2$, donc $\psi(4)=2$
  • $6 = \psi(1)+\psi(2)+\psi(3)+\psi(6)=\psi(6)+4$, donc $\psi(6)=2$
  • $12 = \psi(1)+\psi(2)+\psi(3)+\psi(4)+\psi(6)+\psi(12)$ donc $\psi(12)=12-8=4$

Ceci entraîne que $\psi(p-1)=\varphi(p-1)\not=0$, et donc qu'il existe au moins un élément d'ordre $p-1$.

Le logarithme discret

Dans un groupe cyclique $G$ de générateur $g$, le logarithme $x=\log_g y$ de $y$ en base $g$ est le plus petit entier $x\ge 0$ tel que $$ y = g^x$$

Par exemple, pour $p=31$ et $g=3$, le logarithme de $23$ dans $G_p$ est $27$ :

In [2]:
pow(3,27,31)
Out[2]:
23

Il n'existe pas d'algorithme raisonnable pour calculer le logarithme discret dans un grand groupe (sauf dans des cas particuliers).

Si on prend un grand nombre premier $p$ et un générateur $g$ de $G_p$, on ne peut en général pas calculer $x$ à partir de $y=g^x$.

Le protocole de Diffie-Hellman

Cette technique permet de construire une clé de session connue de deux parties A et B sans jamais la transmettre sur le réseau.

On choisit un grand nombre premier $p$, tel que le problème du logarithme discret soit difficile dans $G_p$, et $g$ un générateur d'un sous groupe d'ordre $q$ (grand) du groupe $G_p$.

Le principe est très simple : A tire au hasard un entier $a$ et B tire au hasard un entier $b$ (inférieurs à $q$).

A envoie à B le nombre $g^a$, B envoie à A le nombre $g^b$ . Ainsi, A et B peuvent tous deux calculer $K=g^{ab}$, mais un adversaire qui intercepterait la communication ne pourrait pas le faire. A et B utilisent ensuite $K$ comme clé de session.

Le protocole utilisé par ssh est un peu plus compliqué. Les protagonistes sont le serveur S et le client C.

  • C tire un nombre aléatoire $x < q$ et envoie $e = g^x \mod p$ à S
  • S tire un nombre aléatoire $y < q$ et calcule $f = g^y \mod p$.
  • S reçoit $e$ et calcule $K = e^y \mod p$, puis un hachage $$H = {\rm hash}(V_C || V_S || I_C || I_S || K_S || e || f || K)$$ où $V_C$ et $V_S$ sont les chaînes d'identification du client et du serveur, respectivement. $K_S$ est la clé publique du serveur, et $I_C$ et $I_S$ sont des messages qui ont été échangés avant cette phase du protocole. S signe ensuite $H$ (signature $s$) et envoie $(K_S || f || s)$ à C.
  • C vérifie que $K_S$ est bien la clé publique de S (en utilisant des certificats ou une base de donnée locale). Il calcule alors à son tour $K = f^x \mod p$, puis $H$, et enfin vérifie la signature $s$ de $H$.

Il y a plusieurs choix possibles pour la fonction de hachage (par exemple SHA-1).

Les détails se trouvent dans la RFC 4253.

Le cryptosystème d'ElGamal

Les clefs se construisent à partir d'un grand nombre premier $p$ et d'un générateur $g$ d'un grand sous groupe (d'ordre $q$) de $G_p=({\mathbb Z}/p{\mathbb Z})^\times$.

Chaque utilisateur choisit un entier $x$ (sa clef secrète) et publie $y=g^x\mod p$.

Pour chiffrer un message $m$ (représenté par un entier modulo $p$), on tire un entier aléatoire $k$ et on calcule $$(c_1,c_2)=(g^k,m⋅y^k).$$

Le destinataire déchiffre avec sa clef secrète en calculant $$m=\frac{c_2}{c_1^x}.$$

On trouvera plus de détails ici.

Il y a des clefs faibles. Il faut que le problème du logarithme discret soit difficile dans $G_p$.

Ce n'est par exemple pas le cas si $p−1$ est un produit de petits facteurs premiers (l'algorithme de Pohlig-Hellman permet de casser la clef).

Les clefs les plus résistantes sont celles pour lesquelles $p$ est un nombre premier sûr, c'est à dire de la forme $p=2q+1$ avec $q$ premier (on dit alors que $q$ est un nombre premier de Sophie Germain). Ces nombres sont rares, et le calcul des clefs est long. On recommande ensuite de choisir pour $g$ un générateur du sous groupe des carrés, qui est d'ordre $q$ premier, et donc cyclique.

Le problème du logarithme discret est supposé être le plus difficile dans les groupes d'ordre premier.

On peut utiliser d'autres groupes, par exemple les groupes multiplicatifs des autres corps finis ${\mathbb F}_q$ (très utilisés pour la construction de codes correcteurs d'erreurs), ou mieux, les groupes associés aux courbes elliptiques sur les corps finis. Ces derniers systèmes, plus complexes et dépendant de mathématiques très sophistiquées, permettent d'avoir des clefs plus courtes à sécurité équivalente, et sont bien adaptés aux environnements embarqués comme les cartes à puces.

Le schéma de signature

Comme dans la plupart des schémas de signature numérique, un utilisateur signe un document en chiffrant un hachage $h$ avec sa clé secrète, et tout le monde peut alors vérifier la signature au moyen de sa clé publique. De manière précise, pour signer un entier $0\le h<p−1$, on tire au hasard un entier $k$ dans ce même intervalle, premier avec $p−1$, et on calcule $$r=g^k\mod p,$$ puis $$s=(h−xr)k^{−1}\mod p−1.$$ La signature est le couple $(r,s)$.

Pour vérifier une signature avec la clé publique $y$, on vérifie deux conditions \begin{align} (1)&\quad 1\le r<p,\\ (2)&\quad g^h\equiv r^sy^r\mod p. \end{align}

La condition (1) est très importante. Si un programme omet de la vérifier, on peut lui faire accepter de fausses signatures sur n'importe quelle valeur de hachage $h'$ pourvu qu'on connaisse une signature valide. On calcule $u=h'h^{−1}\mod p−1$. Alors, $$g^{h'}\equiv g^{h u} \equiv y^{ru}r^{su} \mod p$$ et on peut prendre $s'=s^u\mod p−1$. Ensuite, par le théorème des restes chinois, on peut trouver $r'$ tel que $r'\equiv r^u\mod p−1$ et $r'\equiv r \mod p$. Si la condition (1) n'est pas testée, $(r',s')$ sera accepté comme une signature valide de $h'$.

Un autre problème est lié à la présence de canaux subliminaux. Si l'entier $k$ n'est pas choisi de manière totalement aléatoire, il peut servir à dévoiler des informations sur le signataire (par exemple sa clé secrète) à l'insu de celui-ci.

Un bon exemple, où un patch de deux lignes sur le code source de GPG suffit à compromettre le système, est décrit ici.

ElGamal en Python

Voici un exemple minimal avec pyCrypto (la documentation est essentiellement inexistante, il faut regarder le code source). En particulier il faut un générateur de hasard (randfunc, prise dans les sources). On demande une clé de 1024 bits (le nombre premier $p$). Les autres attributs sont un générateur $g$ d'un grand sous-groupe (taille non précisée), l'exposant secret $x$, et $y=g^x$. On peut chiffrer, déchiffrer, signer, et vérifier une signature.

In [1]:
from Crypto.PublicKey import ElGamal
from Crypto import Random

randfunc = Random.new().read

EG = ElGamal.generate(1024,randfunc) # C'est long ...
In [2]:
print "p = ", EG.p
print "g = ", EG.g
print "x = ", EG.x
print "y = ", EG.y
p =  133411060554765281893574219238826460323777167603785645014278136342221585128167259751013553149708520722045654601400623071788471647082014969264180269266875390063076001658158118031204943062025365142431657088824020701300453690852882397540300360385823780206237292961041347283987673871023647032372193043462681008847
g =  48586369936169103586294809315156744459826261816868529844636467564361344595787342991168775000429772281470402412067148890761909966252474891479748704361539294853838483085202009876144076604499195321965301697878069656223581778916646691494283266305647635489559041938262392791955070705446241413808989716642954276009
x =  126777616757080434242770928750187232005390319013291197473159373015536617815694682689860087294157237472304991405112726115069602625543699453852209288284412334658286735502850267431820936069731609071048160675493685978162234689379884430597864969607914030547045382052894794662101020294419701802074990956467360060151
y =  132080397124465808997141153497115904125483861155806756481508475557410579198178757425531949874323637477627697157684390984938350597262639899290167846309470998659966585178642656579068696022074464382458717158944492364843007733123099636660098062192283598577411439021158138546382022851856279926063493376932657970784

In [3]:
# g n'est pas toujours primitif dans cette version ...

M ='Le cheval de mon cousin ne mange du foin que le dimanche.'
C = EG.encrypt(M, 4567)
print C

D = EG.decrypt(C)
print D

s = EG.sign(M, 4567)
print s
v = EG.verify(M,s)
print v
('\x92\xf7\x1a\x03\x8b\xad\xdf4:\xf2>\xc4i\xc0\x19\xf74\x95\x82B\xee\xb3Y\xb4\x03\x93\x82\xcca\xc3\xecQ4[\xf6\xd1\x1a]\xbc\xf2c\xf5\xeb\xd6\xb2C\x03\x8e/?\xce\x8d\xc9\xb4\x8a>X-k\x81w\x8b\xfe\xf1a\xc3\x9ewj4\x83\xd5+\x1ay$JD\xcb\xe1b\xa5\\\xa0!\xaf^\xb5\xb09\x08\xfe\xd3\x7f\x9a\xcfE"B\x10\x10h\xb3)`\xee$g\x1f%\xa4p@\xebV\x85\x83+\xb6\x98\xe1\x1d\xfc\\\xec7r\x9f', '\x16\x9e\xfd\xe2\x82\xae\x1f\x81\xa0VLY\xd38Q\xb1\x96\xe4\xc6up\x18\xb0\x92\x84\xd0WSs\xe3\x9c0\x12\x81W\xfd5-\xc0\xaaT\xf0N\xaaA\x8b\xcbk\xb1\xbd>=;;\x8df\x9f!\rnYJD\xba\x9b2\xdbD\xc4\xc2\xfd\xd6\xc7a\xbf{\x9a>\xff[\x16Rd\xb6o@\xdb\xb5\x11 \x98\x0c\xf6\x9c\xdaO\xd94\xa4\xcc\xc7\x90\x9c\x19\xb0\xf4I\xea0l\xf7\xdc\xa2\x16\'\xc5}\x1bC#\n\xc6\xec\x17\x99"\xba\xc7')
Le cheval de mon cousin ne mange du foin que le dimanche.
(103202501660755198672070301841285510103315314984277618896942966849771871172453969005994193223915927905070240281319606352528764751128025237390453937475122324718492697427177439546827021913385378747642090048121356609331353649432578790773978235267031530302824679704367361066282389409448322006817663100978946601631L, 74238924163735502758493905163831994794991148939903686962526126408521994037127139793819474225762638753358979825748388283116522095058252439337590968638974114196935683363368832073985992353786674525489143863037835438311199957576630531091521207165221126773828791417450348324348990002309346330425912044739709239995L)
1

Avec un exemple réel sous les yeux, on peut maintenant envisager de coder un ElGamal à partir de zéro (ou presque). Un problème à résoudre est celui des clés faibles. On utilisera donc des nombres premiers sûrs. Pour les construire, on tire un entier aléatoire $u$ dans l'intervalle voulu. S'il est pair, on l'incrémente. Ensuite on teste si $u$ ou $2u+1$ est divisible par un petit nombre premier. Si c'est le cas, on l'incrémente de $2$. Sinon, on fait un seul test de Fermat en base 2 sur $2u+1$. En cas de succès, on fait un test de Miller-Rabin sur $u$

Voici une ébauche de programme (utilisant encore quelques fonctions du ent.py de W. Stein) :

In [4]:
from random import randint
from ent import *

# On utilise un p sûr (p=2q+1, q premier)
# q est un premier de Sophie Germain
# On ne doit pas avoir q = (r-1)/2 mod r (r petit permier)
# sinon p serait divisible par r
# La borne 2**16 est recommandée par Wiener
small_primes = primes(2**16)[1:]

def small_test(u):
    for v in small_primes:
        a = u%v
        if a == 0 or a == (v-1)/2: return False
    return True

def gen_safe_prime(nbits):
    u = randint(2**(nbits-2), 2**(nbits-1)-2**(nbits/2))
    if u%2 == 0:
        u +=1
    while not small_test(u):
        u+=2
    while u < 2**(nbits-1):
        if powermod(2,u-1,u) == 1:
            p = 2*u+1
            if powermod(2,p-1,p)==1:# si u est SG, suffit
                if miller_rabin(u):
                    print "OK"
                    return p
        u += 2
        while not small_test(u):
            u += 2
    return None
In [5]:
p = gen_safe_prime(512)
p
OK

Out[5]:
10646615282562165237128792724322548632859138040849103414964758704319629079992621866437860923489769360932184767331312560313319414811643745360009008294938947L
In [6]:
miller_rabin((p-1)/2)
Out[6]:
True
In [7]:
# Pas plus de 1024 bits en un temps raisonnable ...
# On prend un générateur du sous-groupe des
# carrés, qui est d'ordre q premier

def gen_key(nbits):
    p = gen_safe_prime(nbits)
    q = (p-1)/2
    g = randint(2,p-1)
    g = powermod(g,2,p)
    x = randint(2,q-1)
    y = powermod(g,x,p)
    return ((p,q,g,y),x)


def encrypt(m, pub_key):
    (p,q,g,y) = pub_key
    k = randint(1,q-1)
    u = powermod(g,k,p); v = m*powermod(y,k,p)
    return (u,v)

def decrypt(c,x,p):
    u,v = c
    w = inversemod(u,p)
    return powermod(w,x,p)*v % p
In [8]:
K = gen_key(1024)
print "Key: "
print K
m = randint(2**255,2**256)
print m
c = encrypt(m, K[0])
print c
d = decrypt(c, K[1], K[0][0])
print d
OK
Key: 
((149488799938523964877659807771366430793566730145918043445116112285436748704870183575695847663459394081756880212161723249731462266307374134009176867102518612987756762306753995917042867755315445778156145119991682583822783686723150047444169447579031328435493690120246704765829110815866961214317392537946015424347L, 74744399969261982438829903885683215396783365072959021722558056142718374352435091787847923831729697040878440106080861624865731133153687067004588433551259306493878381153376997958521433877657722889078072559995841291911391843361575023722084723789515664217746845060123352382914555407933480607158696268973007712173L, 40855588599842909634297070379525971551099786608268082204879490800880300814638969152041610646427168371957300118217145211415946286246062102065679397091723987608774761929602485443689162288328642395982420601146150954076580352415887105522011816450596104949436797624788828934525753400320792349239952650814477173617L, 95013780633561310556629394106649667835195973589112883162360675351040872310390991297702620670332965205597462450481206939926131899496272852907747623797996189248850943100285701773065006264545296928600278809455584444618722819248168237279424422138787873450822557679095506247333066905941323062290202608275039178438L), 7906340688888992344131506995677834531599699336221671190809158958800190961249360809216193716114224071633837034578995990888513061058560820926370748006015111647945641042051512814838631833459169823073120693400234636283064782180598966760283629541243950380152848155762697763016628567344986768171344072316775063761L)
102390402899506269693611135741475504069781802923282961312644431095023943150464
(82812110020228934995974590493975032837894004751936549832495258838762485576706916775911240279944391968382382308686270578259725841885143222753451162847737709872910832333059102149585003832227869052471581545470707635222646983608950537169324089984700112489500130513461244748934312396374651686268205381961259448074L, 4534358214495428155194564017534483258720989209821811296017033241192785773797675910087959240004014678162109809226095502053946886358398026715690183356036335189494437024459169078244854026338528668485033369266183322644348593898259922618228756774576586433108241866993614478982071221411052414759419248877252762435095064111755390455524974958442866528411028942551640199455723635664683044486656L)
102390402899506269693611135741475504069781802923282961312644431095023943150464

L'algorithme de Pohlig-Hellman et l'attaque de Bleichenbacher

C'est dans les groupes d'ordre premier que le problème du logarithme discret est le plus difficile. Au contraire, si $p-1$ n'a que de petits facteurs premiers, il existe des algorithmes efficaces, comme l'algorithme de Pohlig-Hellman.

Le principe est le suivant. Pour calculer le logarithme discret $x$ de $h=g^x$ dans un groupe cyclique d'ordre $n$ et de générateur $g$, si $$n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$ n'a que de petits facteurs premiers $p_i$, on calcule les éléments

  • $g_i = g^{n/{p_i^{e_i}}}$, qui est donc d'ordre $p_i^{e_i}$ par le théorème de Lagrange
  • $h_i = h^{n/{p_i^{e_i}}}$, qui appartient au sous-groupe cyclique $\langle g_i\rangle$ engendré par $g_i$
  • $x_i = \log_{g_i} h_i$, problème plus facile qu'on peut résoudre par diverses méthodes

On a $x\equiv x_i \mod p_i^{e_i}$, et on reconstitue $x$ par le théorème des restes chinois.

Baby step - giant step

Pour calculer les $x_i$, on peut utiliser l'algorithme baby step - giant step, qui est un compromis temps-mémoire pour la recherche exhaustive.

Étant donné un groupe cyclique $G$ d'ordre $n$, un générateur $g$ et $h=g^x$, on cherche $x$ sous la forme $x=im+j$ où $m=\lceil\sqrt{n}\rceil$, $0\le i,j<m$.

On précalcule les $g^j$ (dans une table de hachage de clefs $j$), et $g^{-m}$. Alors, $h(g^{-m})^i = g^j$

On initialise $u=h$ et pour $j$ de 0 à $m-1$, on teste si $u=g^j$. Si oui, on renvoie $im+j$, sinon on fait $u:=ug^{-m}$ et on recommence.

In [9]:
from ent import *
from math import ceil, floor, sqrt

def bsgs(h,g,n,mulf,powf):

    m = int(ceil(sqrt(n)))
    d = {j:powf(g,j) for j in range(m)}
    a = powf(g,-m)
    u = h
    for i in range(m):
        for j in range(m):
            if u == d[j]: return i*m+j
        u = mulf(u,a)
    
# Exemple    
def mulf(x,y): return (x*y)% 103
def powf(x,k):
    if k<0: 
        x = inversemod(x,103)
        k = -k
    return powermod(x,k,103)
    
for i in range(103): print pow(2,i,103),
1 2 4 8 16 32 64 25 50 100 97 91 79 55 7 14 28 56 9 18 36 72 41 82 61 19 38 76 49 98 93 83 63 23 46 92 81 59 15 30 60 17 34 68 33 66 29 58 13 26 52 1 2 4 8 16 32 64 25 50 100 97 91 79 55 7 14 28 56 9 18 36 72 41 82 61 19 38 76 49 98 93 83 63 23 46 92 81 59 15 30 60 17 34 68 33 66 29 58 13 26 52 1

In [10]:
h = pow(2,42,103); h
Out[10]:
34
In [11]:
bsgs(34,2,102,mulf,powf)
Out[11]:
42
In [12]:
p = gen_safe_prime(20); p
OK

Out[12]:
687299
In [13]:
q=(p-1)/2; q
Out[13]:
343649
In [14]:
def mulf(x,y): return (x*y)% p
def powf(x,k):
    if k<0: 
        x = inversemod(x,p)
        k = -k
    return powermod(x,k,p)
In [15]:
g = 4
h = pow(g,111111,p); h
Out[15]:
36500
In [16]:
bsgs(h,g,q,mulf,powf)
Out[16]:
111111

Pohlig-Hellman version 1

On utilise baby step-giant step pour trouver les $x_i$. Ce n'est pas efficace si les $e_i>1$.

In [17]:
def solve_chinese(yy,mm):
    assert len(yy) == len(mm), "Arguments must have same length."
    k = len(yy); m = reduce(lambda x,y:x*y, mm); x=0
    for i in range(k):
        u = reduce(lambda x,y:x*y, [mm[j] for j in range(k) if j!=i])
        v = inversemod(u,mm[i])
        x = (x + yy[i]*v*u) % m
    return x


def pohlig_hellman1(h,g,p):
    n = p-1
    ff = factor(n)
    r = len(ff)
    
    def mulf(x,y): 
        return (x*y)% p
    
    def powf(x,k):
        if k<0: 
            x = inversemod(x,p)
            k = -k
        return powermod(x,k,p)
    
    mm = [pow(ff[i][0],ff[i][1]) for i in range(r)]
    print 'mm: ',mm
    gg = [pow(g,n/mm[i],p) for i in range(r)]
    print 'gg: ',gg
    hh = [pow(h,n/mm[i],p) for i in range(r)]
    
    xx = [bsgs(hh[i],gg[i],mm[i],mulf,powf)for i in range(r)]
    print 'hh: ',hh
    print 'xx: ',xx
   
    return solve_chinese(xx,mm)
    
In [18]:
pohlig_hellman1(9451,5,10007)
mm:  [2, 5003]
gg:  [10006, 25]
hh:  [10006, 8926]
xx:  [1, 1054]

Out[18]:
6057
In [19]:
pow(5,6057,10007)
Out[19]:
9451
In [20]:
p = 12214595251480930577
g = 53
h = powermod(g,123456789,p)
print g,h
from time import time
a = time()
print "Computing ..."
print pohlig_hellman1(h,g,p)
print time()-a
53 10281500672050559975
Computing ...
mm:  [16, 109, 3307, 186161, 11376527L]
gg:  [3977706731622236597L, 10794351375895673062L, 9010175095136500157L, 3035679229265288799L, 6400025164451908865L]
hh:  [10837460501653388979L, 1223524356504489457L, 5415912014413668711L, 7779342733905718077L, 9933792936822973415L]
xx:  [5, 10, 3172, 32046, 9691519]
123456789
1.49537801743

Pour les groupes cycliques d'ordre $n=p^e$ avec $e>1$, baby step - giant step n'est pas efficace. On peut se ramener à ne l'appliquer qu'à des groupes d'ordre premier, en calculant successivement les chiffres $d_0,\ldots d_{e-1}$ de $x$ en base $p$. C'est en fait le point essentiel de Pohlig-Hellman.

In [21]:
def pohlig_hellman(h,g,p):
    ff = factor(p-1)
    mm = [q**e for q,e in ff]
    print mm
    xx = []
    u = inversemod(g,p)
    for q,e in ff:
        d = {i:pow(g,((p-1)*i)/q,p) for i in range(q)} # il faudrait remplacer cette étape par un BSGS
        a = 0
        w = h
        for j in range(e):
            v = pow(w,(p-1)/q**(j+1),p)
            for i in d:
                if d[i]==v:
                    a += i*pow(q,j)
                    w = (pow(u,i*q**j,p)*w) % p
                    break
        xx.append(a)
    print xx
    return solve_chinese(xx,mm)
                    
In [22]:
p = 1311606765290211317831
factor(p-1)
Out[22]:
[(2, 1), (5, 1), (7, 1), (257, 4), (65537, 2)]
In [23]:
g = 17
h = pow(g,1234567,p); h
Out[23]:
188315544505038127198L
In [24]:
pohlig_hellman(h,g,p)
[2, 5, 7, 4362470401, 4295098369]
[1, 2, 5, 1234567, 1234567]

Out[24]:
1234567L
In [25]:
pohlig_hellman1(h,g,p)
mm:  [2, 5, 7, 4362470401, 4295098369]
gg:  [1311606765290211317830L, 9219817919881129457L, 785880390810345683336L, 1074196675878546094261L, 1052424187774988976045L]
hh:  [1311606765290211317830L, 140454899200855728206L, 839425818041000397659L, 1276251671872571019226L, 1137709246113480872298L]
xx:  [1, 2, 5, 1234567, 1234567]

Out[25]:
1234567L

L'attaque de Bleichenbacher

On pourra partir des petits programme de démonstration ci-dessus pour tester l'attaque de Bleichenbacher sur le schéma de signature d'ElGamal (décrite dans la section 3 de cet article). Elle fonctionne quand $p−1=bw$ où $b$ n'a que de petits facteurs premiers (on dit qu'il est lisse, smooth en anglais). On peut alors trouver $z$ tel que $g^{wz}\equiv y^w\mod p$ par l'algorithme de Pohlig-Hellman. On peut ensuite trouver $k$ et $r$ tels que $r\equiv g^k\equiv cw\mod p$ pour un $c$ entre 0 et $b$. On peut ensuite,sans connaître la clé secrète, forger des signatures sur tout hachage $h$ vérifiant $h\equiv xr\mod k\wedge(p−1)$. En particulier, si $g$ est lisse et divise $p−1$, on peut signer tout $h$ si $p\equiv 1\mod 4$ et la moitié des hachages possibles sinon.

In []: