RSA-Verschlüsselung am Beispiel erklärt

Grundlagen der RSA-Verschlüsselung

• Bei der RSA-Verschlüsselung handelt es sich um ein System, um Nachrichten zu codieren. Dieses ist nach den Urhebern, Rivest, Shamir und Adleman, benannt worden.
• Grundlage einer jeden Kodierung ist, dass eine Nachricht - bildlich gesprochen - mit einem Schloss versehen wird. Möchte man diese Nachricht lesbar machen, benötigt man den passenden Schlüssel zu dem jeweiligen Schloss.
• Bei der RSA-Verschlüsselung existieren nun zwei Begriffe: der private und der public key. Beim private key handelt es sich um den geheimen Schlüssel und beim public key um einen öffentlichen Schlüssel.
• Zweck hierbei ist, dass ein Empfänger eine mit einem public key verschlüsselte Nachricht mit seinem private key entschlüsseln kann. Demgegenüber kann eine von einem Sender mit private key verschlüsselte Nachricht nur mit dem dazugehörigen public key geöffnet werden. Dieses Zwei-Schlüssel-System ist ein asymmetrisches Verfahren.
• Damit die RSA-Verschlüsselung funktioniert und ein Schlüssel erstellt werden kann, bedarf es sogenannter Einwegfunktionen. Dabei handelt es sich um einfache Berechnungen, die jedoch nur schwer nachzuvollziehen und rückgängig zu machen sind.
• Die bei der RSA-Verschlüsselung zugrunde liegende Einwegfunktion ist die Multiplikation zweier Primzahlen p und q. Diese sollten möglichst groß sein und geheim gehalten werden. Das Produkt N dieser Zahlen wird veröffentlicht als public key.
• Zusätzlich dazu existieren noch die Zahlen e und d. E wird dem public key beigefügt und sollte teilerfremd zur Gleichung (p-1)*(q-1) sein. Bei d handelt es sich indes um den private key, der über die Gleichung e*d=s*(p-1)*(q-1)+1 ermittelt wird. S ist dabei eine beliebig wählbare Zahl, wobei d am Ende glatt sein muss.
• Nun bedarf es noch der Nachricht selbst. Diese kann durch beliebige Zahlen verschlüsselt werden, wobei häufig der ASCII-Code verwendet wird. Es ergibt sich die Formel C = M^e mond N. M ist dabei der Klartext und C die Verschlüsselung. Umgekehrt wird eine Nachricht über M = C^d mod N entschlüsselt.

Das System an einem Beispiel erklärt

• Das Beispiel für die RSE-Verschlüsselung ist nach den eingängigen Bemerkungen recht einfach erklärt. Einigt man sich nun beispielsweise auf die Primzahlen p=43 und q=71, erhält man zunächst N=3053.
• E als teilerfremde Zahl zu (p-1)*(q-1), also 2940, würde etwa zu e=11 führen. Denn 2940 ist nicht durch 11 teilbar.
• D ergibt sich nun aus der Gleichung 11*d=s*2940+1. Diese Gleichung wird zunächst nach d umgestellt, sodass man (s*2940+1)/11=d erhält. Wählt man als beliebige Zahl für s=7, erhält man d=1871.
• Ein Klartext-Buchstabe, zum Beispiel M, wird hierbei mit einer Zahl belegt, beispielsweise 5. Kennt man nun die öffentlichen Schlüssel, ergibt sich die Gleichung: 5¹¹ mod 3053. Als verschlüsselter Buchstabe C ergäbe sich aus M die Zahl 1496.
• Jeder, der nun über d verfügt, kann eine mit e und N verschlüsselte Nachricht auch wieder entschlüsseln. Zum Entschlüsseln von 1496 würde nun d benötigt werden. Nach der Gleichung M = 1496¹⁸⁷¹ mod 3053 ergibt sich für M wieder die Zahl 5.