Verschlüsselung mit RSA

Nachdem wir nun mit Caesar und Vigenere zwei verschiedene Verschlüsselungen kennen gelernt haben, haben wir uns über die Probleme unterhalten, die diese beiden mit sich bringen. Das gravierendste ist das sogenannte Schlüsselproblem. Um eine mit Caesar oder Vigenere verschlüsselte Nachricht wieder entschlüsseln zu können, braucht der Empfänger natürlich ebenfalls den Schlüssel, den der Absender zum Verschlüsseln benutzt hat. Da der Schlüssel also auch übermittelt werden kann, kann er z.B. von einem Hacker ganz einfach abgefangen werden, der dann ganz problemlos die Nachricht entschlüsseln kann. Die Art der Verschlüsselung, bei der man mit dem gleichen Schlüssel ver- und auch wieder entschlüsseln kann, wird symmetrische Verschlüsselung genannt.Eine andere Form ist die asymmetrische Verschlüsselung, bei der es einen Schlüssel zum ver- und einen anderen um entschlüsseln gibt. RSA ist solch eine Verschlüsselung.

Das RSA-Kryptosystem ist ein sogenanntes asymmetrisches kryptographisches Verschlüsselungsverfahren. Es wurde nach den Mathematikern Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt, die 1977 nach jahrelanger Forschung auf Basis einer Theorie zur "Public-Key-Kryptografie" RSA veröffentlichten.

Hier gibt es einen sogenannten öffentlichen Schlüssel, der zum Verschlüsseln benutzt wird und einen Privaten Schlüssel, den man zum Entschlüsseln benötigt. Das Schlüsselproblem lässt sich mit dieser Verschlüsselung auf folgende Weise lösen:

Bob braucht einen neuen Computer. Er möchte ihn im Online-Shop von Alice kaufen. Deswegen schickt er Alice eine Nachricht und sagt ihr, dass er gerne einen bestimmten Rechner bei ihr erwerben möchte. Damit Bobs Bankdaten nicht für jeden abfangbar sind muss er sie Verschlüsseln, so dass nur noch Alice sie wieder entschlüsseln kann. Alice sendet Bob ihren öffentlichen Schlüssel, ihren Privaten behält sie sicher bei sich. Bob verschlüsselt nun seine wertvollen Bankdaten und schickt die Verschlüsselte Nachricht zurück an Alice. Diese braucht jetzt bloß noch mit ihrem Privaten Schlüssel die Nachricht wieder zu entschlüsseln und der Kauf kann abgewickelt werden. Bob ist glücklich, denn er hat einen neuen Computer und seine Bankdaten wurden nicht geklaut. Gleichzeitig sitzt Hacker Emil weinend im Keller seiner Eltern, denn er hat versucht Bobs Bankdaten zu klauen. Aber alles was er abgefangen hat war ein nichts sagender Schlüssel und eine Nachricht die er damit nicht entschlüsseln konnte.

So oder zumindest ähnlich funktioniert die Verschlüsselung wichtiger Daten im Internet tagtäglich. Jedes Mal wenn z.B. ein Kauf über PayPal getätigt wird, müssen sensible Informationen sicher übermittelt werden. Um das Ganze aber noch sicherer zu gestalten gibt es noch einige Anforderungen, die erfüllt werden müssen:

Verfügbarkeit, Authentizität, Vertraulichkeit und Integrität. Diese Begriffe klingen zuerst vielleicht etwas kompliziert, sie alle dienen aber ganz einfach dazu, ein wichtiges Problem, das zweite Schlüsselproblem, zu beheben. Es gibt nämlich für Emil doch eine Möglichkeit an Bobs Bankdaten zu kommen:

Bob ist zufrieden mit seinem neuen Computer, aber leider hat er vergessen sich einen passenden Monitor zu bestellen. Deshalb tritt er wieder mit seiner Lieblingshändlerin Alice in Kontakt. Emil hat davon Wind bekommen will einen Trick anwenden, um diesmal endlich an Bobs Daten zu kommen. Er fängt also Bobs Nachricht ab, in der dieser Alice dazu auffordert ihm ihren öffentlichen Schlüssel zu schicken. Emil leitet diese Nachricht an Alice weiter und fängt wiederum ihre Antwort und somit ihren öffentlichen Schlüssel ab. Dann beginnt Emils Plan erst richtig. Er lässt sich selber ein Schlüsselpaar generieren, gibt sich als Alice aus und schickt Bob dann seinen eigenen Schlüssel. Der ahnt davon nichts, verschlüsselt seine Bankdaten und schickt sie zurück an Alice, aber auch diese Nachricht fängt Emil natürlich ab. Er kann die Daten mit seinem privaten Schlüssel wieder entschlüsseln und hat nun freien Zugang zu Bobs Geld. Damit Alice davon aber nichts merkt, verschlüsselt er Bobs Daten mit ihrem öffentlichen Schlüssel, den er ja bereits abgefangen hatte und schickt diese Nachricht zurück an Alice, natürlich unter Bobs Namen. Diese entschlüsselt das Ganze wieder und wickelt unwissend den Kauf ab. So haben weder Alice noch Bob gemerkt, dass jemand sich zwischen sie geschalten und Bobs Daten geklaut hat. Emil ist stolz auf sich und kauft sich von Bobs Geld eine eigene Wohnung, damit er nicht mehr im Keller seine Eltern leben muss.

