Wie hoch ist die Wahrscheinlichkeit, dass eine Zeichenfolge eine andere Zeichenfolge enthält?

19.01.2013, 18:45

Maxov

Wie hoch ist die Wahrscheinlichkeit, dass eine Zeichenfolge eine andere Zeichenfolge enthält?

Meine Frage:
Hallo,

Ein SHA-256 Hash ist 64 Zeichen lang, jedes Zeichen kann dabei einen von 16 Werten annehmen (0-9, a-z). Hier ist ein Beispiel: fffbdf15af1b58fc48d5562b3e12a2bb9ea91e78324f3909723bf048396773dc

Ich würde nun gerne berechnen können, mit welcher Wahrscheinlichkeit eine zufällige Hex-Zeichenfolge mit der Länge n in einem zufälligen SHA-256 Hash vorkommt.

Ein Beispiel: Was wäre die Wahrscheinlichkeit, dass eine zufällige Zeichenkette mit der Länge n=3 (z.B. 'c62') in einem SHA-256 Hash vorkommt?

Meine Ideen:
Als Anhaltspunkt hab ich für n=3 in Open Office tausende von Werten erstellt und ausgewertet, dabei komme ich auf ca. 1,5% Wahrscheinlichkeit. Leider weiss ich nicht, wie ich die Wahrscheinlichkeiten exakt berechnen kann. Für Hilfe und Tipps bin ich dankbar!

19.01.2013, 19:21

Kasen75

Auf diesen Beitrag antworten »

Hallo,

erstmal eine Frage: Kann denn ein einzelnes Zeichen 16 oder 36 Werte annehmen?

Grüße.

19.01.2013, 19:57

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Kasen75
erstmal eine Frage: Kann denn ein einzelnes Zeichen 16 oder 36 Werte annehmen?

16 Werte. (gemeint sind die Buchstaben von a-f, nicht a-z)

19.01.2013, 21:46

Kasen75

Auf diesen Beitrag antworten »

@Math1986

AH, OK. Danke für den Hinweis. smile

@Maxov

$\begin{eqnarray*} 1. \end{eqnarray*}$
Erstmal sollte man die Anzahl der möglichen Ereignisse bestimmen. Wenn jedes einzelne Zeichen 1 von 16 Werten annehmen kann, wieviele Variationen gibt es, wenn es 64 Zeichen gibt?

$\begin{eqnarray*} 2. \end{eqnarray*}$
günstige Ereignisse:

x = Zeichen mit irgendeiner Ausprägung aus den 16 möglichen Werten.

Allgemein ist folgende Variation vorstellbar:

$\begin{eqnarray*} \underbrace{c62}_{1-3}...xxx...\underbrace{xxx}_{62-64} \end{eqnarray*}$

$\begin{eqnarray*} a) \end{eqnarray*}$ Die ersten drei Stellen sind festgelegt. Somit bleiben noch 61(=64-3) Stellen, bei denen ein beliebiges Zeichen stehen kann. Die Anzahl Ereignisse dieser Variation wird dann berechnet wie bei der Anzahl möglicher Ereignisse. Aber eben mit 61 Stellen statt mit 64.

$\begin{eqnarray*} b) \end{eqnarray*}$ Jetzt ist es aber so, dass "c26" auch an anderen Stellen stehen kann, z.B. an den Stellen 2,3,4 oder 3,4,5. Wenn man die festgelegte Zeichenfolge immer um eine Stelle verschiebt, dann landet man am Ende bei den Stellen 62,63 und 64. Man hat also 62 Möglichkeiten die feste Zeichenfolge "c62" innerhalb der 64 Stellen anzuordnen.
Also muss das Ergebnis aus a) noch mit 62 multiplizieren und man hat die Anzahl der günstigen Ereignisse.

Wenn man jetzt das Ergebnis aus 2. durch das Ergebnis aus 1. teilt, dann hat man die Wahrscheinlichkeit, dass die Ziffernfolge "c26" vorkommt.

Das Ergebnis deiner Simulation entspricht dem, was bei dieser Rechnung herauskommt.

Grüße.

20.01.2013, 00:03

Maxov

Auf diesen Beitrag antworten »

Zitat:

Original von Math1986

Zitat:

Original von Kasen75
erstmal eine Frage: Kann denn ein einzelnes Zeichen 16 oder 36 Werte annehmen?

16 Werte. (gemeint sind die Buchstaben von a-f, nicht a-z)

Sorry, das habe ich im ursprünglichen Beitrag falsch ausgeführt. Danke für die Klarstellung.

20.01.2013, 00:20

Maxov

Auf diesen Beitrag antworten »

@Kasen75 Super, danke. Das bringt mich schon mal ein Stück weiter.

Ich hab versucht, das mal in eine allgemeine Formel zu bringen, die sieht momentan so aus:

