RSA als modernes Verschlüsselungsverfahren

Inhaltsverzeichnis

1 Vorbemerkung

2 Grundlegende Begriffe
2.1 Die Anatomie einer Nachricht
2.2 Offene und geheime Kommunikation

3 Klassische Formen geheimer Kommunikation
3.1 Steganographie
3.2 Transposition.
3.3 Substitution
3.3.1 Codierung
3.3.2 Chiffrierung.
3.3.2.1 Einfache monoalphabethische Substitution
3.3.2.2 Homophone Substitutionschiffren
3.3.2.3 Polyalphabetische Substitutionschiffren

4 Der Weg zur Entwicklung von RSA
4.1 Die Idee der asymmetrischen Verschlüsselung
4.2 Prinzip der Einwegfunktion
4.3 Die Modul-Arithmetik
4.4 Von der Einwegfunktion zur Falltürfunktion
4.5 Die Primfaktorzerlegung
4.6 Das Rivest-Shamir-Adleman-System
4.6.1 Konkretisierung.
4.6.2 Die Sicherheit von RSA

5 Evaluation zum Thema Datenschutz im Internet

6 Schlussbemerkung

7 Anhang
7.1 Quellenverzeichnis
7.2 Fragebogen
7.3 Erklärung

1 Vorbemerkung

Die Kryptographie, die Lehre vom Verschlüsseln von Nachrichten, hat in den vergangenen Jahren immer mehr an Bedeutung gewonnen. Eine wesentliche Ursache hierfür ist die Einführung des Internet, die eine Revolution der Informationsund Kommunikationsinfrastruktur darstellt.

Während in den vergangenen Zeiten meist nur das Militär und die Regierungen auf der einen und Untergrundorganisationen und Kriminelle auf der anderen Seite auf eine sichere Verschlüsselung ihrer Nachrichten angewiesen waren, sieht sich heute nahezu jeder Bürger der Gefahr gegenüber, seine Nachrichten und persönlichen Informationen könnten in die falschen Hände geraten. Die

„Informationsgesellschaft“, in der wir leben, bedeutet nämlich nicht nur, dass jedermann auf vielfältige Informationen Zugriff erlangen kann, sondern eben auch, dass Informationen zur Ware geworden sind. So zahlen verschiedene Unternehmen gerne Geld für Namen und Adressen, wenn diese mit zusätzlichen Informationen, wie etwa Einkaufsverhalten, Einkommensoder Familiensituation, verknüpft sind. Dies sind aber sicherlich noch nicht die sensibelsten Daten, und noch größere Vorsicht ist deshalb bei der Übermittlung von Kontonummern oder gar Kreditkartennummern geboten, zumal Kriminelle gerade im Internet-Umfeld nur schwer zu verfolgen sind.

Der Leichtsinn, mit dem viele Nutzer Informationen über das Internet versenden, hat vermutlich zwei Hauptursachen. Erstens den blinden Fortschrittsglauben und das daraus resultierende Vertrauen in das neue Medium und zweitens die vertraute Atmosphäre – die eigenen vier Wände nämlich – in der man online geht. Das Zuhause vermittelt das trügerische Gefühl der Sicherheit und Privatheit, obwohl man sich im World-Wide-Web auf unbekanntem Terrain bewegt und Lauschangriffen relativ schutzlos ausgeliefert ist.

Diese Seminararbeit befasst sich in der Hauptsache mit einem der modernsten und sichersten Verschlüsselungsverfahren, der RSA-Chiffre, auf dessen Grundlage auch die PGP-Software zur sicheren Verschlüsselung von E-Mails arbeitet. Ein wesentlicher Teil der Arbeit befasst sich aber mit den Ursprüngen der Geheimbotschaften und der Geschichte der Chiffren, da anhand älterer und einfacherer Verfahren die Einführung der Grundbegriffe leichter verständlich ist und die grundsätzliche Vorgehensweise bei der Chiffrierung und Dechiffrierung von Botschaften deutlicher wird. Darüber hinaus stellt die Geschichte der Codes und Chiffren eine durchgehende Entwicklung dar. Der Wettstreit zwischen Verschlüsslern auf der einen und Entschlüsslern auf der anderen Seite hat immer wieder neue und bessere Verfahren hervorgebracht. Ich hoffe, dass die von mir gewählten Beispiele diesen Wettlauf und diesen stetigen Fortschritt in der Komplexität der Verschlüsselungssysteme deutlich machen können.

