Der asymmetrische Verschlüsselungsverfahren funktioniert grob wie folgt (aus einer meiner eigenen geschriebenen Seminararbeiten zitiert)
"Das Prinzip des asymmetrischen Public-Key-Verschlüsselungsverfahrens beruht auf einem öffentlichen und einem geheimen Schlüssel. Wir nehmen an, dass Alice an Bob eine Nachricht verschicken möchte. Dazu braucht Bob zwei verschiedene Schlüssel, eben einen öffentlichen und einen geheimen Schlüssel. Der öffentliche Schlüssel wird zum Verschlüsseln benutzt, während der geheime Schlüssel zum Entschlüsseln der verschlüsselten Nachrichten an Bob selbst benutzt wird.
Sei nun \(S_V\) der Schlüssel zum Verschlüsseln und \(S_E\) der Schlüssel zum Entschlüsseln der verschlüsselten Nachricht. Bob veröffentlicht also den Schlüssel \(S_V\). Jetzt kann Alice mit Hilfe dieses Schlüssels ihre Nachricht \(N\) unter Verwendung des Verschlüsselungsverfahrens \(\mathcal{V}\) verschlüsseln. Alice schickt dann an Bob die Nachricht \(\mathcal{V}(N, S_V)\). Diese Nachricht entschlüsselt Bob mit Hilfe seines geheimen Schlüssels \(S_E\) unter Verwendung des Entschlüsselungsverfahrens \(\mathcal{E}\), also \(\mathcal{E}(\mathcal{V}(N, S_V ), S_E)\). Dabei muss \(\mathcal{E}(\mathcal{V}(N, S_V ), S_E) =N\) gelten, sonst würden die Schlüssel nicht zueinander passen. Desweiteren sollten sich aus den beiden Verfahren zum Ver- und Entschlüsseln kein effizienter Algorithmus zur Entschlüsselung ableiten lassen. Letztendlich darf mithilfe des öffentlichen Schlüssels keine Informationen preisgegeben werden, die es einem erlauben, den geheimen Schlüssel zu rekonstruieren."
Das RSA-Verfahren ist ein asymmetrisches Verschlüsselungsverfahren. Die Schritte für die Berechnung der Schlüsselpaare werden im folgenden Algorithmus gegeben:
1. Wähle zwei große Primzahlen \(n\neq p\)
2. Berechne \(n=p\cdot q\) und \(\varphi(n)\), die eulersche Phi-Funktion
3. Wähle eine ganze Zahl \(e\) so, dass \(e\) teilerfremd zu \(\varphi(n)\) ist und zwischen \(1\) und \(\varphi(n)\) liegt
4. Berechne das Multiplikativ-Inverse \(d\) von \(e \bmod \varphi(n)\)
5. Verschlüsseln einer Nachricht \(N\) mit \(M:=N^e \bmod n\)
6. Entschlüsseln einer Nachricht \(M\) mit \(M^d \bmod n\)
Die eulersche Phi-Funktion gibt für eine ganze, positive Zahl \(n\) an, wie viele ganze Zahlen bis \(n\) teilerfremd zu \(n\) sind. Zum Beispiel wäre \(\varphi(11)=11\), weil \(1,2,\ldots, 10\) teilerfremd zur 11 sind. Mit anderen Worten: Die Zahlen \(1,2,\ldots, 10\) können nicht ganzzahlig durch \(11\) geteilt werden, ohne einen Rest zu lassen.
Der Ausdruck \(x \bmod y\) gibt dabei die ganzzahlige Division zweier ganzer Zahlen mit Rest an. Als kleines Beispiel: \(4 \bmod 2 \equiv 0\), weil die \(4\) ohne Rest durch \(2\) teilbar ist. Das gleiche gilt natürlich auch für \(2,6,8, \ldots\) also alle gerade Zahlen. Die ungeraden Zahlen haben jeweils den Rest \(1\) .
