PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : AES - einige Schwierigkeiten beim Verstehen


Schroeder
2004-03-16, 13:52:07
Also ich schlage mich jetzt schon seit Stunden mit diesem AES (Advanced Encryption Standard) rum, und bleibe immer wieder bei der gleichen Stelle hängen. Das ist jetzt was für Spezies die diesen Mist gefressen haben, ich glaube für alle anderen sauschwer zu verstehen.
Die Schlüsselexpansion. Ich komme soweit mit bis dieser Kack Rcon[i] losgeht, der dann auf die mathematischen Grundlagen in diesem Verfahren zurückführt. Und mit denen habe ich so meine Schwierigkeiten. Und zwar ist dieses Rcon[i] ein Feld mit 4 Bytes [x^(i-1),00,00,00] die letzten drei sind 00h bloß das erste Byte ist wohl variabel. Wenn ich da aber jetzt ein i<8 übergebe, habe ich ja eine Zahl die größer als ein Byte ist, und die wird irgendwie über diese mathematischen Operationen GF(2^8)??? reduziert, und ich habe keinen Plan wie.
Um das mal zu verdeutlichen was ich meine, dazu hab ich mal den offiziellen Standard verlinkt. Im Anhang A.1 ist eine Beispiel-Schlüsselexpansion dargestellt, und in der Tabelle kapiere ich einfach nicht wie die dann bei i=36 auf den Rcon-Wert von 1b000000 kommen.
Ich hoffe irgendeiner kann mir helfen, das ist nämlich äußerst wichtig für mich.
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
http://www.google.de/search?q=cache:bmoDsNYjDUwJ:csrc.nist.gov/publications/fips/fips197/fips-197.pdf+fips+197&hl=de&ie=UTF-8

edit. Kann sein dass die ganze Chose besser aufgehoben ist, im Programmieren-Forum, aber ich wills ja nicht Programmieren, sondern begreifen und erklären.

Schroeder
2004-03-17, 11:02:30
Keiner da der mir helfen kann? ;(

Frank
2004-03-17, 12:15:25
Hallo Schroeder

wenn ich dir deine Frage nach den Operationen in GF(2^8) wirklich exakt(!) beantworten soll, dann wird das ganze hier mehrere A4 Seiten benötigen. Für den ganzen Spass sind einfach ein paar Dinge als Grundlage nötig, die man auch wieder ausführlich erklären sollte. Ich versuch mich aber kurz zu fassen (evtl ist es hilfreich, wenn du mal angibts auf welchem Stand du in Mathe bist).

Also kommen wir zum GF(2^8). Bevor wir mit Operationen anfangen, solltest du vorher ja wissen was das ganze ist. GF ist eine Abkürzung für Galois Field. Das besondere an diesen Feldern (von Elementen) ist wohl, das man darauf mehrere Operationen definieren kann und das ganze sich dann von anderen Feldern abhebt. Um das ganze beim Namen zu nennen: Es gibt zum Beispiel: Gruppen, Ringe, Körper und andere Abarten. Nimm dir zum Beispiel die Ganzen Zahlen (...,-3,-2,...6,7,8,...) zusammen mit der Addition: du kannst nicht nur beliebig addieren sondern auch subtrahieren (mit Inversen Elementen addieren) - wenn das gegeben ist, spricht man von einer Gruppe der ganzen Zahlen bzgl. der Addition. Bei den natürlichen Zahlen (1,2,3,4,5,...) klappt das mit dem Subtrahieren ja nicht immer - das ist auch nur eine Halbgruppe deswegen. Eine Halbgruppe sind aber auch die ganzen Zahlen bzgl. der Multiplikation. Man spricht dann insgesamt von einem Ring (der ganzen Zahlen bzgl Add und Mul). Wo das ganze dann mit Addition und Multiplikation (fast) uneingeschränkt klappt, nennt sich dann Körper (zum Beispiel die Reellen Zahlen).

Zurück zum GF. Am bekanntesten ist wohl der GF(2) - ein Körper. Es gibt nur die Elemente 0 und 1. Die Operationen:
0+0=0
0+1=1
1+0=1
1+1=0
0*0=0
0*1=0
1*0=0
1*1=1
Stell dir einfach vor du rechnest das ganze immer nach jedem Schritt Modulo 2. Damit bleibst du quasi immer in deiner Elementmenge hängen. Das ganze läuft auch unter den Namen Restklassen, was die Operation Modulo auch etwas anschaulicher erklärt:
nehmen wir einfach mal etwas komplizierter den GF(7) wo alles Modulo 7 gerechnet wird: Wenn wir nur Elemente von 0..6 haben, dann bietet sich der Rest bei Division durch 7 förmlich an. Also 14 : 7 = 2 Rest 0 -> 0. 17 : 7 = 2 Rest 3 -> 3. 5 : 7 = 0 Rest 5 -> 5. usw. ...

GF gibt es aber nicht nur von "2" (GF(2)), sondern allgemein von Primzahlen (GF(3), GF(17),...) und - Primzahlpotenzen. Alles schöne Körper. :) Und 256 ist eine Primzahlpotenz. AES verwendet nun den Körper GF(2^8). Wie sehen die Elemente aus? Keine Zahlen sondern alles Polynome höchstens von Grade 7 (2^8) und als Vorfaktoren der einzelnen Elemente nur 0 und 1 (2^8) (quasi GF(2)) (also nicht 4*X^2 sondern da geht nur 0*X^2 und 1*X^2) (man müsste jetzt wohl klären was ein Polynomring ist :( ). Für die Erzeugung aller 256 Element von GF(2^8) wird aber ein spezielles Polynom 8.ten Grades benötigt. Mit diesem lassen sich alle anderen Polynome mit Grad<8 nach und nach generieren. Bei AES ist das glaube ich x^8+x^4+x^3+x+1. Fakt ist, dass wenn du nun in diesem Körper rechnest - analog GF(2) - alles Modulo x^8+x^4+x^3+x+1 gerechnet wird. :D (wiegesagt - bin mir mit dem Polynom nicht sicher - steht aber bestimmt in deinem verlinktem pdf)

Und das ist ja nun wohl deine Frage.
Dazu eine simples Beispiel für den GF(2^3)
Wir nehmen als erzeugendes Polynom "X^3 + X + 1", was jetzt alles Polynome von Grad<3 erzeugen sollte (nur mit Vorfaktoren 0 und 1)
X^0 = 1
X^1 = X
X^2 = X^2
X^3 = ...jetzt wird reduziert mod(ulo) X^3 + X + 1 - um es kurz zu machen: X^3 mod X^3 + X + 1 = X + 1
X^4 = X^3 * X (X^3 "ist" X+1) also: (X + 1)*X = X^2 + X
X^5 = X^3 * X^2 = (X + 1) * X^2 = X^3 + X^2 = X + 1 + X^2
X^6 = X^5 * X = X^3 + X^2 + X = X + 1 + X^2 + X = X^2 + 1
X^7 = X^6 * X = X^3 + X = X + 1 + X = 1 = X^0 -> alle Elemente erzeugt.

Nehmen wir ein großes Beispiel nachdem das Prinzip klar sein sollte:
GF(2^8)
x^8+x^4+x^3+x+1
x^8 mod x^8+x^4+x^3+x+1 = x^4+x^3+x+1 das werden wir verwenden. :)
http://rcswww.urz.tu-dresden.de/~fh468638/temp/mod-ploy.gif
(das "=" ist natürlich dann das "=" für modulo x^8+x^4+x^3+x+1)

