Aufgabe 4 - Signaturverfahren

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Aufgabe 4 - Signaturverfahren

Beitrag von SupeRalF »

Hi,
in der Aufgabe 4 findet man das folgende Signaturverfahren:
\(s = (m-xr)k^{-1} \mathrm{mod}(p-1)\)

ich habe das interpretiert als
\(s = (m-xr)\cdot (k^{-1}) \mathrm{mod}(p-1)\)
\(= \frac{(m-xr)}{k} \mathrm{mod}(p-1)\)

abgesehen davon, dass ich noch kein Verifikationsverfahren gefunden habe, hat es mich stutzig gemacht, dass ich mit dem Signaturverfahren sehr schnell in \(\mathbb{Q}\) lande. Ist das so gewollt, oder habe ich da etwas falsch verstanden?

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: Aufgabe 4 - Signaturverfahren

Beitrag von Blub »

Du rechnest doch in der Gruppe Z_(p-1).
Bitte beachte das k^(-1) dort nicht bedeutet /k zu rechnen. k^(-1) ist lediglich das inverse Element zu k.
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Re: Aufgabe 4 - Signaturverfahren

Beitrag von SupeRalF »

Oh danke... an diese Interpretation des -1 hab ich gar nicht gedacht :oops: . dann werde ich wohl mit dem Denken nochmal von vorne anfangen^^

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Re: Aufgabe 4 - Signaturverfahren

Beitrag von SupeRalF »

Also trotz der Korrektur meiner (etwas peinlichen) Fehlinterpretation des -1 konnte ich auch nach vielen Stunden keine Verifikation für das angegebene Signaturverfahren finden. Das extrahieren von \(m\) aus \(s\) nur mithilfe von \(y\) und \(r\) scheint mir jedenfalls unmöglich zu sein... ichs schaffe es lediglich auf \(g^m\) zu kommen.
Ist es vielleicht möglich, die m-te Wurzel aus (g^m) zu ziehen?
Ich wäre sehr dankbar, wenn mir jemand einen tip geben könnte, wie ich überhaupt vorgehen muss.

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: Aufgabe 4 - Signaturverfahren

Beitrag von Blub »

SupeRalF hat geschrieben:Also trotz der Korrektur meiner (etwas peinlichen) Fehlinterpretation des -1 konnte ich auch nach vielen Stunden keine Verifikation für das angegebene Signaturverfahren finden. Das extrahieren von \(m\) aus \(s\) nur mithilfe von \(y\) und \(r\) scheint mir jedenfalls unmöglich zu sein... ichs schaffe es lediglich auf \(g^m\) zu kommen.
Ist es vielleicht möglich, die m-te Wurzel aus (g^m) zu ziehen?
Ich wäre sehr dankbar, wenn mir jemand einen tip geben könnte, wie ich überhaupt vorgehen muss.
nein die m-te wurzel ziehen geht nicht ;)
Hm mit einem Tipp wäre die ganze Sache schon quasi gelöst ^^ aber du hast ja noch gut nen Monat zeit,vllt kommst du ja noch drauf :)
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Re: Aufgabe 4 - Signaturverfahren

Beitrag von SupeRalF »

Blub hat geschrieben:Hm mit einem Tipp wäre die ganze Sache schon quasi gelöst ^^ aber du hast ja noch gut nen Monat zeit,vllt kommst du ja noch drauf :)
Also das hat mir jetzt wenig geholfen^^
Ist denn mein Weg, erstmal g^m zu bestimmen richtig, oder muss ich anders rangehen?

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: Aufgabe 4 - Signaturverfahren

Beitrag von Blub »

SupeRalF hat geschrieben:
Blub hat geschrieben:Hm mit einem Tipp wäre die ganze Sache schon quasi gelöst ^^ aber du hast ja noch gut nen Monat zeit,vllt kommst du ja noch drauf :)
Also das hat mir jetzt wenig geholfen^^
Ist denn mein Weg, erstmal g^m zu bestimmen richtig, oder muss ich anders rangehen?
mit dem g^m liegst du doch schon ganz gut. Der Post davor klang auch schon ganz gut.
Du musst dir jetzt überlegen was hast du alles bei einem Signaturverfahren, und was muss bei welcher Rechnung übereinstimmen, das du sicher gehen kannst das die Sig gültig ist.
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Re: Aufgabe 4 - Signaturverfahren

Beitrag von SupeRalF »

ich habe noch einige Zeit drüber nachgedacht, aber ich bin zu keiner Lösung gekommen, die micht 100%ig überzeugt hat.
Wenn ich mir irgendein Element aus \(\mathbb{Z}_p^*\) wähle... wie wahrscheinlich ist es, dass ich einen Generator erwische? wenn die Wahrscheinlichkeit sehr gering ist, dann hätte ich eventuell die richtige Lösung...

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: Aufgabe 4 - Signaturverfahren

Beitrag von Blub »

SupeRalF hat geschrieben:ich habe noch einige Zeit drüber nachgedacht, aber ich bin zu keiner Lösung gekommen, die micht 100%ig überzeugt hat.
Wenn ich mir irgendein Element aus \(\mathbb{Z}_p^*\) wähle... wie wahrscheinlich ist es, dass ich einen Generator erwische? wenn die Wahrscheinlichkeit sehr gering ist, dann hätte ich eventuell die richtige Lösung...
Es existieren \(\phi(\phi(n))\) Generatoren in \(Z_n\).

Allerdings sollte deine Verifikation immer klappen, und nicht mit einer Wahrscheinlichkeit unter 1 ;-)
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

SLik_
Neuling
Neuling
Beiträge: 10
Registriert: 30. Nov 2009 15:10

Re: Aufgabe 4 - Signaturverfahren

Beitrag von SLik_ »

Du musst dir jetzt überlegen was hast du alles bei einem Signaturverfahren, und was muss bei welcher Rechnung übereinstimmen, das du sicher gehen kannst das die Sig gültig ist.
Aus der Aufgabenstellung lese ich, dass man in Aufgabe 4b1 zum Verifizieren ausschließlich {m, s, r, y} habe.
Kennt der Verifizierende ebenso p und g? Bei DSA ist das ja der Fall.
Dann hätte ich eine Lösung :)

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Re: Aufgabe 4 - Signaturverfahren

Beitrag von SupeRalF »

SLik_ hat geschrieben:Kennt der Verifizierende ebenso p und g?
also p kennt er natürlich, denn sonst könnte er ja gar kein m wählen, welches signiert werden kann.
Ob er auch g kennt würde mich jetzt auch echt interessiert. wenn dem so währe, hätte ich die Lösung schon seit eingen Tagen ohne es zu wissen -.-

SLik_
Neuling
Neuling
Beiträge: 10
Registriert: 30. Nov 2009 15:10

Re: Aufgabe 4 - Signaturverfahren

Beitrag von SLik_ »

SupeRalF hat geschrieben: also p kennt er natürlich, denn sonst könnte er ja gar kein m wählen, welches signiert werden kann.
Man will doch lediglich eine bekannte Nachricht m mit Hilfe der Signatur auf Integrität prüfen;
daher muss p - zumindest aus diesem Grund - nicht bekannt sein.

Also erwarten wir weiterhin die Antwort auf die Frage bezüglich der Kenntnis von p und g seitens des Verifizierenden. :)

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Aufgabe 4 - Signaturverfahren

Beitrag von Steven »

Domänenparameter werden bei Kryptoverfahren implizit als öffentlich angenommen. Dazu würde ich hier auch das p und das g zählen. Das ist z.B. bei der ElGamal-Verschlüsselung ja auch so. Man einigt sich auf eine Gruppe - hier Zp* - und damit auch auf ein p, das dann jeder kennt. Den Generator geheim zu halten ist sinnlos, den kann sich zur Not eh jeder selbst ausrechnen.

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: Aufgabe 4 - Signaturverfahren

Beitrag von Dennis Albrecht »

Steven hat geschrieben:Domänenparameter werden bei Kryptoverfahren implizit als öffentlich angenommen. Dazu würde ich hier auch das p und das g zählen. Das ist z.B. bei der ElGamal-Verschlüsselung ja auch so. Man einigt sich auf eine Gruppe - hier Zp* - und damit auch auf ein p, das dann jeder kennt. Den Generator geheim zu halten ist sinnlos, den kann sich zur Not eh jeder selbst ausrechnen.
Ich würde dem zwar insofern zustimmen, dass ich auch mal davon ausgehen würde, dass p und g bekannt sind, aber würde anmerken, dass sich die Werte \(g^x\) sowohl bei variablem x als auch bei variablem g variieren (jeder Generator kann die gesamte Menge erzeugen, aber ein anderer Generator erzeugt die Menge im Allgemeinen in einer anderen Reihenfolge: \(g_1^x\neq g_2^x\)). Daher ist der Generator auch sowohl für die Codierung als auch für die Signierung entscheidend. Es ist natürlich möglich einen Generator zu finden und wenn bekannt ist, dass es per Definition der kleinste, der größte <p, etc ist, dann ist g auch eindeutig, aber sollte an g keine Bedingung geknüpft sein, wäre die Person, die den Schlüssel generiert hat sehr einsam, wenn sie g nicht mitteilen würde. Dann könnten auch keine Nachrichten verschickt werden (bzw könnte der Empfänger nicht umbedingt dechiffrieren), daher ist g wohl bekannt.

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Aufgabe 4 - Signaturverfahren

Beitrag von Steven »

Du hast natürlich Recht, dass der Generator nicht eindeutig ist. Ich bin jetzt implizit davon ausgegangen, dass man den kleinsten nicht-negativen Generator nimmt und das wäre dann eindeutig. Nehme ich irgeneinen anderen Generator und sage das keinem, macht das ganze Verfahren wenig Sinn.

Antworten

Zurück zu „Archiv“