Perfekte Sicherheit eines Kryptosystems

26.02.2025, 18:23

Malcang

Auf diesen Beitrag antworten »

Perfekte Sicherheit eines Kryptosystems

Guten Abend smile

smile

ich beschäftige mich in der Kryptographie gerade mit perfekter Sicherheit.
Sei dazu $\begin{eqnarray*} (\mathcal{M},\mathcal{K},\mathcal{C},e,d) \end{eqnarray*}$ ein Kryptosystem. Dabei ist $\begin{eqnarray*} \mathcal{M} \end{eqnarray*}$ die Klartextmenge,, $\begin{eqnarray*} \mathcal{K} \end{eqnarray*}$ die Schlüsserlmenge und $\begin{eqnarray*} \mathcal{C} \end{eqnarray*}$ die Chiffretextmenge, $\begin{eqnarray*} e \end{eqnarray*}$ bzw. $\begin{eqnarray*} d \end{eqnarray*}$ ist die Encryption- bzw. die Decryptionfunktion.

Nun habe ich weiter diese Definitionen:
[attach]58136[/attach]
[attach]58137[/attach]

Dabei ist $\begin{eqnarray*} I(M,C) \end{eqnarray*}$ die Transinformation von M und C, also $\begin{eqnarray*} I(M,C) = H(M) - H(M|C) \end{eqnarray*}$ , wobei $\begin{eqnarray*} H \end{eqnarray*}$ die Entropie bezeichnet. Auch dazu vielleicht die Definitionen:
[attach]58138[/attach]
[attach]58139[/attach]

Wir haben nun diese beiden Sätze:
[attach]58140[/attach]
[attach]58141[/attach]

So, nun die Aufgabe:
[attach]58142[/attach]

(a) Konnte ich durch Anwendung von Satz 1.3.21 lösen.
Aber zu (b) und (c) verstehe ich leider wirklich nicht, was zu tun ist.
Für (b) sagt die Musterlösung ganz knapp
[attach]58143[/attach]

aber ich steige da nicht durch.

Kann mir jemand weiterhelfen?

26.02.2025, 19:24

URL

Auf diesen Beitrag antworten »

RE: Perfekte Sicherheit eines Kryptosystems
Kann man b) nicht auch mit 1.3.21 lösen? Für m=0 und c=0 sind k=0 und k=5 zwei passende Schlüssel.

Was die Musterlösung angeht: Im ersten Schritt wird die Verschlüsselungsfunktion benutzt, im zweiten die Unabhängigkeitn von K und M. Dann benutzt man letztlich meine Beobachtung von oben.

26.02.2025, 19:38

Malcang

Auf diesen Beitrag antworten »

Danke sehr URL für deine Antwort, ich schaue sie mir in Ruhe an.

Was deine bemerkung zu den zwei Schlüsseln angeht: Die Musterlösung sagt, dass auch (c) perfekt sicher ist:
Es ist $\begin{eqnarray*} |\mathcal{K}| = 10 \end{eqnarray*}$ . Da $\begin{eqnarray*} \lbrack k\rbrack_5 = \lbrack k+5\rbrack_5 \forall k=0,\dots 4 \end{eqnarray*}$ gibt es also für alle $\begin{eqnarray*} m \in \mathcal{M}, c\in\mathcal{C} \end{eqnarray*}$ genau zwei Schlüssel, d.h. $\begin{eqnarray*} P(C=c | M=m) = \frac{1}{5}\forall m\in\mathcal{M}, c\in\mathcal{C}. \end{eqnarray*}$
Also ist das System perfekt sicher

Edit: Nein, man kann (b) mit dem Satz nicht lösen, die Voraussetzung dass alle Mengen gleichgroß sind ist verletzt.

26.02.2025, 19:49

URL

Auf diesen Beitrag antworten »

Ach klar, der schlüsselraum ist ja bei b) auch schon größer, deswegen kann man den Satz nicht verwenden.

26.02.2025, 19:53

Malcang

Auf diesen Beitrag antworten »

Hm, aber damit fällt doch dann auch deine zweite Anmerkung, oder? Denn das meinst du doch mit der "Beobachtung von oben"?

26.02.2025, 19:59

URL

Auf diesen Beitrag antworten »

Nein, es gibt zwei geeignete Schlüssel. Daher ist die Wahrscheinlichkeit 2/6=1/3

Anzeige

26.02.2025, 21:27

Malcang

Auf diesen Beitrag antworten »

Achso ist das gemeint. Danke URL ich schaue mir das morgen ausgeschlafen nochmal an. Würde mich freuen wenn du dann wieder reinschaust smile

smile

27.02.2025, 14:52

Malcang

Auf diesen Beitrag antworten »

Hallo nochmal,

