6. Deterministische Abbildungen

Die Abbildungen dieses Abschnitts eignen sich zur Implementierung nicht gleichmäßiger oder gleichmäßiger Codierungen mittels der Konstruktionen aus Abschnitt 3. Manche Abbildungen stellen Einschränkungen an die Form der Kurve oder an ihre Parameter. Für jede vorgestellte Abbildung führt dieses Dokument die relevanten Einschränkungen auf.

Man beachte, dass die Abbildungen dieses Abschnitts nicht austauschbar sind: Unterschiedliche Abbildungen liefern bei Auswertung auf derselben Eingabe mit an Sicherheit grenzender Wahrscheinlichkeit unterschiedliche Punkte.

6.1. Wahl einer Abbildungsfunktion

Dieser Abschnitt gibt kurze Empfehlungen zur Wahl einer Abbildungsfunktion für eine gegebene elliptische Kurve. Man beachte, dass die in Abschnitt 8 angegebenen Suiten die empfohlenen Abbildungen für die jeweiligen Kurven darstellen.

Ist die elliptische Zielkurve eine Montgomery-Kurve (Abschnitt 6.7), so wird die Elligator-2-Methode (Abschnitt 6.7.1) empfohlen. Ist die elliptische Zielkurve entsprechend eine verdrehte Edwards-Kurve (Abschnitt 6.8), so wird die Elligator-2-Methode für verdrehte Edwards-Kurven (Abschnitt 6.8.2) empfohlen.

Die verbleibenden Fälle sind Weierstraß-Kurven. Für Kurven, die von der vereinfachten Shallue-van-de-Woestijne-Ulas-Methode (vereinfachtes SWU, Abschnitt 6.6.2) unterstützt werden, ist diese Abbildung die empfohlene. Andernfalls wird das vereinfachte SWU für AB == 0 (Abschnitt 6.6.3) empfohlen, wenn bestmögliche Leistung das Ziel ist, während die Shallue-van-de-Woestijne-Methode (Abschnitt 6.6.1) empfohlen wird, wenn Einfachheit der Implementierung das Ziel ist. (Der Grund für diese Unterscheidung ist, dass das vereinfachte SWU für AB == 0 zusätzlich zur Abbildungsfunktion die Implementierung einer Isogenie-Abbildung erfordert, die Shallue-van-de-Woestijne-Methode hingegen nicht.)

Die Shallue-van-de-Woestijne-Methode (Abschnitt 6.6.1) funktioniert mit jeder Kurve und kann in Fällen eingesetzt werden, in denen eine generische Abbildung erforderlich ist. Man beachte jedoch, dass diese Abbildung fast immer rechenaufwendiger ist als die obigen kurvenspezifischen Empfehlungen.

6.2. Schnittstelle

Die gemeinsame generische Schnittstelle aller Abbildungen dieses Abschnitts lautet:

(x, y) = map_to_curve(u)

Die Eingabe u und die Ausgaben x und y sind Elemente des Körpers F. Die affinen Koordinaten (x, y) bezeichnen einen Punkt einer über F definierten elliptischen Kurve. Man beachte jedoch, dass der Punkt (x, y) kein gleichverteilt zufälliger Punkt ist.

6.3. Notation

Zur Orientierung werden im Pseudocode die folgenden Konventionen verwendet:

• Alle arithmetischen Operationen werden über einem Körper F ausgeführt, sofern nicht ausdrücklich anders angegeben.

• u: die Eingabe der Abbildungsfunktion. Dies ist ein von der Funktion hash_to_field erzeugtes Element von F.

• (x, y), (s, t), (v, w): die affinen Koordinaten des von der Abbildung erzeugten Punktes. Indizierte Variablen (z. B. x1, y2, ...) werden für Kandidatenwerte verwendet.

• tv1, tv2, ...: wiederverwendbare temporäre Variablen.

• c1, c2, ...: konstante Werte, die vorab berechnet werden können.

6.4. Vorzeichen des resultierenden Punktes

Im Allgemeinen besitzen elliptische Kurven Gleichungen der Form y^2 = g(x). Die Abbildungen dieses Abschnitts bestimmen zunächst ein x, für das g(x) ein Quadrat ist, und ziehen anschließend eine Quadratwurzel, um y zu finden. Da es für g(x) != 0 zwei Quadratwurzeln gibt, kann dies zu einer Mehrdeutigkeit hinsichtlich des Vorzeichens von y führen.