$\begin{eqnarray*} \frac{16^{64-n} *(64-(n-1))}{16^{64} } \end{eqnarray*}$

Das passt bei Werten von 3 oder 4 sehr gut mit meinen numerischen Test in OpenOffice zusammen. Wenn ich aber n=1 nehme, dann kommt 4 heraus.
Das kann natürlich so nicht stimmen.

Wo liegt da der Fehler?

20.01.2013, 09:00

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Kasen75
Also muss das Ergebnis aus a) noch mit 62 multiplizieren und man hat die Anzahl der günstigen Ereignisse.

Es ist zunächst eine Vereinigung dieser 62 Ereignisse. Die Wahrscheinlichkeit davon wäre das 62-fache der Wahrscheinlichkeit eines dieser Ereignisse, falls diese 62 Ereignisse disjunkt wären ... sind sie aber nicht. Sie sind aber unabhängig voneinander, sofern sie weit genug (mindestens 3 Positionen) voneinander entfernt sind. Sind sie aber "nah" benachbart (zwei oder weniger Positionen), dann gilt auch die Unabhängigkeit nicht.

Eine genaue Berechnung der Wahrscheinlichkeit ist damit ziemlicher Horror, allerdings ist mit angenommener näherungsweise gültiger Unabhängigkeit eine gute Schätzung der Wahrscheinlichkeit möglich, jedenfalls eine wesentlich genauere als mit angenommener Disjunktheit: Denn die ergibt mit $\begin{eqnarray*} m \end{eqnarray*}$ statt 64 Positionen für größere $\begin{eqnarray*} m \end{eqnarray*}$ irgendwann Wahrscheinlichkeiten größer als 1. Genau das hat Maxov im Fall n=1 beobachtet. Augenzwinkern

20.01.2013, 09:10

Kasen75

Auf diesen Beitrag antworten »

Die enthaltene Zeichenkeitte darf keine vollkommen identischen Elemente enthalten. So muss man z.B. für die enthaltene Zeichenkette 222 anders herangehen. Das gleiche gilt auch, wenn die enthaltene Zeichenkette nur eine Stelle hat. Hier ist es es klar, dass diese Zeichenkette immer identische "Zeichen" hat.

Wenn die enthaltene Zeichenketten aber nicht identisch sind dann klappt es (meiner Meinung nach). Hier mal ein Beispiel:

Code mit 5 Stellen und den möglichen Zeichen 1 und 2. Es soll die Zeichenkette 121 enthalten sein. Die Variationen sind:

$\begin{eqnarray*} |\textcolor{red}{1|2|1}|1|1| \end{eqnarray*}$
$\begin{eqnarray*} |\textcolor{red}{1|2|1}|1|2| \end{eqnarray*}$
$\begin{eqnarray*} |\textcolor{red}{1|2|1}|2|1| \end{eqnarray*}$
$\begin{eqnarray*} |\textcolor{red}{1|2|1}|2|2| \end{eqnarray*}$
$\begin{eqnarray*} |1|\textcolor{red}{1|2|1}|1| \end{eqnarray*}$
$\begin{eqnarray*} |1|\textcolor{red}{1|2|1}|2| \end{eqnarray*}$
$\begin{eqnarray*} |2|\textcolor{red}{1|2|1}|1| \end{eqnarray*}$
$\begin{eqnarray*} |2|\textcolor{red}{1|2|1}|2| \end{eqnarray*}$
$\begin{eqnarray*} |1|1|\textcolor{red}{1|2|1}| \end{eqnarray*}$
$\begin{eqnarray*} |1|2|\textcolor{red}{1|2|1}| \end{eqnarray*}$
$\begin{eqnarray*} |2|1|\textcolor{red}{1|2|1}| \end{eqnarray*}$
$\begin{eqnarray*} |2|2|\textcolor{red}{1|2|1}| \end{eqnarray*}$

Setzt man dies in deine Formel ein ergibt sich für den Zähler:

$\begin{eqnarray*} 2^{5-3} *(5-(3-1))=2^2 \cdot 3=12 \end{eqnarray*}$

Grüße.

20.01.2013, 10:14

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Kasen75
$\begin{eqnarray*} |\textcolor{red}{1|2|1}|1|1| \end{eqnarray*}$
$\begin{eqnarray*} |\textcolor{red}{1|2|1}|1|2| \end{eqnarray*}$
$\begin{eqnarray*} |\textcolor{red}{1|2|1}|2|1|\qquad (*) \end{eqnarray*}$
$\begin{eqnarray*} |\textcolor{red}{1|2|1}|2|2| \end{eqnarray*}$
$\begin{eqnarray*} |1|\textcolor{red}{1|2|1}|1| \end{eqnarray*}$
$\begin{eqnarray*} |1|\textcolor{red}{1|2|1}|2| \end{eqnarray*}$
$\begin{eqnarray*} |2|\textcolor{red}{1|2|1}|1| \end{eqnarray*}$
$\begin{eqnarray*} |2|\textcolor{red}{1|2|1}|2| \end{eqnarray*}$
$\begin{eqnarray*} |1|1|\textcolor{red}{1|2|1}| \end{eqnarray*}$
$\begin{eqnarray*} |1|2|\textcolor{red}{1|2|1}|\qquad (*) \end{eqnarray*}$
$\begin{eqnarray*} |2|1|\textcolor{red}{1|2|1}| \end{eqnarray*}$
$\begin{eqnarray*} |2|2|\textcolor{red}{1|2|1}| \end{eqnarray*}$

Und (*) hast du falscherweise doppelt gezählt. unglücklich

--------------------------------------------------------------------------------

Mit der "näherungsweisen Unabhängigkeit" bekommt man bei $\begin{eqnarray*} z \end{eqnarray*}$ möglichen Ziffern für das Auftreten eines bestimmten Codes der Länge $\begin{eqnarray*} n \end{eqnarray*}$ in einem Gesamtcode der Länge $\begin{eqnarray*} m \end{eqnarray*}$ die Wahrscheinlichkeit

$\begin{eqnarray*} p \approx 1-\left(1-\frac{1}{z^n} \right)^{m-n+1}\qquad (1) \end{eqnarray*}$

in deinem Fall mit $\begin{eqnarray*} z=16,m=64 \end{eqnarray*}$ also

$\begin{eqnarray*} p \approx 1-\left(1-\frac{1}{16^n} \right)^{65-n} \end{eqnarray*}$ ,

was für $\begin{eqnarray*} n=3 \end{eqnarray*}$ dann $\begin{eqnarray*} p\approx 0.015 \end{eqnarray*}$ bedeutet. Mit der obigen Formel

$\begin{eqnarray*} p \approx \frac{m-n+1}{z^n} \qquad (2) \end{eqnarray*}$

kommt gerundet dasselbe heraus. Beides sind in der Tat Näherungsformeln für diese Wahrscheinlichkeit, man muss sich eben Gedanken machen, für welche $\begin{eqnarray*} m,n,z \end{eqnarray*}$ die getroffenen Approximationsannahmen das Ergebnis noch akzeptabel machen:

(1) basiert auf Unabhängigkeit, ist also desto besser, je kleiner die Überlappungen sind. Im Klartext: (1) ist exakt im Fall $\begin{eqnarray*} n=1 \end{eqnarray*}$ (siehe Beispiel von Maxov), wird dann aber mit größerem $\begin{eqnarray*} n \end{eqnarray*}$ immer schlechter. Wir benötigen daher $\begin{eqnarray*} n\ll m \end{eqnarray*}$ für die Anwendbarkeit von (1).

(2) basiert auf der Disjunktheit von Codes, d.h., das gesuchte Codestück sollte möglichst nicht mehrfach an verschiedenen Positionen im selben Code enthalten sein. Das setzt vergleichsweise große Codestücke sowie die "unregelmäßige Struktur" dieser Codestücke voraus. Wenn also letzteres erfüllt ist und außerdem $\begin{eqnarray*} m-n \ll m \end{eqnarray*}$ gilt, dann ist (2) durchaus praktikabel. Wie das Beispiel von Maxov oben zeigt, kann diese Formel in anderen Konstellationen aber total "ausbrechen" und Werte größer als 1 liefern.

P.S.: Eine exakte Formel für $\begin{eqnarray*} n>1 \end{eqnarray*}$ zu entwickeln, ist wie gesagt ein ziemlicher Horror, zumal sie nicht nur von $\begin{eqnarray*} m,n,z \end{eqnarray*}$ sondern auch der Struktur des Codestückes abhängt. Für $\begin{eqnarray*} n=2 \end{eqnarray*}$ kriegt man das vermutlich noch in den Griff, mit Unterscheidung der beiden Fälle "Codestück besteht aus zwei gleichen / zwei unterschiedlichen Zeichen", bei $\begin{eqnarray*} n=3 \end{eqnarray*}$ dürften bereits die ersten grauen Haare anfallen. Augenzwinkern

20.01.2013, 11:10

Kasen75

Auf diesen Beitrag antworten »

Tatsächlich. Ups

Dann würde ich sagen, dass in der gewünschten Zeichenkette keine Zeichen mehrfach vorkommen dürfen.

Wieder ein Beispiel:

Code mit 5 Stellen und den möglichen Zeichen 1,2 und 3. Es soll die Zeichenkette 132 enthalten sein. Die Variationen sind:

$\begin{eqnarray*} \textcolor{red}{|1|3|2|}1|1| \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{|1|3|2|}1|2| \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{|1|3|2|}1|3| \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{|1|3|2|}2|1| \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{|1|3|2|}2|2| \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{|1|3|2|}2|3| \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{|1|3|2|}3|1| \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{|1|3|2|}3|2| \end{eqnarray*}$
$\begin{eqnarray*} \textcolor{red}{|1|3|2|}3|2| \end{eqnarray*}$
$\begin{eqnarray*} |1\textcolor{red}{|1|3|2|}1| \end{eqnarray*}$
$\begin{eqnarray*} |1\textcolor{red}{|1|3|2|}2| \end{eqnarray*}$
$\begin{eqnarray*} |1\textcolor{red}{|1|3|2|}3| \end{eqnarray*}$
$\begin{eqnarray*} |2\textcolor{red}{|1|3|2|}1| \end{eqnarray*}$
$\begin{eqnarray*} |2\textcolor{red}{|1|3|2|}2| \end{eqnarray*}$
$\begin{eqnarray*} |2\textcolor{red}{|1|3|2|}3| \end{eqnarray*}$
$\begin{eqnarray*} |3\textcolor{red}{|1|3|2|}1| \end{eqnarray*}$
$\begin{eqnarray*} |3\textcolor{red}{|1|3|2|}2| \end{eqnarray*}$
$\begin{eqnarray*} |3\textcolor{red}{|1|3|2|}3| \end{eqnarray*}$
$\begin{eqnarray*} |1|1\textcolor{red}{|1|3|2}| \end{eqnarray*}$
$\begin{eqnarray*} |1|2\textcolor{red}{|1|3|2}| \end{eqnarray*}$
$\begin{eqnarray*} |1|3\textcolor{red}{|1|3|2}| \end{eqnarray*}$
$\begin{eqnarray*} |2|1\textcolor{red}{|1|3|2}| \end{eqnarray*}$
$\begin{eqnarray*} |2|2\textcolor{red}{|1|3|2}| \end{eqnarray*}$
$\begin{eqnarray*} |2|3\textcolor{red}{|1|3|2}| \end{eqnarray*}$
$\begin{eqnarray*} |3|1\textcolor{red}{|1|3|2}| \end{eqnarray*}$
$\begin{eqnarray*} |3|2\textcolor{red}{|1|3|2}| \end{eqnarray*}$
$\begin{eqnarray*} |3|3\textcolor{red}{|1|3|2}| \end{eqnarray*}$

Jetzt sollte keine Variation mehr doppelt sein.

Setzt man die Werte in die Formel ein, ergibt sich: $\begin{eqnarray*} 3^{5-3} \cdot [5-(3-1)]=27 \end{eqnarray*}$

20.01.2013, 11:22

HAL 9000

Auf diesen Beitrag antworten »

Im Fall $\begin{eqnarray*} 2n>m \end{eqnarray*}$ und Codestücken aus sämtlich verschiedenen Zeichen hast du Recht. Im Fall $\begin{eqnarray*} 2n\leq m \end{eqnarray*}$ kannst du aber mehrfaches Zählen gar nicht verhindern, mit keinem Codestück. Augenzwinkern

----------------------------

Ok, hier mal die exakte Formel für Codestücke, wo keine Überlappungen möglich sind (d.h. im Fall $\begin{eqnarray*} n=3 \end{eqnarray*}$ entweder abc, aab oder abb mit paarweise verschiedenen a,b,c):

$\begin{eqnarray*} p = \sum_{k=1}^{\left\lfloor \frac{m}{n} \right\rfloor} (-1)^{k-1} \binom{m-(n-1)k}{k} \frac{1}{z^{nk}} \end{eqnarray*}$

Das ergibt im Fall $\begin{eqnarray*} m=64,n=3,z=16 \end{eqnarray*}$ den Wert

$\begin{eqnarray*} p = \sum_{k=1}^{21} (-1)^{k-1} \binom{64-2k}{k} \frac{1}{2^{12k}} \approx 0.015032 \end{eqnarray*}$

Nochmal zum Vergleich: Mit Näherungsformel (1) kam auf sechs Nachkommastellen gerundet $\begin{eqnarray*} 0.015025 \end{eqnarray*}$ heraus, mit (2) dann $\begin{eqnarray*} 0.015137 \end{eqnarray*}$ , d.h. (1) ist für diese Konstellation etwas besser als (2).

20.01.2013, 13:01

Maxov

Auf diesen Beitrag antworten »

@HAL 9000 Danke für deine Ausführungen!

Formel (1) liefert die Ergebnisse, die ich brauche. Für n=1 erhalte ich laut Formel ~98,39%, mein OpenOffice-Test ergibt ~98,45%. Das passt also recht gut zusammen.

Neue Frage »

Antworten »

Wie hoch ist die Wahrscheinlichkeit, dass eine Zeichenfolge eine andere Zeichenfolge enthält?

Verwandte Themen