In der Geheimschrift ist das Zufall-Zählen die Technik (erfunden von William F. Friedman) davon, zwei Texte nebeneinander zu stellen und die Zahl von Zeiten aufzuzählen, dass identische Briefe in derselben Position in beiden Texten erscheinen. Diese Zählung, entweder als ein Verhältnis der Summe oder normalisiert, indem sie sich durch das erwartete Zählen für ein zufälliges Quellmodell teilt, ist als der Index des Zufalls bekannt.

Anwendung

Der Index des Zufalls ist sowohl in der Analyse der natürlichen Sprache plaintext als auch in der Analyse von ciphertext (cryptanalysis) nützlich. Selbst wenn nur ciphertext für die Prüfung verfügbar ist und plaintext Brief-Identität verkleidet wird, können Zufälle in ciphertext durch Zufälle im zu Grunde liegenden plaintext verursacht werden. Diese Technik ist an cryptanalyze die Ziffer von Vigenère zum Beispiel gewöhnt. Für einen Wiederholen-Schlüssel wird polyalphabetische Ziffer, die in eine Matrix, die Zufall-Rate innerhalb jeder Säule eingeordnet ist, gewöhnlich am höchsten sein, wenn die Breite der Matrix ein Vielfache der Schlüssellänge ist, und diese Tatsache verwendet werden kann, um die Schlüssellänge zu bestimmen, die der erste Schritt im Knacken des Systems ist.

Das Zufall-Zählen kann helfen zu bestimmen, wenn zwei Texte auf derselben Sprache mit demselben Alphabet geschrieben werden. (Diese Technik ist verwendet worden, um den behaupteten Bibel-Code zu untersuchen). Der kausale Zufall ist solche Texte wert wird ausgesprochen höher sein als das zufällige Zufall-Zählen für Texte auf verschiedenen Sprachen oder Texte mit verschiedenen Alphabeten oder Kauderwelsch-Texten.

Um warum zu sehen, stellen Sie sich ein "Alphabet" nur der zwei Briefe A und B vor. Nehmen Sie an, dass auf unserer "Sprache" der Brief A 75 % der Zeit verwendet wird, und der Brief B 25 % der Zeit verwendet wird. Wenn zwei Texte auf dieser Sprache nebeneinander gelegt werden, dann können die folgenden Paare erwartet werden:

Insgesamt ist die Wahrscheinlichkeit eines "Zufalls" 62.5 % (56.25 % für AA + 6.25 % für BB).

Ziehen Sie jetzt den Fall in Betracht, wenn beide Nachrichten encrypted das Verwenden der einfachen monoalphabetischen Ersatz-Ziffer sind, die durch B und umgekehrt ersetzt:

Die gesamte Wahrscheinlichkeit eines Zufalls in dieser Situation ist 62.5 % (6.25 % für AA + 56.25 % für BB), genau dasselbe bezüglich des unencrypted "plaintext" Fall. Tatsächlich ist das neue durch den Ersatz erzeugte Alphabet gerade eine gleichförmige Umbenennung der ursprünglichen Charakter-Identität, die nicht betrifft, ob sie zusammenpassen.

Nehmen Sie jetzt an, dass nur eine Nachricht (sagen das zweite), encrypted das Verwenden derselben Ersatz-Ziffer (A, B)  (B, A) ist. Die folgenden Paare können jetzt erwartet werden:

Jetzt ist die Wahrscheinlichkeit eines Zufalls nur 37.5 % (18.75 % für AA + 18.75 % für BB). Das ist merklich niedriger als die Wahrscheinlichkeit, als dasselbe sprachig Texte des desselben-Alphabetes verwendet wurden. Zweifellos sind Zufälle wahrscheinlicher, wenn die häufigsten Briefe in jedem Text dasselbe sind.

Derselbe Grundsatz gilt für echte Sprachen wie Englisch, weil bestimmte Briefe, wie E, viel öfter vorkommen als andere Briefe — eine Tatsache, die in der Frequenzanalyse von Ersatz-Ziffern verwendet wird. Zufälle, die den Brief E zum Beispiel einschließen, sind relativ wahrscheinlich. So, wenn irgendwelche zwei englischen Texte verglichen werden, wird die Zufall-Zählung höher sein als, wenn ein englischer Text und ein Text in der Fremdsprache verwendet werden.

Es kann leicht vorgestellt werden, dass diese Wirkung fein sein kann. Zum Beispiel werden ähnliche Sprachen eine höhere Zufall-Zählung haben als unterschiedliche Sprachen. Außerdem ist es nicht hart, zufälligen Text mit einem Frequenzvertrieb zu erzeugen, der dem echten Text ähnlich ist, künstlich die Zufall-Zählung erhebend. Dennoch kann diese Technik effektiv verwendet werden, um sich zu identifizieren, wenn zwei Texte wahrscheinlich bedeutungsvolle Information auf derselben Sprache mit demselben Alphabet enthalten werden, um Perioden zu entdecken, um Schlüssel zu wiederholen, und viele andere Arten von nichtzufälligen Phänomenen innerhalb oder unter ciphertexts aufzudecken.

Dieselbe Idee kann auf einen einzelnen Text angewandt werden, wo die Probe tatsächlich im Vergleich zu sich ist.

Mathematisch können wir den Index des Zufalls IC für einen gegebenen Vertrieb der Brief-Frequenz als schätzen

:

wo die Länge des Textes ist und durch die Frequenzen (als ganze Zahlen) von den Buchstaben vom Alphabet (für Monofall-Englisch) sind. Die Summe, notwendigerweise zu sein.

Die Produkte zählen die Zahl von Kombinationen von Elementen genommen zwei auf einmal auf. (Wirklich zählt das jedes Paar zweimal auf; die Extrafaktoren 2 kommen sowohl im Zähler als auch in Nenner der Formel vor und annullieren so.) Jedes der Ereignisse des-th Briefs vergleicht jedes der restlichen Ereignisse desselben Briefs. Es gibt insgesamt Brief-Paare im kompletten Text, und ist die Wahrscheinlichkeit eines Matchs für jedes Paar, einen gleichförmigen zufälligen Vertrieb der Charaktere annehmend (das "ungültige Modell"; sieh unten). So gibt diese Formel das Verhältnis der Gesamtzahl von zur Gesamtzahl von Zufällen beobachteten Zufällen, dass man vom ungültigen Modell erwarten würde.

Der erwartete durchschnittliche Wert für den I.C. kann von den Verhältnisbrief-Frequenzen der Quellsprache geschätzt werden:

:

Wenn alle Briefe eines Alphabetes ebenso verteilt würden, würde der erwartete Index 1.0 sein.

Der wirkliche monografische I.C. für den telegrafischen englischen Text ist ungefähr 1.73, die Unebenkeit des Brief-Vertriebs der natürlichen Sprache widerspiegelnd. Erwartete Werte für verschiedene Sprachen sind:

Manchmal werden ähnliche Werte ohne den Normalisieren-Nenner zum Beispiel für Englisch berichtet; solche Werte können ("kappa-plaintext") aber nicht "I.C" genannt werden., mit ("kappa-zufälligem") hat gepflegt, den Nenner anzuzeigen (der die erwartete Zufall-Quote für eine Rechteckverteilung desselben Alphabetes, für Englisch ist).

Generalisation

Die obengenannte Beschreibung ist nur eine Einführung in den Gebrauch des Index des Zufalls, der mit dem Gesamtkonzept der Korrelation verbunden ist. Verschiedene Formen des Index des Zufalls sind ausgedacht worden; "Delta" I.C. (gegeben durch die Formel oben) tatsächlich misst die Autokorrelation eines einzelnen Vertriebs, wohingegen ein "kappa" I.C. verwendet wird, wenn man zwei Textschnuren vergleicht. Obwohl in einigen Anwendungen unveränderliche Faktoren solcher als und ignoriert werden können, in allgemeineren Situationen gibt es beträchtlichen Wert in aufrichtig dem Indexieren jedes I.C. gegen den für die ungültige Hypothese zu erwartenden Wert (gewöhnlich: Kein Match und ein gleichförmiger zufälliger Symbol-Vertrieb), so dass in jeder Situation der erwartete Wert für keine Korrelation 1.0 ist. So kann jede Form von I.C. als das Verhältnis der Zahl von Zufällen ausgedrückt werden, die wirklich zur Zahl von Zufällen beobachtet sind, erwartet (gemäß dem ungültigen Modell), mit der besonderen Testeinstellung.

Vom Vorstehenden ist es leicht, dass die Formel für kappa I.C zu sehen.' ist

:

wo die allgemeine ausgerichtete Länge der zwei Texte A und B ist, und der eingeklammerte Begriff als 1 wenn der-th Brief des Textes Matchs der-th Brief des Textes B, sonst 0 definiert wird.

Ein zusammenhängendes Konzept, die "Beule" eines Vertriebs, misst die Diskrepanz zwischen dem beobachteten I.C. und dem ungültigen Wert von 1.0. Die Zahl von in einer polyalphabetischen Ziffer verwendeten Ziffer-Alphabeten kann durch das Teilen der erwarteten Beule Deltas I.C. durch die beobachtete Beule geschätzt werden, obwohl in vielen Fällen (solcher als, als ein sich wiederholender Schlüssel verwendet wurde) bessere Techniken verfügbar sind.

Beispiel

Als eine praktische Illustration des Gebrauches von I.C., nehmen Sie an, dass wir die folgende ciphertext Nachricht abgefangen haben:

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDHXC XJYEB IMTRQ WNMEA

IZRVK CVKVL XNEIC FZPZC ZZHKM LVZVZ IZRRQ WDKEC HOSNY XXLSP

MYKVQ XJTDC IOMEE XDQVS RXLRL KZHOV

</nowiki> </pre>

(Die Gruppierung in fünf Charaktere ist gerade eine telegrafische Tagung und hat nichts, um mit wirklichen Wortlängen zu tun.)

Wenn wir

das verdächtigen, ein englischer plaintext encrypted das Verwenden einer Ziffer von Vigenère mit normalen A-Z Bestandteilen und einem kurzen sich wiederholenden Schlüsselwort zu sein, können wir den ciphertext als "aufgeschobert" in eine Zahl von Säulen, zum Beispiel sieben betrachten:

QPWKALV

RXCQZIK

GRBPFAE

OMFLJMS

DZVDHXC

XJYEBIM

TRQWN …

</nowiki> </pre>

Wenn die Schlüsselgröße zufällig dasselbe als die angenommene Zahl von Säulen gewesen ist, dann werden alle Briefe innerhalb einer Einzelspalte mit demselben Schlüsselbrief, tatsächlich eine einfache auf eine zufällige Auswahl an englischen plaintext Charakteren angewandte Ziffer von Caesar verschlüsselt worden sein. Der entsprechende Satz von ciphertext Briefen sollte eine Rauheit des diesem von Engländern ähnlichen Frequenzvertriebs haben, obwohl die Brief-Identität (ausgewechselt durch einen unveränderlichen Betrag entsprechend dem Schlüsselbrief) permutiert worden ist. Deshalb, wenn wir das gesamte Delta I.C. für alle Säulen schätzen ("Delta-Bar"), sollten es ungefähr 1.73 sein. Andererseits, wenn wir die Schlüsselgröße falsch erraten haben (Zahl von Säulen), sollte das gesamte Delta I.C. ungefähr 1.00 sein. So schätzen wir Delta I.C. für angenommene Schlüsselgrößen von ein bis zehn:

Wir sehen, dass die Schlüsselgröße fünf am wahrscheinlichsten ist. Wenn die wirkliche Größe fünf ist, würden wir annehmen, dass eine Breite zehn auch einen hohen I.C meldet., da jede seiner Säulen auch einem einfachen Caesar encipherment entspricht, und wir das bestätigen.

So sollten wir den ciphertext in fünf Säulen aufschobern:

QPWKA

LVRXC

QZIKG

RBPFA

EOMFL

JMSDZ

VDH …

</nowiki> </pre>

Wir können jetzt versuchen, den wahrscheinlichsten Schlüsselbrief für jede Säule betrachtet getrennt zu bestimmen, indem wir Probe Dekodierung von Caesar der kompletten Säule für jede der 26 Möglichkeiten A-Z für den Schlüsselbrief durchführen, und den Schlüsselbrief wählen, der die höchste Korrelation zwischen den entschlüsselten Säulenbrief-Frequenzen und den Verhältnisbrief-Frequenzen für den normalen englischen Text erzeugt. Diese Korrelation, die wir über das Normalisieren nicht zu beunruhigen brauchen, kann als sogleich geschätzt werden

:

wo die beobachteten Säulenbrief-Frequenzen sind und die Verhältnisbrief-Frequenzen für Englisch sind.

Wenn wir das versuchen, wie man berichtet, sind die be-passenden Schlüsselbriefe,",", den wir als ein wirkliches Wort und das Verwenden anerkennen, das für die Dekodierung von Vigenère den plaintext erzeugt:

MUSTC HANGE MEETI NGLOC ATION FROMB KAMM TOUND ERPAS

SSINC EENEM YAGEN TSARE STELLEN VEDTO HAVEB EENAS SIGNE FALSCH DAR

DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

</nowiki> </pre>

von dem vorherrscht:

MUSS VERSAMMLUNGSPOSITION VON DER BRÜCKE BIS UNTERFÜHRUNG ÄNDERN

DA, WIE MAN GLAUBT, FEINDLICHE REAGENZIEN ZUGETEILT WORDEN SIND

ZUR HALT-TREFFEN-ZEIT DER WATCH BRIDGE UNVERÄNDERT XX

</nowiki> </pre>

nachdem Wortabteilungen an den offensichtlichen Positionen wieder hergestellt worden sind. "" sind "zweifellos ungültige" Charaktere, die verwendet sind, um die Endgruppe für die Übertragung auszupolstern.

Dieses komplette Verfahren konnte in einen automatisierten Algorithmus leicht paketiert werden, um solche Ziffern zu brechen. Wegen der normalen statistischen Schwankung wird solch ein Algorithmus gelegentlich falsche Wahlen besonders machen, wenn er kurze ciphertext Nachrichten analysieren wird.

Siehe auch

Themen in der Geheimschrift