All dies hätte verhindert werden können, wenn Alice' System ausgereifter gewesen wäre. Sie hätte Bob ihre Authentizität mit Hilfe ihren elektronischen Fingerabdrucks versichern sollen, dann hätte dieser nämlich gemerkt, dass sich jemand dazwischen geschaltet hat. Dann wäre auch die Vertraulichkeit und Integrität der Nachricht gesichert gewesen. Da das aber leider nicht der Fall war und Emil seine Spuren gut verwischt hat, muss Bob jetzt in die Privatinsolvenz gehen und seinen neuen Computer plus Monitor verpfänden. 

Schlüsselgenerierung in RSA

Wie wir bereits oben gelernt haben, operiert die asymmetrische Verschlüsselung RSA mit zwei Schlüsseln, einem öffentlichen und einem privaten. Im Folgenden werde ich nun erklären, wie ein solches Schlüsselpaar generiert wird. 

Es fängt damit an, dass man sich zwei Primzahlen p und q aussucht. Also z.B. 3 und 11.

Anschließend multipliziert man diese um N zu erhalten: 

N=p*q  3*11=N  N=33

N ist also 33, das ist der erste Teil des Schlüssels. Nun möchte man (N) herausfinden. Die Formel dazu lautet: (N)= (p-1)*(q-1)

(3-1)*(11-1)=(N)

            2*10=(N)

                20=(N)

Im nächsten Schritt muss man eine zu (N) teilerfremde Zahl e herausfinden. Das funktioniert so:

20=2*2*5   Die nächst größere Primzahl ist 7, also ist 7=e

Der öffentliche Schlüssel setzt sich folgendermaßen zusammen: (N, e). Folglich ist unser öffentlicher Schlüssen also (33, 7).

Für den Privaten Schlüssel benötigt man eine Tabelle:

   e            (N)         x           R           a            b

   7             20            0            7

Hier schreibt man in die erste Zeile seine Werte für e und (N) und teilt dann nach Grundschulmanieren mit Rest. Bei 7 durch 20 kommt 0 Rest 7 raus, das schreibt man bei x und R hin.

   e            (N)         x           R           a            b

   7             20            0            7                  

  20             7             2            6

Nun zieht man das (N) aus der ersten Zeile auf die Position des e und das R auf die Position von
 (N). Dann führt man die Division wieder durch. Dies setzt man so lange fort, bis man Rest 0 erhält.
Anschließend schreibt man in der untersten Zeile für a 0 und für B 1.

   e            (N)         x           R           a            b

   7             20            0            7                  

  20             7             2            6
   7              6             1            1
   6              1             6            0           0            1

Nun wendet man folgende Formel an: b=a-(x*b). Man nimmt das a und das b aus der letzten Zeile und das x, ganz wichtig, immer aus der Zeile darüber. Hier also: b=0-(1*1)    b=-1
Das schreibt man in der vorletzten Zeile für b auf, als a wird das b aus der darunter liegenden Zeile verwendet. Also:

   e            (N)         x           R           a            b

   7             20            0            7                  

  20             7             2            6
   7              6             1            1           1           -1
   6              1             6            0           0            1

Dieses Prinzip wird bis oben fortgesetzt, also: b=1-(2*(-1))  b=3

   e            (N)         x           R           a            b

   7             20            0            7                 

  20             7             2            6          -1            3

   7              6             1            1           1           -1

   6              1             6            0           0            1

Das b in der zweitobersten Zeile ist unser wert für d. Wir haben nun also d=3. Der private Schlüssel setzt sich folgendermaßen zusammen: (N, d). Folglich ist unser privater Schlüssel also (33, 3).

Nun wo wir beide Schlüssel, also ein vollständiges Schlüsselpaar haben, können wir auch ver- und entschlüsseln. Dazu gibt es die Formeln:

Zum Verschlüsseln: G=T^e  modN  (G=Geheimtext, T=Orginaltext)

Zum Entschlüsseln: T=G^d modN


Mit der kommenden Klausur werden wir dieses Thema wahrscheinlich abschließen und uns mit einem anderen Teil der Kryptologie beschäftigen.