Übung 5

allein
Mausschubser
Mausschubser
Beiträge: 60
Registriert: 15. Okt 2008 00:01

Re: Übung 5

Beitrag von allein »

fscheepy hat geschrieben:
c-3po hat geschrieben: - "Falls n faktorisiert wird, kann der private Schlüssel berechnet werden"
- "Sicherheit basiert auf der Kollisionsfreiheit von H: zwei Nachrichten m1,m2 mit H(m1)=H(m2) haben die gleiche Signatur!"
Geht man denn hier davon aus, dass der Angreifer die Hashfunktion kennt? Ich gehe mal davon aus, da jeder die Möglichkeit hat, die Gültigkeit einer Signatur zu überprüfen, wofür er wiederum die Hashfunktion kennen muss. Oder habe ich da etwas falsch verstanden?
c-3po hat geschrieben: Was man bekommt, sind zwei identische Signaturen. Daraus lässt sich der private Schlüssel d berechnen.
Wie soll das gehen, wenn nicht über die Zerlegung von n?
1) Ja, die Hash-Funktion ist öffentlich bekannt.
2) Wenn die Hash Funktion nicht kollisionsresistent ist, wie in der Aufgabe, dann kann man mit einem neuen Nachricht m' eine H(m') rechnen mit H(m')=H(m). Signieren bedeutet s=H(m)^d mod n=H(m')^d mod n. Somit kann man einen neuen Nachricht als signierte Nachricht schicken.

Bei Teil c geht es aber nicht darum, dass man d rechnen will. Oder?

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Übung 5

Beitrag von fscheepy »

allein hat geschrieben: Bei Teil c geht es aber nicht darum, dass man d rechnen will. Oder?
Nein, aber das muss man ja bei Aufgabenteil b) sowieso schon erledigen. Meine Frage ging eher darum, dass ich nicht verstehe, wie man aus zwei identischen Signaturen den Schlüssel d berechnen soll. Der Knackpunkt der Aufgabe ist ja eigentlich, dass man, wenn man Kollisionen in der Hashfunktion kennt (welche hier sehr einfach zu bestimmen sind), sich zu einer Nachricht m mit Signatur s eine Nachricht m' mit der gleichen Signatur s wählen kann (und zwar so, dass H(m) = H(m')). Den privaten Schlüssel hingegen sollte man nur über eine Zerlegung von n bestimmen können, oder habe ich da etwas verpasst/falsch verstanden?

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: Übung 5

Beitrag von R_Egert »

Falls ihr n faktoriesieren könnt, dann könnt ihr auch d berechnen^^, darauf basiert ja die gesamte Sicherheit. Und das Berechnen dieses Schlüssels wäre ein Total Break.

Im Aufgabenteil c) geht es nur darum zu zeigen, ob es sicher ist im sinne von "Existential Forgery under choosen message attack". D.H. Ist es dem Angreifer möglich ein gültiges Nachrichten-Signaturen-Paar zu erstellen ohne die Nachricht zuvor an einen gültigen Signierer geschickt zu haben.

grüsse Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Flo S
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 27. Apr 2010 22:50

Re: Übung 5

Beitrag von Flo S »

allein hat geschrieben: 1) Ja, die Hash-Funktion ist öffentlich bekannt.
2) Wenn die Hash Funktion nicht kollisionsresistent ist, wie in der Aufgabe, dann kann man mit einem neuen Nachricht m' eine H(m') rechnen mit H(m')=H(m). Signieren bedeutet s=H(m)^d mod n=H(m')^d mod n. Somit kann man einen neuen Nachricht als signierte Nachricht schicken.

Bei Teil c geht es aber nicht darum, dass man d rechnen will. Oder?
Warum ist die Hash-Funktion öffentlich bekannt?

Nach unserem normalen Modell hätten wir einen Angreifer, der alle "öffentlichen" Informationen kennt, in diesem Falle also den Public Key (n,e), also (77,43). Darüber hinaus hat er keine Informationen über das System. Alles was er machen kann ist dem Richter beliebige Nachrichten zu schicken und er bekommt die Signatur dieser Nachricht zurück.

Wir haben in der c.) also zwei mögliche Lösungen
1.) Faktorisierung von d. Wir haben das in Aufgabenteil b.) geschafft, also kann das auch jeder Angreifer
2.) Viele Nachrichten schicken mit m_(i+1) = m_i + 1 und m_0 = 1.
Nach 77 Nachrichten fangen die Signaturen an sich zu wiederholen in der gleichen Reihenfolge. Der Angreifer kann nun also probieren zu eine Nachricht m_77+n mit n aus {0, 67} die Signatur von m_n an den Richter zu schicken. Er kann sich aber nicht sicher sein, ob diese Signatur stimmt, da er selber die Hashfunktion nicht kennt, sondern nur weiß, dass sie sich "bis jetzt" wie mod 77 verhalten hat.

allein
Mausschubser
Mausschubser
Beiträge: 60
Registriert: 15. Okt 2008 00:01

Re: Übung 5

