Match Index

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2013. március 31-én felülvizsgált verziótól ; az ellenőrzések 28 szerkesztést igényelnek .

A koincidencia index a Vigenère-rejtjel kriptoanalízisének egyik módszere . A leírást William Friedman tette közzé 1920-ban.

A módszer azon a valószínűségen alapul, hogy két véletlenszerű szövegelem egyezik. Ezt a valószínűséget koincidencia indexnek nevezzük. William Friedman kimutatta, hogy az egybeesési index értékei jelentősen eltérnek a különböző jellegű szövegeknél. Ez lehetővé teszi, hogy először meghatározza a rejtjelkulcs hosszát, majd magát a kulcsot keresse meg.

A koincidencia-index módszerének megjelenése új lehetőségeket nyitott meg a Vigenère-rejtjel kriptoanalízisében. Az akkoriban elterjedt Kasiska-módszerhez képest az új módszer kevésbé volt munkaigényes, kevesebb szöveget igényelt, jobban automatizálható volt, és kevésbé volt hibás. Az egyezési index hatékonyabb volt, és lehetővé tette a hosszú kulcsú rejtjelek elemzését.

Történelem

Blaise Vigenère egy egyszerű, de erős rejtjel leírását mutatta be III. Henrik francia megbízatása előtt, 1586-ban, és később neki tulajdonították a rejtjel feltalálását. A Vigenère-rejtjel rendkívül ellenálló volt a „kézi” repedésekkel szemben. Az első sikeres támadást a Vigenère-rejtjel ellen Friedrich Kasiski hajtotta végre 1863-ban. Az ő módszere maradt a Vigenère-rejtjel kriptoanalízisének fő módszere egészen 1920-ig, amikor William Friedman megjelentette az Index of Coincidence and Its Applications in Cryptography című monográfiát . A Friedman által leírt új módszer hatékonyabb és hibatűrőbb módszert kínált a kulcshossz meghatározására. A koincidencia index módszerét széles körben alkalmazzák. Később a géppel segített kriptoanalízisben használták.

Kriptanalízis módszer a Vigenère-rejtjelhez

A Vigenère-rejtjel egy többalfabetikus titkosítás . A kriptoanalízise 2 lépésre bontható:

Először is megpróbálják meghatározni a kulcs hosszát. A kulcs hossza határozza meg a használt ábécék számát és az ábécék általi titkosítás időtartamát. Ezért ebben a szakaszban a rejtjelezett szöveg periodicitását vizsgáljuk;
A hossz megtalálása után elkezdenek keresni egy adott típusú kulcs után. Ehhez kiszámítják a használt ábécék relatív eltolódásait, majd nyers erővel kiválasztják a kulcsot.

Match index

Az alábbiakban a találati index kiszámításának képleteit találjuk. Először az általános esetet vizsgáljuk meg. Ezután több olyan speciális esetet veszünk figyelembe, amikor az egybeesési index szövegelemzés nélkül is becsülhető.

Általános eset

Vegyünk egy szöveget valamilyen nyelven. Egy adott nyelv ábécéje szimbólumokból áll. Vegyünk egy kellően hosszú karaktersorozatot . Az egyezési index annak a valószínűsége, hogy egy karakterláncban két tetszőleges karakter egyezik. Ha az ábécé -edik karakterének a száma a karakterláncban , akkor az egyezési indexet a következő képlettel számítjuk ki: $m$ ${\vec x}$ $n$ $f_{i}$ $én$ ${\vec x}$

I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}{\frac {f_{i}\left({f_{i}-1 }\jobbra)}{n\balra({n-1}\jobbra)}}

(egy)

Bizonyíték

A valószínűséget a kedvező kimenetelek (egy karakterláncban lévő azonos karakterpárok száma) és az összes kimenetel (egy karakterláncban lévő különböző karakterpárok száma) arányaként becsüljük meg.

A karakterlánc th karakterének különböző párjainak száma a következő: ${\displaystyle {\displaystyle i))$

${\displaystyle k_{i}=C_{f_{i}}^{2}={\frac {f_{i}\left({f_{i}-1}\right)}{2}} }$

Azonos karakterpárok száma egy karakterláncban:

${\displaystyle k=\sum _{i=1}^{m}k_{i}=\sum _{i=1}^{m}{\frac {f_{i}\left({f_ {i}-1}\jobbra)}{2}}}$

Különböző karakterpárok száma egy karakterláncban:

${\displaystyle {\displaystyle K=C_{n}^{2}={\frac {n\left({n-1}\right)}{2))))$

Innen kapjuk:

${\displaystyle I\left({\vec {x}}\right)={\frac {k}{K}}=\sum \limits _{i=1}^{m}{\frac { f_{i}\left({f_{i}-1}\right)}{n\left({n-1}\right)}}}$

Egyszerű szöveg

