RSA-Algorithmus und Rechnen mit Restklassen

Inhalt

RSA-Algorithmus und Rechnen mit Restklassen

Computer speichern Buchstaben als Zahlen. Alle Buchstaben und Symbole auf der Computertastatur werden in Wirklichkeit als Zahlen gespeichert, die zwischen zwischen 0 und 255 liegen.

Wir können also eine Nachricht auch in eine Zahlenfolge umwandeln. Nach welcher Methode (oder Algorithmus) dies geschieht, wird im nächsten Abschnitt beschrieben. Darin stellen wir Ihnen die Methode vor, nach der die Verschlüsselung mit GnuPG funktioniert: den RSA Algorithmus. Dieser Algorithmus wandelt eine Zahlenfolge (die ja eine Nachricht darstellen kann) so in eine andere Zahlenfolge um (Transformation), dass die Nachricht dabei verschlüsselt wird. Wenn man dabei nach dem richtigen Verfahren vorgeht, wird die Nachricht sicher kodiert und kann nur noch vom rechtmäßigen Empfänger dekodiert werden. Das sind die Grundlagen des RSA Algorithmus:

Sie selbst haben bei der Installation von Gpg4win während der Eingabe Ihrer Passphrase zwei große Primzahlen erzeugt, ohne es zu bemerken (dieser werden mit p und q bezeichnet). Nur Sie -­ oder in der Praxis Ihr Computer -­ kennen diese beiden Primzahlen, und Sie müssen für ihre Geheimhaltung sorgen.

Es werden daraus nun drei weitere Zahlen erzeugt:

Die erste Zahl

ist das Ergebnis der Multiplikation der beiden Primzahlen, also ihr Produkt. Dieses Produkt wird als Modulus und dem Buchstaben n bezeichnet. Dies ist der Modul mit dem wir später immer rechnen werden.

Die zweite Zahl

ist der sogenannte öffentliche Exponent und eine Zahl an die bestimmte Anforderungen gestellt werden (teilerfremd zu (p-1)(q-1)); sie wird mit e bezeichnet. Häufig wird hier 3, 41 oder 65537 benutzt.

Die dritte Zahl

wird errechnet aus dem öffentlichem Exponent (der zweiten Zahl) und den beiden Primzahlen. Diese Zahl ist der geheime Exponent und wird mit d bezeichnet. Die komplizierte Formel zur Berechnung lautet:

d = e^-1 mod(p - 1)(q -1)

Die erste und die zweite Zahl werden veröffentlicht ­- das ist Ihr öffentlicher Schlüssel. Beide werden dazu benutzt, Nachrichten zu verschlüsseln. Die dritte Zahl muss von Ihnen geheimgehalten werden ­- es ist Ihr geheimer Schlüssel. Die beiden Primzahlen werden danach nicht mehr benötigt.

Wenn eine verschlüsselte Nachricht empfangen wird, kann sie entschlüsselt werden mit Hilfe der ersten (n) und der dritten Zahl (d). Nur der Empfänger kennt beide Schlüsselteile ­- seinen öffentlichen und seinen geheimen Schlüssel. Der Rest der Welt kennt nur den öffentlichen Schlüssel (n und e).

Die Trick des RSA Algorithmus liegt nun darin, dass es unmöglich ist, aus dem öffentlichen Schlüsselteil (n und e) den geheimen Schlüsselteil (d) zu errechnen und damit die Botschaft zu entschlüsseln -- denn: Nur wer im Besitz von d ist, kann die Botschaft entschlüsseln.

RSA-Algorithmus und Rechnen mit Restklassen

Inhalt