Das Verfahren geht nun nach folgendem Schema. Jeder Benutzer B
- berechnet n=pq und
,
- wählt zwei ganze Zahlen d und e zwische 1 und
, die zu
teilerfremd sind und die Bedingung
erfüllen,
- macht
als öffentlichen Schlüssel bekannt, und
- verbirgt
als geheimen Schlüssel.
Falls nun ein Benutzer A eine Nachricht übermitteln will, wird er diese in Buchstabengruppen (etwa zu je vier) zerlegen und diesen Buchstabengruppen jeweils Elemente aus zuordnen (als Zahlen a zwischen 0 und n-1). Der Verschlüsselungsprozeß ist die Abbildung
wobei
wieder durch Zahlen zwischen 0 und n-1 geschrieben wird. der
Entschlüsselungsprozeß besteht darin, daß B aus dem
ihm übermittelten
die Potenz
bildet und damit nach dem Satz am Ende des vorigen Abschnitts das Element
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
-Funktion die nur unwesentlich abgeänderte
-Funktion von Carmichael verwendet
kleinstes gemeinsames Vielfaches von p-1 und q-1)):
Es sei
Weiter wird e=17 und d=157 gewählt. Der Verschlüsselungsschritt ist dann
der durch sukzessives Potenzieren in der Form.
mod mod mod mod 2773)a mod 2773
ausgeführt werden kann. Der Entschlüsselungsschritt ist
Werden nun das Leerzeichen sowie die Buchstaben des Alphabets in Ziffernpaare verwandelt, können wegen 2626<2773 Buchstabenpaaren eindeutig kleinste Reste zugeordnet werden. Die Botschaft
wird dabei zu den Zahlenkombinationen
mit der Verschlüsselung
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
leichter auf p und q geschlossen werden. Es gibt verschiedene Angriffsmethoden. Die für die Mathematik am interessantesten erscheinende soll nun diskutiert werden.