Index of coincidence

V kryptografii , náhoda, počítání je technika (vynalezl William F. Friedman^[ 1 ] ) uvedení dva texty side-by-side a počítání, kolikrát, že identické dopisy se objeví na stejném místě v obou textech. Tento počet, a to buď jako poměr celkové nebo normalizačně vydělením očekávanou počtu pro náhodné zdrojového modelu, je známý jako index náhody .

[ editovat ]Použití

Index náhodou je užitečné jak v analýze přírodních jazyce holého textu a při analýze ciphertext ( kryptoanalýza ). I když jen ciphertext je k dispozici pro testování a dopis holého textu identity jsou skryté, může náhody v ciphertext být způsobeny náhod v podkladové textu. Tato technika se používá kcryptanalyze na Vigenère kód , například. Pro opakování-klíče polyalphabetic kódu uspořádané do matice, bude náhoda rychlost v každém sloupci obvykle nejvyšší, pokud je šířka matice je násobkem délky klíče, a tato skutečnost může být použit k určení, délka klíče, který je Prvním krokem praskání systému.

Náhoda počítání může pomoci určit, kdy jsou dva texty napsány ve stejném jazyce pomocí stejné abecedu . (Tato technika byla použita, aby přezkoumala údajné Bible kód ). Kauzální náhoda počet takových textů bude výrazně vyšší než náhodné koincidenční počet pro texty v různých jazycích, nebo texty s využitím různých abeced, nebo blábol texty.

Chcete-li zjistit, proč, představte si "abecedu" z pouze ze dvou písmen A a B. Předpokládejme, že v našem "jazyk", dopis je používán 75% času, a písmeno B se používá 25% času. Pokud dva texty v tomto jazyce jsou položeny vedle sebe, pak tyto dvojice lze očekávat:

Pár	Pravděpodobnost
AA	56,25%
BB	6,25%
AB	18,75%
BA	18,75%

Nyní uvažujme případ, kdy obě zprávy jsou šifrovány pomocí jednoduchého monoalphabetic substituční šifru, která nahradí s B a naopak:

Pár	Pravděpodobnost
AA	6,25%
BB	56,25%
AB	18,75%
BA	18,75%

Celková pravděpodobnost náhoda v této situaci je 62,5% (6,25% pro AA + 56.25% na BB), přesně stejný jako u nezašifrované "holý" případ. Ve skutečnosti, nová abeceda produkovaný substituce je jen jednotná přejmenováním z původních znaků identit, které nemá vliv, zda se shodují.

Nyní předpokládejme, že pouze jedna zprávy (říci, druhé) jsou kódovány použitím stejného substituční kód (A, B) → (B, A). Následující dvojice může být nyní očekávat:

Pár	Pravděpodobnost
AA	18,75%
BB	18,75%
AB	56,25%
BA	6,25%

Nyní pravděpodobnost náhoda je pouze 37,5% (18,75% pro AA + 18.75% na BB). To je znatelně nižší než pravděpodobnost, kdy byly použity stejné-jazyk, stejný-abecedy texty. Je zřejmé, že náhody jsou pravděpodobnější, pokud nejčastější písmena v každém textu jsou stejné.

Stejná zásada platí pro skutečné jazyků jako je angličtina, protože některá písmena, jako E, se vyskytují mnohem častěji, než jiné dopisy-fakt, který se používá v frekvenční analýzu z substitučních šifer . Coincidences zahrnující písmeno E, například, jsou relativně pravděpodobné. Takže když se porovnávají všechny dva anglické texty, bude náhoda počet bude vyšší, než jsou-li použity anglické znění a cizího jazyka text.

To může být snadno představit, že tento účinek může být jemné. Například, podobné jazyky mají vyšší koincidenční počet než odlišných jazyků. Také, to není těžké vytvořit náhodný text s frekvenčním distribuce podobné skutečnému textu, uměle zvýšit koincidenční počet. Nicméně, tato technika může být efektivně využity k identifikaci, když se dva texty budou pravděpodobně obsahovat smysluplné informace ve stejném jazyce pomocí stejnou abecedu, objevovat období pro opakování kláves, a odhalit mnoho dalších druhů nenáhodné jevů v rámci nebo mezi ciphertexts.

