Das RSA-Verfahren

Das Verfahren geht nun nach folgendem Schema. Jeder Benutzer B

- berechnet n=pq und tex2html_wrap_inline542 ,
- wählt zwei ganze Zahlen d und e zwische 1 und tex2html_wrap_inline550 , die zu tex2html_wrap_inline550 teilerfremd sind und die Bedingung

displaymath554

erfüllen,
- macht tex2html_wrap_inline556 als öffentlichen Schlüssel bekannt, und
- verbirgt tex2html_wrap_inline558 als geheimen Schlüssel.

Falls nun ein Benutzer A eine Nachricht tex2html_wrap_inline562 übermitteln will, wird er diese in Buchstabengruppen (etwa zu je vier) zerlegen und diesen Buchstabengruppen jeweils Elemente tex2html_wrap_inline440 aus tex2html_wrap_inline566 zuordnen (als Zahlen a zwischen 0 und n-1). Der Verschlüsselungsprozeß ist die Abbildung

displaymath574

wobei tex2html_wrap_inline576 wieder durch Zahlen zwischen 0 und n-1 geschrieben wird. der Entschlüsselungsprozeß besteht darin, daß B aus dem ihm übermittelten tex2html_wrap_inline576 die Potenz tex2html_wrap_inline586 bildet und damit nach dem Satz am Ende des vorigen Abschnitts das Element tex2html_wrap_inline440 gewinnt, das wieder in Zahlen zwischen 0 und n-1 geschrieben die Rückübersetzung in den Buchstabentext erlaubt, der übermittelt werden sollte. Aus [Ba] S.179 wird das folgende Beispiel reproduziert (das natürlich kleinere Zahlen verwendet und statt mit der Eulerschen tex2html_wrap_inline516 -Funktion die nur unwesentlich abgeänderte tex2html_wrap_inline596 -Funktion von Carmichael verwendet tex2html_wrap_inline598 kleinstes gemeinsames Vielfaches von p-1 und q-1)):
Es sei

displaymath604

Weiter wird e=17 und d=157 gewählt. Der Verschlüsselungsschritt ist dann

displaymath610

der durch sukzessives Potenzieren in der Form.

tex2html_wrap_inline612 mod tex2html_wrap_inline614 mod tex2html_wrap_inline614 mod tex2html_wrap_inline618 mod 2773)a mod 2773

ausgeführt werden kann. Der Entschlüsselungsschritt ist

displaymath624

Werden nun das Leerzeichen tex2html_wrap_inline626 sowie die Buchstaben des Alphabets tex2html_wrap_inline628 in Ziffernpaare tex2html_wrap_inline630 verwandelt, können wegen 2626<2773 Buchstabenpaaren eindeutig kleinste Reste tex2html_wrap_inline634 zugeordnet werden. Die Botschaft

displaymath636

wird dabei zu den Zahlenkombinationen

displaymath638

mit der Verschlüsselung

displaymath640

Die Verschlüsselung kann aus dem öffentlichen Schlüssel erraten werden (durch einen ,,kryptoanalytische Angriff``), wenn der geheime Schlüssel, also die Zahl d erraten wird. Dies ist nicht schwer, wenn die Zerlegung von n in die Primzahlen p und q gelingt. Als Sicherungsmaßnahmen dagegen gelten

- p und q werden sehr groß gewählt
-p und q werden nicht aus irgendeiner Primzahltabelle gewählt
-p und q unterscheiden sich sowohl als Dezimalzahlen als auch als binäre Zahlen um einige Stellen. Sonst kann nämlich eventuell mit Fermats Idee

displaymath662

leichter auf p und q geschlossen werden. Es gibt verschiedene Angriffsmethoden. Die für die Mathematik am interessantesten erscheinende soll nun diskutiert werden.