ich konnte die Lösung bisher leider nicht nachvollziehen.
In der Lösung berechnen wir ja nun $\begin{eqnarray*} P(C=0|M=0) \end{eqnarray*}$ , das ist also aus der Formel für $\begin{eqnarray*} H(C|M) \end{eqnarray*}$ . Ich denke also dass hier $\begin{eqnarray*} I(M, C) = I(C,M) = H(C) - H(C|M) \end{eqnarray*}$ zugrunde liegt, aber ich kriege noch kein Verständnis für die Aussage verwirrt

verwirrt

27.02.2025, 20:53

URL

Auf diesen Beitrag antworten »

Zum Verständnis: Du hast $\begin{eqnarray*} P(C=0|M=0)=1/3 \end{eqnarray*}$ und $\begin{eqnarray*} P(C=0|M=1)=1/6 \end{eqnarray*}$ .
Wenn du also nur den Ciphertext $\begin{eqnarray*} C=0 \end{eqnarray*}$ beobachtest, ist die Chance, dass $\begin{eqnarray*} M=0 \end{eqnarray*}$ doppelt so groß wie $\begin{eqnarray*} M=1 \end{eqnarray*}$ . Allein aus der Beobachtung von C=0 bekommst du also eine Information über M und das darf bei einem perfekt sicheren Kryptosystem nicht sein.

Zu der elenden Rechnerei: Es wird wohl darauf hinauslaufen, dass $\begin{eqnarray*} H(M) \end{eqnarray*}$ maximal ist, weil es die Entropie der Gleichverteilung ist. Aus $\begin{eqnarray*} P(C=0|M=0)=1/3 \end{eqnarray*}$ und $\begin{eqnarray*} P(C=0|M=1)=1/6 \end{eqnarray*}$ schließt man, dass $\begin{eqnarray*} H(M|C) \end{eqnarray*}$ die Entropie einer anderen Verteilung, also nicht maximal, also nicht gleich $\begin{eqnarray*} H(M) \end{eqnarray*}$ sein kann.

02.03.2025, 09:16

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von URL
...

Hi URL,

danke für deine Antwort, ich glaube ich habe das Konzept dahinter verstanden. Ich werde mir das in Ruhe nochmal anschauen, aber das hat mir sehr geholfen. Danke smile

smile

21.03.2025, 17:15

Malcang

Auf diesen Beitrag antworten »

Hallo mal wieder smile

smile

ich habe das Konzept denk ich verstanden und wollte es nun mit einer weiteren Aufgabe festigen. An einer Stelle hapert es allerdings noch.

Die Aufgabe ist
[attach]58205[/attach]

Nun, ich habe doch $\begin{eqnarray*} \mathbb Z_9^{*} = \{ 1,2,4,5,7,8 \} \end{eqnarray*}$ und $\begin{eqnarray*} \mathcal{K} \end{eqnarray*}$ ist die Menge der ganzen Zahlen von $\begin{eqnarray*} 0 \end{eqnarray*}$ bis einschließlich $\begin{eqnarray*} 80 \end{eqnarray*}$ , die nicht durch drei teilbar sind. nach Euler ist $\begin{eqnarray*} \varphi(\mathcal{K}) = 3^4-3^3 = 54 \end{eqnarray*}$ .

Nun betrachte ich den Ausdruck $\begin{eqnarray*} P(C = c | M=m) = \frac{|\{k\in\mathcal{K}: m\cdot [k]_9 = c\}|}{54} \end{eqnarray*}$ .

Da $\begin{eqnarray*} m \end{eqnarray*}$ und $\begin{eqnarray*} c \end{eqnarray*}$ ebenfalls invertierbar sind, gilt $\begin{eqnarray*} [k]_9 = m\cdot c^{-1}\pmod 9 \end{eqnarray*}$

Aber nun fehlt mir der entscheidende Schritt. Ich will ja darauf hinaus, dass die Menge im Zähler unabhängig von m und c gleichviele Elemente hat.... verwirrt

verwirrt

21.03.2025, 18:11

URL

Auf diesen Beitrag antworten »

$\begin{eqnarray*} mc^{-1}\in\mathbb Z_9^* \end{eqnarray*}$ ist ein Schlüssel, die übrigen müssen dazu kongruent mudulo 9 sein und in $\begin{eqnarray*} \cal K \end{eqnarray*}$

21.03.2025, 18:16

Malcang

Auf diesen Beitrag antworten »

Hi URL,

danke erstmal für deine Antwort. Ich steige noch nicht ganz durch. Was meinst du mit den "Übrigen"?

Ich tue mir vor allem wegen $\begin{eqnarray*} [k]_9\cdot m \end{eqnarray*}$ schwer. Das eine ist eine Restklasse, das andere eine natürliche Zahl. So ohne weiteres dürfte ich die doch gar nicht multiplizieren.

Mit einem Baumdiagramm konnte ich mir zumindest schonmal helfen.
Es wird die Nachricht $\begin{eqnarray*} m \end{eqnarray*}$ gesendet. Nun wird diese verschlüsselt, indem ich $\begin{eqnarray*} c = [k]_9\cdot m \end{eqnarray*}$ bilde. Es gibt $\begin{eqnarray*} 9 \end{eqnarray*}$ Möglichkeiten, dass $\begin{eqnarray*} k \end{eqnarray*}$ zu wählen, demnach ist $\begin{eqnarray*} P(C=c | M=m) = \frac{9}{54} = \frac{1}{6}. \end{eqnarray*}$

