RSA-Algorithmus. Thematische und mathematische Grundlagen und Schlüsselerzeugung


Hausarbeit (Hauptseminar), 2019
21 Seiten, Note: 1,7

Leseprobe

Inhalt

1. Einleitung

2. Idee von Public-Key-Kryptosystemen
2.1 Eigenschaften der Public-Key-Verschlüsselung
2.2 Die elektronische Signatur

3. Zahlentheoretische Grundlagen von Public-Key-Kryptosystemen
3.1 Modulo Rechnung
3.2 Satz von Euler und dessen Folgerungen
3.2.1 Die Eulersche- Phi (φ)- Funktion
3.2.2 Der Satz von Euler und seine Folgerungen
3.3 Erweiterter Euklidischer Algorithmus
3.3.1 Satz von der Vielfachsummendarstellung
3.3.2 Satz von modularen Inversen
3.4 Lösen einer linearen diophantischen Gleichung

5. RSA- Algorithmus
5.1 Erzeugung des öffentlichen und privaten Schlüssels
5.2 Verschlüsselung von Nachrichten
5.3 Entschlüsselung von Nachrichten

6. Die Stärke des RSA- Algorithmus
6.1 Sicherheit des RSA- Algorithmus
6.3 Anwendbarkeit des RSA- Algorithmus

7. Literatur

I Abbildungen

Abbildung 1 - Asymmetrisches Verschlüsselungsverfahren

Abbildung 2 - Algorithmus 2.1 – Public-Key-Kryptosystem

Abbildung 3 - Briefkästen

Abbildung 4 - Werte von 0 bis 99 der φ-Funktion

Abbildung 5 - Aussagen über φ-Funktion von Primzahlen

Abbildung 6 - Satz von Euler

Abbildung 7 - euklidischer Algorithmus

Abbildung 8 - euklidischer Algorithmus für nichtnegative Zahlen

Abbildung 9 - Schlüsselerzeugung im RSA Algorithmus

1. Einleitung

1977 nahmen Ronald Rivest, Adi Shamir und Leonard Adleman die Herausforderung an und entwickelten ein Public-Key-Kryptosystem, welches alle Erwartungen erfüllen sollte. Der Name dieses Verschlüsselungssystems setzt sich aus teilen der Nachnamen der Erfinder zusammen und wird als RSA-Algorithmus bezeichnet. In dieser Hausarbeit soll auf die Grundlagen, die Idee und spezielle Berechnungen eingegangen werden, um das RSA-Verfahren vollkommen zu verstehen. Es handelt sich hierbei um ein sogenanntes asymmetrisches Verschlüsselungsverfahren, welches 1976 von Whitefield Diffle und Martin Hellmann in ihrer Arbeit „New Directions in Carthography“ vorgeschlagen wurde, um Probleme bisheriger symmetrischer Verschlüsselungsverfahren zu lösen (Beutelspacher 20099: 93). Diese Probleme waren, dass beim Chiffriersystem (Verschlüsselungssystem) jeder, der verschlüsseln kann, auch entschlüsseln kann und je zwei Partner einen gemeinsamen geheimen Schlüssel, über teils unsichere Wege, austauschen müssen. In asymmetrischen Verfahren versuchte man sich von der zuerst genannten Eigenschaft soweit wie möglich zu entfernen, um zu garantieren, dass der Schlüsselaustausch von geheimen Schlüsseln nicht mehr stattfinden muss (ebd.)

Das, von den in der Einleitung genannten Wissenschaftlern, erfundenen Programm war eine große Herausforderung. Es dauerte mehrere Monate ehe man sicherstellen konnte das der vorhandene Algorithmus wirklich sicher ist. Rivest machte immerzu neue Vorschläge, wie man anders Ver- und Entschlüsseln könnte und Adlemann griff diese neuen Ideen an, während Shamir beide mit seinen Ideen unterstützte. Schließlich gelang es den drei Forschern im Mai 1977 zur Erkenntnis zu gelangen, wie man mit einfachen zahlentheoretischen Grundlagen das vorhandene Problem löste und endlich ein Public-Key-Kryptosystem entwickelte, welches wirklich sicher war. Hierfür benötigten sie ein bisschen Mathematik, unter anderem den Satz von Euler, die Modulo-Rechnung, das lösen einer linearen diophantischen Gleichung und den erweiterten euklidischen Algorithmus. Nun sollen diese mathematischen Grundlagen, sowie die Idee solcher asymmetrischen Verschlüsselungsverfahren zunächst genauer beleuchtet werden, ehe man sich speziell dem Chiffriersystem des RSA-Algorithmus zuwenden kann (ebd.).

