MastersForum

Servus,

ich arbeite mich gerade durch DES und habe das meiste sehr gut verstanden, jedoch hakt es an einer Stelle:
Wikipedia-Erklärung

Da steht, es gibt R + 1 Runden, also die 10, 12 bzw. 14 Runden + die Schlussrunde. Zählt nun die Vorrunde als die erste reguläre Runde, oder wird nur für die der Schlüssel der ersten regulären Runde verwendet? Kann mir zwar beides nicht so wirklich vorstellen, aber andere Möglichkeiten lese ich daraus nicht.

Danke im Voraus!


lg - eru

Soweit habe ich das auch verstanden, nur was für ein Schlüssel wird in der Vorrunde bei der KeyAddition verwendet? Ein eigener? Müssten es dann aber nicht R + 2 Rundenschlüssel geben?

Ahh... ich verstehe.

Danke! =)

Nächstes Problem.
-> http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Auf Seite 18 oben.
Ich hab mir das Ding mit dem Falk'schen Schema hergeleitet und komme auf das selbe, merkwürdig nur, dass ich bei einer Beispielrechnung, weit über 255 komme. Klar, wenn jede "Zelle", also Byte von dem Word (= Spalte) bis zu 255 sein kann und mit 3 multipliziert wird, dass da nicht selten etwas über 255 rauskommt. In meinem Beispiel bleibt der Wert auch nach dem XOR so groß, ist ja auch nur ein Wert, der so herausragt.


(Die Werte stammen aus einem Zufallsgenerator und haben vermutlich gar keinen Sinn.)

Oben ist meine Spalte = Word, Zelle = Byte.
Links ist die feststehende Tabelle von AES.
Alles binär.

Wo ist mein Fehler?
Danke für jede Hilfe!


lg - eru

Edit: NVM man multipliziert da iwie anders...

Bis eben waren sie mir nicht bekannt, habe mich jetzt schmerzlich da durchgekämpft und verstanden wie es funktioniert, jedoch nicht warum es so funktioniert. In meiner Facharbeit schreibe ich einfach einen Verweis, hat meine Lehrerin eh vorgeschlagen.

Die "Benennung" d.h. was das ist steht drunter.. wüsste nicht was ich nicht groß dazu sagen sollte. Ist halt ein Falk'sches Schema mit einer Matrix und einem Spaltenvektor, nur mit binären Zahlen. Wenn man das allgemein ausformuliert kommt man auf das, was in 5.1.3. in dem PDF bearbeitet wird.
Btw... wtf? Bei mir existiert 5.6. nicht mal. o_O

Jedenfalls hab ich es jetzt, trotzdem danke für die Bemühungen!

Was daran so lustig? Ich finds nicht so dolle...

War eigentlich ganz nett beschrieben, warum das so ist, ist mir zwar ein Rätsel, aber egal. ^^

Habe diese Seite dazu missbraucht.

Naja, irgendwie nette Bezüge von binären Zahlen auf Polynome.

Bspw.
(dec)40 = (hex)28 = (bin)00101000
Also 40 = f(x)=x^5 + x^3 für x=2
(dec)22 = (hex)16 = (bin)00010110
Also 22 = f(x)=x^4 + x^2 + x für x=2

+ entspricht XOR
- entspricht XOR
(Da ist das erste: warum?!)
<< entspricht Linksverschiebung, also * x = * 2

-> 40 * 22 = 40 * (16 + 4 + 2) = 40 * 16 + 40 * 4 + 40 * 2

40 * 2 = 00101000<< = 01010000 = 80
40 * 4 = 80 * 2 = 01010000<< = 10100000 = 160
40 * 8 = 160 * 2 = 10100000<< = 101000000 = 320 > 255, darf nicht!
Also 101000000 XOR 100011011 (nur kP wo die Zahl herkommt) = 01011011 = 91
40 * 16 = 91 * 2 = 01011011<< = 10110110 = 182

Eingesetzt:
10110110 XOR 10100000 XOR 01010000 = 01000110

Ergo ist 40 * 22 = 70



Richtig? Oder absoluter Unsinn?

Ok, nach Probe (= Entschlüsselung) ist alles wieder aufgegangen, von daher gehe ich mal davon aus, dass es richtig ist.

Das ist zum Teil ja sehr AES spezifisch, deshalb hab ich bzgl. Herkunft von 100011011 auf das AES PDF vom NIST verwiesen. Steht da zwar auch nicht, woher das kommt, aber dann sieht die Lehrerin, dass es nicht mal da steht.

