7. Cofaktor-Eliminierung

Die Abbildungen in Abschnitt 6 erzeugen immer einen Punkt auf der elliptischen Kurve, d. h. einen Punkt in einer Gruppe der Ordnung h * r (Abschnitt 2.1). Um einen Punkt in G zu erhalten, kann eine abschließende Operation erforderlich sein, die allgemein als „Cofaktor-Eliminierung“ bezeichnet wird. Diese nimmt einen beliebigen Punkt auf der Kurve als Eingabe und liefert einen Punkt in der (Unter-)Gruppe primzahliger Ordnung G (Abschnitt 2.1) als Ausgabe.

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

In einigen Fällen ist es möglich, den Cofaktor durch eine schnellere Methode als die Skalarmultiplikation mit h zu eliminieren. Diese Methoden sind äquivalent zu (aber im Allgemeinen schneller als) der Multiplikation mit einem bestimmten Skalar h_eff, dessen Wert durch die Methode und die Kurve bestimmt wird. Beispiele für schnelle Methoden zur Cofaktor-Eliminierung sind:

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

• Wahby und Boneh ([WB19], Abschnitt 5) beschreiben einen Trick von Scott zur schnellen Cofaktor-Eliminierung auf jeder elliptischen Kurve, bei der 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. Genauer gesagt:

clear_cofactor(P) := h_eff * P

wobei * die Skalarmultiplikation darstellt. Wenn eine Kurve keine schnelle Methode zur Cofaktor-Eliminierung unterstützt, gilt h_eff = h, und der Cofaktor MUSS durch Skalarmultiplikation eliminiert werden.

Wenn eine Kurve eine schnelle Methode zur Cofaktor-Eliminierung zulässt, KANN clear_cofactor entweder über diese Methode oder über eine Skalarmultiplikation mit dem äquivalenten h_eff ausgewertet werden; beide Methoden liefern das gleiche Ergebnis. Beachten Sie, dass in diesem Fall die Skalarmultiplikation mit dem Cofaktor h im Allgemeinen nicht das gleiche Ergebnis wie die schnelle Methode liefert und NICHT verwendet werden darf.