Generierung des public key

Um den public key zu generieren, wählt man zunächst zwei große Primzahlen zufällig aus. Da man sehr große Primzahlen braucht, um eine möglichst sichere Verschlüsselung zu erreichen, ist das gar nicht so einfach, wie man zunächst vermuten mag. Glücklicherweise gibt es Möglichkeiten, wie etwa das ,,Kriterium von Pocklington``, um aus kleinen Primzahlen und einem Zufallswert, neue größere Primzahlen zu errechnen.

Die beiden Primzahlen nennt man üblicherweise $p$ und $q$, deren Produkt $n$ den ersten Teil des public key darstellt.

$$n = p \cdot q$$ (10)

Der zweite Teil besteht lediglich aus der Zufallszahl $e$. Üblicherweise wird für $e$ einer der Werte 3, 17 oder 65537 verwendet, da diese wenige Einsen in ihrer Binärdarstellung aufweisen und Computer so leicht mit ihnen potenzieren können ([1], Seite 109). Für $e$ gibt es eine weitere Vorraussetzung, die in 7.2 erklärt wird, wegen der es sich empfiehlt, für $e$ ebenfalls eine Primzahl zu wählen.

Um nun eine Nachricht, üblichweise $P$ (für ,,Plain-Text``) genannt, zu verschlüsseln, potenziert man mit $e$ und reduziert um $n$. So erhält man den Cipher-Text $C$:

$$C = P^e \bmod n$$ (11)

Das Anwenden der Modulofunktion verhindert, dass ein Dritter, der $e$ kennt⁸ die Potenzierung rückgängig machen und damit $P$ erhalten kann. Das ist das Problem des ,,diskreten Algorithmus``, das schon in Kapitel 5 verwendet wurde.