Eine Einführung in die Kryptographie

ArticleCategory:

System Administration

AuthorImage:

Pierre Loidreau

TranslationInfo:[Author and translation history]

original in fr Pierre Loidreau

fr to en Axelle Apvrille  

en to de Guido Socher

AboutTheAuthor

Pierre arbeitet als Wissenschaftler und Lehrer bei der ENSTA (Ecole Nationale Supérieure de Techniques Avancées). Er arbeitet auf dem Gebiet Kryptosysteme und Fehlerkorrekturcodes. Er "spielt" fast jeden Tag mit Linux herum und manchmal spielt er Tennis.

Abstract:

Dieser Artikel wurde zuerst in der "Security Spezialausgabe" des Linux Magazine France veröffentlicht. Der Editor, die Autoren und die Übersetzer haben freundlicherweise LinuxFocus die Erlaubnis gegeben, alle Artikel dieser Spezialausgabe zu veröffentlichen, sobald diese auf Englisch verfügbar sind. Ein großes Dankeschön geht an alle, die bei dieser Arbeit beteiligt sind. Dieser Absatz wird in jedem Artikel dieser Serie erscheinen.

ArticleIllustration:

mail

ArticleBody:[The article body]

Warum Kryptographie -- 2500 Jahre Geschichte

Die Geschichte der Kryptographie geht zurück zu den Ursprüngen der Menschheit, als Menschen anfingen miteinander zu kommunizieren. Sie hatten das Bestreben auch geheime Nachrichten auszutauschen, auf eine sichere Art. Die erste gezielte Anwendung von technischen Methoden um Nachrichten zu verschlüsseln geht auf die Griechen zurück. Sie benutzten um 6 vor Christus einen Stock namens "scytale". Der Sender einer Nachricht würde ein Papier um diesen Stock rollen und seine Nachricht der Länge nach darauf schreiben. Danach würde er das Papier wieder vom Stock abrollen und verschicken. Der Empfänger wäre nicht in der Lage die Nachricht zu lesen, ohne die genaue Dicke des Stocks zu kennen. Die Stockdicke war also der geheime Schlüssel. Später haben römische Heere Caesar's Code benutzt, um Botschaften auszutauschen. Caesar's Code verschiebt das Alphabet um drei Buchstaben.

In den nächsten 19 Jahrhunderten wurden mehr oder weniger clevere experimentelle Verschlüsselungsverfahren entwickelt. Ihre Sicherheit hing davon ab, wieviel Vertrauen der Benutzer in dieses Verfahren hatte. Im 19. Jahrhundert schrieb Kerchoff eine der Prinzipien der modernen Kryptographie. Es besagt, daß die Sicherheit eines kryptographischen Systems nicht in dem Verfahren der Verschlüsselung liegt, sondern von der Länge des verwendeten Schlüssels abhängt.

Von diesem Augenblick an konnte man erwarten, daß kryptographische Systeme dieser Anforderung gerecht wurden. Es fehlte jedoch noch an mathematischem Hintergrund und Werkzeugen, um die Widerstandsfähigkeit gegen Angriffe zu testen. 1948 und 1949 untermauerte Claude Shannon die moderne Kryptographie mit zwei Veröffentlichungen: "A Mathematical Theory of Communication" und "The Communication Theory of Secrecy Systems". Diese zwei Artikel fegten Hoffnungen und Vorurteile gleichermaßen hinweg. Shannon bestätigte, daß Vernam's Cipher, die einige Jahre zuvor vorgeschlagen worden war, auch als One Time Pad (einmal Schlüssel) bekannt, das einzige sichere System war, das es jemals geben kann. Leider war dieses System in der Praxis unbenutzbar.... Das ist der Grund, warum die Sicherheit eines Systems heute an dem Rechenaufwand zum Entschlüsseln gemessen wird. Man behauptet, daß ein System sicher ist, wenn kein bekannter Angriff einfacher ist als das Durchprobieren aller möglichen Schlüssel.

