6. Deterministische Abbildungen

Die Abbildungen in diesem Abschnitt eignen sich zur Implementierung sowohl nicht-uniformer als auch uniformer Kodierungen unter Verwendung der Konstruktionen aus Abschnitt 3. Einige Abbildungen schränken die Form der Kurve oder ihre Parameter ein. Für jede vorgestellte Abbildung führt dieses Dokument die relevanten Einschränkungen auf.

Beachten Sie, dass die Abbildungen in diesem Abschnitt nicht austauschbar sind: Verschiedene Abbildungen erzeugen fast sicher unterschiedliche Punkte, wenn sie mit derselben Eingabe ausgewertet werden.

6.1. Auswahl einer Abbildungsfunktion

Dieser Abschnitt gibt kurze Richtlinien zur Auswahl einer Abbildungsfunktion für eine gegebene elliptische Kurve. Beachten Sie, dass die in Abschnitt 8 aufgeführten Suiten empfohlene Abbildungen für die jeweiligen Kurven sind.

Wenn die Zielkurve eine Montgomery-Kurve ist (Abschnitt 6.7), wird die Elligator-2-Methode (Abschnitt 6.7.1) empfohlen. Ebenso wird für eine Twisted-Edwards-Kurve (Abschnitt 6.8) die Elligator-2-Methode für Twisted Edwards (Abschnitt 6.8.2) empfohlen.

In den verbleibenden Fällen handelt es sich um Weierstrass-Kurven. Für Kurven, die von der vereinfachten Shallue-van de Woestijne-Ulas (SWU)-Methode (Abschnitt 6.6.2) unterstützt werden, ist diese Abbildung die empfohlene. Andernfalls wird die vereinfachte SWU-Methode für AB == 0 (Abschnitt 6.6.3) empfohlen, wenn eine bessere Leistung angestrebt wird, während die Shallue-van de Woestijne-Methode (Abschnitt 6.6.1) empfohlen wird, wenn die Einfachheit der Implementierung im Vordergrund steht. (Der Grund für diese Unterscheidung ist, dass die vereinfachte SWU-Methode für AB == 0 zusätzlich zur Abbildungsfunktion die Implementierung einer Isogenie-Abbildung erfordert, während die Shallue-van de Woestijne-Methode dies nicht tut.)

Die Shallue-van de Woestijne-Methode (Abschnitt 6.6.1) funktioniert mit jeder Kurve und kann in Fällen verwendet werden, in denen eine generische Abbildung erforderlich ist. Beachten Sie jedoch, dass diese Abbildung fast immer rechenintensiver ist als die oben genannten kurvenspezifischen Empfehlungen.

6.2. Schnittstelle

Die generische Schnittstelle, die von allen Abbildungen in diesem Abschnitt geteilt wird, ist wie folgt:

(x, y) = map_to_curve(u)

Die Eingabe u sowie die Ausgaben x und y sind Elemente des Körpers F. Die affinen Koordinaten (x, y) spezifizieren einen Punkt auf einer über F definierten elliptischen Kurve. Beachten Sie jedoch, dass der Punkt (x, y) kein uniform zufälliger Punkt ist.

6.3. Notation

Als grobe Orientierung dienen die folgenden Konventionen im Pseudocode:

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

• u: die Eingabe für die Abbildungsfunktion. Dies ist ein Element von F, das von der Funktion hash_to_field erzeugt wird.

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

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

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

6.4. Vorzeichen des resultierenden Punktes

Im Allgemeinen haben elliptische Kurven Gleichungen der Form y^2 = g(x). Die Abbildungen in diesem Abschnitt identifizieren zunächst ein x, so dass g(x) ein Quadrat ist, und ziehen dann eine Quadratwurzel, um y zu finden. Da es zwei Quadratwurzeln gibt, wenn g(x) != 0 ist, kann dies zu einer Mehrdeutigkeit hinsichtlich des Vorzeichens von y führen.

Gegebenenfalls beseitigen die Abbildungen in diesem Abschnitt diese Mehrdeutigkeit, indem sie das Vorzeichen der y-Koordinate in Abhängigkeit von der Eingabe der Abbildungsfunktion spezifizieren. Zwei Hauptgründe unterstützen diesen Ansatz: Erstens deckt er elliptische Kurven über jedem Körper einheitlich ab, und zweitens lässt er Implementierern Spielraum zur Optimierung von Quadratwurzel-Implementierungen.

