CLMUL

Vorlage:Lang (CLMUL) (dt.: übertragsfreie Multiplikation) ist eine Befehlserweiterung der x86-Prozessorarchitektur, die eine schnelle, hardwareunterstützte Berechnung in Bereichen aus der Zahlentheorie ermöglicht. Die Befehlserweiterung wurde im Jahr 2008 von Intel vorgeschlagen und ab 2010 bei der Westmere-Mikroarchitektur eingeführt. Sie ist in allen Intel-Prozessoren ab der Intel-Haswell-Mikroarchitektur und AMD-Prozessoren ab AMD Bulldozer verfügbar.

Übertragsfrei bedeutet hier $1+1=0.$ Die Zwischensummen bei der Multiplikation werden bitweise durch XOR-Verknüpfung gebildet.

Anwendungsbeispiele sind die Kryptografie bei Blockverschlüsselungen im Betriebsmodus Galois/Counter Mode (GCM), welcher auf Berechnungen in einem Galoiskörper basiert. Ein anderes Anwendungsfeld sind die Erzeugung von Prüfsummen im Bereich der zyklischen Redundanzprüfungen (CRC).

Übertragsfreies Produkt

Seien $a$ und $b$ Zahlen mit den Binärdarstellungen $(a_{n-1}\dots a_1{a}_0{)}_2$ bzw. $(b_{n-1}\dots b_1{b}_0{)}_2$. Das übertragsfreie Produkt ist dann wie folgt definiert:

$\mathrm{clmul}(a,b)=\underset{k,l=0}{\overset{n}{⨁}}{2}^{k+l}{a}_k{b}_l$,

wobei $\oplus$ die bitweise XOR-Verknüpfung darstellt. Der Zusatz „übertragsfrei“ wird klar, wenn man obigen Ausdruck mit der regulären Multiplikation vergleicht:

$ab=\sum _{k,l=0}^n{2}^{k+l}{a}_k{b}_l$

wo wegen der Summe immer dann ein Übertrag in das Bit $k+l+1$ notwendig ist, wenn $a_k=b_l=1$. Da aber $1\oplus 1=0$, fällt der Übertrag in clmul weg. Wegen der einfacheren Berechnung ergibt sich folgende einfache Binärdarstellung $(c_{n-1}\dots c_1{c}_0{)}_2$ für das übertragsfreie Produkt:

$c_l=\underset{k=0}{\overset{l}{⨁}}{a}_k{b}_{l-k}$.

Das übertragsfreie Produkt hat ähnliche Eigenschaften wie das reguläre Produkt:

• Kommutativgesetz: $\mathrm{clmul}(a,b)=\mathrm{clmul}(b,a)$
• Assoziativgesetz: $\mathrm{clmul}(a,\mathrm{clmul}(b,c))=\mathrm{clmul}(\mathrm{clmul}(a,b),c)$
• Distributivgesetz: $\mathrm{clmul}(a,b\oplus c))=\mathrm{clmul}(a,b)\oplus \mathrm{clmul}(a,c)$

Befehlssatzerweiterung

Die Befehle aus der Erweiterung berechnen aus den Eingabewerten von zwei 64 Bit das übertragsfreie Produkt von 128 Bit und legen das Ergebnis in einem 128 Bit breiten XMM-Register ab. Als Quelle für die beiden Faktoren kann je nach Adressierungsmodus entweder ein anderes XMM-Register, dann werden die beiden 64 Bit breiten Hälften eines XMM-Registers als zwei Faktoren betrachtet, oder die Hälften von zwei verschiedenen XMM-Registern oder eine Speicheradresse im Hauptspeicher angegeben werden.

Die Multiplikation von zwei 128 bit breiten Eingabewerten kann mit Hilfe des Karazuba-Algorithmus in vier Rechenschritten erfolgen.

Literatur

• Christoph Puttmann: Ressourceneffiziente Hardware-Software-Kombinationen für Kryptographie mit elliptischen Kurven, Dissertation an der Technischen Fakultät der Universität Bielefeld, Bielefeld 2014 PDF