7. Beseitigung des Kofaktors

Die Abbildungen aus Abschnitt 6 erzeugen stets einen Punkt der elliptischen Kurve, d. h. einen Punkt einer Gruppe der Ordnung h * r (Abschnitt 2.1). Um einen Punkt in G zu erhalten, kann eine abschließende Operation erforderlich sein, die üblicherweise als „Beseitigung des Kofaktors" (clearing the cofactor) bezeichnet wird und einen beliebigen Punkt der Kurve als Eingabe entgegennimmt und einen Punkt der Untergruppe G von Primzahlordnung (Abschnitt 2.1) als Ausgabe liefert.

Der Kofaktor kann stets durch Skalarmultiplikation mit h beseitigt werden. Für elliptische Kurven mit h = 1, d. h. Kurven mit einer Primzahl von Punkten, ist keine Operation erforderlich. Dies gilt beispielsweise für die NIST-Kurven P-256, P-384 und P-521 [FIPS186-4].

In manchen Fällen lässt sich der Kofaktor durch eine Methode beseitigen, die schneller ist als die Skalarmultiplikation mit h. Solche Methoden sind äquivalent zur (in der Regel jedoch schneller als die) Multiplikation mit einem bestimmten Skalar h_eff, dessen Wert durch die Methode und die Kurve bestimmt wird. Zu den Beispielen für schnelle Methoden der Kofaktor-Beseitigung zählen die folgenden:

• Für bestimmte pairing-freundliche Kurven mit einer Untergruppe G2 über einem Erweiterungskörper beschreiben Scott et al. [SBCDK09] eine schnelle Methode zur Kofaktor-Beseitigung, die einen effizient berechenbaren Endomorphismus ausnutzt. Fuentes-Castañeda et al. [FKR11] schlagen eine alternative Methode vor, die mitunter effizienter ist. Budroni und Pintore [BP17] geben konkrete Instanziierungen dieser Methoden für die pairing-freundlichen Barreto-Lynn-Scott-Kurven [BLS03] an. Diese Methode wird für den Spezialfall BLS12-381 in Anhang G.3 beschrieben.

• Wahby und Boneh ([WB19], Abschnitt 5) beschreiben einen auf Scott zurückgehenden Kniff, der eine schnelle Kofaktor-Beseitigung auf jeder elliptischen Kurve ermöglicht, für die die Primfaktorzerlegung von h und die Gruppenstruktur der elliptischen Kurve bestimmte Bedingungen erfüllen.

Die Funktion clear_cofactor ist durch einen Skalar h_eff parametrisiert. Konkret gilt:

clear_cofactor(P) := h_eff * P

wobei * die Skalarmultiplikation bezeichnet. Unterstützt eine Kurve keine schnelle Methode zur Kofaktor-Beseitigung, so gilt h_eff = h und der Kofaktor MUSS durch Skalarmultiplikation beseitigt werden.

Unterstützt eine Kurve eine schnelle Methode zur Kofaktor-Beseitigung, so KANN clear_cofactor entweder mit dieser Methode oder durch Skalarmultiplikation mit dem äquivalenten h_eff ausgewertet werden; beide Methoden liefern dasselbe Ergebnis. Man beachte, dass in diesem Fall die Skalarmultiplikation mit dem Kofaktor h im Allgemeinen nicht dasselbe Ergebnis liefert wie die schnelle Methode und NICHT verwendet werden DARF.