RC5-Projekt

Wie funktioniert der RC5-Algorithmus?

Der RC5-Algorithmus ist ein sogenannter symmetrischer Blockchiffre. Hierbei wird der zu verschlüsselnde Klartext in gleich große Blöcke eingeteilt, von denen jeder einzelne mit dem Schlüssel chiffriert wird. Der Chiffretext kann mit dem gleichen Schlüssel auch wieder dechiffriert werden.

Der RC5-Chiffre kann in verschiedenen Varianten angewandt werden, die unterschiedliche Parameter besitzen. Ein bestimmter RC5 Algorithmus wird folgendermaßen angegeben:

RC5 – w / r / b

Die Parameter bedeuten im einzelnen:

w: Die Wortgröße, angegeben in Bits. Der Standardwert ist 32; gültige Werte sind 16, 32 und 64. Der RC5-Algorithmus verschlüsselt aber jeweils zwei-Wort-Blöcke, so dass Klartext- und verschlüsselte Textblöcke jeweils Vielfaches von 2w lang sind.

r: Die Anzahl der Runden, d. h. wie oft die Verschlüsselung durchgeführt wird. Gültige Werte hierfür sind 0, 1, ..., 255.

b: Die Anzahl von Bytes, die der geheime Schlüssel K. enthält. Gültige Werte sind wiederum 0, 1, ..., 255.

RC5 besteht im wesentlichen aus drei Komponenten: einem Schlüssel-Expansions-Algorithmus, einem Verschlüsselungs- und einem Entschlüsselungsalgorithmus.

Diese Algorithmen basieren alle auf den folgenden drei sehr einfachen Operationen (und ihren entsprechenden Umkehroperationen):

Die Addition von Worten modulo 2^w, im folgenden lediglich mit "+” bezeichnet.
Bitweises exklusives Oder von Worten, bezeichnet mit Å.
Bitrotationen: Die Rotation von x nach links um y Bits wird im folgenden mit x <<< y bezeichnet. Achtung: Eigentlich haben nur die log₂(w) unteren Bits von y Einfluß auf diese Rotation.

A) Die Schlüssel Expansion

Hier wird aus dem vom Benutzer des Algorithmus vorgegebenen Schlüssel K eine Schlüsseltabelle S erstellt. Diese Schlüsseltabelle besteht aus einem Feld von t = 2(r +1) binären "Zufallsworten”, die mit Hilfe des Schlüssels K erstellt wurden. Der Algorithmus macht sich zwei "magische Konstanten” zu Nutze und besteht aus drei einfachen Teilen.
Die zwei jeweils ein-Wort-großen magischen Konstanten sehen für eine festgelegte Wortgröße w wie folgt aus:

mit

e = 2,718281828459...        (Basis des natürlichen Logarithmus, Eulerzahl e)
j = 1,618033988749...        (Goldenes Verhältnis / Goldener Schnitt).

Odd(x) ist diejenige ungerade Ganzzahl, die am nächsten an x liegt. Sollte x eine gerade Ganzzahl sein, so wird sie aufgerundet. Dies kann aber hier normalerweise nicht passieren, da sowohl e als auch j irrationale Zahlen sind.

Bevor mit dem Aufbau der Schlüsseltabelle begonnen werden kann, müssen die Schlüsselbytes jeweils so zusammengefaßt werden, dass sie Wortgröße ergeben, d. h. die neuen Schlüssel sind jeweils so groß wie ein Wort. Dazu werden die geheimen Schlüsselbytes K[0, ..., b-1] in ein Feld L[0, ..., c-1] kopiert, wobei c = [b/u] ist, und u = w/8 der Anzahl der Bytes pro Wort entspricht. Dies geschieht ganz natürlich, indem einfach u aufeinanderfolgende Schlüsselbytes in ein Wort L eingetragen werden, zunächst die niederwertigen, dann die höherwertigen Bytes. Jede unaufgefüllte Byte-Position in L wird vernullt. Für den Fall, dass b = c = 0 gilt, wird c auf 1 gesetzt und L[0] auf Null.

Beispiel:

Eintragung der 8 Schlüsselbytes K[0] bis K[7] in die beiden Wort-Felder L[0] und L[1] bei einer Schlüssellänge von 64 Bit (= 8 Byte = b) und einer Wortlänge w von 32 Bit (= 4 Byte).

Der nächste Schritt der Schlüsselexpansion initialisiert das Schlüsselfeld S auf von der Wortlänge abhängige, vom Schlüssel jedoch unabhängige, Pseudo-Zufallswerte. Hierbei werden jeweils die magischen Konstanten P_w und Q_w addiert, anschließend wird ein Modulo 2^w durchgeführt, damit der Wert nicht größer als eine Wortlänge werden kann. Da die beiden Werte ungerade sind, hat dieser Prozeß eine Periode von 2^w.

        S[0]=P_w;
        for i=1 to t-1 do
         S[i] = S[i-1] + Q_w;

Der dritte Schritt des Algorithmus bringt nun den geheimen Schlüssel des Benutzers in Spiel. Hier werden nämlich die beiden Felder S und L miteinander vermischt, sogar dreimal. Genauer gesagt: Das größere der beiden Felder wird dreimal neu beschrieben, das andere sogar noch öfter.

        i = j = 0;
        A = B = 0;
        do 3 * max(t,c) times:
         A = S[i] = (S[i] + A + B) <<< 3;
         B = L[j] = (L[j] + A + B) <<< (A + B);
         i = (i + 1) mod t;
         i = (i + 1) mod t;
         j = (j + 1) mod c;

Die Schlüsseltabelle muß dreimal neu beschrieben werden, da sonst der geheime Schlüssel keinen Einfluß auf alle Elemente dieser Tabelle haben kann. Das erste Element S[0] der Tabelle wird beim ersten Durchlauf lediglich um drei Bits nach links rotiert. Erst beim zweiten Durchlauf kommt durch den Block B der geheime Schlüssel ins Spiel.
Wie man sieht, ist die Schlüsselexpansion in gewisser Weise eine "Einwegfunktion”, da sich aus der Kenntnis von S nicht so einfach auf den Schlüssel K schließen läßt.

B) Verschlüsselung

Der folgende Pseudocode soll den Verschlüsselungsalgorithmus darstellen. Hierbei wird angenommen, dass der zu verschlüsselnde Eingabeblock in den beiden w-Bit-Registern A und B übergeben wird. Der Ausgabeblock wird ebenfalls in diesen beiden Registern abgelegt.

        A = A + S[0]
        B = B + S[1]
        for i = 1 to r do
         A = ((A Å B) <<< B) + S[2i]
         B = ((B Å A) <<< A) + S[2i+1]

oder grafisch:

Diese Schritte werden in jeder Runde durchgeführt, wobei die Ausgabe einer Runde als Eingabe der nächsten Runde verwendet wird. Die einzelnen Blöcke werden also mehrfach chiffriert.

C) Entschlüsselung

Die Entschlüsselung erfolgt genauso wie die Verschlüsselung, nur werden jeweils die Umkehrfunktionen verwendet. Außerdem werden diese in umgekehrter Reihenfolge durchgeführt:

        for i = r downto 1 do
         A = ((A - S[2i]) >>> B) Å B
         B = ((B - S[2i+1]) >>> A) Å A
        A = A - S[0]
        B = B - S[1]

Zurück zum Inhaltsverzeichnis