Probleme mit Galois Feld GF(2^8)

Jester

1+1 = 0 in GF(2^8) und GF(2^8) ist das gleiche wie GF(256), aber es ist was völlig anderes als Z/256Z. Z/nZ ist nur für n prim ein Körper. Endliche Körper mit nicht primer Anzahl von Elementen werden anders konstruiert, nämlich so wie es megaweber schon beschrieben hat. Dadurch ändert sich die Charakteristik des Körpers nicht und 1+1=0 in diesem Körper. Schau Dir die Konstruktion in Ruhe an, so schwer isses nicht.

Ishildur

Ich habe da einen Ausschnitt aus einem PDF:

Die Addition und Multiplikation bei einfachen Galois-Feldern kann problemlos so durchgeführt werden, als ob man sich im natürlichen Zahlenraum befindet. Allei das Endergebnis muss modulo-5 berechnet werden. Beispiele aus der Aufgabe:

1+1=2;
2+3 = 5 = 0 mod 5;
4+4 = 8 = 3 mod 5;
13 = 3;
24 = 8 = 3 mod 5;

Dabei handelte es sich um ein GF(5)
Also hatte ich gedacht, es währe doch naheliegend, wenn es sich bei einem GF(256) auch so verhält mit dem Unterschied, dass ich anstatt mod5 einfach mod256 benutze.
In einem anderen Dokument, welches genau den gleichen Stoff behandelt, lese ich schliesslich folgendes:

In the polynomial representation, multiplication in GF(2^8) corresponds with multiplication of polynomials modulo an irreducible binary polynomial of degree 8. A polynomial is called m(x) and given by m(x) = x^8+x4+x^3+x+1

Also, was solls denn nun bitte sein?

P.S.
Ich bin sicher kein Mathegenie, aber wie gesagt, ich habe nun etwa 25 Dokumente über dieses Thema gesammtelt und überall steht etwas anderes drinnen...

Ich möchte auf keinen Fall den Eindruck hinterlassen, es besser zu wissen, sondern möchte zeigen, wesshalb ich soviel Mühe mit dem Verständnis dieser Materie habe. Ich glaube, mir fehlen ein paar Grundlagen, um diese Galoisfelder zu verstehen. Kann mir denn jemand sagen, wo ich im Internet an gute und wahre Literatur komme?

@kurze Antwort
Ich frage mich, ob du auch so daherkeiffen würdest, wenn wir uns gegenüberstehen würden...
Soll keine Drohung sein, finde es nur ein wenig daneben, wie du mich runterputzt! Könnte gut sein, dass es gewisse Dinge gibt, bei denen DU ein wenig unbeholfen wirken würdest. Ich denke ich würde mich dan anders verhalten...

PeterTheMaster

das ist immer GF(p^k) wobei p ne primzahl ist. bei 256 ist es also mod2, bei 5 ist es mod5 (weil mod p).

Ishildur

Ach so OK, man nimmt die kleinste mögliche Primzahl als Basis. Was ich dann aber immer noch nicht verstehe ist folgendes:

In der Definition von Rijndael wird folgende Vorgehensweise für eine Multiplikation in einem Galoisfeld beschrieben:

c(x) = (a(x) * b(x)) mod x8 + x4 + x3 + x + 1
Wenn ich also folgende Zahlen habe: 0x57 * 0x83, dann mache ich doch:
(0x57 * 0x83) mod 0x11b = 4D

Aber in der Doku steht 0x57 * 0x83 = 0xC1
Ich blicke einfach nicht durch!

Jester

Du bist sicher, daß Du richtig multipliziert hast? Polynommultiplikation? Schreib Dir die Elemente mal als Polynome hin und rechne dann.

Ishildur

Wie, was jetzt?
Polinome sind doch bloss eine andere Darstellung?

Bspw.:
Dez: 283
Hex: 0x11b
Bin: 100011011
Poly: x8 + x4 + x3 + x + 1

Was hat denn dies mit der multiplikation zu tun?

Jester

Polynome werden anders multipliziert als gewöhnliche Zahlen.

Nochmal langsam und zum mitschreiben: GF(256) ist *kein* Z/nZ, Du kannst also nicht einfach normal rechnen und modulo irgendwas tun. Das funktioniert so nicht. Du mußt Dir die Elemente als Polynome hinschreiben und mit denen rechnen.

Beispiel: binär 11, Dezimal 3. Das quadrieren wir mal. In Z kommt 9 raus. In GF(256) ist das aber (x+1)^2 = x^2+2x+1, 2x ist aber 0, also x^2+1, das ist binär 101 oder auch, wenn Du's unebdingt dezimal haben möchtest(macht aber halt keinen Sinn) 5.

Ishildur

Ja, aber 3^2 ist doch nicht 5 sondern 9! Dann stimmt doch schliesslich das Resultat nicht? Was macht es dann für einen Sinn?

SG1

Ishildur schrieb:

Ja, aber 3^2 ist doch nicht 5 sondern 9!

In diesem Koerper schon.

Jester