Sofern erforderlich, lösen die Abbildungen dieses Abschnitts diese Mehrdeutigkeit auf, indem sie das Vorzeichen der y-Koordinate in Abhängigkeit von der Eingabe der Abbildungsfunktion festlegen. Dafür gibt es zwei wesentliche Gründe: Erstens deckt dies elliptische Kurven über beliebigen Körpern einheitlich ab, und zweitens lässt es Implementierern Spielraum zur Optimierung von Quadratwurzel-Implementierungen.

6.5. Ausnahmefälle

Abbildungen können Ausnahmefälle aufweisen, d. h. Eingaben u, für die die Abbildung nicht definiert ist. Diese Fälle müssen sorgfältig behandelt werden, insbesondere bei Implementierungen in konstanter Zeit.

Für jede Abbildung dieses Abschnitts erörtern wir die Ausnahmefälle und zeigen, wie sie in konstanter Zeit behandelt werden können. Man beachte, dass alle Implementierungen inv0 (Abschnitt 4) zur Berechnung multiplikativer Inverser verwenden SOLLTEN, um Ausnahmefälle zu vermeiden, die aus dem Versuch entstehen, das Inverse von 0 zu berechnen.

6.6. Abbildungen für Weierstraß-Kurven

Die Abbildungen dieses Abschnitts gelten für eine Zielkurve E, die durch die Gleichung

y^2 = g(x) = x^3 + A * x + B

definiert ist, wobei 4 * A^3 + 27 * B^2 != 0 gilt.

6.6.1. Shallue-van-de-Woestijne-Methode

Shallue und van de Woestijne [SW06] beschreiben eine Abbildung, die auf im Wesentlichen jede elliptische Kurve anwendbar ist. (Man beachte jedoch, dass diese Abbildung aufwendiger auszuwerten ist als die übrigen Abbildungen dieses Dokuments.)

Die nachstehend angegebene Parametrisierung betrifft Weierstraß-Kurven; ihre Herleitung ist in [W19] ausgeführt. Diese Parametrisierung funktioniert über die in Anhang D angegebenen rationalen Abbildungen auch für Montgomery-Kurven (Abschnitt 6.7) und verdrehte Edwards-Kurven (Abschnitt 6.8): Zunächst wertet man die Shallue-van-de-Woestijne-Abbildung auf eine äquivalente Weierstraß-Kurve aus und bildet diesen Punkt anschließend mittels der entsprechenden rationalen Abbildung auf die Montgomery- oder verdrehte Edwards-Zielkurve ab.

Voraussetzungen: eine Weierstraß-Kurve y^2 = x^3 + A * x + B.

Konstanten:

• A und B, die Parameter der Weierstraß-Kurve.

• Z, ein von null verschiedenes Element von F, das die untenstehenden Kriterien erfüllt. Anhang H.1 gibt ein Sage-Skript [SAGE] an, das das EMPFOHLENE Z erzeugt.

  1. g(Z) != 0 in F.
  2. -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0 in F.
  3. -(3 * Z^2 + 4 * A) / (4 * g(Z)) ist ein Quadrat in F.
  4. Mindestens eines von g(Z) und g(-Z / 2) ist ein Quadrat in F.

Vorzeichen von y: Die Eingaben u und -u ergeben für viele Werte von u dieselbe x-Koordinate. Daher setzen wir sgn0(y) == sgn0(u).

Ausnahmen: Ausnahmefälle für u treten auf, wenn (1 + u^2 * g(Z)) * (1 - u^2 * g(Z)) == 0 gilt. Die oben angegebenen Einschränkungen für Z stellen sicher, dass Implementierungen, die inv0 zur Invertierung dieses Produkts verwenden, ausnahmefrei sind.

Operationen:

1. tv1 = u^2 * g(Z)
2. tv2 = 1 + tv1
3. tv1 = 1 - tv1
4. tv3 = inv0(tv1 * tv2)
5. tv4 = sqrt(-g(Z) * (3 * Z^2 + 4 * A))    # can be precomputed
6. If sgn0(tv4) == 1, set tv4 = -tv4        # sgn0(tv4) MUST equal 0
7. tv5 = u * tv1 * tv3 * tv4
8. tv6 = -4 * g(Z) / (3 * Z^2 + 4 * A)      # can be precomputed
9.  x1 = -Z / 2 - tv5
10. x2 = -Z / 2 + tv5
11. x3 = Z + tv6 * (tv2^2 * tv3)^2
12. If is_square(g(x1)), set x = x1 and y = sqrt(g(x1))
13. Else If is_square(g(x2)), set x = x2 and y = sqrt(g(x2))
14. Else set x = x3 and y = sqrt(g(x3))
15. If sgn0(u) != sgn0(y), set y = -y
16. return (x, y)

