Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 40-1
Die Aufgabe lautet:
Die Zahl p = 4578971 ist eine Primzahl. Weiter werde der Exponent e = 3317271 zum Verschlüsseln benutzt, d.h. E: M->M^e (mod p) für Zahlen M mit 0<=M<p. […] Entschlüsseln Sie die verschlüsselte Nachricht
4137884 […]
d ist doch e^-1 mod Phi(n).
Eigentlich müsste ich doch p und q kennen, um Phi(n) bzw. hier Phi(p) zu berechnen. Greift hier auch die Regel, dass Phi(Primzahl) = Primzahl -1 ist?
(siehe http://uni.unclassified.de/1970,1#19273)
Dann brauche ich n bzw. hier p ja nicht zu faktorisieren, oder?
da steht doch nirgendwo was von RSA Verschlüsselung. Es gibt ja bekanntlich zwei Verfahren. Das Symmetrische mit nur einer Primzahl und das RSA Verfahren mit p*q. In dem Fall handelt es sich um die symmetrische Verschlüsselung und da brauchst bloß das inverse vom e also Euklid von (e, p-1) und der zum e passende Bezout ist das gesuchte Inverse.
Ach ja stimmt. Danke für den Hinweis.