Anhänge

Anhang A. Verwandte Arbeiten

Das Problem der Abbildung beliebiger Bitfolgen auf elliptische Kurvenpunkte war Gegenstand sowohl praktischer als auch theoretischer Forschung. Dieser Abschnitt beschreibt kurz den Hintergrund und die Forschungsergebnisse, die den Empfehlungen dieses Dokuments zugrunde liegen. Dieser Abschnitt dient nur zu Informationszwecken.

Eine naive, aber im Allgemeinen unsichere Methode, eine Zeichenkette msg auf einen Punkt einer elliptischen Kurve E mit n Punkten abzubilden, besteht darin, zunächst einen Punkt P zu fixieren, der die Gruppe der elliptischen Kurve erzeugt, und eine Hash-Funktion Hn von Bitfolgen auf ganze Zahlen kleiner als n; dann Hn(msg) * P zu berechnen, wobei der Operator * die Skalarmultiplikation darstellt. Der Grund, warum dieser Ansatz unsicher ist, besteht darin, dass der resultierende Punkt eine bekannte diskrete Logarithmusbeziehung zu P hat. Daher sollte diese Methode, außer in Fällen, in denen sie durch das Protokoll spezifiziert ist, nicht verwendet werden; dies zu tun riskiert katastrophale Sicherheitsfehler.

Boneh et al. [BLS01] beschreiben eine Kodierungsmethode, die sie MapToGroup nennen und die etwa wie folgt funktioniert: Verwenden Sie zunächst die Eingabezeichenkette, um einen Pseudo-Zufallszahlengenerator zu initialisieren, verwenden Sie dann den Generator, um einen Wert x in F zu erzeugen. Wenn x die x-Koordinate eines Punktes auf der elliptischen Kurve ist, erzeugen Sie diesen Punkt. Andernfalls erzeugen Sie einen neuen Wert x in F und versuchen Sie es erneut. Da ein zufälliger Wert x in F mit einer Wahrscheinlichkeit von etwa 1/2 einem Punkt auf der Kurve entspricht, beträgt die erwartete Anzahl von Versuchen nur zwei. Die Laufzeit dieser Methode, die allgemein als probabilistischer "Try-and-Increment"-Algorithmus bezeichnet wird, hängt jedoch von der Eingabezeichenkette ab. Als solche ist sie nicht sicher für die Verwendung in Protokollen, die empfindlich auf Timing-Seitenkanäle reagieren, wie der Dragonblood-Angriff [VR20] illustriert hat.

Schinzel und Skalba [SS04] führen eine Methode zur deterministischen Konstruktion von elliptischen Kurvenpunkten für eine eingeschränkte Klasse von Kurven und eine sehr kleine Anzahl von Punkten ein. Skalba [S05] verallgemeinert diese Konstruktion auf mehr Kurven und mehr Punkte auf diesen Kurven. Shallue und van de Woestijne [SW06] verallgemeinern und vereinfachen die Konstruktion von Skalba weiter und erzeugen konkret effiziente Abbildungen auf einen konstanten Bruchteil der Punkte auf fast allen Kurven. Fouque und Tibouchi [FT12] geben eine Parametrisierung dieser Abbildung für Pairing-freundliche Barreto-Naehrig-Kurven [BN05].

Ulas [U07] beschreibt eine einfachere Version der Shallue-van de Woestijne-Abbildung, und Brier et al. [BCIMRT10] geben eine weitere Vereinfachung, die die Autoren "vereinfachte SWU-Abbildung" nennen. Diese vereinfachte Abbildung gilt nur für Körper mit Charakteristik p = 3 (mod 4); Wahby und Boneh [WB19] verallgemeinern auf Körper beliebiger Charakteristik und geben weitere Optimierungen.

Boneh und Franklin geben einen deterministischen Algorithmus für die Abbildung auf bestimmte supersingulare Kurven über Körpern der Charakteristik p = 2 (mod 3) [BF01]. Icart gibt einen weiteren deterministischen Algorithmus, der auf jede Kurve über einem Körper der Charakteristik p = 2 (mod 3) abbildet [Icart09]. Mehrere Erweiterungen und Verallgemeinerungen folgen dieser Arbeit, darunter [FSV09], [FT10], [KLR10], [F11] und [CK11].

