2. Hintergrund

Im Folgenden finden Sie eine kurze Definition elliptischer Kurven mit Schwerpunkt auf den wichtigen Parametern und deren Beziehung zum Hashing auf Kurven. Weitere Informationen zu elliptischen Kurven finden Sie unter [CFADLNV05] oder [W08].

2.1. Elliptische Kurven

Sei F das endliche Feld GF(q) mit der Primzahl-Charakteristik p > 3. (Dieses Dokument berücksichtigt keine elliptischen Kurven über Feldern der Charakteristik 2 oder 3.) In den meisten Fällen ist F ein Primfeld, also q = p. Andernfalls ist F ein Erweiterungsfeld, also q = p^m für eine ganze Zahl m > 1. In diesem Dokument werden Elemente von Erweiterungsfeldern in einer Primitiv- oder Polynombasis geschrieben, d. h. als Vektor von m Elementen aus GF(p), die in aufsteigender Reihenfolge des Grades geschrieben werden. Die Einträge dieses Vektors werden in aufsteigender Reihenfolge beginnend mit 1 indiziert, d. h. x = (x_1, x_2, ..., x_m). Wenn beispielsweise q = p^2 und die Primitivbasis (1, I) ist, dann entspricht x = (a, b) dem Element a + b * I, wobei x_1 = a und x_2 = b ist. (Beachten Sie, dass alle Basisentscheidungen isomorph sind, aber einige Entscheidungen zu einer effizienteren Implementierung führen können; dieses Dokument trifft keine besonderen Annahmen über die Wahl der Basis.)

Eine elliptische Kurve E wird durch eine Gleichung in zwei Variablen und ein endliches Feld F spezifiziert. Eine elliptische Kurvengleichung nimmt eine von mehreren Standardformen an, einschließlich (aber nicht beschränkt auf) Weierstrass, Montgomery und Edwards.

Die Kurve E induziert eine algebraische Gruppe der Ordnung n, was bedeutet, dass die Gruppe n verschiedene Elemente hat. (Dieses Dokument verwendet die additive Notation für die Gruppenoperation der elliptischen Kurve.) Die Elemente einer elliptischen Kurvengruppe sind Punkte mit affinen Koordinaten (x, y), die die Kurvengleichung erfüllen, wobei x und y Elemente von F sind. Darüber hinaus haben alle elliptischen Kurvengruppen ein ausgezeichnetes Element, den Punkt im Unendlichen oder Identitätspunkt, der als Identitätselement für die Gruppenoperation fungiert. Auf einigen Kurven (einschließlich Weierstrass- und Montgomery-Kurven) kann der Identitätspunkt nicht als Koordinatenpaar (x, y) dargestellt werden.

Aus Sicherheitsgründen erfordern kryptografische Anwendungen elliptischer Kurven in der Regel die Verwendung einer (Unter-)Gruppe von Primzahlordnung. Sei G eine solche Untergruppe der Kurve der Primzahlordnung r, wobei n = h * r. In dieser Gleichung ist h eine ganze Zahl, die als Kofaktor bezeichnet wird. Ein Algorithmus, der einen beliebigen Punkt auf der Kurve E als Eingabe nimmt und einen Punkt in der Untergruppe G von E als Ausgabe liefert, wird als „Kofaktor-Bereinigung“ bezeichnet. Solche Algorithmen werden in Abschnitt 7 besprochen.

Einige Hash-to-Curve-Algorithmen schränken die Form der Kurvengleichung, die Charakteristik des Feldes oder die Kurvenparameter ein. Für jeden vorgestellten Algorithmus führt dieses Dokument die relevanten Einschränkungen auf.

Die folgende Tabelle fasst die für das Hashing auf Kurven relevanten Größen zusammen:

Symbol	Bedeutung	Relevanz
F,q,p	Ein endliches Feld F der Charakteristik p und #F = q = p^m.	Für Primfelder q = p; andernfalls q = p^m und m>1.
E	Elliptische Kurve.	E wird durch eine Gleichung und ein Feld F spezifiziert.
n	Anzahl der Punkte auf der elliptischen Kurve E.	n = h * r, wobei h und r wie unten definiert sind.
G	Eine Untergruppe von Punkten auf E mit Primzahlordnung.	G ist die Zielgruppe, auf die Byte-Strings kodiert werden.
r	Ordnung von G.	r ist ein Primfaktor von n (normalerweise der größte dieser Faktoren).
h	Kofaktor, h >= 1.	h ist eine ganze Zahl, die n = h * r erfüllt.

