Für das symmetrische Ver­schlüsselungsverfahren AES wird der Erweiterungs­körper 𝔽_2⁸ gebraucht.

Erweiterungskörper 𝔽_2⁸

Eine andere Bezeichnung für 𝔽_2⁸ ist GF(2⁸). Der Buchstabe 𝔽 ist die Abkürzung für field, die englische Bezeichnung für Körper, GF bedeutet Galois field.

Ein Erweiterungs­körper kommt dadurch zustande, dass ein vorhandener Körper K zu einem größeren Körper erweitert wird.

Die Elemente des Erweiterungs­körpers lassen sich auf­fassen als Polynome mit Koeffizienten aus dem Körper K. Dabei entsprechen die Polynome vom Grad 0 den Elementen des ursprüng­lichen Körpers K; dieser bildet somit einen Teilkörper des Erweiterungs­körpers.

Die Darstellung als Polynom ist lediglich erforderlich, um in sinnvoller Weise die Addition und Multi­plikation von Elementen des Erweiterungs­körpers zu ermöglichen. Es geht also jetzt darum, Polynome so zu addieren und Polynome so miteinander zu multi­plizieren, dass wieder Elemente des Erweiterungs­körpers herauskommen.

Addition und Multiplikation im Erweiterungskörper 𝔽_2⁸

Addition

Die Addition zweier Polynome führen Sie durch, indem Sie die Koeffizienten gleicher Potenzen von x addieren. Die Addition der Koeffizienten erfolgt in ℤ₂, also modulo 2, das heißt 1 + 1 = 0.

Multi­plikation

Die Multi­plikation führen Sie durch, indem Sie die Polynome zunächst in gewohnter Weise miteinander multi­plizieren. Beachten Sie dabei aber, dass sich zwei gleiche Potenzen von x gegenseitig aufheben, wegen 1 + 1 = 0 in ℤ₂.

In diesem Beispiel haben Sie ein Polynom vom Grad  ≥ 8 erhalten. Das Ergebnis der Multi­plikation liegt außerhalb des Erweiterungs­körpers 𝔽_2⁸. Um dies zu vermeiden, reduzieren Sie das Produkt noch modulo eines festgelegten Polynoms z vom Grad 8, beispiels­weise

z  =  x⁸ + x⁴ + x³ + x + 1

Mittels einer Polynom­division ermitteln Sie also den Rest, der sich bei Division des Produktes durch das Polynom z ergibt. Dies geht bei Polynomen über dem Körper ℤ₂ am besten mit Bitvektoren – warten Sie noch zwei, drei Absätze ...

Körpereigenschaften

Es fehlt noch der Beweis, dass der gebildete Erweiterungs­körper mit den so definierten Ver­knüpfungen Addition und Multi­plikation tatsächlich die Körperaxiome erfüllt. Die meisten dieser Axiome folgen aus den Axiomen des zugrunde liegenden Körpers ℤ₂.

Dass es zu jedem Polynom p ∈ 𝔽_2⁸ ein multi­plikativ inverses Element gibt, können Sie sich überlegen, wenn Sie gelesen haben, wie Sie mit dem erweiterten euklidischen Algorithmus inverse Elemente in der Gruppe ℤ_n* berechnen. In der multi­plikativen Gruppe von 𝔽_2⁸ funktioniert dies ähnlich. Hier nur so viel:

Da z irreduzibel ist, gilt ggt(p, z) = 1. Den größten gemeinsamen Teiler, hier 1, können Sie darstellen als Linear­kombination

1  =  u·p + v·z

Modulo z gerechnet erhalten Sie

1  ≡  u·p   (mod z)

Damit ist u mod z das inverse Element zu p. Mithilfe des erweiterten euklidischen Algorithmus können Sie es auch ausrechnen.

Polynome aus 𝔽_2⁸ als Bitvektoren darstellen

Das Rechnen im Erweiterungs­körper 𝔽_2⁸ ist einfacher, wenn Sie die Elemente von 𝔽_2⁸, also Polynome über ℤ₂, als Bitvektoren darstellen.

Ein Polynom aus 𝔽_2⁸ können Sie einfach durch Angabe der Koeffizienten darstellen, also durch einen Bitvektor der Länge 8.

So stellen Sie etwa das Polynom

p  =  x⁴ + x³ + 1

durch den Bitvektor

P  =  0 0 0 1 1 0 0 1

dar.

Ob Sie die Elemente des Körpers 𝔽_2⁸ als Polynome oder als Bitvektoren ansehen, ist eben tatsächlich Ansichts­sache. Sie können die beiden Dar­stellungen miteinander austauschen. Mit Polynomen sind Sie eher gewohnt zu rechnen, mit Bitvektoren kann der Computer leichter rechnen.

Bitvektoren addieren

Die Addition von Elementen aus 𝔽_2⁸ in Darstellung als Bitvektoren ist besonders einfach: Sie addieren die Bitvektoren komponenten­weise modulo 2, beispiels­weise

Bitvektoren multi­plizieren

Die Multi­plikation von Elementen aus 𝔽_2⁸ in Darstellung als Bitvektoren ist etwas komplizierter – aber Sie können sie schrittweise leicht nachvollziehen.

