Autokorrelationsmetod

Autokorrelationsmetoden är en metod för kryptoanalys av polyalfabetiska chiffer , såsom Vigenère-chifferet .

Beskrivning av metoden

Autokorrelationsmetoden tillåter kryptoanalytikern att hitta längden på nyckelordet som används i det polyalfabetiska chiffer. När nyckelordets längd har upptäckts arrangerar kryptoanalytikern chiffertexten i kolumner. I det här fallet kan varje kolumn betraktas som en text krypterad med ett monoalfabetiskt chiffer, som kan utsättas för frekvensanalys. $l$ $l$

Denna metod låter dig hitta längden på ett nyckelord med bättre noggrannhet än Kasiski-metoden [1] .

Själva metoden består i att den ursprungliga chiffertexten skrivs ut på en rad, och under den skrivs de rader som erhålls genom att flytta till höger med positioner. För varje beräknas antalet matchningar , där autokorrelationskoefficienterna beräknas : $(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]$ ${\displaystyle \gamma _{t))$

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

För skift som är multipler av en period bör koefficienterna vara märkbart större än för skift som inte är multiplar av en period och har ett värde nära sammanfallsindexet för det använda språket [2] [1] (för det ryska språket ~ 0,0553). Detta förklaras enligt följande. När skiftvärdet är en multipel av nyckelordets längd, krypteras tecknen och med samma monoalfabetiska chiffer, vilket inte ändrar det faktum att de matchar. Och eftersom koincidensindex introduceras som sannolikheten för att matcha två godtyckliga bokstäver i en sträng, så kommer autokorrelationskoefficienter, med en tillräckligt stor textlängd, att vara nära den naturliga språksammanfallen för skift som är multiplar av eller lika med perioden. index [1] . ${\displaystyle \gamma _{t))$ ${\displaystyle c_{i))$ ${\displaystyle c_{i+t))$

Användningsexempel

Låt följande text krypteras utan att ta hänsyn till skiljetecken och skillnaden mellan små och stora bokstäver (bokstäverna I och Y skiljer sig inte heller åt).

Allt som jag råkade vara vittne här var inte helt främmande för mig, jag läste något om sådana fall någonstans och nu kom jag ihåg att beteendet hos människor som hamnat i liknande omständigheter alltid föreföll mig ovanligt, irriterande absurt. Istället för att fullt ut utnyttja de spännande möjligheter som öppnades för dem av en lycklig olycka, blev de rädda, försökte återgå till det vanliga. Någon hjälte trollade till och med läsarna att hålla sig borta från slöjan som skiljer vår värld från det okända, och skrämmer dem med andliga och fysiska skador. Jag visste ännu inte hur händelserna skulle utvecklas, men jag var redan redo att kasta mig in i dem med entusiasm. När jag vandrade runt i rummet på jakt efter en slev eller mugg fortsatte jag att resonera. Dessa rädda människor, tänkte jag, är som vissa experimentella vetenskapsmän, väldigt envisa, väldigt flitiga, men helt fantasilösa och därför väldigt försiktiga. Efter att ha fått ett icke-trivialt resultat drar de sig för det, förklarar det hastigt som experimentets orenhet och går i själva verket bort från det nya, eftersom de har blivit alltför vana vid det gamla, bekvämt lagt inom gränserna för en auktoritativ teori. Jag hade redan övervägt några experiment med blädderboken (den låg fortfarande på fönsterbrädan och var nu Aldridges The Last Exile), med en talande spegel och med ett klick. Jag hade några frågor till katten Vasily, och sjöjungfrun som bodde på eken var av visst intresse, även om det ibland verkade för mig att jag drömde om henne. Jag har inget emot sjöjungfrur, men jag kan inte föreställa mig hur de kan klättra i träd... fast, å andra sidan, fjäll...?

- A.N. och B.N. Strugatsky "måndag börjar på lördag"

Låt oss använda Vigenère-chifferet med nyckelordet KEY. Krypterat meddelande:

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

Låt oss beräkna autokorrelationskoefficienterna för skiftningarna och bygga en graf . Det genomsnittliga avståndet mellan funktionens toppar är 4, så sökordslängden antas vara 4, vilket är samma som används. $t=1,\dotsc ,200$ $\gamma (t)$

Därefter måste du hitta frekvensen av förekomsten av bokstäver för chiffertexterna som erhålls från kolumnerna. $l=4$

Frekvens av förekomst av chiffertextbokstäver från olika kolumner
Chiffertext 1
Chiffertext 2
Chiffertext 3
Chiffertext 4

Låt oss anta att Vigenère-chifferet användes för kryptering. Sedan, för att dekryptera alla fyra chiffertexterna, är det nödvändigt att jämföra frekvensfördelningen av bokstäver i chiffertexter med distributionen av naturligt språk. Detta kan bäst göras med Pearsons godhet -of-fit-test . Låt oss hitta värdena för kriteriet för fördelningarna som erhålls genom en cyklisk förskjutning till höger från fördelningen av frekvensen av förekomst av bokstäver på det ryska språket. $\chi ^{2}$

Kriterievärden för olika chiffertexter $\chi ^{2}$
Testa skift	Chiffertext 1	Chiffertext 2	Chiffertext 3	Chiffertext 4
0	187,33	236,14	305,90	200,40
ett	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
fyra	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
åtta	186,87	108.03	345,46	188,55
9	41,01	133,46	687,30	305,10
tio	149,77	38,14	323,51	499,16
elva	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
fjorton	153,22	158,91	359,30	251,65
femton	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
arton	189,05	180,04	228,15	95,76
19	280,02	198,82	173,35	108,07
tjugo	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
trettio	182,17	259,69	170,44	138,66

Så vi fick värdena för de skift som används i de monoalfabetiska chifferna i var och en av kolumnerna: 9,10,22,29. För det valda alfabetet motsvarar detta nyckelordet för Vigenère-chifferet KEY. Texten har dechiffrerats.

Se även

Litteratur

E.M. Gabidulin. Dataskydd. - Moskva: MIPT, 2011.
Thomas Johansson. Föreläsningsanteckningar i kryptografi . — 2005.

Länkar

Föreläsningsanteckningar i kryptotafi Thomas Johansson