Übung 5
-
- Erstie
- Beiträge: 22
- Registriert: 23. Okt 2008 18:08
Übung 5
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
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
-
- BASIC-Programmierer
- Beiträge: 101
- Registriert: 14. Okt 2008 07:20
- Wohnort: Darmstadt
- Kontaktdaten:
Re: Übung 5
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.
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
Ja.chris_tanase hat geschrieben:Hi,
zu Übung 5:
a)
Ist es richtig, dass die gegebene Hashfunktion NICHT kollisions-resistent ist
Begründung ist, weil es trivial ist zwei nachrichten mit gleichem hashwert zu erzeugen. m2 = hash(m1) + N => hash(m1) = hash(m2)., 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...
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.
Aber du kannst dir d ausrechnen. 77 zu Faktorisieren ist nicht so schwer.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?
Hast du dir die Folie angesehen auf die hier verwiesen wird?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?
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
Re: Übung 5
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.
-
- Windoof-User
- Beiträge: 25
- Registriert: 14. Apr 2010 22:32
Re: Übung 5
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?

Kann das jemand bestätigen?
-
- Erstie
- Beiträge: 22
- Registriert: 23. Okt 2008 18:08
Re: Übung 5
Jip habe für d=7 auch s=65 raus 

Re: Übung 5
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.
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
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.
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
Achso, danke für den Verweis auf Folie 16, den hatte ich übersehen.
Re: Übung 5
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?
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?
-
- Windoof-User
- Beiträge: 25
- Registriert: 14. Apr 2010 22:32
Re: Übung 5
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.
\(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
ah, danke!
Re: Übung 5
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: - "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!"
Wie soll das gehen, wenn nicht über die Zerlegung von n?c-3po hat geschrieben: Was man bekommt, sind zwei identische Signaturen. Daraus lässt sich der private Schlüssel d berechnen.
-
- Windoof-User
- Beiträge: 41
- Registriert: 14. Okt 2010 22:42
Re: Übung 5
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.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?