LE PROBLÈME DU LOGARITHME DISCRET ELLIPTIQUE : INDEX ET XEDNI

Abderrahmane Nitaj

Abstract. Le but est de présenter le problème du logarithme discret elliptique.

1. Introduction-Un peu d’histoire.

2. La méthode du calcul de l’index.

3. Le logartithme discret elliptique.

4. La méthode du calcul de l’index pour les courbes elliptiques.

5. La méthode du xedni.

1. Introduction-Un peu d’histoire.

• Le problème : Soient G un groupe cyclique noté multiplcativement, engendré par un élément

g. Soit a un élément de G. Le problème du logarithme discret est la détermination du plus petit entier x = log_{g} a vérifiant a = g^{x}.

Tout d’abord, une formule de 1984 due à Wells [7] donne : si G = 𝔽_{p} = ⟨g⟩, alors pour tout 1 ≤ a ≤ p − 1,

log_{g} a = ∑_{j=1}^{p−2}(1 − g^{j})^{−1}a^{j} (mod p).

Il est évident que cette belle formule n’est pas pratique.

• Les méthodes :

- Pas de bébé, pas de géant de Shanks, temps exponentiel en O (|G|^{1/2}).

- La méthode Rho de Pollard, G = 𝔽_{q}^{∗}, temps exponentiel en O(\sqrt{q}).

- La méthode de Silver-Pohling-Hellman, G = 𝔽_{q}^{∗}, temps exponentiel en O(\sqrt{p}) où p est le plus grand facteur premier de q − 1. Cet algorithme est donc

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 11G20, 11Y16.

Key words and phrases. logarithme discret, courbes elliptiques.

efficace si p est petit, ce qui oblige les cryptographes à regarder la composition de q − 1.

- La méthode du calcul de l’index, G = 𝔽_{p}^{∗}. Le cas rigoureux, le temps est sous-exponentiel en

O (L_{p} [\frac{1}{2}, c_{1}]) = O (e^{(c_{1}+o(1))(log p)^{1/2}(log log p)^{1/2}})

Le cas heuristique (dépend de certaines conjectures), d’après Gordon, le temps est sous-exponentiel en

O (L_{p} [\frac{1}{3}, c_{2}]) = O (e^{(c+o(1))(log p)^{1/3}(log log p)^{2/3}})

pour des constantes positives c_{1} et c_{2}. Ce dernier résultat a été obtenu par Gordon en 1992, en appliquant la méthode de factorisation du crible algébrique (the Number Filed Sieve). La méthode du calcul de l’index date de 1920 (Kraitchik) et a été redécouverte par Western, Miller, Adelman, Merckle, Pollard et bien d’autres.

document

2. La méthode du calcul de l’index.

Description : Soit p un nombre premier, g un générateur de 𝔽_{p}^{∗} et a un élément de 𝔽_{p}^{∗}. Déterminer x = log_{g} a vérifiant a = g^{x}.

Etape 1.

• Choisir un entier r.

• Poser F_{r} = {2, 3, 5, 7, ⋯, p_{r}} où p_{r} est le r-ème nombre premier. F_{r} est

la base de facteurs.

• Poser ⟨F_{r}⟩ = {z ∈ 𝔽_{p} : z = ∏_{i=1}^{r} p_{i}^{e_{i}}} ≤ p_{r}}. L’ensemble ⟨F_{r}⟩ est

composé des nombres entiers dont les facteurs premiers sont dans F_{r}. Il est appelé l’ensemble des entiers F_{r}-lisses.

Etape 2.

• Pour j = 0, 1, 2, ⋯, calculer g_{j} = g^{j} (mod p).

• Si g_{j} ∈ ⟨F_{r}⟩,factoriser :

g_{j} = ∏_{i=1}^{r} p_{i}^{e_{i}(j)}.

Cette relation donne alors l’équation linéaire :

j ≡ ∑_{i=1}^{r} e_{i}(j) log_{g} p_{i} (mod p − 1),

dans laquelle les inconnues sont log_{g} p_{i}, 1 ≤ i ≤ r.

Le calcul des quantités g_{j} doit se poursuivre jusqu’à l’obtention de r équations linéaires. Ainsi, avec un système (r, r), on peut calculer log_{g} p_{i}, 1 ≤ i ≤ r.

Etape 3.

• Pour j = 0, 1, 2, ⋯, calculer a_{j} = ag^{j} (mod p).

• Si pour un premier entier j on a a_{j} ∈ ⟨F_{r}⟩, factoriser :

a_{j} = ∏_{i=1}^{r} p_{i}^{f_{i}}.

Ceci donne alors l’égalité :

j + log_{g} a ≡ ∑_{i=1}^{n} f_{i} log_{g} p_{i} (mod p − 1),

d’où la valeur de log_{g} a.

Le choix de r.