Tabelle 1: Zusammenfassung der Symbole und ihrer Definitionen

2.2. Terminologie

In diesem Abschnitt definieren wir die wichtigsten Begriffe, die im gesamten Dokument verwendet werden.

2.2.1. Abbildungen

Eine Abbildung (Mapping) ist eine deterministische Funktion von einem Element des Feldes F auf einen Punkt auf einer über F definierten elliptischen Kurve E.

Im Allgemeinen kann die Menge aller Punkte, die eine Abbildung für alle möglichen Eingaben erzeugen kann, nur eine Teilmenge der Punkte einer elliptischen Kurve sein (d. h. die Abbildung ist möglicherweise nicht surjektiv). Außerdem kann eine Abbildung denselben Punkt für zwei oder mehr verschiedene Eingaben erzeugen (d. h. die Abbildung ist möglicherweise nicht injektiv). Betrachten wir zum Beispiel eine Abbildung von F auf eine elliptische Kurve mit n Punkten: Wenn die Anzahl der Elemente von F nicht gleich n ist, kann diese Abbildung nicht bijektiv (d. h. sowohl injektiv als auch surjektiv) sein, da die Abbildung als deterministisch definiert ist.

Abbildungen können auch invertierbar sein, was bedeutet, dass ein effizienter Algorithmus existiert, der für jeden durch die Abbildung erzeugten Punkt P ein x in F liefert, so dass die Anwendung der Abbildung auf x P ergibt. Einige der in Abschnitt 6 angegebenen Abbildungen sind invertierbar, aber dieses Dokument behandelt keine Inversionsalgorithmen.

2.2.2. Kodierungen

Kodierungen (Encodings) sind eng mit Abbildungen verwandt. Wie eine Abbildung ist eine Kodierung eine Funktion, die einen Punkt auf einer elliptischen Kurve erzeugt. Im Gegensatz zu einer Abbildung ist die Eingabe einer Kodierung jedoch ein Byte-String beliebiger Länge.

Dieses Dokument konstruiert deterministische Kodierungen durch Komposition einer Hash-Funktion Hf mit einer deterministischen Abbildung. Insbesondere nimmt Hf einen beliebigen String als Eingabe und liefert ein Element von F. Die deterministische Abbildung nimmt dieses Element als Eingabe und erzeugt einen Punkt auf einer über F definierten elliptischen Kurve E. Da Hf Byte-Strings beliebiger Länge als Eingabe nimmt, kann sie nicht injektiv sein: Die Menge der Eingaben ist größer als die Menge der Ausgaben, daher muss es verschiedene Eingaben geben, die dieselbe Ausgabe liefern (d. h. es muss Kollisionen geben). Somit ist auch jede aus Hf konstruierte Kodierung nicht injektiv.

Wie Abbildungen können auch Kodierungen invertierbar sein, was bedeutet, dass ein effizienter Algorithmus existiert, der für jeden durch die Kodierung erzeugten Punkt P einen String s liefert, so dass die Anwendung der Kodierung auf s P ergibt. Die Instanziierung von Hf, die von allen in diesem Dokument spezifizierten Kodierungen verwendet wird (Abschnitt 5), ist jedoch nicht invertierbar; daher sind auch diese Kodierungen nicht invertierbar.

In einigen Anwendungen des Hashings auf elliptische Kurven ist es wichtig, dass Kodierungen keine Informationen über Seitenkanäle preisgeben. [VR20] ist ein Beispiel für eine solche Leckage, die zu einer Sicherheitsanfälligkeit führt. Siehe Abschnitt 10.3 für weitere Details.

2.2.3. Zufallsorakel-Kodierungen

Eine Zufallsorakel-Kodierung (Random Oracle Encoding) erfüllt eine starke Eigenschaft: Es kann nachgewiesen werden, dass sie unter einer geeigneten Annahme von einem Zufallsorakel [MRH04] ununterscheidbar ist.

