RSA und dessen Ausbauversuch RSAODN. Vergleich zweier Kryptosysteme

Inhaltsverzeichnis

1 Einleitung
1.1 Vorwort
1.2 Begründung der Themenwahl
1.3 Zielstellung der Arbeit

2 Das RSA-Verfahren
2.1 Das Konzept
2.2 Berechnung der Schlüssel
2.3 Ver- und Entschlüsselung
2.4 Alice und Bob in der Moderne

3 Das RSAODN-Verfahren
3.1 Das Konzept
3.2 Modifikation der Zahlen und Verschlüsselung
3.3 Entmodifikation der Zahlen und Entschlüsselung
3.4 Anwendungsmöglichkeiten

4 Vergleich mit dem RSA-Verfahren

5 Schlusswort

6 Anhang
6.1 Literaturverzeichnis

1 Einleitung

1.1 Vorwort

Die Kryptologie ist die Lehre des Ver- und Entschlüsselns von Botschaften. Sie begleitet uns seit jeher, egal, ob als eine geheime Nachricht an unseren Klassenkameraden oder als verschlüsselten Angriffsbefehl an unsere Kampftruppe. Welchen Zweck eine Verschlüsselung auch verfolgt – sie wird immer mit dem Ziel angewandt, einen Dritten von dem Nachrichtenverkehr auszuschließen. Kryptologie ist mehr als nur Mathematik. Sie ändert unser strategisches Denken. Seitdem es Menschen gibt, die etwas geheim halten wollen, gibt es auch diese Wissenschaft. Die wohl bekannteste Verschlüsselungsmethode ist der Cäsar-Code. In diesem vermutlich ältesten Algorithmus findet bereits ein Prinzip Anwendung, welches im Jahr 1883 als Kerckhoffs’ Maxime bekannt wurde. Ein Grundsatz dieser lautet demnach, dass die Sicherheit einer kryptologischen Methode nicht von der Geheimhaltung eines Algorithmus abhängen darf, sondern sich auf die Geheimhaltung frei wählbarer Eingangsgrößen gründet (vgl. Wikipedia). In modernen kryptologischen Verfahren sind diese beispielsweise die geheimen Schlüssel, die ausschließlich in ihr vorhergesehenes Schloss passen, welches eine Kiste mit einem geheimen Inhalt verriegelt.

Diese Arbeit handelt von zwei modernen Systemen, die Schlüssel als Eingangsgrößen für einen festen mathematischen Algorithmus verwenden und versucht, die Funktionsweisen, Anwendungsmöglichkeiten und ihre Tücken aufzuzeigen.

1.2 Begründung der Themenwahl

Geheimnisse begeistern mich seit frühester Kindheit, egal, ob es um das Geheimnis meiner Eltern über die Deaktivierung der Kinderschutzvorrichtung an unserer Mikrowelle oder um die Entwicklung einer geheimen Sprache ging. Mit meinem Interesse an der Informatik wuchs der Spaß an der Mathematik und ich begann, über Verschlüsselungsalgorithmen nachzudenken. Ich entwickelte eine Software, welche die gewünschten Ordner eines USB-Sticks nach noch nicht verschlüsselten Dateien durchsuchte und diese anschließend mithilfe des Programms 7zip, das den amerikanischen Verschlüsselungsstandard (engl. AES: American Encryption Standard) anwendet, verschlüsselt. Findet mein Programm keine Dateien mehr, die es mithilfe von 7zip verschlüsseln kann, beginnt es mit der Entschlüsselung des Inhalts der gewünschten Ordner. Nur wer im Besitz des Schlüssels ist, kann die verschlüsselten Dateien wieder brauchbar machen. Nach der Freude über das funktionierende Programm legte ich mich auf das Thema Kryptologie fest. Ich habe mich für das RSA-Verfahren entschieden, weil ich den Algorithmus und die Sicherheit dieses Verfahrens faszinierend finde. Des Weiteren habe ich mich für die Entwicklung einer eigenen Verschlüsselungsmethode entschieden, da ich dies schon immer tun wollte. Leider wird es mir nicht möglich sein, ein asymmetrisches Verschlüsselungsverfahren neu zu erfinden. Ich werde das RSA-Verfahren modifizieren, um es sicherer zu machen.

1.3 Zielstellung der Arbeit