• Si r est petit, l’étape 2 sera trop longue car il est peu probable qu’un g_{j} = g^{j} soit dans ⟨F_{r}⟩.

• Si r est trog grand, l’étape 2 sera aussi longue car il faut factoriser chaque g_{j}, d’où l’importance du choix de la méthode de factorisation (le crible algébrique est certainement le plus adapté).

• On pose

N(F_{r}) = #{z ∈< F_{r} >: 1 ≤ z ≤ p}.

Ceci donne avec z = ∏_{i=1}^{r} p_{i}^{e_{i}} :

N(F_{r}) = #{(e_{1}, ⋯, e_{r}) ∈ ℕ^{r}, ∑_{i=1}^{r} e_{i} log p_{i} ≤ log p}.

Ainsi N(F_{r}) représente le nombre de r-uplets d’entiers positifs contenus dans le polhèdre de dimension r et de rayon log p.

Soit Ψ(x, y) le nombre d’éléments inférieurs à x et ayant un plus grand facteur jusquà y. Alors

N(F_{r}) = Ψ(p, p_{r}).

Il y a beaucoup de travaux qui concernent la fonction Ψ. On peut appliquer dans notre cas l’approximation suivante (Canfield, Erdös, Pomerance) :

Ψ(x, y) ≈ xe^{− \frac{1}{2} \sqrt{log x log log x}},

dans le cas y ≥ e^{\sqrt{log x log log x}}. En prenant r ≈ e^{\sqrt{log p}}, on obtient

r log r ∼ p_{r} ∼ e^{\sqrt{log p log log p}},

ce qui donne

N(F_{r}) ∼ pp_{r}^{− \frac{1}{2}} > pe^{− \frac{1}{2} \sqrt{log p}}.

La probabilité qu’un nombre 1 ≤ z ≤ p soit dans ⟨F_{r}⟩ est :

\frac{N(F_{r})}{p − 1} ≈ e^{− \frac{1}{2} \sqrt{log p}}.

Ainsi, le choix pour r de prendre r ≃ e^{\sqrt{log p}} représente une valeur sous-exponentielle pour r.

Les records

1. Avec Le Special Number Field Sieve (SNFS): Le record actuel est dû à D. Weber, en résolvant le challenge de Mc-Curley en 1998:

Déterminer x tel que 7^{x} ≡ b (mod p) avec b de 129 chiffres et p = 793· \frac{7^{149}−1}{3} +1 de 129 chiffres aussi. Ici, les corps de nombres considérés sont très favorables au crible, d’où le terme “Special”.

2. Avec Le General Number Field Sieve (GNFS): Lercier : a^{x} ≡ b (mod p), avec a = 2 et b = ⌊10^{119}e⌋ et le 120 chiffres p = ⌊10^{119}π⌋ + 207819. Ici, les corps de nombres considérés ne sont pas très favorables au crible, d’où le terme “General”.

Autres méthode de factorisation : Il s’agit de factoriser un entier n. Le nombre premier p′ est le plus grand facteur premier de n − 1. Il y a cependant deux sortes d’algorithmes, les spéciaux (S) et les généraux (G). Les spéciaux exploitent la forme de n contrairement aux généraux.

Complexité des méthodes de factorisation

Méthode  Autheur, Nature Complexité
Rho de Pollard  P ollard, 1975, S  O(\sqrt{n})
p-1 de Pollard  P ollard, 1974, S  O(sqrtp′)
Courbes elliptiques (ECM) Lenstra, 1985, S  O (e^{\sqrt{2 log nlog log n}})
Le crible algébrique (NFS) LLMP, 1989, G  O (e^{c(log n)^{1/3}(log log n)^{2/3}})
Le crible quadratique (mpqs) P omerance, 1984, G (e^{\sqrt{log nlog log n}})

LLMP=Lenstra, Lenstra, Manasse, Pollard,

L’algorithme de Gordon (Selon Weber):

Puisque a = g^{x} (mod p), alors 1 ≤ x ≤ p − 1. Soit p′ un grand diviseur premier de p−1. Si on trouve deux entiers s et t modulo p−1 avec (t, q) = 1 et si on trouve un entier w modulo p tels que

g^{s}a^{t} ≡ w^{p′} (mod p),

alors s + tx ≡ p′ (mod p) − 1, d’où x = −st^{−1} (mod p′).

A développer plus tard ....

3. Le logartithme discret elliptique.

Soit G un groupe noté additivement et A et B deux éléments de G. Le problème du logarithme discret est la détermination d’un entier n (s’il existe) tel que A = nB.

Les algorithmes disponibles pour le cas des courbes elliptiques sont les analogues de la méthode de Shanks et celle de Pollard.

