Warum funktioniert rsa nur wenn m kleiner n ist

RSA Verschlüsselung Definition

im Videozur Stelle im Video springen

(00:11)

Die RSA Verschlüsselung ist ein von R. Rivest, A. Shamir und L. Adleman 1977 entwickeltes asymmetrisches Verschlüsselungsverfahren, welches sowohl zum Verschlüsseln als auch zum Erstellen einer digitalen Signatur

Warum funktioniert rsa nur wenn m kleiner n ist
eingesetzt wird. Das RSA Verfahren basiert auf einem Schlüsselpaar aus einem öffentlichen Schlüssel zum Verschlüsseln und einem privaten Schlüssel zum Entschlüsseln.

RSA Verfahren

Die Mathematiker R. Rivest, A. Shamir und L. Adleman versuchten 1976 die Annahmen einer Veröffentlichung von W. Diffie und M. Hellman im Bereich der Public-Key Kryptographie zu widerlegen. Dabei fanden sie ein Verfahren, das nach ihrer Einschätzung nicht angreifbar ist. Dieses Verfahren wurde dann nach ihren Entdeckern, RSA benannt. Das RSA Kryptosystem weist mehrere Vorteile auf. Zum einen umgeht das RSA Verfahren das Schlüsselaustauschproblem, das bei symmetrischen Verschlüsselungsverfahren auftritt. Zum anderen gibt es keinen bekannten Algorithmus mit dem aus dem öffentlichen Schlüssel, der zum Verschlüsseln eingesetzt wird, der private Schlüssel, der zum Entschlüsseln verwendet wird, berechnet werden kann.

Eigenschaften

Das RSA Verfahren ist aufgrund folgender Eigenschaften als fast sicher einzustufen:

  • Ein Klartextbuchstabe wird nicht immer auf den gleichen Geheimtextbuchstaben abgebildet. Es ist also nicht monoalphabetisch.
  • Die RSA Verschlüsselung ist ein asymmetrisches Verfahren.
  • Es gibt einen öffentlichen Schlüssel der zum Verschlüsseln eingesetzt wird und einen privaten Schlüssel, der zum Entschlüsseln verwendet wird. Das RSA Verfahren stellt unter anderem deshalb einen sicheren Verschlüsselungsalgorithmus dar, da aus dem öffentlichen Schlüssel nicht der private Schlüssel berechnet werden kann.
  • Das RSA Verfahren eignet sich zur Kommunikation mit vielen Teilnehmern, da der öffentliche Schlüssel allen bekannt sein darf und somit nicht mit jedem Kommunikationsteilnehmer ein Schlüssel geheim ausgetauscht werden muss.
  • Nur der Besitzer des privaten Schlüssels kann eine Nachricht wieder einfach entschlüsseln.

RSA Verschlüsselung einfach erklärt

im Videozur Stelle im Video springen

(01:03)

Wie schon erwähnt, ist die RSA Verschlüsselung ein asymmetrisches Verschlüsselungsverfahren. Bei einem asymmetrischen Verfahren gibt es ein Schlüsselpaar aus einem öffentlichen und einem privaten Schlüssel. Der öffentliche Schlüssel wird zum Verschlüsseln eingesetzt und sollte für jeden frei zugänglich sein. Den privaten Schlüssel hingegen sollte nur der Besitzer kennen, da man nur mit diesem Schlüssel die Nachricht wieder entschlüsseln kann.

RSA Schlüssel

im Videozur Stelle im Video springen

(01:17)

Im Folgenden zeigen wir dir, wie man sich beim RSA Kryptosystem ein Schlüsselpaar mit einem öffentlichen Schlüssel und einem privaten Schlüssel erzeugen kann. Zuerst wählt man sich zwei große Primzahlen

Warum funktioniert rsa nur wenn m kleiner n ist
und
Warum funktioniert rsa nur wenn m kleiner n ist
und berechnet anschließend die Produkte

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Hierbei ist

Warum funktioniert rsa nur wenn m kleiner n ist
die Eulersche Phi-Funktion. Daraufhin sucht man sich eine Zahl
Warum funktioniert rsa nur wenn m kleiner n ist
die teilerfremd zu
Warum funktioniert rsa nur wenn m kleiner n ist
ist, sodass der größte gemeinsame Teiler von
Warum funktioniert rsa nur wenn m kleiner n ist
und
Warum funktioniert rsa nur wenn m kleiner n ist
eins ist:

Warum funktioniert rsa nur wenn m kleiner n ist

Wenn man ein solches

