Sujet 18: Le problème du logarithme discret et attaques III

Dans cette section, on va voir une méthode qui permet, dans certains cas, de résoudre le problème du logarithme discret rapidement en le réduisant à un problème plus simple. Une telle réduction peut être faite grâce aux accouplements de Weil et Tate-Lichtenbaum : le problème du logarithme discret sur une courbe est ramené à un problème sur un groupe multiplicatif fini. Plus précisément, l'attaque MOV, développée par Menezes, Okamoto et Vanstone, utilise l'accouplement de Weil pour convertir un problème du logarithme discret dans \( E(\mathbb{F}_{q})\) en un problème de logarithme discret dans \(\mathbb{F}_{q^{m}}^{\times}\), pour un certain entier \(m\).

Rappels [Modifier]

Définition: Pour une courbe elliptique \(E\) définie sur \( \mathbb{F}_{q} \), \(E[N] = \{P\in E(\bar{K}) | NP = \infty \}\).

Théorème 3.2: Soient \(E\) une courbe elliptique sur un corps \(K\) et \(N\in \mathbb{N}\). Si la caractéristique de \(K\) ne divise pas \(N\) ou si elle vaut \(0\), alors \(E[N]\simeq \mathbb{Z}_{N} \oplus \mathbb{Z}_{N} \).

Définition: \(\mu_{N} = \{ x \in \bar{K} | x^{N} = 1 \} \).

Théorème 3.9: Le couplage de Weil \(e_{N} : E[N] \times E[N] \to \mu_{N} \) vérifie les propriétés suivantes :

\(\forall S_{1}, S_{2}, T \in E[N]\), \( e_{N}(S_{1}+S_{2},T) = e_{N}(S_{1},T)e_{N}(S_{2},T)\) et \(\forall S,T_{1},T_{2} \in E[N]\), \( e_{N}(S,T_{1}+T_{2}) = e_{N}(S,T_{1})e_{N}(S,T_{2})\).
\(\forall T \in E[N]\), \(e_{N}(T,T) = 1\).

Remarque: Si \(gcd(N,q) = 1\) et \(S,T\in E[N]\), alors \(e_N(S,T)\) est une N-ième racine de l'unité.

Corollaire 3.10: Si \(\{S,T\}\) est une base de \(E[N]\), alors \(e_{N}(S,T)\) est une N-ième racine primitive de l'unité.

Corollaire 3.11: Si \(E[N] \subseteq E[K]\), alors \(\mu_{N} \subset K\).

Problème du logarithme discret [Modifier]

Énoncé du problème

Soient \(E\) une courbe elliptique sur \( \mathbb{F}_{q} \) et \( P,Q \in E(\mathbb{F}_{q})\). Notons \(N \) l'ordre de \(P\) et supposons que \(gcd(N,q) = 1\). On cherche un entier \(k\) tel que \(Q = kP\).

Conditions de l'existence de \(k\).

Lemme 5.1

Avec les données ci-dessus, \( \exists k\) tel que \(Q = kP\) \(\iff\) \(NQ = \infty\) et \(e_{N}(P,Q) = 1\).

Preuve du lemme 5.1

