Kurze Frage zur digitalen Signatur am Beispiel von RSA-Signaturen
Signieren:
s = (H(m))^d mod n
Testen:
H(m) kongruent s^e mod n
Gegenen ist n,e und H(m) gegeben. Ich brauche zum Signieren ja d.
Um d zu berechnen brauche ich ja e (ist gegeben) und phi von n (= (p-1)*(q-1))
Aus n kann ich ja nicht wirklich auf phi(n) schließen.
Wie gehts das?
Dank euch!
Felix
Digitale Signatur
Re: Digitale Signatur
Im Allgemeinen geht dies nicht. Die Faktorisierung von n ist (für genügend große n) ein hartes Problem.FGB hat geschrieben: Gegenen ist n,e und H(m) gegeben. Ich brauche zum Signieren ja d.
Um d zu berechnen brauche ich ja e (ist gegeben) und phi von n (= (p-1)*(q-1))
Aus n kann ich ja nicht wirklich auf phi(n) schließen.
Ansonsten könnte ja jeder den privaten Schlüssel errechnen !
Wenn du dich auf die Übungsaufgabe beziehst: n ist hier so klein, dass man auf (Primzahlen)
\(p,q \in Z^*_n\ p * q = n\) schließen kann.
Grüße
Re: Digitale Signatur
Vielen Dank.
Man man man, ich dachte schon, es gibt doch eine "offizelle" Methode das auszurechnen oO
Grüße und nochmals danke,
Felix
Man man man, ich dachte schon, es gibt doch eine "offizelle" Methode das auszurechnen oO
Grüße und nochmals danke,
Felix
Re: Digitale Signatur
Es gibt Algorithmen die p und q ermitteln, sodass man d berechnen kann, aber für große Zahlen dauert das halt Jahre.FGB hat geschrieben: Man man man, ich dachte schon, es gibt doch eine "offizelle" Methode das auszurechnen oO

Re: Digitale Signatur
77 = 11*7, da beides Primzahlen sind, ist das wiederum p und q
damit ist Phi(77) = (11-1)*(7-1)=10*6 = 60
nun musst du noch d, welches das INverse von e mod phi(n) ist, berechnen, sprich
d*e = 1 mode phi(n)
im ENdeffekt erhälst du d dann mittels ggT (phi(n),e) (das errechnete y ist dann das d)
hoffe dir geholfen zu haben...
damit ist Phi(77) = (11-1)*(7-1)=10*6 = 60
nun musst du noch d, welches das INverse von e mod phi(n) ist, berechnen, sprich
d*e = 1 mode phi(n)
im ENdeffekt erhälst du d dann mittels ggT (phi(n),e) (das errechnete y ist dann das d)
hoffe dir geholfen zu haben...