Nach der Arbeit von Farashahi [F11] beschreiben Fouque et al. [FJT13] eine Abbildung auf Kurven über Körpern der Charakteristik p = 3 (mod 4) mit einer durch 4 teilbaren Anzahl von Punkten. Bernstein et al. [BHKL13] optimieren diese Abbildung und beschreiben eine verwandte Abbildung, die sie "Elligator 2" nennen, die auf jede Kurve über einem Körper ungerader Charakteristik mit einem Punkt der Ordnung 2 anwendbar ist. Dies schließt Curve25519 und Curve448 ein, die beide vom CFRG empfohlene Kurven sind [RFC7748]. Bernstein et al. [BLMP19] erweitern die Elligator 2-Abbildung auf eine Klasse von supersingularen Kurven über Körpern der Charakteristik p = 3 (mod 4).

Ein wichtiger Vorbehalt bezüglich aller oben genannten deterministischen Abbildungsfunktionen ist, dass keine von ihnen auf die gesamte Kurve abbildet, sondern vielmehr auf einen Bruchteil der Punkte. Dies bedeutet, dass sie nicht direkt verwendet werden können, um ein Random Oracle zu konstruieren, das Punkte auf der Kurve erzeugt.

Brier et al. [BCIMRT10] geben zwei Lösungen für dieses Problem. Die erste, von der Brier et al. beweisen, dass sie auf die Icart-Methode anwendbar ist, berechnet f(H0(msg)) + f(H1(msg)) für zwei verschiedene Hash-Funktionen H0 und H1 von Bitfolgen nach F und eine Abbildung f von F auf die elliptische Kurve E. Die zweite, die auf im Wesentlichen alle deterministischen Abbildungen anwendbar ist, aber teurer ist, berechnet f(H0(msg)) + H2(msg) * P, wobei P ein Generator der Gruppe der elliptischen Kurve ist, H2 ein Hash von Bitfolgen auf ganze Zahlen modulo r ist und r die Ordnung der Gruppe der elliptischen Kurve ist.

Farashahi et al. [FFSTV13] verbessern die Analyse der ersten Methode und zeigen, dass sie auf im Wesentlichen alle deterministischen Abbildungen anwendbar ist. Tibouchi und Kim [TK17] verfeinern die Analyse weiter und beschreiben zusätzliche Optimierungen.

Komplementär zum Problem der Abbildung von Bitfolgen auf elliptische Kurvenpunkte untersuchen Bernstein et al. [BHKL13] das Problem der Abbildung von elliptischen Kurvenpunkten auf gleichmäßig verteilte zufällige Bitfolgen und geben Lösungen für eine Klasse von Kurven an, die Montgomery-Kurven und verdrehte Edwards-Kurven umfasst. Tibouchi [T14] und Aranha et al. [AFQTZ14] verallgemeinern diese Ergebnisse. Dieses Dokument behandelt dieses komplementäre Problem nicht.

Anhang B. Hashen auf ristretto255

ristretto255 [ristretto255-decaf448] bietet eine Gruppe mit Primordnung basierend auf curve25519 [RFC7748]. Dieser Abschnitt beschreibt hash_to_ristretto255, das eine Random-Oracle-Kodierung auf diese Gruppe implementiert, die eine gleichmäßige Ausgabeverteilung (Abschnitt 2.2.3) und dieselben Sicherheitseigenschaften und Schnittstellen wie die hash_to_curve-Funktion hat (Abschnitt 3).

Die ristretto255-API definiert eine unidirektionale Abbildung ([ristretto255-decaf448], Abschnitt 4.3.4); dieser Abschnitt bezieht sich auf diese Abbildung als ristretto255_map.

Die hash_to_ristretto255-Funktion MUSS mit einer expand_message-Funktion instanziiert werden, die den in Abschnitt 5.3 gegebenen Anforderungen entspricht. Darüber hinaus MUSS sie ein Domain-Separation-Tag verwenden, das wie in Abschnitt 3.1 beschrieben konstruiert ist, und alle in Abschnitt 10.7 gegebenen Domain-Separation-Empfehlungen gelten bei der Implementierung von Protokollen, die hash_to_ristretto255 verwenden.

hash_to_ristretto255(msg)

Parameter:

• DST, ein Domain-Separation-Tag (siehe Diskussion oben).
• expand_message, eine Funktion, die eine Byte-Zeichenkette und ein Domain-Separation-Tag zu einer gleichmäßig verteilten zufälligen Byte-Zeichenkette erweitert (siehe Diskussion oben).
• ristretto255_map, die unidirektionale Abbildung der ristretto255-API.

Eingabe: msg, eine Byte-Zeichenkette beliebiger Länge. Ausgabe: P, ein Element der ristretto255-Gruppe.

Schritte:

1. uniform_bytes = expand_message(msg, DST, 64)
2. P = ristretto255_map(uniform_bytes)
3. return P

