Digitale Signatur

[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

[gravok]

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

[FGB]

Vielen Dank.

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

Grüße und nochmals danke,
Felix

[tobiwan]

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.

[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...