RSA | MathePrisma

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}$ .

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.