6.5. Ausnahmefälle

Abbildungen können Ausnahmefälle haben, 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 in diesem Abschnitt diskutieren wir die Ausnahmefälle und zeigen, wie sie in konstanter Zeit behandelt werden können. Beachten Sie, dass alle Implementierungen inv0 (Abschnitt 4) verwenden SOLLTEN, um multiplikative Inverse zu berechnen, um Ausnahmefälle zu vermeiden, die aus dem Versuch resultieren, das Inverse von 0 zu berechnen.

6.6. Abbildungen für Weierstrass-Kurven

Die Abbildungen in diesem Abschnitt gelten für eine Zielkurve E, die durch die Gleichung definiert ist:

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

wobei 4 * A^3 + 27 * B^2 != 0.

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. (Beachten Sie jedoch, dass diese Abbildung teurer in der Auswertung ist als die anderen Abbildungen in diesem Dokument.)

Die unten angegebene Parametrisierung gilt für Weierstrass-Kurven; ihre Ableitung ist detailliert in [W19] beschrieben. Diese Parametrisierung funktioniert auch für Montgomery-Kurven (Abschnitt 6.7) und Twisted-Edwards-Kurven (Abschnitt 6.8) mittels der in Anhang D angegebenen rationalen Abbildungen: Zuerst wird die Shallue-van de Woestijne-Abbildung auf eine äquivalente Weierstrass-Kurve ausgewertet, und dann wird dieser Punkt unter Verwendung der entsprechenden rationalen Abbildung auf die Ziel-Montgomery- oder Twisted-Edwards-Kurve abgebildet.

Voraussetzungen: Eine Weierstrass-Kurve y^2 = x^3 + A * x + B.

Konstanten:

• A und B, die Parameter der Weierstrass-Kurve.

• Z, ein von Null verschiedenes Element von F, das die unten genannten Kriterien erfüllt. Anhang H.1 enthält ein Sage-Skript [SAGE], 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 legen wir sgn0(y) == sgn0(u) fest.

Ausnahmen: Ausnahmefälle für u treten auf, wenn (1 + u^2 * g(Z)) * (1 - u^2 * g(Z)) == 0. Die oben für Z angegebenen Einschränkungen garantieren, 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)) # kann vorberechnet werden
6. Falls sgn0(tv4) == 1, setze tv4 = -tv4 # sgn0(tv4) MUSS 0 sein
7. tv5 = u * tv1 * tv3 * tv4
8. tv6 = -4 * g(Z) / (3 * Z^2 + 4 * A) # kann vorberechnet werden
9. x1 = -Z / 2 - tv5
10. x2 = -Z / 2 + tv5
11. x3 = Z + tv6 * (tv2^2 * tv3)^2
12. Falls is_square(g(x1)), setze x = x1 und y = sqrt(g(x1))
13. Sonst falls is_square(g(x2)), setze x = x2 und y = sqrt(g(x2))
14. Sonst setze x = x3 und y = sqrt(g(x3))
15. Falls sgn0(u) != sgn0(y), setze y = -y
16. Rückgabe (x, y)

Anhang F.1 enthält ein Beispiel für eine Straight-Line-Implementierung dieser Abbildung.

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

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

Voraussetzungen: Eine Weierstrass-Kurve y^2 = x^3 + A * x + B mit A != 0 und B != 0.

Konstanten:

• A und B, die Parameter der Weierstrass-Kurve.

• Z, ein Element von F, das die unten genannten Kriterien erfüllt. Anhang H.2 enthält ein Sage-Skript [SAGE], das das EMPFOHLENE Z erzeugt. Die Kriterien sind:

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

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

Ausnahmen: Ausnahmefälle sind Werte von u, für die Z^2 * u^4 + Z * u^2 == 0 gilt. Dies schließt u == 0 ein und kann weitere Werte umfassen, die von Z abhängen. Implementierungen müssen diesen Fall erkennen und x1 = B / (Z * A) setzen, wodurch sichergestellt wird, dass g(x1) aufgrund der oben genannten Bedingung für Z ein Quadrat ist.

Operationen:

1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2. x1 = (-B / A) * (1 + tv1)
3. Falls tv1 == 0, setze 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. Falls is_square(gx1), setze x = x1 und y = sqrt(gx1)
8. Sonst setze x = x2 und y = sqrt(gx2)
9. Falls sgn0(u) != sgn0(y), setze y = -y
10. Rückgabe (x, y)

