Probleme mit Galois Feld GF(2^8)

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.

Ishildur

So, ich glaube, ich habs nun verstanden. Habe einen Algorithmus geschrieben, um eine Polynommultiplikation in einem F(2^8) zu berechnen:

// ---------------- method polynomial multiplication in F(2^8) ----------------
 public static byte gf256_mul(byte va1,byte va2){
  // declare and init local variables
  int rst = 0x00000000; // the result value

  // loop for walking each bit beginning a the less significant bit
  for(int i=0;i<8;++i){
   // check if the current bit of the factor was set
   if((va1 & (0x01 << i)) != 0x00){
    // shift the second factor by the current line and xor it by the result
    int tmp = va2 & 0x000000ff;
    rst ^= (tmp << i);
   }
  }

  // loop for walking each bit beginning at the most significant bit
  for(int i=0;i<16;++i){
   // check if the result is greater or equal the dividor and if the current
   // bit of the subresult was set was set
   if(rst >= 0x11b && (rst & (0x8000 >> i)) != 0x00)
    // shift the dividor as needed and xor it by the result
    rst ^= (0x11b << 0x07 - i);
  }

  // return the result
  return (byte)rst;
 }
}
// -----------------------------------------------------------------------------

Aber geht das nicht einfacher?

Lg Ishildur

P.S.
Erbitte konstruktive Kritik und Anregungen

Ishildur

Habe noch ein wenig optimiert:

// ---------------- method polynomial multiplication in F(2^8) ----------------
 public static byte gf256_mul(byte va1,byte va2){
  // declare and init local variables
  int rst = 0x00000000; // the result value

  // loop for walking each bit beginning a the less significant bit
  for(int i=0;i<8;++i){
   // check if the current bit of the factor was set
   if((va1 & (0x01 << i)) != 0x00){
    // shift the second factor by the current line and xor it by the result
    int tmp = va2 & 0x000000ff;
    rst ^= (tmp << i);
   }
  }

  // loop for walking each bit beginning at the most significant bit
  for(int i=0;i<16;++i){
   // break the loop if the current result is smaller than the dividor
   if(rst < 0x11b) break;

   // check if the current bit of the subresult was set
   if((rst & (0x8000 >> i)) != 0x00)
    // shift the dividor as needed and xor it by the result
    rst ^= (0x11b << 0x07 - i);
  }

  // return the result
  return (byte)rst;
 }
}
// -----------------------------------------------------------------------------

Jester

Das sieht schonmal gut aus.
Viel einfacher und schneller wird's wohl kaum gehen. Für das kleine Teil könntest Du aber natürlich auch ne Wertetabelle berechnen, wenn's später schnell gehen soll. Das Kürzen muß nicht zwangsläufig erst am Ende passieren. Du kannst auch das Zwischenresultat immer wieder kürzen. Das ist allerdings vermutlich auch nicht schneller.

Ishildur

@Jester
Ich weiss, ich weiss... Ich poste dies hier, damit man besser den Link dazu machen kann, ohne immer hin und her blättern zu müssen!

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

Ich habe ein wenig Mühe mit den mathematischen Ausdrücken, die du verwendet hast, das liegt daran, dass ich mich nie mit dieser Art der Mathematik beschäftigt habe. Also mal sehen, ob ich das einigermassen verstanden habe:

ist wohl eine andere Schreibweise für GF(2^8) oder F(2^8) ?

2. Mit p(X) ist vermutlich eine Polynofunktion gemeint: bspw. p(X) = x^3+x+1 ?
3. Mit "Wir nehmen daraus 2 Elemente p(X), q(X) währe bspw. x^3+x+1, x^2 möglich?
4. a(X)*p(X)+b(X)*q(X) = 1 währe bspw. <a(X)> * 01000110 + <b(X)> * 11010010 = 00000001, oder so?
5. a(X)*p(X)+b(X)*q(X) mod p(X) = b(X) * q(X) = 1 währe bspw. <a(X)> * 010001100 + <b(X)> * 11010010 mod 010001100 = <b(X)> * 11010010 = 00000001 ?
6. Ich habe schon die allgemeine Definition F(p^n) gesehen. Is es Zufall, dass du p(X) verwendest oder ist das Absicht und damit p(X) = x oder 00000010 gemeint ?

Mit anderen Worten: bspw.

Invertiere x^4+x3+x = 11010 = 0x1A

