Sujet 17: Le problème du logarithme discret et attaques II
Rédacteur: Rana Alshweiki
A traiter
- Attaque \( \rho \) de Pollard
- Attaque de Pohlig-Hellman
Attaque \( \rho \) de Pollard
Soit \(G\) un groupe fini additif et d'ordre N . Soient \(P,Q \in G\).On va chercher \(k\) tel que \(Q=kP\).
Préparation:
Soit \(p_0\in G\) .Soit \(f:G \to G\) une fonction abstrait. Pour la suite \(p_0,p_1,\dots \) qu'est définit par \(f(p_i)=p_{i+1}\) ; \(\exists i_0 \leq j_0\) des indices tels que \(p_{i_0}=p_{j_0}\) car \(G\) fini .En plus on a \(p_{i_0+1} =p_{j_0+1}\) car \(P_{i_0+1} = f(P_{i_0} ) = f(P_{j_0} ) = P_{j_0+1}\).
Donc la suite \((p_i)\) satisfait que \(\forall\ell\geq 0 \),\(p_{i_0+\ell} =p_{j_0+\ell}\).
Notations: - Si \(p_i=p_j\) on dit que \(p_i\) et \(p_j\) sont identiques, ou bien , il y a une collision pour \(i_0\) et \(j_0\).
- on peut décrire la suite precedent à la forme de la lettre \(\rho\).
\( \rho \) de Pollard:
On a trouvé que s'il y a une collision pour deux indices différent par \(d\) , tous les indices suivants différant par \(d\) donneront des collisions .Donc on peut calculer les paires \((p_i,p_{2i})\) pour \(i=1.2,... \) ,par les règles:
\(p_{i+1}=f(P_i)\)
\(P_{2(i+1)}=f(f(P_{2i}))\)
Pour \(i \geq i_0\) et \(i\) est multiple de \(d\) (e.g ; \(i=md\))\( \Rightarrow P_i=P_{2i}\).Le nombre d'etapes pour trouver une match devrait etre au plus un multiple constant \(\sqrt{N}\)
Choix de \(f\) :
On subdivise \(G \) a \(s\) sous-ensembles disjoints \(s_1,s_2,...,s_s\).Choisissons \(2s\) entieres \(a_i,b_i\) mod N.
posons \(M_i=a_iP+b_iQ\).
on choisit \(f(g)=g+M_i \),si \(g\in s_i\).
Trouve \(k\) :
Choisissez des entiers aléatoires \(a_0, b_0\) et posez \(P_0 = a_0P + b_0Q\).si\( P_j = u_jP + v_jQ\) and \(P_{j+1} = Pj + Mi\), then \(P_{j+1} = (u_j + a_i)P + (v_j + b_i)Q\), alors \((u_{j+1}, v_{j+1}) =(u_j , v_j )+(a_i, b_i)\).
Quand on trouve une colision \(P_{j_0} = P_{i_0}\), alors \(u_{j_0} P + v_{j_0}Q = u_{i_0} P + v_{i_0}Q\) ,du coup, \((u_{i_0} − u_{j_0} )P = (v_{j_0} − v_{i_0} )Q\).
si \(gcd(v_{j_0} - v_{i_0} , N) = d\).Alors, \(k \equiv (v_{j_0} - v_{i_0})^{-1} (u_{i_0} - u_{j_0} ) (mod N/d)\).Cela nous donne d choix pour \(k\).D'habitude, d sera petit, nous pouvons donc essayer toutes les possibilités jusqu'à ce que nous ayons \(Q = kP\).
-L'avantage de cette méthode :
c'est trouver la collision sans besoin de beaucoup des espaces de stockage .
Attaque de Pohlig-Hellman
Soit \(G \) un groupe , et soient \(P,Q\in G\) , on cherche \(k\) entière telle que \(Q=kP\).soit \(N\) est l'ordre de \(P\) tel que \(N=\prod_iq_i^{e_i}\).
L'idée principale : trouve \(k\) mod \(q_i^{e_i}\) pour tous \(i\), et puis utilise le théorème des restes chinois pour obtenir \(k \) mod \(N\).
L'algorithme:
Soit \(q\) un nombre premier divise \(N\) , et soit \(q^{e}\) est la plus grand puissance de \(q\) qui divise \(N\).on ecrit \(k\) en base \(q\) :
\(k=k_0+k_1q+k_2q^2+...\) avec \(0\leq k_i\leq q-1\)
On va évaluer \(k\) (mod \(p^{e}\)) en déterminant \(k_0,k_1, ... ,k_{e-1}\) :
1. calculer \(\tau =\{j(\frac{N}{q} P)\) t.q \(0\leq j \leq q-1\}\)
2. Calcule \(\frac{N}{q}Q\) qui est égal à \(k_0(\frac{N}{q} P)\in \tau\)
3. Si \(e=1\) on arrête . Sinon , on continue .
4. Soit \(Q_1=Q-k_0*P\) .
5. Calcule \(\frac{N}{q^2}Q_1\) qui est égal à \(k_1(\frac{N}{q} P)\in \tau\) .
6. Si \(e=2\) on arrête . Sinon , on continue .
7. Supposons que on a calculé \(k_0, k_1,...,k_{r−1}\) et \( Q_1,...,Q_{r−1}\).
8. Soit \(Q_r = Q_{r−1} − k_{r−1}q^{r−1}P\).
9. Déterminer \(K_r\) telle que \(\frac{N}{q^{r+1}}Q_r =k_r(\frac{N}{q} P)\in \tau\).
10. Si \(r = e − 1\) , arrête . Sinon, reviens à l’étape (7).
Alors \(k ≡ k_0 + k_1q + ... + k_{e−1}q^{e−1} (mod q^{e}) \).
Pourquoi ça marche ? : Comme \(k=k_0+k_1q+k_2q^2+...\) ; \(Q = kP\) et \(NP=\infty\) . Alors , \(\frac{N}{q} Q= \frac{N}{q}(k_0+k_1q+...)P =k_0\frac{N}{q}P+(k_1+k_2q+...)NP =k_0\frac{N}{q}P\). alors, l'étape 2 trouve \(k_0\).Donc , comme \(Q_1=Q-k_0P=(k_1q+k_2q^2+....)P\) ,alors; \(\frac{N}{q^2} Q_1= (k_1+k_2q+...)\frac{N}{q}P = k_0\frac{N}{q}P+(k_2+k_3q+...)NP =k_1\frac{N}{q}P\).Cet étape donne \(k_1\) . De même manière on trouve \(k_2,k_3,... \) .On arrête à \(r=e-1\) car on a trouvé \(k\) (mod \(q^{e}\) )
Un exemple :
pour \(G = E(F_{599})\)
\( E : y^2 = x^3 + 1\)
\(P = (60, 19)\) et \(Q = (277, 239)\) .
\(N = 600\).Trouver \(k\) telle que \(Q=kP\).
-La solution: on a \(600 = 2^3 · 3 · 5^2\). On va calculer a , b et c tels que
\(k ≡ a (mod 8)\)
\(k ≡ b (mod 3)\)
\(k ≡ c (mod 25)\)
-Calcule a:
\(\tau=\{\infty,(598, 0)\} \).
On trouve \(k_0=0, k_1=1, k_2=0\) car
\(\frac{N}{2}Q=0*\frac{N}{2}P\)
\(\frac{N}{4} Q_1\) = 1*\(\frac{N}{2} p\) où \(Q_1=Q − 0 P= Q\)
\(\frac{N}{8} Q_2\) = 0*\(\frac{N}{2} p\) où \(Q_2 = Q_1 − 1 · 2 · P = (35, 243)\).
Alors , \(k =0+1 · 2+0 · 4 + ··· ≡ 2 (mod 8) \) , donc \(a=2\).
De même manière on trouve que \(b=2\) et \(c=16\).
Par le théorème des restes chinois on trouve \(k ≡ 266 (mod 600)\), Alors \(k = 266\).
Références
[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Sections 5.2.2 et 5.2.3