RSA Verschlüsseln - ein praktisches Beispiel

Aufgabenstellung: Verwenden von RSA mit fünfstelligen Primzahlen um ein Wort zu verschlüsseln und danach wieder zu rekonstruieren.

Beim RSA, benannt nach den Erfindern Rivest, Shamir und Adleman, handelt es sich um ein Public Key Verfahren.[1, p. 740]

Beim Public Key Verfahren geht es darum Nachrichten zu verschlüsseln und das Problem zu lösen wie die Parteien an die Schlüssel kommen. Und zwar nur die Parteien die diesen auch haben sollen und nicht dritte.

Dabei wird so vorgegangen, dass der Empfänger zwei Schlüssel besitzt. Zum einen den öffentlichen Schlüssel (public Key), diesen Schlüssel kann theoretisch jeder kennen. Zusätzlich zum öffentlichen Schlüssel besitzt der Empfänger noch einen nicht öffentlichen Schlüssel (private Key). Diesen kennt nur der Empfänger selbst, nicht einmal der Sender kennt diesen. Diese zwei Schlüssel werden vom gewählten Algorithmus erstellt und basieren aufeinander, so das es nicht ausreicht zum entschlüsseln den public Key zu kennen, sondern man braucht auf jeden fall den private Key dazu.

Nun möchte jemand dem Empfänger eine Nachricht zukommen lassen. Dazu besorgt der Sender sich den öffentlichen Schlüssel vom Empfänger und verschlüsselt damit und einem Verschlüsselungsalgorithmus die gewünschte Nachricht. Diese kommt nun beim Empfänger an und dieser nutzt den public Key und seinen private Key um die Nachricht wieder zu entschlüsseln. Wenn nun jemand die Nachricht abfängt und nur den public Key des Empfängers hat, kann er die Nachricht nicht entschlüsseln, da er denn dazu gehörigen private Key braucht.

Nun zur Aufgabe, der RSA Algorithmus funktioniert so, das man zunächst zwei Primzahlen wählt. In diesen Fall sind diese fünfstellig.

Primzahl_1 = 10007
Primzahl_2 = 10009

Nun summieren wir die beiden Primzahlen miteinander und summieren die Primzahlen-1.

Primzahl_Summe = 10007 10009 = 100160063
Primzahl_Summe-1 = (10007-1)
(10009-1) = 100140048

Nun wählt man eine Zahl, welche kleiner als Primzahl_Summe ist und keinen gemeinsamen Teiler mit der Primzal_Summe hat, außer 1. Also Teilerfremd sind (größter gemeinsamer Teiler 1). Dieser Wert wird e genannt, da er bei der Verschlüsselung (encryption) gebraucht wird.

e = 11 (laut [2])

Nun muss eine Zahl d (steht für Entschlüsselung – decryption) gesucht werden, welche bei e*d-1 ohne Rest durch Primzahl_Summe-1 teilbar ist.

Diese Rechenarbeit lässt sich durch ein kleines C++ Programm vereinfachen:

long e = 11;
long Primzahl_Summe_1 = 100140048;

for (long d =2; d<10000000000; d++) {
 if ((e*d-1)% Primzahl_Summe_1 == 0) {
  std::cout<<"d: "<<d<<std::endl;
  break;
 }
}

in diesen Fall ist das erste mögliche d = 36414563

Der public Key ist nun das Zahlenpaar (Primzahl_Summe, e) und der geheime Schlüssel ist das Zahlenpaar (Primzahl_Summe, d)

Public Key = (100160063, 11)
Private Key = (100160063, 36414563)

Nun haben wir alles beisammen um Nachrichten zu ver- und entschlüsseln (Länge < Primzahl_Summe).
Nun wollen wir das Wort „hallo“ ver- und entschlüsseln. Dazu interpretieren wir die Buchstaben als Zahl. a=1 bis z=26.
Hier also
h = 8
a = 1
l = 12
l = 12
o = 16

Zum verschlüsseln, Potenzieren wir nun die Zahlenwerte mit e
811 = 8589934592
111 = 1
1211 = 743008370688
1211 = 743008370688
1611 = 17592186044416

Nun berechnen wir den ganzzahligen Rest der Division von Zahlenwertee durch Primzahl_Summe. Das Ergebnis ist der Chiffretext c, welcher versendet wird.

c1 = 8589934592 % 100160063= 76329237
c2 = 1 % 100160063= 1
c3 = 743008370688 % 100160063= 21023354
c4 = 743008370688 % 100160063= 21023354
c5 = 17592186044416 % 100160063= 72579096

Das Chiffrierte Wort lautet nun

76329237 1 21023354 21023354 72579096

Wenn nun der richtige Empfänger die Nachricht bekommen hat, kann dieser diese Nachricht mit Hilfe seines private Key entschlüsseln. Dazu rechnet man

m = cd mod Primzahl_Summe

7632923736414563 mod 100160063 = 8
136414563 mod 100160063 = 1
2102335436414563 mod 100160063 = 12
2102335436414563 mod 100160063 = 12
7257909636414563 mod 100160063 = 16

Diese Zahlen nun wieder in das Alphabet gerechnet, haben wir wieder unsere Ursprüngliche Nachricht „hallo“. Das Ver- und entschlüsseln hat also funktioniert.

Quellen

[1] Kurose, J. F., Ross, K. W.: Computernetzwerke – Der Top-Down-Ansatz. Pearson, München (2012)
[2] http://www.mathepower.com/ggt.php

Back…