Zur MathePrisma-Startseite
Zur Modul-Startseite  


RSA (Knacken)
 
 
 

 
 Zum Schluss noch ein Beispiel, wie RSA aus Sicht des Codeknackers aussieht. Um es schon mal vorwegzunehmen: es ist ein Beispiel, in dem es dem Codeknacker leicht gemacht wird. Also keine Angst, so schnell wie hier lässt sich RSA nicht knacken..
 
Sei ein Spion!
 
 Du hast eine RSA-verschlüsselte Nachricht abgefangen. Sie lautet
 

 
     
    
10473054210223505497035330523101828168
2305497093070549713322042531164705144
 

 
 Außerdem weißt du für wen die Nachricht bestimmt ist. Der öffentliche Schlüssel des Empfängers ist

\[ N = 17947, e = 21 \]

Um die Nachricht zu entschlüsseln, musst du herausfinden, aus welchen beiden Primzahlen \(p\) und \(q\) sich \(N\) zusammensetzt.
 
Wer sucht...
 
 Eine erste Möglichkeit, \(p\) und \(q\) herauszufinden ist, bei 2 anzufangen und jede Zahl zu testen, ob sie ein Teiler von \(N\) ist. Dabei kann man sich die Arbeit einfacher machen, wenn man bedenkt, dass

  • nicht \(p\) und \(q\) beide größer als \(\sqrt{N}\) sein können (man braucht also "nur" die Zahlen bis \(\sqrt{N}\) zu testen)
  • die beiden gesuchten Teiler von \(N\) Primzahlen sind (man braucht also z.B. die geraden Zahlen gar nicht testen).
 
...der findet
 
 Allerdings dauert diese Suche um so länger je größer \(p\) und \(q\) sind. Es scheint also geschickter zu sein, die Suche bei möglichst großen Zahlen anzufangen, d.h. bei \(\sqrt{N}\).
 
Nimm den Taschenrechner und probier's mal mit dem öffentlichen Schlüssel von oben aus! (\(N = 17947\), \(e = 21\)) Runde auf zwei Nachkommastellen!
\(\sqrt{N} = \)            \(p = \)  
 
 
 

 
 Wenn du die Zahlen \(p\) und \(q\) herausgefunden hast, kannst du nun ganz normal den privaten Schlüssel \(d\) bestimmen:
 
N = 17947
e = 21
 
  
 

 
 Die Entschlüsselung geht dann ganz einfach!
 

 
  
 

 
 Dass dieser Text so leicht geknackt werden kann, liegt daran, dass die beiden Primzahlen \(p\) und \(q\) zu dicht beieinanderliegen.
 

 
 Wenn die Primzahlen \(p\) und \(q\) nicht nur groß genug sind, sondern auch weit genug auseinander liegen, kann man sie praktisch nicht herausfinden.
 
Seite 11/12