Im letzten Teil der Arbeit soll noch die Auswertung einer Umfrage zum Thema

„Datensicherheit im Internet“ vorgestellt werden, die ich im Rahmen der Seminararbeit durchgeführt habe.

2 Grundlegende Begriffe

2.1 Die Anatomie einer Nachricht

Bei der Betrachtung kryptographischer Verfahren muss man sich zunächst die Anatomie einer Botschaft vergegenwärtigen: Eine Botschaft hat naturgemäß fünf Komponenten, nämlich einen Sender, einen Empfänger, einen Inhalt, einen Kanal und einen Code. Bei der mathematischen Betrachtung der Kommunikation genügt es den Vorgang als Austausch von Informationen zu verstehen. Weitergehende Überlegungen zu diesem Thema, so wie sie in der modernen Psychologie eine Rolle spielen, können hier vernachlässigt werden.

Erfolgreiche Nachrichtenübermittlung ist gewährleistet, wenn folgende Gegebenheiten gewährleistet sind:

- Der Sender verschlüsselt den Inhalt der Nachricht mittels eines Codes.
- Der Sender gibt die Nachricht in den Kommunikationskanal.
- Der Empfänger erhält die Nachricht aus dem Kommunikationskanal.
- Der Empfänger decodiert die Nachricht erfolgreich und gelangt somit in den Besitz der Information.

Das heißt vereinfacht ausgedrückt, dass Informationsaustausch erfolgreich ist, wenn Sender und Empfänger die selbe Sprache (Code) sprechen und wenn die Verbindung (Kanal) zwischen ihnen nicht gestört ist.¹

Dies sei anhand von aus dem Leben gegriffenen Beispielen erläutert. Probleme beim Informationsaustausch, die auf unterschiedlichen Codes resultieren, kennt jeder aus dem Gespräch mit Ausländern, die der Landesprache noch nicht mächtig sind, häufig treten derartige Probleme aber auch beim übermäßigen Gebrauch von Fremdwörtern oder Termini technici auf. Im schriftlichen Bereich sind solche Probleme beim Gebrauch eigenwilliger Handschriften, die einem persönlichen Code des Verfassers entsprechen, zu erwarten. Störungen des Informationsaustauschs können aber auch durch den Kanal hervorgerufen sein. Beispiele hierfür sind Störungen eines Gesprächs durch Lärm, häufiger treten Kanalstörungen aber beim Gebrauch technischer Instrumente zum Informationsaustausch auf. Dieser Aspekt ist aus zweierlei Gründen interessant. Einerseits nimmt die Menge von auf solchen

Wegen transportierten Informationen in den vergangenen Jahren beschleunigt zu, andererseits birgt der Einsatz von Kommunikationstechnologie ein neues Problem in sich. Im Gegensatz zum normalen Gespräch ist beim Informationsaustausch über Computernetzwerke und ähnliches nämlich nicht mehr augenscheinlich, wer in der Lage ist die Informationen abzugreifen und überdies kann der Empfänger von Nachrichten nicht direkt überprüfen wer der Sender ist, das heißt der Sender ist nicht automatisch authentifiziert.

2.2 Offene und geheime Kommunikation

Bei der bisherigen Betrachtung des Nachrichtenaustauschs wurden in erster Linie Sender und Empfänger als Kommunikationsteilnehmer angesehen. Offensichtlich findet Kommunikation aber nicht im leeren Raum statt, sondern im Umfeld befinden sich Personen, die beabsichtigt oder unbeabsichtigt als weitere Empfänger auftreten. Solche Personen bezeichnet man als Lauscher.

In der Regel sind Lauscher unwillkommen, gerade dann, wenn die Informationen einen vertraulichen oder kompromittierenden Charakter haben. Deshalb ziehen sich die meisten Menschen zu solchen Gesprächen in einen geschützten Bereich zurück, um potentiellen Lauschern keinen Angriffsraum zu geben. So wird aus offener Kommunikation geheime Kommunikation.

Verallgemeinert man nun das Vorgehen bei geheimer Kommunikation über den privaten Bereich hinaus, so ist zunächst festzustellen, dass allen Formen geheimer Kommunikation dasselbe Ziel zugrunde liegt: Lauschangriffe sollen verunmöglicht werden oder zumindest ins Leere laufen. Wenn man nun das oben erläuterte Kommunikationsmodell mit Sender, Empfänger, Kanal, Inhalt und Code betrachtet, so gibt es zwei grundlegende Möglichkeiten, dieses Ziel zu erreichen: Entweder man sichert den Kommunikationskanal so ab, dass die Information ausschließlich vom Empfänger abgegriffen werden kann, oder der Sender benutzt einen Code zur Verschlüsselung der Nachricht, der zwar vom Empfänger, nicht aber von einem eventuellen Lauscher entschlüsselt werden kann.²

