Seite 1 von 1

Hausübung A4 - b)

Verfasst: 26. Dez 2012 14:53
von L4_
Hallo,

ist das wirklich richtig, dass die Hashfunktion H nach Z_(p-1) abbildet? Müsste es nicht Z_p sein?

Ich habe das mal mit der Nachricht 42, p = 31 und der Funktion h: m^2 mod (p-1) durchgespielt:

- 42^2 mod 30 = 6 (nicht Teilerfremd zu 30)
- Konkateniere "42" + "6" = 426
- 426^2 mod 30 = 6
=> Endlosschleife

Mit h: m^2 mod p klappt das dann schon eher und ich erhalte 19 als ersten Teilerfremden Wert.


EDIT:
Okay, mir fiel gerade auf, dass solche Endlosschleifen natürlich zustande kommen, wenn meine Hashfunktion doof ist (m^2 hinterlässt evtl. Lücken).
Sollen wir annehmen, dass die Funktionen irgendwann mal jeden Hashwert annehmen wird?

Re: Hausübung A4 - b)

Verfasst: 5. Jan 2013 13:40
von postkarte
Hallo,

mir ist nicht genau klar, ob ich bei Aufgabe 4b die Werte aus Aufgabe a wie m = 42 und p = 31 verwenden soll? Und angenommen ich soll mich auf m= 42 beziehen, muss ich dann 42 in binär umwandeln, um die Hashfunktion h anwenden zu können, da der Definitionsbereich ja nur aus 0 und 1 bestehen soll?

Danke

Re: Hausübung A4 - b)

Verfasst: 6. Jan 2013 18:42
von Boddlnagg
Ich versteh das so, dass die Hashfunktion aus a) eigentlich nichts mit Aufgabe b) zu tun hat.
Die in a) ist ja angegeben (und zwar mit H: Z -> Z_n) und die in b) ist beliebig mit H: {0,1}* -> Z_(p-1).

Und ich sehe das Problem auch, dass eventuell das wiederholte Aufrufen von H in b) nicht terminiert ... da sollen wir wohl annehmen, dass die Hashfunktion so gewählt ist, dass irgendwann tatsächlich mal was rauskommt, was zu p-1 teilerfremd ist.

Re: Hausübung A4 - b)

Verfasst: 7. Jan 2013 12:04
von errt
Ist denn gefordert, dass es terminiert? Es muss ja nur gezeigt werden, dass, wenn denn so eine Signatur angefertigt wurde, dass die dann auch korrekt verifiziert wird. Dass es unter Umständen nicht möglich ist, so eine Signatur anzufertigen mit dem Verfahren kann einem dafür doch relativ egal sein.

Re: Hausübung A4 - b)

Verfasst: 14. Jan 2013 22:16
von Aaron_H
Was genau ist denn bei Aufgabe iii) gemeint? Soll man für jede Nachricht in der Lage sein, eine gültige Signatur zu bestimmen?
Wenn ja wäre ich für einen Tipp sehr dankbar.

Re: Hausübung A4 - b)

Verfasst: 19. Jan 2013 20:48
von L4_
Btw:

Wofür brauch der Empfänger im PK eig. das g?
Dass man p und c brauch verstehe ich ja noch, aber für g sehe ich gerade keinen Verwendungszweck als Empfänger.

VG

Re: Hausübung A4 - b)

Verfasst: 20. Jan 2013 09:39
von mmi1991
Gelöscht

Re: Hausübung A4 - b)

Verfasst: 21. Jan 2013 21:32
von AnnaW
Also wenn ich das richtig versteh, dann sind die Punkte 1. , 2. und 3. nur die Erklärung wie das Signaturverfahren richtig funktioniert. Die Fragen die wir beantworten müssen sind dann i), ii) und iii). Ich saß auch erst dran und hab das mit den Werten aus der a) gerechnet. Aber ich glaube so macht das mehr Sinn.

In der Hoffnung, dass das noch wem hilft, der die Aufgaben auch erst nicht findet ^^