Anhang F.2 enthält eine allgemeine und optimierte Straight-Line-Implementierung dieser Abbildung. Weitere Informationen zur Optimierung dieser Abbildung finden Sie in Abschnitt 4 von [WB19] oder im Beispielcode auf [hash2curve-repo].

6.6.3. Vereinfachtes SWU für AB == 0

Wahby und Boneh [WB19] zeigen, wie die vereinfachte SWU-Abbildung für Weierstrass-Kurven mit A == 0 oder B == 0 angepasst werden kann, was von der Abbildung in Abschnitt 6.6.2 nicht unterstützt wird. (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] und für paarungsfreundliche Kurven der Barreto-Lynn-Scott-Familie [BLS03], der Barreto-Naehrig-Familie [BN05] und andere Familien.

Diese Methode erfordert das Finden einer anderen elliptischen Kurve E', definiert durch die Gleichung:

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

die zu E isogen ist und A' != 0 sowie B' != 0 hat. (Siehe [WB19], Anhang A, für einen Weg, E' unter Verwendung von [SAGE] zu finden.) Diese Isogenie definiert eine Abbildung iso_map(x', y'), die durch ein Paar rationaler Funktionen gegeben ist. iso_map nimmt als Eingabe einen Punkt auf E' und erzeugt als Ausgabe einen Punkt auf E.

Sobald E' und iso_map identifiziert sind, funktioniert diese Abbildung wie folgt: Wenden Sie bei Eingabe u zuerst die vereinfachte SWU-Abbildung an, um einen Punkt auf E' zu erhalten, und wenden Sie dann die Isogenie-Abbildung auf diesen Punkt an, um einen Punkt auf E zu erhalten.

Beachten Sie, dass iso_map ein Gruppenhomomorphismus ist, was bedeutet, dass die Punktaddition mit iso_map kommutiert. Daher kann bei Verwendung dieser Abbildung in der in Abschnitt 3 behandelten hash_to_curve-Konstruktion eine kleine Optimierung vorgenommen werden, indem zuerst u0 und u1 auf E' abgebildet werden, die resultierenden Punkte auf E' addiert werden und dann iso_map auf die Summe angewendet wird. Dies liefert das gleiche Ergebnis, während nur eine einzige Auswertung von iso_map erforderlich ist.

Voraussetzungen: Eine elliptische Kurve E' mit A' != 0 und B' != 0, die zur Zielkurve E isogen ist, mit einer 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 weitere Vorzeichenanpassung ist nicht erforderlich.

Ausnahmen: map_to_curve_simple_swu behandelt seine Ausnahmefälle. Die Ausnahmefälle von iso_map sind Eingaben, die dazu führen, dass der Nenner einer der rationalen Funktionen zu Null wird; solche Fälle MÜSSEN den Identitätspunkt auf E zurückgeben.

Operationen:

1. (x', y') = map_to_curve_simple_swu(u) # (x', y') ist auf E'
2. (x, y) = iso_map(x', y') # (x, y) ist auf E
3. Rückgabe (x, y)

Siehe [hash2curve-repo] oder Abschnitt 4.3 von [WB19] für weitere Details zur Implementierung 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 definiert ist:

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

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], welche sie als Elligator 2 bezeichnen.

Voraussetzungen: Eine Montgomery-Kurve K * t^2 = s^3 + J * s^2 + s mit J != 0, K != 0, und (J^2 - 4) / K^2 ist ein Nicht-Null-Element und Nicht-Quadrat in F.

Konstanten:

• J und K, die Parameter der elliptischen Kurve.

• Z, ein Nicht-Quadrat-Element von F. Anhang H.3 enthält ein Sage-Skript [SAGE], das das EMPFOHLENE Z erzeugt.

Vorzeichen von t: Diese Abbildung legt das Vorzeichen von t fest, wie in [BHKL13] spezifiziert. Weitere Anpassungen sind 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. Beachten Sie, dass dies nur auftreten kann, wenn q = 3 (mod 4) ist.

Operationen:

1. x1 = -(J / K) * inv0(1 + Z * u^2)
2. Falls x1 == 0, setze 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. Falls is_square(gx1), setze x = x1, y = sqrt(gx1) mit sgn0(y) == 1.
7. Sonst setze x = x2, y = sqrt(gx2) mit sgn0(y) == 0.
8. s = x * K
9. t = y * K
10. Rückgabe (s, t)