Da hash_to_ristretto255 keine Hash-to-Curve-Suite ist, hat sie keine Suite ID. Wenn ein ähnlicher Identifikator benötigt wird, MUSS er gemäß den Richtlinien in Abschnitt 8.10 mit den folgenden Parametern konstruiert werden:

• CURVE_ID: "ristretto255"
• HASH_ID: wie in Abschnitt 8.10 beschrieben
• MAP_ID: "R255MAP"
• ENC_VAR: "RO"

Wenn beispielsweise expand_message expand_message_xmd unter Verwendung von SHA-512 ist, ist der ERFORDERLICHE Identifikator:

ristretto255_XMD:SHA-512_R255MAP_RO_

Anhang C. Hashen auf decaf448

Ähnlich wie ristretto255 bietet decaf448 [ristretto255-decaf448] eine Gruppe mit Primordnung basierend auf curve448 [RFC7748]. Dieser Abschnitt beschreibt hash_to_decaf448, das eine Random-Oracle-Kodierung auf diese Gruppe implementiert, die eine gleichmäßige Ausgabeverteilung (Abschnitt 2.2.3) und dieselben Sicherheitseigenschaften und Schnittstellen wie die hash_to_curve-Funktion hat (Abschnitt 3).

Die decaf448-API definiert eine unidirektionale Abbildung ([ristretto255-decaf448], Abschnitt 5.3.4); dieser Abschnitt bezieht sich auf diese Abbildung als decaf448_map.

Die hash_to_decaf448-Funktion MUSS mit einer expand_message-Funktion instanziiert werden, die den in Abschnitt 5.3 gegebenen Anforderungen entspricht. Darüber hinaus MUSS sie ein Domain-Separation-Tag verwenden, das wie in Abschnitt 3.1 beschrieben konstruiert ist, und alle in Abschnitt 10.7 gegebenen Domain-Separation-Empfehlungen gelten bei der Implementierung von Protokollen, die hash_to_decaf448 verwenden.

hash_to_decaf448(msg)

Parameter:

• DST, ein Domain-Separation-Tag (siehe Diskussion oben).
• expand_message, eine Funktion, die eine Byte-Zeichenkette und ein Domain-Separation-Tag zu einer gleichmäßig verteilten zufälligen Byte-Zeichenkette erweitert (siehe Diskussion oben).
• decaf448_map, die unidirektionale Abbildung der decaf448-API.

Eingabe: msg, eine Byte-Zeichenkette beliebiger Länge. Ausgabe: P, ein Element der decaf448-Gruppe.

Schritte:

1. uniform_bytes = expand_message(msg, DST, 112)
2. P = decaf448_map(uniform_bytes)
3. return P

Da hash_to_decaf448 keine Hash-to-Curve-Suite ist, hat sie keine Suite ID. Wenn ein ähnlicher Identifikator benötigt wird, MUSS er gemäß den Richtlinien in Abschnitt 8.10 mit den folgenden Parametern konstruiert werden:

• CURVE_ID: "decaf448"
• HASH_ID: wie in Abschnitt 8.10 beschrieben
• MAP_ID: "D448MAP"
• ENC_VAR: "RO"

Wenn beispielsweise expand_message expand_message_xof unter Verwendung von SHAKE256 ist, ist der ERFORDERLICHE Identifikator:

decaf448_XOF:SHAKE256_D448MAP_RO_

Anhang D. Rationale Abbildungen

Dieser Abschnitt gibt rationale Abbildungen an, die beim Hashen auf verdrehte Edwards- oder Montgomery-Kurven verwendet werden können.

Gegeben eine verdrehte Edwards-Kurve zeigt Anhang D.1, wie eine entsprechende Montgomery-Kurve abgeleitet wird und wie von dieser Kurve auf die verdrehte Edwards-Kurve abgebildet wird. Diese Abbildung kann beim Hashen auf verdrehte Edwards-Kurven wie in Abschnitt 6.8 beschrieben verwendet werden.

Gegeben eine Montgomery-Kurve zeigt Anhang D.2, wie eine entsprechende Weierstrass-Kurve abgeleitet wird und wie von dieser Kurve auf die Montgomery-Kurve abgebildet wird. Diese Abbildung kann verwendet werden, um auf Montgomery- oder verdrehte Edwards-Kurven über die Shallue-van de Woestijne-Methode (Abschnitt 6.6.1) oder die vereinfachte SWU-Methode (Abschnitt 6.6.2) wie folgt zu hashen:

• Für Montgomery-Kurven zuerst auf die Weierstrass-Kurve abbilden, dann über die Abbildung in Montgomery-Koordinaten konvertieren.

