Passwort knacken (Wahrscheinlichkeiten)

10.11.2014, 10:49

kombina

Auf diesen Beitrag antworten »

Passwort knacken (Wahrscheinlichkeiten)

Meine Frage:
Folgende Situation: Man möchte ein 6-stelliges Passwort knacken, das aus den Symbolen A bis Z und 0 bis 9 besteht, wobei alle möglichen Kombinationen zufällig und gleichverteilt probiert werden.

Man verwende folgende Taktik: Zuerst wähle man zufällig und gleichverteilt eine Kombination. Dann wähle man zufällig und gleichverteilt eine der 6 Stellen und deren Eintrag ersetze man zufällig und gleichverteilt durch ein Symbol aus $\begin{eqnarray*} \left\{A,...,Z,0,...,9\right\} \end{eqnarray*}$ . Diese Prozedur wiederhole man, bis das Passwort gefunden ist.

(1) Was ist die Wahrscheinlichkeit, dass das korrekte Passwort nie gefunden wird?

(2) Was ist die Wahrscheinlichkeit, dass man irgendwann die gleiche Kombinationen zwei Mal hintereinander probiert?

Meine Ideen:
Hallo,

ich finde diese Aufgabe sehr schwer...

Und ich könnte sehr gut Hilfe gebrauchen.

Mich überfordern die kombinatorischen Überlegungen, die man hier braucht.

10.11.2014, 11:42

HAL 9000

Auf diesen Beitrag antworten »

(2) kann man eigentlich anhand der beschriebenen Taktik sehr einfach ausrechnen:

Die Folgekombination geht aus der aktuellen Kombination dadurch hervor, dass man nur eine der 6 Stellen zufällig neu auswürfelt. Mit welcher Wahrscheinlichkeit ergibt diese Neuauswürfelung also genau dasselbe Symbol (A-Z,0-9), welches vorher an dieser Stelle stand?

--------------------------
Zu (1) erstmal eine Frage: Sind dir Markov-Ketten ein Begriff? Um eine solche handelt es sich hier, und mit deren Theorie lässt sich die Sache hier elegant und schnell beantworten.

10.11.2014, 11:43

kombina

Auf diesen Beitrag antworten »

Hallo,

ja ich kenne Markovketten und mich würde sehr interessieren, wie man es damit schnell und schön lösen kann.

10.11.2014, 11:49

kombina

Auf diesen Beitrag antworten »

Kannst du mir vielleicht erklären, wie ich das ganze Problem als Markov Kette auffassen kann?
Das sehe ich nämlich nícht.

10.11.2014, 11:50

HAL 9000

Auf diesen Beitrag antworten »

Modellmäßig handelt es sich hier um eine Markov-Kette mit endlichem Zustandsraum (genauer: Es sind $\begin{align*} 36^6 \end{align*}$ Zustände). Jeder Zustand ist mit jedem anderen verbunden, denn man kann in 6 Schritten mit positiver (wenn auch sehr kleiner ) Wahrscheinlichkeit von jedem Zustand in jeden anderen gelangen. Daher ist die Kette irreduzibel und damit aufgrund ihrer Endlichkeit auch positiv rekurrent. D.h., es wird jeder Zustand mit Wahrscheinlichkeit 1 unendlich oft angelaufen - und somit wird das korrekte Passwort auch irgendwann mit Wahrscheinlichkeit 1 gefunden.

10.11.2014, 12:03

kombina

Auf diesen Beitrag antworten »

Danke!

Von einem Zustand zum anderen zu kommen, hat die Wahrscheinlichkeit

$\begin{eqnarray*} (\frac{1}{6}\cdot\frac{1}{36})^6=9.8464\cdot 10^{-15} \end{eqnarray*}$ , richtig?

---

positiv rekurrent bedeutet, dass für einen Zustand (ich nenne ihn mal $\begin{eqnarray*} i \end{eqnarray*}$ ) gilt

