Courbes elliptiques et cryptographie

samurai
samurai
dans Arithmétique
Bonjour
je m'intéresse en tant qu'amateur aux courbes elliptiques et la cryptographie.
Mes références sont :
- An Introduction to the Theory of Elliptic Curves (Joseph Silverman), Summer School on Computational Number Theory and Applications to Cryptography, un powerpoint en pdf de 104 pages de 2006
- Chapitre VII - Courbes Elliptiques (Alain Kraus, cours de Cryptographie MM067 2012/2013)
- Elliptic Tales (Ash & Gross)
J'avais lu ce matériel il y a quelques années et fait quelques programmes d'encryption/décryption et de factorisation de grands nombres (ECPP ...), mais tout ça s'oublie vite hélas.

[EDIT:
je rajoute le texte suivant à ma liste de lecture:
- Pairings for beginners by Craig Costello (2012), qui va parler notamment de "Weil Pairing, Tate Pairing, Miller's algorithm" et qui semble très à jour sur le sujet tout en restant accessible]

Je suis en train de relire le matériel et mes notes, et je me permets de vous poser quelques questions au fur et à mesure que j'avance, dans ce sujet.

D'autre part, je crois avoir déjà pu poser quelques questions sur le forum il y a quelques années sur ce sujet, mais bizarrement je ne trouve hélas rien sur le moteur de recherche, désolé de reposer peut-être les mêmes questions.
Voici la première question.
Dans le pdf de Silverman il est écrit:
"Dans le corps fini $F_p$ il y a environ 2p courbes elliptiques différentes que l'on peut définir"
[Par courbe elliptique, on entend $Y^2 = X^3 + AX + B$ avec un discriminant $4 A^3 + 27 B^2$ $\neq$ 0].

Or, sur Sage, par exemple pour p=5, je trouve 20 combinaisons (A,B) qui me donnent un discriminant non nul, et pour p=7 j'en trouve 42, et en listant sur SAGE les points de ces courbes pour toutes les combinaisons, il semble bien qu'elles soient bien distinctes.
Faut-il comprendre l'affirmation de Silverman à une symétrie (que je ne vois pas) près ?
L'affirmation de Silverman, si elle est correcte, est-elle facile à s'en convaincre, et la preuve en est-elle facile ou bien hors de portée ? 
# SAGE

p = 5
Fp = FiniteField(p)
R = IntegerModRing(p)
A = matrix(R, p, p, lambda i, j: 4*i*i*i+27*j*j)

L= []
for i in range(p): 
      for j in range(p):
         if A[i,j]!=0 :
            E = EllipticCurve(Fp,[i,j])
            L.append(E.points())

S = list (set(L))
S

