CLMUL

(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.<ref name="intel1"/> Sie ist in allen Intel-Prozessoren ab der Intel-Haswell-Mikroarchitektur und AMD-Prozessoren ab AMD Bulldozer verfügbar.

Übertragsfrei bedeutet hier <math>1+1=0.</math> 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 <math>a</math> und <math>b</math> Zahlen mit den Binärdarstellungen <math>(a_{n-1} \ldots a_1 a_0)_2</math> bzw. <math>(b_{n-1} \ldots b_1 b_0)_2</math>. Das übertragsfreie Produkt ist dann wie folgt definiert:

<math>\operatorname{clmul}(a,b) = \bigoplus_{k,l=0}^n 2^{k+l} a_k b_l</math>,

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

<math>ab = \sum_{k,l=0}^n 2^{k+l} a_k b_l</math>

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

<math>c_l = \bigoplus_{k=0}^l a_k b_{l-k}</math>.

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

• Kommutativgesetz: <math>\operatorname{clmul}(a,b) = \operatorname{clmul}(b,a)</math>
• Assoziativgesetz: <math>\operatorname{clmul}(a,\operatorname{clmul}(b,c)) = \operatorname{clmul}(\operatorname{clmul}(a,b),c)</math>
• Distributivgesetz: <math>\operatorname{clmul}(a,b\oplus c)) = \operatorname{clmul}(a,b) \oplus \operatorname{clmul}(a,c)</math>

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.<ref> 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</ref>

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

<references> <ref name="intel1">Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode. Abgerufen am 15. Dezember 2016. </ref> </references>

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