Die beiden in Abschnitt 3 beschriebenen Konstruktionen sind von Zufallsorakeln [MRH04] ununterscheidbar, wenn sie gemäß den Empfehlungen dieses Dokuments instanziiert werden. Die Konstruktionen unterscheiden sich in ihren Ausgabeverteilungen: Eine liefert einen gleichmäßig zufälligen Punkt auf der Kurve, die andere liefert einen Punkt, der aus einer nicht gleichmäßigen Verteilung abgetastet wurde.

Eine Zufallsorakel-Kodierung mit einer gleichmäßigen Ausgabeverteilung eignet sich für die Verwendung in vielen kryptografischen Protokollen, deren Sicherheit im Zufallsorakel-Modell nachgewiesen wird. Siehe Abschnitt 10.1 für weitere Details.

2.2.4. Serialisierung

Ein mit der Kodierung verwandtes Verfahren ist die Umwandlung eines elliptischen Kurvenpunkts in einen Bit-String. Dies wird als Serialisierung bezeichnet und in der Regel verwendet, um Punkte kompakt zu speichern oder zu übertragen. Die Umkehroperation, die Deserialisierung, wandelt einen Bit-String wieder in einen elliptischen Kurvenpunkt um. Beispielsweise enthalten [SEC1] und [p1363a] Standardmethoden für die Serialisierung und Deserialisierung.

Die Deserialisierung unterscheidet sich von der Kodierung dadurch, dass nur bestimmte Strings (nämlich solche, die durch das Serialisierungsverfahren erzeugt wurden) deserialisiert werden können. Im Gegensatz dazu befasst sich dieses Dokument mit Kodierungen beliebiger Strings auf elliptische Kurvenpunkte. Die Serialisierung oder Deserialisierung wird in diesem Dokument nicht behandelt.

2.2.5. Domänentrennung

Kryptografische Protokolle, deren Sicherheit im Zufallsorakel-Modell nachgewiesen wird, werden oft unter der Annahme analysiert, dass das Zufallsorakel nur auf Anfragen antwortet, die mit diesem Protokoll verknüpft sind (einschließlich Anfragen von Angreifern) [BR93]. In der Praxis ist diese Annahme nicht haltbar, wenn zwei Protokolle dieselbe Funktion zur Instanziierung des Zufallsorakels verwenden. Konkret betrachten wir die Protokolle P1 und P2, die ein Zufallsorakel RO abfragen: Wenn sowohl P1 als auch P2 RO mit demselben Wert x abfragen, kann die Sicherheitsanalyse eines oder beider Protokolle ungültig werden.

Ein üblicher Weg, dieses Problem anzugehen, wird als Domänentrennung (Domain Separation) bezeichnet. Sie ermöglicht es einem einzigen Zufallsorakel, mehrere unabhängige Orakel zu simulieren. Dies wird dadurch erreicht, dass sichergestellt wird, dass jedes simulierte Orakel Anfragen sieht, die sich von den Anfragen aller anderen simulierten Orakel unterscheiden. Um beispielsweise zwei Orakel RO1 und RO2 aus einem einzigen Orakel RO zu simulieren, könnte man definieren:

RO1(x) := RO("RO1" || x) RO2(x) := RO("RO2" || x)

wobei || der Konkatenationsoperator ist. In diesem Beispiel werden „RO1“ und „RO2“ als Domänentrennung-Tags (DST) bezeichnet; sie stellen sicher, dass Anfragen an RO1 und RO2 nicht zu identischen Anfragen an RO führen können, was bedeutet, dass RO1 und RO2 sicher als unabhängige Orakel behandelt werden können.

Im Allgemeinen erfordert die Domänentrennung die Definition einer separaten injektiven Kodierung für jedes simulierte Orakel. Im obigen Beispiel haben „RO1“ und „RO2“ die gleiche Länge und erfüllen daher diese Anforderung, wenn sie als Präfixe verwendet werden. Die in diesem Dokument spezifizierten Algorithmen verwenden einen anderen Ansatz, um Injektivität zu gewährleisten; siehe Abschnitte 5.3 und 10.7 für weitere Details.