Berechnung der Entropie einer Schlüssellänge (Informatik)

Question

Aufgabe:

Sie arbeiten mit einem Kryptosystem, welches als Schlüssel Binärzahlen der Länge 256 benutzt. Leider hat sich jedoch
jemand unbemerkt Zugriff auf Ihren Rechner verschafft und das System manipuliert, so dass die von Ihnen erzeugten
Schlüssel nun nicht mehr alle solche Binärzahlen umfassen, sondern nur solche, die maximal acht Einsen enthalten.

1. Wie viele mögliche Schlüssel gibt es, wenn Ihr Rechner nicht kompromittiert wurde?
2. Wie viele mögliche Schlüssel erzeugt Ihr Rechner nach der Manipulation?
3. Inwieweit ändert sich die Entropie durch die Manipulation?
4. Nehmen Sie an, dass ein Angreifer einen „Brute-Force“-Angriff auf Ihr Kryptosystem startet und dabei 10^11 Passwörter in der Sekunde durchprobieren kann. Wie lange benötigt der Angreifer im schlimmsten Fall, wenn Ihr
Rechner kompromittiert bzw. nicht kompromittiert wurde?

Problem/Ansatz:

1. 2^256 Schlüssel

2. Summe der Bionominalkoeffizienten mit n= 256 und k = 0 bis 8 (hoffe ich)

3. Ich weiß nicht, wie ich das beginnen soll. Die normale Entropie beträgt ja 256 ( 256 *log(2) ).

4. Für einen unkomprimierten Rechner sollte das ja einfach 2*255 / 10^11 sein, da im schlimmsten Fall ja direkt der erste Treffer bei voller 256 Schlüssellänge der richtige wäre. (Wobei der Brute-Force theoretisch nicht bei 1 Stelle beginnen müsste, aber ich gehe davon aus, dass es so gedacht ist). Auch hier weiß ich für den kompromittierten Rechner keinen Anfang...

Liebe Grüße

Comments

Wie lange benötigt der Angreifer im schlimmsten Fall

Ich vermute es ist "im für den Angreifer schlimmsten Fall" gemeint.

Answer 1

2. Summe der Bionominalkoeffizienten mit n= 256 und k = 0 bis 8

Ist richtig. Das ergibt

        \(s\coloneqq 423\,203\,101\,008\,289\)

mögliche Schlüssel. In diesen Schlüsseln befinden sich

        \(h_1 \coloneqq \sum\limits_{k=0}^8k\cdot {256\choose k}=3\,371\,698\,714\,836\,992\)

Einsen von insgesamt

        \(z\coloneqq 256\cdot s = 108\,339\,993\,858\,121\,984\)

Zeichen. Die Wahrscheinlichkeit für eine Eins ist also

        \(p_1 \coloneqq \frac{h_1}{z}\approx 0{,}031121\).

Die Wahrscheinlichkeit für eine Null ist dementsprechend

        \(p_0 \coloneqq 1-\frac{h_1}{z}\approx 0{,}968879\).