Imprimer

Groupes cycliques et cryptographie

La cryptographie des courbes elliptiques est basée sur un groupe cyclique dans lequel nous considérons un problème dur de logarithme discret.  Comme déjà mentionné ailleurs, le problème du logarithme discret vient du fait que dans un groupe cyclique avec générateur G, il est facile de calculer A = Gn où n est un nombre naturel plus petit que l'ordre du groupe, mais qu'il est parfois très difficile de calculer n si on a A (et G).  n est le "logarithme discret" en base G de A dans le groupe cyclique.  Il nous faut bien sur un groupe cyclique, car il faut pouvoir atteindre chaque élément du groupe avec une puissance de G.  En fait, la dénomination de "logarithme" et la notion de "puissance" viennent de l'idée que la loi de composition du groupe est une "multiplication".  Mais si nous imaginons que notre groupe a une loi de composition "additive", alors notre exposant devient un multiple, et notre logarithme devient une division.  Nous pourrions appeler le problème alors un problème de "division discrète dure".  Pas tous les problèmes de division sont durs !  Par exemple, la division dans un corps est souvent assez facile à calculer.  La raison historique pour laquelle nous avons utilisé souvent le groupe multiplicatif d'un corps modulaire, est qu'il est connu qu'on ne peut pas avoir des "corps triples", c'est à dire, une loi additive, une loi multiplicative, et une loi exponentielle de telle façon que l'addition et la multiplication forment un corps, et que la multiplication et l'exponentiation formeraient un autre corps.  Ainsi, en prenant le groupe de la loi multiplicative dans un corps, on se protège contre le "logarithme" comme division dans un groupe.  Ainsi, le groupe multiplicatif du corps modulaire était relativement sûr.   En plus, le groupe modulaire multiplicatif d'un corps modulaire premier est cyclique, donc c'est vraiment un environnement idéal pour un problème de logarithme dur.  Effectivement, le groupe multiplicatif modulaire est souvent utilisé à cette fin.  Cependant, comme ce groupe est très étudié, et qu'il possède beaucoup de propriétés mathématiques, beaucoup de progrès est fait dans la solution du problème du logarithme.  Ils sont toujours utilisables, mais il faut utiliser des ordres très grands pour avoir une cryptographie sûre.   L'attaque la plus efficace et générale de factorisation, et les méthodes les plus efficaces et générales du problème de logarithme discret dans un groupe modulaire sont liés et le niveau de sécurité en fonction de l'ordre du groupe est:

