Zum Hauptinhalt springen

3. Codierung von Bytestrings auf elliptische Kurven

Dieser Abschnitt stellt ein allgemeines Rahmenwerk und eine Schnittstelle zur Codierung von Bytestrings auf Punkte elliptischer Kurven vor. Die Konstruktionen dieses Abschnitts stützen sich auf drei Basisfunktionen:

  • Die Funktion hash_to_field hasht Bytestrings beliebiger Länge auf eine Liste eines oder mehrerer Elemente eines endlichen Körpers F; ihre Implementierung ist in Abschnitt 5 definiert.
hash_to_field(msg, count)

Input:
- msg, a byte string containing the message to hash.
- count, the number of elements of F to output.

Output:
- (u_0, ..., u_(count - 1)), a list of field elements.

Steps: defined in Section 5.
  • Die Funktion map_to_curve berechnet aus einem Element des endlichen Körpers F, über dem E definiert ist, einen Punkt der elliptischen Kurve E. Abschnitt 6 beschreibt Abbildungen für eine ganze Reihe von Kurvenfamilien.
map_to_curve(u)

Input: u, an element of field F.
Output: Q, a point on the elliptic curve E.
Steps: defined in Section 6.
  • Die Funktion clear_cofactor bildet einen beliebigen Punkt der Kurve E auf die Untergruppe G von E ab. Abschnitt 7 beschreibt Methoden für diese Operation.
clear_cofactor(Q)

Input: Q, a point on the elliptic curve E.
Output: P, a point in G.
Steps: defined in Section 7.

Die beiden in diesem Abschnitt definierten Codierungen (Abschnitt 2.2.2) besitzen dieselbe Schnittstelle und sind beide Zufallsorakel-Codierungen (Abschnitt 2.2.3). Beide sind als Komposition der drei obigen Basisfunktionen implementiert. Der Unterschied zwischen beiden besteht darin, dass ihre Ausgaben aus unterschiedlichen Verteilungen gezogen werden:

  • encode_to_curve ist eine nicht gleichmäßige Codierung von Bytestrings auf Punkte in G. Das heißt, die Verteilung ihrer Ausgabe ist nicht gleichverteilt zufällig in G: Die Menge der möglichen Ausgaben von encode_to_curve umfasst nur einen Bruchteil der Punkte in G, und einige Punkte dieser Menge werden mit höherer Wahrscheinlichkeit erzeugt als andere. Abschnitt 10.4 gibt eine genauere Definition der Ausgabeverteilung von encode_to_curve.
encode_to_curve(msg)

Input: msg, an arbitrary-length byte string.
Output: P, a point in G.

Steps:
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 gleichmäßige Codierung von Bytestrings auf Punkte in G. Das heißt, die Verteilung ihrer Ausgabe ist statistisch nahe an der Gleichverteilung auf G.

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

hash_to_curve(msg)

Input: msg, an arbitrary-length byte string.
Output: P, a point in G.

Steps:
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              # Point addition
5. P = clear_cofactor(R)
6. return P

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

3.1. Anforderungen an die Domänentrennung​

Alle Verwendungen der in diesem Dokument definierten Codierungsfunktionen MÜSSEN eine 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 eine Domänentrennung zwischen diesen Instanzen erzwingen. 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 unterschiedliche Kurven abzielen. (Dies liegt daran, dass die interne Primitive hash_to_field (Abschnitt 5) eine Domänentrennung erfordert, um die Unabhängigkeit der Ausgaben zu gewährleisten.)

Die Domänentrennung wird mittels eines Domänentrennungs-Tags (DST) erzwungen, eines Bytestrings, 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 besitzen. Eine Mindestlänge von 16 Byte wird EMPFOHLEN, um das Kollisionsrisiko mit anderen Anwendungen zu verringern.

  3. Tags SOLLTEN mit einem festen, anwendungsspezifischen Kennungsstring beginnen.

  4. Tags SOLLTEN eine Versionsnummer enthalten.

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

  6. Bei Anwendungen, die mehrere Codierungen verwenden – sei es auf dieselbe oder auf unterschiedliche Kurven –, MUSS jede Codierung ein anderes Tag verwenden. Zu diesem Zweck wird EMPFOHLEN, die Suite-ID (Suite ID, Abschnitt 8) der Codierung in das Domänentrennungs-Tag aufzunehmen. Bei unabhängigen Codierungen, die auf derselben Suite beruhen, SOLLTE jedes Tag zusätzlich eine unterscheidende Kennung enthalten, beispielsweise „ENC1" und „ENC2".

Als Beispiel betrachte man eine fiktive Anwendung namens Quux, die mehrere unterschiedliche Cipher Suites definiert, jeweils für eine andere Kurve. Eine sinnvolle Tag-Wahl ist „QUUX-V<xx>-CS<yy>-<suiteID>", wobei <xx> und <yy> zweistellige Zahlen sind, welche die Version bzw. die Cipher Suite angeben, und <suiteID> die Suite-ID der in Cipher Suite <yy> verwendeten Codierung ist.

Ein weiteres Beispiel: Man betrachte eine fiktive Anwendung namens Baz, die zwei unabhängige Zufallsorakel auf dieselbe Kurve benötigt. Sinnvolle Tag-Wahlen für diese Orakel sind „BAZ-V<xx>-CS<yy>-<suiteID>-ENC1" bzw. „BAZ-V<xx>-CS<yy>-<suiteID>-ENC2", wobei <xx>, <yy> und <suiteID> wie oben beschrieben sind.

Die oben angegebenen Beispiel-Tags werden als ASCII-codierte Bytestrings ohne Nullterminierung angenommen, was das EMPFOHLENE Format darstellt. Andere Codierungen können verwendet werden, in jedem Fall MUSS die Codierung als Bytefolge jedoch eindeutig spezifiziert sein.

Letztes Update am