Egybeesés-számlálás

A Wikipédiából, a szabad enciklopédiából

A kriptográfiában az egybeesések számlálásának módszerével, amelyet William F. Friedman talált fel, két különböző szöveget egymás mellé téve meg kell számolni, hogy egy adott betű hányszor szerepel a két szövegben ugyanabban a pozícióban. A kapott számnak az összeshez való arányát nevezzük az egybeesés mértékének. Ezt a módszert használják például a Vigenère-rejtjel megfejtésére.

Az egybeesések számlásásával meghatározhtajuk, hogy két szöveg ugyanazon a nyelven, ugyanazon ábécé használatával íródott-e. Ezen szövegek közt az egybeesés jóval nagyobb lesz, mint két különböző nyelven írott vagy különböző ábécével kódolt szöveg között, vagy ha az egyik szöveg értelmetlen. Ezzel a technikával vizsgálták a közelmúltban megismert Biblia-kódot.

A módszer megértéséhez tekintsük a csak A és B betűkből álló "ábécét". Tegyük fel, hogy a "nyelvünkben" 75%-ban A betűt, 25%-ban B betűt használunk. Ha két ilyen nyelven írott szöveget egymás mellé helyezünk, a következő párokra számíthatunk:

Pár Valószínűség
AA 56.25%
BB 6.25%
AB 18.75%
BA 18.75%

Összességében tehát az egybeesésnek a valószínűsége 62.5% (56.25% az AA esélye + 6.25% a BB esélye).

Most tegyük fel azt, hogy két másik szöveget helyezünk egymás mellé: az egyik ezen a nyelven íródott, a másik pedig egy helyettesítő rejtjellel kódolt, amely az A-t B-vel, a B-t pedig A-val helyettesíti. Ezúttal az alábbi párokat várhatjuk:

Pár Valószínűség
AA 18.75%
BB 18.75%
AB 56.25%
BA 6.25%

Az egybeesés valószínűsége tehát 37.5% (18.75% mind az AA-ra, mind a BB-re). Ez láthatóan alacsonyabb, mint amit az azonos nyelvű, azonos ábécével kódolt szövegeknél tapasztaltunk. Valójában azért voltak valószínűbbek az egybeesések, mert mindkét szövegben ugyanazok voltak a leggyakoribb betűk, tehát annak az esélye, hogy azok egymás mellett megjelennek, maximális volt.

Ugyanez az elv érvényesül a valódi nyelvekre, így a magyarra és az angolra is. Bizonyos betűk, mint például az E, sokkal gyakrabban fordul elő, mint mások (ezen a tényen alapszik a helyettesítő rejtjelek gyakoriságelemzése is). Az E betűk egybeesése ebből adódóan elég valószínű. Tehát amikor két magyar nyelvű szöveget összevetünk egymással, az egybeesés mértéke magasabb lesz, mint amikor egy másik nyelvű szöveggel hasonlítjuk össze.

Könnyen elgondolható, hogy ez az eltérés igen finom is lehet. Például hasonló nyelvek egybeesésének mértéke nagyobb lesz, mint az eltérőeké. Sőt, nem nehéz olyan szövegutánzatot létrehozni, amelyben mesterségesen megnöveljük az egybeesés mértéke egy adott nyelvvel.

Az angol nyelv egybeesési mértéke 6.6% körül, a német nyelvé 7.6% körül van. Ha egy ábécének mind az n betűje pontosan ugyanolyan gyakori lenne, akkor a mérték 1/n lenne. A mértéket az angol index szó után I-vel jelölve, felírhatjuk rá az alábbi képletet:

\mathbf{I} = \sum_{i=1}^{n}\frac{n_i(n_i -1)}{n(n-1)}

ahol n a szöveg hosszát, az ábécé egyes betűinek betűgyakoriságát angol nyelv esetén  n_1 ,…, n_{26} , magyar nyelv esetén  n_1 ,…, n_{40} jelöli.