Anhang F.3 enthält ein Beispiel für eine Straight-Line-Implementierung dieser Abbildung. Anhang G.2 enthält optimierte Straight-Line-Verfahren, die für spezifische Klassen von Kurven und Grundkörpern gelten.

6.8. Abbildungen für Twisted-Edwards-Kurven

Twisted-Edwards-Kurven (eine Klasse von Kurven, die Edwards-Kurven einschließt) sind definiert durch die Gleichung:

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

wobei a != 0, d != 0 und a != d gilt [BBJLP08].

Diese Kurven sind eng mit Montgomery-Kurven verwandt (Abschnitt 6.7): Jede Twisted-Edwards-Kurve ist birational äquivalent zu einer Montgomery-Kurve ([BBJLP08], Theorem 3.2). Diese Äquivalenz bietet einen effizienten Weg zum Hashen auf eine Twisted-Edwards-Kurve: Zuerst wird auf eine äquivalente Montgomery-Kurve gehasht und dann das Ergebnis über eine rationale Abbildung in einen Punkt auf der Twisted-Edwards-Kurve transformiert. Diese Methode des Hashens auf eine Twisted-Edwards-Kurve erfordert daher die Identifizierung einer entsprechenden Montgomery-Kurve und einer rationalen Abbildung. Wir beschreiben unmittelbar im Folgenden, wie eine solche Kurve und Abbildung identifiziert werden.

6.8.1. Rationale Abbildungen von Montgomery- zu Twisted-Edwards-Kurven

Es gibt zwei Möglichkeiten, eine Montgomery-Kurve und eine rationale Abbildung auszuwählen, die beim Hashen auf eine gegebene Twisted-Edwards-Kurve verwendet werden sollen. Die gewählte Montgomery-Kurve und die rationale Abbildung MÜSSEN als Teil der Hash-to-Curve-Suite für eine gegebene Twisted-Edwards-Kurve spezifiziert werden; siehe Abschnitt 8.

1. Beim Hashen auf eine standardisierte Twisted-Edwards-Kurve, für die eine entsprechende Montgomery-Form und eine rationale Abbildung ebenfalls standardisiert sind, SOLLTEN die Standard-Montgomery-Form und die standardmäßige rationale Abbildung verwendet werden, um die Kompatibilität mit existierender Software zu gewährleisten.

   In einigen Fällen, beispielsweise bei edwards25519 [RFC7748], ist das Vorzeichen der rationalen Abbildung von der Twisted-Edwards-Kurve zu ihrer entsprechenden Montgomery-Form nicht explizit angegeben. In diesem Fall MUSS das Vorzeichen so festgelegt werden, dass die Anwendung der rationalen Abbildung auf den Basispunkt der Twisted-Edwards-Kurve den Basispunkt der Montgomery-Kurve mit dem richtigen Vorzeichen erzeugt. (Für edwards25519 siehe [RFC7748] und [Err4730].)

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

2. Beim Hashen auf eine Twisted-Edwards-Kurve, die über keine standardisierte Montgomery-Form oder rationale Abbildung verfügt, SOLLTE die in Anhang D angegebene Abbildung verwendet werden.

6.8.2. Elligator-2-Methode

Voraussetzungen: Eine Twisted-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) auf M nimmt und einen Punkt (v, w) auf E zurückgibt. Diese rationale Abbildung muss 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 weitere Vorzeichenanpassung ist nicht erforderlich.

Ausnahmen: Die Ausnahmen für die Elligator-2-Abbildung sind die in Abschnitt 6.7.1 angegebenen. Die Ausnahmen für die rationale Abbildung sind die in Abschnitt 6.8.1 angegebenen. Weitere Ausnahmen sind nicht möglich.

Das folgende Verfahren implementiert die Elligator-2-Abbildung für eine Twisted-Edwards-Kurve. (Beachten Sie, dass der Ausgabepunkt mit (v, w) bezeichnet wird, da es sich um einen Punkt auf der Ziel-Twisted-Edwards-Kurve handelt.)

map_to_curve_elligator2_edwards(u)

Eingabe: u, ein Element von F. Ausgabe: (v, w), ein Punkt auf E.

1. (s, t) = map_to_curve_elligator2(u) # (s, t) ist auf M
2. (v, w) = rational_map(s, t) # (v, w) ist auf E
3. Rückgabe (v, w)