Data Encryption Standard - Eine erste moderne Chiffre auf Basis des Dualsystems


Facharbeit (Schule), 2010

22 Seiten, Note: 1,0

Christian Sperber (Autor)


Leseprobe

Inhaltsverzeichnis

1 Geschichtlicher Hintergrund und Grundlagen
1.1 Entstehung und Entwicklung des DES
1.2 Klärung grundlegender Begriffe und Ideen der Kryptologie
1.2.1 Symmetrische Chiffren
1.2.2 Blockchiffren
1.2.3 Exclusive Or (XOR)

2 Erklärung der Funktionsweise des DES-Algorithmus
2.1 Überblick über die Funktionsweise
2.2 Eingangs- und Ausgangspermutation
2.3 Der Algorithmus f
2.4 Schlüsselgenerierung durch Shift-Operationen
2.5 Dechiffrierung

3 Betriebsmodi von Blockchiffren
3.1 Electronic Codebook Modus (ECB)
3.2 Cipher Block Chaining Modus (CBC)
3.3 Cipher Feedback Modus (CFB)
3.4 Output Feedback Modus (OFB)
3.5 TripleDES

4 Sicherheit von DES
4.1 Eigenschaften des DES
4.1.1 S-Boxen
4.1.2 Lawineneffekt
4.1.3 Schwache Schlüssel
4.2 Der Brute Force Angriff
4.3 Mittel der differentiellen Kryptoanalyse
4.4 Die lineare Kryptoanalyse
4.5 Laufzeitabschätzungen

5 Anwendung heute
5.1 Verschlüsselung im Internet
5.2 Finanzwesen

6 Der Nachfolger AES

7 Abkürzungsverzeichnis

8 Literaturangaben
8.1 Literaturquellen
8.2 Internetquellen
8.3 Bildquellen

9 Anhang
9.1 Permutationstabellen
9.2 S-Boxen

1 Geschichtlicher Hintergrund und Grundlagen

Der Data Encryption Standard (DES) war 20 Jahre lang der weltweite Standard für die Ver­schlüsselung von Daten in der Informationstechnologie und ist wohl der wichtigste Vertreter der sogenannten symmetrischen Blockchiffren. Er galt lange Zeit als äußert sicher, ist aber heute aufgrund der kleinen Schlüssellänge mit der entsprechenden Rechenkapazität leicht zu brechen.

1.1 Entstehung und Entwicklung des DES

Vor den 1970ern hatte das Thema Kryptologie in der Öffentlichkeit noch kaum Bedeutung, lediglich das Militär bemühte sich, seine Kommunikation zu verschlüsseln. Erst mit dem Aufkommen der Informationstechnologie wuchs auch bei Unternehmen und staatlichen In­stitutionen der Bedarf an einer sicheren, codierten Datenübertragung.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1 Horst Feistel

Das erkannte auch das National Bureau of Standards (NBS).[1] der USA und veröffentlichte im Mai 1973 eine Ausschreibung im Federal Register der USA. Gesucht wurde hierbei ein geeigneter Verschlüsselungsalgorithmus. Da auf diese Einschreibung kein einziger Vorschlag einging, der die Sicherheitskriterien erfüllte, folgte ein Jahr später eine zweite Ausschreibung, auf die ein Team von IBM nun einen Vorschlag einreichen konnte. Das Projekt ba­sierte auf dem Algorithmus Lucifer des in Deutschland geborenen Horst Feistel. Es wurde schließlich der National Security Agency (NSA) zur Beurteilung der Sicherheit übergeben.

Nach der Veröffentlichung im Jahr 1975 wurde der Algorithmus am 23. November 1976 unter dem Namen Data Encryption Standard schließlich zum amerikanischen Standard er- klärt[2] In den folgenden Jahren (1980-1986) wurden weitere Standards bezüglich der Be­triebsmodi, der Implementierung des DES, oder des Einsatz in der Finanzindustrie definiert (Näheres bei Schneier: Kryptographie, S. 311). Der Standard wurde „(trotz Exportbeschrän­kungen) weltweit [...] zum Marktführer." (Bauer: Geheimnisse, S.173)