Stejný nápad může být použita na jediném textu, kde vzorek je ve skutečnosti v porovnání s sobě . Matematicky můžeme spočítat index náhoda IC pro daný dopis-frekvenční distribuci jako

kde $N$ je délka textu a $n_1$ prostřednictvím $n_c$ jsou frekvence (jako celá čísla) o $C$ písmena abecedy ( $c = 26$ pro monocase angličtině ). Součet $n_i$ je nutně $N$ .

Tyto výrobky $n (n-1)$ počítat množství kombinací z $n$ prvků o dva najednou.(Ve skutečnosti tento počítá každý pár dvakrát, že další faktory 2 se vyskytují v obou čitatele a vzorce, a tím se ruší.) Každý z $n_i$ výskytů $já$ -tého písmene odpovídá každá ze zbývajících $n_i -1$ výskytů stejným písmenem. Existuje celkem $N (N-1)$ páry písmen v celém textu, a $1 / c$ je pravděpodobnost partner pro každou dvojici, za předpokladu, že jednotný náhodný rozdělení znaků ("null model", viz níže). Tak, tato rovnice udává poměr celkového počtu shodujících pozorovaných na celkovém počtu shodujících že by se očekávalo od nulové modelu. ^[ 2 ]

Očekává průměrná hodnota pro IC mohou být počítány z relativních písmeny frekvencí $f_i$ na zdrojovém jazyce:

Pokud jsou všechny $C$ dopisy abecedy byly rovnoměrně rozděleny, by očekávaný index 1,0. Skutečný monografická IC pro telegrafické anglického textu je asi 1,73, což odráží nerovnosti přirozené jazykové dopisu distribucí.Očekávané hodnoty pro různé jazyky ^[ 3 ] jsou:

Jazyk	Index shody okolností
Angličtina	1.73
Francouzština	2.02
Němec	2.05
Italština	1.94
Portugalština	1.94
Rus	1.76
Španělština	1.94

Někdy podobné hodnoty jsou uvedeny bez Normalizační jmenovateli, např. $0.067 = 1.73/26$ pro anglicky; tyto hodnoty mohou být navštíveny $\ Kappa_p$ ("kappa-plaintext"), spíše než "IC", s $\ Kappa_r$ ("kappa-random") používá k označení jmenovatele $1 / c$ (což je Očekává náhoda sazba pro rovnoměrné rozložení stejné abecedy, $0.0385 = 1/26$ pro angličtinu).

[ editovat ]Generalizace

Výše uvedený popis je pouze úvodem do používání indexu koincidence, která se vztahuje k obecnému pojmu korelace . Různé formy indexu shody okolností byly vytvořeny, "delta" IC (podle vzorce výše) v podstatě měří autokorelačníjednoho distribuce, zatímco "kappa" IC se používá při spojení dvou textových řetězců. ^[ 4 ] Ačkoli v některých faktorech aplikace stálých jako $C$ a $N$ mohou být ignorovány, v obecnějším situacích existuje značná hodnota skutečněindexování každý IC proti hodnoty, která se očekává na nulové hypotézy(obvykle: žádná shoda a rovnoměrné náhodné symbol distribuce), tak, že v každé situaci očekávaná hodnota je 1,0 pro žádný korelace. Tak může být každý forma IC vyjádřit jako poměr počtu shodujících skutečně pozorovaných na počtu shodujících očekává (v závislosti na nulové modelu), za použití konkrétního nastavení testu.

kde $N$ je společný souladu délka obou textů a B , a bracketed termín je definován jako 1, pokud -th dopis textu odpovídá -tého dopis textu B , jinak 0. $j$ $j$

Příbuzné pojetí, "boule" z distribuce, měří rozdíl mezi pozorovanou IC a nulové hodnoty 1,0. Počet kódové abeced používaných v polyalphabetic kódu může být odhadnuta vydělením očekávaný výběžku delta IC pozorovanou vyboulení, i když v mnoha případech (například při opakování klíč byl použit) lepší techniky jsou k dispozici.