• Für verdrehte Edwards-Kurven die Abbildung von Weierstrass nach Montgomery mit der Abbildung von Montgomery nach verdrehter Edwards (Anhang D.1) komponieren, um eine Weierstrass-Kurve und eine Abbildung auf die verdrehte Edwards-Zielkurve zu erhalten. Auf diese Weierstrass-Kurve abbilden, dann über die Abbildung in Edwards-Koordinaten konvertieren.

D.1. Generische Abbildung von Montgomery nach verdrehter Edwards

Dieser Abschnitt gibt eine generische birationale Abbildung zwischen verdrehten Edwards- und Montgomery-Kurven an.

Die Abbildung in diesem Abschnitt ist eine vereinfachte Version der in [BBJLP08], Theorem 3.2 angegebenen Abbildung. Insbesondere behandelt die Abbildung in diesem Abschnitt die Ausnahmefälle auf eine vereinfachte Weise, die auf das Hashen auf die Untergruppe mit Primordnung einer verdrehten Edwards-Kurve ausgerichtet ist.

Die verdrehte Edwards-Kurve a * v^2 + w^2 = 1 + d * v^2 * w^2 ist birational äquivalent zur Montgomery-Kurve K * t^2 = s^3 + J * s^2 + s die die für die Elligator 2-Abbildung aus Abschnitt 6.7.1 erforderliche Form hat. Die Koeffizienten der Montgomery-Kurve sind:

• J = 2 * (a + d) / (a - d)
• K = 4 / (a - d)

Die rationale Abbildung vom Punkt (s, t) auf der obigen Montgomery-Kurve zum Punkt (v, w) auf der verdrehten Edwards-Kurve ist gegeben durch:

• v = s / t
• w = (s - 1) / (s + 1)

Diese Abbildung ist nicht definiert, wenn t == 0 oder s == -1, d.h. der Nenner einer der obigen rationalen Funktionen ist null. Implementierungen MÜSSEN die Ausnahmefälle erkennen und den Wert (v, w) = (0, 1) zurückgeben, der das Identitätselement auf allen verdrehten Edwards-Kurven ist.

Die folgende Straight-Line-Prozedur der obigen rationalen Abbildung behandelt die Ausnahmefälle.

monty_to_edw_generic(s, t)

Eingabe: (s, t), ein Punkt auf der Kurve K * t^2 = s^3 + J * s^2 + s. Ausgabe: (v, w), ein Punkt auf einer äquivalenten verdrehten Edwards-Kurve.

1. tv1 = s + 1
2. tv2 = tv1 * t # (s + 1) * t
3. tv2 = inv0(tv2) # 1 / ((s + 1) * t)
4. v = tv2 * tv1 # 1 / t
5. v = v * s # s / t
6. w = tv2 * t # 1 / (s + 1)
7. tv1 = s - 1
8. w = w * tv1 # (s - 1) / (s + 1)
9. e = tv2 == 0
10. w = CMOV(w, 1, e) # Ausnahmefall behandeln
11. return (v, w)

Der Vollständigkeit halber geben wir auch die inversen Beziehungen an. (Beachten Sie, dass diese Abbildung beim Hashen auf verdrehte Edwards-Kurven nicht erforderlich ist.) Die Koeffizienten der verdrehten Edwards-Kurve, die der obigen Montgomery-Kurve entsprechen, sind:

• a = (J + 2) / K
• d = (J - 2) / K

Die rationale Abbildung vom Punkt (v, w) auf der verdrehten Edwards-Kurve zum Punkt (s, t) auf der Montgomery-Kurve ist gegeben durch:

• s = (1 + w) / (1 - w)
• t = (1 + w) / (v * (1 - w))

Die Abbildung ist nicht definiert, wenn v == 0 oder w == 1. Wenn das Ziel darin besteht, in die Untergruppe mit Primordnung der Montgomery-Kurve abzubilden, genügt es, in den Ausnahmefällen das Identitätselement auf der Montgomery-Kurve zurückzugeben.

D.2. Abbildung von Weierstrass nach Montgomery

Die rationale Abbildung vom Punkt (s, t) auf der Montgomery-Kurve K * t^2 = s^3 + J * s^2 + s zum Punkt (x, y) auf der äquivalenten Weierstrass-Kurve y^2 = x^3 + A * x + B ist gegeben durch:

• A = (3 - J^2) / (3 * K^2)
• B = (2 * J^3 - 9 * J) / (27 * K^3)
• x = (3 * s + J) / (3 * K)
• y = t / K

Die inverse Abbildung vom Punkt (x, y) zum Punkt (s, t) ist gegeben durch:

• s = (3 * K * x - J) / 3
• t = y * K