Réponses

  • aurelpage
    aurelpage
    Bonjour,

    Silverman identifie les courbes isomorphes. Deux courbes sont isomorphes sur la cloture algébrique si et seulement si elles ont le même $j$-invariant, qui peut prendre toutes les valeurs possible du corps ambiant. Deux courbes elliptiques peuvent être non-isomorphes mais devenir isomorphes sur la cloture algébrique, on parle alors de tordues (twists); sur un corps fini, la plupart des courbes ont exactement une tordue distincte (toujours au moins une on parle de sa tordue quadratique, quadratic twist). On obtient bien un total d'à peu près $2p$ sur $\mathbb{F}_p$.

    Amitiés,
    Aurel
  • samurai
    samurai
    Merci beaucoup.
    On m'a expliqué que d'un point de vue plus "pratique", si $(x,y)$ est solution de $y^2 = x^3 + ax+b$ alors $(g^2 x, g^3 y)$ est solution de $Y^2 = X^3 + (g^4)aX+(g^6)b$.

    C    e qui est facile à voir et à constater en pratique en effet.
  • samurai
    samurai
    bonjour, j'avance doucement dans le cours, mais j'ai des difficultés même avec des choses très très basiques :-(

    la question est basée sur les pages 29-30 du cours de crypto elliptique de Kraus mentionné dans le 1er message.

    le Théorème 7.9 dit que dans un corps fini de caractéristique p, une courbe E est super-singulière ssi $card(E(K)) == 1 [p]$

    Or, considérons l'exemple 7.11
    la courbe E définie $y^2 = x^3 +2x + 1$ dans $F_5$

    Sage me donne 7 points
    [(0 : 1 : 0), (0 : 1 : 1), (0 : 4 : 1), (1 : 2 : 1), (1 : 3 : 1), (3 : 2 : 1), (3 : 3 : 1)]

    à part le point à l'infini, je peux vérifier que les autres points sont tous d'ordre 7.

    donc E[5], le sous-groupe des points de d'ordre 5 est réduit au seul point à l'infini.

    mais cela semble être alors un contre-exemple du théorème, puisque card(E) = 7 n'est pas congru à 1 modulo 5 ?



    Où est-ce que je me suis trompé dans ma compréhension du théorème ?

    merci
  • claude quitté
    claude quitté
    Bonjour Samourai. On s'est ``déjà vu'' sur ce forum, n'est ce pas ?

    La courbe elliptique sur $\mathbb F_5$ que tu donnes n'est pas super-singulière, tout simplement.
  • samurai
    samurai
    oui forcément car le théorème est juste,

    j'ai compris une grosse incompréhension de ma part, je n'avais pas encore absorbé que

    en général, E[n] est un sous-groupe de $E(\bar{K})$ et non pas de $E(K)$

    j'ai pu effectivement constaté qu'il n'y a donc aucun point d'ordre 5 dans $E(F_5)$ mais il y a bien 4 points d'ordre 5 dans $E(F_{5^{2n}})$

    et donc que E[5] est bien le groupe cyclique d'ordre 5.

    Oui, Claude je me souviens que tu m'avais guidé quand j'avais posé des questions. merci encore.

    Ce que j'aime faire c'est m'amuser avec Sage, vérifier tous les théorèmes sur des exemples pour au moins comprendre les énoncés et saisir la beauté des résultats... les démonstrations, la plupart sont beaucoup sont trop compliquées pour moi
  • samurai
    samurai
    en page 35 du cours de Kraus, il y a l'exemple suivant:

    Exemple 7.16.

    Prenons pour E la courbe elliptique sur $F_p$ d'équation $y^2 = x^3 + x + 1$
    Le point P = (0, 1) appartient à $E(F_p)$.

    Avec $p = 10^10 + 19$, on trouve en une minute quinze secondes environ que m = 9999881780
    est le seul entier de Hp tel que mP = O, d’où |E(Fp)| = m. Vérifions que E(Fp) est cyclique. Pour cela, on constate que l’on a
    $m=2^2.5.7^2.17.600233$

    Le polynôme $X^3 + X + 1$ ayant une seule racine modulo p, le groupe E[2] n’est pas contenu dans $E(F_p)$, autrement dit, $E(F_p)$ ne contient pas un sous-groupe isomorphe à Z/2Z x Z/2Z. Puisque 7 ne divise pas p 1, le théorème 7.5 implique l’assertion.

    ----

    la remarque en gras "Le polynôme $X^3+X+1$ ayant une seule racine modulo p" est-elle d'ordre général, fait-elle référence à quelque chose ? ou bien est-ce juste une constatation (sans intérêt) qu'on puisse faire avec un calcul brutal en testant toutes les valeurs possibles de x ?

    je me suis posé la question en testant de petites valeurs de p, et en fait en allant jusque p=31, on trouve que 3 et 14 sont racines de ce polynôme dans $F_{31}$
    ou bien que pour $F_{47}$; on a 24 , 34 et 35 qui sont racines de ce polynôme
  • Poirot
    Poirot
    Je ne comprends pas ta question. C'est un argument permettant de mener le raisonnement que tu as écrit, que cherches-tu à savoir de plus ? Tu as trouvé toi-même des $p$ tels que ce polynôme admette des racines dans $\mathbb F_p$, donc tels que la courbe $E(\mathbb F_p)$ contienne des points d'ordre $2$.
  • samurai
    samurai
    moi je ne comprends pas la logique de Kraus.

    Il faut la remettre dans le contexte du paragraphe, que je n'ai pas recopié entièrement, à savoir de déterminer l'ordre de E, par une méthode brutale qui consiste à essayer toutes les valeurs m dans l'intervalle de Hasse, soit $4\sqrt{p}$ valeurs,

    mais si il faut aussi à côté essayer p valeurs pour vérifier qu'il n'y a qu'une seule racine modulo p ça compromet l'intérêt de la méthode non ?

    donc j'ai l'impression qu'il y a quelque chose qui m'échappe

    [dans le paragraphe suivant, il détaille l'algorithme baby step-giant step qui est plus sophistiqué]
  • claude quitté
    claude quitté
    $\def\F{\mathbb F}$Rebonjour Samourai

    A propos de quatrième ligne ``il faut aussi à côté essayer $p$ valeurs ...etc...". NON. Car il existe des algorithmes efficaces de factorisation sur $\F_p$. Qu'il suffit d'appliquer au polynôme $F(X) = X^3 + X + 1$.

    Et il existe des $p$ tels que le polynôme $X^3 + X + 1$ possède 3 racines distinctes : par exemple, $p = 47, 67$. Tu as parlé de $p = 31$, mais ce 31 est un peu spécial car $F = X^3 + X + 1$ est de discriminant $-31$, si bien que sur $\F_{31}$, $F$ admet deux racines dont une de multiplicité 2 (les racines sont $3$, racine simple et $14$ de multiplicité 2).

    Pour $p = 47$, le groupe $E(\F_p)$ n'est donc pas cyclique du fait de la 2-torsion $\Z/2\Z \times \Z/2\Z$. 
    [color=#000000]> p := 47 ;                         
> E := EllipticCurve([GF(p)| 1,1]) ;
> E ;
Elliptic Curve defined by y^2 = x^3 + x + 1 over GF(47)
> m := #E ;
> Factorization(m) ;
[ <2, 2>, <3, 1>, <5, 1> ]
[/color]
    Le groupe $E(\F_p)$ est d'ordre $m = 60 = 2^2 \times 3 \times 5$. Et le théorème de structure des groupes des courbes elliptiques sur les corps finis, puisque $2$ est le seul facteur de $m$ avec un exposant $\ge 2$, dit que
    $$
    E(\F_p) \simeq \Z/2\Z \times \Z/30\Z
    $$ 
    [color=#000000]> AbelianGroup(E) ;                 
Abelian Group isomorphic to Z/2 + Z/30
Defined on 2 generators
Relations:  2*$.1 = 0    30*$.2 = 0
[/color]

    Autre chose mais qui n'est pas le sujet de ta question. Quel est le statut modulo $p$ du polynôme $F(X) = X^3 + X + 1$ ? Si on met de côté $p = 31$, une réponse de normand : le nombre de racines dans $\F_p$ est 0 ou 1 ou 3.

    Et l'étude précise de cette question (apparemment simple) conduit à ``quelque chose d'explosif'' : corps des classes de Hilbert, groupe des classes d'idéaux, représentations galoisiennes, formes modulaires. Et j'en oublie peut-être. C'est à la fois super intéressant et super complexe.
  • gai requin
    gai requin
    Salut Claude,

    Si je me souviens bien, il faut d'abord déterminer le corps de classes de Hilbert de $\Q[\sqrt{-31}]$.
    Est-ce le corps des racines de $X^3+X+1$ ?
  • flipflop
    flipflop
    Hello,

    Si je me souviens bien, la coquine se cache ici : 
    sage: d = delta_qexp(100)
sage: e4 = 240*eisenstein_series_qexp(4,100)
sage: (d*e4)%31
q + 30*q^2 + 30*q^5 + 30*q^7 + q^8 + q^9 + q^10 + q^14 + 30*q^16 + 30*q^18 + 30*q^19
 + q^31 + q^35 + q^38 + 30*q^40 + 30*q^41 + 30*q^45 + 2*q^47 + 30*q^56 
+ 30*q^59 + 30*q^62 + 30*q^63 + q^64 + 2*q^67 + 30*q^70 + 30*q^71 + q^72 + q^80 + q^81 + q^82
 + q^90 + 29*q^94 + q^95 + 30*q^97 + O(q^100)

    Du coup, le polynôme $X^3+X+1$ est totalement scindé sur $\mathbb{F}_{47}$ :-D
  • gai requin
    gai requin
    :-D
    Oui, mais si on veut un résultat général (pour $p$ quelconque), il faut répondre à ma question et s'attaquer aux formes quadratiques binaires de discriminant $-31$. ;-)
  • samurai
    samurai
    merci de la réponse détaillée...

    ok donc pour l'existence d'un algorithme pour factoriser le polynôme dans Fp et l'existence de critères facilement calculable pour connaître le nombre de racines.

    le reste de la discussion m'échappe mais ça a l'air très très intéressant
  • flipflop
    flipflop
    Samurai, je répond au hors sujet, sorry,

    Hello Gai requin,

    Le résultat est général, tu prends un nombre premier et tu ajoutes $1$ au coefficient de $E_4 \times \Delta \pmod{31}$ en $q^p$ et tu obtient le nombre de racine (mod $31$) de $X^3+X+1 =0$ dans $\mathbb{F}_p$.

    Ensuite, si tu veux prouver de A à Z ce résultat, je n'ai absolument pas les capacités, je pense qu'on a déjà passé des milliers d'heures à essayé de comprendre les énoncés de quelques résultats, il faut une vie pour prouver ce petit truc (d'ailleurs c'est peux être faux) :-D ! Mais c'est quasi-certain qu'étudier les formes binaires de discriminant $-31$ est une étape !
  • gai requin
    gai requin
    Salut flipflop,

    Au contraire, tu es capable de tout ! ;-)
  • samurai
    samurai
    bonjour une question qui n'a pas de relation directe avec les courbes elliptiques, mais qui vient du même cours, à travers un exemple

    je voudrais juste être sûr d'un point:

    la formule donnée pour la racine carrée d'un nombre x modulo p, quand p est premier et que p = 5 modulo 8 dans l'exemple me semble générale,

    à savoir +/- $x^{((p+3)/8)}$

    mais bizarrement l'autre pdf distingue le cas p = 3 mod 4 et p=1 mod 4 alors que si ma compréhension est correcte,
    il y aurait en fait une formule exacte pour p=3 mod 4 à savoir $x^{((p+1)/4)}$
    et p=5 mod 8 vu plus haut

    et que le cas difficile reste p=1 mod 8 ??? où il faut utiliser l'algorithme de Shank. mais c'est alors bizarre que ça n'ait pas été mentionné sur le pdf... qui parle de l'utiliser dès le cas p= 1 mod 4 ???

    ou bien je me suis emmélé les pinceaux ?

    PS j'essaie de joindre des fichiers pdf au message , ils s'affichent dans l'aperçu mais ils ne sont pas sauvegardés à la publication....103578
    103580
    103584
    103586
    103588
    103590
  • samurai
    samurai
    J'ai cherché à reproduire les résultats de l'exemple 2.2.10 illustrant l'algorithme de Schoof sur SageMath mais je n'y suis pas arrivé, sans doute parce que j'ai mal compris les formules et donc mal codé...

    J'ai créé un post sur un autre forum https://math.stackexchange.com/questions/3715445/schoof-algorithm-working-on-an-example-with-sagemath pour ne pas polluer ici, si quelqu'un a la gentillesse de regarder, le code est sur le lien précédent.104112
    104114
    104116
  • samurai
    samurai
    Par rapport au post précédent.
    La réponse était triviale en fait, il y a une petite inexactitude dans le texte Schoof(3).png car il définit l'addition, il ne regarde que le cas de figure $x_1$ et $x_2$ égaux ou non pour la définition de $m$, et du coup il omet de distinguer le cas $(x_1=x_2 \text{ et } y_2 = -y_1)$ et $(x_1=x_2 \text{ et } y_1=y_2)$ et je n'ai bêtement pas fait attention au début.

    S    inon j'ai pas mal avancé dans le texte de Costello, je suis vers la fin.

    Il y a un petit point pourtant élémentaire que je n'arrive pas à démontrer concernant les pages 53-55.
    On considère une courbe elliptique $E$ sur un corps fini $F_q$ avec $q$ premier. On s'interesse au points de $r$-torsion $E[r]$ et on a besoin de considérer l'extension finie de degré minimal $k$ contenant $E[r]$ (considérons le cas $k\geq 2$). $k$ est le plus petit entier tel que $r$ divise $(q^k - 1)$.
    Ensuite on définit l'application Trace : $E \rightarrow E$ par $Tr(P) = P + \pi(P) + \pi^2(P) + \cdots + \pi^{k-1}(P),$ où $\pi$ est le Frobénius $(x,y)\mapsto(x^q,y^q)$ et l'application anti-trace $P \rightarrow P' = [k]P - Tr(P)$.
    Alors
    on définit $G_1 = E[r] \cap \ker(\pi - [1])$ et $G_2 = E[r] \cap \ker(\pi - [q])$

    $G_1$ est appelé le "base-field subgroup", et toute trace d'un point de $E[r]$ atterrit dans $G_1$ (je n'arrive à le démontrer).
    $G_2$ est le sous-groupe de trace 0. En effet, tout élément de $G_2$ a pour trace 0 (j'arrive à le démontrer).
    Par contre je n'arrive pas à voir comment démontrer la réciproque : que tout élément de $E[r]$ de trace 0 est dans $G_2$ ...
    Dans le chapitre suivant, l'auteur donne la définition et méthode de calcul de l'accouplement de Weil et de Tate, avec quelques exemples qui montrent leur propriété de bilinéarité.
    Par contre il ne donne pas la démonstration de leur bilinéarité.
    Apparemment c'est lié à la loi de réciprocité de Weil qu'il expose et donne des exemples, mais dont il ne donne pas la démonstration non plus.

    Si ces 2 points peuvent être au moins vaguement expliqués (intuition, heuristique) ou une référence vers un texte accessible.
    Pourriez-vous m'aider un peu ? Merci.
  • samurai
    samurai
    1) Montrons que si $Q = Tr(P) $ et $Q$ est dans $E[r]$, alors $Q$ est dans $G_1$.

    En effet $\pi (Q) = \pi (Tr(P)) = \pi(P) + \pi ^2 (P) + \pi^{k-1}P) + \pi^k (P)$,
    il suffit de prouver alors que $\pi^k(P) = P$ mais c'est le cas en revenant à la définition,
    $\pi ^k(P)= (x^{q^k},y^{q^k})=(x(x^{q^{k-1}},y(y^{q^{k-1}})=(x,y)=P$ car l'ordre de $P$ est $r $, et $r$ divise $q^{k-1}$.
    Pour prouver que l'ordre de $Q$ est aussi $r$, il suffit de remarquer que $\pi(P)$ et ses puissances sont aussi d'ordre $r$ car le [large]F[/large]robénius est un morphisme, et donc $Q$ étant la somme de tout ça est aussi d'ordre $r$.

    2) montrons que $G_2 = E[r] \cap\ker(\pi - [q])$ est bien le groupe de trace zéro.

    (i) Si $P$ est dans $G_2$, $Tr(P) = P+\pi(P) + \cdots+\pi^{k-1}(P) = [1+q+q^2+\cdots+q^{k-1}] P = [(q^k - 1) / (k-1)]P$ (somme géométrique),
    mais $r$ divise $q^k-1$ sans diviser $k-1$ donc le nombre entre crochets est divisible par $r$, l’ordre de $P$ donc $Tr(P)=0.$

    (ii) Réciproquement,
    soit $P \in E[r]$. si $Tr(P) =0$, alors ???
    NB. Trace et Anti_Trace sont des “projections” sur $G_1$ et $G_2$.

    [Georg Frobenius (1849-1917) prend toujours une majuscule. AD]
  • samurai
    samurai
    je sèche toujours sur la question...
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 10

10 Invités