hoffe das reicht vorerst. Wenn nicht weiter fragen.

Schroeder
2004-03-17, 13:06:22
Ich beginne zu begreifen, danke. :massa:

Schon erstmal Wahnsinn das du dich 100% richtig an das Polynom erinnert hast, ich vergess das garantiert innerhalb von ein paar Wochen ...

Deine Erläuterung klingt für mich zwar an einigen Stellen, noch sehr "tiefgründig" (um es mal dezent zu sagen) aber das wass ich verstehen wollte, hab ich jetzt erstmal begriffen (der genaue Rechenvorgang) und das sollte für meine Studienarbeit erstmal ausreichen. Ich hatte das zwar schon so gerechnet aber eben falsch, und da war ich dann sehr "frustriert", da hab ich mir dann erstmal den RC4 vorgenommen, der im Vergleich um Welten einfacher ist. Danke dir. Falls ich aber trotzdem noch Fragen haben sollte komme ich schon damit.

Frank
2004-03-17, 13:30:27
Ich hatte neben den ganzen Algebra Vorlesungen auch ausgiebig die Reihe Kryptologie und Kyryptologie auf Elliptischen Kurven. Irgendwann muss ja was hängen bleiben. :) Wenn du noch irgendwo Erklärungsbedarf hast, einfach hier oder per PN :)

Gast
2004-03-17, 13:34:12
Respekt Frank!

Immer wieder schön zu sehen, was für Genies unter den Moderatoren wandeln. :)

Frank
2004-03-17, 17:46:50
danke für die Blumen - aber übertreib mal nicht. Das dürft wohl jeder normale MatheGrundstudiumStudent auf die Reihe bekommen. :)

Schroeder
2004-03-19, 14:01:36
Ich hätte mal noch eine etwas "stupidere" Frage. Was wäre eine gute Übersetzung, ins Deutsche halt, für das im Standard immer wieder verwendete "finite field (elements)". Tut mir leid mir sagt das herzlich wenig, hat das was mit den Finiten Elementen zu tun? Sowas hatte ich in meinen 4 "Mathe-Semestern" nicht daher, bitte nicht lachen oder so.

ethrandil
2004-03-19, 15:30:22
finite adj. [math.] - endlich
field [math.] - der Körper
elements - die Grundbestandteile

Ein Körper mit einer endlichen Anzahl Ecken/Dimensionen wasweißich?

bzw. ein endliches Galois Field?

mehr kann ich dazu nicht vermuten...

- Eth

Stone2001
2004-03-19, 15:41:15
'Finite field' ist AFAIK nur ein anderer Name für 'Galois Field'