AES/ S-Box berechnen < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:54 Fr 05.11.2010 | | Autor: | Lybius |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hey Servus,
Ich schreib jetzt dank eurer Hilfe seit Sommer erfolgreich an meiner Facharbeit über Kryptographie.
Ich hab eigentlich das meiste schon fertig, aber ich stocke zur Zeit an der Erläuterung von AES (128).
Und zwar bekomme ich es einfach nicht hin, die Substitution ohne vorgefertigte S-Box zu bewältigen.
Das Invertieren klappt noch, aber nach dem Multiplizieren mit der Matrix und dem Addieren des Vektors, mag das Ergebnis einfach nicht stimmen.
Könnte mir jemand einen Beispielwert berechnen, damit ich hinter das System steige ? Wäre mir wirklich eine Hilfe.
Ich rechne eigentlich immer mit Hexadez-System, invertiere im Dezimal und multipliziere mit Binär. Weiß nicht ob das sinnvoll ist.
Vielen Dank euch allen für dieses Forum. Bis dann und Servus !!
[mm] \produkt_{i=1}^{100}(i*"Danke [/mm] !!!")
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:44 Sa 06.11.2010 | | Autor: | rainerS |
Hallo!
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hey Servus,
>
> Ich schreib jetzt dank eurer Hilfe seit Sommer erfolgreich
> an meiner Facharbeit über Kryptographie.
> Ich hab eigentlich das meiste schon fertig, aber ich
> stocke zur Zeit an der Erläuterung von AES (128).
> Und zwar bekomme ich es einfach nicht hin, die Substitution
> ohne vorgefertigte S-Box zu bewältigen.
> Das Invertieren klappt noch, aber nach dem Multiplizieren
> mit der Matrix und dem Addieren des Vektors, mag das
> Ergebnis einfach nicht stimmen.
> Könnte mir jemand einen Beispielwert berechnen, damit ich
> hinter das System steige ? Wäre mir wirklich eine Hilfe.
> Ich rechne eigentlich immer mit Hexadez-System, invertiere
> im Dezimal und multipliziere mit Binär. Weiß nicht ob das
> sinnvoll ist.
Ich verstehe deine Frage nicht, vielliecht führst du mal genau aus, was dein Problem ist.
Kennst du übrigens ![[]](/images/popup.gif) CrypTool ? Das ist einiges zu AES dabei.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:52 Sa 06.11.2010 | | Autor: | Lybius |
Mein Problem ist:
- Ich bin grad bei dem Kapitel AES
- Erläutere gerade die S-Box
- Wollte schreiben wie man die Werte der S-Box berechnet
- Habe es geschafft den Wert (irgendeinen) zu invertieren
- Ich scheitere an der Multiplikation mit der Matrix
- bzw. meine Werte stimmen nie mit denen aus den vorgefertigten S-Boxen überein
- ich wäre sehr dankbar wenn mir jemand einen Wert berechnet.
- ja Cryptool hab ich, aber ich find dort die Dokumentation nicht
Vielen Dank für die schnelle Antwort.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:55 Sa 06.11.2010 | | Autor: | felixf |
Moin!
> Mein Problem ist:
> - Ich bin grad bei dem Kapitel AES
> - Erläutere gerade die S-Box
> - Wollte schreiben wie man die Werte der S-Box berechnet
> - Habe es geschafft den Wert (irgendeinen) zu invertieren
> - Ich scheitere an der Multiplikation mit der Matrix
> - bzw. meine Werte stimmen nie mit denen aus den
> vorgefertigten S-Boxen überein
> - ich wäre sehr dankbar wenn mir jemand einen Wert
> berechnet.
> - ja Cryptool hab ich, aber ich find dort die
> Dokumentation nicht
Es waer hilfreich, wenn du eine Beispielsberechnung mitposten wuerdest, so dass man nachschauen kann wo es hakt.
Ich nehme das hier mal als Referenz.
Sei [mm] $GF(2^8) [/mm] = [mm] \IF_2[x] [/mm] / [mm] (x^8 [/mm] + [mm] x^4 [/mm] + [mm] x^3 [/mm] + x + 1)$ (das ist wie beim Link; bei AES ist evtl. das Polynom ein anderes, was natuerlich auch zu anderen Ergebnissen fuehrt).
Sei jetzt $f = [mm] x^7 [/mm] + [mm] x^2 [/mm] + 1 [mm] \in GF(2^8)$ [/mm] gegeben. Um das Inverse zu berechnen, bequeme ich den Erweiterten Euklidischen Algorithmus mit $f$ und $g = [mm] x^8 [/mm] + [mm] x^4 [/mm] + [mm] x^3 [/mm] + x + 1$.
$g = x [mm] \cdot [/mm] f + [mm] x^4 [/mm] + 1$
$f = [mm] x^3 \cdot (x^4 [/mm] + 1) + [mm] x^3 [/mm] + [mm] x^2 [/mm] + 1$
[mm] $x^4 [/mm] + 1 = (x + 1) [mm] \cdot (x^3 [/mm] + [mm] x^2 [/mm] + 1) + [mm] x^2 [/mm] + x$
[mm] $x^3 [/mm] + [mm] x^2 [/mm] + 1 = x [mm] \cdot (x^2 [/mm] + x) + 1$
Damit ist $ggT(f, g) = 1$.
Zurueckeinsetzen:
$1 = [mm] (x^3 [/mm] + [mm] x^2 [/mm] + 1) + x [mm] \cdot (x^2 [/mm] + x) = [mm] (x^3 [/mm] + [mm] x^2 [/mm] + 1) + x [mm] \cdot (x^4 [/mm] + 1 + (x + 1) [mm] \cdot (x^3 [/mm] + [mm] x^2 [/mm] + 1)) = (1 + x + [mm] x^2) (x^3 [/mm] + [mm] x^2 [/mm] + 1) + x [mm] \cdot (x^4 [/mm] + 1) = (1 + x + [mm] x^2) [/mm] (f + [mm] x^3 (x^4 [/mm] + 1)) + x [mm] \cdot (x^4 [/mm] + 1) = (1 + x + [mm] x^2) [/mm] f + (x + [mm] x^3 [/mm] + [mm] x^4 [/mm] + [mm] x^5) \cdot (x^4 [/mm] + 1) = (1 + x + [mm] x^2) [/mm] f + (x + [mm] x^3 [/mm] + [mm] x^4 [/mm] + [mm] x^5) \cdot [/mm] (g + x f) = (1 + x + [mm] x^4 [/mm] + [mm] x^5 [/mm] + [mm] x^6) [/mm] f + (x + [mm] x^3 [/mm] + [mm] x^4 [/mm] + [mm] x^5) [/mm] g$
Also ist $1 + x + [mm] x^4 [/mm] + [mm] x^5 [/mm] + [mm] x^6$ [/mm] das modulare Inverse von $f$.
So. Jetzt entspricht das Inverse dem Vektor [mm] $\pmat{ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 }$. [/mm] Multiplikation des Vektors mit der Matrix aus dem Link gibt [mm] $\pmat{ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1 }$. [/mm] Dazuaddieren von [mm] $\pmat{ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 }$ [/mm] ergibt schliesslich [mm] $\pmat{ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 }$.
[/mm]
Wandeln wir das mal in Hexadezimalschreibweise um. Es ist $f = [1000 [mm] \, [/mm] 0101]$, also $0x85$. Das Ergebnis ist $[1001 [mm] \, [/mm] 0111] = 0x97$. Vergleicht man das jetzt mit der Tabelle, so sieht man, dass es passt.
Das waer also ein Beispiel.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:14 Sa 06.11.2010 | | Autor: | Lybius |
Vielen Dank für die genaue Aufstellung. So hab ich rausgefunden, dass es bei mir schon beim inversen Element scheitert.
Ich hab zuerst 85 ins Dezimalsystem umgerechnet =133 und dann das Inverse Element modulo 256 gesucht, was bei mir 77 war. Ich hab bis jetzt versucht immer um das Galois-Feld rumzuarbeiten, da ich denke, dass das für ne Facharbeit ein Overkill wäre, und ich eh schon Probleme hab unter 20 Seiten zu bleiben. Ist die Rechnung ohne Polynomrechnung möglich ???
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:35 Sa 06.11.2010 | | Autor: | felixf |
Moin!
> Vielen Dank für die genaue Aufstellung. So hab ich
> rausgefunden, dass es bei mir schon beim inversen Element
> scheitert.
> Ich hab zuerst 85 ins Dezimalsystem umgerechnet =133 und
> dann das Inverse Element modulo 256 gesucht, was bei mir 77
> war.
Das ist auch das falsche Inverse berechnen. Du invertierst in [mm] $\IZ/2^8\IZ$, [/mm] nicht in [mm] $GF(2^8)$.
[/mm]
> Ich hab bis jetzt versucht immer um das Galois-Feld
> rumzuarbeiten, da ich denke, dass das für ne Facharbeit
> ein Overkill wäre, und ich eh schon Probleme hab unter 20
> Seiten zu bleiben. Ist die Rechnung ohne Polynomrechnung
> möglich ???
Du kannt es mit dem kleinen Satz von Fermat machen [mm] ($x^{-1} [/mm] = [mm] x^{255}$ [/mm] in [mm] $GF(2^8)$), [/mm] dann musst du jedoch modular exponentieren, also hast du wieder Polynomrechnung.
Um die Polynomrechnung wirst du wohl nicht herumkommen. Es sei denn, du gibst einfach eine Wertetabelle dafuer an. Aber ob das erwuenscht ist, ist eine andere Frage...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:48 So 07.11.2010 | | Autor: | Lybius |
Mmmh, ja ,danke für deine Hilfe.
Ich les mir grad das Kapitel Galois-Körper durch.
Ich hab bloß das Gefühl, dass irgendwann meine Mathe Lehrerin nicht mehr durchblickt.
Vielen Dank für das Beispiel und Servus !!!!!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:21 So 07.11.2010 | | Autor: | Lybius |
Hab es übrigens jetzt geschafft, auf dein Ergebnis zu kommen. Bin dir sehr dankbar.
|
|
|
|
Es hat ja schon einen Grund warum die S-Boxen meist einfach als Tabelle angegeben werden, und in der Implementation auch einfach nur eine Tabelle benutzt wird.