nsécurité = (1.923*(b*ln(2))1/3 ( ln(b*ln(2)) )2/3 / ln(2)

pour un ordre de groupe exprimé en b bits.  On peut dire grosso modo que leur sécurité va en b1/3.

Ceci donne lieu à la liste standard des ordres de groupe (log2 de cet ordre, le nombre de bits dans la clé) pour obtenir un niveau de sécurité:

niveau sécurité (bits) ordre groupe (bits)
80 1024
112 2048
128 3072
192 7680
256 15360

Pour des niveaux de sécurité élevés, les ordres de groupes (et la taille des clés) deviennent grandes.

On peut construire d'autres groupes, et la famille des groupes elliptiques est une telle série de groupes.  Sur le plan algébrique, tous les groupes cycliques sont isomorphes entre eux et sont isomorphes à Zn,+.  Ainsi, n'importe quel groupe cyclique A qu'on utilisera est en faite l'utilisation d'un isomorphisme f entre Zn et A.  f(1) = G sera le générateur du groupe, et f(n) = Gn.  Comme les éléments du groupe A sont représentés par des entiers, h(U) = m, nous avons essentiellement que notre isomorphisme est une fonction numérique compliquée g(n) = h(f(n)) = h(Gn) = m, tel que:

En d'autres termes: même si l'isomorphisme induit, sur le groupe G, un anneau et même une structure de corps, nous ne connaissons que l'opération d'addition et nous ne savons pas comment implémenter la division dans l'anneau sans "retourner".  Si f est considéré comme une fonction a sens unique, nous ne pouvons pas retourner.

L'élément cryptographique essentiel n'est donc pas la structure du groupe en lui-même, mais plutôt le fait que l'isomorphisme entre Zn,+ et le groupe en question est une fonction en sens unique.  Il est généralement accepté que les groupes elliptiques ont un isomorphisme plus "sens unique" que les groupes multiplicatifs des corps modulaires, même s'ils sont tous identiques sur le plan algébrique.

Définition de groupes elliptiques

Courbes elliptiques réelles

Les courbes elliptiques sont introduites par discrétisation de courbes elliptiques réelles, qui sont simplement des courbes ayant l'équation suivante:

y2 = x3 + a x + b

de la même façon qu'une ligne droite est définie par une équation:

y = a x + b

et qu'un cercle est défini par:

y2 = R2 - x2

et qu'une ellipse est définie par:

y2 = R2 - a x2

en d'autres termes, c'est juste une courbe dans le plan avec une équation donnée.  Souvent, il y a une condition supplémentaire posée aux paramètres a et b:

4 a3 + 27 b2 ne doit pas être zéro.

Dans l'équation de la courbe elliptique, il y a donc deux paramètres a et b, qui déterminent la forme exacte de la courbe.  Elle a des propriétés remarquables:

  1.  Si nous prenons deux points au hasard sur la courbe, et nous construisons une droite passant par ces deux points, alors cette droite va couper la courbe dans un troisième point si la droite n'est pas une verticale
  2. la courbe est symétrique autour de l'axe x: pour tout point avec une valeur positive de y, il y a aussi un point avec la valeur négative de y.

Cela peut paraître une propriété banale, mais en fait, cela nous permet d'associer un point à chaque pair de points.  On prend les deux points, on trouve le troisième à l'intersection de la droite, et on passe de l'autre coté de l'axe X.  En d'autres termes, si nous avons deux points P et Q sur la courbe, nous pouvons associer un troisième point R = s(P,Q).  s est symétrique: R = s(P,Q) = s(Q,P), car c'est la même droite qui passe par P et Q, ou par Q et P.

Définissons maintenant le point "opposé" de R, qu'on appelle "- R", et qui est le point miroir dans l'axe X de R.

Alors, nous avons:

C'est ce que nous attendions si s(P,Q) était une opération binaire et commutative comme "+":

Il nous faut introduire encore un élément neutre.  Ce n'est pas un point sur la courbe géométrique, et nous allons donc introduire un nouveau point "zéro" Z qui est le résultat quand nous combinons un point et son inverse, ce qui donne lieu à une droite verticale qui ne coupe pas la courbe en un troisième point.  s(R,-R) n'était donc pas défini jusque là, et nous  définissons que s(R,-R) = Z.  De la même façon, nous définissons que s(R,Z) = R et que s(Z,R) = R.  Aussi, s(Z,Z) = Z.

Ainsi, nous avons donc une loi de composition s(_ , _) sur les points de la courbe (et Z) qui est:

mais on peut en plus démontrer que cette loi de composition est associative: s(P,s(Q,R)) = s(s(P,Q),R)

Ainsi, cette association de points sur la courbe est donc une loi de groupe commutatif !

Le calcul algébrique des points d'intersection (en miroir) est le suivant:

  1. si xP est différent de xQ: Calculez s = (yP - yQ) / (xp - xQ), et en suite: xR = s2 - xP - x et yR = - yP - s(xR - xP)
  2. si xP = xQ et si yP = - yQ alors le résultat est zéro
  3. si xP = xQ et si yP = yQ != 0 (donc P = Q)  alors calculons s = (3 xP2 + a)/(2 yP) et xR = s2 - 2 xP et yR = - yP - s(xR - xP)
  4. si xP = xQ et si yP = yQ = 0 (donc P = Q) alors le résultat est zéro
  5. si un des éléments (Q ou P) est zéro, alors le résultat est l'autre élément (P ou Q)

Notez qu'un point dans le groupe peut être zéro (alors il n'a pas de x et y), ou il n'est pas zéro, et alors il possède des coordonnées x et y.

Comme ces expressions sont purement algébriques, faites avec des additions et des multiplications, ces équations et la définition de la courbe peut s'appliquer dans n'importe quel corps commutatif, pas seulement dans le corps des nombres réels.  Comme les expressions pour des propriétés initialement géométriques sont aussi purement algébriques, elles sont donc valables dans n'importe quel corps commutatif.  Ainsi, la loi de groupe des points de la courbe reste aussi valable.

Groupes elliptiques discrets sur un corps fini F

