Seite 1 von 1

Digitale Signatur

Verfasst: 12. Mär 2011 21:27
von FGB
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

Re: Digitale Signatur

Verfasst: 12. Mär 2011 21:39
von gravok
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.
Im Allgemeinen geht dies nicht. Die Faktorisierung von n ist (für genügend große n) ein hartes Problem.
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

Verfasst: 12. Mär 2011 22:22
von FGB
Vielen Dank.

Man man man, ich dachte schon, es gibt doch eine "offizelle" Methode das auszurechnen oO

Grüße und nochmals danke,
Felix

Re: Digitale Signatur

Verfasst: 12. Mär 2011 22:48
von tobiwan
FGB hat geschrieben: Man man man, ich dachte schon, es gibt doch eine "offizelle" Methode das auszurechnen oO
Es gibt Algorithmen die p und q ermitteln, sodass man d berechnen kann, aber für große Zahlen dauert das halt Jahre. :wink:

Re: Digitale Signatur

Verfasst: 13. Mär 2011 12:29
von Gerrit
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...