Vigenère'i šiffer: leia võtme pikkus ja murra kood

L tähest koosnev võti muudab sõnumi L läbipõimunud Caesari šifriks. Kirjuta salatekst k-kaupa ridadesse ja loenda veergudes kokkulangevusi: õige k korral käitub iga veerg taas tavalise inglise keelena. Liigu ründes sammhaaval edasi või vali tulp ise.

Näidisarvutus — Vigenère'i šiffer: leia võtme pikkus ja murra kood

Tähti sõnumis, N	600
Salateksti kokkulangevusindeks	0,0417
I peatüki kokkulangevusindeks (8606 tähte)	0,0665
Võtme pikkus: väikseim k üle joone	6
6 veeru keskmine IC	0,0659
Tuletatud võti	RABBIT
Õigesti taastatud tähed	600 600-st (100,0%)

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Vigenère'i šiffer: leia võtme pikkus ja murra kood

Vigenère'i šiffer liidab sõnumile täht-tähelt korduva võtme. Kui A = 0 kuni Z = 25, on salateksti täht i arvutatav valemiga (sõnumi täht i + võtmetäht i mod L) mod 26, mis tähendab, et iga võtmetäht teeb igale L-ndale tähele Caesari nihke. N tähe kokkulangevusindeks IC = Σ n(n − 1) / (N(N − 1)) väljendab tõenäosust, et kaks eri kohtadest võetud tähte langevad kokku: juhuslike tähtede puhul on see 1/26 = 0,0385, inglise keeles ligikaudu 0,066. Friedmani testis kirjutatakse salatekst k-kaupa ridadesse ja loendatakse kokkulangevusi veergude kaupa: võtmepikkuse ja selle kordsete korral käitub iga veerg nihutatud inglise keelena ning selle IC tõuseb taas inglise keele tasemele. 1863. aastal avaldatud Kasiski test tegurdab korduvate täherühmade vahekaugusi.

Mida iga sümbol tähendab

L: tähtede arv võtmes
k: katsetatav võtme pikkus: veergude arv, millesse salatekst jaotatakse
N: tähtede arv sõnumis
n: IC valemis ühe tähe esinemiskordade arv

Eeldab: Vaid tähed: suurtähed, tühikud ja kirjavahemärgid jäetakse enne šifreerimist kõrvale, täpselt nagu Carrolli kaardil. „Inglise keel“ tähistab siin teose „Alice Imedemaal“ I peatükki (8 606 tähte); selle tähesagedused ja IC väärtus 0,0665 on iga testi etaloniks. Tulemuslikkust mõõtvad katsed võtavad sõnumeid samast peatükist, mis rünnaku edukust pisut soosib. Võtme pikkuseks loetakse väikseim k, mille veergude keskmine IC jõuab vähemalt kolm neljandikku teest väärtusest 1/26 inglise keeleni. Juhuslikud võtmed valivad iga tähe ühtlase jaotusega, mistõttu võivad tähed korduda. Kui võtme muster kordub poolel pikkusel, võib see tõsta vastava poole pikkuse tulba üle otsustusjoone.

Tulbad ulatuvad keskmiselt gcd(k, L)/L võrra inglise keele poole 🖖

Vajuta RABBIT, 600 tähte ja jälgi tulpi. Kui salatekst jagada k veergu, seguneb igas veerus L/gcd(k, L) võtmetähe tähestik. Keskmiselt säilib seal gcd(k, L)/L juhuslike tähtede ja inglise keele vahelisest vahemikust. RABBIT-i kuue tähe puhul viib see tulbad 6, 12 ja 18 tippu ning 3, 9 ja 15 poolele kõrgusele. Teised paarisarvulised k väärtused jäävad kolmandiku ja ülejäänud kuuendiku peale; siinsed tulbad maanduvad vahemikesse 98–106%, 42–52%, 26–37% ja 9–23%. Tulp 1 hõlmab kogu salateksti, mistõttu jätab kümnetäheline võti tähtede sagedustesse keskmiselt alles kümnendiku inglise keele omapärast, samas kui iga kümnes täht on endiselt puhas inglise keel. Katsetades seda 100 juhusliku võtmega igast pikkusest 1 kuni 12, jäävad kõik kakskümmend tulpa 3% piiresse sellest, kuhu suhe gcd(k, L)/L nad asetab. Friedmani 1935. aasta kokkulangevusindeksi uurimus toob välja mõlemad äärmused: õige perioodi korral 0,066 ja vale puhul 0,038. Selle peatüki tegelik väärtus on 0,0665 ning 1/26 on 0,0385. Otsustusjoon asub kolme neljandiku kõrgusel seetõttu, et tulp kohal L/2 jõuab keskmiselt umbes poolele teele, lühikeste veergude korral pisut allapoolegi.