Aber das Formelle habe ich noch nicht richtig geblickt...

21.03.2025, 19:22

URL

Auf diesen Beitrag antworten »

Es gibt mehrere Schlüssel $\begin{eqnarray*} k\in \cal K \end{eqnarray*}$ , die $\begin{eqnarray*} m \end{eqnarray*}$ in $\begin{eqnarray*} c \end{eqnarray*}$ überführen. Beispiel $\begin{eqnarray*} m=2, k=7 \end{eqnarray*}$ liefert $\begin{eqnarray*} [km]_9=5 \end{eqnarray*}$ und ebenso liefert $\begin{eqnarray*} k=16 \end{eqnarray*}$ das Ergebnis $\begin{eqnarray*} [32]_9=5 \end{eqnarray*}$ .

Zitat:

Ich tue mir vor allem wegen $\begin{eqnarray*} [k]_9 \cdot m \end{eqnarray*}$ schwer. Das eine ist eine Restklasse, das andere eine natürliche Zahl. So ohne weiteres dürfte ich die doch gar nicht multiplizieren.

$\begin{eqnarray*} m\in \mathbb Z_9^* \end{eqnarray*}$ ist auch eine Restklasse, auch wenn die Notation das nicht offensichtlich macht smile

smile

Das Ergebnis muss auch 1/6 sein, denn das ist die Wahrscheinlichkeit, zufällig eine Nachricht aus $\begin{eqnarray*} \mathbb Z_9^* \end{eqnarray*}$ zu wählen. Damit ist dann $\begin{eqnarray*} P(C=c|M=m)=P(M=m) \end{eqnarray*}$ , wie es sein muss: Die Kenntnis des Chiffretextes gibt einem keine Information über die Nachricht.

21.03.2025, 19:55

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von URL
Das Ergebnis muss auch 1/6 sein, denn das ist die Wahrscheinlichkeit, zufällig eine Nachricht aus $\begin{eqnarray*} \mathbb Z_9^* \end{eqnarray*}$ zu wählen. Damit ist dann $\begin{eqnarray*} P(C=c|M=m)=P(M=m) \end{eqnarray*}$ , wie es sein muss: Die Kenntnis des Chiffretextes gibt einem keine Information über die Nachricht.

geschockt

Super!! Das hat mich richtig weitergebracht beim Verständnis, vielen Dank dafür! Genau so eine Erklärung brauche ich außerhalb des Formelwusts. Toll, danke Freude

Freude

Zitat:

$\begin{eqnarray*} m\in \mathbb Z_9^* \end{eqnarray*}$ ist auch eine Restklasse, auch wenn die Notation das nicht offensichtlich macht smile

smile

Ja, irgendwie dachte ich in diese Richtung, aber ich kam nicht ganz dahinter. Ich schreibe eine Klausur in diesem Fach und will dann natürlich formal ganz korrekt sein. In einer mündlichen Prüfung könnte ich das ja mal eben in zwei Sätzen erklären.
Aber schriftlich?

Zitat:

Da $\begin{eqnarray*} m\in\mathbb Z_9^* \end{eqnarray*}$ gewählt ist, gilt $\begin{eqnarray*} m=[m]_9 \end{eqnarray*}$ .

Hmmm...ob das wohl ginge? verwirrt

verwirrt

21.03.2025, 20:04

URL

Auf diesen Beitrag antworten »

In meiner Welt reicht $\begin{eqnarray*} m\in\mathbb Z _9^* \end{eqnarray*}$ vollkommen aus. Dass es sich um Äquivalenzklassen handelt, ist bekannt - und spielt meisten keine Rolle smile

smile

Hier hat man es natürlich mit dem Umstand zu tun, dass man zu den Elementen aus $\begin{eqnarray*} \cal K \end{eqnarray*}$ - und das sind jetzt wirklich ganze Zahlen - auch deren Äquivalenzklasse in $\begin{eqnarray*} \mathbb Z_9 \end{eqnarray*}$ braucht. Um das zu verdeutlichen hat der Autor vermutlich $\begin{eqnarray*} [k]_9\cdot m \end{eqnarray*}$ geschrieben. Damit hat man es mit dem Produkt zweier Äquivalenzklassen zu tun - wie es sein soll.

21.03.2025, 20:05

URL

Auf diesen Beitrag antworten »

Mein eigener Doppelpost Big Laugh

Big Laugh

21.03.2025, 20:18

Malcang

Auf diesen Beitrag antworten »

URL, ich danke dir vielmals dass du dir soviel Zeit nimmst. Ich muss das alles jetzt mal über Nacht verarbeiten, werde mich aber morgen wieder melden smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »