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.
F2003 III-6: RSA-Kryptomanie
Wie kriege ich denn die Lösungen?
Gegeben: n = 377, e = 59.
Gefragt: Was ist d?
d ist ja bekanntlich e^(-1) mod Phi(n)
und Phi(n) = (p-1)(q-1) mit ggT(e, Phi(n)) = 1
und n = p * q
Ok, ich weiß es - oder fast - ich muss aus dubiosen Quellen (den Tiefen meines benötigten, aber nicht vorhandenen IQ 180-Verstandes) wissen, was die Primfaktorzerlegung von n ist!!!
Dann kann ich p und q ausrechnen, dann Phi(n), dann brauche ich nur noch den eggT von 59 und 377 berechnen, um das Inverse zu 59 zu bekommen, dann rechne ich Inverses mod Phi(n), und dann habe ich auch schon die Lösung und ganze 4 (!!!) Punkte verdient.
Na wenn das nicht einfach war!!! 
Frage: stimmt doch so, oder? Was ist die Primfaktorzerlegung von 59? Wie kriege ich sie?
59 ist prim 
Ja, schon, aber wie kriege ich daraus p und q? Ist Phi(n) damit einfach 59 und ich brauche kein p und q? :wand:
Dann hoffe ich mal, dass ich daraus schlau werde…
Danke, Brüder!
Du arbeitest hier nur mit einer Primzahl. Also kein p und q. Und Phi von nur einer Primzahl ist eben Primzahl -1. Also rechnest du mit dem Euklid das Inverse von 59 bezüglich Primzahl -1.
Ok, danke!
p und q sind die faktoren von 377: 13 und 29.
Ach ja stimmt, habe ich ja so die Formeln hingeschrieben und dann noch falsch gemacht - ich depp
Ok, ich nehme alles zurück und behaupte das gegenteil :red:
(hätte vielleicht doch mal die aufgabenstellung durchlesen sollen. 377 ist natürlich keine Primzahl) Also so wie palmcron sagt.
[esoterik]
btw … wir haben beim lernen festgestellt, das bei primfaktorisierungsaufgaben immer wieder die 13 als faktor auftritt … scheint so ne marode von den thi profs zu sein … also falls mal in der klausur die faktorisierung nicht angegeben ist, einfach mal durch die 13 teilen 
[/esoterik]
DAS KANN DOCH NICHT MIT RECHTEN DINGEN ZUGEHEN (danke für den guten Tipp)
Vermutlich, weil 13 nicht offensichtlich ist, man aber beim Probedividieren dann trotzdem recht schnell bei ihr anlangt. 
481 hat auch eine schoene Faktorisierung
@MatthiasM: da war was falsch in deiner eröffnenden Bemerkung, dass man dann den eggt(377,59) berechnet. denn: wenn e = d^(-1) mod phi(n) dann musst du zwecks berechnung der inversen zu e (also d) den eggt(phi(n),e) berechnen. Notabene: wir rechnen im exponenten mod phi(n) aber in der basis mod n (!)
ok danke fredator - oder wer auch immer du bist (hacked!)
das war schon ich.
Wie ist denn nun die Lösung zur Aufgabe? Ich glaube nicht, dass man uns in der Klausur solche, zu große Zahlen faktorisieren lässt. Ich glaube es hat was damit zu tun, dass die Symbole, aus denen die zu codierenden Messages bestehen selbst aus Z(377) sind. Das muss man irgendwie verwerten - dann kommt man bestimmt auch ohne Faktorisierung auf die Lösung. Weshalb sollte sonst explizit dastehen dass die Symbole aus Z(377) sind. Redundante Information?
Vielleicht kommt ja doch noch jemand drauf.
Herzlichen Gruß,
Marco
@ML: Da unser n aus 3129 besteht, können wir daraus phi(n)=1228=336 bestimmen.
Dann berechnest Du mit dem eeA: 59d≡1mod336 und kommst
dann auf das gesuchte d=131.
Oder wolltest Du irgendwas andres wissen?
woher nimmst du denn die faktorisierung von 377? wie soll man das denn in der klausur machen? also ich für meinen teil glaube, dass der kern der Aufgabe darin besteht, die Aussage “werden die zu codierenden symbole mit zahlen x element Z(377) dargestellt” richtig zu interpretieren.
Oder ich übersehe etwas ganz essenzielles. Ich kann mir nicht vorstellen, das ein Professor es wagt uns in einer Klausur ne dreistellige Zahl faktorisieren zu lassen - das steht auch im widerspruch zu den üblichen Vorgehensweisen in sämtlichen anderen Aufgaben, bei denen die Faktorisierung immer angegeben ist.
Hmm… mensch, das bereitet Kopfzerbrechen (-:
Gruß,
Marco