Considérons le corps (commutatif) F, et considérons des couples dans F x F.  Considérons l'ensemble de ces couples qui satisfait une équation de courbe elliptique avec des paramètres a et b choisis dans F.   Cet ensemble est bien défini.  Ajoutons un élément supplémentaire à cet ensemble, qu'on appelle "zéro".  Nous appelons cela l'ensemble étendu E.  La loi de composition comme nous l'avons vu plus haut définit une loi de groupe commutatif sur cet ensemble E: le groupe elliptique sur F, avec les paramètres a et b.

Si F est un corps fini, et E est un groupe elliptique sur F avec paramètres a et b, alors on peut se demander combien d'éléments il y a dans E.  Le théorème de Hasse nous indique que si q est l'ordre du corps F, alors le groupe elliptique doit avoir un ordre qui n'est pas très différent de q: la déviation est au plus 2 sqrt(q) de q.  Ainsi, si q est très grand, alors tout groupe elliptique est aussi très grand et d'ordre comparable à q.

Sous-groupes cycliques

Pour des besoins cryptographiques, nous n'avons pas seulement besoin d'un groupe: il nous faut un "isomorphisme compliqué" entre Zp,+ et un sous-groupe cyclique, avec p un grand nombre.  Dans un groupe fini, on peut toujours construire des sous-groupes cycliques, en choisissant un élément du groupe et en considérant l'ensemble de tous ces multiples/puissances (dépendant du choix d'appeler la loi de groupe une "addition" ou une "multiplication").  Mais le problème qui se pose, est de savoir si l'ordre du groupe associé (p donc) sera grand, et si l'isomorphisme est vraiment en "sens unique" (c.a.d. qu'il n'y ait pas de propriétés mathématiques qu'on puisse inverser l'isomorphisme dans la pratique).

Il est intéressant de savoir que le groupe elliptique E lui-même, sur un corps fini, est un groupe cyclique, ou un produit de deux groupes cycliques.  Mais attention, ces groupes peuvent bien avoir des sous-groupes cycliques !  En choisissant un élément du groupe, et en considérant tous ces multiples, on court le danger d'avoir choisi sans le savoir, un petit sous-groupe !

Sous-groupe cyclique d'un groupe elliptique, et cryptographie

Supposons que nous avons choisi un corps F, et une courbe elliptique (en choisissant des coefficients a et b dans F) ; nous avons donc notre groupe elliptique E(F,a,b).  Supposons que nous avons aussi choisi un générateur g dans E(F,a,b): ceci nous définit donc un sous-groupe cyclique G de E(F,a,b).  Si ce sous-groupe est d'ordre premier, alors nous savons que nous n'avons pas de sous-groupe de notre groupe cyclique.  Il n'y a qu'une seule façon de s'en assurer: c'est de faire en sorte que G soit égal à E(F,a,b), ce qui est le cas si l'ordre de E(F,a,b) lui-même, N, est un nombre premier.

Ainsi, si l'ordre de E(F,a,b) est un nombre premier, tout élément de E(F,a,b) sera un bon générateur et le groupe cyclique sera le groupe elliptique en entier.

A priori, le niveau de sécurité en bits du groupe cyclique d'ordre premier N est au plus 1/2 log2 N, parce que tous ces problèmes de logarithme discret sont attaquables par une variante de Pollard's rho, ce qui réduit le nombre d'essais de N en sqrt(N).  Il est généralement accepté que la plupart des groupes elliptiques ont effectivement ce niveau de sécurité, car pour la plupart d'entre eux, on ne connaît pas d'attaque plus puissante.  C'est la motivation principale d'utiliser des groupes elliptiques: que le niveau de sécurité est accepté d'être du niveau de log(sqrt(N)), ce qui est bien plus favorable que le problème du logarithme discret dans un groupe modulaire ou un problème de factorisation, où, comme nous avons mentionné, le niveau de sécurité est de (log(N))1/3.

Ainsi, il semble donc qu'il suffit de trouver une courbe elliptique avec un ordre N qui est premier, sur un corps fini F.  Mais cela ne suffit pas, car il y a des réductions connues, qui réduisent le groupe elliptique en un groupe modulaire multiplicatif d'un corps Fq, dans les cas suivants:

