Zur MathePrisma-Startseite
Zur Modul-Startseite  


RSA (RSA 3)
 

 
 
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
Es gilt: \(3 \cdot 2 \bmod 5 = 1\).
Also ist   modulo   invertierbar mit der modularen Inversen   .
 
 
 

 
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

 
Seite 7/12