Wiki du cours

Rédacteur: Rana Alshweiki

A traiter [Modifier]

• Attaque \( \rho \) de Pollard
• Attaque de Pohlig-Hellman

Attaque \( \rho \) de Pollard [Modifier]

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 [Modifier]

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 [Modifier]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Sections 5.2.2 et 5.2.3