Ainsi, la construction d'un problème sûr de logarithme discret dans un sous-groupe de groupe elliptique demande des précautions du corps Fp, et de la courbe (a et b).  Le générateur n'a pas beaucoup d'importance si l'ordre N de la courbe est premier.  Il faut éviter les conditions ci-dessus.  Si on n'est pas certain de pouvoir assurer ces conditions, il faut s'abstenir de vouloir inventer sa propre courbe, mais alors il faut faire confiance à l'organisme qui publie des courbes "fiables", pour en utiliser une qui est connue.  On peut toujours soupçonner que cet organisme a choisi une courbe bien particulière avec une porte dérobée dedans.

D'une certaine façon, il peut faire peur qu'on ait trouvé deux familles de courbes "faibles", dans lesquelles le problème du logarithme discret se réduit à un problème dans un groupe modulaire multiplicatif dont nous savons qu'il peut être résolu avec un niveau de sécurité (log(N))1/3.  Peut-être qu'il y ait d'autres familles du genre, dont nous n'avons pas encore découvert l'existence, ou dont l'existence n'est pas publiquement connue.  La seule chose qui peut nous rassurer est que ces deux familles sont connues depuis plus que 30 ans, et que depuis ce moment, aucune autre famille a été trouvée publiquement, malgré beaucoup de recherche publique dans le domaine.  L'idée est alors que si de telles familles existent, leur représentants doivent être rare parmi les bons candidats d'aujourd'hui.  Ainsi, si nous sélectionnons une bonne courbe "au hasard", il y a peu de chances qu'elle sera par hasard vulnérable à une attaque d'une nouvelle famille dont la densité de représentants est faible.  Mais pour que ce "choix au hasard" d'une courbe publiée soit crédible, il faut que ce hasard soit prouvable. et n'est pas un choix très précis, mais caché.

Cette dernière partie est un aspect critique dans certaines courbes standardisées: l'aspect "aléatoire" n'est pas démontré.  Ainsi, la possibilité existe que ces courbes ont été sélectionnées soigneusement avec une faiblesse cachée dedans.  D'un autre coté, certaines de ces courbes ont été publiées il y a 20 ans, et aucune autre famille de courbes faibles a été découverte depuis ; ainsi, la probabilité qu'il y avait des gens, il y a 20 ans, qui avaient connaissance d'une courbe qui souffre d'une faiblesse qui n'est pas publiquement connue, devient de plus en plus faible.  Si on est, cependant, paranoïde sur ce domaine, on peut toujours générer sa propre courbe, mais alors il faut bien être conscient de ce qu'on fait.

Code: opérations élémentaires sur des courbes elliptiques

Nous voulons rappeler le cadre général des Exemples de code