Iga võtmetäht on veel üks alistatav Caesari šiffer 🖖

Vajuta Kaheteisttäheline võti. Pikkus on leitud ja igaüks kaheteistkümnest veerust kujutab endast nüüd 18-tähelist Caesari šifrit, mille murdmiseks proovitakse kõiki 26 nihet peatüki tähesageduste vastu. Üksteist veergu annavad õige tulemuse. 5. veerus leidub vaid kaks E-d ja kolm R-i ning nihe, mis muudab iga R-i E-ks, sobitub inglise keelega pisut paremini kui tegelik võti. Üksik 30-täheline veerg laheneb õigesti 98% juhtudest, ent võtme taastamiseks peab õnnestuma iga veerg: selle peatüki 2 000 tekstilõigu põhjal (30 tähte veerus) osutusid kõik kaksteist veergu korraga õigeks vaid 81% kordadest. Iga veerg kordab eelmist Caesari rünnakut ja pikk võti kasvatab eksimisvõimalusi. Viietäheliste sammudega testides saavutab kaheteisttäheline võti 99% kindluse alles 55 tähe juures veerus, mis teeb kokku 660 tähte. Ja see kehtib alles siis, kui pikkus on juba käes. Tulpade test ise vajab lühikese võtme puhul rohkem teksti, sest keskmistada saab vähemate veergude üle: 60 tähe juures veerus taastab rünnak ühetähelise võtme umbes 87% juhtudest, kaheteisttähelise aga enam kui 99% tõenäosusega.

Sõnumipikkune võti jätab alles vaid E 🖖

Vajuta Sõnumipikkune võti ja liigu lõpuni. Kakskümmend tähte kahekümne võtmetähe all jätab igasse veergu üheainsa tähe. Kuna paare pole, puudub tulp 20 ning üksiku tähe hii-ruut saab eelistada vaid nihet, mis teeb sellest peatüki sagedaseima tähe E. Iga veerg annab vasteks E ning lahendus osutub õigeks kahel korral, fraasi „Alice was beginning to g“ kahe E kohal. Terves peatükis moodustab E 8 606 tähest 1 078 ehk 12,5%, ning ühe tähega veerus tabab rünnak tekstilõikudel 12,6%: täpselt seda, mida ta inglise keele kohta juba teadis, õppimata salatekstist vähimatki. Kui need kakskümmend võtmetähte valitakse täiesti juhuslikult ja neid ei kasutata enam kunagi, sobib iga kahekümnetäheline sõnum nende kahekümne salateksti tähega võrdselt hästi. See ongi ühekordne šiffer.

Ülesanne täielikult lahendatud

Kas Carrolli šifrikaardil oli õigus? 4 sammu
Lewis Carroll laskis trükkida šifrit selgitava kaardi. See on dateerimata, kuid tema kirjad märksõna saatmise kohta pärinevad 1868. aasta aprillist, viis aastat pärast Kasiski raamatu ilmumist. Kaardil šifreeritakse lause „meet me on Tuesday evening at seven“ märksõnaga vigilance ning lubatakse, et märksõnata on teadet võimatu dešifreerida isegi tabeli abil. Vajuta Carrolli kaart: kas leht suudab tema sõnumi lahti lugeda? Seejärel šifreeri sama märksõnaga I peatüki algus. Mitu tähte vajab leht, et tuletada tagasi VIGILANCE?