In der Öffentlichkeit regte sich währenddessen scharfe Kritik an der unklaren Rolle der NSA bei der Bearbeitung des Algorithmus. So soll auf Druck der Behörde die Schlüssellänge klein gehalten worden sein und auch die sicherheitsrelevanten S-Boxen wurden angeblich von der NSA verändert (Vgl. Wobst: Abenteuer, S. 125). Es wurde der Vorwurf laut, die Agency hätte sich Hintertürchen eingebaut, um selbst mit eigener Rechenkapazität codierte Texte entschlüsseln zu können. Die Veröffentlichung (also nicht nur die Implementierung in Hard­ware) des Algorithmus beruht wahrscheinlich sogar nur auf einem Missverständnis zwi­schen NBS und NSA, inoffiziell bezeichnete die NSA den DES als ihren größten Fehler (Vgl. Schneier: Kryptographie, S. 311). Es ist aber auch möglich, dass die NSA die S-Boxen verän­dert hat, um zu verhindern, dass IBM hier zum eigenem Vorteil eine Schwachstelle einbaut.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2 Logo der NSA

Nach der Entdeckung der differentiellen Kryptoanalyse (siehe Kap. 3.3) im Jahr 1990 durch Elie Biham und Adi Shamir wurde klar, dass die DES-Schöpfer diesen Angriff damals schon kannten, das Wissen um diesen Angriff aber geheim halten wolten und deshalb die Entwurfskri­terien der S-Boxen nicht preisgaben (siehe Kap. 4.3). Trotzdem bot der DES immer weniger Sicherheit. Aus Mangel an Alternativen jedoch wurde der Standard weiterhin vom NBS zertifiziert.

Der Algorithmus wurde 1994 dann erstmals innerhalb von 50 Tagen mit einem Rechnerver­bund per Brute Force (Durchprobieren aller möglichen Schlüssel; siehe Kap. 3.2) geknackt. Vier Jahre später benötigte man nur noch drei Tage und 1999 schließlich wurde der „bislang schnellste Angriff gegen DES" (Ertel: Kryptographie, S. 56 und S. 63, Stand: 2003) in 22 Stun­den durchgeführt, allerdings war hierfür auch ein Netzwerk aus etwa 100.000 PCs nötig.

Nach einer Entwicklungszeit von vier Jahren wurde 2001 der Data Encryption Standard vom Advanced Encryption Standard (AES) offiziell abgelöst. Auch der AES ist eine Blockchiffre, die per Ausschreibung gefunden wurde, er ist vor allem wegen der größeren Schlüssellänge sicherer. Doch der Umstieg auf den neuen Standard dauerte Jahre und noch heute wird DES vereinzelt eingesetzt.

1.2 Klärung grundlegender Begriffe und Ideen der Kryptologie

1.2.1 Symmetrische Chiffren

Grundsätzlich gibt es zwei Arten von Verschlüsselungsalgorithmen: Symmetrische und asymmetrische. Während bei der asymmetrischen Methode zwei Schlüssel benötigt werden, wird bei der symmetrischen Verschlüsselung zum Ver- und Entschlüsseln der gleiche

Schlüssel verwendet oder Chiffrierschlüssel und Dechiffrierschlüssel lassen sich leicht ausei­nander berechnen. Um eine geheime Nachrichtenübertragung zu ermöglichen, muss ein ge­meinsamer Schlüssel vereinbart und geheim gehalten werden.

1.2.2 Blockchiffren

Unter den symmetrischen Algorithmen gibt es Block- und Stromchiffren. Eine Stromchiffre verschlüsselt Informationen zeichenweise oder bitweise. Blockchiffren hingegen bearbeiten den Klartext in Bitgruppen, Blöcke genannt. Lässt sich der Klartext nicht genau in solche Blöcke aufteilen, so wird beim sogenannten Padding der letzte Block üblicherweise mit Zu­fallsbits aufgefüllt.

1.2.3 Exclusive Or (XOR)

