Appendix A. Deterministic Generation

Appendix A. Génération déterministe

Cette section décrit la procédure ayant servi à générer les courbes ci-dessus ; elle définit notamment comment générer le paramètre A de la courbe de Montgomery y^2 = x^3 + A*x^2 + x. Cette procédure vise à être aussi objective que possible afin qu'il soit clair qu'aucune considération douteuse n'a influé sur le choix de la courbe. L'entrée du processus est p, le premier définissant le corps sous-jacent. La taille de p détermine le coût du calcul d'un logarithme discret dans le groupe de la courbe elliptique, et le choix d'un p précis dépend de nombreuses contraintes d'implémentation. Les performances de la courbe sont dominées par les opérations dans GF(p) ; le choix soigneux d'une valeur permettant des réductions efficaces sur l'architecture visée est donc crucial. Le présent document ne prétend pas exposer l'ensemble de ces contraintes.

La valeur (A-2)/4 intervient dans plusieurs formules d'arithmétique sur les points de la courbe. Pour des raisons de simplicité et de performance, il est souhaitable que cette constante soit petite, autrement dit qu'on choisisse A de sorte que (A-2) soit un petit entier divisible par quatre.

Pour chaque courbe à un niveau de sécurité donné :

1. La trace de Frobenius NE DOIT PAS appartenir à {0, 1}, afin d'exclure les attaques décrites dans [smart], [satoh] et [semaev], comme dans [brainpool] et [safecurves].

2. Degré MOV [reducing] : le degré d'immersion DOIT être strictement supérieur à (order - 1) / 100, comme dans [brainpool] et [safecurves].

3. Discriminant CM : le discriminant D DOIT être supérieur à 2^100, comme dans [safecurves].

A.1. p = 1 mod 4

Pour les nombres premiers congrus à 1 modulo 4, les cofacteurs minimaux de la courbe et de sa courbe tordue quadratique sont soit {4, 8}, soit {8, 4}. Nous choisissons une courbe dont les cofacteurs sont {8, 4}, de sorte que les algorithmes qui tiennent compte du cofacteur n'aient pas à vérifier les points situés sur la courbe tordue, le cofacteur de celle-ci étant le plus petit des deux.

Pour générer la courbe de Montgomery, on détermine la plus petite valeur positive de A telle que A > 2, que (A-2) soit divisible par quatre et que les cofacteurs aient les valeurs voulues. La fonction find1Mod4 du script Sage ci-dessous renvoie cette valeur pour p donné :

def findCurve(prime, curveCofactor, twistCofactor):
    F = GF(prime)

    for A in xrange(3, int(1e9)):
        if (A-2) % 4 != 0:
          continue

        try:
          E = EllipticCurve(F, [0, A, 0, 1, 0])
        except:
          continue

        groupOrder = E.order()
        twistOrder = 2*(prime+1)-groupOrder

        if (groupOrder % curveCofactor == 0 and
            is_prime(groupOrder // curveCofactor) and
            twistOrder % twistCofactor == 0 and
            is_prime(twistOrder // twistCofactor)):
            return A

def find1Mod4(prime):
    assert((prime % 4) == 1)
    return findCurve(prime, 8, 4)

Génération d'une courbe pour p = 1 mod 4

A.2. p = 3 mod 4

Pour un premier congru à 3 modulo 4, les cofacteurs de la courbe et de la courbe tordue quadratique peuvent tous deux valoir 4, ce qui est minimal. Nous retenons donc la courbe présentant ces cofacteurs et la plus petite valeur positive de A telle que A > 2 et (A-2) divisible par quatre. La fonction find3Mod4 du script Sage suivant renvoie cette valeur pour p donné :

def find3Mod4(prime):
    assert((prime % 4) == 3)
    return findCurve(prime, 4, 4)

Génération d'une courbe pour p = 3 mod 4

A.3. Points de base

Le point de base d'une courbe est le point de plus petite coordonnée u positive appartenant au sous-groupe attendu. La fonction findBasepoint du script Sage ci-dessous renvoie ce point pour p et A donnés :

def findBasepoint(prime, A):
    F = GF(prime)
    E = EllipticCurve(F, [0, A, 0, 1, 0])

    for uInt in range(1, 1e3):
      u = F(uInt)
      v2 = u^3 + A*u^2 + u
      if not v2.is_square():
        continue
      v = v2.sqrt()

      point = E(u, v)
      pointOrder = point.order()
      if pointOrder > 8 and pointOrder.is_prime():
        return point

Génération du point de base