Bestimmen Sie alle 4 Bit Primzahlen und setzen Sie damit ein RSA-System mit e = 17 auf.

Question

Aufgabe: Bestimmen Sie alle 4 Bit Primzahlen und setzen Sie damit ein RSA-System mit e = 17 auf.
Analog mit sicheren 5 Bit Primzahlen.

Answer 1

Eine 4-Bit-Zahl liegt zwischen $2^3$ und $2^4-1$. Es gibt also nur die Primzahlen $p=11$ und $q=13$.

Mit $n=11\cdot 13=143$ ist der RSA-Modul dann $\varphi(n)=(p-1)(q-1)=10\cdot 12 = 120$.

Es lässt sich leicht prüfen, dass $e=17$ teilerfremd zu $120$ ist. Damit ist $(n,\, e)$ der öffentliche Schlüssel.

Jetzt muss man noch das multiplikativ Inverse von $e$ modulo 120 suchen. Das geht mit dem erweiterten euklidischen Algorithmus oder man erkennt durch Ausprobieren schnell, dass $1=120-7 \cdot 17$. Es ist also $-7\equiv 113 \mod 120$ das Inverse zu $e$.

Der private Schlüssel ist $d=113$.

Analog geht das im Fall von 5-Bit-Primzahlen.

Solche Aufgaben sind im Allgemeinen wirklich nicht schwierig. Es gibt ja einen Algorithmus dahinter und den sollte man in den Unterlagen stehen haben. Man muss das einfach mal gewissenhaft durchgehen. Darüber hinaus gibt es dazu auch genügend Material im Netz, die die Vorgehensweise erklären. :)