Probleme mit Galois Feld GF(2^8)

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.

Ishildur

Naja, ich kenne die lineare sowie die quadratische Algebra, Logarithmen, Geometrie und Trigonometrie, Matrix sowie Vektorenberechnunen und habe keine Probleme mit Termumformungen. Ich kenne die Mengenlehre und die damit verbundenen Symbolik. Ich kenne mich bestens mit den verschiedenen Zahlensystemen Dezimal, Oktal, Hexadezimal und Binärsystem aus.

Von den Programmierkenntnissen her, glaube ich, dass diese doch nicht schlecht sind, habe auch schon (für mich) grössere Projekte > 20'000 Codezeilen geschrieben. Kenne folgende Sprachen gut: C/C++/C#, Java, Delphi, PHP/HTML/CSS/Javascript.

So nun kommt das, was ich nicht kann:
Ich hatte vor 2 Tagen noch keine Ahnung, was ein Polynom oder ein irreduzibles Polynom vom x'ten Grad usw. ist (nun weiss ich es immer noch nicht wirklich). Den neuen euklidischen Algorithmus in seiner iterarischen sowie in seiner rekursiven Ausführung habe ich mittlerweile verstanden, was ich vom erweiterten allerdings nicht behaupten kann. Zwar habe ich kein Problem damit, ihn in irgendeiner Sprache zu implementieren, doch verstehe ich noch nicht 100%, was er genau macht, und ich habe wahnsinnig Mühe damit, Codeteile in meinen Programmen zu haben, die ich nicht vollständig verstehe...

Naja, wie dem auch sei, ich habe in der Zwischenzeit glaube ich ein wenig ein Bild davon bekommen, was mir fehlt und zwar ist dies die "Restklassenarithmetik" sowie die "Modulararithmetik" oder was meint Ihr?

Lg Ishildur

P.S.
Vielen vielen Dank für die vielen Post, das finde ich wirlich super cool`

Jester

Mit Vorkenntnisse meinte ich hauptsächlich die mathematischen Vorkenntnisse. Gut, lineare Algebra, das ist schonmal was Wert. Mit Z/pZ (also dem Körper mit p Elementen für p prim) kannste ja rechnen.

Um mehr zu verstehen wir die Konstruktion funktioniert würde ich Dir empfehlen mal GF(2^n) für kleine n zu studieren. Wenn Du Zeit und Lust hast vielleicht auch mal GF(3^n) für kleine n. Konstruktion geht so: F_2[X} und modulo X^n + X + 1 rechnen (oder auch ein anderes irreduzibles Polynom). Und dann bauste mal ne Verknüpfungstabelle für + und *. Daran sieht man schon einiges, wie's funktioniert. Wenn Du Fragen dazu hast, dann kannste sie ja hier stellen.

Ishildur

Ich habe nun ein wenig weiter ausgehohlt: Habe mir nun Funktionen sowie die Mengenlehre angeeignet und eigentlich auch Problemlos verstanden. Aber bei den Polynomen hänge ich fest:
Also was ist denn nun ein Polynom und wieso verwendet man diese? In Wikipedia steht folgendes drinn: "die Summe aus Vielfachen von Potenzen einer Variablen x"
Na klar, wenn das da drinn steht...

Also mal ehrlich: 2x^4+3x3+8x^2+x+8 Nehmen wir das mal auseinander:

Bspw. 8x^2 Sie Summe aus

Vielfache von Potenzen

einer Variablen x. 2 ist dann das Vielfache von was bitte sehr? das währe ja eine Irrationale Zahl?

Ausserdem:

Wenn ein Polynom nur aus der Summe aus Vielfachen von Potenzen bestehen würde, dann müsste ja 8x^2 = x^2 sein.

Also was genau verstehe ich denn nun nicht? Werde nicht aufgeben!

Wenn du schon Vorkenntnisse in Lineare Algebra hast, wird folgendes am einfachsten und genausten sein: Wenn du als Basis des Vektorraums der Polynome die Menge B := { x^0, x^1, x^2, ... } (auch "Monome" genannt) zugrunde legst, ist ein Polynom eine Linearkombination aus Vektoren der Basis B.

Jester

2 ist ein vielfaches von x^0, was ja nach Definition 1 ist. Warum sollte 8x^2 = x^2 sein? Beides sind Polynome, aber halt verschiedene.