Seite 2: Multiplikation

Inhaltsverzeichnis

Multiplikation in GF(2^8)

Leider gestalten sich Multiplikation und Division in GF(2^8) etwas komplizierter als Addition und Subtraktion. Die Multiplikation ist definiert als eine Polynommultiplikation Modulo (mod) eines irreduziblen Polynoms vom Grad 8. Die Polynommultiplikation ist einleuchtend, schließlich sind die Elemente von GF(2^8) Polynome. Die "Restoperation" mod führt salopp ausgedrückt dazu, dass man innerhalb der Byte-Darstellung des endlichen Körpers bleibt (mathematische Stichworte: Restklassenring und Vertretersystem). Eine ausführliche Darstellung von Restklassenringen und Vertretersystemen lässt sich [1] entnehmen.

Ein irreduzibles Polynom kann nur durch 1 und sich selbst dividiert werden. Es ist also innerhalb des endlichen Körpers prim. Da das irreduzible Polynom vom Grad 8 ist, lässt es sich nicht mehr durch 8 Bits darstellen, sondern benötigt ein 9. Bit. In AES ist dieses Polynom dargestellt als Bitfeld 100011011 oder als hexadezimale Zahl 0x011B.

Das Multiplizieren zweier Polynome, wie die Leser es in der Schule gelernt haben, dauert ziemlich lange. Zumal das Produkt anschließend noch durch das irreduzible Polynom zu dividieren ist, um den Rest und damit das endgültige Ergebnis zu erhalten. Rein rechnerisch wäre eine Lösung nach der Schulmethode korrekt, aber eben bei weitem nicht effizient.

An der Stelle heißt es für den Cryptography Engineer, die Literatur zu bemühen, also Antworten oder zumindest Ansätze auf die Frage zu finden: Wie lässt sich effizient die Multiplikation mod eines irreduziblen Polynoms in GF(2^8) implementieren? Ähnlich wie sich ein Maschinenbauer auf Tabellenbücher und Literatur zur Physik und Analysis verlässt, heißt es für den Informatiker Literatur zur Algebra, Teilbarkeit und algorithmischen Mathematik zu durchstöbern. Findet sich keine brauchbare "fertige" Lösung, heißt es, selbst eine Antwort aus dem vorhandenen Wissen zu kombinieren und zu konstruieren.

Zum Glück bietet die mathematische Trickkiste an der Stelle eine komfortable, einsatzfähige Antwort für das Multiplikationsproblem, die sich kurz und prägnant bereits in der Spezifikation von AES in Abschnitt 4.2 findet. Zum Verständnis der Lösung sind zusätzlich die in den Literaturangaben gelisteten Bücher hilfreich. Insbesondere das Werk von Hankerson, Menezes und Vanstone [3] zeigt, dass ein Blick über den Tellerrand durchaus lohnt. Obwohl AES nicht auf der Kryptografie über elliptischen Kursen beruht, bietet deren Buch eine Reihe fertiger Algorithmen zum Rechnen in GF(2^8) und über Polynomen.

Funktion xtime()

Für die Implementierung der Polynommultiplikation schlägt die AES-Spezifikation die Funktion xtime(p(x)) vor. Die Funktion multipliziert das Polynom p(x) mit x und reduziert es mod 0x011B. Sie führt also noch keine Multiplikation zweier beliebiger Polynome p(x) und q(x) mod 0x011B aus. Das folgt ein wenig später.

xtime(p(x)) implementiert die Multiplikation von p(x) * x mit einem Left-Shift. Dieses Linksschieben entspricht der Multiplikation mit 2, also dem Wert der Byte-Repräsentation des Polynoms x. Danach hat das Ergebnis entweder einen kleineren Grad als das irreduzible Polynom 0x011B oder ebenfalls den Grad 8 wie 0x011B. Im ersten Fall ist nichts weiter zu machen, da bereits das Ergebnis vorliegt. Im zweiten Fall – p(x) * x hat den Grad 8 – ist das Ergebnis noch mod 0x011B zu rechnen. Die aufwendige Division mit dem Rest lässt sich an der Stelle sparen. Das Ergebnis von p(x) * x liegt in der Form 0x011B + r vor, wobei r der Rest der Division p(x) mod 0x011B ist. Es genügt also, das Ergebnis von p(x) * x - 0x011B zu rechnen. Mit anderen Worten: Das Resultat der Multiplikation mit x ist schlicht XOR 0x011B zu rechnen. (Erinnert sei daran, dass Addition und Subtraktion in GF(2^8) identisch sind.)

Nachdem der Leser nun mit xtime() in der Lage ist, ein Polynom mit x zu multiplizieren, kann er aufbauend auf dieser Operation die Multiplikation zweier beliebiger Polynome darstellen. Durch rekursives Anwenden von xtime() lassen sich Multiplikationen des Polynoms p(x) mit x, x^2, x^3 und so weiter errechnen:

