serious-cool

Der folgende Beitrag soll Euch erklären wie die DES Chiffre funktioniert. Um alles nachvollziehen zu können sollte euch die Modulus Arithmetik geläufig sein.

DES gehört zur Kategorie der Feistel Blockchiffren mit einem Schlüsselraum von 56 Bit. Die Grundlage dieser Verschlüsselung ist eine Kombination aus Diffusion und Konfusion

Übersicht DES

DES verwendet einen symmetrischen Algorithmus mit 16 Runden. Die Ver- und Entschlüsselung unterscheidet sich hierbei quasi nur in der Reihenfolge der Schlüssel (Unterschlüssel).

Input : 64 Bit vom Klartext + 56 Bit Schlüssel Output: 64 Bit Chiffrat.

Die Folgende Graphik verdeutlicht den runden-basierenden Durchlauf der Chiffrierung:

Wir erkennen sofort dass der Klartext nach der initialen Permutation in 2 32 Bit Blöcke aufgeteilt wird. Dabei wird immer nur ein Block pro Runde verschlüsselt. Diese Verhalten ist charakteristisch für Feistel-Netzwerke. Mathematisch kann man die Runden als L i = R i-1; i = {1,2,...,16} R i = L i-1 XOR F(R i-1, K i) darstellen.

Bei der Initialen und Finalen Permutation handelt es sich um eine ,,bitweise'' Permutation. Sozusagen macht die Finale Permutation die Initiale rückgängig, bzw. invertiert diese.

An dieser Stelle möchte ich die weiteren Abkürzungen noch kurz erläutern, wir werden später im Text sehen was es Damit auf sich hat:

F: wird schlicht F-Funktion genannt.

PC 1: Permuted Choice

T: Schlüsselrunde

XOR: Mathematische Operation XOR (bitweise Addition 1+1=0; 0+0=0; 0+1=1).

Eine Runde:

Die Rechte Hälfte der 64 Bit (R0) werden zunächst in den nachfolgenden Linken Block (L1) kopiert. Danach wird der Block R0 bei der F Funktion mit einem 48 Bit langem Unterschlüssel K1 versehen, wie das funktioniert steht unter ,,F - Funktion" und letztlich wird noch der linke 32 Bit Block L0 XOR addiert. So erhält man das neue R1. DIe erste Runde ist damit Fertig und das Ganze beginnt von vorne.

Die F - Funktion

1. Schritt : Expansion

Der 32 bit Input wird auf 48 bit expandiert. Danach kommen 16 der 32 Bit doppelt vor. Später werden diese 48 Bit in 8 6 Bit Blöcke unterteilt, dabei ist es wichtig dass bei der Expansion kein Bit im selben 6 bit Block verdoppelt wird. Dieser Schritt erfüllt die Diffusion.

2. Schritt: XOR

Der 48 Bit Unterschlüssel Ki wird XOR addiert.

3.Schritt: Substitution

Die 8 6 Bit Blöcke werden auf einen 4 bit Output Substituiert. Dies erfolgt mit 8 verschiedenen ,,S-Boxen" diese sind Teil der Spezifikation von DES und sind so gewählt dass lineare und differenzielle Kryptoanalyse nicht greifen.

4. Schritt Permutation

Der 32 Bit Output der 8 S-Boxen wird bitweise Permutiert Dies stellt sicher dass in der nächsten Runde wieder 6 verschiedene S-Box inputs zur Verfügung stehen. Nach Ende der 5.Runde ist jedes Bit eine Funktion aus jedem Klartext- und jedem Schlüsselbit.

Für den Fall dass Ihr euch die S-Boxen genauer ansehen wollt:

Schüsselfahrplan ,,Key Shadule"

PC 1: Permuted Choice lässt jedes 8. Bit fallen und permutiert das Ergebnis. Die Unterschlüssel Ki sind somit lediglich Permutationen des Schlüssels K

LS: Left Shift, rotiert die Bits nach links. in Runde 1,2,9,16 wird um 2 Bit rotiert in allen anderen Runden um 1 Bit. Also sind C16/D16 relativ zu C0/D0 um 28Bit rotiert. Dieses Verhalten wird für die Dechiffrierung interessant.

DES Dechiffrierung

Ziel: In der ersten Runde der Dechiffrierung wird die letzte Runde der Chiffrierung rückgängig gemacht. Runde eins der Dechiffrierung invertiert Runde 16 der Chiffrierung, der Schlüsselfahrplan ist dabei ebenfalls invertiert. Hier machen wir es uns zu Nutze das C16/D16 gleich C0/D0 ist. Allgemein verwenden Feist-Chiffren zum ver- und entschlüsseln den gleichen Algorithmus.

Sicherheit:

Mathematische Kryptoanalyse:

Beste Attacke benötigt 2^43 X,Y Paare die auch speziell für die lineare Kryptoanalyse gewählt sein müssen.

Brute Force

Schlüsselraum 56 Bit also 2^56 Möglichkeiten. Mit dem Heim PC in ca. 500 Jahren, mit spezial Hardware 6 Tage im Schnitt. siehe dazu COPACOBANA

Sichere Alternative

3DES bietet einen effektive Schlüssellänge von 112 Bit bei dem Nachteil dass die allgemein schlechte Software Implementierung von DES auch noch 3 mal ausgeführt werden muss. Effektiv wird hierbei mit 3 verschiedenen Schlüssel 3 mal mit DES verschlüsselt.