RSA | MathePrisma

private key

Der private key ist eine Zahl $d$ , die aus der Gleichung

$e \cdot d \bmod (p-1)(q-1) = 1$

berechnet wird.

Grundlage zur Berechnung von $d$ durch $e \cdot d \bmod (p-1)(q-1) = 1$ ist folgender Satz, der garantiert, dass es eine solche Zahl überhaupt gibt - vorausgesetzt die Zahl $e$ hat eine bestimmte Eigenschaft...

modulare Inverse

Sind zwei Zahlen $a, b \in \mathbb{Z}$ teilerfremd, so gibt es eine (positive) ganze Zahl $c$ , für die gilt:

$b \cdot c \bmod a = 1$

Man sagt, $b$ ist modulo $a$ invertierbar, und nennt $c$ die modulare Inverse von $b$ .

Beispiel

In unserem Fall sind wir gerade daran interessiert $e$ modulo $(p-1)(q-1)$ zu invertieren. Das heißt insbesondere, dass $e$ und $(p-1)(q-1)$ teilerfremd sein müssen.

Und wie berechnet man die modulare Inverse nun? Ein Verfahren für diese Berechnung ist in dem Beweis zu obigem Satz versteckt. Deswegen folgt er hier ausführlich:

Beweise bitte!

Der Beweis erfolgt in drei Schritten:

Schritt 1:
Der euklidische Algorithmus zur Bestimmung von $ggT(a,b)$

Schritt 2:
Vielfachensummendarstellung $ggT(a,b) = x\cdot a + y \cdot b$

Schritt 3:
Betrachtung des Falls $ggT(a,b) = 1$ , d.h. $a$ und $b$ sind teilerfremd