Les premiers shemas cryptographiques utilisant les courbes elliptiques furent introduits indépendament par V. Miller et N. Koblitz en 1985. L’intérêt des courbes elliptiques, est que les problèmes du logarithme discret y sont difficiles à résoudre, et aucun algorithme sous-exponentiel n’y est disponible. Un avantage évident dans ce domaine est de prendre des clées de longueur assez petites par rapport à celles requises pour RSA ou pour les corps finis (160 bits au lieu de 1024 bits).

Soit E une courbe elliptique définie sur 𝔽_{p} par l’équation :

E :  Y^{2} + a_{1}XY + a_{3}Y = X^{3} + a_{2}X^{2} + a_{4}X + a_{6},  (1)

avec a_{1}, a_{2}, a_{3}, a_{4} et a_{6} ∈ 𝔽_{p}. On pose N_{p} = #E(𝔽_{p}). Une combinaison des des algorithmes de Schoof, Elkies et Atkin (SEA) permet de calculer N_{p} en un temps polynômial en

O(log^{6} p).

Le problème du logarithme discret elliptique est le suivant :

Etant donné deux points S et T de E(𝔽_{p}) vérifiant S ∈ ⟨T ⟩, déterminer un entier x tel que S = xT. On pose alors x = log_{T} S.

Les méthodes connues sont les suivantes :

- La méthode exhaustive. Cette méthode consiste à calculer T, 2T, 3T, ⋯ jusquà obtenir S. Ceci peut prendre N_{p} étapes.

- La méthode de Shanks (Baby Step, Giant Step). Cette méthode requiert \sqrt{N_{p}} étapes.

- La méthode Rho de Pollard. Cette méthode requiert \sqrt{πN_{p}/2} étapes.

- La méthode Western-Pohling-Hellman. Cette méthode requiert \sqrt{n} étapes, où n est le plus grand facteur premier de N_{p}.

Il existe des cas de courbes elliptiques pour lesquelles le problème du logarithme discret peut être plongé dans des corps finis, et donc peuvent être considérées comme triviales pour la cryptographie.

- Les courbes supersingulières. (Menezes, Okamoto, Vanstone) Ce sont les courbes pour lesquelles N_{p} = p + 1. Le probléme du logarithme discret sur ces courbes peut être réduit au groupe multiplicatif 𝔽_{p}^{∗}.

- Les courbes elliptiques anomales “anomalous”. (Samaev, Araki, Satoh, Smart) Ce sont les courbes pour lesquelles N_{p} = p. Le probléme du logarithme discret sur ces courbes peut être réduit au groupe additif 𝔽_{p}.

- Les courbes spéciales. Ce sont les courbes pour lesquelles N_{p} n’admet que des facteurs premiers petits. Dans ce cas, la méthode de Pollard et celle de Western-Pohling-Hellman peuvent être efficacement utilisées.

4. La méthode du calcul de l’index pour les courbes elliptiques.

Soit E/𝔽_{p} une courbe elliptique et deux points S et T de E(𝔽_{p}) vérifiant S ∈ ⟨T ⟩. On veut déterminer un entier x tel que S = xT. On pose alors x = log_{T} S.

Pour appliquer la méthode du calcul de l’index dans le cas elliptique, voici comment on pourrait procéder :

Etape 1.

• Choisir une courbe elliptique E/ℚ qui se réduit à E/𝔽_{p}. Etape 2.

• Choisir un entier r.

• Choisir r points indépendants Q_{1}, Q_{2}, ⋯, Q_{r} de E/ℚ.

• Pour i = 1, ⋯, r, poser P_{i} ≡ Q_{i} (mod p). Le but est de déterminer r entiers log_{T} (P_{i}) (mod N_{p}) vérifiant P_{i} = (log_{T} (P_{i}))T. Etape 3.

• Pour j = 1, 2, · · · ., calculer les points T, 2T, ⋯, jT, ⋯ dans E(𝔽_{p}),

et pour chaque j, essayer de plonger jT dans un point T_{j} de E(ℚ). Ainsi, T_{j} ≡ jT (mod p). Si le plongement estpossible, essayer d’écrire dans E(ℚ) :

T_{j} = ∑_{i=1}^{r} n_{i}Q_{i}.

sinon reprendre un autre j.

Cette étape doit être poursuivie jusqu’à l’obtention de r combinaison de la forme ci-dessus.

La combinaison ci-dessus donne

j ≡ ∑_{i=1}^{r} n_{i} log_{T} (P_{i}) (mod N_{p}),

avec log_{T} (P_{i}) vérifiant P_{i} = (log_{T} (P_{i}))T, et le système de r équations aux r inconnues log_{T} (P_{j}) peut être donc résolu.

Etape 4.

• Pour j = 0, 1, ⋯, essayer de plonger S + jT dans un point T′_{j} de E(ℚ).

On doit poursuivre cette opération jusqu’à obtenir un entier j pour lequel T′_{j} est dans E(ℚ).

• Essayer décrire dans E(ℚ) :