Die erste Möglichkeit, also die Absicherung des Kanals, ist aus mathematischer Sicht relativ uninteressant, da diese Problemstellung eher von technischer Natur ist.

Deshalb wird im folgenden hauptsächlich auf die zweite Möglichkeit eingegangen, also auf die Frage wie man Nachrichten effektiv Verschlüsseln kann. In der mathematischen Fachwelt ist dieser Fragestellung mit der Kryptographie ein eigener Fachzweig gewidmet.

Unter Kryptographie versteht man die Verschlüsselung der Nachrichten durch den Sender, so dass sie, selbst wenn sie im Kanal von einem Lauscher abgefangen wird, nicht verstanden oder verfälscht werden kann. Der Versuch des Lauschers, die Nachricht zu entschlüsseln, wird im Gegensatz dazu als Kryptoanalyse bezeichnet. Die Verbindung zur Mathematik besteht darin, dass derartige Verschlüsselungen auf Abbildungsvorschriften beruhen, vergleichbar einer mathematischen Funktion die jedem x-Wert einen y-Wert zuordnet. Solche Verschlüsselungsvorschriften können auch öffentlich bekannt sein, denn zusätzlich werden zwischen Sender und Empfänger noch Schlüssel vereinbart, so dass es dem Lauscher erst dann möglich ist eine Nachricht zu entschlüsseln, wenn ihm neben der Abbildungsvorschrift auch der Schlüssel bekannt ist. Bezogen auf den obigen Vergleich mit der mathematischen Funktion stellt der Schlüssel also eine unbekannte Variabel, die zur Lösung der

Funktion nötig ist, dar.³

An dieser Stelle sollten noch zwei Begriffe eingeführt werden: Die Nachricht vor der Verschlüsselung wird Klartext genannt, die verschlüsselt wird mit Geheimtext bezeichnet, das heißt der Klartext wird durch die Verschlüsselung auf den Geheimtext abgebildet.

3 Klassische Formen geheimer Kommunikation

Im Lauf der Geschichte war es immer wieder von Nöten, bestimmte Nachrichten auf eine Weise zu übermitteln, so dass die Informationen nicht in die Hände feindlicher Spitzel gelangen. Eine große Zahl verschiedenster Methoden und Geheimschriften besteht bereits seit Jahrtausenden. Einige wesentliche Methoden sollen daher im folgenden an Hand von Beispielen erläutert werden, wenngleich die älteren Verfahren in der modernen Kryptographie eine nur untergeordnete Rolle spielen.

Die Sonderform Steganographie ist hier nur der Vollständigkeit halber aufgeführt, im Mittelpunkt der Betrachtung sollen hier zunächst klassische kryptographische Verfahren stehen. Kryptographie, abgeleitet vom griechischen kryptos und graphein für „verborgen“ beziehungsweise „schreiben“, hat das Ziel den Sinn einer Nachricht, nicht aber die Existenz derselben, vor Lauschern zu schützen. Diese Verfahren finden sich in den Unterpunkten Transposition und Substitution beschrieben.⁴

3.1 Steganographie

Die Steganographie, abgeleitet vom griechischen steganos für „bedeckt“, ist eine besondere Art der geheimen Kommunikation, bei der die Nachricht selbst unverschlüsselt bleibt. Hier wird versucht eine Nachricht so durch den Kanal zu befördern, dass sie von einem Lauscher nicht entdeckt wird, die Nachricht wird also nur versteckt.

Vom Einsatz einfacher Geheimtinten bis hin zur Benutzung von sogenannten Mikropunkten, einer Spielart aus dem zweiten Weltkrieg, bei der ganze Fotographien so weit verkleinert wurden, dass sie von feindlichen Spionen nicht mehr entdeckt werden konnten, haben sich im Lauf der Zeit vielfältigste Steganographie-Methoden entwickelt.