p(x) * x   = xtime(p(x))
p(x) * x^2 = xtime(p(x) * x)   = xtime(xtime(p(x))
p(x) * x^3 = xtime(p(x) * x^2) = xtime(xtime(p(x) * x)) = xtime(xtime(xtime(p(x)))

und so fort. Das funktioniert, da beim Rechnen mit Modulo Folgendes gilt:

(a*b*c) mod z = ((a * b) mod z) * c) mod z

Der noch zusätzlich nötige Fall p(x) * x^0 = p(x) * 1 = p(x) ist trivial und benötigt xtime() nicht. Damit kann der Leser nun p(x) mit jeder beliebigen Potenz von x multiplizieren.

Um nun p(x) mit einem anderen Polynom q(x) zu multiplizieren, sei betrachtet, wie man die beiden nach der Schulmethode multiplizieren würde. Es geht um Multiplikation der einzelnen Terme von q(x) mit p(x) und die Addition der so entstehenden Produkte. Die Terme von q(x) sind a_0 * x^0, a_1 * x^1, a_2 * x^2 und so fort. Die a_i haben die Werte 0 oder 1 und geben lediglich an, ob ein x^i in q(x) "vorhanden" ist. Damit setzt sich q(x) aus einer Summe von x^i-Termen zusammen. Die Multiplikation von q(x) mit solchen x^i lassen sich dank der rekursiven Anwendung von xtime() berechnen. Die Ergebnisse zu summieren ist nur noch trivial.

Man benötigt also eine Schleife, die nichts anderes macht, als sukzessive mit mehrfach angewendetem xtime() die Ergebnisse für p(x) * x^i zu berechnen. Je nachdem, ob das entsprechende a_i in q(x) gesetzt ist, ist das jeweilige p(x) * x^i dem Ergebnis hinzuzuaddieren oder eben nicht. Die a_i sind dabei durch die Bits in der Byte-Darstellung von q(x) repräsentiert. Damit ergibt sich der Algorithmus aus Abbildung 1.

Die Variablen p und q enthalten zu Anfang die zu multiplizierenden Polynome in ihren Byte-Darstellungen. Die Variable r dient zur Aufnahme der aufsummierten Produkte aus den Termen von q(x) mitp(x). Die Laufvariable i zählt die Bits von q von 0 bis 7 durch. Ist jeweils das niederwertigste Bit in q gesetzt, wird r der aktuelle Wert von p hinzu addiert. p nimmt nacheinander die Ergebnisse der verschachtelten xtime()-Ergebnisse auf. Diese werden im grau hinterlegten Teil nach der oben beschriebenen Regel berechnet und in p abgelegt. Zum Ende wird jeweils q um ein Bit nach rechts geschoben. Somit ist das betrachtete Bit immer an Position 0.

Optimierte Multiplikation

Mit dieser Grundvariante des Algorithmus lässt sich die Multiplikation schon effizient mit linearer Laufzeit realisieren. Soweit kann man das Ganze aus der Fachliteratur ohne großen Aufwand ableiten. Allerdings benötigt diese Grundvariante noch eine Variable t mit mindestens 9 Bits, also auf herkömmlichen CPUs mindestens einen 16-Bit-Integer. Wo sich die Elemente in GF(2^8) sonst gut in einen Byte unterbringen lassen, ist das ein Makel, der sich jedoch leicht ausräumen lässt.

Das Resultat der Schiebeoperation in xtime() ist nur dann vom Grad 8, wenn das höchstwertige Bit der Byte-Darstellung von p(x) gesetzt ist. In dem Fall wandert das Bit an Position 7 durch den Left-Shift auf Position 8. Mit anderen Worten: Es lässt sich vor der Schiebeoperation vorhersagen, ob das Ergebnispolynom den Grad 8 haben wird oder nicht. Das Ergebnis hat nämlich genau dann Grad 8, wenn das höchstwertige Bit vor der Schiebeoperation gesetzt ist. Damit ergibt sich der Algorithmus wie auf der rechten Seite von Abbildung 1 dargestellt. Der geänderte Teil ist grau unterlegt.

Ist das höchstwertige Bit des Bytes in p nicht gesetzt, genügt ein Left-Shift. Ist es hingegen gesetzt, erfolgt nach dem Left-Shift noch ein XOR 0x1B. Das Bit an der Position 8 und den XOR mit dem höherwertigen Byte 0x01 des irreduziblen Polynoms kann man sich sparen. Das 8. Bit von p steckt nicht in dem Byte, sondern im Carry-Flag des Prozessors. Damit passt das Ganze wieder in ein Byte.

Nun bleibt einzig noch die Division als Umkehrung der Multiplikation offen. Die Division ist analog zur Multiplikation eine Division von Polynomen. Sie lässt sich dabei wie die Multiplikation implementieren, denn die Division ist nichts anderes als die Multiplikation mit dem Inversen. Anschaulich gesprochen: Man würde mit dem "Kehrwert" multiplizieren. Wie sich dieser "Kehrwert", das Inverse, ermitteln lässt, darauf geht ein späterer Artikel bei der Implementierung auf 8-Bit-Mikrocontrollern ein.