Pour commencer, nous n'allons pas générer nous-même une bonne courbe elliptique cryptographique avec générateur, car cela implique le calcul de l'ordre N du groupe cyclique, ce qui est compliqué pour des grands groupes.  Ainsi, dans les exemples qui vont suivre, nous allons assumer que nous avons déjà un groupe elliptique (un nombre premier qui détermine le corps modulaire, une courbe donnée (les paramètres a et b) et un générateur.

Nous introduisons deux nouveaux types:

/* "elliptic" is a structure that contains a number and a boolean that tells us whether
   the number is "zero" or not, because elliptic curves have a non-number neutral element */
typedef struct digitos {bool zero ; number x ; number y;} elliptic;

/* "ellipcurve" is a structure that contains the parameters of an elliptic curve on a modular field */
typedef struct digitossos {number prime ; number a ; number b ; elliptic generator; } ellipcurve;

Un "elliptic" est un record qui contient deux "nombres", mais aussi un flag qui nous dit si le point est l'élément neutre ("zéro") - au quel cas les nombres n'ont pas de signification - ou non.  Une courbe elliptique "ellipcurve" contient un nombre qui est le nombre premier, deux nombres qui sont les coefficients a et b, et un point elliptique (le générateur).  

Nous avons besoin d'une fonction auxiliaire qui copie un point elliptique en un autre:

void ellipcopy(elliptic* orig, elliptic* copy)
/* copies an elliptic point into another one */
  {
  int i;
  copy->zero = orig->zero;
  for (i = 0 ; i < nofdigits ; i++)
    {
    copy->x.digit[i] = orig->x.digit[i];
    copy->y.digit[i] = orig->y.digit[i];
    }
  }  // end ellipcopy 

L'algorithme fondamental est celui qui fait la somme de deux points elliptiques:

void ellipsum(ellipcurve* mycurve,elliptic* a, elliptic* b, elliptic* sum)
/* calculates the sum of two elliptic points on a given curve */
  {
  number s;
  number zeero;
  number two;
  number three;
  number xa2;
  number xa2t3;
  number xa2t3pa;
  number yat2;
  number invyat2;
  number xamxs;
  number stxamxs;
  number s2;
  number xat2;
  number yamyb;
  number xamxb;
  number invxamxb;
  number s2mxa;
  number oldmodulo;
  unsigned int i;
  
  // we apply the prime number of the modular field of the curve
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = mycurve->prime.digit[i];
    }
  makebig(0,&zeero);
  if (a->zero && b->zero)
    {
    // we have zero plus zero
    sum->zero = true;
    }
  else if (a->zero)
    {
    // a is zero, so the sum is b
    ellipcopy(b,sum);
    }
  else if (b->zero)
    {
    // b is zero, so the sum is a
    ellipcopy(a,sum);
    }
  else if (isbigger(&(a->x),&(b->x)) == 0)
    {
    // both points a and b are on a vertical line
    // there are only two possibilities: a = b != 0 or a = -b
    if (isbigger(&(a->y),&(b->y)) == 0 && isbigger(&(a->y),&zeero) != 0)
      {
      // a is b, so we have 2a
      sum->zero = false;
      timesnum(&(a->x),&(a->x),&xa2);
      makebig(2,&two);
      makebig(3,&three);
      timesnum(&three,&xa2,&xa2t3);
      sumnum(&xa2t3,&(mycurve->a),&xa2t3pa);
      timesnum(&two,&(a->y),&yat2);
      inversenum(&yat2,&invyat2);
      timesnum(&xa2t3pa,&invyat2,&s);
      timesnum(&s,&s,&s2);
      timesnum(&two,&(a->x),&xat2);
      difnum(&s2,&xat2,&(sum->x));
      difnum(&(a->x),&(sum->x),&xamxs);
      timesnum(&xamxs,&s,&stxamxs);
      difnum(&stxamxs,&(a->y),&(sum->y));
      }
    else
      {
      // a is minus b, so we have zero
      sum->zero = true;
      }
    }
  else
    {
    // a and b are different, not on a vertical line, and not zero
    sum->zero = false;
    difnum(&(a->x),&(b->x),&xamxb);
    difnum(&(a->y),&(b->y),&yamyb);
    inversenum(&xamxb,&invxamxb);
    timesnum(&yamyb,&invxamxb,&s);
    timesnum(&s,&s,&s2);
    difnum(&s2,&(a->x),&s2mxa);
    difnum(&s2mxa,&(b->x),&(sum->x));
    difnum(&(a->x),&(sum->x),&xamxs);
    timesnum(&xamxs,&s,&stxamxs);
    difnum(&stxamxs,&(a->y),&(sum->y));  
    }
  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  } // end ellipsum
 

Finalement, nous utilisons la technique du carré-multiplier, variante de la puissance modulaire, pour implémenter la multiplication d'un point elliptique avec un nombre.  Le nombre est transformé en représentation binaire, et cette représentation est utilisée pour savoir s'il faut doubler ("carré" en langage multiplicatif) le point actuel, ou s'il faut aussi ajouter le point original ("multiplier" dans le langage multiplicatif).

void elliptictimes(ellipcurve* mycurve, elliptic* x, number* y, elliptic* xy)
/* number x to the power y */
  {
  int i;
  int j;
  elliptic p;
  elliptic s;
  number zero;
  number half;
  number full;
  int uneven;
  int bitsequence[basisbits * nofdigits];
  int bitcounter;
  xy->zero = true;
  for (i = 0 ; i < nofdigits ; i++)
    {
    zero.digit[i] = 0;
    full.digit[i] = y->digit[i];
    }
  bitcounter = 0;
  /* we find the binary representation of the power */
  do
    {
    divide2(&full,&half,&uneven);
    bitsequence[bitcounter] = uneven;
    for (i = 0 ; i < nofdigits ; i++)
      {
      full.digit[i] = half.digit[i];
      }
    bitcounter++;
    }
  while (isbigger(&half,&zero) > 0);
  /* the square-and-multiply algorithm */
  for (i = bitcounter - 1 ; i >= 0 ; i--)
    {
    ellipsum(mycurve,xy,xy,&s);  // we "square"
    ellipsum(mycurve,&s,x,&p);   // we "multiply"
    if (bitsequence[i] == 1)
      {
      ellipcopy(&p,xy);
      }
    else
      {
      ellipcopy(&s,xy);
      }
    }
  }  // end elliptictimes
 

