Kryptographie

Inhalt

Vorwort

DES (Data Encryption Standard)

Der Diffie-Hellmann-Schlüsseltausch

Das El-Gamal-Verfahren

Der RSA-Algorithmus

Das Fiat-Shamir-Verfahren (Zero-Knowledge)

Mathematik – Natürliche Zahlen Teil 1

Mathematik – Natürliche Zahlen Teil 2

Mathematik – Natürliche Zahlen Teil 3

Mathematik – Natürliche Zahlen Teil 4

Anhang – Primitive Elemente bis p =

Vorwort

Da ich herausgefunden habe, dass man ein Sache wirklich besser lernt, wenn man die wichtigsten Dinge einmal schön herausgeschrieben hat, oder man etwas dazu schreibt, wollte ich mal diese Zusammenfassung schreiben.

Da ich meine, dass mir diese Arbeit jede Menge gebracht hat - ich glaube nun wenigstens, dass ich die Grundzüge dieser hier beschriebenen Verfahren verstehe – wollte ich sie mal ins Netz setzen, denn vielleicht hilft Euch das Ding auch etwas weiter.

In dieser Zusammenfassung befinden sich Text aus anderen Büchern, verschiedenen Internetseiten, eigenen Hinzufügungen und Beispielen die ich mal durchgerechnet habe (und das Ergebnis auch hinkam, was bedeuten (müsste), dass die Rechnung richtig ist.

Damit will ich jedoch keine Panik zum wegwerfen dieses Dokumentes verbreiten, sondern einfach nur sagen, dass Ihr keinen Anspruch auf 100% Richtigkeit dieses Schriftstückes stellen dürft. Zwar werde ich mich wohl nicht großartig vertippt haben, aber Fehler passieren immer und ich bin ja auch kein Kryptomeister. Vor allem wäre ich Euch aber sehr sehr dankbar, wenn Ihr einen Fehler (oder auch Anregungen) findet, euch sofort auf dem Weg zu einem Rechner macht und mir ne E-Mail zukommen lassen würdet.

Aber da bald die Krypto-Vorklausur ansteht und die Richtige wohl nicht lange auf sich warten wird, denke ich mal, dass diese Zusammenfassung zunächst mal einen kleinen Lichtblick in das Chaos dieses Faches bringen wird.

Also, lest Euch das Script hier einfach mal durch und dann könnt Ihr selbst entscheiden.

Martin K.

e-M@il senden

DES (Data Encryption Standard)

Hintergrund

Ab Mitte der siebziger Jahre begann mit DES (Data Encryption Standard) der Siegeszug der modernen Kryptographie. Zwar waren solche Verschlüsselungssysteme schon vorher bekannt, jedoch waren diese Systeme extrem teuer und zudem fehlte ein als sicher befundener Standard, der einen Austausch zwischen den Systemen möglich gemacht hätte.

Der Auswahl eines geeigneten Algorithmus ging eine Ausschreibung des US-amerikanischen

„National Institute of Standard Technology“ (NIST) voraus, das für die Auswahl und Dokumentation dieses Standards führend war.

Schließlich wurde 1976 ein Vorschlag akzeptiert, der auf einen Algorithmus zurückging, welcher Anfang der siebziger Jahre unter dem Namen LUCIFER veröffentlicht wurde und auf IBM zurückging.

Dieser Algorithmus LUCIFER wurde jedoch unter Mitwirkung des Geheimdienstes NSA in einigen Punkten abgewandelt. So wurde z.B. die ursprüngliche Schlüssellänge von 128 auf 56 Bit reduziert. Darüber hinaus arbeitete die NSA an an der Definition der sogenannten S-Boxen mit. Darum ist in der Vergangenheit des öfteren zu hören gewesen, dass die NSA diese S- Boxen so definiert hätte, dass sie jede damit verschlüsselte Nachricht wieder entschlüsseln könnte. Entsprechende Vermutungen konnten jedoch nie bestätigt werden.

Die Technik des DES

Stellen wir zunächst fest, dass DES zur Gattung der symmetrischen Blockchiffrier- Algorithmen gehört. Dies bedeutet, dass eine Nachricht mit den gleichen Schlüssel ver- und entschlüsselt wird.

DES arbeitet so, dass jeweils 64 Bit ( = 8 Byte ) des Quelltextes an einem Stück mit einem 56-Bit-Schlüssel verschlüsselt werden. Dabei werden keine komplexen mathematischen Prozeduren ausgeführt, sondern es werden Bits nach fest vorgegebenen Regeln vertauscht ( Permutation) und ersetzt (Substitution).

In sechzehn Arbeitsschritten (Runden) wird der Klartext mit diesem Schlüssel so durcheinander gewürfelt, dass eine Entschlüsselung, ohne Kenntnis des Schlüssels, in annehmbarer Zeit nicht mehr möglich sein sollte. Was sich anscheinend jedoch nicht bestätigt hat, da der DES Algorithmus bereits geknackt wurde und es zahlreiche Internetseiten und Bücher gibt. welche genau erklären, wie man diesen DES knacken kann.

Da der Schlüssel ja nur 56 Bit lang ist, wobei der Textblock eine Länge von 64 Bit hat, wird dieser Schlüssel intern in einer 64 Bit Notation gehandhabt, wobei die Bits 0 bis 6 eines jeden Bytes 7 Bit des Schlüssels wiedergeben. Das oberste siebte Bit eines jeden Bytes bleibt hingegen ungenutzt.

Zu beginn einer Runde werden zunächst die zu verschlüsselnden 64 Bit des Klartextes permutiert (untereinander Vertausch). Danach werden diese 64 Bit in zwei Teile geteilt (zu je 32 Bit). Hierauf erfolgt dann die eigentliche Verschlüsselung:

Das ganze sieht im groben folgendermaßen aus:

Abbildung in dieser Leseprobe nicht enthalten

In 16 Runden wird die rechte Hälfte des Klartextes mit dem Schlüssel sowie der linken Klartext-Hälfte verknüpft und dadurch verschlüsselt. Dabei entsteht wieder ein neuer 32-Bit- Wert, der dem nächsten Durchgang als Eingabe dient und ihm als die neue rechte Hälfte zugeführt wird. Als linke Hälfte wird in der nächsten Runde die unverschlüsselte rechte Hälfte aus der vorangegangenen Runde herangezogen.

Auch dazu eine kleine Skizze:

Abbildung in dieser Leseprobe nicht enthalten

Am Anfang einer jeden Runde wird die rechte Hälfte mit Hilfe einer sogenannten Expansionspermutation von 32 Bit auf 48 Bit expandiert. Gleichzeitig wird der 64-Bit-DES- Schlüssel auf einen 48 Bit umfassenden Rundenschlüssel reduziert. Somit haben nun beide Werte die gleiche Breite (48 Bit) und nun werden Sie über eine Exklusiv-Oder-Operation (XOR) verknüpft.

Bis zu diesem Zeitpunkt ist die linke Hälfte des Klartextes unberührt geblieben. Nun soll die linke Hälfte jedoch mit der rechten Hälfte verknüpft werden. Dazu wird die rechte Hälfte erst wieder von 48 Bit auf 32 Bit heruntergerechnet. Hierfür stehen die sogenannten S-Boxen zur Hilfe. Sie liefern eine Art Abbildungstabelle. Dabei werden jeweils 6 Bits aus dem 48-Bit- Wert der rechten Hälfte in 4 Bits umgewandelt.

Die so gewonnenen 32 Bit werden ein weiteres mal permutiert (untereinander vertauscht), um abschließend mit der linken Hälfte per Exklusiv-Oder-Operation verknüpft zu werden. Damit ist eine Runde beendet und gleichzeitig die Grundlage für die nächste Runde geschaffen.

Zur Verdeutlichung noch einmal die Graphik:

Abbildung in dieser Leseprobe nicht enthalten

Für jede der 16 Runden wird aus dem DES-Schlüssel ein eigener Rundenschlüssel erzeugt. Dazu werden die 56 Bit Schlüssel durch eine sogenannte Schlüsselpermutation kräftig durchgemischt. Der resultierende 56-Bit-Schlüssel wird anschließend in zwei Hälften zu je 28 Bit aufgeteilt.

Zu Beginn einer jeden Runde wird jede Hälfte um ein oder zwei Bit nach links rotiert. Aus den rotierten 56 Bit wird über eine Kompressionspermutation ein 48 Bit großer Rundenschlüssel erzeugt, der als Eingangswert in die Verschlüsselungsfunktion einfließt.

Um die Erzeugung des Rundenschlüssels noch einmal besser zu verdeutlichen, folgt auch hier eine kleine Skizze:

Abbildung in dieser Leseprobe nicht enthalten

Rundenschlüssel

Nach der letzten DES-Runde werden die beiden verschlüsselten 32-Bit-Hälften des Klartextes wieder zu einem 64-Bit-Wert zusammengefügt, und die Wirkung der Start-Permutation wird durch eine End-Permutation wieder aufgehoben.

DES-Entschlüsselung

Das angenehme bei DES ist, dass die Entschlüsselung tatsächlich auf dem gleichen Verfahren und den gleichen Operationsschritten beruht, wie die Verschlüsselung.

Allerdings

Ist ein kleiner, aber enormer Unterschied zu beachten: Die Reihenfolge der Rundenschlüssel muss umgekehrt werden, um den Prozess der Verschlüsselung wieder rückgängig zu machen. Werden zur Verschlüsselung die Rundenschlüssel in der Reihenfolge k1, k2, ... , k16 verwendet, muss die Reihenfolge beim Entschlüsseln k16, k15, ..., k1 lauten.

Der Diffie-Hellmann-Schlüsseltausch

Hintergrund

1976 erschien eine Arbeit mir dem Titel: „New Directions in Cryptographie“. Geschrieben wurde sie von Whitfield Diffie und Martin Hellmann. In dieser Arbeit nehmen sich die beiden Autoren des Problems einer Verschlüsselung ohne vorherigen Schlüsseltausch an, das bis dahin für „offensichtlich unlösbar“ gehalten wurde:

„Kann ich jemandem, mit dem ich noch nie Kontakt hatte, insbesondere noch nie ein Geheimnis ausgetauscht habe, eine verschlüsselte Nachricht schicken, die nur er entschlüsseln kann?“

Wenn man ehrlich ist, haben die zwei das Problem eigentlich nicht gelöst. Der Verdienst dieser Arbeit liegt darin, dass Diffie und Hellmann die entscheidende Frage überhaupt stellen und sie ernst nahmen. Sie präparierten das Problem in aller Schärfe und übersetzten es in mathematische Sprache. Dabei spielt der Begriff der „trapdoor Einwegfunktionen“ die Schlüsselrolle.

Eine Einwegfunktion ist eine Funktion, die wie eine Einbahnstraße funktioniert: In eine Richtung geht es ganz einfach, in die andere Richtung geht nichts.

Eine „ trapdoor “ (Geheimgang oder Hintertür) ist eine geheime Information, mit der man die

Einwegfunktion doch rückgängig machen kann.

Diffie und Hellmann weisen nach: Wenn es trapdoor Einwegfunktionen gäbe, dann wäre auch die Frage der Verschlüsselung ohne vorherigen Geheimaustausch gelöst. Damit ist die Frage auf die Frage nach der Existenz dieser Trapdoor Einwegfunktionen zurückgeführt.

Zum Verfahren

Zunächst stellen wir einmal fest, dass der Diffie-Hellmann-Schlüsseltausch ein asymmetrisches Verfahren ist.

Die Art und Weise, wie zwei Personen öffentlich eine geheime Zahl bestimmen, soll nun erläutert werden.

Abbildung in dieser Leseprobe nicht enthalten

Zunächst müssen sich die beiden Partner auf eine Primzahl p einigen. Ferner wählen Sie eine natürliche Zahl s, die größer als 1 und kleiner als p sein soll. Nun muss noch weiter gelten, dass s ein primitives Elements ist (siehe Mathe Teil 4). Das s ein primitives Element sein muss liegt daran, dass bei kleiner Rechnung als Ergebnis 1 herauskommen darf, da sonst jeder Außenstehende den Endschlüssel berechnen könnte. Diese beiden Zahlen (p, s) bilden praktisch die Grundlage, aus der die geheime Zahl durch zweimalige Verfeinerung entstehen wird. Es liegt also bisher noch kein Geheimnis in den Zahlen p und s. Jeder Außenstehende darf p und s kennen.

Nun beginnt der zweistufige Verfeinerungsprozesses. Die Partner A und B wählen jeweils geheim eine Zahl a bzw. b, wobei auch diese kleiner als p -1 sein muss (ap-1, bp-1) und potenzieren die Zahl s mit a bzw. b, jeweils mit modulo p.

Das heißt, A berechnet die Zahl

Abbildung in dieser Leseprobe nicht enthalten

Hierauf werden die Zahlen a und b ausgetauscht: Die Zahl a wird öffentlich an B geschickt und die Zahl b wird öffentlich an A geschickt.

Nun sind A und B in der Lage, dass Endprodukt herzustellen. Dazu potenzieren sie die jeweils erhaltenen Werte mit ihren geheimen Zahlen.

Das heißt, A berechnet

Abbildung in dieser Leseprobe nicht enthalten

und B berechnet

Abbildung in dieser Leseprobe nicht enthalten