In dieser Arbeit werden grundsätzliche Ideen von Public-Key Kryptosystemen vermittelt und erklärt wann dieses ein asymmetrisches Verschlüsselungsverfahren darstellt. Die Unterschiede zu einem symmetrischen Verschlüsselungsverfahren werden ebenfalls deutlich. Unterlegt wird diese Hausarbeit von Abbildungen aus Beutelspacher. Anschließend werden alle mathematischen Grundlagen, mit Beispielen und die wichtigen Sätze mit Beweisen, dargelegt. Es gibt wirklich für jeden Schritt des RSA- Algorithmus ein Beispiel. Zum Schluss wird dargestellt, wie nun eigentlich verschlüsselt beziehungsweise entschlüsselt wird und die Sicherheit und die Anwendbarkeit vom RSA Verfahren beurteilt.
Inhaltsverzeichnis
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
Zielsetzung & Themen
Die vorliegende Arbeit befasst sich mit den theoretischen Grundlagen und der praktischen Funktionsweise des RSA-Algorithmus als asymmetrisches Verschlüsselungsverfahren. Das primäre Ziel ist es, die mathematischen Konzepte, die diesem Verfahren zugrunde liegen, sowie dessen Implementierung und Sicherheit kritisch zu beleuchten.
- Grundlagen asymmetrischer Kryptosysteme und deren Abgrenzung zu symmetrischen Verfahren.
- Zahlentheoretische Kernkonzepte wie Modulo-Rechnung und Eulerscher Satz.
- Verfahren zur Schlüsselerzeugung mittels des Erweiterten Euklidischen Algorithmus.
- Analyse der Sicherheit des RSA-Verfahrens im Kontext der Faktorisierung großer Zahlen.
- Praktische Anwendbarkeit und Leistungsfähigkeit des Algorithmus in heutigen IT-Systemen.
Auszug aus dem Buch
6.1 Sicherheit des RSA- Algorithmus
Um die Sicherheit des Verfahrens beurteilen zu können sollte man sich zwei zentrale Fragen stellen: Kann man mit der Kenntnis des öffentlichen Schlüssels den geheimen erzeugen? und kann man dechiffrieren, ohne den geheimen Schlüssel explizit zu kennen? Arbeiten wir uns mal stetig voran: Jedermann kennt den öffentlichen Schlüssel und somit e und n. Der Angreifer weiß somit, dass er die e-te Modulare Wurzel aus dem Geheimtext berechnen muss. Damit hätte der Angreifer dann d und müsste den Geheimtext nur noch mit d potenzieren. Wenn der Angreifer hierzu φ (n) kennen würde, wäre das, mit Hilfe des euklidischen Algorithmus, kein Problem d zu berechnen.
Das Problem besteht also darin φ (n) zu berechnen. Dafür müsste der Angreifer n in seine Primfaktoren p und q zerlegen können, da φ (n) = (p-1)*(q-1) und n = p*q ist. Das bedeutet, dass der Angreifer entweder φ (n) berechnen oder n faktorisieren müsste. Bei Zahlen, wie 72, 123 oder 221 geht das noch relativ einfach, doch bei größeren Zahlen, wie 8633 ist dies schon ein Problem. Wenn man dann beachtet, dass das n beim RSA- Verfahren ca. 200 Dezimalstellen besitzt, dann wäre das schon ein enormer rechnerischer Aufwand.
Man müsste bei allen Primzahlen probieren, von 2 bis √n, ob sich n durch diese beiden darstellen lässt. Dieses Verfahren ist jedoch sehr ineffizient. Überlege man sich, dass dies bei 200 Dezimalstellen 1097 Primzahlen wären, das sind mehr als die Anzahl der Atome im Universum, versteht man weshalb dies ein Problem darstellt. Anders gesagt, es ist wahrscheinlich unmöglich! Es wurde jedoch versucht einige andere Algorithmen zu entwickeln, jedoch konnte keiner das Problem lösen. Es gibt nicht mal einen Beweis dafür, dass so ein Algorithmus überhaupt existiert. Bisher wurden nur 512 Bit lange RSA-Zahlen faktorisiert, jedoch verwendet man mindestens 1024 Bit, meist sogar 2048 Bit, lange RSA- Zahlen. Somit ist eine Entschlüsselung mit Hilfe des öffentlichen Schlüssels und mit anderen Methoden bisher nicht auffindbar. Der RSA- Algorithmus gilt somit als sicher BEUTELSPACHER 2009: 112ff).
Zusammenfassung der Kapitel
1. Einleitung: Einführung in die Geschichte und Entstehung des RSA-Algorithmus durch Rivest, Shamir und Adleman als asymmetrisches Verschlüsselungsverfahren.
2. Idee von Public-Key-Kryptosystemen: Erläuterung des Prinzips asymmetrischer Verschlüsselung, der Funktion öffentlicher/privater Schlüssel sowie des Konzepts der elektronischen Signatur.
3. Zahlentheoretische Grundlagen von Public-Key-Kryptosystemen: Detaillierte Darstellung der notwendigen mathematischen Bausteine wie Modulo-Rechnung, Eulerscher Satz, Euklidischer Algorithmus und diophantische Gleichungen.
5. RSA- Algorithmus: Beschreibung des konkreten Verfahrens zur Schlüsselerzeugung sowie der Verschlüsselungs- und Entschlüsselungsschritte anhand eines Zahlenbeispiels.
6. Die Stärke des RSA- Algorithmus: Analyse der Sicherheit basierend auf dem Faktorisierungsproblem großer Zahlen und Diskussion der praktischen Anwendbarkeit.
Schlüsselwörter
RSA-Algorithmus, Public-Key-Kryptographie, Asymmetrische Verschlüsselung, Zahlentheorie, Modulo-Rechnung, Eulerscher Satz, Euklidischer Algorithmus, Schlüsselerzeugung, Faktorisierung, Primzahlen, Elektronische Signatur, Kryptosicherheit, Diophantische Gleichungen, Entschlüsselung, Geheimtext.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die mathematischen Grundlagen und die Funktionsweise des RSA-Algorithmus, eines der bedeutendsten asymmetrischen Verschlüsselungsverfahren.
Was sind die zentralen Themenfelder?
Die Schwerpunkte liegen auf der Kryptologie, der elementaren Zahlentheorie, dem Schlüsselmanagement und der mathematischen Sicherheit von Verschlüsselungsprotokollen.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist es, den RSA-Algorithmus von der theoretischen mathematischen Basis bis hin zur konkreten Anwendung und Sicherheitsanalyse verständlich aufzuarbeiten.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt eine deduktive Herleitung mathematischer Sätze und wendet diese schrittweise auf den Algorithmus an, unterstützt durch Beispiele und Beweisskizzen.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die Vorstellung der Public-Key-Idee, die mathematische Fundierung durch den Satz von Euler und Euklidische Algorithmen sowie die praktische Durchführung der RSA-Operationen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die zentralen Begriffe sind RSA-Algorithmus, Asymmetrische Verschlüsselung, Primfaktoren, Modulare Arithmetik und Datensicherheit.
Wie unterscheidet sich RSA von symmetrischen Verfahren?
Im Gegensatz zu symmetrischen Verfahren benötigt RSA keinen gemeinsamen geheimen Schlüssel, da das Paar aus öffentlichem und privatem Schlüssel eine Einweg-Kommunikation ermöglicht.
Warum gilt der RSA-Algorithmus als sicher?
Die Sicherheit beruht auf der enormen Schwierigkeit, sehr große Zahlen in ihre Primfaktoren zu zerlegen, was für heutige Computer bei adäquater Schlüssellänge praktisch unlösbar ist.
- Arbeit zitieren
- Felix Busch (Autor:in), 2019, RSA-Algorithmus. Thematische und mathematische Grundlagen und Schlüsselerzeugung, München, GRIN Verlag, https://www.grin.com/document/458228
