RSA-Algorithmus

R



Der RSA-Algorithmus wurde im Jahre 1977 von Ron Rivest, Adi Shamir und Leonard Adleman entwickelt.
Das Verfahren verwendet große Primzahlen und seine Sicherheit basiert auf der Schwierigkeit, große natürliche Zahlen in Primfaktoren zu zerlegen.
Die Verschlüsselung ist relativ einfach und leicht in verschiedenster Software zu implementieren.
RSA wurde einer intensiven Kryptanalyse, die zwar das Verfahren nicht brechen, allerdings auch keinen Beweis für die Sicherheit liefern konnte, unterzogen.
In diesem Aufsatz sollen sowohl die Einfachheit als auch die Effektivität dieser Verschlüsselungsmethode präsentiert werden. Die durchzuführenden Schritte werden nur mit einem Minimum an mathematischen Formeln beschrieben, ferner werden bewusst kleine und einfache Zahlen, die in der Realität natürlich keinesfalls anwendbar sind, verwendet.

1. Schritt: Festlegen zweier Primzahlen P und Q

Für den ersten Teil des öffentlichen Schlüssels werden zwei Primzahlen P und Q, die jeweils eine Größe von mindestens 1024 bit besitzen, benötigt.
Dabei sollen P und Q so gewählt werden, sodass das Produkt N = P.Q mehr als 300 Stellen besitzt.
Für das in diesem Artikel angeführte Beispiel werden die Werte P = 5 und Q = 17 gewählt, sodaß das Modul N = P.Q den Wert 85 besitzt.

2. Schritt: Wählen eines öffentlichen Schlüssels E

Für den zweiten Teil des öffentlichen Schlüssels wird eine Zahl E festgelegt, die folgende Bedingungen erfüllen muss:
  1. E muss kleiner als N = P.Q sein.
  2. E darf keine gemeinsamen Faktoren mit dem Produkt (P–1).(Q–1) haben.
  3. E muss zwar keine Primzahl, aber ungerade sein.
Aus den Werten P = 5 und Q = 17 ergibt sich für das Produkt (P–1).(Q–1) der Wert 64.
Da die Zahl 64 die Primfaktorenzerlegung 26 besitzt, kann für die Zahl E der Wert 3 verwendet werden.
Damit lautet der öffentliche Schlüssel E = 3 und N = 85.
Übrigens: Die in diesem Beispiel relativ einfach zu ermittelnden
Primfaktoren P und Q dürfen keinesfalls angegeben werden.

Möchte man nun beispielsweise das Wort Sparbuch verschlüsseln, so benötigt man zunächst einen Zeichensatz, der idealerweise eine Länge von P.Q = 85 Zeichen besitzt und etwa aus Leerzeichen, numerischen Ziffern, Groß– und Kleinbuchstaben sowie Umlauten und Sonderzeichen besteht, wie z.B. „0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ
abcdefghijklmnopqrstuvwxyzäöüß,;.?!+–*/§$%&()“.
Dabei wird jedem Zeichen der zu verschlüsselnden Nachricht eine Zahl, die die Position des Zeichens innerhalb des Zeichensatzes (das erste Zeichen des Zeichensatzes besitzt dabei die Position 0 !) wiedergibt, zugeordnet.

Zeichen S p a r b u c h
Position 29 55 40 57 41 60 42 47

Jetzt wird jedes Zeichen K des unverschlüsselten Klartextes mit dem Schlüssel E potenziert und anschließend der Rest bei Division
dieser Zahl KE durch das Modul N ermittelt.
Der dabei entstehende Rest C entspricht einem Zeichen des verschlüsselten Ciphertextes.
Somit ergibt sich:

Klartext-Buchstabe Klartext-Zeichen KE Rest bei Division KE/N Ciphertext-Zeichen Ciphertext-Buchstabe
S 29 293 79 79 §
p 55 553 30 30 T
a 40 403 80 80 $
r 57 573 63 63 x
b 41 413 71 71 ;
u 60 603 15 15 E
c 42 423 53 53 n
h 47 473 38 38 Ö

Die verschlüsselte Nachricht lautet daher §T$x;EnÖ.

3. Schritt: Bilden eines Geheimschlüssels D

Um einen verschlüsselten Ciphertext wieder in Klartext umzuwandeln, muss eine Zahl D derart bestimmt werden, sodass der Wert D.E – 1 ohne Rest durch das Produkt (P–1).(Q–1) teilbar ist.
Dies bedeutet, dass für eine Zahl X die Gleichung

X.(P–1).(Q–1) = D.E – 1

gelten muss.
Durch Umformung erhält man

D = [X.(P-1).(Q-1)+1]/E.

Setzt man in unserem Beispiel X = 2, so erhält man den Wert D = 43 (übrigens sollten der öffentliche Schlüssel E und der Geheimschlüssel D nicht den gleichen Wert - Stichwort: symmetrische Verschlüsselungsmethoden - haben).

Um nun einen verschlüsselten Nachrichtentext wieder zu entschlüsseln, wird jedes Zeichen C des verschlüsselten Ciphertextes mit dem Geheimschlüssel D potenziert und anschließend der Rest bei Division dieser Zahl CD durch das Modul N berechnet.
Für unsere verschlüsselte Nachricht §T$x;EnÖ gilt somit:

Ciphertext-Buchstabe Ciphertext-Zeichen CD Rest bei Division CD/N Klartext-Zeichen Klartext-Buchstabe
§ 79 793 29 29 S
T 30 303 55 55 p
$ 80 803 40 40 a
x 63 633 57 57 r
; 71 713 41 41 b
E 15 153 60 60 u
n 53 533 42 42 c
Ö 38 383 47 47 h

Zum Schluss noch ein Hinweis:

In einigen Veröffentlichungen wird beschrieben, die Stärke des
RSA–Algorithmus basiere auf der Schwierigkeit, große Primzahlen zu faktorisieren.
Dies ist ein Schreibfehler, denn Primzahlen haben – egal ob groß oder klein – nur zwei Teiler (nämlich 1 und sich selbst).
Vielmehr geht es bei diesem Verfahren um die Schwierigkeit, große natürliche Zahlen wie z.B. das Modul N zu faktorisieren, d.h. in seine Primfaktoren zu zerlegen.