Ava see ülesanne tööriistas
1. Kontrollime ühte tähte käsitsi. m on 12 ja v on 21; 12 + 21 = 33 ning 33 − 26 = 7, mis annab tähe h. Lehel kuvatav salatekst HMKBXEBPXPMYLLYRXIIQTOLTFGZZV kattub Carrolli omaga täht-tähelt.
  
  $m + v = 12 + 21 = 33 \equiv 7 = h (mod 26)$
2. 29 tähte 9 veerus annab kaks 4-tähelist ja seitse 3-tähelist veergu. Ükski kolmetäheline rühm ei kordu, seega pole Kasiskil midagi tegurdada. Ükski tulp ei küüni jooneni (0,0595); kõrgeim on k = 9 väärtusega 0,0556, mistõttu võtmepikkus määratakse õigesti. Kolme või nelja tähe pealt arvutatud hii-ruut on aga sisuliselt huupi pakkumine: võtmeks leitakse HIGXXLNPM, kus selle 9 tähest on õiged 3 ning sõnumi 29 tähest 10.
  
  $29 = 9 \times 3 + 2 : columns of 4, 4, 3, 3, 3, 3, 3, 3, 3; \overline{IC}_{9} = 0.0556 < 0.0595$
3. Vajuta VIGILANCE, 189 tähte: peatüki algus Carrolli märksõnaga, 21 tähte igas veerus. Tulp 9 ületab esimesena joone väärtusega 0,0794 ning korduvate rühmade 5 vahekaugusest 4 on arvu 9 kordsed (54, 36, 27 ja 72; viies on 29). Kõik üheksa veergu annavad õige tulemuse, nagu ka kõik 189 sõnumitähte.
  
  $189 = 9 \times 21 : \overline{IC}_{9} = 0.0794 \geq 0.0595; 54, 36, 27, 72 divisible by 9, 29 not$
4. Määra tähtede arvuks 188. Võtme pikkus on endiselt 9, kuid 9. veerus on nüüd 20 tähte ning sinna sobib paremini T kui E: 188 tähest taastatakse 168. Just 189. täht langeb 9. veergu ja kallutab tulemuse E kasuks.
  
  $188 = 8 \times 21 + 20 : column 9 reads T, \frac{168}{188}$
Vastus

Siinsel lehel jääb Carrolli enda sõnum murdmatuks, Alice'i 189 tähte aga mitte. Kolm või neli tähte veerus on analüüsiks liiga vähe ja võtmeks tuleb HIGXXLNPM; 21 tähest veerus piisab, et VIGILANCE välja lugeda. Carrolli sõnumit kaitses eelkõige selle lühidus. Kas keegi, kes arvanuks ära mõne sõna (näiteks „Tuesday“), suutnuks lugeda ka ülejäänu, seda siinne leht ei kontrolli: see loendab üksnes tähti.

$29 letters: 10 right; 189 letters: VIGILANCE$

Õpitee

Kuidas koode murtakse

Allikad (3)

The two ends of the bar chart in the first insight (.066 for a correct period, .038 for a wrong one), and the method itself: write the ciphertext in lines of the assumed period and count coincidences down the columns, for each assumption in turn: William F. Friedman, "The Index of Coincidence and Its Applications in Cryptanalysis," Technical Paper, War Department, Office of the Chief Signal Officer. Washington: Government Printing Office, 1935. A 1923 revision of the paper of the same title published in 1922 by the Riverbank Laboratories. p. 11.
Kasiski's 1863 book and what his method does (repetitions, their spacings factored, the key length, then letter frequencies), in the lesson's definition: David Kahn, "Kasiski, Friedrich W.," in Neue Deutsche Biographie 11 (1977), pp. 317 f.
Carroll's Alphabet-Cipher card, its example (vigilance, 'meet me on Tuesday evening at seven', the ciphertext the page reproduces) and its promise, in the worked problem; the April 1868 letters about a key-word: Lewis Carroll (C. L. Dodgson), "The Alphabet-Cipher," printed card, undated (c. 1868). Images of both sides and an account of the letters at Lewis Carroll Resources, "Ciphers."

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.