Am 15 Mai 1973 rief das NBS (National Bureau of Standards, heute NIST - National Institute of Standards and Technologygenannt) im Federal Register (das amerikanische Bundeszentralregister ) zur Erzeugung eines Chiffrier-Algorithmus' auf, der den folgenden Kriterien entspricht :
Ende 1974 schlug IBM « Lucifer » vor, der am 23 November 1976 von der NSA (National Security Agency) verändert wird, daraus entsteht der DES (Data Encryption Standard). Der DES wurde 1978 endgültig von der NBS anerkannt. Der DES wurde vom ANSI (American National Standard Institute) unter dem Namen ANSI X3.92, besser bekannt unter dem Namen DEA (Data Encryption Algorithm) standardisiert.
Es handelt sich um ein symmetrisches Chiffrier-System mit Blocks von 64 Bits, davon dienen 8 Bits (ein Byte) als Paritätstest (um die Integrität des Schlüssels zu überprüfen). Jedes Paritätsbit des Schlüssels (1 alle 8 Bits) dient dazu, eines der Bytes des Schlüssels durch ungerade Parität zu testen, das heißt, jedes Paritätsbit ist so gewählt, dass eine ungerade Anzahl an Einsen im zugehörigen Byte steht. Der Schlüssel hat daher eine « effektive » Länge von 56 Bits, das bedeutet, dass nur 56 Bits im Algorithmus wirklich genutzt werden.
Der Algorithmus besteht darin, Kombinationen, Substitutionen und Permutationen zwischen dem zu chiffrierenden Text und dem Schlüssel auszuführen, während darauf geachtet wird, dass die Operationen in beide Richtungen ausgeführt werden können (für die Dechiffrierung). Die Kombination von Substitutionen und Permutationen heißt Produktchiffre .
Der Schlüssel ist auf 64 Bits codiert und besteht aus 16 Blocks von 4 Bits, meist bezeichnet als k1 bis k16. Da « nur » 56 Bits effektiv zum Chiffrieren genutzt werden, gibt es 2 56 (oder 7.2*1016) verschiedene mögliche Schlüssel !
Die wichtigsten Teile des Algorithmus sind die folgenden :
Zuerst wird jedes Bit eines Blocks der Anfangs-Permutation unterzogen, die durch die folgende Anfangs-Permutations-Matrix dargestellt werden kann :
| PI |
|
Durchläuft man die Matrix von links nach rechts und dann von oben nach unten, gibt sie an, dass das 58te Bit des Textblocks von 64 Bits sich an der ersten Stelle befindet, das 50te an zweiter Stelle, und so weiter.
Une fois la permutation initiale réalisée, le bloc de 64 bits est scindé en deux blocs de 32 bits, notés respectivement G et D (pour gauche et droite, la notation anglo-saxonne étant L et R pour Left and Right). Den ursprünglichen Zustand dieser beiden Blocks bezeichnet man mitL0 undR0.
| L0 |
|
| R0 |
|
Es ist interessant, festzustellen, dass L0 alle Bits enthält, die eine gerade Position in der ursprünglichen Nachricht einnehmen, währendR0 die Bits mit ungerader Position enthält.
Die BlocksLn undRn durchlaufen eine Anzahl an iterativen Transformationen, genanntRunden, dargestellt in diesem Diagramm, deren Details weiter unten geliefert werden :
Die 32 Bits des BlocksR0 werden auf 48 Bits aufgeteil, dies geschieht durch eine Tabelle (Matrix), genanntExpansionstabelle (notiertE), in der die 48 Bits vermischt werden und 16 davon verdoppelt werden :
| E |
|
So wird das letzte Bit vonR0 (also das 7te
Bit des Anfangsblocks) zum ersten, das erste wird zum zweiten, ...
Außerdem werden die Bits 1,4,5,8,9,12,13,16,17,20,21,24,25,28 und 29 vonR0 (also
57, 33, 25, l, 59, 35, 27, 3, 6l, 37, 29, 5, 63, 39, 31 und 7 des Anfangsblocks) verdoppelt und
in der Matrix verteilt.
Die entstandene Matrix von 48 Bits wirdR'0 oderE[R0] genannt. Danach führt der DES-Algorithmus einexklusives ODER zwischen dem ersten SchlüsselK1und E[R0] aus. Das Ergebnis dieses exklusiven ODERs ist eine 48 Bit-Matrix, die wir aus Bequemlichkeit alsR0 bezeichnen (es handelt sich aber nicht um das D0 vom Anfang!).
R0 wird danach in 8 Blocks mit jeweils 6 Bits zerteilt, notiert alsR0i.
Jeder dieser Blocks durchläuft Selektionsfunktionen (manchmal
Substitutions-Boxen oderKompressionsfunktionengenannt), die meist folgendermaßen angeschrieben werdenSi.
Die ersten und letzten Bits jedes R0i bestimmten (in Binärform) die Zeile der
Selektionsfunktion, die anderen Bits (nacheinander 2, 3, 4 und 5) bestimmen die Spalte. Die Selektion
der Linie erfolgt auf zwei Bits, daher gibt es 4 Möglichkeiten (0,1,2,3). Die Selektion der Spalte
erfolgt auf 4 Bits, daher gibt es 15 Möglichkeiten (0 bis 15). Mit diesen Informationen
"selektiert" die Selektionsfunktion einen auf 4 Bits codierten Wert.
Dies ist die erste Substitutionsfunktion, dargestellt durch eine 4 mal 16-Matrix :
| S1 |
|
Angenommen,R01 hat den Wert101110. Die ersten und letzten Bits ergeben 10, also 2 in Binärform. Die Bits 2,3,4 und 5 ergeben 0111, also 7 in Binärform. Das Ergebnis der Selektionsfunktion ist daher der Wert aus der Zeile n°2, in der Spalte n°7. Dies ist der Wert 11, oder in Binärform111.
Jeder der 8 Blocks von 6 Bits durchläuft die entsprechende Selektionsfunktion, daraus ergeben sich 8 Werte mit jeweils 4 Bits. Dies sind die anderen Wahlfunktionen :
| S2 |
|
| S3 |
|
| S4 |
|
| S5 |
|
| S6 |
|
| S7 |
|
| S8 |
|
Jeder Block von 6 Bits wird so durch einen Block mit 4 Bits ersetzt. Diese Bits werden neu gruppiert, um einen Block von 32 Bits zu bilden.
Der erhaltene 32 Bit-Block wird dann einer Permutation P unterzogen, dessen Tabelle hier aufgeführt ist :
| P |
|
Die gesamten ausgegebenen Ergebnisse von P werden einemExklusiven ODER unterzogen, mit dem anfänglichem L0 (wie im ersten Diagramm angegeben) um R1 zu ergeben, während das ursprüngliche R0 zuG1 führt.
Alle vorherigen Schritte (Runden) werden 16 Mal wiederholt.
Am Schluss der Iterationen werden die zwei BlocksL16 undR16 wider zusammengefügt, und dann der inversen Anfangs-Permutation unterzogen :
| PI-1 |
|
Das Ausgabeergebis ist ein codierter Text von 64 Bits !
Da der unten vorgestellte DES-Algorithmus öffentlich ist, beruht die Sicherheit allein auf der Komplexität der Chiffrier-Schlüssel.
Dieser Algorithmus veranschaulicht, wie man, ausgehend von einem Schlüssel mit 64 Bits (der aus 64 beliebigen alphanumerischen Zeichen besteht), 8 verschiedene Schlüssel mit jeweils 48 Bits erhält, die alle im DES-Algorithmus genutzt werden :
Zuerst werden die Paritätsbits des Schlüssels eliminiert, um zu einem Schlüssel mit einer effektiven Länge von 56 Bits zu gelangen.
Der erste Schritt beinhaltet eine Permutation, die CP-1 genannt ist, deren Matrix sieht folgendermaßen aus :
| CP-1 |
|
Diese Matrix kann in der Form von zwei Matrizen notiert werden, LiundRi (für rechts und links), von denen jede aus 28 Bits besteht :
| Li |
|
| Ri |
|
Das Ergebnis dieser ersten Permutation wird alsL0 undR0 bezeichnet.
Danach unterliegen diese beiden Blocks einer Linksrotierung, so, dass die Bits an zweiter
Stelle die erste Stelle einnehmen, die in dritter Stelle die zweite,...
Die Bits an erster Stelle werden an die letzte Stelle gereiht.
Die 2 Blocks von 28 Bits werden dann zu einem Block von 56 Bits zusammengefasst. Dieser wird einer Permutation unterzogen, die alsCP-2 bezeichnet wird, sie liefert einen Block von 48 Bits, der dem Schlüssel Ki enspricht.
| CP-2 |
|
Durch die Iterationen des Algorithmus erhält man die 16 Schlüssel K1 bisK16, die im DES-Algorithmus verwendet werden.
| LS |
|
1990 entwickelten Eli Biham und Adi Shamir die differentielle Kryptoanalyse, Klartextpaare und Chiffre-Textpaare sucht. Diese Methode funktioniert bei einer Rundenanzahl von 15 oder weniger, daher enthält der unten vorgestellte Algorithmus 16 Runden.
Aber auch wenn ein ein Schlüssel von 56 Bits eine enorme Anzahl an Möglichkeiten ergibt, sind viele Rechner im Stande, über 106 Schlüssel pro Sekunde zu berechnen, so ist es für ein großes Organ (ein Staat zum Beispiel) möglich, den richtigen Schlüssel zu finden, indem man mehrere Rechner zur selben Zeit laufen lässt...
Eine kurzfristige Lösung besteht darin, drei DES- Chriffierungen durch zwei 56 Bit-Schlüssel zu verketten (entspricht einem 112 Bit-Schlüssel). Diese Prozedur nennt manTriple DES, geschriebenTDES (manchmal3DES oder3-DES).
DurchTDES lässt sich die Sicherheit von DES signifikant erhöhen, es hat allerdings den großen Nachteil, dass auch mehr Ressourcen zum Chiffrieren und Dechiffrieren nötig sind.
Man unterscheidet drei Arten der Triple DES-Chiffrierung :
1997 wurde vomNIST ein neuer Aufruf gestartet, zur Entwicklung desAES (Advanced Encryption Standard), ein Chiffrierungs-Algorithmus, der den DES ersetzen soll.
Das Chiffrier-SystemDES wurde alle 5 Jahre erneuert. Bei der letzten Revision im Jahr 2000 wurde nach einem 3-jährigem Evaluationsprozess, ein Algorithmus, der zusammen von zwei belgischen Kandidaten, Vincent RijmenundJoan Daemen entwickelt wurde, von derNIST zum neuen Standard gewählt. Dieser neue Algorithmus mit dem NamenRIJNDAEL wird künftig den DES ersetzen.