Warum funktioniert rsa nur wenn m kleiner n ist
wählt, dann ist
Warum funktioniert rsa nur wenn m kleiner n ist
in
Warum funktioniert rsa nur wenn m kleiner n ist
invertierbar. Somit kann man ein zu
Warum funktioniert rsa nur wenn m kleiner n ist
inverses Element
Warum funktioniert rsa nur wenn m kleiner n ist
mit folgender Formel berechnen:

Warum funktioniert rsa nur wenn m kleiner n ist

Damit hat man nun einen öffentlichen Schlüssel

Warum funktioniert rsa nur wenn m kleiner n ist
, den man für jeden frei zugänglich macht und einen privaten Schlüssel
Warum funktioniert rsa nur wenn m kleiner n ist
, den man nur selbst kennen sollte.

RSA verschlüsseln

im Videozur Stelle im Video springen

(03:17)

Um mit dem RSA Verfahren eine Nachricht verschlüsseln zu können, muss eine aus Buchstaben bestehende Nachricht zuerst in natürliche Zahlen umgewandelt werden. Hierfür wird oft der ASCII Code verwendet. Im Folgenden gehen wir davon aus, dass Bob an Alice eine geheime Nachricht senden möchte. Alice habe sich hierfür ein Schlüsselpaar mit dem öffentlichen Schlüssel

Warum funktioniert rsa nur wenn m kleiner n ist
und einem privaten Schlüssel
Warum funktioniert rsa nur wenn m kleiner n ist
erzeugt.

RSA berechnen – Verschlüsselung

Sei nun

Warum funktioniert rsa nur wenn m kleiner n ist
, die Nachricht, die Bob an Alice senden möchte. Diese Nachricht verschlüsselt Bob mit Hilfe des öffentlichen Schlüssels
Warum funktioniert rsa nur wenn m kleiner n ist
von Alice, indem er

Warum funktioniert rsa nur wenn m kleiner n ist

berechnet, wobei

Warum funktioniert rsa nur wenn m kleiner n ist
. Nachdem er
Warum funktioniert rsa nur wenn m kleiner n ist
berechnet hat, verschickt er
Warum funktioniert rsa nur wenn m kleiner n ist
an Alice.

RSA entschlüsseln

im Videozur Stelle im Video springen

(04:41)

Damit nun Alice die Nachricht von Bob entschlüsseln kann, benötigt sie eine Zusatzinformation, die der private Schlüssel enthält. Eine Funktion, die in eine Richtung leicht zu berechnen, aber sehr schwer umzukehren ist, nennt man eine Einwegfunktion. Gibt es jedoch eine Zusatzinformation, mit der die Umkehrung leicht durchgeführt werden kann, so spricht man von einer Falltürfunktion. Bei der RSA Verschlüsselung besitzt Alice gerade eine solche Zusatzinformation, mit Hilfe der die Funktion einfach umgekehrt werden kann.

RSA berechnen Entschlüsselung

Alice hat nun die Nachricht

Warum funktioniert rsa nur wenn m kleiner n ist
erhalten und möchte diese Nachricht entschlüsseln, um herauszufinden, was Bob ihr mitteilen möchte. Hierfür berechnet sie

Warum funktioniert rsa nur wenn m kleiner n ist

in

Warum funktioniert rsa nur wenn m kleiner n ist
. Wie oben schon erwähnt, gilt

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Mit einer Verallgemeinerung des kleinen Satzes von Fermat, kann man nun

Warum funktioniert rsa nur wenn m kleiner n ist
berechnen. Sei

Warum funktioniert rsa nur wenn m kleiner n ist

mit einem

Warum funktioniert rsa nur wenn m kleiner n ist
. Hiermit gilt, dass
Warum funktioniert rsa nur wenn m kleiner n ist
für alle
Warum funktioniert rsa nur wenn m kleiner n ist
. Deshalb ist insbesondere

Warum funktioniert rsa nur wenn m kleiner n ist

Mit diesem Wissen kann Alice nun den Klartext

Warum funktioniert rsa nur wenn m kleiner n ist
berechnen:

Warum funktioniert rsa nur wenn m kleiner n ist

Definiert man sich

Warum funktioniert rsa nur wenn m kleiner n ist
, dann erhält man durch einfaches Einsetzen und unter Verwendung der Verallgemeinerung des kleinen Satzes von Fermat den Klartext
Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Alice kann somit den Klartext lesen und weiß nun, was Bob ihr mitteilen möchte.

RSA Signatur