T′_{j} = ∑_{i=1}^{r} f_{i}Q_{i}.

Si cette opération réussi, alors

log_{T} (S) + j = ∑_{i=1}^{r} f_{i} log_{T} (P_{i}),

et donc finalement log_{T} (S), ce qui résoud le problème du logarithme discret.

Cette méthode ne peut être utilisée efficacement à cause des trois problèmes suivants :

Problème 1. Il est très difficile de déterminer des courbes elliptiques définis sur ℚ ayant un grand rang.

Le record actuellement est de 24.

Problème 2. Il est très difficile de déterminer des courbes elliptiques définis sur ℚ engendrés par des points ayant des petites hauteurs.

Problème 3. Il est très dificle de plonger un point de E(𝔽_{p}) dans un point de E(ℚ).

Analyse des difficultés.

La hauteur d’un rationnel r/s est :

H (\frac{r}{s}) = max(|r|, |s|).

La hauteur canonique d’un point P ∈ E(ℚ) est :

ĥ(P) = \frac{1}{2} lim_{n→∞} \frac{1}{n^{2}} log H(x(nP)),

ce qui défini le produit :

⟨P, Q⟩ = \frac{1}{2}(ĥ(P + Q) − ĥ(P) − ĥ(Q)).

Le régulateur d’un ensemble de points P_{1}, ⋯, P_{r} de E(ℚ) est alors :

R(E) = det(⟨P_{i}, P_{j}⟩)_{1≤i,j≤r}.

Soit B une borne fixée. On pose

N(E, B) = #{P ∈ E(ℚ) : H(x(P)) ≤ B}.

Alors, on démontre que :

N(E, B) ≃ 16\frac{1}{\sqrt{πr}} (\frac{πe log B}{rR(E)^{1/r}} )^{r/2} .

Pour que N(E, B) soit assez grand, on doit donc avoir

log B ≥ \frac{r}{πe}R(E)^{1/r}.

D’autre part, on a le résultat classique suivant :

R(E)^{1/r} ≥ (\frac{\sqrt{3}}{2})^{r−1} min_{P ∈E(ℚ),ĥ(P)≠0} ĥ(P).

Une conjecture de Lang dit :

ĥ(P) ≥ c_{1} log |Δ(E)|,

où c_{1} est une constante indépendante de E et Δ(E) est le discriminant de E. On obtient ainsi

log B ≥ c_{2}r log |Δ(E)|,

où c_{2} est une constante. Enfin, une conjecture de Mestre donne

log |Δ(E| ≥ c_{3}r log r,

où c_{3} est une constante. On obtient finalement :

log B ≥ c_{4}r^{2} log r,

où c_{4} est une constante.

Ainsi, si r (le rang de E) est grand, B est très grand. Cela veut dire que même si le problème 1 est résolu, en démontrant l’existence de r (grand) générateurs de E), le problème 2 se pose pour déterminer explicitement ces générateurs.

la probablité pour qu’un point P de E(𝔽_{p}) soit plongé dans un point Q de E(ℚ) avec une hauteur inférieur à B est :

\frac{N(E, B)}{N_{p}} ∼ \frac{N(E, B)}{p},

puisque, d’après le théorème de Hasse N_{p} = p + 1 − t avec |t| ≤ 2\sqrt{p}. Pour maximiser cette probabilité, on doit prendre N(E, B) proche de p. On peut prendre par exemple une constante c_{5} et imposer N(E, B) ≥ p/c_{5}. On obtient alors :

log B ≥ (\frac{p\sqrt{πr}}{16c_{5}} )^{2/r} \frac{rR(E)^{\frac{1}{r}}}{πe} ,

et en utilisant l’estimation R(E)^{1/r} ≥ c_{6}r log r, on obtient

log B ≥ (\frac{p\sqrt{πr}}{16c_{5}} )^{2/r} \frac{c_{6}r^{2} log r}{πe} .

Expérimentalement, en reprenant des exemples de courbes elliptiques définies sur ℚ de grands rangs (inérieurs à 14) déterminées par Mestre, et heuristiquement, en admettant des conjectures optimistes de Lang et Mestre, Silverman et Suzuki ont explicité les constantes ci-dessus avec p = 173 et on obtenu la minoration suivante :

log B ≥ \frac{r log(p^{11.93}r^{0.26r})}{20πe} (\frac{p\sqrt{πr}}{2^{10}} )^{2/r} ,

ce qui permet d’établir le tableau suivant

Table minimum de B

p  r  B
2^{20}  15  p^{3.63}
2^{40}  40  p^{9.95}
2^{80}  87  p^{22.79}
2^{120}  134  p^{35.81}
2^{160}  180  p^{48.94}

Pour avoir une sécurité suffisante, il faut prendre p ≥ 2^{80}, ce qui veut dire avoir une courbe elliptique de rang au moins 87 (à comparer avec le record actuel).

