4. Hilfsfunktionen

Die Algorithmen dieses Dokuments verwenden die nachstehend beschriebenen Hilfsfunktionen sowie die üblichen arithmetischen Operationen (Addition, Multiplikation, modulare Reduktion usw.) und Operationen auf Punkten elliptischer Kurven (Punktaddition und Skalarmultiplikation).

Aus Sicherheitsgründen SOLLTEN Implementierungen dieser Funktionen in konstanter Zeit ablaufen: Kurz gesagt bedeutet dies, dass Laufzeit und Speicherzugriffsmuster NICHT von den Werten geheimer Eingaben, Zwischenwerte 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 sein. Abschnitt 10.3 behandelt kurz die Sicherheitsfragen im Zusammenhang mit konstanter Laufzeit.

Empfehlungen zur Implementierung von Low-Level-Operationen (in konstanter Zeit oder nicht) liegen außerhalb des Rahmens dieses Dokuments; der Leser sei auf die einschlägigen Standardwerke verwiesen [MOV96] [CFADLNV05].

• CMOV(a, b, c): Ist c gleich False, so gibt CMOV den Wert a zurück, andernfalls b. Für Implementierungen in konstanter Zeit muss diese Operation in einer Zeit ablaufen, die unabhängig vom Wert von c ist.

• AND, OR, NOT und XOR sind die üblichen bitweisen logischen Operatoren. Für Implementierungen in konstanter Zeit MÜSSEN Operatoren mit verzögerter Auswertung (Kurzschlussauswertung) vermieden werden.

• is_square(x): Diese Funktion gibt genau dann True zurück, wenn der Wert x ein Quadrat im Körper F ist. Nach dem Euler-Kriterium lässt sich diese Funktion in konstanter Zeit wie folgt berechnen:

is_square(x) := { True,  if x^((q - 1) / 2) is 0 or 1 in F;
                { False, otherwise.

In manchen Erweiterungskörpern lässt sich is_square in konstanter Zeit schneller berechnen als durch die obige Exponentiation. [AR13] und [S85] beschreiben optimierte Methoden für Erweiterungskörper. Anhang I.5 gibt eine optimierte Straight-Line-Methode für GF(p^2) an.

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

Der bevorzugte Weg zur Berechnung von Quadratwurzeln besteht darin, einen deterministischen, für F spezifischen Algorithmus festzulegen. Mehrere Algorithmen sind in Anhang I angegeben.

• sgn0(x): Diese Funktion gibt 0 oder 1 zurück und zeigt damit das „Vorzeichen" von x an; sgn0(x) == 1 gilt genau dann, wenn x „negativ" ist. (Mit anderen Worten betrachtet diese Funktion 0 stets als positiv.) Abschnitt 4.1 definiert diese Funktion und erörtert ihre Implementierung.

• inv0(x): Diese Funktion gibt das multiplikative Inverse von x in F zurück, erweitert auf ganz F durch die Festlegung inv0(0) == 0. Eine einfache Möglichkeit, inv0 in konstanter Zeit zu implementieren, ist die Berechnung von

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

Man beachte, dass die Ausgabe für die Eingabe 0 gleich 0 ist, wie gefordert. Manche Körper erlauben schnellere Inversionsmethoden; eine ausführliche Erörterung dieser Methoden liegt außerhalb des Rahmens dieses Dokuments.

• I2OSP und OS2IP: Diese Funktionen dienen der Umwandlung eines Bytestrings in eine nichtnegative ganze Zahl und umgekehrt, wie in [RFC8017] beschrieben. (Man beachte, dass diese Funktionen auf Bytestrings in Big-Endian-Reihenfolge arbeiten.)

• a || b: bezeichnet die Verkettung der Bytestrings a und b. Beispielsweise gilt "ABC" || "DEF" == "ABCDEF".

• substr(str, sbegin, slen): Für einen Bytestring str gibt diese Funktion den Teilstring aus slen Bytes zurück, der an Position sbegin beginnt; die Positionen sind ab null indiziert. Beispielsweise gilt substr("ABCDEFG", 2, 3) == "CDE".

• len(str): Für einen Bytestring str gibt diese Funktion die Länge von str in Bytes zurück. Beispielsweise gilt len("ABC") == 3.

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

4.1. Die Funktion sgn0

Dieser Abschnitt definiert eine generische Implementierung von sgn0, die auf jeden Körper F = GF(p^m) anwendbar ist. Zudem werden vereinfachte Implementierungen für die Fälle F = GF(p) und F = GF(p^2) angegeben.

Die Definition der Funktion sgn0 für Erweiterungskörper beruht auf der Polynombasis bzw. der Vektordarstellung der Körperelemente und iteriert über die gesamte Vektordarstellung des Eingabeelements. Folglich hängt sgn0 von dem 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 Erörterung der Darstellung von Elementen von Erweiterungskörpern als Vektoren.

sgn0(x)

Parameters:
- F, a finite field of characteristic p and order q = p^m.
- p, the characteristic of F (see immediately above).
- m, the extension degree of F, m >= 1 (see immediately above).

Input: x, an element of F.
Output: 0 or 1.

Steps:
1. sign = 0
2. zero = 1
3. for 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) # Avoid short-circuit logic ops
7.   zero = zero AND zero_i
8. return sign

Für m == 1 lässt sich sgn0 erheblich vereinfachen:

sgn0_m_eq_1(x)

Input: x, an element of GF(p).
Output: 0 or 1.

Steps:
1. return x mod 2

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

sgn0_m_eq_2(x)

Input: x, an element of GF(p^2).
Output: 0 or 1.

Steps:
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) # Avoid short-circuit logic ops
5. return s