zurück
weiter
MARS
Auch
IBM nahm mit seiner Chiffre MARS an der Ausschreibung
zum AES teil. In der Runde der letzten Fünf belegte MARS
den letzten Platz.
MARS
bietet Schlüssellängen von 128 bis 448 Bit, wobei die
Schlüssellänge ein Vielfaches von 32 Bit sein muss. Die
Blocklänge beträgt 128 Bit und die Standardrundenzahl
beträgt 32.
Der
128-Bit-Textblock wird in vier Worte – D[0], D[1], D[2]
und D[3] – à 32 Bit aufgeteilt. Diese vier Worte
durchlaufen drei Phasen des Algorithmus. In der ersten
Phase werden die Worte D[0] bis D[3] zunächst mit je
einem 32-Bit-Teilschlüssel K[i] modulo 232
addiert. Anschließend durchlaufen D[0] bis D[3] acht
Runden einer schlüssellosen Vermischung der Daten. Diese
Phase wird als „forward mixing“ bezeichnet. Danach
beginnt die Phase 2 des Algorithmus. Die Worte D[0] bis
D[3] werden acht Runden einer Transformation, die als
„forward transformation“ bezeichnet ist, unter
Einbeziehung der Teilschlüssel K[i] unterzogen.
Anschließend durchlaufen die vier Worte acht Runden
einer Transformation, die als „backwards transformation“
bezeichnet ist und ebenfalls unter Einbeziehung der
Teilschlüssel K[i] durchgeführt wird. Diese 16 Runden
der Transformation und Rückwärtstransformation werden
als der kryptographische Kern der Chiffre bezeichnet.
Danach beginnt die dritte Phase des Algorithmus, die als
„backwards mixing“ bezeichnet ist. Die Worte D[0] bis
D[3] werden in acht Runden einer schlüssellosen
Rückwärtsvermischung bearbeitet. Abschließend wird von
jedem der Worte je ein Teilschlüssel K[i] modulo 232
abgezogen. Die Struktur von MARS ist im folgenden Bild
dargestellt.
Nun
wird Phase 1 des Algorithmus genauer betrachtet. Nach
der Addition der Teilschlüssel K[i] wird in jeder Runde
ein Wort D[j] als Input für die S-Boxen S0 und S1
genutzt, die anderen drei Worte werden anschließend
durch die Outputs der S-Boxen modifiziert. Die S-Boxen
besitzen 256 Einträge der Größe 32 Bit, die durch einen
8-Bit-Input ausgewählt werden. Hierzu wird das jeweilige
Wort D[j] in seine vier Bytes unterteilt, die mit b0,
b1, b2 und b3 bezeichnet sind. Das niedrigstwertige Byte
wird hierbei durch b0 repräsentiert. Die Bytes b0 und b2
dienen als Input für die S-Box S0 und die Bytes b1 und
b3 dienen als Input für die S-Box S1. Die S-Boxen können
frei definiert werden und werden durch einen
pseudozufälligen Algorithmus generiert, bei dem der
SHA-1, ein Hashalgorithmus, eingesetzt wird.
In
der ersten Runde dient D[0] als Input für die S-Boxen.
Zunächst wird D[1] mit S0[b0] XOR-verknüpft und dann
wird S1[b1] zu diesem Ergebnis modulo 232
hinzu addiert. Zu D[2] wird S0[b2] modulo 232
addiert und D[3] wird mit S1[b3] XOR-verknüpft.
Abschließend rotiert D[0] um 24 Positionen nach rechts.
Die
nächste Runde wird nach dem gleichen Schema
durchgeführt, nachdem die vier Worte um eine Position
nach rechts rotiert sind (z.B. (D[3],D[2],D[1],D[0]) ®
(D[0],D[3],D[2],D[1])). In den Runden, in denen D[0]
oder D[1] als Input dienen, wird nach der Rotation D[3]
bzw. D[2] zu D[0] bzw. D[1] modulo 232
addiert. Die im Bild dargestellte Struktur wird zweimal
durchlaufen, so dass sich acht Runden ergeben.
Die
Phase 2 des Algorithmus wird als der kryptographische
Kern bezeichnet. Hauptbestandteil dieser Phase ist die
Funktion E. Diese verarbeitet ein 32-Bit-Inputwort und
produziert drei 32-Bit-Outputworte. Ein Datenwort D[j]
dient in jeder Runde als Input für die Funktion E, die
anderen drei Worte werden durch den Output entweder
mittels Addition modulo 232 oder
XOR-Verknüpfung modifiziert. Anschließend rotiert das
Datenwort, das als Input diente, um 13 Positionen nach
links. Der „forward mode“ und der „backwards mode“
unterscheiden sich nur durch die Zuordnung zu den
einzelnen Datenworten, wie im folgenden Bild gezeigt.
In
der Funktion E werden drei temporäre Variablen benutzt,
die als L, M und R bezeichnet sind und die Länge 32 Bit
haben. Die Variable R wird gleich dem Ergebnis der
Linksrotation um 13 Positionen des Inputs gesetzt und M
wird gleich dem Ergebnis der Addition modulo 232
vom Input und einem Teilschlüssel K[i] gesetzt. Nun
werden die neun niedrigstwertigen Bits von M als Input
einer S-Box genutzt, die 512 Einträge besitzt und aus
der Verkettung der S-Boxen S0 und S1 aus der
„mixing“-Runde entsteht. Der Output dieser S-Box wird in
L gespeichert. Des Weiteren wird R mit einem zweiten
Teilschlüssel K’[i] modulo 232 multipliziert,
wobei der Teilschlüssel eine ungerade ganze Zahl sein
muss. Anschließend rotiert R um 5 Positionen nach links
und wird mit L XOR-verknüpft. Nun rotiert M um den
Inhalt der fünf niedrigstwertigen Bits von R. R rotiert
anschließend nochmals um 5 Positionen nach links und
wird wiederum mit L XOR-verknüpft. Abschließend rotiert
L um den Inhalt der fünf niedrigstwertigen Bits von R
nach links. Nun entspricht L dem Output 1, M dem Output
2 und R dem Output 3. Die beschriebenen Vorgänge zeigt
das folgende Bild.
Phase
3, das sogenannte „backwards mixing“ läuft nach sehr
ähnlichem Schema wie Phase 1 ab. Die Unterschiede
bestehen in der Zuordnung der einzelnen Bytes zu den
S-Boxen und die Addition modulo 232 wurde
durch eine Subtraktion modulo 232 ersetzt. Zu
Beginn wird D[1] mit S1[b0] XOR-verknüpft und S0[b3] von
D[2] modulo 232 subtrahiert. Dann wird S1[b2]
von D[3] modulo 232 subtrahiert und S0[b1]
mit dem Ergebnis XOR-verknüpft. Abschließend werden die
vier Worte D[j] einer Subtraktion von je einem
Teilschlüssel unterzogen. Sind D[1] bzw. D[3] die
Inputworte, so werden zu Beginn die Inhalte von D[1] bei
D[2] bzw. D[0] bei D[3] subtrahiert.
Für
den gesamten Algorithmus werden 40 Teilschlüssel
benötig, die in einem Feld K[0] bis K[39] gespeichert
werden. Die Länge des geheimen Schlüssels wird in Bit
dividiert durch 32 angegeben. Demnach ist bei einem
Schlüssel der Länge 128 Bit n = 4. Zur Generierung der
Teilschlüssel K[0] bis K[39] wird zunächst ein
temporäres Feld T mit 15 Einträgen der Größe 32 Bit
gebildet. Diese Einträge werden von T[0] bis T[n – 1]
gleich dem geheimen Schlüssel gesetzt. T[n] wird gleich
n gesetzt und T[n + 1] bis T[14] wird mit Nullen
gefüllt. Anschließend werden vier Runden , die aus
XOR-Verknüpfungen und Rotationen bestehen. Die
Teilschlüssel K[i] werden hierbei den Einträgen von T
zugeordnet. Abschließend müssen die Teilschlüssel, die
zur Multiplikation genutzt werden, folgende
Anforderungen erfüllen:
Um
die erste Voraussetzung zu erfüllen, werden einfach die
zwei niedrigstwertigen Bits ausgelesen und anschließend
per ODER-Verknüpfung zu ´1´ gesetzt. Hat das so
entstandene Wort w 10 oder mehr aufeinander folgende
Nullen oder Einsen, so wird eine Maske M erzeugt. In M
werden zunächst alle Stellen zu ´1´ gesetzt, an denen in
w ein „run“ – so nennt man eine Abfolge von gleichen
Zeichen – von Nullen oder Einsen steht. Anschließend
werden das höchstwertige Bit, die beiden
niedrigstwertigen Bits und das erste und letzte Bit des
jeweiligen „runs“ zu Null gesetzt. So entsteht z.B. aus
einem Wort w = 031130121011
die Maske M = 041110011005,
wobei die hochgestellten Zahlen die Wiederholungen des
jeweiligen Zeichens angeben. Anschließend wird mit Hilfe
der ausgelesenen zwei niedrigstwertigen Bits des
ursprünglichen Wortes einer der Einträge 265 bis 268 der
S-Box ausgewählt. Dieser Eintrag rotiert um den Inhalt
der fünf niedrigstwertigen Bits des letzten
Teilschlüssels K[i – 1] nach links und wird mit der
Maske UND-verknüpft. Dieses Ergebnis wird mit dem Wort w
XOR-verknüpft und man erhält den Teilschlüssel K[i].
Man
glaubt, dass die Ver- und Entschlüsselung bei MARS
gleichwertige Stärke besitzen, da beim Design der
Chiffre auf größtmögliche Symmetrie geachtet wurde. Die
Einschränkung der möglichen Teilschlüssel zur
Multiplikation soll schwache Teilschlüssel verhindern
und trotzdem möglichst zufällig ermittelte Teilschlüssel
bieten.
zurück
weiter
|