Klausur

Moderator: Einführung in die Kryptographie

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Klausur

Beitrag von Maeher » 10. Feb 2012 17:00

Wenn das längenerhaltend ist, muss das "Verschlüsselungsverfahren" die Identitätsabbildung sein. Ansonsten kann es nicht möglich sein, dass die Ordnung erhalten bleibt.

Tatsächlich geht die ganze Sache aber noch viel einfacher soweit ich das gesehen habe. (Hatte die Ehre euch zu beaufsichtigen, habe die Aufgaben aber auch nur während der Klausur gesehen.)

Wenn das längenerhaltend ist, ist das eine \(\{0,1\}^n \rightarrow \{0,1\}^n\) Abbildung, das heißt Ein- und Ausgabemenge sind gleich mächtig.
Demnach gibt zu jedem Plaintext nur einen Ciphertext. Ergo ist das Verfahren deterministisch und kann nicht IND-CPA sein.

Für den zweiten Teil müsste das auch recht ähnlich sein:

Da \(m_1 \le m_2 \Leftrightarrow C_1 \le C_2\) gilt, gilt insbesondere wegen der Antisymmetrie einer totalen Ordung \(m_1 = m_2 \Leftrightarrow C_1 = C_2\).
Das Verfahren ist also schon wieder deterministisch und somit nicht IND-CPA sicher.
(Außer da war ein \(<\) anstatt ein \(\le\), dann gilt das so nicht.)


Das war allerding soweit ich gesehen habe nicht die Musterlösung.

fischlin
Moderator
Moderator
Beiträge: 54
Registriert: 11. Mai 2006 17:14

Re: Klausur

Beitrag von fischlin » 12. Feb 2012 22:05

Längenerhaltend ist einfacher: dann muss die Verschlüsselungsfunktion die
Identitätsfunktion (im zweiten Argument) sein: Enc(k,m)=m. Die ist natürlich nicht
IND-CPA.

Den Ansatz über die m1=m2 gdw C1=C2 habe ich nicht verstanden. Wieso folgt das
aus m1 =< m2 gdw C1 =< C2? Es könnte doch die Nachrichten auf Ciphertexte der doppelten
Länge abgebildet werden, und dieser Raum in disjunkte Intervalle unterteilt werden, so
dass die Verschlüsselung den Ciphertext C für m aus dem entsprechenden Intervall
zufällig wählt. Dann würde m1=m2 nicht unbedingt C1=C2 implizieren. Oder übersehe
ich hier etwas?

Der Angriff mit "Frage erst die Enc-Box über 100..0, 100...0 und dann über 00..0, 11...1
erlaubt es aber einfach, das geheime Bit zu bestimmen: genau dann ist das 0, wenn der
zweite Ciphertext kleiner als der erste ist.

Die oben diskutierte Lösung mit "Erst m0,m0, dann m0,m1 und Vergleich" ist etwas
komplizierter zu analysieren, denke ich. Es könnte selbst im Fall b=0 sehr wohl dann
der zweite Ciphertext größer als der erste sein -das Verfahren kann ja durchaus
probabilistisch sein. Man müsste dann argumentieren, dass dies wegen der Symmetrie
nur mit Wskeit 1/2 der Fall ist, wöhrend im Fall b=1 dies stets passiert.

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Klausur

Beitrag von Maeher » 12. Feb 2012 22:33

Den Ansatz über die m1=m2 gdw C1=C2 habe ich nicht verstanden. Wieso folgt das
aus m1 =< m2 gdw C1 =< C2? Es könnte doch die Nachrichten auf Ciphertexte der doppelten
Länge abgebildet werden, und dieser Raum in disjunkte Intervalle unterteilt werden, so
dass die Verschlüsselung den Ciphertext C für m aus dem entsprechenden Intervall
zufällig wählt. Dann würde m1=m2 nicht unbedingt C1=C2 implizieren. Oder übersehe
ich hier etwas?
Nun, wenn gilt \(m_1=m_2\) dann gilt insbesondere auch \(m_1 \le m_2\) und \(m_2 \le m_1\).
Aus der Ordnungserhaltung folgt dann \(C_1 \le C_2\) und \(C_2 \le C_1\).
Die Antisymmetrie besagt nun, dass \(C_1 \le C_2\land C_2 \le C_1 \Rightarrow C_1 = C_2\).
Und somit ist das Verfahren deterministisch.

Das mit den disjunkten Intervallen funktioniert nur für \(<\), nicht aber für \(\le\).

fischlin
Moderator
Moderator
Beiträge: 54
Registriert: 11. Mai 2006 17:14

Re: Klausur

Beitrag von fischlin » 13. Feb 2012 16:54

Ha, ha, super. :-)

Habe tatsächlich < gedacht und =< gemacht, also geschrieben. Na, da bin ich ja mal gespannt, wer das auch so
in der Klausur gelöst hat....

Lukas
Neuling
Neuling
Beiträge: 5
Registriert: 18. Jan 2011 16:33

Re: Klausur

Beitrag von Lukas » 13. Feb 2012 17:02

Die Lösung "Erst m0,m0, dann m0,m1 und Vergleich" müsste dann also nicht so "kompliziert" begründet werden, oder?

Antworten

Zurück zu „Einführung in die Kryptographie“