Zur MathePrisma-Startseite
Zur Modul-Startseite  


RSA (Einwegfunktionen 2)
 

 
 
Primfaktorzerlegung
 
Das Produkt zweier Primzahlen zu berechnen, ist leicht. Wie sieht es mit der Umkehrung aus?
 


 
Berechne die Primfaktorzerlegung! (falls sie relativ schnell berechenbar sind...)
21 = x  
65 = x  
14803 = x  
12863273 = x  
 

 
Aber Achtung! Manchmal ist auch die Zerlegung einer so großen Zahl einfach, wenn man weiß, dass sie nur zwei Primfaktoren hat:
 

 
2469135782 = x  

 

 
Obige Aufgabe ist so einfach, weil einer der beiden Primfaktoren sehr klein ist.

Die Funktion "Multipliziere zwei große Primzahlen" ist eine Einwegfunktion. Halten wir fest:

 

 
Wählt Bob zwei (große!!) Primzahlen \(p\) und \(q\) und hält diese geheim, so kann er gefahrlos das Produkt \(N = p\cdot q\) veröffentlichen. Niemand außer ihm wird an die Primfaktoren \(p\) und \(q\) herankommen.
 

 
Darauf beruht das bekannteste asymmetrische Verschlüsselungsverfahren, das RSA-Verfahren.
 
Seite 4/12