RSA

33.12 RSA

public key - privat key

Alle Verschlüsselungen haben gemeinsam, dass der der den Klartext M chiffriert, eine Funktion E_k mit dem Schlüssel K benutzt. Den so entstandenen Geheimtext kann man entschlüsseln, wenn man den inverse Funktion D_k = E_k^-1kennt.

Allgemein gilt:

E_K(M)=C und D_k(C) = D_k(E_k(M)=M

Die Cäsarverschlüsselung (z.B. Verschieben um 3) ist durch die mathematische Operation E_k(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 D_k(c) = m = c-k beschrieben. Wir sehen, zum Dechiffrieren notwendige Funktion D_k ist sehr leicht aus aus der Verschlüsselungsfunktion E_k 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).

Um den nachfolgenden Text leichter verstehen zu können, wollen wir im weiteren Text 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. Personen, die den Austausch der geheimen Botschaft zwischen Alice und Bob belauscht und zu entschlüsseln versucht, nennen wir Eva.

Ein raffinierter Trick verändert die Sachlage grundlegend: Er besteht nun darin, dass Bob nach einer Entschlüsselungsfunktion D_k sucht, die es erlaubt, sehr leicht E_k zu bestimmen, aber umgekehrt es jemanden sehr schwer ist, ja so gut wie unmöglich macht, D_k aus E_k zu berechnen.

Rivest
Shamir
Adleman Wir beschreiben zunächst einmal das Verfahren, das Ronald Rivest, Adi Shamir und Len Adleman 1978 entwickelt haben und das nach den Initialen der drei Entwickler als RSA bezeichnet wird.

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. 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. N und e sind der sog. public key. Die Zahl d , die Bob nicht bekannt gibt ist dann der sog. privat key.

Wenn Alice einen Text, bestehend aus Wörtern verschlüsseln wollen, übersetz sie diese Wörter in eine Folge von Zahlen (z.B. entsprechend seinem ASCII-Code und fassen den gesamten Text zu 4er-Blöcken zusammen. 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= m^e mod N

In unserem konkreten Fall ergibt sich somit der 948 = 920¹⁷ mod 2773.

Bob erhält diese Nachricht und entschlüsselt sie mit:

m = c^d mod N

Er bekommt damit wieder konkret 948¹⁵⁷ mod 2773 = 920 (oder als 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.
d = (k^.Z+1)/e; k 'frei' wählbar, muss aber die Division restfrei halten.

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 Euler¹.

Verschlüsselung:

c = m^e mod N

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

Entschlüsselung:

m = c^d mod N

m = 3¹¹ 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. N und e gibt er an Alice weiter. Alice kennt also N = 35 und e = 3. Auch Eva kennt diese Zahlen und 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 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 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. Leicht sieht man ein, 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 (4 Ziffern): ");

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

     int c = (int)(Math.pow(m,E))% N;

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

  }

}

import info1.*;

public class RSADecrypt{

  public static void main(String[] args){

     int N = 15;

     int D = 11;

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

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

     int m = (int)(Math.pow(c,D))% N;

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

  }

}

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 33.13 Übungen

zur Startseite www.pohlig.de (C) MPohlig 2004