AES (Advanced Encryption Standard)

Kürzlich, im Oktober 2000, hat das NIST (National Institute of Standards and Technology) einen neuen Standard zur Verschlüsselung unter 15 Kandidaten ausgewählt. Dieser neue Standard soll den alten DES Algorithmus ablösen. Rijndael -- ein Phantasiename aus den Namen der Erfinder, Rijmen und Daemen, wurde als AES ausgewählt.

Dieses kryptographische System wird als "block cipher" bezeichnet, da es 128-Bit Blöcke verschlüsselt. Verschiedene Optionen erlauben die Benutzung von Schlüsseln der Länge 128, 192 oder 256 Bit. Nur zu deiner Information: Der DES war eine 64 Bit "block cipher" mit einer Schüssellänge von 56 Bit. Tripple-DES verschlüsselt 64 Bit Blöcke mit einer Schüssellänge von 112-Bit.

AES

Abb. 1: AES Iterationen

Das Verfahren von AES ist in Abb. 1 beschrieben. Zunächst wird der geheime Schlüssel K0 mit der Nachricht ver-XOR-ed. Danach wir die Funktion F iterativ (wie bei allen "block ciphers") angewandt, unter Benutzung von Unterschlüsseln, die durch eine Schüsselexpansionsroutine erzeugt werden.

Für AES wird die Funktion F 10 mal angewandt.
F function

Abb 2: Funktion F

Nun wollen wir noch schnell sehen, wie die Substitutionen gebaut werden und wofür die Konstanten ai gebraucht werden. Technisch und aus Gründen der einfachen Berechnung, wird ein Byte als ein Element aus einer Menge von 256 Elementen betrachtet, genannt Finite Field. In einem Finite Field existieren einfache Operationen wie Addition, Multiplikation und Inverses-Element. Die Substitution S ist die Inverse eines solchen Finite Field.
Die Substitution S ist eine sehr einfache Operation und kann deshalb leicht implementiert werden. Element ai ist einfach die i-te Potenz im Finite Field. Das macht die AES sehr effizient.

Da AES nur mit einfachen Bit Operationen arbeitet hat es zwei Vorteile:
Key expansion routine

Abb. 3: Schlüsselexpansion

Public Key Cryptography

Im Jahr 1976 haben Diffie und Hellman einen Artikel mit dem Titel "New Directions in Cryptography" veröffentlicht, der zum Renner in der Kryptographiegemeinde wurde. Dieser Artikel stellte ein neues Konzept vor: Public Key Cryptography. Die bis zu dieser Zeit bekannten symmetrischen Algorithmen mit geheimen Schlüssel wurden nicht mehr den Bedürfnissen der modernen Kommunikation gerecht.

Das neue an Public Key Cryptography war die Idee der Trapdoor One-Way Functions. Diese Funktionen lassen sich einfach in einer Richtung berechnen, aber es gibt keine gute Möglichkeit, die Umkehrfunktion zu berechnen. Jedoch haben sie eine Hintertür und wenn man diese Hintertür kennt, kann man auch die Umkehrfunktion leicht aufstellen. Mit anderen Worten: Alle können Nachrichten verschlüsseln, aber nur der, der die Hintertür kennt, kann die Nachricht wieder entschlüsseln. Das war die Geburtsstunde von Alice und Bob. Alice und Bob sind zwei Personen, die geheime Nachrichten austauschen wollen und erfolgreich Eindringlinge schlagen. Eindringlinge, die ihrer Kommunikation lauschen und Daten verändern.


Das schönste Beispiel der Public Key Cryptography (und sicher das Einfachste) wurde zwei Jahre später, 1978, präsentiert. Es wurde erfunden von Rivest, Shamir und Adleman und ist daher als RSA bekannt. Es basiert auf der mathematischen Schwierigkeit eine ganze Zahl in Primfaktoren zu zerlegen. Der geheime Schlüssel besteht aus drei Zahlen (p,q,d) wobei p und q zwei Primzahlen mit ungefähr gleicher Größe sind und d eine relative Primzahl zu p-1 and q-1 und die unten stehende Gleichung erfüllen muß. Der öffentliche Schlüssel besteht aus dem Paar (n,e), wobei n=pq, und e der inverse Modulus von (p-1)(q-1) ist.
ed = 1 mod(p-1)(q-1).



