2. Hintergrund
2.1. Elliptische Kurven
Im Folgenden findet sich eine kurze Definition elliptischer Kurven mit Schwerpunkt auf wichtigen Parametern und deren Bezug zum Hashing auf Kurven. Weiterführende Informationen zu elliptischen Kurven finden sich in [CFADLNV05] oder [W08].
Sei F der endliche Körper GF(q) mit Primzahlcharakteristik p > 3. (Dieses Dokument betrachtet keine elliptischen Kurven über Körpern der Charakteristik 2 oder 3.) In den meisten Fällen ist F ein Primkörper, es gilt also q = p. Andernfalls ist F ein Erweiterungskörper, sodass q = p^m für eine ganze Zahl m > 1 gilt. Dieses Dokument schreibt Elemente von Erweiterungskörpern in einer Basis aus primitiven Elementen bzw. in einer Polynombasis, d. h. als Vektor aus m Elementen von GF(p), aufsteigend nach Grad geordnet. Die Einträge dieses Vektors werden aufsteigend ab 1 indiziert, d. h. x = (x_1, x_2, ..., x_m). Ist beispielsweise q = p^2 und die Basis aus primitiven Elementen (1, I), so entspricht x = (a, b) dem Element a + b * I, wobei x_1 = a und x_2 = b gilt. (Alle Basiswahlen sind zueinander isomorph, bestimmte Wahlen können jedoch zu einer effizienteren Implementierung führen; dieses Dokument trifft keine besonderen Annahmen über die Wahl der Basis.)
Eine elliptische Kurve E wird durch eine Gleichung in zwei Variablen und einen endlichen Körper F festgelegt. Eine Gleichung einer elliptischen Kurve besitzt eine von mehreren Standardformen, darunter (aber nicht beschränkt auf) die Weierstraß-, Montgomery- und Edwards-Form.
Die Kurve E induziert eine algebraische Gruppe der Ordnung n, d. h. die Gruppe besitzt n verschiedene Elemente. (Dieses Dokument verwendet additive Notation für die Gruppenoperation auf elliptischen Kurven.) Elemente einer elliptischen Kurvengruppe sind Punkte mit affinen Koordinaten (x, y), welche die Kurvengleichung erfüllen, wobei x und y Elemente von F sind. Darüber hinaus besitzen alle elliptischen Kurvengruppen ein ausgezeichnetes Element, den Identitätspunkt, der als neutrales Element der Gruppenoperation fungiert. Auf bestimmten Kurven (einschließlich Weierstraß- und Montgomery-Kurven) lässt sich der Identitätspunkt nicht als Koordinatenpaar (x, y) darstellen.
Aus Sicherheitsgründen erfordern kryptografische Anwendungen elliptischer Kurven im Allgemeinen die Verwendung einer (Unter-)Gruppe von Primzahlordnung. Sei G eine solche Untergruppe der Kurve mit Primzahlordnung r, wobei n = h * r gilt. In dieser Gleichung ist h eine ganze Zahl, die als Kofaktor bezeichnet wird. Ein Algorithmus, der als Eingabe einen beliebigen Punkt auf der Kurve E entgegennimmt und als Ausgabe einen Punkt in der Untergruppe G von E liefert, wird als „Kofaktor-Beseitigung" (clear the cofactor) bezeichnet. Solche Algorithmen werden in Abschnitt 7 behandelt.
Bestimmte Hash-to-Curve-Algorithmen schränken die Form der Kurvengleichung, die Charakteristik des Körpers oder die Parameter der Kurve ein. Für jeden vorgestellten Algorithmus führt dieses Dokument die relevanten Einschränkungen auf.
Die nachstehende Tabelle fasst die für das Hashing auf Kurven relevanten Größen zusammen:
| Symbol | Bedeutung | Relevanz |
|---|---|---|
| F,q,p | Ein endlicher Körper F der Charakteristik p mit #F = q = p^m. | Für Primkörper gilt q = p; andernfalls q = p^m mit m>1. |
| E | Elliptische Kurve. | E wird durch eine Gleichung und einen Körper F festgelegt. |
| n | Anzahl der Punkte auf der elliptischen Kurve E. | n = h * r, mit h und r wie unten definiert. |
| G | Eine Untergruppe der Punkte auf E mit Primzahlordnung. | G ist die Zielgruppe, in die Bytestrings codiert werden. |
| r | Ordnung von G. | r ist ein Primfaktor von n (üblicherweise der größte solche Faktor). |
| h | Kofaktor, h >= 1. | h ist eine ganze Zahl mit n = h * r. |
Tabelle 1: Übersicht der Symbole und ihrer Definitionen
2.2. Terminologie
In diesem Abschnitt definieren wir wichtige Begriffe, die im gesamten Dokument verwendet werden.
2.2.1. Abbildungen
Eine Abbildung (Mapping) ist eine deterministische Funktion von einem Element des Körpers F auf einen Punkt einer über F definierten elliptischen Kurve E.
Im Allgemeinen kann die Menge aller Punkte, die eine Abbildung über alle möglichen Eingaben erzeugen kann, nur eine Teilmenge der Punkte einer elliptischen Kurve sein (d. h. die Abbildung muss nicht surjektiv sein). Darüber hinaus kann eine Abbildung für zwei oder mehr verschiedene Eingaben denselben Punkt ausgeben (d. h. die Abbildung muss nicht injektiv sein). Betrachten wir beispielsweise eine Abbildung von F auf eine elliptische Kurve mit n Punkten: Ist die Anzahl der Elemente von F ungleich n, so kann diese Abbildung nicht bijektiv sein (d. h. sowohl injektiv als auch surjektiv), da die Abbildung als deterministisch definiert ist.
Abbildungen können außerdem invertierbar sein, d. h. es existiert ein effizienter Algorithmus, der für jeden von der Abbildung ausgegebenen Punkt P ein x in F liefert, sodass die Anwendung der Abbildung auf x den Punkt P ergibt. Einige der in Abschnitt 6 angegebenen Abbildungen sind invertierbar, dieses Dokument behandelt jedoch keine Inversionsalgorithmen.
2.2.2. Codierungen
Codierungen (Encodings) sind eng mit Abbildungen verwandt. Wie eine Abbildung ist eine Codierung eine Funktion, die einen Punkt auf einer elliptischen Kurve ausgibt. Im Gegensatz zu einer Abbildung ist die Eingabe einer Codierung jedoch ein Bytestring beliebiger Länge.
Dieses Dokument konstruiert deterministische Codierungen durch Komposition einer Hashfunktion Hf mit einer deterministischen Abbildung. Konkret nimmt Hf einen beliebigen String als Eingabe entgegen und gibt ein Element von F aus. Die deterministische Abbildung nimmt dieses Element als Eingabe und gibt einen Punkt auf einer über F definierten elliptischen Kurve E aus. Da Hf Bytestrings beliebiger Länge als Eingaben entgegennimmt, kann sie nicht injektiv sein: Die Menge der Eingaben ist größer als die Menge der Ausgaben, also muss es verschiedene Eingaben geben, die dieselbe Ausgabe liefern (d. h. es muss Kollisionen geben). Folglich ist auch jede aus Hf gebildete Codierung nicht injektiv.
Wie Abbildungen können auch Codierungen invertierbar sein, d. h. es existiert ein effizienter Algorithmus, der für jeden von der Codierung ausgegebenen Punkt P einen String s liefert, sodass die Anwendung der Codierung auf s den Punkt P ergibt. Die Instanziierung von Hf, die von allen in diesem Dokument spezifizierten Codierungen verwendet wird (Abschnitt 5), ist jedoch nicht invertierbar; somit sind auch diese Codierungen nicht invertierbar.
In manchen Anwendungen des Hashings auf elliptische Kurven ist es wichtig, dass Codierungen keine Informationen über Seitenkanäle preisgeben. [VR20] ist ein Beispiel dafür, wie diese Art von Informationsabfluss zu einer Sicherheitslücke führt. Siehe Abschnitt 10.3 für eine weitergehende Diskussion.
2.2.3. Zufallsorakel-Codierungen
Eine Zufallsorakel-Codierung (random-oracle encoding) erfüllt eine starke Eigenschaft: Sie kann unter einer geeigneten Annahme als ununterscheidbar (indifferentiable) von einem Zufallsorakel [MRH04] bewiesen werden.
Beide in Abschnitt 3 beschriebenen Konstruktionen sind von Zufallsorakeln [MRH04] ununterscheidbar, sofern sie gemäß den Leitlinien dieses Dokuments instanziiert werden. Die Konstruktionen unterscheiden sich in ihren Ausgabeverteilungen: Die eine liefert einen gleichverteilt zufälligen Punkt auf der Kurve, die andere einen Punkt aus einer nicht gleichmäßigen Verteilung.
Eine Zufallsorakel-Codierung mit gleichmäßiger Ausgabeverteilung eignet sich für die Verwendung in vielen kryptografischen Protokollen, deren Sicherheit im Zufallsorakel-Modell bewiesen wurde. Siehe Abschnitt 10.1 für eine weitergehende Diskussion.
2.2.4. Serialisierung
Ein mit der Codierung verwandtes Verfahren ist die Umwandlung eines Punktes einer elliptischen Kurve in einen Bitstring. Dies wird als Serialisierung bezeichnet und typischerweise zur kompakten Speicherung oder Übertragung von Punkten verwendet. Die Umkehroperation, die Deserialisierung, wandelt einen Bitstring in einen Punkt einer elliptischen Kurve um. Beispielsweise geben [SEC1] und [p1363a] Standardmethoden für Serialisierung und Deserialisierung an.
Die Deserialisierung unterscheidet sich von der Codierung dadurch, dass nur bestimmte Strings (nämlich jene, die von der Serialisierungsprozedur ausgegeben werden) deserialisiert werden können. Dieses Dokument befasst sich dagegen mit Codierungen von beliebigen Strings auf Punkte elliptischer Kurven. Serialisierung und Deserialisierung werden in diesem Dokument nicht behandelt.
2.2.5. Domänentrennung
Kryptografische Protokolle, deren Sicherheit im Zufallsorakel-Modell bewiesen wurde, werden häufig unter der Annahme analysiert, dass das Zufallsorakel ausschließlich Anfragen beantwortet, die mit diesem Protokoll zusammenhängen (einschließlich Anfragen von Angreifern) [BR93]. In der Praxis gilt diese Annahme nicht, wenn zwei Protokolle dieselbe Funktion zur Instanziierung des Zufallsorakels verwenden. Konkret betrachte man die Protokolle P1 und P2, die ein Zufallsorakel RO abfragen: Fragen P1 und P2 beide RO mit demselben Wert x ab, so kann die Sicherheitsanalyse eines oder beider Protokolle ungültig werden.
Ein gängiger Ansatz zur Behebung dieses Problems ist die Domänentrennung (domain separation), die es einem einzelnen Zufallsorakel erlaubt, mehrere unabhängige Orakel zu simulieren. Dies wird dadurch erreicht, dass sichergestellt wird, dass jedes simulierte Orakel Anfragen sieht, die sich von denen aller anderen simulierten Orakel unterscheiden. Um beispielsweise zwei Orakel RO1 und RO2 mithilfe eines einzigen Orakels 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änentrennungs-Tags (DSTs) bezeichnet; sie stellen sicher, dass Anfragen an RO1 und RO2 nicht zu identischen Anfragen an RO führen können, sodass RO1 und RO2 sicher als unabhängige Orakel behandelt werden können.
Im Allgemeinen erfordert die Domänentrennung die Definition einer eindeutigen injektiven Codierung für jedes simulierte Orakel. Im obigen Beispiel besitzen "RO1" und "RO2" dieselbe Länge und erfüllen diese Anforderung somit bei Verwendung als Präfixe. Die in diesem Dokument spezifizierten Algorithmen verfolgen einen anderen Ansatz zur Sicherstellung der Injektivität; siehe Abschnitte 5.3 und 10.7 für weitere Einzelheiten.