Matchindex

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 mars 2013; kontroller kräver 28 redigeringar .

Sammanfallsindexet är en av metoderna för kryptoanalys av Vigenère-chifferet . Beskrivningen publicerades av William Friedman 1920.

Metoden bygger på att beräkna sannolikheten för att två slumpmässiga textelement kommer att matcha. Denna sannolikhet kallas coincidence index. William Friedman visade att värdena för slumpindexet skiljer sig avsevärt för texter av olika karaktär. Detta gör att du först kan bestämma längden på chiffernyckeln och sedan hitta själva nyckeln.

Tillkomsten av slumpindexmetoden öppnade för nya möjligheter i kryptoanalysen av Vigenère-chifferet. Jämfört med den då vanliga Kasiska-metoden var den nya metoden mindre arbetsintensiv, krävde mindre text, var mer mottaglig för automatisering och mindre felbenägen. Matchningsindexet var mer effektivt och tillät analys av chiffer med långa nycklar.

Historik

Blaise Vigenère presenterade en beskrivning av ett enkelt men starkt chiffer före uppdraget av Henrik III av Frankrike 1586, och uppfinningen av chifferet tillskrevs senare till honom. Vigenère-chifferet hade ett rykte om sig att vara exceptionellt resistent mot "manuell" sprickbildning. Den första framgångsrika attacken mot Vigenère-chifferet utfördes av Friedrich Kasiski 1863. Hans metod förblev den huvudsakliga metoden för kryptoanalys av Vigenère-chifferet fram till 1920, när William Friedman publicerade monografin Index of Coincidence och dess tillämpningar i kryptografi . Den nya metoden som Friedman beskrev erbjöd ett mer effektivt och feltolerant sätt att bestämma nyckellängden. Slumpindexmetoden har använts flitigt. Den användes senare i maskinassisterad kryptoanalys.

Krypteringsmetod för Vigenère-chifferet

Vigenère-chifferet är ett polyalfabetiskt chiffer . Hans kryptoanalys kan delas upp i två steg:

Först försöker de bestämma nyckellängden. Nyckellängden anger antalet alfabet som används och perioden för kryptering av dessa alfabet. Därför undersöks i detta skede chiffertextens periodicitet;
Efter att längden har hittats börjar de söka efter en specifik typ av nyckel. För att göra detta beräknas de relativa skiftningarna av de använda alfabeten, och sedan väljs nyckeln med brute force.

Matchindex

Nedan finns formlerna för att beräkna träffindexet. Först övervägs det allmänna fallet. Sedan överväger vi flera specialfall där sammanfallsindex kan uppskattas utan textanalys.

Allmänt fall

Tänk på en text skriven på något språk. Alfabetet för ett givet språk antas bestå av symboler. Tänk på en tillräckligt lång teckensträng . Matchningsindexet är sannolikheten att två godtyckliga tecken i en sträng matchar. Om är numret på det -: te tecknet i alfabetet i strängen , så beräknas matchningsindexet med formeln: $m$ ${\vec x}$ $n$ $f_{i}$ $i$ ${\vec x}$

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

(ett)

Bevis

Vi kommer att uppskatta sannolikheten som förhållandet mellan gynnsamma utfall (antalet par av identiska tecken i en sträng) och det totala antalet utfall (antalet olika teckenpar i en sträng).

Antalet distinkta par av det e tecknet i strängen är: ${\displaystyle {\displaystyle i))$

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

Antal par av identiska tecken i en sträng:

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

Antal distinkta teckenpar i en sträng:

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

Härifrån får vi:

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

Vanlig text

Låt oss säga att strängen är vanlig text eller erhålls från den genom en enkel permutation . I det här fallet uttrycks indexet av sammanträffanden bekvämt i termer av sannolikheterna för förekomsten av den -te symbolen. Låt oss utse dem . Då får vi följande formel: ${\vec {x}}$ $i$ $pi}$

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

(2)

Därför att värden har väldefinierade värden, för vanlig text beror indexet över tillfälligheter inte på dess innehåll, utan beror bara på språket som texten är skriven på. Dessutom är värdena undersökta och kända, vilket gör det möjligt att beräkna värdena för klartextmatchningsindex för olika språk. $pi}$ $pi}$

Språk	Matchindex
ryska	0,0553 [1]
engelsk	0,0644 [1] 0,0667 [2]
italienska	0,0738 [2]
spanska	0,0775 [2]
Deutsch	0,0762 [2]
franska	0,0778 [2]
Vedisk sanskrit	0,021076696
Prakrit	0,046635758
Klassisk sanskrit	0,045567736
hindi	0,041837864
urdu	0,057535302