Eine Multi­plikation eines Polynoms p mit dem Polynom q = x¹ hat ja zur Folge, dass alle Potenzen von p um 1 erhöht werden. In der Darstellung des Polynoms p als Bitvektor P hat dies zu Folge, dass P um eine Position nach links geschoben wird, wobei rechts eine 0 nachgezogen wird.

• Wird dabei links eine 1 heraus­geschoben, so muss das Ergebnis modulo des festgelegten Polynoms z =  x⁸ + x⁴ + x³ + x + 1 reduziert werden. Dies kommt einer Addition modulo 2 des Bitvektors Z' = 0 0 0 1 1 0 1 1 gleich.
• Wird links eine 0 heraus­geschoben, ist nichts weiter zu tun.

Die links heraus­geschobene Stelle fällt weg, sodass der Bitvektor die Länge 8 behält.

Um die Schiebe­operation darzustellen und um fest­zustellen, ob links eine 1 oder eine 0 heraus­geschoben wird, benutzen Sie am besten die folgenden kurzen Definitionen:

• Wenn P ein Bitvektor der Länge 8 ist, dann bedeutet P≪, dass der Bitvektor um eine Stelle nach links geschoben wird, wobei rechts eine Null nachgezogen wird. Die links heraus­geschobene Stelle fällt weg, sodass der Bitvektor die Länge 8 behält.
• Wenn P ein Bitvektor der Länge 8 ist, dann bedeutet P = 0X, dass das erste Bit des Bitvektors eine 0 ist. Entsprechend bedeutet P = 1X, dass das erste Bit eine 1 ist.

Mithilfe dieser Definitionen können Sie jetzt ausdrücken, was einem Bitvektor P aus 𝔽_2⁸ widerfährt, wenn er mit dem Polynom x multi­pliziert wird:

x • P  =

P≪     falls P = 0X P≪ +  Z'     falls P = 1X

Es ist Zeit für ein Beispiel. Der Bitvektor P = 1 0 0 0 1 1 1 0 wird mit dem Polynom x multi­pliziert. Er wird nach links geschoben, rechts wird eine 0 nachgezogen, links wird eine 1 heraus­geschoben:

Das heraus­geschobene Bit fällt weg; es ist aber eine 1, daher ist eine Reduktion modulo z erforderlich und darum wird noch Z' addiert:

Jetzt sind Sie in der Lage, einen Bitvektor P mit x zu multi­plizieren – und damit auch mit x². Denn Sie brauchen ihn lediglich ein weiteres Mal mit x zu multi­plizieren: x² • P = x • (x • P).

Können Sie auch mit x⁰ = 1 multi­plizieren? Na klar. Aber dann können Sie auch mit x +1 multi­plizieren, denn (x+1) • P = x • P + P.

Und Sie können mit x·(x +1) multi­plizieren, mit x² + 1 usw.

Bitvektoren als Bytes hexadezimal darstellen

Um die Notation noch weiter zu vereinfachen, stellen Sie Polynome aus 𝔽_2⁸ wie x, x², x+1 usw. als Bitvektoren dar und diese wiederum noch kürzer als Bytes in hexadezimaler Darstellung, also als zweistellige Hexa­dezimal­zahlen.

Aus dem Polynom x und damit dem Bitvektor 0 0 0 0 0 0 1 0 wird das Byte 02. Aus dem Polynom 1 wird 01, aus dem Polynom x+1 wird 03, aus x² wird 04.

Die folgenden Produkte kommen bei der Ver- und Ent­schlüsselung mit dem AES-Ver­schlüsselungsverfahren vor:

Wenn Sie Produkte in dieser Notation darstellen, geben Sie zugleich auch den Gang der Berechnung wieder: Bei jeder Multi­plikation mit 02 nehmen Sie ja, wenn nötig, eine Reduktion modulo z vor. Multi­plikationen und Reduktionen modulo z verlaufen also ineinander verschränkt.

Die so dar­gestellten Berechnungen werden im Computer sehr schnell durch Schiebe­operationen (bei der Multi­plikation mit 02) und bitweise Exklusiv-Oder-Operationen (bei Additionen) durchgeführt.

Sie haben jetzt drei Dar­stellungen der Elemente des Körpers 𝔽_2⁸ zur Verfügung:

• als Polynom, wie etwa x + 1,
• als Bitvektor, wie etwa 00000011,
• als Byte in Hexadezimal­darstellung, wie etwa 03.

Sie müssen sich nicht für eine Darstellung entscheiden, sondern Sie dürfen je nach Anwendungs­fall die Dar­stellungen auch vermischen, so etwa wie oben 02 • P oder x • P.

Aufgaben

Berechnen Sie 03 • C4 auf zwei Arten:

Überführen Sie zunächst die Bytes in die entsprechenden Polynome und multi­plizieren Sie diese modulo des festgelegten Polynoms z. Überführen Sie dann das Ergebnis wieder zurück in die Byte-Darstellung.

Multi­plizieren Sie 03 und C4 nach der Methode

03 • P   =   02 • P + P

wobei P = C4 ist.