Bis jetzt gibt es zwar keine Möglichkeiten, den RSA-Algorithmus schnell und unkompliziert zu lösen - Allerdings wird es irgendwann Maschinen geben, die dieser Fähigkeit mächtig sind. Mein Ziel ist es, das moderne Verschlüsselungsverfahren RSA vorzustellen und ein wenig sicherer zu machen. Mit der Entwicklung eines erweiterten und asymmetrischen Kryptosystems kann ich die Möglichkeit, dass irgendwann eine Entschlüsselung durch einen Angreifer gelingt, zwar nicht verringern oder gar ausschließen, aber dafür sorgen, dass der Angreifer nichts mit dem entschlüsselten Text anfangen kann. Das Geheimnis der Funktionsweise dieses Verfahrens lüfte ich in Punkt 3. Im Weiteren möchte ich beide Verschlüsselungsmethoden sowohl sicherheitstechnisch vergleichen, als auch einen Vergleich der Einfachheit der Anwendung der Verfahren aufstellen.

2 Das RSA-Verfahren

2.1 Das Konzept

Jeder kennt noch die kleinen Chiffrier- Scheibchen, in denen das Alphabet um n Stellen verschoben wurde. Die Zahl n nennt man in der Kryptologie „Schlüssel“. Im weiteren Textverlauf werde ich die Kommunikationsbeispiele mit den Kommunikationspartnern Alice und Bob veranschaulichen. Nur wenn Bob den Schlüssel kannte, konnte er den verschlüsselten Text in eine lesbare Form bringen. Natürlich muss Alice die Nachricht zuvor mit exakt diesem Schlüssel verschlüsselt haben. Jeder benutzt also den gleichen Schlüssel. Ein solches System bezeichnet man in der Kryptologie als symmetrisches Kryptosystem. Nun betrachten wir aber die Theorie, dass es zwei Schlüssel gibt. Einen Schlüssel zum Verschlüsseln, einen anderen zum Entschlüsseln. Ein System dieser Art bezeichnet man als asymmetrisches Kryptosystem. Das moderne kryptologische Verfahren „RSA“ ist dem letzteren System zuzuordnen. Der Name setzt sich aus den Anfangsbuchstaben der Nachnamen der Erfinder Ronald Rivest, Adi Shamir und Leonard Adleman zusammen. Ich werde hier aber nicht weiter auf die Historie eingehen. Stattdessen werde ich anhand der beiden Kommunikationspartner Alice und Bob das Verfahren anschaulich beschreiben. Alice hat vor, eine Nachricht an Bob zu verfassen. Die beiden sind ein Liebespaar. Sie möchten aber nicht, dass Max etwas davon mitbekommt. Max ist nämlich die Gerüchteküche in der Schule und möchte nun beweisen, dass die Liebestheorie, die er einst veröffentlichte, stimmt. Bob verdächtigt Max, dass Max die Briefe von Alice und Bob abfängt. In einigen Testbriefen war der Umschlag bereits geöffnet. Also grübelt Alice nach einer alternativen Kommunikationsmöglichkeit. Bob sucht im Internet nach Möglichkeiten, eine Geheimschrift zu entwickeln. Allerdings ist Bobs Schrift so sonderbar ausgeprägt, dass man glaubt, seine normale Schrift wäre bereits eine Geheimschrift. Also sucht er, als leidenschaftlicher Mathematiker, nach einer Möglichkeit, seinen Text zu verschlüsseln. Er probiert es mit Rotation. Aus dem Geschichtsbuch hatte er gelernt, dass sich auch Julius Cäsar dieser einfachen Methode bediente. Eine Rotationsverschlüsselung (häufig auch als ROT-n bezeichnet) rotiert die Buchstaben des Alphabets um n Stellen weiter. Zum Beispiel wird bei Anwendung von ROT-1 der Buchstabe ‚a’ zum Buchstaben ‚b’. Allerdings könnte man mit der sogenannten „Brute-Force“-Methode (engl. für „rohe Gewalt“) jede der 25 Möglichkeiten ausprobieren und überprüfen, bei welchem Schlüssel (n) ein sinnvolles und lesbares Wort herauskommt. Bob stößt auf das RSA-Verfahren. Er liest sich in einem Mathematikbuch an, dass jeder Benutzer einen öffentlichen Schlüssel und einen privaten Schlüssel berechnet. Es gibt also zwei Schlüssel. Die Theorie besagt, dass Bob jedem seinen öffentlichen Schlüssel geben könnte. Seinen privaten Schlüssel gibt er weder Alice noch sonst irgendwem. Obwohl der öffentliche Schlüssel mathematisch und logisch mit dem privaten Schlüssel zusammenhängt, ist es momentan nicht möglich, aus dem öffentlichem Schlüssel den privaten Schlüssel zu schließen. Bob fragt seinen Großvater, einen renommierten Mathematik-Professor, was passieren würde, wenn jemand den Algorithmus errät. Er antwortet, dass der Algorithmus jedem zur Verfügung steht, der sich für ihn interessiert. Er steht in vielen Büchern und im Internet. Denn gemäß Kerckhoffs’ Maxime besteht die Herausforderung der Entwicklung einer guten Verschlüsselungsmethode nicht in der Geheimhaltung des Algorithmus, sondern in der der Schlüssel. Weder der Algorithmus, noch, wenn vorhanden, der/die anderen Schlüssel dürfen auf einen Schlüssel folgern lassen. Dies ist bei dem RSA-Verfahren durch ein bis heute ungelöstes mathematisches Problem gegeben. Primzahlen begeistern die Menschen schon immer. Sie weisen nach dem heutigen Forschungsstand keine feste Struktur auf und sind geheimnisvoll, was sich die Erfinder des Algorithmus zunutze machten. Die Theorie besagt, dass es zwar möglich ist, Wasser und Kaffeepulver durch einen Filter zu gießen, es aber wiederum nicht möglich ist, das entstandene koffeinhaltige Endprodukt wieder in seine eigentlichen Bestandteile zu trennen. Es ist möglich, um die Zahl N zu erhalten, zwei Primzahlen p und q zu multiplizieren. Es ist wiederrum bei einem großen Modul nicht in absehbarer Zeit die Zahl N in ihre ursprünglichen Primfaktoren p und q zu zerlegen. Man sollte aber beachten, dass der private Schlüssel zwar indirekt mit den Primfaktoren p und q zu tun hat, allerdings werden alle in 2.2 folgenden Berechnungen unter anderem mit N durchgeführt. Die Primfaktoren p und q sollte man also schnell entsorgen, weil sie nach der Berechnung des sogenannten RSA-Moduls N keinen Wert mehr erfüllen. Bob hilft Alice, einen öffentlichen und einen privaten Schlüssel zu berechnen. Natürlich hält Bob sich bei der Betätigung der Ergebnistaste des Taschenrechners bei der Berechnung des privaten Schlüssels von Alice die Augen zu. Bob notiert sich Alice’ öffentlichen Schlüssel. Auch Bob errechnet seine Schlüssel und händigt Alice seinen öffentlichen Schlüssel aus. Die beiden verabschieden sich und probieren das Verfahren heimlich in der Mathematikstunde aus. Dann hätten sie bei einer Entdeckung des geheimen Nachrichtenaustausches durch den Lehrer wenigstens das Motiv, dass sie sich lieber mit höherer Mathematik als mit Trigonometrie beschäftigen. Bob möchte Alice eine romantische Liebesbotschaft per Zettel übermitteln. Für die Verschlüsselung benötigt er den öffentlichen Schlüssel von Alice. Mit dem RSA-Verfahren kann nämlich nur gezielt an einen bestimmten Empfänger verschlüsselt werden. Eine verschlüsselte Flaschenpost ist also ohne Beilage des privaten Schlüssels nicht möglich. Wenn Partner A mit dem öffentlichen Schlüssel von Partner B eine Nachricht für Partner B verschlüsselt, kann auch nur Partner B diese Nachricht entschlüsseln, weil nur er im Besitz seines privaten Schlüssels ist. Ein Angreifer könnte zwar die Nachricht abgreifen, aber er könnte mit seinem privaten Schlüssel nichts anfangen, weil die Nachricht mit dem öffentlichen Schlüssel von Partner B, nicht mit dem des Angreifers, verschlüsselt worden ist. Bob konvertiert anschließend seine vor Romantik strotzende Nachricht in Zahlen, indem er die Buchstaben in ihre Stellung im Alphabet übersetzt. Der Buchstabe ‚a’ wird zum Beispiel zu 1, ‚b’ wird zu 2 und ‚c’ wird zu 3. Darauffolgend berechnet er den verschlüsselten Text, in dem er Wort für Wort mit dem öffentlichen Schlüssel von Alice verschlüsselt und einen Bindestrich als Trennzeichen und zwei aufeinanderfolgende Nullen als Leerzeichen benutzt. Nun zerknüllt er einen Zettel, auf dem seine im wahrsten Sinne des Wortes kryptische und durch Bindestriche getrennte Zahlenfolge steht. Alice empfängt seine Botschaft und versucht, seine Nachricht mit ihrem privaten Schlüssel zu entschlüsseln. Als Alice im Gesicht rot wird und lächelt, vermutet Bob, dass Alice die Nachricht mit ihrem privaten Schlüssel korrekt entschlüsselt hat. Seitdem schreiben beide viele verschlüsselte Briefe. Einige davon wurden zwar wieder geöffnet, aber anscheinend ohne Erfolg, denn Max hat keine Beweise veröffentlicht und stattdessen das Liebesgerücht dem Gerücht weichen lassen, dass Alice und Bob zwei Freaks sind, die mit Zahlen kommunizieren.

[...]