Slumpmässig sträng

Slutligen, låt vara en slumpmässig sträng. Då är sannolikheten för förekomst av varje symbol lika med ${\vec {x}}$

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

Med formeln får vi: $(2)$

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

(3)

Denna formel kan användas för att uppskatta matchningsindexet för ett polyalfabetiskt chiffer . För det engelska språket kommer indexet för sammanträffanden för det polyalfabetiska chiffret att vara 0,03846, för ryska (utan bokstaven "e") - 0,03125.

Värdena för sammanfallsindexet för ren text och för det polyalfabetiska chifferet är signifikant olika. Detta gör det möjligt att, genom att känna till indexet för matchningar, avgöra om texten erhålls från det öppna genom en enkel permutation eller är ett polyalfabetiskt chiffer.

Ömsesidigt matchningsindex

Ett annat viktigt koncept är det ömsesidiga matchningsindexet .

Allmänt fall

Betrakta två strängar och med längder och respektive. Alfabetet består liksom tidigare av symboler. Det ömsesidiga matchningsindexet för dessa strängar är sannolikheten att ett tecken slumpmässigt valt från den första strängen kommer att matcha ett slumpmässigt valt tecken från den andra strängen. Låt vara numret på det e tecknet i alfabetet på den första respektive andra raden. Då kommer det ömsesidiga indexet för matchningar att vara lika med: ${\vec x}$ ${\vec {y}}$ $n$ $n'$ $m$ ${\displaystyle f_{i},g_{i))$ $i$

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

(fyra)

Beviset för denna formel liknar beviset för formeln . $(ett)$

Förskjutna rader

Praktiskt viktigt för matchningsindexmetoden är ett specialfall när båda strängarna erhålls genom att skifta klartextalfabetet. Beteckna — sannolikheterna för förekomsten av det -: te tecknet i strängen , — förskjutningen av strängens alfabet i förhållande till strängens alfabet (till vänster). Då är sannolikheterna för utseendet av alfabetets -te tecken i strängen lika (numreringen av strängens alfabet används ). För det ömsesidiga indexet av tillfälligheter får vi följande formel: $pi}$ $i$ ${\vec x}$ $s$ ${\vec {y}}$ ${\vec x}$ $i$ ${\vec {y}}$ ${\displaystyle p_{i+s))$ ${\vec x}$

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

(5)

Observera att sedan Skiftet är alltså cykliskt

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

och ömsesidigt matchningsindex för skift och tar samma värde. $s$ $ms$

Nedan är värdena för det ömsesidiga sammanträffande indexet beroende på skiftet för de ryska och engelska språken. Värden anges för skift från till . Som nämnts ovan, baserat på dessa värden, kan det ömsesidiga träffindexet beräknas för varje skift. $0$ $m/2$

För ryska språket:

Flytta	Ömsesidigt index
0	0,0553
ett	0,0366
2	0,0345
3	0,0400
fyra	0,0340
5	0,0360
6	0,0326
7	0,0241
åtta	0,0287
9	0,0317
tio	0,0265
elva	0,0251
12	0,0244
13	0,0291
fjorton	0,0322
femton	0,0244
16	0,0249

För engelska:

Flytta	Ömsesidigt index
0	0,0644
ett	0,0394
2	0,0319
3	0,0345
fyra	0,0436
5	0,0332
6	0,0363
7	0,0389
åtta	0,0338
9	0,0342
tio	0,0378
elva	0,0440
12	0,0387
13	0,0428

Observera att vid nollskift är det ömsesidiga koincidensindexet märkbart större än vid icke-nollskift. Så, enligt det kända värdet av det ömsesidiga indexet av tillfälligheter, kan vi dra slutsatsen om ändringen av strängalfabeten är noll eller inte.

Algoritm för att hitta nyckellängden

Låt oss dela upp texten i kolumner med storlek . $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}

...

Om det är en multipel av nyckellängden, krypteras vartannat element i texten åtskilda av positioner, , med samma alfabet. Och detta betyder att varje rad i tabellen som skrivits ut ovan erhålls från klartexten genom permutation . Om det inte är en multipel av nyckellängden är strängarna ett polyalfabetiskt chiffer . $t$ $a\times t$ $a\in N$ $t$

Tidigare har det visat sig att indexet för matchningar för en permutation av klartext och för ett polyalfabetiskt chiffer är märkbart olika. Genom att iterera över olika värden och beräkna indexet för matchningar för var och en av dem, kan vi alltså välja de som är multiplar av nyckelns längd. Det är inte svårt att bestämma nyckellängden från dessa data. $t$ $t$

