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:

EK(M)= und Dk(C) = Dk(Ek(M)=M

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


Ronald Rivest


Adi Shamir


Len Adleman
 

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)


Zu klären sind noch zwei Fragen: Wie findet Bob die beiden Zahlen e und d, wenn er sich auf zwei Primzahlen p und q festgelegt hat? Und warum ist dieses Verfahren u.U. so sicher?

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

  • n = p . q
  • z = (p-1)(q-1)
  • e  größer als 1 und keinen Primfaktor mit z gemeinsam (also auf jeden Fall ungerade, warum?) sonst frei. e ist also zu z teilerfremd
  • d = (k.z+1)/e;  k 'frei' wählbar, muss aber die Division restfrei halten.
    Oder: Wähle d so, dass
    e.d = 1 mod z ist, d.h d ist die multiplikative Inverse zu e mod z.
  • n = 3 . 5 = 15
  • z = (3-1)(5-1) = 8
  • e = 3


     
  • d = (4.8+1)/3 = 11
    [wenn k = 4]
  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:

 

c = me mod n

m = 12
c = 123 mod 15 = 1728 mod 15 = 3


Entschlüsselung:
m = cd mod n c = 3
m = 311 mod 15= 177147 mod 15 = 12
 

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:

RSAEncrypt.java

RSADecrypt.java

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.
import info1.*;

public class RSAEncrypt{

  public static void main(String[] args){

     int n = 15;

     int e = 3;

     System.out.print("Klartext eingeben: ");

     int m = Integer.parseInt(Console.in.readWord());

     int c = (int)(Math.pow(m,e))% n;

     System.out.println("Geheimtext: "+c);

  }

}

Klartext eingeben: 12
Geheimtext: 3

 

import info1.*;

public class RSADecrypt{

  public static void main(String[] args){

     int n = 15;

     int d = 11;

     System.out.print("Geheimtext eingeben: ");

     int c = Integer.parseInt(Console.in.readWord());

     int m = (int)(Math.pow(c,d))% n;

     System.out.println("Originaltext: "+m);

  }

}

Geheimtext eingeben: 3
Originaltext: 12

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.
 

1

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