Mit Hilfe des RSA Verschlüsselungsverfahrens ist es auch möglich eine digitale Signatur zu erstellen. Eine digitale Signatur wird verwendet, um die Authentizität des Absenders zu überprüfen. Hierbei wird das Prinzip der Chiffrierung und Dechiffrierung umgedreht. Das heißt, der Absender einer Nachricht erstellt eine digitale Signatur unter Verwendung seines privaten Schlüssels und der Empfänger kann dann mit dem öffentlichen Schlüssel des Absender überprüfen, ob der Absender mit der digitalen Unterschrift übereinstimmt.

Man unterscheidet zwischen einer universellen Unterschrift und einer nicht universellen Unterschrift. Bei der universellen Unterschrift, wird wie schon beschrieben mit dem privaten Schlüssel eine digitale Signatur erstellt und an die zu übertragende Nachricht angehängt. Jeder der die Nachricht empfängt, also auch ein Dritter, der eventuell den Kommunikationskanal abhört, kann die Unterschrift mit dem öffentlichen Schlüssel des Senders überprüfen. Dies stellt jedoch meistens kein Problem dar, da die Unterschrift im Allgemeinen nicht geheim gehalten werden muss, da sie gerade dafür da ist, um die Authentizität des Senders zu überprüfen. Im Gegensatz zur universellen Unterschrift, wird bei der nicht universellen Unterschrift die digitale Signatur des Senders noch zusätzlich mit dem öffentlichen Schlüssel des Empfängers verschlüsselt, sodass nur der Empfänger die Authentizität des Senders überprüfen kann und nicht ein Dritter, der den Kommunikationskanal abhört.

RSA Verschlüsselung Beispiel

im Videozur Stelle im Video springen

(02:09)

Im Folgenden werden wir uns an einem konkreten Beispiel anschauen, wie man einen Schlüssel erzeugt, und wie anschließend Nachrichten ausgetauscht werden können.

Gehen wir wieder von Alice und Bob aus. Damit sie Nachrichten austauschen können, muss jeder von ihnen ein Schlüsselpaar aus einem öffentlichen und einem privaten Schlüssel erzeugen.

Zuerst schauen wir uns an, wie Alice ein Schlüsselpaar generiert. Gehen wir davon aus, dass Alice die Primzahlen

Warum funktioniert rsa nur wenn m kleiner n ist
und
Warum funktioniert rsa nur wenn m kleiner n ist
wählt, dann kann Alice
Warum funktioniert rsa nur wenn m kleiner n ist
und
Warum funktioniert rsa nur wenn m kleiner n ist
berechnen

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Anschließend kann sie

Warum funktioniert rsa nur wenn m kleiner n ist
und
Warum funktioniert rsa nur wenn m kleiner n ist
mit folgender Formel bestimmen

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Wählt Alice zum Beispiel

Warum funktioniert rsa nur wenn m kleiner n ist
, so folgt
Warum funktioniert rsa nur wenn m kleiner n ist
. Der öffentliche Schlüssel von Alice ist also
Warum funktioniert rsa nur wenn m kleiner n ist
und der private Schlüssel ist
Warum funktioniert rsa nur wenn m kleiner n ist
. Nun besitzt Alice ein Schlüsselpaar und ist mit der Schlüsselgenerierung fertig.

Analog erzeugt sich Bob ein Schlüsselpaar. Angenommen, Bob wählt die Primzahlen

Warum funktioniert rsa nur wenn m kleiner n ist
und
Warum funktioniert rsa nur wenn m kleiner n ist
. Dann erhält er hiermit

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Damit kann er nun

Warum funktioniert rsa nur wenn m kleiner n ist
und
Warum funktioniert rsa nur wenn m kleiner n ist
bestimmen mit

Warum funktioniert rsa nur wenn m kleiner n ist

Wählt Bob

Warum funktioniert rsa nur wenn m kleiner n ist
, dann erhält er
Warum funktioniert rsa nur wenn m kleiner n ist
. Damit ist Bob fertig mit der Schlüsselerzeugung. Er besitzt nun ein Schlüsselpaar aus dem öffentlichen Schlüssel
Warum funktioniert rsa nur wenn m kleiner n ist
und dem privaten Schlüssel
Warum funktioniert rsa nur wenn m kleiner n ist

Gehen wir davon aus, dass Alice nun Bob die Nachricht „super“, senden möchte. Dann müssen die Buchstaben zuerst in Zahlen umgewandelt werden. Hierfür werde folgende Tabelle verwendet:

Warum funktioniert rsa nur wenn m kleiner n ist
Tabelle folgt…

Wenn man das Wort „super“ mit dieser Tabelle in Zahlen ausdrückt, erhält man „super“