Conclusion et moralité : La méthode du calcul de l’index pour les courbes elliptiques aboutit a des problèmes encore plus difficiles que le problème original.

Comparaison des tailles des éléments des bases de facteurs

Dans le cas de 𝔽_{p}, le plus grand facteur premier p_{r} vérifie p_{r} ≃ r log r.

Dans le cas des courbes elliptiques, on a pour chaque i, ĥ(Q_{i}) ≥ c_{7}r log r. De plus, un résultat de Silverman donne :

ĥ(Q_{i}) = \frac{1}{2} log H(x(Q_{i})) + c_{8},

où c_{8} est une constante positive dépendant de E. Ainsi

H(x(Q_{i})) ≥ c_{9}r^{2c_{7}r}.

Ceci montre que la taille des générateurs dans le cas elliptique est exponentiel relativement au cas entiers.

Description des étapes

Etape 1. On veut plonger plonger E/𝔽_{p} dans E/ℚ. Si E est définie par l’équation :

E : Y^{2} + a_{1}XY + a_{3}Y = X^{3} + a_{2}X^{2} + a_{4}X + a_{6},

avec a_{1}, a_{2}, a_{3}, a_{4} et a_{6} ∈ 𝔽_{p}. Alors, si t_{i}, 1 ≤ i ≤ 7 sont des nombres rationnels de dénominateurs premiers avec p, la courbe E/ℚ définie par :

E :  (1 + pt_{1})Y^{2} + (a_{1} + pt_{2})XY + (a_{3} + pt_{3})Y
= (1 + pt_{4})X^{3} + (a_{2} + pt_{5})X^{2} + (a_{4} + pt_{6})X + (a_{6} + pt_{7}),

vérifie E ≡ E (mod p). Le choix de valeurs t_{i}, 1 ≤ t_{i} ≤ 7 est celui qui donne une courbe elliptique E/ℚ de grand rang.

Etape 2.

La construction de courbes elliptiques de grand rang est un problème difficile. Ce fut Mestre qui commeça la recherche dans ce domaine.

Ancienne méthode, 1982. Cette méthode est à la base de la plupart des calculs qui ont produit des courbes elliptiques de grand rang. Soit p[X] un polynôme de degré 12 à coefficients dans Q. Il existe un unique triplet g[X], r_{1}[X] et r_{2}[X] tels que deg(g) = 4, deg r_{1}, deg r_{2} ≤ 3 et p = g^{3} + r_{1}g + r_{2}. Soit la courbe y^{3} + r_{1}(x)y + r_{2}(x). Cette courbe contient 12 points (x_{i}, g(x_{i})) où x_{i} sont les racines de p. Si deg r_{2} ≤ 2, alors on obtient une courbe elliptique de rang au moins 11.

Nouvelle méthode, 1984. Cette méthode consiste à considérer une courbe elliptique E sous la forme de Weierstrass et de déterminer les coefficients a_{i} de telle sorte que, modulo des nombres premiers l = 2, 3, ⋯, l_{0}, #E(𝔽_{l}) est maximal pour la relation de Hasse. En utilisant le théorème Chinois, on peut déterminer des entiers a_{i}, avec la condition supplémentaire que |Δ(E)| soit assèz petit. Alors, en admettant la conjecture de Birch-Swinnerton-Dyer, on peut espérer un grand rang. La conjecture BSD étant la suivante :

lim_{s→1} \frac{L(s)}{(s − 1)^{r}} = \frac{1}{r!}L^{(r)}(1) = \frac{ΩRC|Shaf|}{|T |^{2}}.

avec les quantités habituelles.

Etapes 3 et 4.

On veut plonger un point P (u, v) de E(𝔽_{p}) dans un point Q(U, V) de E(ℚ). On se place alors dans le cas projectif Q(r, s, t) avec des entiers r, s et t et prendre

r = u + pu′,  s = v + pv′,  t = 1 + pt′,

et déterminer des entiers u′, v′ et t′ de telle sorte que Q(r, s, t) soit un point de E(ℚ). Cette opération conduit à la recherche de points rationnels sur une courbe elliptique.

Etant donné une base {Q_{1}, ⋯, Q_{r}} de E(ℚ), il y a deux façon de déterminer les entiers n_{1}, ⋯, n_{r}, f_{1}, ⋯, f_{r} dans ces étapes : la méthode de la 2-descente et la méthode du régulateur (voir partie 5).

5. La méthode du xedni

En 1998, Silverman d’une part, Kim, Cheon et Hahn d’autre part annoncèrent une méthode pour résoudre le problème du logarithme discret elliptique. Un des nombreux problèmes qui se posent dans l’application de la mathode du calcul de l’index elliptique est la détermination d’une courbe elliptique E/ℚ de grand rang qui se réduit à E/𝔽_{p} modulo p et qui contient tous les points plongés de E(𝔽_{p}). L’idée de la méthode du xedni est inverse.