Anhang F.1 gibt eine beispielhafte Straight-Line-Implementierung dieser Abbildung an.

6.6.2. Vereinfachte Shallue-van-de-Woestijne-Ulas-Methode

Die Funktion map_to_curve_simple_swu(u) implementiert eine von Brier et al. [BCIMRT10] beschriebene Vereinfachung der Shallue-van-de-Woestijne-Ulas-Abbildung [U07], die die Autoren als „vereinfachte SWU"-Abbildung bezeichnen. Wahby und Boneh [WB19] verallgemeinern und optimieren diese Abbildung.

Voraussetzungen: eine Weierstraß-Kurve y^2 = x^3 + A * x + B mit A != 0 und B != 0.

Konstanten:

• A und B, die Parameter der Weierstraß-Kurve.

• Z, ein Element von F, das die untenstehenden Kriterien erfüllt. Anhang H.2 gibt ein Sage-Skript [SAGE] an, das das EMPFOHLENE Z erzeugt. Die Kriterien lauten:

  1. Z ist ein Nichtquadrat in F,
  2. Z != -1 in F,
  3. das Polynom g(x) - Z ist über F irreduzibel, und
  4. g(B / (Z * A)) ist ein Quadrat in F.

Vorzeichen von y: Die Eingaben u und -u ergeben dieselbe x-Koordinate. Daher setzen wir sgn0(y) == sgn0(u).

Ausnahmen: Ausnahmefälle sind Werte von u mit Z^2 * u^4 + Z * u^2 == 0. Dazu gehört u == 0 und je nach Z möglicherweise weitere Werte. Implementierungen müssen diesen Fall erkennen und x1 = B / (Z * A) setzen, was aufgrund der oben angegebenen Bedingung an Z sicherstellt, dass g(x1) ein Quadrat ist.

Operationen:

1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2.  x1 = (-B / A) * (1 + tv1)
3.  If tv1 == 0, set x1 = B / (Z * A)
4. gx1 = x1^3 + A * x1 + B
5.  x2 = Z * u^2 * x1
6. gx2 = x2^3 + A * x2 + B
7.  If is_square(gx1), set x = x1 and y = sqrt(gx1)
8.  Else set x = x2 and y = sqrt(gx2)
9.  If sgn0(u) != sgn0(y), set y = -y
10. return (x, y)

Anhang F.2 gibt eine allgemeine und optimierte Straight-Line-Implementierung dieser Abbildung an. Weitere Informationen zur Optimierung dieser Abbildung finden sich in Abschnitt 4 von [WB19] oder im Beispielcode in [hash2curve-repo].

6.6.3. Vereinfachtes SWU für AB == 0

Wahby und Boneh [WB19] zeigen, wie sich die vereinfachte SWU-Abbildung an Weierstraß-Kurven mit A == 0 oder B == 0 anpassen lässt, die von der Abbildung aus Abschnitt 6.6.2 nicht unterstützt werden. (Der Fall A == B == 0 ist ausgeschlossen, da y^2 = x^3 keine elliptische Kurve ist.)

Diese Methode gilt für Kurven wie secp256k1 [SEC2] sowie für pairing-freundliche Kurven der Barreto-Lynn-Scott-Familie [BLS03], der Barreto-Naehrig-Familie [BN05] und weiterer Familien.

Diese Methode erfordert das Auffinden einer weiteren elliptischen Kurve E', gegeben durch die Gleichung

