Übung 5

[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

[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.

[x539]

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.

[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.

[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?

[chris_tanase]

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

[redDragonfly]

danke

[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.

[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.

[Capono]

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

[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?

[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.

[einalex]

ah, danke!

[fscheepy]

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

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]

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.