Anhang E. Isogenie-Abbildungen für Suites

Dieser Abschnitt spezifiziert die Isogenie-Abbildungen für die in Abschnitt 8 aufgeführten secp256k1- und BLS12-381-Suites.

Diese Abbildungen sind in Form von affinen Koordinaten angegeben. Wahby und Boneh ([WB19], Abschnitt 4.3) zeigen, wie diese Abbildungen in einem projektiven Koordinatensystem (Anhang G.1) ausgewertet werden können, was modulare Inversionen vermeidet.

Siehe [hash2curve-repo] für ein Sage-Skript [SAGE], das diese Isogenien konstruiert.

E.1. Isogenie-3-Abbildung für secp256k1

Dieser Abschnitt spezifiziert die Isogenie-Abbildung für die in Abschnitt 8.7 aufgeführte secp256k1-Suite.

Die Isogenie-3-Abbildung von (x', y') auf E' zu (x, y) auf E ist durch die folgenden rationalen Funktionen gegeben:

• x = x_num / x_den, wobei

  • x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + k_(1,0)
  • x_den = x'^2 + k_(2,1) * x' + k_(2,0)

• y = y' * y_num / y_den, wobei

  • y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' + k_(3,0)
  • y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0)

Die zur Berechnung von x_num verwendeten Konstanten sind wie folgt:

• k_(1,0) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7
• k_(1,1) = 0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581
• k_(1,2) = 0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262
• k_(1,3) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c

Die zur Berechnung von x_den verwendeten Konstanten sind wie folgt:

• k_(2,0) = 0xd35771193d94918a9ca34ccbb7b640dd86cd409542f8487d9fe6b745781eb49b
• k_(2,1) = 0xedadc6f64383dc1df7c4b2d51b54225406d36b641f5e41bbc52a56612a8c6d14

Die zur Berechnung von y_num verwendeten Konstanten sind wie folgt:

• k_(3,0) = 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
• k_(3,1) = 0xc75e0c32d5cb7c0fa9d0a54b12a0a6d5647ab046d686da6fdffc90fc201d71a3
• k_(3,2) = 0x29a6194691f91a73715209ef6512e576722830a201be2018a765e85a9ecee931
• k_(3,3) = 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84

Die zur Berechnung von y_den verwendeten Konstanten sind wie folgt:

• k_(4,0) = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b
• k_(4,1) = 0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573
• k_(4,2) = 0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f

hinweis

Aufgrund der erheblichen Länge der Anhänge E, F, G, H, I und J (die zahlreiche hexadezimale Konstanten, Implementierungscode und Testvektoren enthalten), wurde der vollständige Inhalt aus Gründen der Kürze aus dieser Dokumentation weggelassen.

Um die vollständigen Anhänge einzusehen, einschließlich:

• Anhang E: Vollständige Isogenie-Abbildungen für BLS12-381 G1 und G2
• Anhang F: Straight-Line-Implementierungen deterministischer Abbildungen
• Anhang G: Kurvenspezifischer optimierter Beispielcode
• Anhang H: Skripte zur Parametergenerierung
• Anhang I: sqrt- und is_square-Funktionen
• Anhang J: Vollständige Suite-Testvektoren für alle Kurven

Bitte beziehen Sie sich auf das Original-RFC 9380-Dokument.

Danksagungen

Die Autoren möchten Adam Langley für seine detaillierte Beschreibung von Elligator 2 mit Curve25519 [L13] danken; Dan Boneh, Benjamin Lipp, Christopher Patton und Leonid Reyzin für lehrreiche Diskussionen; und David Benjamin, Daniel Bourdrez, Frank Denis, Sean Devlin, Justin Drake, Bjoern Haase, Mike Hamburg, Dan Harkins, Daira Hopwood, Thomas Icart, Andy Polyakov, Thomas Pornin, Mamy Ratsimbazafy, Michael Scott, Filippo Valsorda und Mathy Vanhoef für ihre konstruktive Kritik und Kommentare.

Mitwirkende

Sharon Goldberg
Boston University
E-Mail: [email protected]

Ela Lee
Royal Holloway, University of London
E-Mail: [email protected]

Michele Orru
E-Mail: [email protected]

Adressen der Autoren

Armando Faz-Hernandez
Cloudflare, Inc.
E-Mail: [email protected]

Sam Scott
Oso Security, Inc.
E-Mail: [email protected]

Nick Sullivan
Cloudflare, Inc.
E-Mail: [email protected]

Riad S. Wahby
Stanford University
E-Mail: [email protected]

Christopher A. Wood
Cloudflare, Inc.
E-Mail: [email protected]