Beitrag von allein »

Hash Funktion ist öffentlich bekannt, aber es bringt normalerweise nichts sie zu wissen. Warum ist öffentlich bekannt? weil alle Clients, die mit einem Server kommunizieren wollen, der diese Hash Funktion benutzt um Nachrichten zu signieren, müssen in der Lage sein,den Hashwert von dem original Nachricht zu rechnen. Somit vergleichen sie das Ergebnis mit dem Hashwert, was sie von dem Signatur abgeleitet haben.

c-3po
Erstie
Erstie
Beiträge: 11
Registriert: 4. Nov 2010 17:16

Re: Übung 5

Beitrag von c-3po »

Man kann in Aufgabe c) aus den zwei Signaturen natürlich nicht den privaten Schlüssel d berechnen. Das war Kokolores. Sry dafür ;) Es geht wie schon mehrfach erwähnt, nur über die Faktorisierung von n.

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: Übung 5

Beitrag von R_Egert »

Man geht grundsätzlich davon aus, dass ein Angreifer sämtliche Mechanismen die man selbst nutzt kennt. Sei es nun das Verschlüsselungsverfahren oder eine genutzte Hashfunktion^^ was er nicht kennt ist eben der geheime Schlüssel ;)

mfg Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

duongel
Neuling
Neuling
Beiträge: 8
Registriert: 20. Mai 2012 11:17

Re: Übung 5

Beitrag von duongel »

redDragonfly hat geschrieben:Ich hab das versucht mal nachzurechnen (war in der Übung leider nicht anwesend :( ) und habe für d=7 die Signatur s = 65 raus.
Kann das jemand bestätigen?
hi, kann mir jemand verraten warum
s = 65 und nicht s = 65^7 mod 77 ist?

steh ich zu später stunde auf dem schlauch?

sorry muss die veranstaltung jetzt als auflage machen und konnte daher weder vorlesungen noch übungen besuchen

gruß duong

redDragonfly
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2010 22:32

Re: Übung 5

Beitrag von redDragonfly »

Hast du 65^7 mod 77 mal ausgerechnet? ;)

duongel
Neuling
Neuling
Beiträge: 8
Registriert: 20. Mai 2012 11:17

Re: Übung 5

Beitrag von duongel »

redDragonfly hat geschrieben:Hast du 65^7 mod 77 mal ausgerechnet? ;)
hab da 44 raus, kommt da etwa 77??

redDragonfly
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2010 22:32

Re: Übung 5

Beitrag von redDragonfly »

Nein, 65...!
(Und 77 darf da nie rauskommen.)

duongel
Neuling
Neuling
Beiträge: 8
Registriert: 20. Mai 2012 11:17

Re: Übung 5

Beitrag von duongel »

redDragonfly hat geschrieben:Nein, 65...!
(Und 77 darf da nie rauskommen.)
ups ich meinte natürlich nicht 77 sondern 65 :-D

65^7 mod 77 = 65??

ich hab mich auf nen online modulo rechner verlassen der sagt
65^7 mod 77 = 44

:-/ aber danke!

moel
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 19. Apr 2011 13:57

Re: Übung 5

Beitrag von moel »

hab das gleiche raus s= 65.

Aber bei der a) hab ich heraus das die Hashfunktion kollisionsresistent ist da die 2 als generator fungiert, d.h.ich kann alle werte von 1 bis 76 darstellen.
stimmt das?

und bei der c) die Funktion ist sicher gegen existenzielle Fälschung da wir nicht auf die Nachricht kommen sondern nur auf den Hashwert wenn er geknackt werden würde.

redDragonfly
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2010 22:32

Re: Übung 5

Beitrag von redDragonfly »

Hm.... ich hätte da genau das Umgekehrte behauptet:

a) Dass die Hashfunktion nicht kollisionsresistent ist, da H(x) = H(y), mit y = x*77. (Die Definition für "kollisions-resistent" steht bei V5-F4.)

c) Hier würde ich daher entsprechen das Gegenteil behaupten. Wenn ich das jetzt richtig verstehe ist, existential forgery under a chosen message doch, wenn man zu einer (beliebigen, weil "chosen"?) Nachricht eine Signatur erstellen kann. Da wir in a) die Hashfunktion nach nur 77 Testnachrichten "geknackt" haben, kann ich doch eine Signatur für jede x-beliebige Nachricht erstellen (fälschen). Entsprechend ist die Hashfunktion in diesem Sinne nicht sicher... oder?

redDragonfly
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2010 22:32

Re: Übung 5

Beitrag von redDragonfly »

duongel hat geschrieben: ich hab mich auf nen online modulo rechner verlassen der sagt
65^7 mod 77 = 44
Ich weiß leider nicht, wie dieser Onlinerechner arbeitet, aber ich hab's einmal mit Schneller-Exponentation und Taschenrechner und einmal mit Matlab ausgerechnet. Vor allem bei Matlab erwarte ich eigentlich, dass der korrekt modulo rechnen kann ;)

Antworten

Zurück zu „Archiv“