|
3.1 Vorbereitungen zur RSA-Verschlüsselung
|
|
Der 1978 entwickelte RSA-Algorithmus ist einer der bekanntesten sogenannten asymmetrischen Verschlüsselungsalgorithmen (auch "Public-Key-Verfahren" genannt) und auch heute noch in Verwendung. Der Name stammt von den Entwicklern des Algorithmus: Ron Rivest, Adi Shamir und Leonard Adleman. Asymmetrische Algorithmen verwenden nicht, wie viele Verschlüsselungsmethoden die wir schon aus der Kindheit kennen einen Code ("Schlüssel"), sondern zwei verschiedene, die jedoch mathematisch - je nach Algorithmus - zusammenhängen. Auch der RSA verwendet zum Ver- und Entschlüsseln von Nachrichten 2 Schlüssel: einen öffentlichen ("public key") zum Verschlüsseln und einen privaten ("private key") zum Entschlüsseln. Hier bestehen Schlüssel jeweils aus einem Zahlenpaar, das gemeinsam den öffentlichen bzw. privaten Schlüssel bildet.
Die Schlüsselerzeugung funktioniert beim RSA-Algorithmus für jedeN BenutzerIn gleich wie folgt:
- Alice denkt sich 2 Primzahlen p und q aus
- Damit berechnet Alice n = p*q und die Euler'sche Phi-Funktion Φ = (p-1)*(q-1)
- Nun sucht Alice eine Zahl e ∈ Z/ΦZ das invertierbar ist, also ggt(e,Φ)=1
- Als letztes benötigt Alice noch das multiplikative Inverse von e in Z/ΦZ und nennt es d (also d*e mod Φ = 1 + k*(p-1)*(q-1)).
Nun hat Alice alles um Public-Key-Kryptographie zu betreiben. Sie veröffentlicht das Zahlenpaar
- (e,n) als ihren öffentlichen Schlüssel und merkt sich das Zahlenpaar
- (d,n) als ihren privaten Schlüssel.
Alle anderen Zahlen und Zwischenergebnisse vernichtet sie auf sichere Art und Weise.
Lernstoff
|
|
3.2 Ablauf des RSA-Algorithmus
|
|
Der Algorithmus selbst ist von erschreckender Einfachheit. Jemand, sagen wir Bob, will Alice eine geheime Nachricht senden. Diese Nachricht sei der Einfachheit halber eine Zahl M zwischen 1 und (n-1)
Um die Nachricht zur Verschlüsseln, verwendet Bob Alices öffentlichen Schlüssel und berechnet:
Dieses C kann nun beliebig an Alice übertragen werden. Niemand ohne Kenntnis von Alice privatem Schlüssel kann aus C wieder M errechnen. Empfängt nun Alice die Nachricht C, so kann sie daraus wieder die Nachricht entschlüsseln:
Nur mit Kenntnis von d (und natürlich n) ist es möglich, C zu entschlüsseln. Umgekehrt ist es natürlich auch möglich, dass Alice mit ihrem privaten Schlüssel eine Nachricht verschlüsselt, die dann jeder mit Kenntnis des öffentlichen Schlüssel entschlüsseln kann. Dieses auf den ersten Blick vielleicht sinnlose Unterfangen wird z.B. im Bereich der digitalen Signatur verwendet. Denn so kann man Nachweisen, dass eine Nachricht nur von Alice stammen kann!
Hast du verstanden wofür wer welchen Schlüssel verwendet? Teste dich selbst!
Lernstoff, Selfchecking Test
|
|
3.4 Theoretische und praktische Ergänzungen
|
|
Überlege dir: warum muss man eigentlich nach e suchen? Warum gibt es nicht für jedes e∈Z/ΦZ ein Inverses? Notiere deine Überlegungen und Antworten ins Lerntagebuch!
Im vorigen Abschnitt findest du ein Beispiel, in dem du eine RSA-Verschlüsselung durchprobieren kannst. Dort solltest du relativ kleine Primzahlen verwenden. In der Praxis verwendet man jedoch Primzahlen p und q, die z.B. 1024 Bit Speicherplatz (oder mehr für höhere Sicherheit) zur Verfügung haben. Das sind Zahlen mit 300 Dezimalstellen. Multipliziert man p mit q, so erhält man Ergebnisse, die auch 600 Dezimalstellen haben. Hier liegt nämlich die vermutete Sicherheit des Algorithmus: dass es unmöglich ist, aus Kenntnis der Zahl n die beiden Primfaktoren p und q zu berechnen ohne alle Primzahlen von 2 bis zur Wurzel aus n auszuprobieren. Und bei derartig großen Zahlen benötigt das Probieren von Zahlen auch auf schnellen Computern viel Rechenzeit (Monate bis Jahrhunderte).
RSA zählt zur Gruppe der Algorithmen mit sogenannter "Provable Security". Seine Sicherheit beruht auf der Komplexität eines mathematischen Problems und ist somit "beweisbar". Er ist sicher, solange keine Methode gefunden wird mit der es möglich wird schnell ("deutlich besser als probieren") eine Zahl n in zwei Primfaktoren zu zerlegen.
Versuche selbst zu beweisen, warum RSA funktioniert. Wenn das nicht klappt, lies im Buch zur Lehrveranstaltung auf Seite 112 nach und schreibe den Beweis mit eigenen Gedanken dazu in dein Lerntagebuch!
Eine offene Frage ist noch, wie man eine Nachricht, die ja im Allgmeinen nicht nur eine einzelne Zahl ist, in eine solche umwandelt. Dazu muss man sich nur bewusst machen, dass für Computer alles nur Zahlen sind. Für jeden Algorithmus gibt es ja nach Implementierung viele sogenannte "Padding Schemes", die eine Vorschrift zur Verfügung stellen, wie beispielsweise Buchstaben oder Wörter in Zahlen konvertiert werden und umgekehrt. Eine einfache, aber nicht besonders sichere Variante wäre es z.B. statt einzelner Buchstaben deren ASCII-Codes zu verwenden und jeden Buchstaben einzeln zu verschlüsseln.
Hast du nun die Zahlenzusammenhänge und den Ablauf von RSA verstanden? Teste dein Wissen zu RSA!
Vertiefung, Eintrag in das Lerntagebuch, Selfchecking Test
|
Lernpfadseite als User öffnen (Login)
Falls Sie noch kein registrierter User sind, können Sie sich einen neuen Zugang anlegen. Als registrierter User können Sie ein persönliches Lerntagebuch zu diesem Lernpfad anlegen.
|