In dem Körper gibt es keine 9. Rechne mit den Polynomen. Fertig. Normale Zahlen funktionieren in diesem Körper nicht. 1+1 ist dort 0 und deswegen ist 9=1, wenn man so will. Du mußt in die Polynomdarstellung wenn Du verstehen willst was da passiert.

Ishildur

Ich habe nun versucht, eine Funktion in Java zu schreiben, welche 2 Werte in einem GF(2^8) berechnet, aber das Resultat stimmt nicht?

Weiss jemand, was ich falsch berechne?

// --------------------------------------- method pmul ---------------------------------------
 private static byte pmul(byte va1,byte va2){
  // declare and init local variables
  short rst = 0x00,tmp = 0x00;

  // start a loop for walking each bit
  for(byte i=0;i<8;++i){
   // check if the current bit in the first value is set
   if((va1 & (0x01 << i)) != 0x00){
    // copy the 2nd value into a temporary 16-Bit field and xor the shifted 2nd value
    tmp = va2;
    rst ^= (tmp << i);
   }
  }

  // return the result modulo an inreducible polynom of the 8th degree
  return (byte)(rst % 0x11b);
 }
 // -------------------------------------------------------------------------------------------

Jester

Dein modulo ist immer noch das modulo der ganzen Zahlen. Du mußt schon ne Polynomdivion machen und den Rest zurückgeben. Zumindest glaube ich das.

Hast Du mal ein Beispiel, das "falsch ausgerechnet" wird als Polynom hingeschrieben und von Hand berechnet, und dann den Debugger angeworfen?

Ishildur

Ach so, OK, alles klar!
Das letzte Problem ist nun nur noch, ein multiplikatives Inverses zu einem bestimmten Polynom zu berechnen. Also normalerweise ist ja z.B. das multiplikative Inverse von 3 einfach 1/3. Aber dies scheint ja hier wieder nicht zu funktionieren, da ja ein Galois Feld nur natürliche Zahlen enthalten darf. Ich habe in diesem Zusammenhang etwas von einem euklidischen Algorithmus gelesen, mit diesem kann man doch aber nur den grössten gemeinsamen Teiler berechnen:

Ich habe mir das mal in Java geschrieben:

private static byte ggt(byte va1,byte va2){
 while(va2 != 0x00){
  byte tmp = (byte)(va1%va2);
  va1 = va2;
  va2 = tmp;
 }

 return va1;
}

Aber wie ich damit ein multiplikatives Inverses einer bestimmten Zahl in einem Galois Feld als Polynom berechnen soll, ist mir schleierhaft...

Jemand eine Idee?

Jester

Such mal nach dem erweiterten euklidischen Algorithmus, der liefert Dir die Inverse. Denk aber dran, daß die Multiplikationen und modulos wieder im im richtigen Körper gerechnet werden müssen.

Ishildur

Ich bin mir noch nie so blöd vorgekommen, wie gerade nun! Ich verstehe überhaupt nichts! Das fängt schon mal damit an, dass ja der erweiterte euklidische Algorithmus zwei Eingabeparameter braucht, aber ich will ja nur das multiplikative Inverse zu EINEM Wert. Dazu kommt, dass da steht, dass es nicht für jede Zahl ein multiplikatives Inverses gibt, und da frage ich mich doch was das soll. Ich muss eben für jeden Wert zwischen 1 und 255 das multiplikative Inverse auf Polynombasis berechnen... geht das überhaupt?

Ich bin eigentlich normalerweise nicht so schwer von Begriff, aber diese vereinfachten Formeln, deren Herleitung ich nichtmal erahnen kann, verstehe ich einfach nicht! Und Formeln auswendig lernen, ohne sie wirklich zu verstehen, ist ja auch nicht das Wahre!

Gibt es denn keine Literatur, welche diese Dinge ein wenig veranschaulichen und nicht einfach Seitenweise Formeln und Gleichungen auflisten?

Lg Ishildur

Jester

Du hängst immer noch bei den Werten von 1 bis 255 fest. Vergiss das. In diesem Körper sind keine Zahlen so wie Du sie gewohnt bist.

über dem Körper mit 2 Elementen F_2 (oder GF(2) oder wie auch immer). Nimmt man sich daraus 2 Elemente p(X), q(X), die Teilerfremd sind, so läßt sich daraus die 1 kombinieren, das heißt es existieren a(X),b(X) Polynome in F_2[X] so daß gilt:

a(X)*p(X)+b(X)*q(X) = 1

Der erweiterte euklidische Algorithmus liefert Dir zur Eingabe von p(X) und q(X) die beiden anderen Polynome a und b.

Okay, wie hilft uns das nun bei unserer Problemstellung?

Ganz einfach, wir rechnen doch in F_2[X]/(p(X)) für ein bestimmtes p (hatte oben schon jemand gepostet). Wenn Du also ein Elemente q(X) da invertieren möchtest, dann schmeißt Du den euklidischen Algorithmus an und kriegst a(X) und b(X) mit a(X)*p(X)+b(X)*q(X) = 1. Das schauen wir uns nun modulo p(X) an und siehe da, es wird zu b(X)*q(X)=1. Also ist q(X) Inverse. Daß das immer klappt liegt daran, daß p(X) prim ist und jedes Polynom, das in GF(256) nicht 0 ist damit teilerfremd zu p(X) ist und man das daher immer machen kann.

