Javascript wird benötigt. Bitte einschalten !
aufgeschlossen Programmieren mit JavaScript

RSA - Verschlüsselung

 einfache Verschlüsselung        Inhalt         Bruchrechnung

RSA

Alle bisher erwähnten Verfahren sind symmetrisch in dem Sinn, dass die Entschlüsselung mit dem selben Schlüssel erfolgt wie die Verschlüsselung. Die notwendige Übermittlung des Schlüssels stellt dabei ein Sicherheitsrisiko dar.

Beim RSA - Verfahren (benannt nach den Erfindern Rivest, Shamir und Adleman) gibt man die beiden Zahlen seines öffentlichen Schlüssels bekannt (etwa E = 484577 und N = 8272811).

Da RSA nur mit Zahlen arbeitet, ersetzen wir die Buchstaben etwa durch ihre Nummer im Alphabet und setzen gleich eine etwas größere Zahl aus mehreren Buchstaben zusammen ( < N ). So wird etwa "ABBA" zu "01020201".

Verschlüsselt wird mit der Rechnung: 1020201 hoch E modulo N (+ evtl. irgendein Vielfaches von N).
Das heißt, die Zahl 1020201 wird 484577 mal mit sich selbst multipliziert und das Ergebnis durch 8272811 geteilt. Von der Division verwendet man nur den Rest als verschlüsselte Zahl: 750769.
Durch die Restbildung ist es nicht möglich, ausgehend von 750769 die ursprüngliche Zahl wieder zu finden (So etwas nennt man eine "Falltür - Funktion").

Nur mit dem geheimen Entschlüsselungsexponenten D (in diesem Beispiel 3297929) und dem bekannten N kann man durch eine ähnliche Rechnung wie bei der Verschlüsselung den Urtext wieder finden.

Das Verfahren beruht darauf, dass N Produkt von zwei großen Primzahlen ist. Wenn man diese Primzahlen kennt, kann man D bestimmen. Es ist also für die Sicherheit des Verfahrens wichtig, wirklich sehr große Primzahlen zu finden, damit eine Zerlegung in die beiden Faktoren nicht so schnell möglich ist.

Die gerade verwendete Zahl N = 8272811 ist sehr unsicher, denn ein kleines Programm ("pzzerlegung.html") benötigt nur Sekundenbruchteile, um 8272811 = 5749 * 1439 zu berechnen.
Wenn N mehr als 100 Stellen hat, gilt das Verfahren als sicher.

verständlich
oder
sicher
verständlich: Das Ganze noch einmal mit kleinen Zahlen.
N = 14 ist das Produkt der beiden Primzahlen 2 und 7.
Als Verschlüsselungs - Exponent ist E = 11 geeignet.
Wenn wir den Buchstaben "B" (Nummer "2" im Alphabet) verschlüsseln, rechnen wir 2 hoch 11 = 2048 und bestimmen den Rest beim Teilen durch 14:
2048 = 146 * 14 + 4.
Damit ist "4" das Ergebnis unserer Verschlüsselung.
Für den Weg zurück benötigt man zunächst einmal den sogenannten Nebenmodul (aus den beiden Primzahlen 2 und 7): (2-1)*(7-1) = 1*6 = 6.
E=11 war eben "geeignet", weil 11 und 6 keinen gemeinsamen Teiler besitzen.
Deshalb findet man unter den Vielfachen von 11 eine Zahl D * 11, die beim Teilen durch 6 den Rest 1 hat. 5*11 = 55 = 54 + 1 = 9*6 + 1. Damit ist D=5 der gesuchte Exponent.
Entschlüsselung von "4": 4 hoch 5 = 1024, und 1024 geteilt durch N=14 ergibt als Rest die Zahl "2" und damit den Buchstaben "B". (1024 = 73 * 14 + 2)

sicher: Wie bei allen Programmiersprachen kann man auch in Javascript nur mit einer begrenzten Genauigkeit rechnen.
Bei ganzen Zahlen mit mehr als 17 Stellen werden die letzte(n) Stelle(n) bei der Rechnung durch 0 ersetzt. Die oben geschilderten Rechenvorgänge führen dann zu unbrauchbaren Ergebnissen.
Eine Lösung dieses Problems besteht darin, Zahlen aufzuteilen, etwa 123456 Billionen 789012 Millionen 345678, und mehrere Speicher für eine Zahl zu benutzen.
Auf diese Weise erhält man jede denkbare Stellenzahl; man muss allerdings für diese "langen Zahlen" alle Rechenvorgänge durch Funktionen nachbilden, weil die normalen Rechenoperationen "+", "-", "*", "/" (und "%" für den Divisionsrest) nur für einzelne Speicherinhalte funktionieren.
Entsprechend vergrößert sich auch die Rechenzeit !
RSA
zum
Testen

Im Rahmen der normalen Zahldarstellung von JavaScript (d. h. nicht sicher) können Sie in dem folgenden Formular das RSA - Verfahren erforschen.
Die Quelltexte der Javascript - Funktionen finden sie auch in "rsa1.html".

Falls Ver- oder Entschlüsselung keine sinnvollen Ergebnisse liefern, waren die Primzahlen oder der Entschlüsselungsexponent (D) evtl. zu groß. Beachten Sie auch die lange Rechenzeit der vielfachen Multiplikationen! Bei einer Warnmeldung des Browsers sollten Sie den Vorgang natürlich nicht abbrechen!

Primzahltester:
Ist eine Primzahl

Bitte geben Sie zwei Primzahlen an (vorher testen; beide höchstens vierstellig):
Primzahl 1 : Primzahl 2 :

Hauptmodul (N) : Nebenmodul :

Das Hauptmodul muss größer als 42 sein, da hier ein Alphabet mit 42 Zeichen (große Buchstaben, die Ziffern und einige Satzzeichen) benutzt wird. Eine korrekte Entschlüsselung ist sonst nicht möglich !

Der Verschlüsselungsexponent darf mit dem Nebenmodul keinen gemeinsamen Teiler haben (teilerfremd), damit der Entschlüsselungsexponent berechnet werden kann.

Schlagen Sie einen Verschlüsselungsexponent (E) vor:

Das Programm sucht automatisch den passenden Entschlüsselungsexponent (D). Bedingung : D*E muss beim Teilen durch den Nebenmodul den Rest 1 haben.


Geben Sie jetzt einen kurzen Text ein:

Hier werden jetzt die Buchstaben einzeln verschlüsselt:



sollte den eingegebenen Text in Großbuchstaben zeigen.

  einfache Verschlüsselung      Seitenanfang      Bruchrechnung