Exclusive Or ist eine logische Operation, die zwei Bits miteinander verknüpft. Es gilt die Re­gel: Sind die Bits gleich, so ist das Ergebnis der Operation eine Null. Bei unterschiedlichen Bits hat XOR eine Eins als Ergebnis.[3] Mit Hilfe von XOR kann man so eine Daten-Bitfolge mit einer Schlüssel-Bitfolge zu einem Code verknüpfen. Aus diesem Code können dann per Ver­knüpfung mit dem Schlüssel wieder die Daten gewonnen werden. In Abbildungen findet sich hierfür das Zeichen „®".

2 Erklärung der Funktionsweise des DES-Algorithmus

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3 Das DES-Schema

Der Data Encryption Algorithm (DEA) entspricht einer symme­trischen Blockchiffre, die auf Transpositionen (auch Permutationen genannt) und Substitutionen beruht. D.h. der binäre Klartext wird in Blöcke von 64 Bit zerlegt und jeder Block wird nach dem gleichen Prinzip in 16 Feistel-Runden [4] durch Vertauschungen (Permuta­tionen) und Ersetzungen (Substitutionen) zu einem 64 Bit Chiffre­block verschlüsselt. DES verwendet hierbei effektiv einen 56-Bit- Schlüssel. Es gilt das Kerkhoffsche Prinzip: Die ganze Sicherheit liegt in der Geheimhaltung des Schlüssels, nicht etwa auf der Geheimhal­tung des Algorithmus.

2.1 Überblick über die Funktionsweise

Der binäre Klartextblock von 64 Bit wird nach einer Eingangspermutation in zwei 32 Bit Blöcke zerlegt. Mit diesen Hälften werden nun 16 identische Runden durchgeführt, in denen die Daten mit dem Schlüssel verknüpft werden. Dabei wird die sogenannte rechte Hälfte doppelt verwendet. Zum einen bildet sie die linke Hälfte der nächsten Runde, zum anderen wird sie in der Funktion f mit dem Rundenschlüssel Ki verknüpft. Das Ergebnis der Funktion wird mit der linken Hälfte XOR (siehe Kap. 1.2.3) verrechnet und formt so die rechte Hälfte der nächsten Runde. Nach 16 Runden folgt eine der Eingangspermutation inverse Ausgangs­permutation (Abb. 3).

2.2 Eingangs- und Ausgangspermutation

Abbildung in dieser Leseprobe nicht enthalten

Tab. 1 Eingangsper-mutation

Vor der ersten Runde erfolgt die Eingangspermutation. Sie vertauscht die 64 Eingangsbits gemäß Tabelle 1. So wird beispielsweise das Bit an der Stelle 58 an die erste Outputstelle geschoben, das 50. Bit besetzt die zweite Outputstelle usw. Nach der letzten Runde folgt die Ausgangspermuta­tion, die invers zur Eingangspermutation ist,[5] d.h. erfährt ein Bitblock lediglich diese beiden Operationen, so ist das Ergebnis genau wieder dieser Bitblock. Deshalb haben diese Permutationen keinen sicherheitsre­levanten Einfluss auf den Algorithmus. Man brauchte diese Permuta­tionen, da früher DES in Hardware implementiert wurde, und so wurden sie im Standard verankert.

2.3 Der Algorithmus f

Zunächst werden die 32 Eingangsbits in einer sogenannten Expansion Permutation ver­tauscht und teilweise doppelt verwendet (Abb. 4). Der so entstehende 48 Bit Output wird dann mit dem Runden-Teilschlüssel, ebenfalls von einer Länge von 48 Bit, XOR verknüpft.