AEA(x,x^4+x3+x) = AEA(10,11010) = AEA(0x02,0x1A)

a(X) * x^4+x3+x + b(X) * x mod x = <b(X)> * x^4+x3+x = 1
<a(X)> * 11010 + <b(X)> * 10 mod 10 = <b(X)> * 11010 = 1
<a(X)> * 0x1A + <b(X)> * 0x02 mod 0x02 = <b(X)> * 0x1A = 0x01;

Also schlussendlich b(X) = Inv(0x1A) weil b(X) * 0x1A = 0x01 umgeformt so aussieht: b(X) = 0x01/0x1A ?

Sag mir bitte, wenn ich etwas falsch verstanden habe!

P.S.
Ich komme mir gerade ein wenig vor wie ein Schüler, der seinen Lehrer zum 20. Mal dieselbe Frage stellt und dabei hofft, es dieses Mal zu verstehen... :p

Jester

der Polynomring über R. F_2[X] sind also die Polynome mit Koeffizienten in F_2. Das ist noch nicht der Körper GF(256). Beispielsweise hat x dadrin noch keine Inverse. Erst durch das modulo-Rechnen wird daraus ein Körper.

Deine angegeben Polynome sind natürlich möglich. Allerdings soll p(X) später die Rolle des Polynoms spielen, das Du rausfaktorisierst (bzgl. dem Du modulo rechnest). megaweber hatte es m genannt: p(X) = X^8+X4+X^3+X+1. Als q(X) nimmste das Element das Du invertieren willst.

Die komplette Rechnung vor dem mod p(X) findet sozusagen rein mit Polynomen statt. Letztlich wollte ich damit aber nur zeigen, warum das ganze funktioniert.

Die Frage mit dem F(p^n) verstehe ich nicht ganz. F(p^n) ist einfach der Körper mit p^n Elementen (p Primzahl). Auch wenn man die unterschiedlich erzeugen kann, kann man zeigen, daß sie alle isomorph sind.

Deine restliche Rechnung stimmt nicht, weil Du nicht das richtige p(X) verwendet hast. Du kannst immer nur den ggT kombinieren. Bei Deinen beiden verwendeten Polynomen ist das X und nicht 1. Die Irreduzibilität von X^8+x4+x^3+x+1 gewährleistet aber, daß jedes Polynom kleineren Grades dazu teilerfremd ist.

Hoffe das hilft.
Wenn Du noch ein bissel mehr Theorie dazu haben willst, dann beschäftige Dich mal mit Idealen und sowas.

Ishildur

Ja, was ich einfach nicht verstehe, was ist denn das richtige p(X) ? Wenn ich bspw. das Polynom x^4+x2+x+1 habe, wie sehen dann die beiden parameter für den erweiterten euklidischen Algorithmus aus? Der Eine Parameter ist natürlich das oben beschriebene Polynom, aber was in aller Welt ist dann der zweite Parameter? Ich dachte eben erst, es sei p aus GF(p^n). In einem GF(256) also p = 2 = x, aber du hast ja gesagt, dass dies falsch sei...

Lg Ishildur

SG1

Ishildur schrieb:

Ja, was ich einfach nicht verstehe, was ist denn das richtige p(X) ? Wenn ich bspw. das Polynom x^4+x2+x+1 habe, wie sehen dann die beiden parameter für den erweiterten euklidischen Algorithmus aus? Der Eine Parameter ist natürlich das oben beschriebene Polynom, aber was in aller Welt ist dann der zweite Parameter?

Ein beliebiges, irreduzibles Polynom vom Grad 8 aus F_2[X]. Grad 8 heisst dabei, dass der hoechste Exponent 8 ist, irreduzibel heisst, dass man es nicht als Produkt von 2 (oder mehr) Polynomen schreiben kann. Also zum Beispiel das von Dir im ersten Post genannte x^8 + x^4 + x^3 + x + 1.

Jester

Ishildur schrieb:

also p = 2 = x

Du hast ja die Zahlen immer noch nicht losgelassen. 2!=x 2 ist 0 in diesem Körper. Laß das mit den Zahlen am besten ganz und schreibe alles als Polynome. Alles andere ist nur verwirrend. GF(...) sagt nur wieviele Elemente der Körper hat. Da diese Körper nur für Primzahlpotenzen existieren schreibt man oft auch GF(p^n).