Kryptographie - RSA-Verfahren

Asymmetrische Verschlüsselung
über so genannte „Public-Key-Verfahren“

Bei diesen Verfahren wird im Gegensatz zum symmetrischen Verfahren mit einem Schlüsselpaar gearbeitet. Der eine bleibt völlig geheim (private key) der andere wird allgemein bekannt gemacht (public key) und steht jedermann zur Verfügung.

Will ein Absender dem Empfänger eine vertrauliche Nachricht senden, so verschlüsselt er diese mit dem public key des Empfängers. Anschließend ist nur dieser in der Lage mit Hilfe seines private key diese Nachricht wieder zu dechiffrieren.^[1]

public key
des Empfängers

private key
des Empfängers

Beachte die elektronische Signatur wird dagegen mit dem privaten Schlüssel des Absenders chiffriert und diese kann nur mit dem öffentlichen Schlüssel des Absenders authentifiziert werden.

Das RSA-Verfahren

Diese Methode soll im Folgenden anhand des RSA-Verfahrens^[2], das im Internet eine allgemeine Bedeutung erlangt hat, dargestellt werden. Die Sicherheit dieses Verfahrens beruht letztlich darauf, dass die Mathematik - trotz jahrhundertelanger Bemühungen - keine Formel gefunden hat, mit der Primzahlen einfach und schnell berechnet werden können. Nach wie vor stehen hier nur Probiermethoden zur Verfügung. Angesichts der riesigen Anzahl der durchzuprobierenden Zahlenwerte führen diese Probiermethoden bei entsprechend langen Schlüsselwerten nicht in vernünftiger Zeit zum gewünschten Ergebnis.
(Nach den Abschätzungen der Mathematik gibt es vermutlich 10 mal mehr Primzahlen mit 512 bit Länge, als Atome im Universum.)
RSA-Verfahren Das kann kurz wie folgt beschrieben werden:^[3]

Zutaten:
öffentlicher Schlüssel zum Chiffrieren
(e : encrypt)

privater Schlüssel zum Dechiffrieren:
(d : decrypt)

p, q als zwei große Primzahlen

(e; n) wobei n = p ▪ q
und e teilerfremd zu (p - 1)∙▪ (q - 1)
mit d ▪ e = 1 mod((p – 1) ▪ (q – 1))

Der Wert der jeweils zu chiffrierenden Zeichen z (z.B. Buchstaben) der Nachricht kann nun wie folgt chiffriert und dechiffriert werden:

Chiffrieren: z' = z^e mod n

Dechiffrieren: z = z'^d mod n

Zum besseren Verständnis ein einfaches Beispiel mit praxisfremden "kleinen" Primzahlen:

1.	Man wählt zwei Primzahlen p und q	Wir nehmen 11 und 17
2.	p und q werden miteinander multipliziert, um n zu erhalten	n = 11 x 17 = 187
3.	Berechne die eulersche Phi-Funktion phi(n) = (p – 1)(q – 1)	phi(n) = (11 – 1)(17 – 1) = 160
4.	Berechne phi(n) + 1	phi(n) + 1 = 160 + 1 = 161
5.	Der Wert e wird ausgewählt, wobei d ein Teiler aus phi(z)+1 sein muss. Der zweite Teiler aus phi(n)+1 ist d. Es muss gelten: d*e=phi(z)+1 . Unzulässige Werte von d und e (z.B. d=e) werden als unsicher abgelehnt.	da 161 = 7 x 23 (Faktorisierung) sind 7 und 23 geeignete Kandidaten für e und d Wir wählen e = 7 für den public key und d = 23 für den private key
6.	Der Wert e wird zusammen mit n als öffentlicher Schlüssel definiert, der Wert d als privater Schlüssel. Der öffentliche Schlüssel, mit dem verschlüsselt wird, kann nun allgemein bekannt gemacht werden. Der private Schlüssel, muss geheim gehalten werden	der ganze public key besteht also aus zwei Zahlen, nämlich ( e; n), hier also (7; 187) der ganze private key besteht dann dem entsprechend aus den Zahlen (d; n), hier also (23; 187)

Chiffrieren: z‘ = z^d mod n	Dechiffrieren: z = z’^e mod n	z sei der Dezimalwert des jeweiligen Zeichens; so hat z.B. dem Buchstabe „H“ im ISO-Zeichensatz der Wert 72 zugeordnet


H (72) 72⁷ mod 187 = 30 A (65) 65⁷ mod 187 = 142 L (76) 76⁷ mod 187 = 32 L (76) 76⁷ mod 187 = 32 O (79) 79⁷ mod 187 = 139	30²³ mod 187 = 72 ( H ) 142²³ mod 187 = 65 ( A ) 32²³ mod 187 = 76 ( L ) 32²³ mod 187 = 76 ( L ) 139²³ mod 187 = 79 ( O )

Sind p und q genügend groß, benötigt nach dem gegenwärtigen Stand der Technik mehr als 10¹² Jahre, in denen diese Nachricht wahrscheinlich wertlos geworden ist. Genau auf dieses Verfahren greift auch die digitale Signatur zurück, mit der zukünftig die Authentizität eines Dokumentes gerichtsverwertbar bewiesen werden kann.

^[1] Quelle: http://www.oszhdl.be.schule.de/
^[2] RSA (entwickelt 1977, von den Mathematikern Ron Rivest, Adi Shamir und Leonard Adleman am MIT)
^[3] Quelle: http://www-aix.gsi.de