Partant de E/𝔽_{p}, choisir 2 ≤ r ≤ 9 points P_{1}, ⋯, P_{r} de E(𝔽_{p}). Les transformer en points Q_{1}, ⋯, Q_{r} à coefficients entiers. Déterminer une courbe elliptique E/ℚ passant par ces points. Tester si les points Q_{1}, ⋯, Q_{r} sont dépendants dans E(ℚ). Si oui, le problème du logarithme discret est résolu.

Le problème qui se pose ici donc est de trouver une courbe elliptique de rang inférieur à r.

Rappel: p est un nombre premier, E/𝔽_{p} est une courbe elliptique, S et T sont deux points de E(𝔽_{p}) tels que S ∈ ⟨T ⟩. Déterminer un entier x tel que S = xT.

L’algorithme du xedni (Version très simplifiée): Etape 1.

• Choisir un entier r, 2 ≤ r ≤ 9.

• Choisir des couples d’entiers (s_{i}, t_{i}), 1 ≤ i ≤ r.

• Poser dans E(𝔽_{p}), P_{i} = s_{i}S − t_{i}T, 1 ≤ i ≤ r. Etape 2.

• Plonger les points P_{i} dans des points Q_{i} à coordonnées entières.

• Déterminer une courbe elliptique E/ℚ passant par les points Q_{i}, 1 ≤

i ≤ r.

Etape 3.

• Déterminer si les points Q_{1}, ⋯, Q_{r} sont indépendants, si oui, retourner

à l’étape 1.

• Déterminer des entiers α_{1}, ⋯, α_{r} tels que, dans E(ℚ)

α_{1}Q_{1} + ⋯ + α_{r}Q_{r} = 0.

Etape 4.

• Calculer

s = ∑_{i=1}^{r} α_{i}s_{i},  et  t = ∑_{i=1}^{r} α_{i}t_{i}.

• Si (s, N_{p}) > 1, aller à l’étape 1.

• Calculer x = ts^{−1} (mod N_{p}). Alors log_{T} (S) = x et le problème du logarithme discret est résolu.

Commentaires sur les étapes: Etape 1. Le choix 2 ≤ r ≤ 9 est basé sur le fait que la détermination d’une

cubique (et par la suite une courbe elliptique) nécessite au plus 9 points de passage.

Etape 2. Dans cette étape, on détermine d’abord l’équation d’une cubique avec 10 coefficients :

u_{1}X^{3} + u_{2}X^{2}Y + u_{3}XY^{2} + u_{4}X^{3} + u_{5}X^{2}Z
+ u_{6}XY Z + u_{7}Y^{2}Z + u_{8}XZ^{2} + u_{9}Y Z^{2} + u_{10}Z^{3} = 0.

On peut alors la transformer en une équation de Weierstrass par l’algorithme de Nagell.

Etape 3. Il y a deux façon de déterminer les entiers α_{1}, ⋯, α_{r} en question : la méthode de la 2-descente et la méthode du régulateur.

La méthode de la 2-descente. On veut déterminer des entiers α_{1}, ⋯, α_{r} tels que α_{1}Q_{1} + ⋯ + α_{r}Q_{r} = 0.

Etape a. Déterminer des entiers ε_{i} ∈ {0, 1}, 1 ≤ i ≤ r tels que

ε_{1}Q_{1} + ⋯ + ε_{r}Q_{r} = 0 (mod 2E(ℚ)),

Si tous les coefficients ε_{i} sont nuls, alors, les points Q_{i} sont linéairement indépendants dans E(ℚ)/2E(ℚ), et par conséquent dans E(ℚ).

Etape b. Déterminer un point R de E(ℚ) tel que 2R = ε_{1}Q_{1} + ⋯ + ε_{r}Q_{r}. Si les racines du polynôme de 2-division ne sont pas rationnelles, alors R est unique. En effet, si V est un point de 2-torsion, on peut utiliser la relation 2V = 0 si et seulement si ψ_{2}(V) = 0 avec ψ_{2}^{2}(X) = 4X^{3} + b_{2}X^{2} + 2b_{4}X + b_{6}.

Etape c. Si R n’est pas un point de torsion, soit j un entier tel que ε_{j} ≠ 0. On remplace le point Q_{j} par R et on recommence à l’étape a.

Cette étape peut durer assez longtemps, dans ce cas on peut tester si les points R n’apparaissent pas deux fois, ou bien on arrête carrément les calculs.

Etape d. Si R est un point de torsion, alors en multipliant par son ordre, et en remplaçant tous les points R de l’étape b, on obtient une relation entre les points Q_{i}, ce qui donne les valeurs des α_{i}.