$\begin{eqnarray*} E(t(i))<\infty \end{eqnarray*}$ , wobei $\begin{eqnarray*} t(i) \end{eqnarray*}$ die erste Rückkehrzeit ist.

Wieso bedeutet $\begin{eqnarray*} E(t(i))<\infty \end{eqnarray*}$ , dass "jeder Zustand mit Wahrscheinlichkeit 1 unendlich oft angelaufen" wird?

Anzeige

10.11.2014, 12:06

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von kombina
Von einem Zustand zum anderen zu kommen, hat die Wahrscheinlichkeit

$\begin{eqnarray*} (\frac{1}{6}\cdot\frac{1}{36})^6=9.8464\cdot 10^{-15} \end{eqnarray*}$ , richtig?

Nein, aber es ist eine korrekte untere Schranke für die Wahrscheinlichkeit, dass dies in genau 6 Schritten geschieht.

Wenn keines der 6 Symbole von beiden Zuständen übereinstimmt, dann lautet diese Wahrscheinlichkeit exakt

$\begin{align*} \frac{6!}{6^6} \cdot \frac{1}{36^6} = \frac{6!}{6^{18}} \approx 7.1\cdot 10^{-12} \end{align*}$ .

Wenn allerdings einige der Symbole bereits stimmen, wird es erheblich komplizierter, der angegebene Wert ist aber sicher eine untere Schranke für den dann zu bestimmenden Wahrscheinlichkeitswert.

Zitat:

Original von kombina
Wieso bedeutet $\begin{eqnarray*} E(t(i))<\infty \end{eqnarray*}$ , dass "jeder Zustand mit Wahrscheinlichkeit 1 unendlich oft angelaufen" wird?

Ach nö, ich mach jetzt keine Markovketten-Vorlesung - lies dir das bitte selber an.

10.11.2014, 12:15

kombina

Auf diesen Beitrag antworten »

D.h. man muss gar nicht genau wissen, mit welcher Wahrscheinlichkeit man von einem Zustand zum anderen kommt, es reicht zu wissen, dass diese Wahrscheinlichkeit nicht 0 ist? Und das ist sie nicht, weil die Wahrscheinlichkeit, die ich ausgerechnet habe, eine untere Schranke ist?

10.11.2014, 12:32

kombina

Auf diesen Beitrag antworten »

Könntest du mir nochmal (2) erklären?

10.11.2014, 12:51

HAL 9000

Auf diesen Beitrag antworten »

Oh, ich hatte oben bei (2) das irgendwann überlesen. Nun, man kann nicht nur $\begin{align*} (X_n)_{n=1,2,\ldots} \end{align*}$ als Markov-Kette betrachten, sondern auch die geordneten Paare von jeweils zwei aufeinander folgenden Zuständne, also $\begin{align*} ((X_n,X_{n+1}))_{n=1,2,\ldots} \end{align*}$ . Sind dann ein paar mehr Zustände, aber sonst alles prinzipiell ähnlich: Wieder Irreduzibilität, usw.

10.11.2014, 18:09

kombina

Auf diesen Beitrag antworten »

Ist folgende Argumentation für (2) dann korrekt:

Als Zustände betrachte man diesesmal die geordneten Paare zweier aufeinander folgender Zustände (der beschriebenen Dekodierungsstrategie). Dann hat man diesmal $\begin{eqnarray*} \binom{36^6}{2} \end{eqnarray*}$ Zustände.

Jeder Zustand (in diesem Sinne) ist dann verbunden mit einem anderen Zustand, weil man (im Bestfall) 18 Schritten von einem Zustand in den anderen kommen kann.

Also ist der Zustandsraum irreduzibel und geschlossen und somit hat man also eine geschlossene, endliche Klasse, die dann positiv rekurrent ist.

Damit gilt für ein beliebiges geordnetes Paar $\begin{eqnarray*} i \end{eqnarray*}$ und ein beliebig anderes geordnetes Paar $\begin{eqnarray*} j \end{eqnarray*}$

