Zur MathePrisma-Startseite
Zur Modul-Startseite  


RSA (RSA Vielfachensummen)
 

 
 

 
Die Vielfachensummen-Darstellung erhält man aus dem erweiterten euklidischen Algorithmus. Hierbei wird der größte gemeinsame Teiler der Zahlen \(a\) und \(b\) genau wie im  euklidischen Algorithmus berechnet, gleichzeitig aber die entstehenden Zahlen qi zu \(x\) bzw \(y\) zusammengefasst
 
erweiterter euklidischer Algorithmus
 
read a, b (b < a)
(u1, u2, u3) = (1, 0, a)
(v1, v2, v3) = (0, 1, b)
while v3 != 0 do
     q = u3 div v3     (Division ohne Rest)
     (t1, t2, t3) = (u1, u2, u3) - q (v1, v2, v3)
     (u1, u2, u3) = (v1, v2, v3)
     (v1, v2, v3) = (t1, t2, t3)
 

 
Es gilt dann:

\[ ggT(a,b) = u_3 = u_1\cdot a + u_2\cdot b. \]

 

 
Angenommen, du hast die Primzahlen \(p = 17\) und \(q = 11\) gewählt. Als nächstes brauchst du eine Zahl \(e\), die keine gemeinsamen Teiler mit \((p-1)(q-1) = 160\) hat. Wie wäre es mit \(e = 7\)? Die folgende Diashow zeigt den erweiterten euklidischen Algorithmus für 160 und 7:
 

 
 
zurück reset vor
 

 
Daraus lässt sich nun nicht nur die Vielfachensummen-Darstellung des ggT(160,7), sondern auch der private key \(d\) ablesen.
 
(p-1)(q-1) = 160, e = 7
Lies aus der Diashow ab!
\(1 = \)   \(\cdot \color{blue}{160} + \)   \(\cdot \color{blue}{7}\)
\(d = \)  
 
 
 
Probier' es auch mal mit Papier und Bleistift! Verwende \(p = 5\), \(q = 11\) und \(e = 7\). Bestimme zunächst die Vielfachensummen-Darstellung:
\(1 = \)   \(\cdot \color{blue}{40} + \)   \(\cdot \color{blue}{7}\)
 
 
Lies dann den private key \(d\) ab: (Achtung! \(d > 0\)!)
\(d = \)  
 
 
 
bild4_1
bild4_2
bild4_3
bild4_4
bild4_5
bild4_6
bild4_7
bild4_8
bild4_9
bild4_10
bild4_11
bild4_12