Tegyük fel, hogy a karakterlánc egyszerű szöveg, vagy egyszerű permutációval nyerhető belőle . Ebben az esetben az egybeesések indexét kényelmesen a -edik szimbólum előfordulási valószínűségével fejezzük ki . Jelöljük ki őket . Ekkor a következő képletet kapjuk: ${\vec {x}}$ $én$ $p_{i}$

I\left({\vec {x}}\right)=\sum \limits _{i=1}^{m}p_{i}^{2}

(2)

Mert az értékek jól meghatározott értékekkel rendelkeznek, akkor egyszerű szöveg esetén az egybeesések indexe nem a tartalmától, hanem csak attól függ, hogy a szöveg milyen nyelven íródott. Sőt, az értékeket kutatják és ismerik, ami lehetővé teszi az egyszerű szöveges egyezési index értékeinek kiszámítását különböző nyelvekre. $p_{i}$ $p_{i}$

Nyelv	Match Index
orosz	0,0553 [1]
angol	0,0644 [1] 0,0667 [2]
olasz	0,0738 [2]
spanyol	0,0775 [2]
Deutsch	0,0762 [2]
Francia	0,0778 [2]
védikus szanszkrit	0,021076696
prakrit	0,046635758
Klasszikus szanszkrit	0,045567736
hindi	0,041837864
urdu	0,057535302

Véletlenszerű karakterlánc

Végül legyen egy véletlenszerű karakterlánc. Ekkor minden szimbólum előfordulási valószínűsége egyenlő ${\vec {x}}$

p_{i}={\frac {1}{m))

A képlet segítségével a következőt kapjuk: $(2)$

I\left({\vec {x}}\right)=\sum _{i=1}^{m}{1 \over m^{2}}={1 \over m}

(3)

Ez a képlet használható egy többalfabetikus rejtjel egyezési indexének becslésére . Az angol nyelv esetében a többalfabetikus rejtjel egybeesésének indexe 0,03846, az orosz esetében (az "e" betű nélkül) - 0,03125.

Az egyszerű szöveg és a többalfabetikus rejtjel egybeesési indexének értékei jelentősen eltérnek. Ez lehetővé teszi az egyezések indexének ismeretében annak megállapítását, hogy a szöveget a nyíltból nyerjük egyszerű permutációval, vagy többalfabetikus titkosítás.

Kölcsönös egyeztetési index

Egy másik fontos fogalom a kölcsönös egyezési index .

Általános eset

Tekintsünk két karakterláncot , amelyek hossza és ill. Az ábécé, mint korábban, szimbólumokból áll. E karakterláncok kölcsönös illeszkedési indexe annak a valószínűsége, hogy az első karakterláncból véletlenszerűen kiválasztott karakter megegyezik a második karakterlánc véletlenszerűen kiválasztott karakterével. Legyen az ábécé edik karakterének száma az első és a második sorban. Ekkor az egyezések kölcsönös indexe egyenlő lesz: ${\vec x}$ ${\vec {y}}$ $n$ $n'$ $m$ ${\displaystyle f_{i},g_{i))$ $én$

