DES - Algorithmus

Mit dem Einsatz leistungsfähiger Computer in den Unternehmen brauchte man sichere Verfahren zur Datenübermittlung. Das sollte in chiffrierter Form erfolgen. Da keine geeigneten Verschlüsselungsverfahren vorhanden waren, drängten insbesondere die Banken auf die Entwicklung sicherer Verschlüsselungsalgorithmen.

Deshalb gab das National Bureau of Standards (NBS, heute NIST) den Anstoß zur Entwicklung eines einheitlichen und standardisierten Verschlüsselungsalgorithmus. Am 15. Mai 1973 veröffentlichte das NBS in einem Bundesanzeiger eine Ausschreibung:
Entwurf eines kryptographischen Algorithmus mit folgenden Anforderungen:

Der Algorithmus muss einen hohen Grad an Sicherheit gewährleisten.
Der Algorithmus muss vollständig spezifiziert und leicht nachzuvollziehen sein.
Die Sicherheit des Algorithmus muss auf dem Schlüssel beruhen, sie darf nicht von der Geheimhaltung des Algorithmus abhängen.
Der Algorithmus muss für alle Anwender zur Verfügung stehen.
Der Algorithmus muss an verschiedene Anwendungen angepasst werden können.
Der Algorithmus muss sich kostengünstig in elektronischen Komponenten implementieren lassen.
Der Algorithmus muss effizient in der Benutzung sein.
Es muss möglich sein, den Algorithmus zu validieren.
Der Algorithmus muss exportierbar sein.

Es gab genug Interesse, aber von allen eingereichten Algorithmen erfüllte keiner die Bedingungen auch nur annähernd. Am 27. August veröffentlichte das NBS eine zweite Ausschreibung. Ein Algorithmus mit der Bezeichnung Lucifer, der in den siebziger Jahren von Roy Adler, Don Coppersmith, Edna Grossman, Horst Feistel, Alan Konheim, Carl Meyer, Bill Notz, Lyn Smith, Walt Tuchman und Bryant Tuckerman bei IBM entwickelt wurde, kam in die nähere Auswahl und wurde von der NSA hinsichtlich seiner Sicherheit untersucht.

Die National Security Agency (NSA) ist das offizielle Sicherheitsorgan der US-Regierung. Hier werden unter anderem kryptographische Forschungen im nationalen Sicherheitsinteresse durchgeführt. Das NSA ist der weltweit größte Arbeitgeber für Mathematiker und es besitzt die leistungsfähigsten Computer.

1975 wurde der Algorithmus im Bundesanzeiger veröffentlicht. Allgemein wurde kritisiert, dass die NSA die Schlüssellänge von ursprünglich 128 auf 56 Bit reduziert hatte. Trotz der Kritik wurde der Data Encryption Standard am 23. November 1976 als Bundesstandard angezeigt und zur Verwendung für alle nichtgeheimen Regierungsvorgänge freigegeben. Die offizielle Beschreibung des Verfahrens wurde im Januar 1977 veröffentlicht.

Der Data Encryption Standard ist eine Blockchiffrierung, denn es wird in Blöcken von 64 Bit chiffriert. Es ist ein symmetrisches Verfahren, da beim Chiffrieren und Dechiffrieren der gleiche Schlüssel benutzt wird. Das Verschlüsselungssystem besteht aus 16 Runden, eine Runde setzt sich aus der Kombination von Permutation und Substitution zusammen.

Der Klartext liegt als Strom von Binärzahlen vor. Dieser wird in Blöcke von 64 Bit verarbeitet. Der Block wird in einen linken Teil L_i und in einen rechten Teil R_i von je 32 Bit gespalten.

Der 56 Bit lange Schlüssel wird ebenfalls in einen linken und rechten Teil von je 28 Bit zerlegt. In jeder Runde wird jede Hälfte abhängig von der Rundenzahl um 1 oder 2 Bit rotiert, das heißt, alle Bits wandern um 1 oder 2 Stellen nach rechts, danach werden beide Teile wieder zusammengefasst. Dieser Schlüssel wird in der Kompressionspermutation(K) auf 48 Bit reduziert, dadurch kommt in jeder Runde ein anderer Schlüssel zum Einsatz.

Der rechte Teilblock R_i muss nun auch auf 48 Bit erweitert werden, damit er mit dem Schlüssel per XOR verknüpft werden kann. Das geschieht, indem jedes 4. und darauf folgende Bit in der Expansionspermutation(E) wiederholt wird. Nach der XOR-Operation wird in den acht Substitions-Box(S) das Ergebnis auf 32 Bit transformiert. Eine S-Box besteht aus einer Tabelle mit 4 Zeilen und 16 Spalten. In der Permutationsbox(P) wird die Reihenfolge der einzelnen Bits geändert. Schließlich wird der entstandene Block mit dem linken Teilblock L_i per XOR verknüpft, daraus ergibt sich der rechte Teilblock für die nächste Runde R_i+1. Der linke Teilblock L_i+1 ergibt sich aus R_i.

Insgesamt werden alle Bits des Klartextblockes mit den Bits des Schlüssels in jeder Runde scheinbar chaotisch vermischt. Nach 16 Runden werden beide Teilblöcke wieder zusammengefügt und man erhält den Geheimtextblock. Beim Dechiffrieren wird der gleiche Schlüssel verwendet, das Schema jedoch in umgekehrter Reihenfolge durchlaufen.

Der DES war der erste Chiffrier-Algorithmus der Geschichte, der vollständig publiziert wurde. Ursprünglich sollte er nur in Hardware implementiert werden, es wurden aber viele der Einzelheiten des Verfahrens veröffentlicht, sodass auch Software entwickelt werden konnte.

Die Schlüssellänge beträgt 56 Bit. Das ergibt 2⁵⁶ = 7 * 10¹⁶(Billiarden) Möglichkeiten für den Schlüssel. Das Alphabet des monoalphabetischen Algorithmus besteht aus {(a₁,..., a₆₄) | a_i {0, 1}}.

Im Jahre 1993 konnte der DES mit einer 1 Mio. Dollar Maschine mittels Brute-Force Attacke in 3,5 h geknackt werden. Um das veraltete Verfahren jetzt zu knacken, bräuchte man mit einem Budget von 10 Billionen Dollar 1 Millisekunde.

| Hauptseite Proseminar | Katrin Mücke - Wirtschaftsinformatik 2000 |