Wie funktioniert die RSA-Verschlüsselung


Die RSA-Verschlüsselung bekam ihren Namen aus ihren Urhebern Rivest, Shamir und Adleman. Hierbei handelt es sich um ein asymmetrisches Verfahren, daher werden zwei Schlüssel – ein öffentlicher und ein privater Schlüssel – benötigt [1]. Da der RSA-Algorithmus nur Zahlen Verschlüssen kann, muss der Klartext zuerst in einem Zahlensystem umgewandelt werden. Zudem kann die RSA-Verschlüsselung als digitale Signatur genutzt werden [2].

Prinzip

Das Prinzip ist leicht nachzuvollziehen. Sagen wir zum Beispiel, dass Alice dem Bob eine verschlüsselte Information senden möchte. Dazu muss Bob einen öffentlichen Schlüssel generieren, der auch tatsächlich öffentlich zugänglich ist. Für die Zugänglichkeit kann Bob auch das Web nutzen. Somit können nun alle (darunter auch Alice) Bob eine Information, verschlüsselt mit dem öffentlichen Schlüssel vom Bob, zusenden. Damit die Information wieder entschlüsselt wird, braucht Bob nun noch einen privaten Schlüssel, der mathematisch aus dem öffentlichen Schlüssel resultiert. Nur dieser kann die Information korrekt entschlüsseln. Dieser muss privat bleiben, niemand außer Bob darf diesen haben.

RSA-Verschlüsselungsverfahren [3]

Für die Verschlüsselung werden folgende Parameter benötigt:

Parameter Beschreibung
m Klartext; Text vor der Verschlüsselung
c Chiffretext; Text nach der Verschlüsselung
p, q Primzahlen
n n = p \cdot q, wobei der Klartext m größer als n seien sollte
\Phi (n)  \Phi (n)=(p-1)\cdot(q-1)
e Öffentlicher Schlüssel e < \Phi (n) und kein gemeinsamer Teiler außer 1
d Privater Schlüssel

Die RSA-Verschlüsselung kann in 5 Schritten unterteil werden.

Schritt 1: Öffentlichen Schlüssel e berechnen

Wähle zwei Primzahlen  p und q aus. Aus den Primzahlen bilde das Produkt n. Je größer die Primzahlen p, q sind, je sichere das Verfahren. Im Realfall sollten die Primzahlen mehrere hundert Stellen aufweisen.

n=p \cdot q

Als Beispiel nehmen wir für p, q die 3 und 7 (im Realfall jedoch viel zu kleine Primzahlen). Das Ergebnis ist: n=p \cdot q = 3 \cdot 7 = 21.

Nun bilde ein zweites Produkt \Phi (n). Hierbei muss eine Zahl gefunden werden, die keinen gemeinsamer Teiler mit dem Ergebnis \Phi (n) hat außer 1 und kleiner wie \Phi (n) ist.

\Phi (n) = (p-1) \cdot (q-1)

e < \Phi (n)
Für unser Beispiel heißt dies: \Phi (n) = (p-1) \cdot (q-1) = (3-1) \cdot (7-1) = 12

Nun suche ich eine Zahl die kleiner als 12 seien soll und keinen gemeinsamen Teiler außer 1 haben darf. Zum Beispiel 5. Daher ist der öffentliches Schlüssel e = 5.

Schritt 2: Privaten Schlüssel d berechnen

Hierzu wird der Satz von Euler benötigt um auf die nachfolgende Formel zu kommen:

d = \frac{k \cdot \Phi (n) + 1}{e}

wobei: k\in N_{0}

Die Variabel k muss eine natürliche Zahl sein, dabei ist zu beachten das für d eine Ganzzahl resultieren muss. Daher muss man verschiedene Werte für k testen bis d eine Ganzzahl ist. Für unser Beispiel probiere ich k=1 aus: d = \frac{k \cdot \Phi (n) + 1}{e}=\frac{1 \cdot 12 + 1}{5} = 2,6. Da dies keine Ganzzahl ist, wird diese ausgeschlossen. Nun probiere ich k=2 aus: d = \frac{k \cdot \Phi (n) + 1}{e}=\frac{2 \cdot 12 + 1}{5} = 5. Ist eine Ganzzahl, daher darf ich sie nehmen. Der private Schlüssel lautet d = 5.

Schritt 3: Empfänger veröffentlicht den öffentlichen Schlüssel e und Produkt n

Weil auch das Produkt n versendet werden muss, müssen die Primzahlen p und q deutlich groß sein. Sonst könnte ein Angreifer durch leichtes ausprobieren den Algorithmus knacken.

Schritt 4: Sender verschlüsselt Information

Der Sender möchte im Beispiel die Information “TEST“ senden. Da RSA nur Zahlen versteht, müssen die Buchstaben in Zahlen umgewandelt werden, dazu nutzen wir zum Beispiel das Alphabet: Die Buchstaben von A bis Z bekommen die Werte 1 – 26. Aus “TEST“ wird somit “20 5 19 20“. Beachte vorhin hatten wir für n = 21 berechnet. Das heißt, dass wir maximal den Dezimalwert 20 (im Beispiel der Buchstabe T) bekommen dürfen. Wenn größere Zahlen benötigt werden muss n größer gewählt (über p, q) werden. Dies liegt an der Modulo-Operation welche in diesem Beispiel keine Werte größer als 20 durchlässt.

Nun nutzt der Sender den öffentlichen Schlüssel e und das Produkt der Primzahlen n des Empfängers. Zusammen mit der nachfolgenden Formel kann er nun die Information verschlüsseln:

 c = m^{{e}} \cdot mod(n)

Bsp.:  c = m^{{e}} \cdot mod(n) = 20^{{5}} \cdot mod(21) = 3200000 \cdot mod(21) = 20

Die Verschlüsselte Nachricht dezimal “20 17 10 20“ oder als Text “TQJT“.

Schritt 5: Empfänger entschlüsselt Information

Für die Entschlüsselung benötigt der Empfänger seinen privaten Schlüssel d und die nachfolgende Formel:

 m = c^{{d}} \cdot mod(n)

Bsp.:  m = c^{{d}} \cdot mod(n) = 20^{{5}} \cdot mod(21) = 3200000 \cdot mod(21) = 20

Um daraufhin die Anfangsnachricht zu erhalten: “TEST“

Zusammengefasst über der RSA-Verschlüsselung

  • RSA ist ein asymmetrisches Verschlüsselungsverfahren
  • RSA kann nur Zahlen verschlüsseln
  • Das Produkt n muss größer als der Klartext m sein
  • Die Verschlüsselungsmethode ist sehr stark. Je größer die Primzahlen die genutzt werden je sicherer der Algorithmus
  • RSA kann auch als digitale Signatur genutzt werden [2]

Literatur

[1] http://www.inf.fh-flensburg.de: RSA-Verschlüsselung.
http://www.inf.fh-flensburg.de/lang/krypto/protokolle/rsa.htm – Stand 17.05.2017
[2] https://www.zum.de: Der RSA-Algorithmus.
https://www.zum.de/Faecher/Inf/RP/infschul/kr_rsa.html – Stand 17.05.2017
[3] http://www.oberstufeninformatik.de: Das RSA-Verschlüsselungsverfahren http://www.oberstufeninformatik.de/krypto/rsavollmer.pdf – Stand 17.05.2017

 

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

*

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.