Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Matrizenmultiplikation im Galois Körper

Matrizenmultiplikation im Galois Körper

Universität / Fachhochschule

Körper

Polynome

Kryptologie

Tags: AES, Körper, Kryptologie, polynom, Rijndael

cable aktiv_icon

08:38 Uhr, 26.04.2012

Hallo,

ich beschäftige mich gerade mit dem AES oder eher Rijndael. In dem Algorithmus finden in einer Funktion namens mixColumns() Matrizenmultiplikationen statt. Also immer ein 4 er Spaltenvektor multipliziert mit einer

4 x 4

Matrix. Die Multiplikation findet jedoch auf dem Galois-Körper GF

(2^{8})

statt. Nun ist meine Frage wie diese Multiplikation im Galois Körper definiert ist. Ich versteh die Beispiele im Internet nicht.

folgendes Beispiel

(\begin{matrix} b 8 \\ 41 \\ 11 \\ f 1 \end{matrix}) \cdot (\begin{matrix} 2 & 1 & 1 & 3 \\ 3 & 2 & 1 & 1 \\ 1 & 3 & 2 & 1 \\ 1 & 1 & 3 & 2 \end{matrix}) = (\begin{matrix} 48 \\ f 8 \\ d 3 \\ 7 a \end{matrix})

kann mir hier jemand erklären wie man auf das Ergebnis kommt? Ich weiß, dass die Werte in den Vektoren bzw. in der Matrix Hex-Werte sind und jeder Wert ein Byte darstellt. Man kann also mit einem Byte ein Polynom 7ter Ordnung aus dem GF

(2^{8})

darstellen.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Polynomfunktionen / ganzrationale Funktionen - Einführung
Raummessung

hagman aktiv_icon

17:03 Uhr, 26.04.2012

G F (2^{8})

ein 8-dimensionaler

G F (2)

-Vektorraum ist, kann man bezüglich einer geeigneten Basis 8 bit als Darstellung wählen.
Die Addition im Körper ist dann auch die Addition im Vektorraum, also XOR
Die Multiplikation hängt von der Basis ab.
Konstruiert man den Körper als Quotientenkörper des Polynomringes

G F (8) = G F (2) [X] / (f)

mit einem irreduziblen Polynom

f (X) = X^{8} + c_{7} X^{7} + . .

+ c_{1} X + c_{0},

bietet es sich an, die offensichlich linear unabhängigen Elemente

1, X, X^{2}, + ..., X^{7}

(genauer: deren Restklassen) als Basis zu wählen.
Das Produkt von 2 Bytes

a = (a_{0}, ..., a_{7})

entsprechend

a_{0} + a_{1} X + . .

+ a_{7} X^{7}

und

b = (b_{0}, ..., b_{7})

entsprechend

b_{0} + b_{1} X + . .

+ b_{7} X^{7}

liefert zunächst einmal ein Polynom

u_{0} + u_{1} X + .

+ u_{14} X^{14},

also einen 15-Bit-Wert (indem einige um 0 bis 7 Stellen geshiftete Kopien von

a

per XOR addiert werden)
Die höherwertigen Bits sind modulo

f (X)

zu gewissen vorberechenbaren Polynomen vom Grad

< 8

kongruent, die (wenn das jeweilige hohe Bit gesetzt ist) zum "lower Byte" geXORt werden.

cable aktiv_icon

21:27 Uhr, 26.04.2012

Vielen Dank für Deine ausführliche Erklärung. Ich hab jetzt nur noch ne Verständnisfrage zweck der Modulo Operation. Wenn ich jetzt durch die Multiplikation mein Polynom bekomme.

zum Beispiel

x^{8} + x^{7} + x^{5} + x^{3}

dann muss ich das

mod

dem irreduziblen Polynom rechnen.
Das ist

x^{8} + x^{4} + x^{3} + x + 1

. Also

(x^{8} + x^{7} + x^{5} + x^{3}) mod (x^{8} + x^{4} + x^{3} + x + 1)

nun habe ich auf Wikipedia gesehen, dass wenn die Polynome in binärer Schreibweise angegeben sind, die Modulo Operation ersetzt wird mit der Addition.

also

110101000 + 100011011

Diesen Schritt versteh ich nicht. Ich weiß, dass die Addition, im

G F (2^{8}),

als XOR ausgeführt wird, so wie Du es ja am Ende auch beschreibst. Das ist alles einleuchtend, jedoch nicht das Ersetzen von

mod

mit einer Addition.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

996525

996317

	Status: nicht eingeloggt	Noch nicht registriert?