Warum funktioniert rsa nur wenn m kleiner n ist
„19 21 16 05 18“. Um dies verschlüsseln zu können, benötigt Alice den öffentlichen Schlüssel von Bob. Diesen findet sie zum Beispiel frei zugänglich im Internet
Warum funktioniert rsa nur wenn m kleiner n ist
. Zum Verschlüsseln werden diese Zahlen nun in Blöcke der Länge vier geschrieben, sodass man folgende Blöcke erhält „1921 1605 1800“.
Anschließend verschlüsselt Alice jeden Block mit

Warum funktioniert rsa nur wenn m kleiner n ist

in

Warum funktioniert rsa nur wenn m kleiner n ist
, sie erhält

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Daraufhin sendet Alice die Nachricht „1172 5791 3536“ an Bob und Bob entschlüsselt diese Nachricht mit

Warum funktioniert rsa nur wenn m kleiner n ist

Er erhält mit seinem privaten Schlüssel

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Warum funktioniert rsa nur wenn m kleiner n ist

Splittet Bob nun die vierer Blöcke „1921 1605 1800“ wieder in zweier Blöcke „19 21 16 05 18 00“ auf und übersetzt die Zahlen nach der obigen Tabelle in Buchstaben, so erhält er die Nachricht von Alice im Klartext „super“.

RSA Verschlüsselung – Zusammenfassung

Zum Abschluss fassen wir nun die wichtigsten Eigenschaften des RSA Verfahrens zusammen.

Das RSA Verfahren ist ein asymmetrisches Verfahren, sodass das Schlüsselaustauschproblem, das bei symmetrischen Verfahren auftritt, umgangen wird. Außerdem können mit dem RSA Verfahren Integrität und Authentizität sichergestellt werden. Denn es gibt bis heute keinen effizienten Algorithmus, der eine Zahl in seine Primfaktoren zerlegen kann. Somit ist die Verschlüsselung mit dem RSA Verfahren sicher und es ist so gut wie nicht möglich eine mit dem RSA Verfahren erstellte digitale Signatur zu fälschen. Hört ein Angreifer eine RSA verschlüsselte Nachricht ab, so benötigt er sehr viel Rechenleistung und Zeit, um die RSA Verschlüsselung zu knacken.

Dies sind die Gründe, weshalb heutzutage häufig das RSA Verfahren bei der Datenübertragung im Internet eingesetzt wird. Würde es in der Zukunft jedoch gelingen, einen Algorithmus zu entwickeln, der eine Zahl effizient in ihre Primfaktoren zerlegen kann, so ist der RSA Algorithmus nicht mehr sicher. Eine weitere Gefahr für das RSA Verschlüsselungsverfahren stellt der Quantencomputer dar. Kommt jedoch ein solcher Computer auf den Markt, dann sind vermutlich alle bis heute bekannten Verschlüsselungsalgorithmen hinfällig, da dieser über eine gigantische Rechenleistung verfügt.

Warum funktioniert das RSA Verfahren?

Die Idee und die Sicherheit des RSA-Verfahrens beruhen darauf, dass es zwar sehr leicht ist, zwei sehr große Primzahlen miteinander zu multiplizieren, andererseits jedoch ein riesiger Zeitaufwand erforderlich ist, um aus dem Produkt dieser beiden Primzahlen die Primzahlen selbst wieder zu berechnen.

Wie funktioniert im Prinzip das RSA Verfahren?

Wie schon erwähnt, ist die RSA Verschlüsselung ein asymmetrisches Verschlüsselungsverfahren. Bei einem asymmetrischen Verfahren gibt es ein Schlüsselpaar aus einem öffentlichen und einem privaten Schlüssel. Der öffentliche Schlüssel wird zum Verschlüsseln eingesetzt und sollte für jeden frei zugänglich sein.

Auf welchem mathematischen Problem basiert RSA?

Die Sicherheit des RSA-Algorithmus beruht auf dem Problem der Faktorisierung einer (großen) zusammengesetzten Zahl. Man nutzt also dabei aus, dass es leicht ist, Zahlen zu multiplizieren, dass man aber keinen Algorithmus kennt, der effizient die Primfaktorzerlegung einer beliebigen Zahl angeben kann.

Ist RSA asymmetrisch?

RSA ist ein asymmetrisches Verschlüsselungsverfahren in der Form einer Public-Key- Kryptographie (Kryptographie mit einem öffentlichen Schlüssel). Das bedeutet, das ein Schlüssel jedem bekannt sein kann. Entschlüsseln kann die Nachricht aber nur der Besitzer des geheimen privaten Schlüssels.