\(\Rightarrow\) : Si \(Q = kP\), alors \(NQ = kNP = k \infty = \infty \) (car \(P\) est d'ordre \(N\)). Aussi, \(e_{N}(P,Q) = e_{N}(P,kP) = e_{N}(P,P)^{k} = 1^{k} = 1\), par les propriétés de \(e_{N}\).

\(\Leftarrow\) : Si \(NQ = \infty\), alors \(Q\in E[N]\). Comme \(gcd(N,q) = 1\), on a \(E[N] \simeq \mathbb{Z}_{N} \oplus \mathbb{Z}_{N} \) par le théorème 3.2. Considérons un point \(R\) tel que \(\{P,R\}\) forme une base de \(E[N]\). Alors, on peut écrire \(Q = aP + bR\), avec certains entiers \(a, b\). Du corollaire 3.10, on déduit que \(e_{N}(P,R) = \zeta\) est une N-ième racine primitive de l'unité. Par hypothèse, \(e_{N}(P,Q) = 1\), alors \(1 = e_{N}(P,aP+bR) = e_{N}(P,P)^{a}e_{N}(P,R)^{b} = 1^{a} \zeta^{b} = \zeta^{b}\). Donc, \(b\equiv0\) (mod \(N\)) et \(Q = aP + bQ = aP + 0Q = aP\). \( \blacksquare \)

Algorithme MOV [Modifier]

Remarquons que comme chaque point de \(E[N]\) a ses coordonnées dans \( \bar{\mathbb{F}}_q = \bigsqcup_{j \in \mathbb{N}} \mathbb{F}_{q^j} \), \(\exists m\) tel que \(E[N]\subseteq E(\mathbb{F}_{q^{m}})\). Ainsi, \(\mu_{N} \subset \mathbb{F}_{q^{m}}\) par le corollaire 3.11.

L'algorithme MOV se déroule comme suit:

On choisit un point quelconque \(T \in E(\mathbb{F}_{q^{m}})\).
On calcule l'ordre de \(T\), noté \(M\).
Soit \(d = gdc(M,N)\) et notons \( T_{1} = (M/d)T\). Alors, l'ordre de \(T_{1}\) est \(d\), et comme \(d\) divise \(N\), \(T_{1} \in E[N]\).
On calcule \( \zeta_{1} = e_{N}(P,T_{1})\) et \(\zeta_{2} = e_{N}(Q,T_{1})\). Comme \(1 = e_{N}(P,\infty) = e_{N}(P,dT_{1}) = e_{N}(P,T_{1})^{d} = \zeta_{1}^{d}\) et pareillement pour \( \zeta_{2}\), donc \( \zeta_{1}\) et \( \zeta_{2}\) sont dans \(\mu_{d}\) \(\subseteq\) \(\mu_{N}\) \(\subseteq\) \(\mathbb{F}_{q^{m}}^{\times}\).
On résout le problème du logarithme discret pour \(\zeta_{2} = \zeta_{1}^{k}\) dans \(\mathbb{F}_{q^{m}}^{\times}\). Ceci fournit \(k\) (mod \(d\)).
On répète avec des points quelconques \(T\) jusqu'à ce qu'on ait \( gdc(M,N) = N\). Ceci détermine \(k\) (mod \(N\)).

Remarques [Modifier]

En raison de la structure de \(E(\mathbb{F}_{q^{m}})\), \(d=1\) n'aura pas souvent lieu. En effet, on se rappelle que \(E(\mathbb{F}_{q^{m}})\simeq \mathbb{Z}_{n_1}\oplus \mathbb{Z}_{n_2}\), pour des entiers \(n_{1}, n_{2}\) tels que \(n_{1} \mid n_{2}\) (avec possibilité que \(n_{1} = 1\), auquel cas le groupe est cyclique). \(n_{2}\) étant le plus grand ordre possible pour un élément du groupe \(E(\mathbb{F}_{q^{m}})\), on a que \(N \mid n_{2}\). Soient \(B_{1}, B_{2}\) des points d'ordre \(n_{1}, n_{2}\) respectivement qui engendrent \(E(\mathbb{F}_{q^{m}})\). On peut donc écrire \(T = a_{1}B_{1} + a_{2}B_{2}\). Soit \(l^{e} \mid N\) avec \(l\) premier. Alors, il existe \( f \ge e\) tel que \(l^{f} \mid n_{2}\). Si \(l \nmid a_{2}\), alors \(l^{f} \mid M\) (l'ordre de \(T\)). En effet, \(\infty = MT = Ma_{1}B_{1} + Ma_{2}B_{2}\) implique que \(Ma_{1}B_{1} = Ma_{2}B_{2} = \infty\). Donc, \(n_{2} \mid Ma_{2}\) et comme \(l \nmid a_{2}\), \(l^{f} \mid n_{2}\), alors \(l^{f} \mid M\). Ainsi, \(l^{e} \mid d\), \(d = gcd(M,N)\). La probabilité que \(l \nmid a_{2}\) est \(1-1/l\), donc la probabilité que \(d \ne 1\) est au moins \(1-1/l\). Ainsi, après avoir choisi certains \(T\) différents, on devrait parvenir à trouver un \(d \ne 1\). Enfin, après quelques itérations de l'algorithme, on devrait trouver \(k\).
Si l'entier \(m\) de \(E(\mathbb{F}_{q^{m}})\) est grand, alors le problème du logarithme discret dans le groupe \(\mathbb{F}_{q^{m}}^{\times}\), qui est d'ordre \(q^{m}-1\), est aussi difficile à résoudre que le problème du logarithme discret dans \( E(\mathbb{F}_{q})\), qui est d'ordre environ \(q\), par le théorème de Hasse. Dans le cas des courbes supersingulières, on va voir qu'on peut en général prendre \(m = 2\).

Réduction du problème dans le cas d'une courbe supersingulière [Modifier]

Avant-propos

Soit \(E\) une courbe elliptique définie sur \( \mathbb{F}_{q} \), où \(q\) est la puissance d'un nombre premier \(p\). Alors \( \# E(\mathbb{F}_{q^{m}}) = q+1-a\), pour un certain entier \(a\). On dit qu'une courbe \(E\) est supersingulière si \(a \equiv 0\) (mod \(p\)), ce qui équivaut à \(a = 0\) si \(p = q \ge 5\) par le corollaire 4.32.

Proposition 5.3

Soit \(E\) une courbe elliptique sur \( \mathbb{F}_{q}\) et supposons que \(a = 0\) (c'est-à-dire que \(E\) est supersingulière). Soit \(N\in \mathbb{N}\). S'il existe un point \(P \in E(\mathbb{F}_{q})\) d'ordre \(N\), alors \(E[N] \subseteq E(\mathbb{F}_{q^{2}})\).

Preuve de la proposition 5.3

L'endomorphisme de Frobenius \( \phi_{q} : \bar{\mathbb{F}}_q \to \bar{\mathbb{F}}_q\), \(x \to x^{q}\) satisfait \( \phi_{q}^{2}-a\phi_{q}+q=0\) par le théorème 4.10. Par hypothèse, \(a=0\), donc \( \phi_{q}^{2} = -q\). Soit \(S \in E[N]\), puisque \( \# E(\mathbb{F}_{q}) = q+1\) et qu'il existe un point d'ordre \(N\), on a \(N \mid (q+1)\), autrement dit \(-q \equiv 1\) (mod \(N\)). Donc, \( \phi_{q}^{2}(S) = -qS = 1S\). \( \phi_{q}^{2} = \phi_{q^{2}}\), donc \(S \in E(\mathbb{F}_{q^{2}})\) par le le lemme 4.5. \( \blacksquare \)

Remarque

La preuve ci-dessus utilise des résultats qu'on n'a pas vus. (Voir littérature pour les détails)

Conclusion

L'algorithme MOV est donc très efficace lorsque la courbe \(E(\mathbb{F}_{q})\) est supersingulière et que \(a=0\) car on peut se ramener à un problème de logarithme discret sur \( \mathbb{F}_{q^{2}}\).

Références [Modifier]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 5.3.1