Asendusšifrid: 26! võtit, murtud tähtede loendamisega

Üks lõik Sherlock Holmesi jutust on pandud salajase võtmega koodi. Caesari nihke puhul proovi läbi kõik 25 võtit ning jälgi igaühe hii-ruudu tulpa. Täieliku asenduse korral sea krüptoteksti sagedamad tähed paari inglise keele omadega ja täpsusta seoseid väljatulevate sõnade abil.

Näidisarvutus — Asendusšifrid: 26! võtit, murtud tähtede loendamisega

Võimalikke võtmeid	25
Tähti teates	120
Analüüsi tulemus, madalaim χ²	23,3
Järgmine madalaim	445,8
Kas see on õige võti?	Jah
Õige 20 000 juhusliku 120-tähelise teate seas	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 — Asendusšifrid: 26! võtit, murtud tähtede loendamisega

Asendusšiffer asendab sõnumi iga tähe vastavalt võtmele kindla teise tähega. Võti kujutab endast tähestiku ümberjärjestust, mis annab 26! ≈ 4,03 × 10²⁶ võimalikku võtit. Caesari šiffer on selle erijuht, mis nihutab kõiki tähti tähestikus edasi sama arvu kohtade võrra, jättes alles 25 võtit. Sagedusanalüüs murrab mõlemat šifrit, võrreldes krüptoteksti tähtede esinemissagedust tavalise teksti omaga.

Mida iga sümbol tähendab

χ²: hii-ruut: kõigi 26 tähe peale arvutatud summa (O − E)² / E. Mida väiksem see on, seda enam sarnanevad dešifreeringu sagedused inglise keelele
O: mitu korda täht esineb hinnatavas dešifreeringus
E: mitu korda täht esineks sama pikas tekstis jutu „Karglevad mehed“ tähesageduste järgi

Eeldab: Šifreeritakse ainult 26 tähte. Tühikud ja kirjavahemärgid jäävad oma kohale, reedates iga sõna pikkuse; täpselt samamoodi tegid karglevad mehikesed oma lippudega. „Inglise keel“ tähendab siin ühe Holmesi jutu 39 859 tähe sagedusi. Kuna lehe enda näidislõigud pärinevad teisest jutust, ei hinnata ühtegi teksti tema enda põhjal. Katsed võtavad jutu „Üksik jalgrattur“ juhusliku lõigu ja fikseeritud algväärtusega generaatori juhusliku võtme, nii et igal katsel tulevad välja täpselt samad arvud.

Kõiki 25 võtit on lihtne läbi proovida; õige eristamiseks kulub umbes 30 tähte 🖖

Caesari nihkel on 25 võimalikku võtit, mida kõiki jõuab katsetada käsitsi. Vaev seisneb otsustamises, milline tulemus on tegelikult inglise keel. Selle töö usaldab leht Pearsoni hii-ruudule: valem summeerib täht-tähelt, kui kaugele jäävad lahenduse tähesagedused sellest, mida jutustus „Karglevad mehed“ sama pika teksti kohta ennustab. Ühe teise Holmesi jutu 20 000 juhusliku lõigu põhjal annab madalaim tulemus õige võtme 12 tähe korral 85,0% ning 31 tähe korral 99,1% kordadest. Klõpsa nupule Caesar, 11 tähte, et näha eksimust: nihe 7 saab õigest võtmest parema skoori ja annab lauseks dan reoep swo – inimene lükkaks sellise pudikeele pikemata tagasi, ent valemil puudub selleks taip.

Loendamine leiab tähe e ja peaaegu mitte midagi muud 🖖

Kui seada tähed sagedusjärjestusse 600-tähelises teates, satub täht e õigele kohale 96,5% juhtudest 400 juhusliku katse seas. Järgmised tähed on sageduselt liiga tasavägised, et nende pingerida lühikeses tekstis püsima jääks. Loos „Karglevad mehed“ jäävad a, o, i, n, h ja s kõik vahemikku 6,3% kuni 8,0%, mistõttu lööb juba paari tähe juhuslik lisandumine korra sassi. Kui seada sageduse järgi ritta kõik tähed, läheb 23,5 esinevast tähest täppi keskmiselt 6,3 ehk vaid kolmandik tekstist. Holmes tõdes sealsamas jutus sedasama: „Inglise keele tähtede järjestus pärast E-d pole sugugi selgepiiriline ning ülekaal, mis avaldub terve trükipoogna keskmises, võib ühes lühikeses lauses hoopis vastupidiseks pöörduda.“ Nõnda jäi ta ootama uusi teateid ja asus lugema terviksõnu.

