4. Hilfsfunktionen

Die Algorithmen in diesem Dokument verwenden die unten beschriebenen Hilfsfunktionen sowie standardmäßige arithmetische Operationen (Addition, Multiplikation, modulare Reduktion usw.) und elliptische Kurvenpunktoperationen (Punktaddition und Skalarmultiplikation).

Aus Sicherheitsgründen SOLLTEN Implementierungen dieser Funktionen in konstanter Zeit erfolgen: Kurz gesagt bedeutet dies, dass Ausführungszeit und Speicherzugriffsmuster NICHT von den Werten geheimer Eingaben, Zwischenwerten oder Ausgaben abhängen SOLLTEN. Für solche Implementierungen in konstanter Zeit MÜSSEN auch alle arithmetischen Operationen, Vergleiche und Zuweisungen in konstanter Zeit implementiert werden. Abschnitt 10.3 behandelt kurz Sicherheitsfragen bezüglich konstanter Zeit.

Anleitungen zur Implementierung von Low-Level-Operationen (in konstanter Zeit oder anderweitig) liegen außerhalb des Umfangs dieses Dokuments; Leser sollten Standardreferenzmaterial [MOV96] [CFADLNV05] konsultieren.

• CMOV(a, b, c): Wenn c False ist, gibt CMOV a zurück; andernfalls gibt es b zurück. Für Implementierungen in konstanter Zeit muss diese Operation in einer Zeit ausgeführt werden, die unabhängig vom Wert von c ist.

• AND, OR, NOT und XOR sind standardmäßige bitweise logische Operatoren. Für Implementierungen in konstanter Zeit MÜSSEN Kurzschluss-Operatoren vermieden werden.

• is_square(x): Diese Funktion gibt True zurück, wenn der Wert x ein Quadrat im Feld F ist. Nach dem Euler-Kriterium kann diese Funktion in konstanter Zeit wie folgt berechnet werden:

  is_square(x) := { True, wenn x^((q - 1) / 2) gleich 0 oder 1 in F ist; { False, andernfalls.

  In bestimmten Erweiterungsfeldern kann is_square in konstanter Zeit schneller berechnet werden als durch die obige Exponentiation. [AR13] und [S85] beschreiben optimierte Methoden für Erweiterungsfelder. Anhang I.5 gibt eine optimierte Straight-Line-Methode für GF(p^2).

• sqrt(x): Die sqrt-Operation ist eine mehrwertige Funktion, d. h. es existieren zwei Wurzeln von x im Feld F, wenn x ein Quadrat ist (außer wenn x = 0). Um die Kompatibilität zwischen Implementierungen aufrechtzuerhalten und gleichzeitig Implementierern Spielraum für Optimierungen zu lassen, verlangt dieses Dokument nicht, dass sqrt() einen bestimmten Wert zurückgibt. Stattdessen spezifiziert jede Funktion, die sqrt aufruft, wie in Abschnitt 6.4 erläutert, auch, wie die korrekte Wurzel bestimmt wird.

  Die bevorzugte Methode zur Berechnung von Quadratwurzeln besteht darin, einen für F spezifischen deterministischen Algorithmus festzulegen. Wir geben mehrere Algorithmen in Anhang I an.

• sgn0(x): Diese Funktion gibt entweder 0 oder 1 zurück und zeigt das "Vorzeichen" von x an, wobei sgn0(x) == 1 genau dann gilt, wenn x "negativ" ist. (Mit anderen Worten, diese Funktion betrachtet 0 immer als positiv.) Abschnitt 4.1 definiert diese Funktion und diskutiert ihre Implementierung.

• inv0(x): Diese Funktion gibt das multiplikative Inverse von x in F zurück, erweitert auf ganz F durch Festlegen von inv0(0) == 0. Eine einfache Methode zur Implementierung von inv0 in konstanter Zeit besteht darin, zu berechnen:

  inv0(x) := x^(q - 2).

  Beachten Sie, dass bei Eingabe 0 die Ausgabe wie erforderlich 0 ist. Bestimmte Felder können schnellere Inversionsmethoden ermöglichen; eine detaillierte Diskussion solcher Methoden liegt außerhalb des Umfangs dieses Dokuments.

• I2OSP und OS2IP: Diese Funktionen werden verwendet, um einen Byte-String in eine nicht-negative ganze Zahl umzuwandeln und umgekehrt, wie in [RFC8017] beschrieben. (Beachten Sie, dass diese Funktionen auf Byte-Strings in Big-Endian-Byte-Reihenfolge arbeiten.)

• a || b: bezeichnet die Verkettung der Byte-Strings a und b. Zum Beispiel "ABC" || "DEF" == "ABCDEF".

• substr(str, sbegin, slen): Für einen Byte-String str gibt diese Funktion den slen-Byte-Teilstring zurück, der an Position sbegin beginnt; Positionen sind nullindiziert. Zum Beispiel substr("ABCDEFG", 2, 3) == "CDE".

• len(str): Für einen Byte-String str gibt diese Funktion die Länge von str in Bytes zurück. Zum Beispiel len("ABC") == 3.

• strxor(str1, str2): Für Byte-Strings str1 und str2 gibt strxor(str1, str2) das bitweise XOR der beiden Strings zurück. Zum Beispiel strxor("abc", "XYZ") == "9;9" (die Strings in diesem Beispiel sind ASCII-Literale, aber strxor ist für beliebige Byte-Strings definiert). In diesem Dokument wird strxor nur auf Eingaben gleicher Länge angewendet.

4.1. Die sgn0-Funktion

Dieser Abschnitt definiert eine generische sgn0-Implementierung, die auf jedes Feld F = GF(p^m) anwendbar ist. Er gibt auch vereinfachte Implementierungen für die Fälle F = GF(p) und F = GF(p^2) an.

Die Definition der sgn0-Funktion für Erweiterungsfelder basiert auf der Polynombasis oder Vektordarstellung von Feldelementen und iteriert über die gesamte Vektordarstellung des Eingabeelements. Daher hängt sgn0 vom primitiven Polynom ab, das zur Definition der Polynombasis verwendet wird; siehe Abschnitt 8 für weitere Informationen zu dieser Basis und Abschnitt 2.1 für eine Diskussion der Darstellung von Elementen von Erweiterungsfeldern als Vektoren.

sgn0(x)

Parameter:

• F, ein endliches Feld der Charakteristik p und Ordnung q = p^m.
• p, die Charakteristik von F (siehe unmittelbar oben).
• m, der Erweiterungsgrad von F, m >= 1 (siehe unmittelbar oben).

Eingabe: x, ein Element von F. Ausgabe: 0 oder 1.

Schritte:

1. sign = 0
2. zero = 1
3. für i in (1, 2, ..., m):
4. sign_i = x_i mod 2
5. zero_i = x_i == 0
6. sign = sign OR (zero AND sign_i) # Kurzschluss-Logikoperationen vermeiden
7. zero = zero AND zero_i
8. return sign

Wenn m == 1, kann sgn0 erheblich vereinfacht werden:

sgn0_m_eq_1(x)

Eingabe: x, ein Element von GF(p). Ausgabe: 0 oder 1.

Schritte:

1. return x mod 2

Der Fall m == 2 ist nur geringfügig komplizierter:

sgn0_m_eq_2(x)

Eingabe: x, ein Element von GF(p^2). Ausgabe: 0 oder 1.

Schritte:

1. sign_0 = x_0 mod 2
2. zero_0 = x_0 == 0
3. sign_1 = x_1 mod 2
4. s = sign_0 OR (zero_0 AND sign_1) # Kurzschluss-Logikoperationen vermeiden
5. return s