Cette méthode est maintenant classique et est implémentée dans de nombreux systèmes de calculs (Mwrank, Simath, Lidia,...). Cette méthode donne une solution en un temps polynômial en max_{i}(ĥ(Q_{i})).

La méthode du régulateur. Cette méthode consiste à calculer le régulateur ⟨Q_{i}, Q_{j}⟩_{1≤i,j≤r}, et si ce déterminant est proche de 0, on utilise l’algorithme LLL pour déterminer une relation linéaire sur les colonnes du déterminant, ce qui donne la réponse voulue.

Etape 4. Si dans E(ℚ) on a α_{1}Q_{1} + ⋯ + α_{r}Q_{r} = 0, alors dans E(𝔽_{p}) on a α_{1}P 1 + ⋯ + α_{r}P_{r} = 0 et puisque Q_{i} = s_{i}S − t_{i}T, alors

(∑_{i=1}^{r} α_{i}s_{i}) S − (∑_{i=1}^{r} α_{i}t_{i}) T = sS − tT = 0,

et donc (sx − t)T = 0, où x vérifie S = xT. Comme dans E(𝔽_{p}) on a N_{p}T = 0, alors sx − t ≡ 0 (mod N_{p}), ce qui justifie le test (s, N_{p}) > 1.

Théorème (Jacobson, Koblitz, Silverman, Stein, Teske). La probalité pour que de la méthode du xedni résolve le problème du logarithme discret est inférieure à C_{0}/p, où C_{0} est une constante qui ne dépend que de certaines conjectures.

On suppose que les points Q_{i}, 1 ≤ i ≤ r sont linéairement dépendants. Soit E′ = ⟨Q_{1}, ⋯, Q_{r}⟩. Soit r′ le rang de E′. Alors r′ ≤ r − 1. Ainsi E′/E′_{tors} est engendré par r′ points Q′_{1}, ⋯, Q′_{r′}. Soit T′ le nombre de points de torsion de E′. Alors le théorème de Mazur donne T′ ≤ 16. Soit R′ le régulateur de E′, i.e. R′ = det(⟨< Q_{i}, Q_{j}⟩)_{1≤i,j≤r′}. Pour B > 0, on pose

N(B) = #{Q ∈ E′ : ĥ(Q) ≤ B}.

Alors, on a :

N(B) = T′ \frac{V (r′)}{\sqrt{R′}}B^{r′/2} + O (B^{(r′−1)/2}) ,

où V (r′) est le volume de la sphère de dimension r′ et de rayon 1.

Pour r′ assez grand, on peut utliser la formule de Stirling qui donne :

V (r′) ≈ \frac{1}{\sqrt{πr}} (\frac{2πe}{r})^{r/2} .

D’autre part, si on pose m = min_{Q∈E(ℚ),ĥ(Q)≠0} ĥ(Q), alors

R′ ≥ (\frac{\sqrt{3}}{2})^{r′(r−1)} m^{r′}.

Ceci donne alors

N(B) < T′V (r′) (\frac{\sqrt{3}}{2})^{−r′(r′−1)/2} (\frac{B}{m})^{r′/2} + O (B^{(r′−1)/2}) ,

D’autre part, puisque \sqrt{ĥ} est est une distance, alors :

\sqrt{ĥ} (∑_{i=1}^{r} n_{i}Q_{i}) ≤ ∑_{i=1}^{r} \sqrt{ĥ}(n_{i}Q_{i}) ≤ r max_{1≤i≤r} n_{i} max_{1≤i≤r} \sqrt{ĥ}(Q_{i}).

En posant M = max_{1≤i≤r} ĥ(Q_{i}) et C = max_{1≤i≤r} n_{i}, on obtient :

ĥ (∑_{i=1}^{r} n_{i}Q_{i}) ≤ (r^{2}C^{2})M.

On peut donc prendre B = (r^{2}C^{2})M, ce qui donne :

N(B) < T′V (r′) (\frac{\sqrt{3}}{2})^{−r′(r′−1)/2} (rC)^{r′} (\frac{M}{m})^{r′/2} .

Comme il y a (2C)^{r} points de la forme ∑_{i=1}^{r} n_{i}Q_{i} avec |n_{i}| ≤ C, si on a

(2C)^{r} > T′V (r′) (\frac{\sqrt{3}}{2})^{−r′(r′−1)/2} (rC)^{r′} (\frac{M}{m})^{r′/2} ,

alors il y a deux points identiques avec des coefficients non tous égaux, ce qui signifie certifie que les points Q_{i}, 1 ≤ i ≤ r sont linéairement dépendants, en explicitant les quantités α_{i}. On pose

C′ = \frac{log |Δ|}{M},

où Δ est le dsicriminant de la courbe E. La conjecture de Lang donne alors

m = min_{Q∈E(ℚ),ĥ(Q)≠0} ĥ(Q) ≥ C_{L} log |D| ≥ C′C_{L}M,