Algoritm för att hitta nyckeln

Anta att vi har definierat nyckellängden . Låt oss hitta nyckeln nu. $t$

Låt oss skriva texten igen i kolumner med storlek . $t$

x_{1}

x_{t+1}

x_{2t+1}

...

x_{2}

x_{t+2}

x_{2t+2}

...

...

...

...

...

x_t

{\displaystyle x_{2t))

x_{3t}

...

Tänk på två rader i denna tabell. Låt oss ändra alfabetet för en av strängarna med tecken och beräkna det ömsesidiga indexet för matchningar av de mottagna strängarna. Därför att var och en av dessa två strängar erhålls genom att skifta klartext-alfabetet, sedan kommer det maximala ömsesidiga indexet för matchningar att observeras vid noll slutlig relativ skiftning. $s$

Därför tillämpas följande algoritm: det ömsesidiga indexet av sammanträffanden beräknas för olika , värdet söks efter vid vilket det ömsesidiga indexet av sammanträffanden är maximalt. Då kommer den initiala relativa förskjutningen av linjerna att vara lika med ( - storleken på alfabetet). Relativa förskjutningar mellan alla linjepar beräknas. Därför att skiftningarna i tabellens rader motsvarar skiftningarna av nyckelns bokstäver, sedan återstår att sortera igenom de möjliga nycklarna och välja den mest troliga bland dem. $s$ $s$ $ms$ $m$ $m$

Användningsexempel

Låt lite text krypterad med Vigenère-chifferet ges . Hitta nyckelordet och läs klartexten.

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

På grund av det faktum att den fullständiga algoritmen för att hitta nyckellängden är extremt besvärlig, beräknar vi matchningsindexet endast för och ser till att nyckellängden verkligen är lika med 5. $t=5$

vthmtststmtsyaatstsatsyavoayabya'fyanyustuyebauduvu... lzhshagmshpshchgchpegryuefyiffegshbgshzhnzhll ... tsbyabobyeueebbkgutsrebuaanynbeyuochvchtsrb ... durrorfusnydrrbkuyoukrkrfzhyvfrjorfyayoyuzhenyu... utsrhekyautkputsshcheuanapkyaobuyechkykbeachechp...

Matcha indexvärden för var och en av raderna:

Linje	Matchindex _
ett	0,05676
2	0,05896
3	0,06340
fyra	0,05810
5	0,07230

Processen att söka efter relativa linjeskift sammanfattas också:

Linje	Flytta	Ömsesidigt matchningsindex
ett	—	—
2	6	0,05494
3	3	0,05798
fyra	16	0,06068
5	3	0,06045

Hittade nyckelord: "ord".

Efter dekryptering får vi följande klartext:

Är att vara frisk är samma sak som att inte vara sjuk, definitivt är hälsa något smärta hals för oss fysisk hälsa detta tillstånd och förmågan och energin att göra saker Jag måste njuta av det och återhämta mig utan någon hjälp från hälsa, paradoxalt nog kan du inte direkt tvinga dig själv att vara frisk. allt som återstår är att observera hur din kropps fantastiska förmåga att läka du själv börjar agera på egen hand din rikedom eller fattigdom grymhet eller annat aktivitet verkar inte spela någon roll här hälsa är något positivt men det betyder inte förnekande av njutning, hälsa är en naturlig följd av vår livsstil i relation kost miljö hälsa är en oumbärlig dmethproperty detta är en process det här är vad vi gör resultatet av våra tankar och känslor detta o sätt att existera är det intressant att riktningen för medicinsk forskning är mer och mer avviker mer mot ett område som hittills ansetts som ett verksamhetsområde sti psykologer och det är nu svårt att dra tydliga skillnader mellan fysiska och mentala faktorer av sjukdomar

Anteckningar

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

Se även

Litteratur

William Frederick Friedman. Militär kryptoanalys. Del II. Enklare varianter av polyalfabetiska substitutionssystem . - Washington: USA:s regeringstryckeri, 1938. - 120 sid. Arkiverad 11 september 2010 på Wayback Machine
Pilidi V. S. Kryptografi. Inledande kapitel . - Rostov-on-Don: SFU, 2009. - 110 sid.
Bauer F., Hemligheter dechiffrerade. Metoder och principer för kryptologi: Per. engelsk - M.: Mir, 2007. - 550 sid. — ISBN 5-03-003551-6
Zhdanov O.N., Kudenkova I.A. Kryptanalys av klassiska chiffer – Krasnoyarsk 2008