Seite 1 von 3

Übung 5

Verfasst: 7. Mär 2012 15:26
von chris_tanase
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

Re: Übung 5

Verfasst: 7. Mär 2012 16:26
von gregor
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.

Re: Übung 5

Verfasst: 7. Mär 2012 16:32
von x539
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.

Re: Übung 5

Verfasst: 8. Mär 2012 12:26
von c-3po
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.

Re: Übung 5

Verfasst: 8. Mär 2012 16:03
von redDragonfly
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?

Re: Übung 5

Verfasst: 8. Mär 2012 16:24
von chris_tanase
Jip habe für d=7 auch s=65 raus :)

Re: Übung 5

Verfasst: 9. Mär 2012 07:40
von redDragonfly
danke :)

Re: Übung 5

Verfasst: 10. Mär 2012 11:12
von Capono
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.

Re: Übung 5

Verfasst: 10. Mär 2012 11:27
von c-3po
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.

Re: Übung 5

Verfasst: 10. Mär 2012 12:16
von Capono
Achso, danke für den Verweis auf Folie 16, den hatte ich übersehen.

Re: Übung 5

Verfasst: 10. Mär 2012 16:29
von einalex
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?

Re: Übung 5

Verfasst: 10. Mär 2012 16:55
von redDragonfly
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.

Re: Übung 5

Verfasst: 10. Mär 2012 17:21
von einalex
ah, danke!

Re: Übung 5

Verfasst: 10. Mär 2012 21:30
von fscheepy
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?

Re: Übung 5

Verfasst: 10. Mär 2012 22:42
von Matthias Senker
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.