Mais avant de pouvoir envisager ajouter deux points sur une courbe, ou de multiplier un point sur la courbe avec un nombre, il faut déjà avoir un point sur la courbe.  Le théorème de Hasse indique que le nombre de points dans un groupe elliptique (l'ordre N du groupe) sur un corps modulaire avec un nombre premier p, n'est pas très loin de p (la déviation est de l'ordre de la racine carrée de p).  Mais les points elliptiques sont dans le "plan" de p x p points, ce qui veut dire qu'un x et un y au hasard on très peu de chances d'appartenir à la courbe.  Heureusement, il n'est pas très difficile de vérifier si un nombre donné x est le carré d'un autre nombre dans un corps modulaire: il suffit de calculer le symbole de Legendre.  Un nombre qui est le carré d'un autre nombre est appelé un résidu quadratique.  Le symbole de Legendre d'un nombre x, est  x(p-1)/2. Si le résultat est égal à 1, alors x est un résidu quadratique ; sinon, il sera -1.  Le cas particulier où x est 0, donne 0.  Il est facilement compris en considérant le petit théorème de Fermat: si  x = a2 alors x(p-1)/2 = a(p-1) = 1.

Le code qui met cela en œuvre suit:

int legendresymbol(number* prime,number* a)
  /* implementation of the Legendre symbol that verifies whether a
     is a square residue in the modular field with prime */
  {
  unsigned int i;
  number oldmodulo;
  number zero;
  number one;
  number mone;
  number pm1d2;
  number blegendre;
  int rr;
  int result;

  // we apply the prime number
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = prime->digit[i];
    }
  makebig(0,&zero);
  makebig(1,&one);
  difnum(&zero,&one,&mone);
  divide2(&mone,&pm1d2,&rr);
  result = 15;
  if (rr != 0)
    {
    printf("legendresymbol: failure !\n");
    result = 2;
    }
    if (result == 15)
    {
    power(a,&pm1d2,&blegendre);
    if (isbigger(&blegendre,&one) == 0)
      {
      result = 1;
      }
    else if(isbigger(&blegendre,&zero) == 0)
      {
      result = 0;
      }
    else if (isbigger(&blegendre,&mone) == 0)
      {
      result = -1;
      }
    else
      {
      printf("legendresymbol: internal inconsistency!\n");
      result = 2;
      }
    }
  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  return result;
  }

Il faut noter que cette fonction nous indique si un nombre est le carré d'un autre ou pas, mais cela ne veut pas dire que nous connaissons ce nombre (cette "racine carrée").  Trouver les racines carrées si elles existent, est un peu plus sophistiqué, mais il y a un algorithme connu, l'algorithme de Cipolla, qui fait exactement cela.

L'algorithme a besoin d'un nombre a, tel que a2 - x n'est, justement, pas un résidu quadratique.  Il n'y a pas d'autre méthode que d'essayer pour trouver un tel a, mais ces a ne sont pas rares, donc on trouve vite, par une boucle d'essai et erreur, un tel a.  Quand nous détenons un a, nous considérons le "non-nombre" w = sqrt(a2 - x) et nous obtenons une sorte d'extension algébrique si nous ajoutons ce non-nombre au corps, de la même façon qu'ajouter sqrt(-1) = i qui est un non-réel, aux nombres réels, pour obtenir une extension algébrique (r + i s) avec deux nombres réels r et s, pour obtenir les nombres complexes.  Ainsi, nous allons donc considérer les nombres u + w.v avec u et v des nombres dans le corps modulaire, et tous les règles algébriques, avec  w2 = a2 - x.

L'algorithme de Capolla consiste simplement en le calcul de  (a + w)(p+1)/2. Ce nombre dans l'algèbre étendue est postulé ne pas contenir une composante en w, et est donc un nombre dans le corps modulaire: une des racines carrées de x.  L'autre racine est bien sûr moins ce nombre.  Pour calculer cette puissance dans l'algèbre étendue, nous appliquons un algorithme de carré et multiplier, avec les règles suivantes:

Voici son implémentation:

void cipolla(number* prime, number* square, number* root1, number* root2)
  {
  int i;
  unsigned int j;
  number oldmodulo;
  number a;
  number a2;
  number a2msquare;
  number zero;
  number one;
  number two;
  number pm1;
  number pm1d2;
  int rr;
  number pp1d2;
  number half;
  number full;
  int uneven;
  int bitsequence[basisbits * nofdigits];
  int bitcounter;
  number root1u;
  number root1v;
  number root1u2;
  number root1v2;
  number root1v2w2;
  number root1uv;
  number root1svw2;
  number root1sua;
  number root1sva;
  number su;
  number sv;
  number pu;
  number pv;
 
  // first, we check whether "square" is a quadratic residue
  if (legendresymbol(prime,square) != 1)
    {
    printf("cipolla: Trying to find a square root of a square non-residue !\n");
    return;
    }
  // we apply the prime number
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = prime->digit[i];
    }  
  // finding a non-square residue a^2 - n
  do
    {
    randomgenmod(prime,&a);
    timesnum(&a,&a,&a2);
    difnum(&a2,square,&a2msquare);
    }
  while (legendresymbol(prime,&a2msquare) != -1);
  makebig(0,&zero);
  makebig(1,&one);
  makebig(2,&two);
  difnum(&zero,&one,&pm1);
  divide2(&pm1,&pm1d2,&rr);
  sumnum(&pm1d2,&one,&pp1d2);

  // preparing the square and multiply algorithm in F_p x F_p
  for (i = 0 ; i < nofdigits ; i++)
    {
    full.digit[i] = pp1d2.digit[i];
    }
  bitcounter = 0;
  /* we find the binary representation of the power */
  do
    {
    divide2(&full,&half,&uneven);
    bitsequence[bitcounter] = uneven;
    for (i = 0 ; i < nofdigits ; i++)
      {
      full.digit[i] = half.digit[i];
      }
    bitcounter++;
    }
  while (isbigger(&half,&zero) > 0);
  makebig(1,&root1u);
  makebig(0,&root1v);
 
  /* we will now find (a + 1 sqrt(a^2 - square))^(pp1d2)
  /* the square-and-multiply algorithm */
  for (i = bitcounter - 1 ; i >= 0 ; i--)
    {
    // we calculate root1^2 which is (u^2 + v^2*w^2, 2*u*v)
    timesnum(&root1u,&root1u,&root1u2);
    timesnum(&root1v,&root1v,&root1v2);
    timesnum(&root1v2,&a2msquare,&root1v2w2);
    sumnum(&root1u2,&root1v2w2,&su);
    timesnum(&root1u,&root1v,&root1uv);
    timesnum(&two,&root1uv,&sv);
    // we calculate s*(a,1) which is (sv*w^2 + su*a,su + a*sv)
    timesnum(&sv,&a2msquare,&root1svw2);
    timesnum(&a,&su,&root1sua);
    sumnum(&root1svw2,&root1sua,&pu);
    timesnum(&a,&sv,&root1sva);
    sumnum(&root1sva,&su,&pv);
    // we pick the right one for this bit
    if (bitsequence[i] == 1)
      {
      for (j = 0 ; j < nofdigits ; j++)
        {
        root1u.digit[j] = pu.digit[j];
        root1v.digit[j] = pv.digit[j];
        }
      }
    else
      {
      for (j = 0 ; j < nofdigits ; j++)
        {
        root1u.digit[j] = su.digit[j];
        root1v.digit[j] = sv.digit[j];
        }
      }
    }
  /* now we test whether the v-part of the root has become 0 */
  if (isbigger(&root1v,&zero) != 0)
    {
    printf("cipolla: inconsistency: v-part non-zero !\n");
    }

  /* root1u is one of the roots, -root1u is the other one */
  sumnum(&zero,&root1u,root1);
  difnum(&zero,&root1u,root2);
  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }
  }  // end cipolla