Weils vielleicht auf den ersten Blick etwas kompliziert aussieht, das wichtigste nochmal in Kürze:

GF(256)=F_2[X]/(p(X)), q(X) wollen wir dadrin invertieren.

Schmeiße euklidischen Algorithmus mit p(X) und q(X) als Eingabe an, erhalte a(X) und b(X).
b(X) in GF(256) reinstecken (kann sein, daß Du mod p(X) machen mußt).
Das Ergebnis ist das Inverse zu q(X).

MfG Jester

Ishildur

@Jester
Also ich habe einen riesen Respekt, wie du das so einfach ohne Weiteres beschreiben kannst, aber ich verstehe wirklich überhaupt nichts! das liegt aber bestimmt nicht an deinen Ausführungen sondern an meinen mangelnden Kenntnissen:

Bspw.
Ich weis nicht, was ein Polynom-Ring ist, ich kenne nicht die Bedeutung Teilerfremd und was ich am schlimmsten finde, ich habe immer noch nicht verstanden, wieso man mit einem Körper rechnet, in dem eigene Gesetze gelten, welche mit jenen, welche man in der Schule lernt, nicht vereinbahr sind...

Ich möchte euch auch nicht auf der Pelle sitzen und ständig dumme Fragen stellen, sondern mir stattdessen das benötigte Wissen aneignen. Das Problem hierbei ist nur, dass ich im Internet keine geeignete Literatur finden kann. Alles, was ich finde, sind Vorlesungsscripts von diversen Universitäten, aus deren Ausführungen mir aber wiederum die Grundlagen fehlen.

Gibt es denn wirklich eine Literatur, wo diese Dingen samt Verwendungszweck und Aufbau umfassen und für einen Laien wie mich verständlich erklärt wird?

Lg Ishildur

Ishildur

Gut, die Bezeichnung Teilerfremd konnte ich einfach in Wikipedia nachschlagen und habe ich auch auf Anhieb verstanden, aber die Bezeichnung Polynomringe, da verstehe ich nichts!

Ich zweifle langsam an mir selber...

Ich habe das Gefühl, ich habe einfach etwas gaaaaanz, gaaaaanz Grundlegendes nicht verstanden, worauf all diese Dinge aufbauen!

megaweber

Sowas ist für Schüler(ich vermute mal, dass du einer bist!) auch nicht sehr einfach.
Habe das Buch "Einführung in die Kryptographie" von J.Buchmann erschienen im Springerverlag.

Dort sind sehr viele kryptographische Methoden beschrieben, unter anderem AES/Rijndael! Aber ebenso die mathematischen 'Grundpfeiler' zum rechnen in Restklassen- Polyomringen etc...

Jester

Ishildur: Ohne die Grundlagen ist das natürlich blöd. Kann ich verstehen. Der Polynomring über einem anderen Ring oder Körper ist im Prinzip einfach nur so, wie man Polynome normal halt auch macht:

a_n*x^n + ... + a_1 * x + a_0. Nur daß man halt als Koeffizienten Elemente aus dem Ring nimmt über dem man den Polynomring betrachtet. Hier also Koeffizienten in F_2.

Teilerfremd heißt im Prinzip nix anderes als ggT ist 1. Die Analogie zu den normalen Zahlen ist schon noch da, aber man muß halt sehr vorischtig sein, was man überträgt und was nicht. Polynomdivision kennst Du bestimmt. Damit kann man sagen was Teiler sein sollen (nämlich polynome durch die die Division aufgeht) und dann kann man auch sagen was teilerfremd sein soll.

Warum man sich das ganze anschaut? F_2 verhält sich ein bißchen wie ein Bit. Und wenn man sich die Polynome mit Koeffizienten in F_2 anschaut, dann verhalten die sich ein bißchen wie mehrere Bits. Betrachtet man alle Polynome über F_2 mit Maximalgrad 7, dann gibt es davon genau 2^8 Stück. Das heißt es gibt genau so viele wie ein Byte Werte annehmen kann. Über diese Konstruktion kriegste nun auf Deinen Bytes ne Addition und ne Multiplikation definiert. Und das tolle ist, Du fällst nicht raus, sondern landest immer wieder drin. Der Byte-Wert 128 entspricht einem Polynom, der Byte-Wert 2 auch. Das Produkt dieser Polynome kann man auch wieder in nem Byte speichern. Mit der normalen Multiplikation wäre es aber 2*128=256, Du würdest also nur noch ne 0 sehen in Deinem Byte und könntest die Operation daher nicht umkehren.

edit: Literatur ist ein bißchen schwierig, das gibt's in allen Varianten. Sag doch mal was zu Deinen Vorkenntnissen, dann können wir eventuell mehr sagen.

edit2: Algebraic Codes for Data Transmission | ISBN: 0521553741 fand ich nicht so schlecht. Ich habe die Einführung in dieses Thema aber nur überflogen, weil ich das schon kannte. Aber wenn Du in ner Bib dran kommst ist das ja kein Problem.