2. Idee von Public-Key-Kryptosystemen

Im Folgenden sollen alle Instanzen und Eigenschaften von Public-Key-Kryptosystemen erläutert werden, wodurch man erst die Notwendigkeit eines solchen Verfahrens versteht.

2.1 Eigenschaften der Public-Key-Verschlüsselung

Sei Ti i={1, … ,n} die Anzahl der Teilnehmer an einer Konversation. Jeder Teilnehmer Ti hat einen öffentlichen Schlüssel E= ETi , i={1, … ,n} und einen privaten Schlüssel D=DTi i={1,…,n}. Wie die Namen schon sagen, ist der öffentliche Schlüssel für alle Teilnehmer frei zugänglich, während der private Schlüssel geheim ist. Man kann sich hierbei vorstellen, dass jeder Mensch den öffentlichen Schlüssel, des jeweiligen Kommunikationspartners, in einer Art Telefonbuch ablesen kann. Die Bezeichnungen kommen von den Begriffen Encryption und Decryption, welche Ver- bzw. Entschlüsseln bedeuten und aus dem griechischen stammen. Sei nun m die Nachricht, die der Absender schreibt und welche noch im Klartext, also unverschlüsselt, vorzufinden ist. Man bezeichne c als verschlüsselte Nachricht und schreibt somit auch c=E(m) (Beutelspacher 20099: 94). Die entscheidende Eigenschaft eines asymmetrischen oder Public-Key-Kryptosystems wird hier deutlich, denn mit dem öffentlichen Schlüssel kann der private Schlüssel nicht erzeugt werden. Diese Eigenschaft ist essentiell, um ein Kryptosystem als asymmetrisch betiteln zu dürfen (Bundesamt für Sicherheit in der Informationstechnik 2019: o.S.). Somit können wir folgende Definition festhalten: „Ein asymmetrisches Kryptosystem heißt Public-Key-Verschlüsselungssystem oder asymmetrisches Verschlüsselungsverfahren, falls für jede Nachricht m gilt: Wenn c = E(m) ist, dann gilt D(c) = m“ (Beutelspacher 20099: 94). Das bedeutet also, dass D die Wirkung von E rückgängig macht und somit D(E(m)) = m ist. Im folgenden Beispiel sollen die vorausgegangenen Definitionen verständlich gemacht werden:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Asymmetrisches Verschlüsselungsverfahren (Beutelspacher 20099: 95)

Die junge Dame, welche wir im ab sofort Anna nennen möchte eine Nachricht an Bernd schicken. Hierfür sucht sie aus einer Art Telefonbuch den öffentlichen Schlüssel EB von Bernd und wendet diese Chiffrierfunktion auf ihre geschrieben Nachricht m an. Somit erhält sie den Geheimtext c und kann diesen nun Bernd übermitteln. Dieser wendet seinen privaten bzw. geheimen Schlüssel DB auf die verschlüsselte Nachricht c an und erhält somit wieder die, von Anna geschriebene Nachricht m. Niemand anderes kann somit die verschickte Nachricht entschlüsseln und damit lesen, da man nach Voraussetzung von EB nicht auf DB schließen kann (ebd.). es ergibt sich zusammenfassend folgender Algorithmus:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Algorithmus 2.1 – Public-Key-Kryptosystem (Beutelspacher 20099: 96)