y'^2 = g'(x') = x'^3 + A' * x' + B'

die zu E isogen ist und A' != 0 sowie B' != 0 erfüllt. (Siehe [WB19], Anhang A, für eine Möglichkeit, E' mithilfe von [SAGE] zu finden.) Diese Isogenie definiert eine Abbildung iso_map(x', y'), gegeben durch ein Paar rationaler Funktionen. iso_map nimmt als Eingabe einen Punkt von E' entgegen und liefert als Ausgabe einen Punkt von E.

Sind E' und iso_map einmal bestimmt, funktioniert diese Abbildung wie folgt: Auf die Eingabe u wendet man zunächst die vereinfachte SWU-Abbildung an, um einen Punkt von E' zu erhalten, und wendet anschließend die Isogenie-Abbildung auf diesen Punkt an, um einen Punkt von E zu erhalten.

Man beachte, dass iso_map ein Gruppenhomomorphismus ist, was bedeutet, dass die Punktaddition mit iso_map vertauscht. Bei Verwendung dieser Abbildung in der in Abschnitt 3 beschriebenen hash_to_curve-Konstruktion lässt sich daher eine kleine Optimierung erzielen, indem man zunächst u0 und u1 auf E' abbildet, die resultierenden Punkte auf E' addiert und anschließend iso_map auf die Summe anwendet. Dies ergibt dasselbe Resultat, erfordert jedoch nur eine einzige Auswertung von iso_map.

Voraussetzungen: eine elliptische Kurve E' mit A' != 0 und B' != 0, die zur Zielkurve E isogen ist, samt der Isogenie-Abbildung iso_map von E' nach E.

Hilfsfunktionen:

• map_to_curve_simple_swu ist die Abbildung aus Abschnitt 6.6.2 auf E'

• iso_map ist die Isogenie-Abbildung von E' nach E

Vorzeichen von y: Für diese Abbildung wird das Vorzeichen durch map_to_curve_simple_swu bestimmt. Eine zusätzliche Vorzeichenanpassung ist nicht erforderlich.

Ausnahmen: map_to_curve_simple_swu behandelt ihre eigenen Ausnahmefälle. Ausnahmefälle von iso_map sind Eingaben, die den Nenner einer der beiden rationalen Funktionen zu null machen; solche Fälle MÜSSEN den neutralen Punkt (Identität) von E zurückgeben.

Operationen:

1. (x', y') = map_to_curve_simple_swu(u)    # (x', y') is on E'
2.   (x, y) = iso_map(x', y')               # (x, y) is on E
3. return (x, y)

Siehe [hash2curve-repo] oder Abschnitt 4.3 von [WB19] für Implementierungsdetails der Isogenie-Abbildung.

6.7. Abbildungen für Montgomery-Kurven

Die in diesem Abschnitt definierte Abbildung gilt für eine Zielkurve M, die durch die Gleichung

K * t^2 = s^3 + J * s^2 + s

definiert ist.

6.7.1. Elligator-2-Methode

Bernstein, Hamburg, Krasnova und Lange geben eine Abbildung an, die für jede Kurve mit einem Punkt der Ordnung 2 gilt [BHKL13] und die sie Elligator 2 nennen.

Voraussetzungen: eine Montgomery-Kurve K * t^2 = s^3 + J * s^2 + s mit J != 0, K != 0, wobei (J^2 - 4) / K^2 von null verschieden und ein Nichtquadrat in F ist.

Konstanten:

• J und K, die Parameter der elliptischen Kurve.

• Z, ein Nichtquadrat-Element von F. Anhang H.3 gibt ein Sage-Skript [SAGE] an, das das EMPFOHLENE Z erzeugt.

Vorzeichen von t: Diese Abbildung legt das Vorzeichen von t wie in [BHKL13] spezifiziert fest. Eine zusätzliche Anpassung ist nicht erforderlich.

Ausnahmen: Der Ausnahmefall ist Z * u^2 == -1, d. h. 1 + Z * u^2 == 0. Implementierungen müssen diesen Fall erkennen und x1 = -(J / K) setzen. Man beachte, dass dies nur für q = 3 (mod 4) auftreten kann.

Operationen:

1.  x1 = -(J / K) * inv0(1 + Z * u^2)
2.  If x1 == 0, set x1 = -(J / K)
3. gx1 = x1^3 + (J / K) * x1^2 + x1 / K^2
4.  x2 = -x1 - (J / K)
5. gx2 = x2^3 + (J / K) * x2^2 + x2 / K^2
6.  If is_square(gx1), set x = x1, y = sqrt(gx1) with sgn0(y) == 1.
7.  Else set x = x2, y = sqrt(gx2) with sgn0(y) == 0.
8.   s = x * K
9.   t = y * K
10. return (s, t)

Anhang F.3 gibt eine beispielhafte Straight-Line-Implementierung dieser Abbildung an. Anhang G.2 gibt optimierte Straight-Line-Prozeduren an, die für bestimmte Klassen von Kurven und Basiskörpern gelten.

6.8. Abbildungen für verdrehte Edwards-Kurven

Verdrehte Edwards-Kurven (eine Kurvenklasse, die die Edwards-Kurven einschließt) sind durch die Gleichung

a * v^2 + w^2 = 1 + d * v^2 * w^2

gegeben, mit a != 0, d != 0 und a != d [BBJLP08].

Diese Kurven sind eng mit Montgomery-Kurven (Abschnitt 6.7) verwandt: Jede verdrehte Edwards-Kurve ist birational äquivalent zu einer Montgomery-Kurve ([BBJLP08], Satz 3.2). Diese Äquivalenz liefert ein effizientes Verfahren zum Hashing auf eine verdrehte Edwards-Kurve: Zunächst hasht man auf eine äquivalente Montgomery-Kurve und transformiert das Ergebnis anschließend mittels einer rationalen Abbildung in einen Punkt der verdrehten Edwards-Kurve. Dieses Verfahren zum Hashing auf eine verdrehte Edwards-Kurve erfordert somit die Bestimmung einer entsprechenden Montgomery-Kurve und einer rationalen Abbildung. Wie eine solche Kurve und Abbildung zu bestimmen sind, beschreiben wir unmittelbar nachfolgend.

6.8.1. Rationale Abbildungen von Montgomery-Kurven auf verdrehte Edwards-Kurven

Es gibt zwei Möglichkeiten, eine Montgomery-Kurve und eine rationale Abbildung für das Hashing auf eine gegebene verdrehte Edwards-Kurve auszuwählen. Die ausgewählte Montgomery-Kurve und rationale Abbildung MÜSSEN als Bestandteil der Hash-to-Curve-Suite für eine gegebene verdrehte Edwards-Kurve spezifiziert werden; siehe Abschnitt 8.

1. Beim Hashing auf eine standardisierte verdrehte Edwards-Kurve, für die auch eine entsprechende Montgomery-Form und eine rationale Abbildung standardisiert sind, SOLLTEN die standardisierte Montgomery-Form und rationale Abbildung verwendet werden, um die Kompatibilität mit bestehender Software zu gewährleisten.

   In manchen Fällen, etwa bei edwards25519 [RFC7748], ist das Vorzeichen der rationalen Abbildung von der verdrehten Edwards-Kurve auf die entsprechende Montgomery-Kurve nicht explizit angegeben. In diesem Fall MUSS das Vorzeichen so festgelegt werden, dass die Anwendung der rationalen Abbildung auf den Basispunkt der verdrehten Edwards-Kurve den Basispunkt der Montgomery-Kurve mit dem korrekten Vorzeichen liefert. (Für edwards25519 siehe [RFC7748] und [Err4730].)

   Bei der Definition neuer verdrehter Edwards-Kurven SOLLTEN ebenfalls ein Montgomery-Äquivalent und eine rationale Abbildung spezifiziert werden, und das Vorzeichen der rationalen Abbildung SOLLTE explizit angegeben werden.

2. Beim Hashing auf eine verdrehte Edwards-Kurve, für die keine standardisierte Montgomery-Form oder rationale Abbildung vorliegt, SOLLTE die in Anhang D angegebene Abbildung verwendet werden.

6.8.2. Elligator-2-Methode

Voraussetzungen: eine verdrehte Edwards-Kurve E und eine äquivalente Montgomery-Kurve M, welche die Anforderungen aus Abschnitt 6.8.1 erfüllen.

Hilfsfunktionen:

• map_to_curve_elligator2 ist die Abbildung aus Abschnitt 6.7.1 auf die Kurve M.

• rational_map ist eine Funktion, die einen Punkt (s, t) von M entgegennimmt und einen Punkt (v, w) von E zurückgibt. Diese rationale Abbildung sollte wie in Abschnitt 6.8.1 definiert gewählt werden.

Vorzeichen von t (und v): Für diese Abbildung wird das Vorzeichen durch map_to_curve_elligator2 bestimmt. Eine zusätzliche Vorzeichenanpassung ist nicht erforderlich.

Ausnahmen: Die Ausnahmen der Elligator-2-Abbildung sind die in Abschnitt 6.7.1 angegebenen. Die Ausnahmen der rationalen Abbildung sind die in Abschnitt 6.8.1 angegebenen. Weitere Ausnahmen sind nicht möglich.

Die folgende Prozedur implementiert die Elligator-2-Abbildung für eine verdrehte Edwards-Kurve. (Man beachte, dass der Ausgabepunkt mit (v, w) bezeichnet wird, da es sich um einen Punkt der verdrehten Edwards-Zielkurve handelt.)

map_to_curve_elligator2_edwards(u)

Input: u, an element of F.
Output: (v, w), a point on E.

1. (s, t) = map_to_curve_elligator2(u)      # (s, t) is on M
2. (v, w) = rational_map(s, t)              # (v, w) is on E
3. return (v, w)