Übung 5

chris_tanase
Erstie
Erstie
Beiträge: 22
Registriert: 23. Okt 2008 18:08

Übung 5

Beitrag von chris_tanase » 7. Mär 2012 15:26

Hi,
zu Übung 5:

a)
Ist es richtig, dass die gegebene Hashfunktion NICHT kollisions-resistent ist, weil durch das "mod n" ja nur 77 verschiedene (0,...,76) Werte angenommen werden können? Ansonsten ist die Hashfunktion ja nur eine Umwandlung von Binär nach Dezimal...

b)
Formel zum signieren aus der 5. Vorlesung S. 15: s = [H(m)]^d (mod n)
d sollte aber eigentlich der private Schlüssel sein, den wir hier allerdings nicht kennen, also was hab ich falsch verstanden?

c)
Meiner Meinung nach ist das Signaturverfahren bezüglich “existential forgery under a chosen message attack” nicht sicher, jedoch weiss ich nicht, was genau hier als Antwort verlangt ist. Kann da jemand was zu sagen?

Viele Grüße,
Chris

gregor
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 14. Okt 2008 07:20
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 5

Beitrag von gregor » 7. Mär 2012 16:26

zur b)

in der aufgabe wird signiert und nicht verschlüsselt. wenn du es mit dem geheimen schlüssel verschlüsselst, kannst du es mit dem öffentlichen entschlüsseln und somit verifizieren.
die unterscheidung wird aber auch im skript gemacht.

x539
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 24. Nov 2010 15:52

Re: Übung 5

Beitrag von x539 » 7. Mär 2012 16:32

chris_tanase hat geschrieben:Hi,
zu Übung 5:

a)
Ist es richtig, dass die gegebene Hashfunktion NICHT kollisions-resistent ist
Ja.
, weil durch das "mod n" ja nur 77 verschiedene (0,...,76) Werte angenommen werden können? Ansonsten ist die Hashfunktion ja nur eine Umwandlung von Binär nach Dezimal...
Begründung ist, weil es trivial ist zwei nachrichten mit gleichem hashwert zu erzeugen. m2 = hash(m1) + N => hash(m1) = hash(m2).
Das eine Hashfunktion nicht kollisions frei ist, ist quasi per deffinition der Fall. (Der hashwert ist im normallfall kleiner als die nachricht, also gibt es mehr Nachrichten als hashwerte und somit kollisionen.)
Kollisions-resistent ist ein hash wenn es schwer ist zwei nachrichten zu erstellen mit dem gleichen hashwert.
b)
Formel zum signieren aus der 5. Vorlesung S. 15: s = [H(m)]^d (mod n)
d sollte aber eigentlich der private Schlüssel sein, den wir hier allerdings nicht kennen, also was hab ich falsch verstanden?
Aber du kannst dir d ausrechnen. 77 zu Faktorisieren ist nicht so schwer.
c)
Meiner Meinung nach ist das Signaturverfahren bezüglich “existential forgery under a chosen message attack” nicht sicher, jedoch weiss ich nicht, was genau hier als Antwort verlangt ist. Kann da jemand was zu sagen?
Hast du dir die Folie angesehen auf die hier verwiesen wird?
Angreifer lässt sich nachrichten m_1, m_2, ... m_n signieren, und generiert eine neue nachricht m = X mit gültiger signatur Y.
„Reality is that which, when you stop believing in it, doesn't go away.“ Philip K. Dick

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

Re: Übung 5

Beitrag von c-3po » 8. Mär 2012 12:26

Du weißt ja schon, dass die Hashfunktion nicht kollisionsresistent ist. Auf Folie 16 - Skript Teil5 findest du noch einen nützlichen Hinweis, der dich zusammen mit den restlichen Hilfen zum Ergebnis bringen sollte.

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

Re: Übung 5

Beitrag von redDragonfly » 8. Mär 2012 16:03

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?

chris_tanase
Erstie
Erstie
Beiträge: 22
Registriert: 23. Okt 2008 18:08

Re: Übung 5

Beitrag von chris_tanase » 8. Mär 2012 16:24

Jip habe für d=7 auch s=65 raus :)

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

Re: Übung 5

Beitrag von redDragonfly » 9. Mär 2012 07:40

danke :)

Capono
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Okt 2011 16:01

Re: Übung 5

Beitrag von Capono » 10. Mär 2012 11:12

Sicherheitsbegriff: Als Spiel
Angreifer generiert Nachricht m0,m1, ...,mn
Richter liefert dazu s0,s1,...,sn
Spiel gewonnen WENN neue Nachricht m=! m0, m1,...,mn und Signatur s berechnen kann.
s= H(m)hochd mod n

Also meiner Meinung nach ist das Verfahren sicher, da H(m) ja nicht bekannt ist. Und daher es den Angreifer schwer macht neue Nachrichten mit der Signatur zu berechnen, daher verliert er mit Hoher Wahrscheinlichkeit.

Oder versteh ich das falsch.
Kann mir da jemand helfen?
In Folie 19 steht ja noch das RSA-Signaturen gegen existential forgeries under chosen message attacks sicher sind.

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

Re: Übung 5

Beitrag von c-3po » 10. Mär 2012 11:27

a) Wir hatten gesagt, dass die Hashfunktion nicht kollisionsresistent ist, da leicht zwei Zahlen gefunden werden können, die den gleichen Hashwert erhalten. H(x) = H(x+n).

b) n=77 ist faktorisierbar, in 11*7.

c) Skript Teil 5 - Folie 16:

- "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!"

Man suche sich also zwei Nachrichten m1 und m2 die den gleichen Hashwert haben und schicke diese an den Richter. Dieser signiert beide Nachrichten und schickt sie zurück. Was man bekommt, sind zwei identische Signaturen. Daraus lässt sich der private Schlüssel d berechnen.

Capono
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Okt 2011 16:01

Re: Übung 5

Beitrag von Capono » 10. Mär 2012 12:16

Achso, danke für den Verweis auf Folie 16, den hatte ich übersehen.

einalex
Nichts ist wie es scheint
Beiträge: 23
Registriert: 23. Aug 2010 13:40

Re: Übung 5

Beitrag von einalex » 10. Mär 2012 16:29

Woraus folgt denn in der b, dass d=7?
Faktorisierung 77 = 7*11 schön und gut aber da fehlt noch ein Schritt in der Argumentation warum einer der Primfaktoren dann d ist.

mit modul4 folie5 kann ich zwar bestätigen das d = 7 ist:
e*d = 1 (mod(phi(n)) also 43 * 7 = 1 (mod 60) check.

aber das ist doch nicht der weg um d zu berechnen..


modul5 Folie 16 "Falls n faktorisiert wird, kann der private Schlüssel berechnet werden"
aha, und wie?

hab ich was übersehn?

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

Re: Übung 5

Beitrag von redDragonfly » 10. Mär 2012 16:55

Doch, d wurde aus ed = 1 mod 60 mit dem Erweiterten Eulerschen Algorithmus berechnet:
\(ed \equiv 1 \text{mod } 60\)
\(\Leftrightarrow 60 \vert ed - 1\)
\(\Leftrightarrow x \cdot 60 = ed - 1\), für irgendein ganzzahliges x
\(\Leftrightarrow 1 = 43 \cdot d - x \cdot 60\) ==> genau das, was der Erw. Eulersche Algo. berechnet.

Ich bin mir nicht sicher, aber dass d zufällig mit einem Primfaktor von 77 übereinstimmt, ist hier nur ein Zufall.

einalex
Nichts ist wie es scheint
Beiträge: 23
Registriert: 23. Aug 2010 13:40

Re: Übung 5

Beitrag von einalex » 10. Mär 2012 17:21

ah, danke!

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

Re: Übung 5

Beitrag von fscheepy » 10. Mär 2012 21:30

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?

Matthias Senker
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 14. Okt 2010 22:42

Re: Übung 5

Beitrag von Matthias Senker » 10. Mär 2012 22:42

fscheepy hat geschrieben: 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?
Das hab ich auch nicht verstanden. Ist aber auch egal. Es ist ja nur existential forgery und kein total break verlangt, das heißt der Angreifer muss gar nicht den privaten Schlüssel berechnen. Er sendet einfach eine Nachricht m an den Richter und bekommt die passende Signatur s. Und weil ja H(m) = H(m + n), ist auch die Signatur der Nachricht (m+n) s (gleicher Hashwert heißt ja auch gleiche Signatur!). Also kann der Angreifer mit m+n und s ein neues, gültiges Paar aus Nachricht und Signatur angeben und der Angriff ist erfolgreich.

Antworten

Zurück zu „Archiv“