Es wurden hierbei also nur Schlüssel vom Empfänger der Nachricht, in dem Fall Bernd, verwendet und es ist kein Schlüsselaustausch notwendig, da Anna nur den öffentlichen Schlüssel von Bernd benötigt und keinen eigenen. Ein entscheidender Vorteil im vergleich zu symmetrischen Verschlüsselungsverfahren. Des Weiteren werden hier deutlich weniger Schlüssel verwendet: Beispielsweise müssten bei 1001 Teilnehmern 2002 Schlüssel vorhanden sein, während bei symmetrischen Verfahren 1/2n(n-1) = 500.500 Schlüssel benötigt werden. Ein weiterer positiver Effekt ist, dass neue Teilnehmer problemlos hinzugefügt werden können, was bisher nicht der Fall war (ebd.). Jedoch haben Public-Key-Kryptosysteme auch Nachteile, der größte ist wohl, dass bisher kein Kryptoverfahren bekannt ist, welches sowohl sicher, als auch schnell ist. Das bedeutendste ist der RSA-Algorithmus, weshalb werden wir später sehen. Außerdem benötigt man ein gewisses Schlüsselmanagement, wie man am folgenden Beispiel gut erkennen kann:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Briefkästen (Beutelspacher 20099: 96)

Wenn man sich vorstellt, dass verschiedene Absender in die Briefkästen, der jeweiligen Kommunikationspartner, Briefe wirft, dann wendet er beim rein werfen den öffentlichen Schlüssel des Empfängers an. Nur dieser kann mit dem Briefkastenschlüssel (geheimen Schlüssel) die Post herausholen und somit lesen. Was ist aber, wenn jemand auf einen Briefkasten einen anderen Namen klebt? Also beispielsweise der Name J.C. Fisher sich plötzlich auf dem Briefkasten von Dr. No befindet? Dann kann Dr. No alle Briefe lesen, die für J.C. Fisher bestimmt sind, ohne seinen geheimen Schlüssel zu kennen, da schon der falsche öffentliche Schlüssel verwendet wurde. Damit dies in der Praxis nicht geschieht gibt es sogenannte Zertifikate. Um sowas sinnvoll zu machen gibt es eine dritte Instanz, die überprüft, ob öffentlicher Schlüssel und Name des Empfängers zusammenpassen. Diese vertrauliche Partei wird Trustcenter oder Certification Authority (CA) genannt. Nachdem sichergestellt ist, dass Name und öffentlicher Schlüssel zusammen gehören signiert das Trustcenter mit seinem privaten Schlüssel das Paar. Diese Gesamtheit von öffentlichem Schlüssel, Name vom Empfänger und Signatur des Trustcenters bezeichnet man dann als Zertifikat (Beutelspacher 20099: 123f). Nun stellt sich die Frage was genau solch eine elektronische Signatur eigentlich ist und ob sie nur vom Trustcenter eingesetzt wird oder allgemein von Bedeutung ist.

2.2 Die elektronische Signatur

Jeder Mensch hat seine eigene, ganz persönliche Unterschrift und so ist es auch bei der elektronischen Signatur. Im Idealfall sollte jede Unterschrift folgende Eigenschaften haben:

i. Nur die jeweilige Peron kann die Unterschrift produzieren
ii. Jeder andere kann verifizieren, dass die Unterschrift von der Person X stammt

