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. 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}\ldots a_{1}a_{0})_{2}$ bzw. $(b_{n-1}\ldots b_{1}b_{0})_{2}$. Das übertragsfreie Produkt ist dann wie folgt definiert:

$\operatorname {clmul} (a,b)=\bigoplus _{k,l=0}^{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}\ldots c_{1}c_{0})_{2}$ für das übertragsfreie Produkt:

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

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

• Kommutativgesetz: $\operatorname {clmul} (a,b)=\operatorname {clmul} (b,a)$
• Assoziativgesetz: $\operatorname {clmul} (a,\operatorname {clmul} (b,c))=\operatorname {clmul} (\operatorname {clmul} (a,b),c)$
• Distributivgesetz: $\operatorname {clmul} (a,b\oplus c))=\operatorname {clmul} (a,b)\oplus \operatorname {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

Einzelnachweise

V

Befehlssatzerweiterungen der x86-Architektur (16 Bit; 32 Bit: IA-32; 64 Bit: x64)

Betriebsmodi	Real Mode • Protected Mode • Virtual 8086 Mode • System Management Mode • Long Mode • Compatibibility Mode
Befehlssatzerweiterungen	x87 ⬝ PAE ⬝ NX ⬝ AMD64/Intel 64 (x64) ⬝ HTT ⬝ VT-x/AMD-V/VIA VT ⬝ 3DNow! ⬝ MMX ⬝ SSE ⬝ SSE2 ⬝ SSE3 ⬝ SSSE3 ⬝ SSE4 ⬝ SSE4a ⬝ SSE5 ⬝ F16C ⬝ AVX ⬝ CLMUL ⬝ AES ⬝ FMA ⬝ TSX ⬝ BMI ⬝ MPX ⬝ SGX