Zum Hauptinhalt springen

Appendix A. Deterministic Generation (Anhang A. Deterministische Generierung)

Appendix A. Deterministic Generation (Deterministische Generierung)​

Dieser Abschnitt spezifiziert das Verfahren, mit dem die obigen Kurven erzeugt wurden; insbesondere definiert er, wie der Parameter A der Montgomery-Kurve y^2 = x^3 + A*x^2 + x erzeugt wird. Dieses Verfahren soll so objektiv wie vernünftigerweise erreichbar sein, damit klar ist, dass bei der Kurvenwahl keine unzulässigen Erwägungen eine Rolle spielten. Die Eingabe dieses Prozesses ist p, die Primzahl, die den zugrunde liegenden Körper definiert. Die Größe von p bestimmt den Aufwand zur Berechnung eines diskreten Logarithmus in der elliptischen Kurvengruppe, und die Wahl eines bestimmten p hängt von vielen implementierungsbezogenen Gesichtspunkten ab. Die Leistung der Kurve wird von Operationen in GF(p) dominiert; daher ist die sorgfältige Wahl eines Werts, der auf der Zielarchitektur einfache Reduktionen ermöglicht, entscheidend. Dieses Dokument versucht nicht, all diese Erwägungen darzulegen.

Der Wert (A-2)/4 wird in mehreren Formeln für die Punktarithmetik auf elliptischen Kurven verwendet. Aus Gründen der Einfachheit und Leistung ist es vorteilhaft, diese Konstante klein zu machen, d. h. A so zu wählen, dass (A-2) eine kleine ganze Zahl ist, die durch vier teilbar ist.

Für jede Kurve auf einem bestimmten Sicherheitsniveau gilt:

  1. Die Spur des Frobenius DARF NICHT in {0, 1} liegen, um die in [smart], [satoh] und [semaev] beschriebenen Angriffe auszuschließen, wie in [brainpool] und [safecurves].

  2. MOV-Grad [reducing]: Der Einbettungsgrad MUSS größer als (order - 1) / 100 sein, wie in [brainpool] und [safecurves].

  3. CM-Diskriminante: Die Diskriminante D MUSS größer als 2^100 sein, wie in [safecurves].

A.1. p = 1 mod 4​

Für Primzahlen, die kongruent zu 1 mod 4 sind, sind die minimalen Kofaktoren der Kurve und ihrer Twist entweder {4, 8} oder {8, 4}. Wir wählen eine Kurve mit letzteren Kofaktoren, damit Algorithmen, die den Kofaktor berücksichtigen, keine Punkte auf dem Twist prüfen müssen, weil der Twist-Kofaktor der kleinere der beiden sein wird.

Zur Erzeugung der Montgomery-Kurve suchen wir den minimalen positiven A-Wert mit A > 2 und (A-2) ist durch vier teilbar und die Kofaktoren sind wie gewünscht. Die Funktion find1Mod4 im folgenden Sage-Skript liefert diesen Wert bei gegebenem p:

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)

Erzeugung einer Kurve mit p = 1 mod 4

A.2. p = 3 mod 4​

Für eine Primzahl, die kongruent zu 3 mod 4 ist, können sowohl der Kurven- als auch der Twist-Kofaktor 4 sein, und dies ist minimal. Daher wählen wir die Kurve mit diesen Kofaktoren und minimalem positivem A mit A > 2 und (A-2) ist durch vier teilbar. Die Funktion find3Mod4 im folgenden Sage-Skript liefert diesen Wert bei gegebenem p:

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

Erzeugung einer Kurve mit p = 3 mod 4

A.3. Base Points (Basispunkte)​

Der Basispunkt einer Kurve ist der Punkt mit minimalem positivem u-Wert, der in der richtigen Untergruppe liegt. Die Funktion findBasepoint im folgenden Sage-Skript liefert diesen Wert bei gegebenem p und A:

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

Erzeugung des Basispunkts

Letztes Update am