Nehmen wir an, Alice möchte einen Text verschlüsselt mit Bobs öffentlichem Schlüssel verschicken (n,e). Dazu transformiert sie die Nachricht in eine Zahl m kleiner n und dann berechnet sie:
c = me mod n,


und schickt c zu Bob. Bob berechnet auf seiner Seite mit dem geheimen Schüssel (p,q,d):
cd mod n = med mod n = m.


Bei RSA ist die Trapdoor One-Way Function die Funktion, die eine ganze Zahl x<n, mit dem Wert xe mod n assoziiert.

Seit RSA wurden viele andere public key cryptosystems entwickelt. Eine der beliebtesten Alternativen zu RSA ist ein Kryptosystem, das auf diskreten Logarithmen basiert.

Moderne Kryptographie

Public key cryptography ist sehr interessant, weil sie einfach zu benutzen ist und viele Sicherheitsprobleme löst: Daneben bietet public key cryptography, genau wie Kryptographie mit geheimen Schüssel, eine sichere und geheime Kommunikation.

Nehmen wir an, dass Alice geheim mit Bob kommunizieren möchte. Alice holt sich dazu aus einem öffentlichen Verzeichnis den öffentlichen Schüssel von Bob und verschlüsselt damit ihre Nachricht. Bob erhält die Nachricht und kann sie mit seinem geheimen Schlüssel entschlüsseln. Beide Schlüssel, öffentlicher Schüssel und geheimer Schlüssel, haben sehr unterschiedliche Rollen. Deshalb nennt man das auch asymmetrische Kryptographie. Bei Systemen mit geheimen Schlüssel wird derselbe Schlüssel zum Ver- und Entschlüsseln benutzt (symmetrisch).


Public key cryptography bietet einen weiteren riesigen Vorteil. Wenn n Leute miteinander kommunizieren wollen, dann braucht man bei geheimen Schlüsseln für jedes möglich Paar einen Schlüssel. Also n(n-1) Schlüssel. Bei Public key cryptography braucht man nur n Schlüssel. Ein riesiger Vorteil, wenn mehr als tausend Leute miteinander reden möchten. Weiterhin ist es schwierig, mit symmetrischer Kryptographie ein neues Mitglied in die Gruppe einzuführen. Man müßte dazu n Schlüssel erzeugen und sie auf einem sicheren Weg an alle verteilen. Im Gegensatz dazu braucht man bei public key cryptography lediglich einen neuen Schlüssel im Schlüsselverzeichnis zu veröffentlichen.

Öffentlicher Schlüssel oder geheimer Schlüssel: Die richtige Wahl treffen.

Im vorherigen Abschnitt haben wir gesehen, daß public key cryptography viele Probleme löst die Kryptographie mit geheimem Schlüssel nicht lösen kann. Da mag man sich fragen, warum AES, ein symmetrisches Verfahren (geheimer Schlüssel), entwickelt wurde. Es gibt zwei wesentliche Gründe: Zum reinen Verschlüsseln sind also symmetrische Verfahren besser. Zimmermann hat ein interessantes Verfahren ausgearbeitet, daß sowohl asymmetrische als auch symmetrische Verfahren benutzt: PGP. Wenn Alice und Bob kommunizieren wollen, dann sieht das so aus: Nach der Kommunikation wird der geheime Schlüssel (session key) einfach vernichtet. Normalerweise ist der leichter angreifbare Teil der Kommunikation das Schlüsselaustauschprotokoll mit public key cryptography.

Bibliografie

Geschichte der Kryptographie: Zu AES :
Kryptographie im Allgemeinen :