23.19 RSA |
|||||||
public key - privat key |
Wir hatten gesehen, dass alle
Verschlüsselungen bei der Chiffrierung eines Klartextes M eine Funktion Ek
mit dem Schlüssel K benutzten. Den so entstandenen Geheimtext kann
man entschlüsseln, wenn man die inverse Funktion Dk = Ek-1
kennt.
Allgemein gilt: Die Cäsarverschlüsselung (z.B. Verschieben um 3) ist durch die mathematische Operation Ek(m) = c = m+k gegeben (wir gehen davon aus, dass die Zeichen m z.B. im ASCII Code dargestellt sind, so dass numerische Operationen auf diese Zeichen anwendbar sind). Die Entschlüsselung wird dann durch die Funktion Dk(c) = m = c-k beschrieben. Wir sehen, die zum Dechiffrieren notwendige Funktion Dk ist sehr leicht aus aus der Verschlüsselungsfunktion Ek zu berechnen. Der Schlüssel wird also zwischen dem Absender und dem Empfänger ausgemacht und kein Dritter darf davon wissen (wir sehen einmal davon ab, dass eine Lauscher z.B. mit Häufigkeitsanalysen etc. sehr schnell die geheime Botschaft entschlüsseln kann). Da für Chiffrieren und Dechiffrieren der gleiche Schlüssel benutzt wird, sprechen wir auch gerne von einem symmetrischen Verschlüsselungsverfahren. Symmetrische Verfahren haben immer zwei wesentliche Unsicherheitsstellen. Zum einen muss der Schlüssel unbedingt geheim beleiben. Zum zweiten kann man aus den verschlüsselten Texten häufig den Schlüssel und damit den Originaltext z.B. durch Häufigkeitsanalysen finden. Im One-Time-Pad - Verfahren fanden wir eine Lösung, die die zweite Lücke schloss. Im folgenden wollen wir ein Verfahren kennen lernen, das die erste Lücke schließt, ein Verfahren, das zum Chiffrieren und Dechiffrieren zwei unterschiedliche Schlüssel nämlich den public key zum Chiffrieren und den private key zum Dechiffrieren benutzt. Wir sprechen dann von einem asymmetrischen Verfahren. Um den nachfolgenden Text leichter verstehen zu können, wollen wir die Person, die eine geheime Botschaft empfängt und entschlüsseln soll, wie in der Kryptologie üblich, Bob nennen. Alice heißt die Person, die einen Klartext zu einer geheimen Botschaft verschlüsselt und an Bob schickt. Eine Personen, die den Austausch der geheimen Botschaft zwischen Alice und Bob belauscht und zu entschlüsseln versucht, nennen wir Eva. Die Überlegungen Shannons haben
gefordert, dass das Verschlüsseln mittels einer bijektiven und damit
umkehrbaren Funktion geschieht. Wie kann man diese Forderung in Einklang
mit der Idee des asymmetrischen Verfahrens bringen? Die Lösung ist: Bob
sucht nach einer
Entschlüsselungsfunktion Dk, die es erlaubt, sehr leicht Ek zu bestimmen, aber umgekehrt es jemanden sehr schwer ist, ja
so gut wie unmöglich macht, Dk aus Ek zu berechnen.
Ein solches Verfahren ist RSA. |
||||||
Rivest Shamir Adleman |
RSA sind die Initialen seiner
Entwickler Ronald Rivest, Adi Shamir und Len Adleman. Es wurde 1978
entwickelt. Wir beschreiben
das Verfahren zunächst an einem einfachen Beispiel: |
||||||
Der RSA Ver-
schlüsselungs- algorithmus
|
Bob wählt zwei Primzahlen
p = 47 und
q = 59 und bestimmt deren
Produkt n = 2773 (das sog.
RSA-Modul). Aus
diesen Zahlen werden zwei Schlüssel
e = 17 (encryption key) und
d = 157 (decrytion key)
bestimmt. Wie das geht, wollen wir später beschreiben. Die beiden Zahlen n
und e gibt er allen, die ihm geheime Botschaften verschicken wollen,
bekannt. Das Ensemble (n,e) ist der sog. public key. Das Ensemble (n,d)
das Bob nicht
bekannt gibt ist dann der sog. privat key. Wenn Alice einen Text verschlüsseln wollen, übersetz sie diese Wörter in eine Folge von Zahlen (z.B. entsprechend seinem ASCII-Code und fassen den gesamten Text z.B zu 4er-Blöcken zusammen. Die Größe der Blöcke muss kleiner als n sein. So hat sie z.B. den Klartext K: 0920 1900 0112 1200 ... Sie chiffriert nun den ersten 4er Block, nämlich m = 0920, und benutz dabei : c= me mod n In unserem konkreten Fall ergibt sich somit der 948 = 92017 mod 2773. Bob erhält diese Nachricht und entschlüsselt sie mit: m = cd mod n Er bekommt mit 948157 mod 2773 = 920, also 4er Block 0920)
Wenden wir uns der Beantwortung der ersten Frage zu. Die Tabelle zeigt nach welchem Schema Bob den public und den privat key berechnet.
|
||||||
N, e und d Beispiel mit p = 3 und q = 5 |
|
||||||
Dass d so einfach zu berechnen ist,
dass also die Division (k.z+1)/e immer ohne Rest geht,
garantiert der sog. Satz von Euler1. Verschlüsselung: |
|||||||
|
|||||||
Sicherheit |
Kommen wir zur Beantwortung der zweiten Frage: Wir geben von den beiden Primzahlen 5 und 7 vor. Aus ihnen bestimmt Bob nach dem oben beschrieben Verfahren n und e und d. Das Ensemble (n,e) gibt er an Alice weiter. Alice kennt also n = 35 und e = 3. Da die Schlüssel öffentlich sind, kennt auch Eva diese Zahlen und natürlich auch das Verfahren. Wenn nun Eva die geheime Botschaft von Alice an Bob abfängt oder belauscht, benötigt sie, wie unsere Formeln zeigen, neben n aber auch die Zahl d. Um d zu bestimmen benötigt sie aber den Wert von z, z wiederum kennt sie dann, wenn sie die beiden Primzahlen kennt, deren Produkt n ist. Dies scheint auf den ersten Blick einfach. Ist nämlich n = 15, hat man schnell p und q zu 3 und 5 berechnet oder auch einfach erraten. Ganz anders ist die Situation, wenn Bob größere Primzahlen gewählt hat, z.B. p = 31991 und q = 9973. Ihr Produkt ist n = 319046243. Aus ihr die Primzahlen p und q zu bestimmen ist schon aufwändiger. Es ist leicht einzusehen, dass der Aufwand p und q aus n zu bestimmen immer größer wird, je größer die Primzahlen sind. Sind p und q z.B. 100-stellig, so brauchen selbst schnelle Rechner Millionen von Jahren um die Zerlegung zu schaffen und man verwendet in der Realität wesentlich größere. So kann man verstehen, dass die Wirtschaft ein großes Interesse daran hat, dass Mathematiker immer größere Primzahlen finden, was nicht einfach ist.
|
||||||
Beispiel Download: |
Ein Java-Programm RSAEncrypt.java
liest eine vierstellige Zahl (als String ein) und verschlüsselt diese mit
dem public key : n = 15 und e = 3. Der so erhaltene Code soll durch ein Programm RSADecrypt.java aus der Sicht von Bob entschlüsselt werden, d.h. d = 11 ist bekannt.
Klartext eingeben: 12
Geheimtext eingeben: 3
Achtung: die oben dargestellte
Programme funktionieren nur für den public Key (15,3) und den private Key
(15,11) und den Originaltext 12, der zu 8 verschlüsselt wird. Schon die
Veränderung des Originaltextes kann dazu führen, dass das Programm nicht
korrekt mehr arbeitet. Der Grund dafür liegt in der Arithmetik. Das
Potenzieren bei Verschlüsseln bzw. Entschlüsseln erzeugt sehr große
Zahlen, für die die Genauigkeitsgrenzen von
double-Typen
(Math.pow(double basis, double
exponent) erzeugt
Fließkommawerte) nicht ausreicht. Im nächsten Kapitel wollen sehen wir,
wir diese Problem in den Griff bekommen. |
||||||
Eine genauere Betrachtung des RSA Verfahrens findet man in dem Buch. Kryptologie von Albrecht Beutelspacher ISBN 3-528-58990-6. Beutelspacher geht in diesem Buch auch auf den Beweis des genannten Satzes von Euler ein. | |||||||
zu | 23.20 Implementierung von RSA in den Klassen EnKrypt und DeKrypt | ||||||
zur Startseite | www.pohlig.de (C) MPohlig 2004 |