Terve jutu pikkune krüptotekst jätab ikkagi viis tähte valeks 🖖

Pikem krüptotekst küll tasandab sagedusi, ent need koonduvad loetava teose enda eripärade ümber, ja isegi sama autori kaks juttu ei kattu kunagi täielikult. Klõpsa nupule Asendus, terve jutt: kõik 32 725 tähte loost „Üksik jalgrattur“, seatuna jutu „Karglevad mehed“ sageduste järgi, viivad õigele kohale 21 tähte ja panevad viiega mööda (h, i, n, f ja y). Tulemusena on õige 76,1% tekstist. „Üksik jalgrattur“ kasutab h-tähte (6,69%) karvavõrra sagedamini kui i-d (6,67%) ja n-i (6,34%), samas kui „Karglevates meestes“ edestavad i ja n kindlalt h-d. Holmes peab õigeks järjestust T, A, O, I, N, S, H, R, D, L – kuigi jutus, kus ta seda lausub, esineb H hoopis sagedamini kui S.

Ülesanne täielikult lahendatud

Kus loendamine lõpeb ja algab lugemine 4 sammu
Klõpsa nupule Asendus, 600 tähte. Kui kaua kuluks arvutil kõigi võtmete läbiproovimiseks, kui see katsetab miljard võtit sekundis? Seejärel murra sõnum: mida annavad sagedused ja mida sagedamad sõnad?

Ava see ülesanne tööriistas
1. Võtmeid on 26! = 403 291 461 126 605 635 584 000 000 ehk ligikaudu 4,03 × 10²⁶. Kiirusel 10⁹ võtit sekundis kulub 4,03 × 10¹⁷ sekundit. Kuna aastas on 3,16 × 10⁷ sekundit, teeb see 1,28 × 10¹⁰ aastat ehk 12,8 miljardit aastat.
  
  $26! = 403291461126605635584000000 \approx 4.03 \times 1 0^{26}, \frac{4.03 \times 1 0 ^{26}}{1 0 ^{9} \times 3.16 \times 1 0 ^{7}} = 1.28 \times 1 0^{10} years$
2. Krüptoteksti sagedaseim täht on I: 80 korda 600-st ehk 13,3%. Jutus „Karglevad mehed“ on tähe e osakaal 12,44%, seega vastab I tähele e. Järgmised kolm, O, N ja X, esinevad 49, 47 ja 45 korda – need vahed on kindla järjekorra määramiseks liiga napid, ja sagedus seob need tähtedega t, a ja o, mis lähevad kõik kolm valesti. Tulemuste tabel näitab sellise pimesi järjestamise hinda: ainuüksi sageduse põhjal läheb täppi 3 tähte 23-st ehk 14,2% tekstist.
  
  $\frac{80}{600} = 13.3% \approx 12.44% : I \to e, 49, 47, 45 for O, N, X$
3. Nüüd sõnade juurde. Kolmetähelised sõnad OBJ ja XDI esinevad kumbki viis korda. Sõna XDI lõpeb tähega I, mis on e: järelikult the, kust X on t ja D on h. OBJ on seepeale suure tõenäosusega and: O on a, B on n ja J on d. Kõige sagedam kahetäheline sõna PK esineb kaheksa korda ja sobib vasteks sõnale of; viis korda esinev XP annab seejärel kuju to, mis kinnitab valikut.
  
  $XDI \to t h e, OBJ \to an d, PK \to o f, XP \to t o$
4. Kirjuta need kaheksa tähte lahtritesse. Tähed e, t, h, a, n, d, o ja f katavad 600 tähest 321 ehk 53,5%, ning esimene rida loeb f·o· the ·ea·· 1894 to 1901. Sagedustel pole siit enam midagi anda. Aastaarvu ees on f·o· peaaegu kindlasti from, mis annab tähed r ja m. Sealt edasi on juba puhtalt lugemise vaev.
  
  $\frac{321}{600} = 53.5% of the message from 8 letters$
Vastus

12,8 miljardit aastat, et proovida läbi iga võti. Loendamine annab kätte üheainsa tähe, e; kolm sagedast sõna toovad juurde veel seitse, ja need kaheksa tähte dešifreerivad juba 53,5% sõnumist.

$1.28 \times 1 0^{10} years; 8 letters \to 53.5%$

Õpitee

Kuidas koode murtakse

Allikad (1)

Both passages the page counts, and Holmes's words quoted in the second and third insights: Arthur Conan Doyle, "The Adventure of the Dancing Men" and "The Adventure of the Solitary Cyclist," in The Return of Sherlock Holmes. Project Gutenberg eBook #108.

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