Harry Feldmann: Kap.1

Das Prinzip des RSA-Verfahrens besteht darin, daß man leicht, in wenig Rechenzeit, aus zwei geheimzuhaltenden großen Primzahlen p,q das öffentlich bekanntzugebende Produkt n=p*q berechnen kann, aber nur sehr schwer, in ggf. zu langer Rechenzeit, die öffentlich bekannte Zahl n wieder in ihre beiden geheimen Primfaktoren p,q zerlegen kann. Sein Reiz besteht darin, daß der erforderliche Aufwand zur "Faktorisierung" (uns) bisher nicht bekannt ist. Man nimmt an, daß eine Zahl n von mindestens 1024 Binärstellen mit heutiger Rechner-Technologie nicht "faktorisiert" werden kann.

Das RSA-Verfahren verschlüsselt und entschlüsselt nur Zahlen in Zahlen, d.h. als Vorlauf - und umgekehrt als Nachlauf - muß der Klartext P (Plaintext) mit einem öffentlich bekannten Code-Alphabet in eine Zahlenfolge E (numerical Encoding) übersetzt werden. Für einführende Beispiele wählt man z.B. den kurzen Code

mit den Zahl-Indizes 0..26 und z.B. das öffentlich bekannte Füllzeichen (fill) ' ', z.B. auf Index 0. Außerdem sollten entsprechend der modularen Arbeitsweise des RSA-Verfahrens jeweils so viele Zahlen mit jeweils führenden Nullen zu einem Block aneinandergereiht werden, daß der Block gerade noch kleiner ist als der Modul n. Alle Blöcke müssen gleich lang sein, d.h. die Blocklänge wird bestimmt durch den größten Index des Text-Codes, z.B. 26. Der letzte Block muß ggf. mangels weiterer Klartext-Zeichen mit Füllzeichen aufgefüllt werden.

Die Blöcke M der Nachricht (Message) werden verschlüsselt in Blöcke C der chiffrierten Nachricht (Ciphertext) durch

Zur Bestimmung von n,e,d werden zwei voneinander verschiedene große Primzahlen p,q gewählt. Der öffentliche Schlüssel e wird relativ prim (teilerfremd) zu ((p-1)(q-1)) gewählt und der geheime Schlüssel d als ((p-1)(q-1))-modulare Inverse von e, d.h. e*d mod ((p-1)(q-1)) = 1. Eine kurze Übersicht über modulare Arithmetik findet der Leser in 3.1. Der Beweis dafür, daß die Entschlüsselung der Verschlüsselung von M wieder auf M zurückführt, d.h. (M^e mod n)^d mod n = M, wird in 3.2.2 geführt. Der effiziente Reduktions-Algorithmus zur Berechnung der modularen Potenzen M^e mod n und C^d mod n wird in 3.3.3 als Java-Programm dargestellt.

In Lehrbüchern bemüht man sich, dem Leser das RSA-Verfahren durch Schematisierung verständlich zu machen und an Hand von ausgewählten Beispielen zu erläutern. Wir nutzen den Vorteil der interaktiven Arbeit mit Applets und der sich daraus ergebenden Möglichkeit, selbst Beispiele durchzurechnen. "Das Beste an der Theorie sind immer die selbst durchgerechneten Beispiele" oder wie Goethe sagt: "Grau, teurer Freund, ist alle Theorie, Und grün des Lebens goldner Baum" (Faust, Der Tragödie erster Teil, Schüler-Szene).

Java scheint mit seiner Klasse Biginteger, die seltsamerweise in keinem der bekannten Java-Lehrbücher direkt erwähnt wird, von Anfang an (1996) "maßgeschneidert" zu sein auf das RSA-Verfahren (1977). Die effizienten modularen Methoden der Klasse BigInteger werden in 3.3 dargestellt. BigInteger-Zahlen sind nicht beschränkt auf die interne Zahldarstellung der bisherigen 32-Bit -Rechner oder künftigen 64-Bit-Rechner und erfordern auch keine Reihungs-Techniken, sondern ermöglichen das direkte Rechnen mit beliebig großen Zahlen, z.B. mit mehr als 1024 Bit, wie dies heute aus Gründen der Sicherheit für das RSA-Verfahren verlangt wird.

Die Java-Applets 1 (unten) und 2 (Kap.2) arbeiten mit BigInteger-Zahlen, d.h. sie sind für beliebig große n zugelassen. Zur übersichtlichen Gestaltung der Benutzeroberfläche werden allerdings die sichtbaren Teile der Ein- und Ausgabetexte beschränkt. In Applet 1 ist zur Einführung ein Modul n mit 12 Bit vorgewählt, der für die sichere Verschlüsselung in der Praxis viel zu klein ist und vom Benutzer durch einen größeren Modul ersetzt werden sollte. In Applet 2 ist bereits ein hinreichend großer Modul n mit 1128 Bit voreingestellt.

Das folgende Applet 1 zeigt die Verschlüselung und Entschlüsselung des Klartextes (Plaintext) "rsa". Voreingestellt ist der öffentliche Code " abcdefghijklmnopqrstuvwxyz" mit dem öffentlichen Füllzeichen ' ' auf Index 0. Gewählt wurden die geheimen Primzahlen p=61, q=47.

Zunächst überzeugt man sich, daß n=p*q=2867 groß genug gewählt wurde, damit überhaupt innerhalb des Moduls codiert werden kann, d.h. n muß größer sein als der größte Index 26 des Codes. Danach bildet man durch Aneinanderreihung des größten Index des Codes den größten Block, der gerade noch kleiner als n ist, d.h. 2626<2867. In diesem Fall ist die Blocklänge 4 (2 Indizes mit je 2 Ziffern). Kodiert man nun den Klartext "rsa" in die Zahlenfolge E (Encoding) 18,19,01, so stellt sich heraus, daß für die Bildung von Blöcken der Länge 4 der letzte Block mit dem Füllzeichen (fill) ' ' des Codes aufgefüllt werden muß, d.h. 1819, 0100,

Apl_1: RSA-Verfahren in Java, Zahldarstellung BigInteger

Applet 1 zeigt, daß der Chiffrier-Schlüssel (encryption key) vorgewählt wurde als e=11 relativ prim (teilerfremd) zu (p-1)(q-1) =2760. Mit e werden die Blöcke M der Nachricht (Message) in Blöcke C der chiffrierten Nachricht (Ciphertext) verschlüsselt, d.h. 1819 ^11 mod 2867 = 0438, 0100^11 mod 2867 = 0202. Der Dechiffrier-Schlüssel (decryption key) d=251 wird berechnet als (p-1)(q-1)-modulare Inverse von e=11, d.h. es gilt 11*251 mod 2760 = 1. Mit d werden die Blöcke C der chiffrierten Nachricht wieder entschlüsselt in Blöcke M der ursprünglichen Nachricht, d.h. 0438^251 mod 2867 = 1819, 0202^251 mod 2867 = 0100.

Wiederaufteilung der Blöcke M in die Zahlenfolge 18,19,01,00, und Rückkodierung gemäß Code ergibt den ursprünglichen Klartext "rsa ", der allerdings wegen Blockbildung inzwischen um ein nachgesetztes Füllzeichen verlängert wurde.

Leser, die selbst mit ihrem (Taschen-) Rechner eine modulare Inverse bestimmen möchten, z.B. 11*? mod 2760=1, oder selbst eine modulare Potenz berechnen möchten, z.B. 100^11 mod 2867=?, verweisen wir auf die Beschreibung der entsprechenden effizienten Methoden in 3.3.2 oder 3.3.3.

Die Inverse wird mit dem Euklidischen Reduktions-Algorithmus zur Bestimmung des größten gemeinsamen Teilers berechnet, der als "Nebeneffekt" auch die Inverse liefert.

Bei modularen (auch mehr als zweistelligen) Multiplikationen können Zwischenergebnisse durch zusätzliche Modulbildung auf kleinere Zahlen reduziert werden (mod. Reduktion 3.1.2, 3.1.4), z.B.

     11 dezimal entspricht  1        0        1        1 binär
 100^11 mod 2867=(((1^2*100^1)^2*100^0)^2*100^1)^2*100^1 mod 2867
                =((     10000 mod 2867)^2*100^1)^2*100^1 mod 2867
                =(       1399          ^2*100^1)^2*100^1 mod 2867
                =(    1957201 mod 2867   *100^1)^2*100^1 mod 2867
                =(       1907            *100^1)^2*100^1 mod 2867
                =(     190700 mod 2867         )^2*100^1 mod 2867
                =        1478                   ^2*100^1 mod 2867
                =     2184484 mod 2867            *100^1 mod 2867
                =        2697                     *100^1 mod 2867
                =      269700                            mod 2867
                =         202

code, public alphabet=" abcdefghijklmnopqrstuvwxyz", index 0..26
p, secret prime      :47 
q, secret prime      :59 
e, public encrypt.key:17 
P  laintext          :"errare humanum est"
n, public modul      =2773 (4 Dig,12 Bit)
E  ncoding           =05,18,18,01,18,05,00,08,21,13,01,14,21,13,
                      00,05,19,20
M  essage            =0518,1801,1805,0008,2113,0114,2113,
                      0005,1920,
C  iphertext         =1787,2003,2423,0596,0340,1684,0340,
                      0508,2109,
d, secret decrypt.key=157

code, public alphabet=" abcdefghijklmnopqrstuvwxyz", index 0..26
p, secret prime      :3336670033 
q, secret prime      :9876543211 
e, public encrypt.key:1031 
P  laintext          :"sauna stoves are hot"
n, public modul      =32954765761773295963 (20 Dig, 65 Bit)
E  ncoding           =19,01,21,14,01,00,19,20,15,22,
                      05,19,00,01,18,05,00,08,15,20,
M  essage            =19012114010019201522,05190001180500081520,
C  iphertext         =25199835365382073661,04085020958227885216,
d, secret decrypt.key=31963885304131991

code, public alphabet=" abcdefghijklmnopqrstuvwxyz", index 0..26
p, secret prime      :7 
q, secret prime      :17 
e, public encrypt.key:5 
P  laintext          :"stallings"
n, public modul      =119 (3 Dig,7 Bit)
E  ncoding           =19,20,01,12,12,09,14,07,19,
M  essage            =19,20,01,12,12,09,14,07,19,
C  iphertext         =066,000,090,001,003,003,025,063,028,066,
d, secret decrypt.key=77