Nun kommen die S-Boxen („Substitution-Boxes") zum Einsatz, die wesentlich zur Sicherheit des DEA beitragen: Die Bits werden gleichmäßig auf die acht S-Boxen aufgeteilt und jede S­Box verarbeitet ihren 6 Bit Input zu einem 4 Bit Output. Für jede S-Box gibt es hierfür verschiedene Vorschriften im Standard, als Beispiel soll hier die S-Box 1 dienen (Vgl. Tab. 2):

Abbildung in dieser Leseprobe nicht enthalten

Tab. 2 Die erste S-Box

Die sechs Input-Bits seien b1, b2, b3, b4, b5 und be. Die Tabelle ist so zu lesen, dass für die Spal­te die Bits b2, b3, b4, b5 in eine Dezimalzahl umgerechnet werden. Die Zeile bestimmen b1 und bé. Angenommen es kämen die sechs Bits 11DD11 in die S-Box, so bilden die Bits zwei bis vier und das entspricht der Dezimalzahl 9. Die äußeren beiden Bits bilden 11, was

einer dezimalen 3 entspricht. Nun findet man in der Spalte 9 und der Zeile 3 den Eintrag 11. Umgerechnet erhält man die vier Output-Bits 1D11.

Die Ergebnisse der acht S-Boxen werden anschließend wieder zusammengesetzt und dann in der Permutation P abschließend vertauscht.

Für weitere Tabellen der Permutationen E und P sowie der S-Boxen sei auf den Anhang ver­wiesen.

2.4 Schlüsselgenerierung durch Shift-Operationen

Für jede der 16 DES-Runden wird ein eigener Teilschlüssel generiert. Dafür durchläuft der Originalschlüssel einige Operationen. Er erfährt zu Anfang eine Eingangspermutation („Per­muted Choice 1"), die den 64-Bit-Schlüssel auf 56 Bit reduziert. Die acht ignorierten, soge­nannten Paritätsbits des Originalschlüssels sind lediglich zur Überprüfung der fehlerfreien Übertragung des Schlüssels gedacht und werden somit nicht in den weiteren Prozess mitein- bezogen.

Nun folgen 16 Runden, wobei in jeder ein Teilschlüssel von 48 Bit für die Funktion f der je­weiligen Runde bereitgestellt wird. Der Schlüssel wird - geteilt in zwei Hälften - in den Run­den je durch eine Shift-Operation[6] und eine auswählende Permutation bearbeitet (Abb. 4).

[...]


[1] heute: National Institute of Standards and Technology (NIST)

[2] Der Bundesstandard wurde veröffentlicht unter: National Bureau of Standards (Hg.): Data Encryption Standard, FIPS PUB 46. National Technical Information Service, 1980.

[3] Diese Regel entspricht einer Addition modulo 2.

[4] Benannt sind die Feistel-Runden nach ihrem Erfinder Horst Feistel.

[5] Die Tabellen aller Permutationen sowie S-Boxen sind im Anhang zu finden. Sie sind der Übersichtlichkeit halber nicht im Hauptteil aufgeführt.

[6] Die Bits werden um eine festgelegte Zahl nach rechts verschoben, Bits am Ende werden an den Anfang gestellt (zyklische Verschiebung); zur Anzahl der Verschiebungen siehe Anhang.

Ende der Leseprobe aus 22 Seiten

Details

Titel
Data Encryption Standard - Eine erste moderne Chiffre auf Basis des Dualsystems
Note
1,0
Autor
Jahr
2010
Seiten
22
Katalognummer
V181344
ISBN (eBook)
9783656064091
ISBN (Buch)
9783656064121
Dateigröße
1077 KB
Sprache
Deutsch
Anmerkungen
Diese Seminararbeit wurde im Rahmen des W-Seminars Mathematik mit dem Titel "Kryptologie - Anwendung moderner Geheimcodes" erstellt und erhielt 15 von 15 Punkten.
Schlagworte
Kryptologie, National Security Agency, Data Encryption Standard, DES, symmetrische Blockchiffren, Feistel-Code, Feistel-Prinzip, Horst Feistel, Electronic Codebook Modus, Cipher Block Chaining Modus, Cipher Feedback Modus, Output Feedback Modus, Electronic Codebook Mode, Cipher Block Chaining Mode, Cipher Feedback Mode, Output Feedback Mode, Triple DES, S-Boxen, Lawineneffekt, Brute Force, Brute Force Angrif
Arbeit zitieren
Christian Sperber (Autor), 2010, Data Encryption Standard - Eine erste moderne Chiffre auf Basis des Dualsystems, München, GRIN Verlag, https://www.grin.com/document/181344

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Data Encryption Standard - Eine erste moderne Chiffre auf Basis des Dualsystems



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden