Autokorrelaatiomenetelmä

Autokorrelaatiomenetelmä on menetelmä monikirjaimien salausten , kuten Vigenère -salauksen, kryptausanalyysiin .

Menetelmän kuvaus

Autokorrelaatiomenetelmän avulla kryptanalyytikko voi löytää moniaakkosisessa salauksessa käytetyn avainsanan pituuden. Kun avainsanan pituus on löydetty, kryptanalyytikko järjestää salatekstin sarakkeiksi. Tässä tapauksessa jokaista saraketta voidaan pitää yksiaakkosisella salauksella salattuna tekstinä, jolle voidaan tehdä taajuusanalyysi. $l$ $l$

Tällä menetelmällä voit löytää avainsanan pituuden paremmin kuin Kasiski-menetelmä [1] .

Menetelmä itsessään koostuu siitä, että alkuperäinen salateksti kirjoitetaan rivillä ja sen alle kirjoitetaan paikoilla oikealle siirtymällä saadut rivit . Jokaiselle lasketaan osumien määrä , jossa lasketaan autokorrelaatiokertoimet : $(c_{1},c_{2},\dotsc ,c_{L})$ $t=1,2,3,\dotsc$ $t$ $n_t$ ${\displaystyle c_{i}=c_{i+t))$ $i\in\left[1,Lt\right]$ ${\näyttötyyli \gamma _{t))$

\gamma _{t}={\dfrac {n_{t}}{Lt}}

Jakson kerrannaisina olevien vuorojen kertoimien tulee olla huomattavasti suurempia kuin vuorojen, jotka eivät ole jakson kerrannaisia, ja niiden arvon tulee olla lähellä käytetyn kielen koinsidenssiindeksiä [2] [1] (venäjän kielelle ~ 0,0553). Tämä selitetään seuraavasti. Kun siirtoarvo on avainsanan pituuden kerrannainen, merkit ja salataan samalla yksiaakkosisella salauksella, mikä ei muuta niiden yhteensopivuutta. Ja koska yhteensattumaindeksi otetaan käyttöön todennäköisyydeksi sovittaa kaksi mielivaltaista kirjainta merkkijonossa, niin siirtymillä, jotka ovat pisteen kerrannaisia tai yhtä suuria, autokorrelaatiokertoimet riittävän suurella tekstipituudella ovat lähellä luonnollisen kielen yhteensattumaa. indeksi [1] . ${\näyttötyyli \gamma _{t))$ ${\displaystyle c_{i))$ ${\displaystyle c_{i+t))$

Käyttöesimerkki

Olkoon seuraava teksti salattu ottamatta huomioon välimerkkejä ja pienten ja isojen kirjainten eroa (kirjaimet I ja Y eivät myöskään eroa toisistaan).

Kaikki mitä täällä satuin olemaan todistajaksi, ei ollut minulle täysin tuntematonta, jostain luin tällaisista tapauksista ja nyt muistin, että samanlaisiin olosuhteisiin joutuneiden ihmisten käyttäytyminen tuntui minusta aina epätavalliselta, ärsyttävän absurdilta. Sen sijaan, että olisivat käyttäneet täysimääräisesti hyväkseen iloisen onnettomuuden heille avaamia jännittäviä näkymiä, he pelästyivät, yrittivät palata arkielämään. Jotkut sankarit jopa loihdittivat lukijat pysymään poissa verhosta, joka erottaa maailmamme tuntemattomasta ja pelotti heitä henkisillä ja fyysisillä vammoilla. En vielä tiennyt, miten tapahtumat etenevät, mutta olin jo valmis sukeltamaan niihin innostuneena. Kulkiessani ympäri huonetta etsimään kauhaa tai mukia, jatkoin järkeilyä. Luulin, että nämä pelokkaat ihmiset ovat kuin joitain kokeellisia tiedemiehiä, hyvin itsepäisiä, erittäin ahkeria, mutta täysin mielikuvituksettomia ja siksi hyvin varovaisia. Saatuaan ei-triviaalin tuloksen he ujostelevat sitä, selittäen sen hätäisesti kokeen epäpuhtaudeksi ja itse asiassa siirtyvät pois uudesta, koska he ovat liian tottuneet vanhaan, mukavasti asettuneet kokeen rajoihin. arvovaltainen teoria. Olin jo harkinnut kokeiluja käännettävällä kirjalla (se oli vielä ikkunalaudalla ja nyt Aldridgen viimeinen maanpako), puhuvalla peilillä ja napsautuksella. Minulla oli muutama kysymys kissa Vasilille, ja tammen päällä asuva merenneito kiinnosti, vaikka välillä tuntuikin, että unelmoin hänestä. Minulla ei ole mitään merenneitoja vastaan, mutta en voi kuvitella kuinka ne voivat kiivetä puihin... vaikka toisaalta vaa'at...?

- A.N. ja B.N. Strugatski "Maanantai alkaa lauantaina"

Käytetään Vigenère-salausta avainsanan KEY kanssa. Salattu viesti:

MYGOPTsSVTsRPBBZHBCHYSHDYUORPUUNZHYPGBPTSLLEIDKHGZCHNGZHBRLGCHCHGYU TsLZDHEKDSHVDLCHSCHMHSOCKUTSNPGICHBRDYSHHYALYYRNSHCHAZSHKGTHCHCHMSCH PPGGTRIKHORZHECHSHCHYUKNTSYAYUNYUGKHMTBLTPSHYAZYSHEIPKHZYNYUSCHRBYKSHCHOOYRCH МХЭБЧЫВЦРЛЧМШОКУЛАДЧЛЭЫЧЛДЧЗГГГПХГДКАВЫРДЫШБДДЦВЧПИ EIZHZSHIUSACHYZHSSCHFRZCHYRIUCEGEPЪPEPFRYAMEMIUSCCHBUGZIPIZZUUZALPI FUATHYIKALGVCHZHEOYUBTYYZYLOCHFUPUMROG'ZINMSHDPGGTSSHGAKFMYYSHB SCHSHZHYKSGUKFIYATSLIOTYUIPHGYAOROEKY'ZISCHMYKKHPPSHRYUKNGZDSHRYPHEHVRZHG KVKYASCHSHRGPNGYCHTSMCHSCSHSKKKVKYUSHAGDZHYAEUEYAARPATTZZHKMRKHUITZZHTSPGGGPPTLCH FFUASCHPLICKYYEZCHMSCHMSHIELDKLDSGSHDKHBDYSHAZZHCHRKSUYUHSHKDUELKYZHPTSMCHM LMYISCHMACHTSLCHYRAECUPAKYAZDMVYUYAFUZHZYADOSHIEKHOCHYSEOLRUGGEE OYYAMEGBZPZHYYTSYUBISCHMMCHSZHGKCHGACHMZHDYASOPCHCHMZHFPEPJVPCHRCHYSHODMSHH TsZHSECHLTYUSHKHTSZHZHPMBZMZHSHCHDYALDTSLHYAMBTVGGTSEUSCCHSHYAZHKGGTKZHECHZRD HEMOPCCHDJHCHSLTYUSCHMBBZHSCCCRRZHTNZHCHFZHLTTT'GYUHIKMKMGTVYUZHKYYYYYYYED YCHGCHCHMZSHRTSGCHYASIYLTZZGCHCHGOTYRDYSHZHFUYNSCHUKTSYUYAELZITBGZUUSSM CHPEICHLDMShBDSHRDKHEHICHYYBFMVSSZHBTYYZCHYRCCHEKKZLDHMECHLTHNNZH PPGBDLAICHZHIPLDTHGDSHUZHTSSGDLPSVDNYUBUSHGAKFJZHFPEPJVPCRTJFL NSHZHEP'GSHCHP'RTBRKDTsLNDSH'GETSRKKFRDCHFLLCHSHVDUSHLGTFGYALEIIICHYRNCHZHND ЪHGYTSUKYASOLCHTSCHZHACHTSMBOYJYRLPCHNMZHIGZHVSROAKKHMVTYFTULLUPTSVPCHESH DHMGPYZDFZDMSHNZHCHYMSCHUFMINYUZTHJHOLZHYYBULDYAMECHICHYYMGESCHRVZ YLABIHYUDSHGYPHGGZZHYATSGZHPYYYKGPCYGKTsZZHRZHSLIDJHICHSHLCHYSHKG PNPYLZYASHJZTSUICHZHEGTBGCHCHGYAHRIESCHSHRYAMSZKHMATSSHLSHGYYYUSCHFKZ PMGAKFMGTTSM'YICHSURUSHSHVSHCHRAUITSUDYKPYSHCHEBDTYRDCHSHLTARTSKI

Lasketaan siirtymien autokorrelaatiokertoimet ja rakennetaan kuvaaja . Funktion huippujen välinen keskimääräinen etäisyys on 4, joten avainsanan pituudeksi oletetaan 4, mikä on sama kuin käytetty. $t=1,\dotsc ,200$ ${\näyttötyyli \gamma (t)}$

Seuraavaksi sinun on löydettävä sarakkeista saatujen salatekstien kirjainten esiintymistiheys . $l=4$

Eri sarakkeiden salatekstikirjaimien esiintymistiheys
Salateksti 1
Salateksti 2
Salateksti 3
Salateksti 4

Oletetaan, että salaukseen käytettiin Vigenère-salausta. Sitten kaikkien neljän salatekstin salauksen purkamiseksi on tarpeen verrata salatekstien kirjainten taajuusjakaumia luonnollisen kielen jakaumaan. Tämä voidaan tehdä parhaiten käyttämällä Pearsonin sopivuustestiä . Etsitään kriteerin arvot jakaumille, jotka on saatu syklisellä siirrolla oikealle venäjän kielen kirjainten esiintymistiheyden jakaumasta. $\chi ^{2}$

Kriteeriarvot eri salateksteille $\chi ^{2}$
Testaa vaihtoa	Salateksti 1	Salateksti 2	Salateksti 3	Salateksti 4
0	187,33	236.14	305,90	200.40
yksi	290,44	273,37	113.24	304,52
2	272,67	273.02	219,89	236,90
3	177,16	228,69	174,97	207,69
neljä	98,71	163,95	310,41	155,80
5	128,73	109,71	422,07	303,72
6	131,38	120,38	195.10	311,95
7	149,33	104.18	212.48	237,96
kahdeksan	186,87	108.03	345,46	188,55
9	41.01	133,46	687,30	305.10
kymmenen	149,77	38.14	323,51	499,16
yksitoista	203.27	106,64	220,85	273,98
12	98.06	166,77	506,90	207,85
13	160,70	107,82	403,45	254,92
neljätoista	153,22	158,91	359,30	251,65
viisitoista	329,41	125,60	231,77	227,18
16	339,94	293,00	348,73	149,73
17	185,61	328,77	448,32	91,33
kahdeksantoista	189.05	180.04	228.15	95,76
19	280.02	198,82	173,35	108.07
kaksikymmentä	505.03	274,43	187.07	87,90
21	259,86	357,71	254,99	71,54
22	159,53	267.11	217,55	38,73
23	315,64	163,35	128,58	115.03
24	300,66	234,87	87,64	159,85
25	254,91	310,44	118,82	95,58
26	175,78	293.11	116.28	118,71
27	259.02	216,49	180,47	139,34
28	424,97	263,13	259,86	290,69
29	240,80	479,59	45,60	283,53
kolmekymmentä	182,17	259,69	170,44	138,66

Joten saimme kunkin sarakkeen yksiaakkosisissa salakirjoissa käytettyjen siirtymien arvot: 9,10,22,29. Valitulle aakkostolle tämä vastaa Vigenèren salausavainsanaa KEY. Teksti on purettu.

Katso myös

Kirjallisuus

E. M. Gabidulin. Datan suojelu. - Moskova: MIPT, 2011.
Thomas Johanson. Salaustekniikan luentomuistiinpanot . – 2005.

Linkit

Luentomuistiinpanot kryptogtafiasta Thomas Johansson