Somit benötigt jede Person ihr ganz spezielles Geheimnis, damit kein anderer diese Unterschrift (re-)produzieren kann. Genau dieses Geheimnis ist bei Verschlüsselungsverfahren der schon angesprochene geheime Schlüssel D. Wenn Anna also seine Nachricht m signieren will, so geht sie folgendermaßen vor: Sie wendet zunächst ihren privaten Schlüssel D auf die Nachricht m an und veröffentlicht diese signierte Nachricht sig = DA(m). Jeder andere Teilnehmer, in unserem Beispiel Bernd, wendet den öffentlichen Schlüssel EA von Anna auf die signierte Nachricht an und erhält wiederum m. Beim RSA-Verfahren überprüft man, ob EA(sig) = EA(DA(m)) = m gilt. Um dies durchzuführen wird entweder die Nachricht m veröffentlicht und so verglichen ob es stimmt oder, was meist der Fall ist, wird die Nachricht m nicht veröffentlicht, sondern man schaut nach, ob die der Nachrichtenrückgewinnung ein sinnvoller Text herauskommt. Dies hat natürlich als grundlegende Voraussetzung, dass m nicht eine sinnlose Aneinanderreihung von zufällig gewählten Zeichen ist, sondern wirklich eine sinnvolle Zeichenabfolge. Dies wird als Beweis akzeptiert, sodass keine Unsicherheiten bleiben. Hierbei ist es wichtig zu sehen, dass wieder kein Schlüsselaustausch stattfindet, sondern nur die Schlüssel des Senders verwendet werden (Beutelspacher 20099: 98ff). Es gibt jedoch einen Unterschied zwischen der elektronischen Signatur und einer normalen Unterschrift. Während die digitale Signatur nicht vom Text trennbar ist, kann eine normale Unterschrift unabhängig verwendet werden und der elektronischen Signatur sogar noch hinzugefügt werden. Außerdem bleibt die digitale Signatur immer gleich, da die Schlüssel sonst nicht mehr zueinander passen würden, während sich die normale Unterschrift im Laufe des Lebens häufiger im Detail verändert (ebd.).

Nachdem wir nun die Theorie beleuchtet haben bleibt nur noch die Frage wie so ein Public-Key-Kryptosystem in der Realität umgesetzt werden kann. Dafür müssen wir zunächst alle zahlentheoretischen Grundlagen betrachten, ehe wir dazu kommen selbst zu Ver- und Entschlüsseln.

3. Zahlentheoretische Grundlagen von Public-Key-Kryptosystemen

3.1 Modulo Rechnung

Die Modulo Rechnung bildet die Grundlage für fast alle Public-Key-Kryptosysteme. Hierbei geht es darum, dass wir eine ganze Zahl mit ihrem Rest identifizieren wollen, der bei Division, durch eine andere ganze Zahl, entsteht. D.h. wir teilen eine ganze Zahl n1 durch eine andere n2 und nehmen als Lösung nicht die ganze Zahl n3, sondern den Rest r, der dabei herauskommt. Man schreibt: n1 mod(n2) = n3 Rest r. Ein Beispiel für eine Aufgabe der Modulo- Rechnung wäre die Aufgabe 17:5. Jeder weiß, dass 17 geteilt durch 5 keine ganzzahlige Lösung hat. Wenn wir nun 17 mod (5) rechen schauen wir zunächst, „wie oft die 5 in die 17 reinpasst“. 5+5+5= 15, nochmal 5 addiert würde mehr als 17 ergeben. Die fünf passt also dreimal in die 17. Und von der 15 zur 17 fehlen 2, was dem Rest r entspricht. Somit ist 17 mod(5) = 2. Weitere Regeln zur Modulo Rechnung sind:

...

Ende der Leseprobe aus 21 Seiten

Details

Titel
RSA-Algorithmus. Thematische und mathematische Grundlagen und Schlüsselerzeugung
Hochschule
Friedrich-Schiller-Universität Jena  (Mathematik und Informatik)
Veranstaltung
Kryptologie Seminar
Note
1,7
Autor
Jahr
2019
Seiten
21
Katalognummer
V458228
ISBN (eBook)
9783668898936
ISBN (Buch)
9783668898943
Sprache
Deutsch
Schlagworte
RSA, RSA- Algorithmus, Satz von Euler, lineare diophantische Geichung, euklidischer Algorithmus, erweiterter euklidischer Algorithmus, Vielfachsummendarstellung, modulare Inverse, Schlüsselerzeugung RSA, Verschlüsselung RSA, Entschlüsselung RSA, Public-Key-Kryptosysteme, asymmetrisches Verschlüsselungsverfahren, Geschichte RSA
Arbeit zitieren
Felix Busch (Autor), 2019, RSA-Algorithmus. Thematische und mathematische Grundlagen und Schlüsselerzeugung, München, GRIN Verlag, https://www.grin.com/document/458228

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: RSA-Algorithmus. Thematische und mathematische Grundlagen und Schlüsselerzeugung


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