0 Daumen
99 Aufrufe

Aufgabe:

Es sei (1159,23) der öffentliche Schlüssel von Alice in einem RSA-Kryptosystem. Alice wird der Schlüsseltest 23+1159ℤ zugeschickt. Wie lautet der Klartext?

Um klartext berechnen zu können, muss man d (privater Schlüssel) kennen.
d berechnet man mit folgender Gleichung:
e.d kongruent 1 mod PHI(n)

Wie kann ich PHI(n) berechnen, wenn ich p und q nicht kenne.

Danke schon mal für eure Hilfe


Code:

von

1 Antwort

0 Daumen

Da \(n\) durch den öffentlichen Schlüssel \(S_V=(n, e)\) gegeben ist, könntest du in diesem Fall \(n\) faktorisieren. Das funktioniert auch relativ schnell, weil \(n\) klein ist. Bei realen Anwendungen von RSA-Schlüsseln werden natürlich deutlich größere Primzahlen verwendet, damit das Faktorisieren von \(n\) sehr viel Zeit in Anspruch nimmt.

Die Faktorisierung könntest du hier mittels Probedivision bis zum Faktor \(\sqrt{1159}\approx 34\) vornehmen. Dabei kannst du die 2 als Faktor ausschließen, weil die Zahl 1159 nicht gerade ist. Desweiteren kann 1159 nicht durch 3 teilbar sein, weil die Quersumme \(1+1+5+9=16\) nicht durch 3 teilbar ist. Außerdem sieht man sofort, dass die Zahl nicht durch 5 teilbar sein kann, weil weder 0 noch 5 die letzte Ziffer ist. Für alle anderen Faktoren berechnest du schnell mit Probedivision, ob ein Rest bleibt. Falls ja, war der Faktor nicht der gesuchte Faktor für die Faktorisierung von 1159. Als Ergebnis solltest du dann die 19 als möglichen Faktor finden. 19 ist durch keine Primzahl kleiner als 19 teilbar, also muss 19 eine Primzahl sein. Weil \(1159/19=61\) ist, müssen wir noch prüfen ob \(61\) eine Primzahl ist. Da \(61\) durch keine kleinere Primzahl \(\sqrt{61}\approx 7.8\) teilbar ist, ist \(61\) Primzahl. Damit hast du die Primzahlfaktoren \(19\) und \(61\) gefunden. Jetzt kannst du $$\varphi(n)=(19-1)(61-1)=1080$$ ausrechnen, weil $$\varphi(n)=(p-1)(q-1)$$ mit \(pq=n\) und \(p,q\) zwei verschiedene Primzahlen.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community