Generierung des private key

Mit Hilfe der Eulerschen-$\phi$-Funktion (1) lässt sich folgender Zusammenhang feststellen:

$$P^e \equiv P^{e \bmod \phi (n)} = P^{e \bmod \phi (pq)} \pmod{n}$$ (12)

Jetzt stellt man folgende Überlegung an: Wenn es für $e$ ein inverses Element $d$ gibt, für das gilt $(d \cdot e) \bmod \phi (n) = 1$, dann kann man den Cipher-Text $C = P^{e \bmod \phi (n)} \bmod n$ mit $d$ potenzieren und erhält $P^1 = P$:

$$C^d \equiv (P^e)^d = P^{e \cdot d} \equiv P^{e \cdot d \bmod \phi (n)} = P^1 = P \pmod{n}$$ (13)

Allerdings ist nicht garantiert, dass ein inverses Element überhaupt existiert. Damit dies der Fall ist, müssen $\phi (n)$ und $e$ teilerfremd sein. Das inverse Element $d$ ist das einzige (ausser der bekannten Zahl $n$), das zum Entschlüsseln gebraucht wird. Um $d$ berechnen zu können, muss man aber $\phi (n)$ berechnen können. Das ist aber nur möglich, wenn $p$ und $q$ bekannt sind.

Wenn $\phi (n)$ bekannt ist, muss immer noch folgende Gleichung gelöst werden, was analog zu (2) mit Hilfe des erweiterten Euklidischen Algorithmus einfach zu bewerkstelligen ist:

$$e \cdot d \equiv 1 \pmod{\phi (n)}$$ (14)