et on obtient ainsi la condition suffisante :

(2C)^{r} > T′V (r′) (\frac{\sqrt{3}}{2})^{−r′(r′−1)/2} (rC)^{r′}(C′C_{L})^{−r′/2}.

Comme r′ ≤ r − 1, alors il suffit d’avoir

C ≥ T′V (r − 1) (\frac{\sqrt{3}}{2})^{−(r−1)(r−2)/2} (\frac{r}{2})^{r−1} (C′C_{L})^{−(r−1)/2}.

Ainsi, on peut donc avoir des coefficients n_{i} de magnitude C. On a alors pour les points P_{i}, 1 ≤ i ≤ r de la courbe E/𝔽_{p},

#{P = ∑_{i=1}^{r} n_{i}P_{i} : max |n_{i}| ≤ C} ≈ (2C)^{r},

et la probabilité pour qu’une combinaison soit nulle est donc

\frac{(2C)^{r}}{p} = \frac{C_{0}}{p} ,

ce qui prouve le théorème puisque 2 ≤ r ≤ 9.

Numériquement, On prend les hypothèses suivantes :

• pour le nombre de points de torsion, T′ = 1,

• pour la constante de Lang : C_{L} ≥ 0.00005,

• Pour la constante C′ = log |D|/ max_{1≤i≤r} ĥ(Q_{i}), on prend

C′ = \{ \begin{matrix}12(1 + 3r/(7 − r)) & si 2 ≤ r ≤ 6, \\ 110(1 + 3r/(10 − r)) & si 7 ≤ r ≤ 9, \end{matrix}

On obtient ainsi une valeur explicite pour C, puis pour C_{0}, qui ne dépend que r, ce qui donne le tableau suivant :

C et C_{0}
r  C ≈  C_{0} ≈
2  10^{1.8}  10^{4}
3  10^{3.8}  10^{12}
4  10^{5.6}  10^{23}
5  10^{7.5}  10^{38}
6  10^{8.9}  10^{54}
7  10^{9.2}  10^{65}
8  10^{10.4}  10^{84}
9  10^{11}  10^{100}

Expérimentalement, Jacobson et al. on testé l’algorithme du Xedni avec r = 2, 3, 4 pour des petites valeurs de p (p = 17, 67, 5167), et on dressé le tableaux suivant :

Expériences

r #courbes #courbes positives
2 200000  2895
3 200000  21165
4 200000  10698

Conclusion : En considérant l’application de ℤ^{r} dans E(𝔽_{p}) définie par :

(n_{1}, ⋯, n_{r}) → n_{1}P_{1} + ⋯ + n_{r}P_{r},

avec |n_{i}| ≤ C pour une constante C, les points n_{1}P_{1} + ⋯ + n_{r}P_{r} sont équirépartis. La probabilité pour que qu’un point vérifie n_{1}P_{1} + ⋯ + n_{r}P_{r} = 0 est (2C)^{r}/p. Il suffit donc de prendre C vérifiant (2C)^{r} ≈ p et donc C = O (p^{1/r}) avec 2 ≤ r ≤ 9. Deux possibilités se posent alors :

• Si les points Q_{i} de E(ℚ), images des points P_{i} de E(𝔽_{p}) par le plongement, sont linéirement dépendants, l’algorithme du xedni donne la réponse avec des coefficients n_{i} de magnitude C = O(p^{1/r}).

• Si les points Q_{i} sont indépendants, alors il faut changer de paramètres à l’étape 1 ou 2.

Ainsi, l’algorithme du xedni est en O(p), ce qui n’est pas pratique pour les valeurs prises pour p en cryptographie.

References

1. Kim, Hwan Joon; Cheon, Jung Hee; Hahn, Sang Geun, Elliptic curve lifting problem and its applications., Proc. Japan Acad. Ser. A Math. Sci. 75 (1999), 166-169..

2. , On remarks of lifting problems for elliptic curves., Adv. Stud. Contemp. Math. (Pusan) 2 (2000), 2 (2000), 21-36..

4. Jacobson, Michael J.; Koblitz, Neal; Silverman, Joseph H.; Stein, Andreas; Teske, Edlyn, Analysis of the xedni calculus attack, Des. Codes Cryptogr. 20 (2000), no. 1, 20 (2000), 41-64..

5. Silverman, Joseph H., The xedni calculus and the elliptic curve discrete logarithm problem, Des. Codes Cryptogr. 20 (2000), 5–40..

6. Silverman, Joseph H.; Suzuki, Joe, Elliptic curve discrete logarithms and the index calculus, In Advances in cryptology - ASIACRYPT ’98. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1514 (1998), 5–40..

7. Wells, Albert L.jun., A polynomial form for logarithms modulo a prime, IEEE Trans. Inf. Theory 30 (1984), 845-846.