Il faut seulement appeler cette fonction quand la racine carrée existe, c.a.d. il faut seulement appeler cette fonction sur un résidu quadratique.  Il faut donc calculer le symbole de Legendre avant de considérer appeler cette fonction. 

Ceci complète notre boîte à outils pour calculer le y correspondant potentiel à un x donné sur une courbe elliptique:

int ellipyfromx(ellipcurve* mycurve,number* x,number* y1,number* y2)
  /* calculates the two possible y-values for a given x-value on the curve
     if ever that x-value is possible.  The integer return value gives us the number
     of y-values (0,1 or 2) that are returned */
  {
  int i;
  number oldmodulo;
  number x2;
  number x3;
  number ax;
  number axpb;
  number yp2;
  int leg;
  int result;
 
  // we apply the prime number
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = mycurve->prime.digit[i];
    }  
  // we calculate the y^2 corresponding to the x for the given curve
  timesnum(x,x,&x2);
  timesnum(&x2,x,&x3);
  timesnum(&(mycurve->a),x,&ax);
  sumnum(&ax,&(mycurve->b),&axpb);
  sumnum(&x3,&axpb,&yp2);
  leg = legendresymbol(&(mycurve->prime),&yp2);
  if (leg == -1)
    {
    result = 0;
    }
  else if (leg == 0)
    {
    result = 1;
    makebig(0,y1);
    makebig(0,y2);
    }
  else if (leg == 1)
    {
    cipolla(&(mycurve->prime),&yp2,y1,y2);
    result = 2;
    }
  else
    {
    result = -1;
    printf("ellipyfromx: inconsistency ! \n");
    }
    

  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }
  return result;
  }  // end ellipyfromx