Dass es sich bei 100011011 und das irreduzible Rijandael Polynom handelt habe ich im laufe meiner Recherchen schon mindestens fünf mal gelesen, ich weiß einfach nicht, was ein irreduzibles Polynom ist. Wenn ich den Namen richtig interpretiere lässt es sich nicht (z.B. per Partitialdivision) in kleinere ganzrationale Polynome aufteilen? Ergo ist jedes ganzrationales Polynom ohne reelle Nullstellen ein irreduzibles Polynom?
In dem Fall wurde 100011011 zufällig gepickt, könnte auch jedes andere mit x^8 sein, was irreduzible ist?

Kommt von Wand, sowie Rächtschreibung von Rache und Lebensgefährtin von Lebensgefahr.

Quoted

Original von AtroX_Worf
Was ist denn ein ganzrationales Polynom? Ansonsten ist ein Polynom über R ohne Nullstellen in R nicht irreduzibel. Das Polynom f(x)=x-c hat die Nullstelle c, ist aber irreduzibel. Nur konstante Polynome f(x) = c mit c!=0 haben keine Nullstellen mehr, aber für konstante Polynome macht die Eigenschaft Irreduzibilität wenig Sinn bzw. ist gar nicht erst für sie definiert.

Ein ganzrationales Polynom ist ein Polynom mit ausschließlich natürlichen Exponenten vom x, also Exponent aus |N_+\0 . Das jedenfalls lehrt man uns in der Schule, nichts ungewöhnliches wenn es Unsinn ist....

Quoted

Ohne den Algorythmus zu kennen kannst du wohl jedes Polynom vom Grad 8 aus dem F_256 nehmen, welches irreduzibel über dem F_2 ist.
Ich schätze mal du brauchst ein Polynom vom Grad 8, um bei der Multiplikation von Polynomen immer modulo dieses Polynoms rechnen zu können und so immer bei Grad max 8 zu bleiben.

Genau, x^8 muss auf jeden Fall vorhanden sein.
In GF(2^8) ist ja die größte mögliche Zahl 255 (2^8-1), entspricht binär 11111111 . Beim multiplizieren wird der kleinere Faktor in Zweierpotenzen zerlegt (was beim binären ja im Endeffekt auch gemacht wird, deswegen rechne ich ganze Zeit im binären Zahlensystem) die resultierenden Zweierpotenzen werden ausgeklammert und jedes Einzelergebnis wie folgt berechnet:
Man beginnt mit dem größeren Exponenten, den ich an dieser Stelle mal mit p bezeichne, und multipliziert ihn mit 2^0, also 1. Das Ergebnis ist trivial p. Ergo p*1=p .
Danach rechnet man p * 2^1 = p * 2. Um das zu berechnen kann man binär entweder eine Linksverschiebung durchführen oder in der Polynomschreibweise mit x (also 2) multiplizieren. Im binären wird für den Fall, dass an der 1. Stelle von links (also x^7) von p eine 1 steht nach der Linksverschiebung mit 100011011 XOR verknüpft (bzw. Polynomschreibweise Modulo gerechnet), so dass die 1, die für einen auf jeden Fall größeren Wert als 255 sorgt, "verschwindet". Aus dem Grund muss in der Polynomschreibweise x^8 vorhanden sein, bzw. binär die neunte Stelle von rechts eine 1.
Das Ergebnis wird wieder *2 (also p*4) gerechnet und das wieder etc bis man alle notwendigen Teile hat. Die Einzelergebnisse werden am Ende addiert, dass heißt in GF auf mit XOR Verknüpft.
Das ist übrigens auch sehr entscheidend... eine Addition ist genauso wie eine Subtraktion immer eine XOR Verknüpfung und eine Multiplikation kann/sollte immer (zumindest in GF(2^8)) nur mit einem Faktor 2 durchgeführt werden.

Quoted

Original von AtroX_Worf
Für mich hat ein Polynom immer nur Exponenten aus den natürlichen Zahlen. Aber ich kenne mich in Algebra auch nicht sonderlich gut aus.

Was meinst du mit Faktor 2? Über F_2 ist das die Zahl 10, d.h. das Polynom 1*x+0 = x?! Wenn du ein Polynom mit x multiplizierst, dann erhöht sich überall der Polynomgrad um 1, d.h. im Binärsystem schiebst du alles eine Stelle nach links.

Jep, genau das meine ich.

f(x)=x^8+x^4+x^3+x+1

p*30 -> 30=16+8+4+2 -> p*30=p*16+p*8+p*4+p*2
p*43 -> 43=32+8+2+1 -> 43*p=p*32+p*8+p*2+p

p=p
a = 2*p -> p * x, falls größer 255: mod f(x)
b = 4*p = 2*a -> a * x falls größer 255: mod f(x)
etc.

Edit: x=2 ^^