Anzahl Möglichkeiten eines manipulierten 256Bit Schlüssels

Question

Ich bin etwas am verzweifeln, vermutlich ist es einfachste Mathematik, aber ich komme um diese Uhrzeit echt nicht mehr drauf. Eigentlich geht es um 2 Fragen, wobei ich die eine bereits (hoffentlich richtig gelöst habe).

1. Aufgabe:

Es wird ein 256Bit Key genutzt, der jedoch kompromittiert wurde, sodass nur noch Schlüssel in Betracht kommen, die maximal 8 Einsen nutzen.

Problem/Ansatz:

Ein normaler Key hätte 2^256 Möglichkeiten. Und da hört es bei mir schon auf. 2^8 wäre Quatsch, da die länge von 256 Zeichen gegeben bleibt.

2. Aufgabe:

Sie nehmen an zwei Quiz-Shows teil:
1. Es gibt eine Urne mit insgesamt 10 Bällen, die mit den Zahlen 1 bis 10 beschriftet sind, sodass jede Zahl genau
einmal darin vorkommt. Der Spielleiter zieht nun einen Ball und bittet Sie, die darauf angegebene Nummer zu
raten.
2. Der Spielleiter wirft von Ihnen unbemerkt so lange eine Münze, bis er das Ergebnis Kopf erhält. Gelingt ihm dies
in den ersten 10 Versuchen nicht, so hört er auf. Sie sollen nun raten, wie häufig er die Münze geworfen hat.
In beiden Fällen dürfen Sie Fragen stellen, allerdings nur solche, die mit ja oder nein beantwortet werden können. Der
Spielleiter beantwortet jede solche Frage korrekt.
Sie haben jeweils ein Startkapital von 1000 Euro; für jede Frage werden Ihnen 100 Euro abgezogen. Sie dürfen jederzeit
eine Zahl benennen, um das Quiz zu beenden. Ist die Zahl korrekt, erhalten Sie das verbleibende Kapital, andernfalls
gehen Sie leer aus.
Wie verhalten Sie sich beim ersten bzw. beim zweiten Quiz, um einen möglichst hohen Gewinn zu erzielen?

Problem/Ansatz:

Ich würde bei beiden einfach immer größer/kleiner Fragen stellen, wobei ich bei den Münzen bei 6 beginnen würde, für den Fall, dass mehr als 10 benötigt wurden. Laut Entropie ergibt das maximal 4 Fragen für beide Situationen.

Liebe Grüße

Answer 1

nur noch Schlüssel in Betracht kommen, die maximal 8 Einsen nutzen.

Aus n Stellen werden k Stellen ausgesucht, an denen die Einsen stehen. Dazu gibt es \(\binom{n}{k}\) Möglichkeiten.

Summiere von k = 0 bis 8 für n = 256.

Answer 2

Aloha :)

1) Es gibt \(\binom{256}{k}\) Möglichkeiten, genau k Eins-Bits unter den den 256 mögichen Bits zu setzen. Da wir wissen, dass maximal 8 Eins-Bits vorkommen können, müssen wir die 9 Werte von \(k=0\) bis \(k=8\) addieren:$$\sum\limits_{k=0}^8\binom{256}{k}=423.203.101.008.289$$

2) Ich würde die möglichen Intervalle bei jeder Frage halbieren. Also fragen, ob die Zahl <=5 ist? Wenn ja, fragen, ob die Zahl <=3 ist. Wenn nein, fragen, ob sie <=8 ist...