[ editovat ]Příklad

Jako praktickou ukázku používání IC, předpokládám, že jsme zachytili následující šifrový zpráva:

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

(Seskupení do pěti postav je jen telegrafické konvence a nemá nic společného se skutečnými slovo délky.) podezření, že se jedná o anglický plaintext šifrované pomocí Vigenère kód s běžnými A-Z komponentů a krátké opakující klíčovým slovům, můžeme zvážit ciphertext "naskládané" do nějakého počtu sloupců, například sedm:

QPWKALV
RXCQZIK
GRBPFAE
OMFLJMS
DZVDHXC
XJYEBIM
TRQWN ...

Pokud je klíč velikost se stane byly stejné jako předpokládaný počet sloupců, pak všechny dopisy v rámci jednoho sloupce bude muset být zašifrován používat stejný klíč dopis, ve skutečnosti jednoduché Caesarova šifra použije na náhodném výběru anglických znaků prostého textu . Odpovídající soubory písmen šifrového by měl mít drsnost rozdělení četností podobném tomu angličtiny, ačkoli písmeno totožnost byla deionizovaná (posunuty o konstantní výši odpovídající klíče písmeno). Proto, když počítáme celkovou delta IC pro všechny sloupce ("delta bar"), mělo by to být kolem 1,73. Na druhé straně, pokud se již nesprávně odhadl velikost klíče (počet sloupců), měl by být souhrnný delta IC být kolem 1,00. Takže počítáme delta IC pro převzatých klíčové velikosti jedna-deset:

Velikost	Delta-bar IC
1	1.12
2	1.19
3	1.05
4	1.17
5	1.82
6	0.99
7	1.00
8	1.05
9	1.16
10	2.07

Je vidět, že velikost klíče je pravděpodobně pět. Pokud skutečná velikost je pět, bychom očekávali, že šířku deseti také nahlásit vysoké IC, protože každý z jeho sloupců odpovídá i jednoduché zašifrování Caesar, a my to potvrzují.Takže bychom měli skládat ciphertext do pěti sloupců:

QPWKA
LVRXC
QZIKG
RBPFA
EOMFL
JMSDZ
VDH ...

Nyní můžeme pokusit určit nejpravděpodobnější klíč dopis pro každý sloupec posuzovaného zvlášť, provedením zkušební Caesar dešifrování celého sloupce pro každý z 26 možností-Z pro klíčové dopisu, a výběr klíčové dopis, který produkuje nejvyšší korelaci mezi dešifrovaných frekvencí sloupců písmen a relativní dopis frekvencí pro normální anglického textu. To korelace, které nemáme potřebu se starat o normalizaci, lze snadno vypočítat jako

kde $n_i$ jsou pozorované frekvence sloupců písmeno a $f_i$ jsou relativní dopis kmitočty pro češtině. Když jsme zkusit, jsou ustavovací klíčové dopisy ohlásen být " KAŽDÝ , "které považujeme za skutečné slovo, a pomocí tohoto pro dešifrování Vigenère produkuje holý:

MUSTC HANGE MEETI NGLOC ACE FROMB RIDGE TOUND ERPAS 
SSINC EENEM YAGEN TSARE popírá VEDTO HAVEB EENAS Signe 
DTOWA TCHBR IDGES TOPME eting TIMEU NCHAN GEDXX

Se musí změnit umístění setkání z mostu k podchodu
OD nepřátelské agenty jsou považovány za byly přiřazeny
DÁVAT BRIDGE STOP času schůzky beze změny XX

po divize slova byly obnoveny v zřejmých místech. " XX "jsou evidentně" null "znaky používané pro podložku z finálové skupině pro přenos.

Celý tento postup by mohl být snadno balí do automatizovaného algoritmu pro porušení těchto šifer. Vzhledem k běžné statistické fluktuace, bude takový algoritmus občas dělají špatná rozhodnutí, a to zejména při analýze krátké šifrový text zprávy.