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.
RSA
Hi;
kurze Frage zu den alten Klausuraufgaben:
Teilnehmer A schickt an Teilnehmer B und C die gleiche Nachricht mit gleichen Moduln aber unterschiedlichen Encryption-Keys.
Durch den erweiterten EA habe ich die Nachricht entschlüsseln können, d.h. ich habe nun:
Die eigentliche Nachricht, die 2 verschlüsselten Nachrichten, die 2 Module und die 2 Encryption-Keys.
Kann ich mir daraus irgendwie die Faktorisierung vom Modul oder die Decryption Keys zusammenbaun oder muss ich wieder neu anfangen und eine Faktorisierung raten?
MfG
PS:
Ich könnte die Faktorisierung ja auch ausrechnen wenn ich n und Phi(?) von n gegeben habe also pq und (p-1)(q-1); dadurch kann ich mir zusammenbaun:
p + q = n - Phi(n) + 1
aber wie löse ich das nu auf? ; /
jo,
n = p * q
phi(n) = (p-1)(q-1)
damit kommst du auf deine schon genannte Gleichung
p + q -(n-phi(n)+1) = 0 dann kannst du mit p multiplizieren, daraus ergibt sich
p² + pq -(n-phi(n)+1)p = 0; und da p*q = n kommst du dann zu
p² -(n-phi(n)+1)p + n = 0
und dann Mitternachtsformel 
so mach ichs zumindest immer… und hat immer funktioniert
Gruß
Marco
Lösungen
Hier mal meine Lösungen zu den 2 RSA Aufgabentypen:
H08
a) s = 3, t = -2, m = 12288
b) p = 19, q = 23, Phi(N) = 396, d_B = 317, d_C = 283
F09
- d = 761
- p = 43, q = 29
- 5
- Phi(Phi(N)) = Phi(1176) = 336
Keine Gewähr 
a) s und t stimmt. Bei m hab ich 52, weil man die 12288 noch mod 437 nehmen muss. Der Klartext darf auch nicht größer sein als als das RSA Modul.
ah, verstehe. Dann Hat das Z_437 in der Angabe doch ne Bedeutung 
Hab ich auch so bis auf 2):
p=43. 42 ist keine Primzahl! Ich schätze Du hast das nur falsch abgeschrieben
richtig
War wohl ein FreudAdams’scher Vertipper. 
[bloede Frage]
ich kann alle Ergebnisse bestätigen
selbst die Aufgabe ist ja relativ machbar, aber es ist schon einiges an Rechnerei dabei…da kann man sich im Stress leicht verrechnen…hat jmd Ahnung, ob wir ein Taschenrechner mitnehmen dürfen?
und noch ne frage. wie kommt man auf diese Zahl?
4) Phi(Phi(N)) = Phi(1176) = 336
bei uns war kein taschenrechner erlaubt. ich denke das ist immer noch so.
phi berechnet man so: http://de.wikipedia.org/wiki/Eulersche_φ-Funktion#Allgemeine_Berechnungsformel
Aussage von Anfang September war
“für diese Klausur [KompAlg] sind keinerlei Hilfsmittel zugelassen”
hmmm schade…
Supi. Danke sehr!