$\begin{eqnarray*} E_i(t(j))<\infty \end{eqnarray*}$ . (*)

So, wenn jetzt schon der allererste Zustand ist, dass man zwei gleiche Kombinationen hat, ist die gesuchte Wahrscheinlichkeit sowieso 1.

Wenn man am Anfang einen Zustand hat, der aus zwei nicht identischen Kombinationen hat (ich nenne ihn i), und j ein Zustand ist, der aus zwei identischen Kombinationen besteht, sagt (*), dass man j auf lange Sicht gesehen erreicht.

Also ist die gesuchte Wahrscheinlichkeit 1.

---

Mit anderen Worten: Egal, ob man schon ganz zu Beginn einen Zustand hat, der aus zwei identischen Kombinationen besteht, oder, ob man mit irgendeinem geordneten Paar beginnt (dann ist jeder beliebige Zustand, der aus zwei identischen Kombinationen besteht, irgendwann erreicht) - - - die Wahrscheinlichkeit, dass man irgendwann zwei identische Kombinationen hintereinander hat ist 1.

Noch kürzer gesagt: Egal, welche beiden Kombinationen man als die ersten hat... irgendwann (sofort oder irgendwann später) hat man direkt hintereinander zwei Mal die gleiche Kombination. Also ist die gesuchte Wahrscheinlichkeit 1.

10.11.2014, 18:12

kombina

Auf diesen Beitrag antworten »

ich glaube doch eher, dass man $\begin{eqnarray*} 2\cdot\binom{36^6}{2} \end{eqnarray*}$ Zustände hat

10.11.2014, 22:08

kombina

Auf diesen Beitrag antworten »

Hey, lieg ich richtig? Wink

Wink

10.11.2014, 22:15

HAL 9000

Auf diesen Beitrag antworten »

Naja, wirklich erreichbar sind deutlich weniger Zustände:

Für $\begin{align*} X_n \end{align*}$ gibt es $\begin{align*} 36^6 \end{align*}$ Zustände, hatten wir ja bereits festgestellt. Für festes $\begin{align*} X_n \end{align*}$ gibt es aber für $\begin{align*} X_{n+1} \end{align*}$ nur $\begin{align*} 6\cdot 35+1 = 211 \end{align*}$ verschiedene erreichbare Zustände:

Nur eine von 6 Passwortstellen kann in diesem einen Schritt geändert werden, und dort nur jeweils mit 35 Möglichkeiten - und außerdem gibt es natürlich auch noch die Variante $\begin{align*} X_{n+1}=X_n \end{align*}$ . Augenzwinkern

Augenzwinkern

Es gibt also für die Paare $\begin{align*} (X_n,X_{n+1}) \end{align*}$ summa summarum nur $\begin{align*} 211\cdot 36^6 \end{align*}$ wirklich erreichbare Zustände.

10.11.2014, 22:20

kombina

Auf diesen Beitrag antworten »

danke

wenn ich es korrekt verstanden habe, ist es aber eigentlich gar nicht unbedingt nötig zu wissen, wie viele Möglichkeiten es genau gibt, oder? zumal danach auch gar nicht gefragt ist.

wichtig ist doch eigentlich nur, dass man weiß, dass die zustände (in diesem fall paare) irgendwie gegenseitig erreichbar sind (damit man irreduzibel hat) - und dafür reicht es in diesem fall zu wissen, dass man von einem zustand zum anderen in 18 schritten kommen kann.

(was sonst noch möglich ist, muss man eigentlich nicht wissen um die aufgabe lösen zu können, oder?)

10.11.2014, 22:31

HAL 9000

Auf diesen Beitrag antworten »

Ja, so ist es (eigentlich auch schon in 7 Schritten).

11.11.2014, 11:23

kombina

Auf diesen Beitrag antworten »

Vielen herzlichen Dank für Deine Hilfe!

Gott

Gott

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »