3. Kodierung von Byte-Strings auf elliptische Kurven

Dieser Abschnitt präsentiert ein allgemeines Framework und eine Schnittstelle für die Kodierung von Byte-Strings auf Punkte einer elliptischen Kurve. Die Konstruktionen in diesem Abschnitt basieren auf drei grundlegenden Funktionen:

• Die Funktion hash_to_field hasht Byte-Strings beliebiger Länge auf eine Liste von einem oder mehreren Elementen eines endlichen Feldes F; ihre Implementierung ist in Abschnitt 5 definiert.

  hash_to_field(msg, count)

  Eingabe:

  • msg, ein Byte-String, der die zu hashende Nachricht enthält.
  • count, die Anzahl der zu erzeugenden Elemente von F.

  Ausgabe:

  • (u_0, ..., u_(count - 1)), eine Liste von Feldelementen.

• Die Funktion map_to_curve berechnet einen Punkt auf der elliptischen Kurve E aus einem Element des endlichen Feldes F, über dem E definiert ist. Abschnitt 6 beschreibt Abbildungen für eine Reihe von Kurvenfamilien.

  map_to_curve(u)

  Eingabe: u, ein Element des Feldes F. Ausgabe: Q, ein Punkt auf der elliptischen Kurve E.

• Die Funktion clear_cofactor sendet jeden Punkt auf der Kurve E zur Untergruppe G von E. Abschnitt 7 beschreibt Methoden zur Durchführung dieser Operation.

  clear_cofactor(Q)

  Eingabe: Q, ein Punkt auf der elliptischen Kurve E. Ausgabe: P, ein Punkt in G.

Die beiden in diesem Abschnitt definierten Kodierungen (Abschnitt 2.2.2) haben dieselbe Schnittstelle und sind beide Zufallsorakel-Kodierungen (Abschnitt 2.2.3). Beide sind als Komposition der drei oben genannten Grundfunktionen implementiert. Der Unterschied zwischen den beiden besteht darin, dass ihre Ausgaben aus unterschiedlichen Verteilungen abgetastet werden:

• encode_to_curve ist eine nicht-uniforme Kodierung von Byte-Strings auf Punkte in G. Das heißt, die Verteilung ihrer Ausgabe ist nicht gleichmäßig zufällig in G: Die Menge der möglichen Ausgaben von encode_to_curve ist nur ein Bruchteil der Punkte in G, und einige Punkte in dieser Menge werden mit höherer Wahrscheinlichkeit ausgegeben als andere. Abschnitt 10.4 gibt eine präzisere Definition der Ausgabeverteilung von encode_to_curve.

  encode_to_curve(msg)

  Eingabe: msg, ein Byte-String beliebiger Länge. Ausgabe: P, ein Punkt in G.

  Schritte:

  1. u = hash_to_field(msg, 1)
  2. Q = map_to_curve(u[0])
  3. P = clear_cofactor(Q)
  4. return P

• hash_to_curve ist eine uniforme Kodierung von Byte-Strings auf Punkte in G. Das heißt, die Verteilung ihrer Ausgabe ist statistisch nahe an der Gleichverteilung in G.

  Diese Funktion eignet sich für die meisten Anwendungen, die ein Zufallsorakel benötigen, das Punkte in G zurückgibt, wenn sie mit einer der in Abschnitt 6 beschriebenen map_to_curve-Funktionen instanziiert wird. Siehe Abschnitt 10.1 für weitere Diskussionen.

  hash_to_curve(msg)

  Eingabe: msg, ein Byte-String beliebiger Länge. Ausgabe: P, ein Punkt in G.

  Schritte:

  1. u = hash_to_field(msg, 2)
  2. Q0 = map_to_curve(u[0])
  3. Q1 = map_to_curve(u[1])
  4. R = Q0 + Q1 # Punktaddition
  5. P = clear_cofactor(R)
  6. return P

Jede Hash-to-Curve-Suite in Abschnitt 8 instanziiert eine dieser Kodierungsfunktionen für eine spezifische elliptische Kurve.

3.1. Anforderungen an die Domänentrennung

Alle Verwendungen der in diesem Dokument definierten Kodierungsfunktionen MÜSSEN Domänentrennung (Abschnitt 2.2.5) einschließen, um Interferenzen mit anderen Verwendungen ähnlicher Funktionalität zu vermeiden.

Anwendungen, die mehrere unabhängige Instanzen von hash_to_curve oder encode_to_curve instanziieren, MÜSSEN Domänentrennung zwischen diesen Instanzen durchsetzen. Diese Anforderung gilt sowohl für den Fall mehrerer Instanzen, die auf dieselbe Kurve abzielen, als auch für den Fall mehrerer Instanzen, die auf verschiedene Kurven abzielen. (Dies liegt daran, dass die interne hash_to_field-Primitive (Abschnitt 5) Domänentrennung erfordert, um unabhängige Ausgaben zu garantieren.)

Die Domänentrennung wird mit einem Domänentrennungs-Tag (DST) durchgesetzt, das ein Byte-String ist, der gemäß den folgenden Anforderungen konstruiert wird:

1. Tags MÜSSEN als DST-Parameter an hash_to_field übergeben werden, wie in Abschnitt 5 beschrieben.

2. Tags MÜSSEN eine Länge ungleich Null haben. Eine Mindestlänge von 16 Bytes wird EMPFOHLEN, um die Wahrscheinlichkeit von Kollisionen mit anderen Anwendungen zu verringern.

3. Tags SOLLTEN mit einer festen Identifikationszeichenfolge beginnen, die für die Anwendung eindeutig ist.

4. Tags SOLLTEN eine Versionsnummer enthalten.

5. Für Anwendungen, die mehrere Cipher-Suites definieren, MUSS das Tag jeder Suite unterschiedlich sein. Zu diesem Zweck wird EMPFOHLEN, eine Cipher-Suite-Kennung in jedes Tag aufzunehmen.

6. Für Anwendungen, die mehrere Kodierungen verwenden, entweder auf dieselbe Kurve oder auf verschiedene Kurven, MUSS jede Kodierung ein anderes Tag verwenden. Zu diesem Zweck wird EMPFOHLEN, die Suite-ID der Kodierung (Abschnitt 8) in das Domänentrennungs-Tag aufzunehmen. Für unabhängige Kodierungen, die auf derselben Suite basieren, SOLLTE jedes Tag auch eine eindeutige Kennung enthalten, z. B. "ENC1" und "ENC2".

Als Beispiel betrachten Sie eine fiktive Anwendung namens Quux, die mehrere verschiedene Cipher-Suites definiert, jeweils für eine andere Kurve. Eine vernünftige Wahl für ein Tag ist "QUUX-V-CS-", wobei und zweistellige Zahlen sind, die die Version bzw. die Cipher-Suite angeben, und die Suite-ID der in Cipher-Suite verwendeten Kodierung ist.

Als weiteres Beispiel betrachten Sie eine fiktive Anwendung namens Baz, die zwei unabhängige Zufallsorakel auf dieselbe Kurve benötigt. Vernünftige Wahlmöglichkeiten für Tags für diese Orakel sind "BAZ-V-CS--ENC1" bzw. "BAZ-V-CS--ENC2", wobei , und wie oben beschrieben sind.

Die oben angegebenen Beispiel-Tags werden als ASCII-kodierte Byte-Strings ohne Null-Terminierung angenommen, was das EMPFOHLENE Format ist. Andere Kodierungen können verwendet werden, aber in allen Fällen MUSS die Kodierung als Byte-Sequenz eindeutig spezifiziert werden.