Als einfaches Beispiel sei noch eine verblüffende Methode, die im 15. Jahrhundert vom italienischen Wissenschaftler Giovanni Porta beschrieben wurde, erwähnt. Eine Botschaft kann verborgen werden, indem man sie mit einer Mischung von Essig und Alaun auf die Schale eines hartgekochten Eis schreibt. Diese spezielle Tinte ist in der Lage, die Schale zu durchdringen, und hinterlässt ihre Spuren erst auf der

Eioberfäche, so dass man nur durch das Schälen des Eis in Besitz der Botschaft gelangt.⁵

Alle steganographischen Verfahren haben allerdings den gemeinsamen Makel, dass sie nur so lange Geheimhaltung gewährleisten, bis der Lauscher weiß, wo er suchen muss. Nur eine zusätzliche Verschlüsselung könnte die Nachricht weiterhin schützen, wenn ihr Versteck erst einmal gefunden wurde. Wie solche zusätzlichen Verschlüsselungen aussehen könnten, wird in den folgenden Punkten beschrieben.

3.2 Transposition

Transpositionsverfahren, abgeleitet vom lateinischen transponere für „verschieben“, zielen darauf ab, den Sinn eines Textes zu verschleiern, in dem die Reihenfolge der einzelnen Buchstaben verändert wird. Die deutschen Bezeichnungen

„Würfelverfahren“ oder auch „Versatzverfahren“ beschreiben dieses Prinzip recht gut. Die Art der Verwürfelung wird als Permutation bezeichnet, und orientiert sich in der Regel an bestimmten geometrischen Figuren beziehungsweise Mustern. Der Geheimtext geht hier also aus dem Klartext hervor, indem man ihn nach einem gewissen Muster aus dem Klartext herausliest, und somit ist dieses Muster ein Teil zur Entschlüsselung der Nachricht.

Das älteste Beispiel für die Transposition zur Verschlüsselung von Nachrichten ist die bereits 400 v.Chr. von den Griechen benutzte Skytale. Hierbei handelt es sich um einen Zylinder bestimmten Durchmessers, der mit einem Papyrusstreifen umwickelt wird, um dann zeilenweise (bezogen auf die Zylinderachse) beschrieben zu werden. Wird der Papyrusstreifen wieder abgewickelt, so enthält er die Zeichen in permutierter Reihenfolge. Mit Hilfe einer Matrix, in die man den Klartext zeilenweise einträgt und den Chiffretext spaltenweise ausliest, kann man die Skytala simulieren:⁶

Gegeben sei der Klartext „die kunst ist lang und kurz das leben“.

Überträgt man diesen Text zeilenweise in eine Matrix mit sechs Spalten, so erhält man folgendes Bild:

Abbildung in dieser Leseprobe nicht enthalten

Ein solcher Geheimtext kann leicht durch Ausprobieren entschlüsselt werden, da der Schlüsselraum, also die Anzahl möglicher Schlüssel sehr begrenzt ist. Er entspricht der Anzahl der Spalten, beziehungsweise dem Durchmesser des Zylinders. Ein weiteres Manko dieses Verfahrens besteht darin, dass zwei aufeinander folgende Zeichen des Klartextes im Geheimtext immer denselben Abstand zueinander aufweisen, wodurch die Entschlüsselung relativ einfach erscheint.

Eine auf dieser Überlegung basierende Verbesserung des Kryptosystems besteht nun darin die Spalten nicht mehr der Reihenfolge nach auszulesen, sondern in einer willkürlich gewählten Abfolge. Diese Permutation π der Spalten wird somit ein Teil des Schlüssels, der zur Entschlüsselung notwendig ist, was an folgendem Beispiel verdeutlicht wird:

Abbildung in dieser Leseprobe nicht enthalten

Bei s Spalten beträgt die Zahl der möglichen Permutationen

s !, womit der

Schlüsselraum um diesen Faktor erweitert wird. Im Beispiel käme man somit auf 6! oder 720 mögliche Permutationen.

[...]

¹ Vgl.: Horster, Patrick: Kryptologie S. 12f Beth, Thomas u.a.: Kryptographie S. 10ff

² Vgl.: Beth, Thomas u.a.: Kryptographie S. 10ff

³ Vgl.: Fumy, Walter Rieß, Hans Peter: Kryptographie S.13 f

⁴ Vgl.: Beth, Thomas u.a.: Kryptographie S. 5

⁵ Vgl.: Singh, Simon: Geheime Botschaften S.20f

⁶ Vgl.: Bauer, Friedrich: Kryptologie S.73 Fumy, Walter Rieß, Hans Peter: Kryptographie S.39ff