CLMUL

Carry-less Multiplication (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.^[1] Sie ist in allen Intel-Prozessoren ab der Intel-Haswell-Mikroarchitektur und AMD-Prozessoren ab AMD Bulldozer verfügbar.

Übertragsfrei bedeutet hier ${\displaystyle 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).

Seien ${\displaystyle a}$ und ${\displaystyle b}$ Zahlen mit den Binärdarstellungen ${\displaystyle (a_{n-1}\ldots a_{1}a_{0})_{2}}$ bzw. ${\displaystyle (b_{n-1}\ldots b_{1}b_{0})_{2}}$. Das übertragsfreie Produkt ist dann wie folgt definiert:

${\displaystyle \operatorname {clmul} (a,b)=\bigoplus _{k,l=0}^{n}2^{k+l}a_{k}b_{l}}$,

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

${\displaystyle ab=\sum _{k,l=0}^{n}2^{k+l}a_{k}b_{l}}$

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

${\displaystyle c_{l}=\bigoplus _{k=0}^{l}a_{k}b_{l-k}}$.

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

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

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.^[2]

• 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

1. ↑ Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode. Abgerufen am 15. Dezember 2016. 
2. ↑ Tetsu Iwata, Jung Hee Cheon: Advances in Cryptology - AsiaCrypt 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand. Part 1, Verlag Springer, Heidelberg 2015 ISBN 9783662487969 PDF