kopf
brlogo
fensterobenrechts
   
   
fensteruntenblau
   
 

 

Grundlagen der Kryptologie

 

6. Die RSA-Methode

 

Wie beim Verfahren von ELGamal beruht dieses Verfahren auf einem "öffentlichen" und "geheimen" Schlüssel. Die Sicherheit dieses Verfahrens liegt in der kombinatorischen Komplexität der Primfaktorzerlegung.

Mit x als Nachricht gilt dann f*(f(x)) = x

Die Schlüsselerzeugung geschieht folgendermassen:

rsa_10

 

Beispiel:

p = 47; q = 59; n = p  q = 2773

rsa_20

 

Um einen Text zu verschlüsseln müssen zunächst die Buchstaben in Zahlen umgewandelt werden. Wählt man die ASCII-Verschlüsselung, so erhält man sehr schnell einen Überlauf. Man kann z.B. A = 01, B = 02 usw. setzen. Das als Zahl dargestellte Wort wird anschliessend in Blöcke gleicher Größe eingeteilt, die getrennt verschlüsselt werden. Für die Blockgröße ist es sinnvoll eine Zahl i zu wählen für die gilt: 10i-1 < n < 10i

Die Zahldarstellung des Wortes STALL lautet dann: 1920011212

Nach Zerlegung in Blöcke der Länge 4 und Auffüllen mit Leerzeichen erhält man:

1920 0112 1200

Durch Anwendung der Verschlüsselungsfunktion folgt der Schlüsseltext:

2109 1084 1444

Es gilt z.B. 1920 = 2109157 Mod 2773

Die bei der Ver- und Entschlüsselung auftretenden hohen Potenzen brauchen nicht effektiv ausgerechnet werden. Es gibt Algorithmen, mit denen das Ergebnis indirekt berechnet werden kann. Die Sicherheit des RSA-Verfahrens hängt im wesentlichen davon ab, ob in der Zukunft schnelle Algorithmen gefunden werden, um Zahlen in Primfaktoren zu zerlegen, was gleichbedeutend mit dem Knacken des Systems ist.

Man braucht nicht unbedingt wirkliche Primzahlen, sondern man wählt für p und q nur Pseudoprimzahlen. Das sind solche Zahlen, die alle leicht nachprüfbaren Primzahlkriterien erfüllen.

rsa_30

 

Im Unterricht genügt es die Funktionsfähigkeit des Verfahrens mit Zahlenbeispielen durchzuführen.

Obwohl die Methode und die Werte c, n bekannt sind, fällt es schwer, daraus den zur Entschlüsselung notwendigen Wert d zu berechnen. Das RSA-Verfahren wäre wertlos, wenn es gelänge, die c-te Wurzeln Modulo n zu lösen, ohne n zu kennen. Bis dahin muss man alle möglichen Primfaktorzerlegungen des Wertes n ausprobieren. In [4] ist die folgende Tabelle für einen sehr schnellen Algorithmus zum Potenzieren und die Permutationen von n aufgeführt. Jede Permutation benötge 1 Microsekunde.

 

n Länge in Ziffern

Anzahl der Operationen

Permutationszeiten

50

1,4  1010

3,9 Stunden

100

2,3  1015

74 Jahre

200

1,2  1023

3,8  109 Jahre

300

1,5  1029

4,9  1015 Jahre

 

Mit steigender Rechenleistung braucht lediglich die Stellenzahl der verwendeten Primzahlen p und q erhöht werden, um ein entsprechend grosses n zu erzeugen.

Im Prinzip kann der Algorithmus "Sieb des Eratostenes" zum Finden großer Primzahlen eingesetzt werden. In der Praxis ist er jedoch ungeeignet. In [5] werden geeignete Algorithmen beschrieben, die eine beliebige Zahl prüfen, ob diese bereits eine Primzahl ist oder die nächstgelegene Primzahl zu der eingegebenen Zahl suchen. Für das Rechnen mit diesen großen Zahlen sind geeignete Algorithmen mit Listen zu entwerfen.

Ein Zweifler könnte angesichts der schönen Eigenschaften fragen, ob die klassische symmetrische Kryptographie überhaupt noch einen Sinn macht. Sie hat aber weiterhin eine Daseinsberechtigung insbesondere deshalb, weil die Arbeit mit Public-Key-Verfahren in etwa um den Faktor 1000 langsamer sind als die verbreiteten symmetrischen Verfahren.

 

Programm zur RSA-Verschlüsselung

Zugehörige Algorithmen und ein Programmierbeispiel in Pascal//Delphi-Notation:  RSA

 

Weiter: Literaturhinweise

 

 
 
Tuesday, 21. November 2017 / 00:01:23