Le code s'explique lui-m^eme: nous calculons u = x3 + ax + b,nous vérifions si u est bien un résidu quadratique.  Si c'est le cas, nous calculons les deux racines carrées de u, qui sont les deux valeurs possible de y du point sur la courbe elliptique avec un x donné ; si ce n'est pas le cas, alors x n'est pas la valeur de x d'un point sur la courbe.  Il y a le cas particulier où u = 0, au quel cas il n'y a qu'un seul y possible: y = 0.

Finalement, nous présentons un générateur "jouet" de courbe elliptique.  Nous mettons en garde: ce générateur de courbe ne vérifie pas si la courbe est cryptographiquement faible, ou si elle a des petits sous-groupes cycliques.  Ce générateur sert seulement à nous donner des courbes cohérentes pour tester des algorithmes cryptographiques, dans la vérification automatique de la cohérence des résultats.

void toycurve(ellipcurve* mycurve,int nbits)
  /* inefficient algorithm to generate small elliptic curves */
  /* impossible to use for real crypto */
  {

  number oldmodulo;
  number zero;
  number one;
  number two;
  number nbitsbig;
  number allbits;
  number ranlim;
  int i;
  int yok;
  number dummy;

  /* we put the current modulus away and set the modulus to its maximum */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = basis - 1;
    zero.digit[i] = 0;
    one.digit[i] = 0;
    two.digit[i] = 0;
    }
  one.digit[0] = 1;
  two.digit[0] = 2;
  /* we calculate the highest possible number in agreement with our number of bits (minus 1) */
  makebig(nbits-1,&nbitsbig);
  power(&two,&nbitsbig,&allbits);
  /* we just find a prime number of the order of n bits */
  do
    {
    randomgenmod(&allbits,&ranlim);
    findnextprimerabin(&ranlim,&(mycurve->prime),10);
    }
  while (isbigger(&(mycurve->prime),&allbits) == 1);

  /* we generate a random curve (random a and b) */
  randomgenmod(&(mycurve->prime),&(mycurve->a));
  randomgenmod(&(mycurve->prime),&(mycurve->b));
 
  /* we now have to find a random point on the curve.
     For this, we have to generate a random x value, and
     verify whether the corresponding y^2 = x^3 + ax + b
     is a square residue */
  mycurve->generator.zero = false;
  do
    {
    randomgenmod(&(mycurve->prime),&(mycurve->generator.x));
    yok = ellipyfromx(mycurve,&(mycurve->generator.x),&(mycurve->generator.y),&dummy);
    }
  while (yok < 2);

  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }
  }  // end toycurve

Nous répétons que ce générateur va nous donner un corps modulaire, une courbe elliptique aléatoire et un générateur de sous-groupe cyclique aléatoire, mais aucune vérification de la solidité cryptographique est faite pour éliminer tous les cas faibles, ce qui peut donc donner lieu à des applications très vulnérables.