MI\left({{\vec {x)),{\vec {y))}\right)={\sum \limits _{i=1}^{m}{\frac {f_{i }g_{i}}{nn'}}}

(négy)

Ennek a képletnek a bizonyítása hasonló a képlet bizonyításához . $(egy)$

Eltolt sorok

Gyakorlatilag fontos a match index módszernél egy speciális eset, amikor mindkét karakterláncot a plaintext ábécé eltolásával kapjuk. Jelölje - a -edik karakter előfordulásának valószínűségét a karakterláncban , - a karakterlánc ábécéjének eltolódását a karakterlánc ábécéjéhez képest (balra). Ekkor az ábécé -edik karakterének a karakterláncban való megjelenésének valószínűsége egyenlő (a karakterlánc ábécéjének számozását használjuk ). Az egybeesések kölcsönös indexére a következő képletet kapjuk: $p_{i}$ $én$ ${\vec x}$ $s$ ${\vec {y}}$ ${\vec x}$ $én$ ${\vec {y}}$ ${\displaystyle p_{i+s))$ ${\vec x}$

MI\left({{\vec {x)),{\vec {y))}\right)=\sum \limits _{i=1}^{m}{p_{i}p_{i +s}}

(5)

Vegye figyelembe, hogy azóta akkor a váltás ciklikus

\sum \limits _{i=1}^{m}{p_{i}p_{i+s}}=\sum \limits _{i=1}^{m}{p_{is}p_ {i}}=\sum \limits _{i=1}^{m}{p_{i+ms}p_{i}}

és a műszakok kölcsönös egyezési indexe, és ugyanazt az értéket veszi fel. $s$ $ms$

Az alábbiakban a kölcsönös koincidencia index értékei láthatók az orosz és az angol nyelv eltolódásától függően. Az értékek a -tól való eltolásokhoz vannak megadva . Mint fentebb említettük, ezen értékek alapján a kölcsönös találati index bármely eltolódásra kiszámítható. $0$ $m/2$

Orosz nyelvhez:

Váltás	Kölcsönös index
0	0,0553
egy	0,0366
2	0,0345
3	0,0400
négy	0,0340
5	0,0360
6	0,0326
7	0,0241
nyolc	0,0287
9	0,0317
tíz	0,0265
tizenegy	0,0251
12	0,0244
13	0,0291
tizennégy	0,0322
tizenöt	0,0244
16	0,0249

Angol nyelven:

Váltás	Kölcsönös index
0	0,0644
egy	0,0394
2	0,0319
3	0,0345
négy	0,0436
5	0,0332
6	0,0363
7	0,0389
nyolc	0,0338
9	0,0342
tíz	0,0378
tizenegy	0,0440
12	0,0387
13	0,0428

Megjegyzendő, hogy nulla eltolásnál a kölcsönös egybeesési index észrevehetően nagyobb, mint nullától eltérő eltolások esetén. Tehát az egybeesések kölcsönös indexének ismert értéke alapján megállapíthatjuk, hogy a karakterlánc ábécé eltolódása nulla vagy sem.

Algoritmus a kulcshossz meghatározásához

Osszuk fel a szöveget méretű oszlopokra . $x_{1}$ $x_{2}$ $...$ $x_{n}$ $t$

x_{1}

x_{t+1}

x_{2t+1}

...

x_{2}

x_{t+2}

x_{2t+2}

...

...

...

...

...

x_t

{\displaystyle x_{2t))

x_{3t}

...

Ha a kulcshossz többszöröse, akkor a szöveg minden két eleme pozíciókkal elválasztva, , ugyanazzal az ábécével van titkosítva. Ez pedig azt jelenti, hogy a táblázat fentebb kiírt minden sora az egyszerű szövegből származik permutációval . Ha nem többszöröse a kulcs hosszának, akkor a karakterláncok egy többalfabetikus rejtjel . $t$ $a\times t$ $a\in N$ $t$

Korábban kimutatták, hogy a nyílt szöveg permutációjának és a többalfabetikus titkosításnak az egyezési indexe észrevehetően különbözik. Így a különböző értékek iterálásával és mindegyikhez az egyezések indexének kiszámításával kiválaszthatjuk azokat , amelyek a kulcs hosszának többszörösei. Ezekből az adatokból nem nehéz meghatározni a kulcs hosszát. $t$ $t$

Algoritmus a kulcs megtalálásához

Tegyük fel, hogy meghatároztuk a kulcs hosszát . Most keressük meg a kulcsot. $t$

Írjuk újra a szöveget méretű oszlopokba . $t$

x_{1}

x_{t+1}

x_{2t+1}

...

x_{2}

x_{t+2}

x_{2t+2}

...

...

...

...

...

x_t

{\displaystyle x_{2t))

x_{3t}

...

Tekintsük ennek a táblázatnak két sorát. Toljuk el az egyik karakterlánc ábécéjét karakterenként, és számítsuk ki a kapott karakterláncok egyezéseinek kölcsönös indexét. Mert e két karakterlánc mindegyikét az egyszerű szöveges ábécé eltolásával kapjuk, akkor az egyezések maximális kölcsönös indexe nulla végső relatív eltolódásnál lesz megfigyelhető. $s$

Ezért a következő algoritmust alkalmazzuk: kiszámoljuk az egybeesések kölcsönös indexét különböző , és azt az értéket keressük , amelynél a koincidenciák kölcsönös indexe maximális. Ekkor a vonalak kezdeti relatív eltolódása egyenlő lesz ( - az ábécé mérete). A rendszer kiszámítja az összes vonalpár közötti relatív eltolódást. Mert a táblázat sorainak eltolásai megfelelnek a kulcs betűinek eltolásainak, ezután hátra van a lehetséges billentyűk közötti válogatás és közülük a legvalószínűbb kiválasztása. $s$ $s$ $ms$ $m$ $m$

Használati példa

Adjunk meg néhány Vigenère-rejtjellel titkosított szöveget . Keresse meg a kulcsszót, és olvassa el az egyszerű szöveget.

vltsduzhbutzhyarrmshbrkhtseooetsgbrtsmyfktyyumshesyatspunuyashcheytaedkzibr tsgbrpackkkutspbsegktsguuschartsyoevryuoyuekaaebrnyafukabarpyaafkyzhyaffnyo yafyvbnenfuyugbrsshzhetbeyochyuyuryegofkbchyabashvyoyyuadnzhzhzhuztseevlrnchulb yuptsurun'shseyuuzktskhyarrnryuvyaspemaschkpeuzhzhyatufuyaruravrtuburpeshlafouf buatsmnubsyukytaedyunooegyuozhbgkbryntsepotchmeodztsvbtsshshvshchepchdchdryyusksag yppegyukdoyrsrevoopchschshokazrbbneugnyaloksrbyuyebdeulbyuasshowetshkrsdugefl bubujchchtrtpegyukiugyuemegyukk'pegyaapufuezradzzhchyurmftskhrayuyuanchechyuhyyhy tsomeftspoirknshchpeteuzyabaschushchbayechdfrpetsjrtsjtspoillufedtsoyedyatrrachkubu fnytaedktskrnntsyuabugyuuuburpyuezhtgyurkuyuschoufegyasuoichschshchdtssfyredshe yuyafshechtsyuyrshvyakhvmkrshrpgyuopeutschytaedktsybrtsyyazhturbuetebduyascheubibruv hedgehoggibrbagbrympunotsshyazhtsechkfodscho'chzhshyuytskhchshvuebdldegyasuahzzebdeulkn shbzhyatseerredyvyuvlnyafuoohfekgtschgezhtanopchynazhpackkyumenkyrefshchebbud endadyaryeyueletchoubcefevlnoegfdseveyokbschoukgouteypubbtschkpegyuchsaabenefark atskhyovaetufyaepryuvrzhadfezhbfutoshchoyavgupchrshhuiteachychiramchufchouyayuonkyazhy kgstsbryasshchyot'zhrsshchl

Tekintettel arra, hogy a kulcshossz keresésének teljes algoritmusa rendkívül körülményes, csak a megfelelőségi indexet számítjuk ki, és ellenőrizzük, hogy a kulcs hossza valóban 5 legyen. $t=5$

vthmtststmtsyaatstsatsyavoayabya'fyanyustuyebauduvu... lzhshagmshpshchgchpegryuefyiffegshbgshzhnzhll ... tsbyabobyeueebbkgutsrebuaanynbeyuochvchtsrb ... durrorfusnydrrbkuyoukrfzhyvfrzherfyayoyuzhenyu... utsrhekyautkputsshcheuanapkyaobuyechkykbeachechp...

Az egyes sorok indexértékeinek egyezése:

Vonal	Match Index
egy	0,05676
2	0,05896
3	0,06340
négy	0,05810
5	0,07230

A relatív vonaleltolódások keresésének folyamatát is összefoglaljuk:

Vonal	Váltás	Kölcsönös Match Index
egy	—	—
2	6	0,05494
3	3	0,05798
négy	16	0,06068
5	3	0,06045

Talált kulcsszó: "szó".

A visszafejtés után a következő egyszerű szöveget kapjuk:

Egészségesnek lenni ugyanaz, mint nem betegnek lenni, az egészség minden bizonnyal fájdalom nyakunkba a fizikai egészségünknek ezt az állapotot és a képességet és energiát a dolgok elvégzésére Örömet kell szereznem belőle, és minden segítség nélkül felépülni egészség, paradox módon nem tudod közvetlenül rákényszeríteni magad arra, hogy egészséges legyél. nincs más hátra, mint megfigyelni, hogyan gyógyul testének csodálatos képessége te magad kezd el cselekedni a saját vagyonod vagy szegénységed kegyetlensége vagy egyéb úgy tűnik, hogy a tevékenység itt nem számít, az egészség valami pozitív dolog de ez nem jelenti az élvezet megtagadását, az egészség természetes következménye életmódunk a kapcsolat diéta környezet egészség nélkülözhetetlen dmethproperty ez egy folyamat ezt csináljuk gondolataink és érzéseink eredménye ez o létezés módja érdekes, hogy az orvosi kutatás iránya egyre inkább inkább eltér egy olyan terület felé, amelyet eddig tevékenységi körnek tekintettek sti pszichológusok és ma már nehéz egyértelmű különbséget tenni a fizikai és betegségek mentális tényezői

Jegyzetek

↑ 1 2 Pilidi, 2009 , p. 55.
↑ 1 2 3 4 5 Friedman, 1938 , p. 117.

Lásd még

Irodalom

William Frederick Friedman. Katonai kriptoanalízis. rész II. A többalfabetikus helyettesítési rendszerek egyszerűbb változatai . - Washington: Egyesült Államok kormányának nyomdája, 1938. - 120 p. Archivált : 2010. szeptember 11. a Wayback Machine -nél
Pilidi V. S. Kriptográfia. Bevezető fejezetek . - Rostov-on-Don: SFU, 2009. - 110 p.
Bauer F., Titkok megfejtve. A kriptológia módszerei és alapelvei: Per. angol - M.: Mir, 2007. - 550 p. — ISBN 5-03-003551-6
Zsdanov O.N., Kudenkova I.A. Klasszikus titkosítások kriptoanalízise – Krasznojarszk 2008