Ühekordne šifriplokk: korra murdmatu, kahel korral murtav

Tee sõnumi iga baidiga juhuslikule võtmebaidile XOR-tehe ja krüptogramm ei reeda vastasele midagi. Kasuta sama võtit kahel sõnumil ning võti kaob sealt sootuks: arva ära üksainus sõna, libista seda edasi ja loe teine sõnum alt välja.

Näidisarvutus — Ühekordne šifriplokk: korra murdmatu, kahel korral murtav

Märkide arv	14
Võimalikke võtmeid	5,2 × 10³³
Võimalikke sõnumeid	1,1 × 10²⁰
Võti tekstini „retreat at ten“	11 1e fa a1 83 6d 23 7c 98 ee 06 32 d1 84

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

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Ühekordne šifriplokk: korra murdmatu, kahel korral murtav

Ühekordne šifriplokk seob sõnumi iga märgi juhuslikult valitud võtmemärgiga, mida kasutatakse vaid selle ainsa märgi jaoks ja mitte kunagi uuesti. Siin rakendatakse baithaaval bitikaupa välistavat või-tehet: C = P ⊕ K, ning dekrüpteerimine on täpselt sama tehe: P = C ⊕ K. Kui juhuslik võti on sama pikk kui sõnum, tagab šiffer täiusliku salastuse: krüptogrammi nägemine ei anna vähimatki teavet selle kohta, milline sõnum tegelikult saadeti. Kui aga sama võtit kasutatakse kahel sõnumil, taandub võti välja: C₁ ⊕ C₂ = P₁ ⊕ P₂. Meetod nimega spikri libistamine liigutab arvatavat sõna w piki seda tulemust: kus iganes üks sõnum sisaldabki sõna w, seal annab w ⊕ C₁ ⊕ C₂ teise sõnumi teksti.

Mida iga sümbol tähendab

P: sõnum, üks bait märgi kohta
K: võti: juhuslikud baidid, täpselt sama palju kui sõnumis märke
C: krüptogramm, P ⊕ K
⊕: välistav või: tulemuse iga bitt on 1 seal, kus kaks vastavat bitti erinevad
w: spikker: sõna, mida oletatakse leiduvat ühes sõnumitest

Eeldab: Sõnumid koosnevad väiketähtedest ja tühikutest, mis on salvestatud ASCII-baitidena. Võtmebaidid pärinevad juhuarvugeneraatorist, mille seemneks on 32-bitine arv. Seetõttu suudab veebileht luua vaid 2³² ≈ 4,3 × 10⁹ võtit; alates seitsmest märgist on see juba vähem kui võimalikke sõnumeid, mistõttu pole lehe enda šifriplokk Shannoni kriteeriumi järgi täiuslikult salastatud. Ehtne šifriplokk nõuab baite, mida mitte keegi ei saa uuesti genereerida. Katke „meenutab teksti“, kui selle iga bait on täht või tühik ning iga kolmetäheline lõik esineb Edgar Allan Poe jutu „Kuldmardikas“ (1843) kahes esimeses kolmandikus; mõõdetud paarid pärinevad teose viimasest kolmandikust. Tähtede liitmisele mooduli 26 järgi eelistatakse XOR-tehet seetõttu, et XOR-il puudub märk: saadav katke on täpselt sama sõltumata sellest, kummas sõnumis spikker asub.

Kõiki võtmeid läbi proovides leiab iga võimaliku sõnumi 🖖

Keri sammhaaval läbi Rünnak koidikul ja silmitse kahte alumist rida. Seal seisab võti, mis teisendaks selsamal kujul krüptogrammi teateks „retreat at ten“. Trüki teise kasti mistahes muud 14 tähte ja tühikut: otsekohe ilmub võti ka tolle teate tarvis. XOR pöörab nimelt iseennast tagasi, sest krüptogrammi ja sinu sõnumi XOR-tehe annabki vajaliku võtme. Nii ei jõua vastane, kes proovib läbi kõik 256¹⁴ võtit, sugugi ainsa õige sõnumini. Ta saab kätte eranditult kõik 27¹⁴ ≈ 1,1 × 10²⁰ selle pikkusega sõnet, kus igaüks vastab täpselt ühele võtmele. Kuna iga võti oli algselt võrdtõenäoline, ei muutnud vaheltlõikamine ühtegi neist variandist põrmugi usutavamaks kui enne. Shannon nimetas seda 1949. aastal täiuslikuks salastuseks ja tõestas ka selle vääramatu hinna: võimalikke võtmeid peab olema vähemalt sama palju kui võimalikke sõnumeid. Korduva võtmega Vigenère'i šifril on võtmeid hoopis napimalt, mistõttu saab selle sagedusanalüüsiga lahti harutada.

Tühikud paistavad välja juba enne esimestki oletust 🖖

Klõpsa Kus on tühikud. Võti on välja taandunud: C₁ ⊕ C₂ on baithaaval puhas P₁ ⊕ P₂ ning võtmest pole järel kriipsugi. Vaata nüüd siniseid baite, mida on 50-st 19. Väiketähe kood jääb vahemikku 0x61 kuni 0x7a ja tühik on 0x20. Biti 0x40 seab üheks üksnes tähe ja tühiku omavaheline XOR. Seepärast tähistab iga bait väärtusega 64 või enam kohta, kus täpselt ühes kahest sõnumist on tühik. Sõnavahed paistavad kätte enne, kui keegi jõuab ainsatki sõna oletada, kuigi pole veel teada, kummas tekstis tühik asub. Enam kui 2 000 paari Poe jutu „Kuldmardikas“ 60-märgiliste lõikude võrdluses paljastub selline tühik ligikaudu 30% positsioonidest. Nõukogude diplomaatiline ja luureside, mida Meredith Gardner hakkas 1946. aastal USA projekti Venona raames lahti muukima, liitis koodirühmadele võtmenumbreid, mitte ei kasutanud baitide XOR-tehet, ent ühe krüptogrammi lahutamine teisest kaotab ühise võtme täpselt samamoodi. Võtit oli taaskasutatud eksikombel: Saksa vägede pealetungil Moskva all trükkis KGB koodiraamatuid valmistanud trükikoda umbes 35 000 lehekülge korduvat võtit.

Suurima töö teevad ära kaks tühikut spikri otstes 🖖

Klõpsa Ilma tühikuteta. Sõna „the“ positsioonil 26 annab vasteks „org“, pelgalt tähed, mille iga kolmik esineb etalonteksis, ometi pole kummaski sõnumis seal seda sõna. Paneme tühikud tagasi: „ the “. Nüüd läbivad selle paari puhul kontrolli üksnes tõelised tabamused. Kui võrrelda enam kui 2 000 paari 60-märgilisi lõike jutu „Kuldmardikas“ viimasest kolmandikust, mida etaloni koostamisel ei kasutatud, läbis „ the “ kontrolli 3 661 positsioonil ning leidus seal tegelikult 3 281 korral ehk ligikaudu 9 juhul 10-st. Ilma tühikuteta „the“ läbis kontrolli 9 615 positsioonil, ent pidas paika vaid 4 169 korral — vähem kui pooltel juhtudel. Põhjus peitub sinistes baitides. Spikri tühik annab tähe ainult baidi 64 või enama kohal ning tühiku üksnes väärtuse 0 kohal; mistahes muu arvu puhul tekib bait, mis pole üldse täht. Niisiis peab spikri iga tühik langema kohale, kus ühes sõnumis ongi sõnavahe, ja vale positsioon klapib harva kahe tühikuga korraga.

Ülesanne täielikult lahendatud

Viis tähte kahest sama võtit jaganud sõnumist 4 sammu
Kaks 50 märgi pikkust sõnumit saadeti välja ühe ja sama ühekordse šifriplokiga. Positsioonidel 32 kuni 36 on C₁ ⊕ C₂ kuueteistkümnendsüsteemis 54 06 09 0c 4e. Oletame, et ühes sõnumis asub seal „ the “ ehk baidid 20 74 68 65 20. Mida ütleb teine sõnum neis viies kohas? Kui see oletus peab paika 2. sõnumi kohta, mille krüptogramm on seal 9d 8e 23 40 9e, siis millised on need viis võtmebaiti? Vajuta seejärel nuppu Näidisülesanne ja tee lehel järgmine samm.

Ava see ülesanne tööriistas
1. Kirjuta esimene paar kahendsüsteemis: 0x54 on 01010100 ja tühik 0x20 on 00100000. XOR annab tulemuseks 1 seal, kus need kaks bitti erinevad; saame 01110100, mis on 0x74 ehk täht t. Baidi 0x54 bitt 0x40 oli juba enne igasugust oletust reetnud, et ühes sõnumis asub positsioonil 32 tühik.
  
  $0x54 \oplus 0x20 = 01010100 \oplus 00100000 = 01110100 = 0x74 = t$
2. Ülejäänud neli: 0x06 ⊕ 0x74 = 0x72, r; 0x09 ⊕ 0x68 = 0x61, a; 0x0c ⊕ 0x65 = 0x69, i; 0x4e ⊕ 0x20 = 0x6e, n. Teises sõnumis seisab seega „train“ ning selle kõik kolm kolmikut, „tra“, „rai“ ja „ain“, esinevad etalonteksis.
  
  $54 06 09 0c 4e \oplus 20 74 68 65 20 = 74 72 61 69 6e = train$
3. Kui „ the “ kuulub 2. sõnumisse, on võtmeks C₂ ⊕ P₂: 0x9d ⊕ 0x20 = 0xbd, 0x8e ⊕ 0x74 = 0xfa, 0x23 ⊕ 0x68 = 0x4b, 0x40 ⊕ 0x65 = 0x25, 0x9e ⊕ 0x20 = 0xbe. Kui oletus oleks käinud hoopis 1. sõnumi kohta, seisaks 2. sõnumis „train“ ning võtmebaidid tuleksid tehtest C₁ ⊕ „ the “. Tulemus C₁ ⊕ C₂ on mõlemal juhul täpselt sama, mistõttu aritmeetika abil pole võimalik kindlaks teha, kumb variant on õige.
  
  $K = C_{2} \oplus P_{2} = 9d 8e 23 40 9e \oplus 20 74 68 65 20 = bd fa 4b 25 be$
4. Lehel on „ the “ kinnitatud 2. sõnumisse positsioonil 32 ning spikrikastis seisab positsioonil 31 „ train “ — oletus, et 1. sõnumi „train“ on omaette sõna. 2. sõnumi vasteks tuleb „y the r“: tähed ja tühikud, kus iga kolmik on etalonteksis juba kohatud. Kui kinnitada see 1. sõnumisse, pikenevad mõlemad read seitsme märgini.
  
  $(C_{1} \oplus C_{2})_{31..37} \oplus 20 74 72 61 69 6e 20 = 59 54 06 09 0c 4e 52 \oplus 20 74 72 61 69 6e 20 = 79 20 74 68 65 20 72$
Vastus

„train“, ning võtmebaidid bd fa 4b 25 be, kui oletus kuulus 2. sõnumile. Tehtes C₁ ⊕ C₂ ei reeda miski, kummas sõnumis asub „ the “, ega hakkagi iial reedama: vaheta need kaks sõnumit tervenisti omavahel ja C₁ ⊕ C₂ jääb täpselt samaks. Järgmine oletus määrab üksnes selle, millised katked kuuluvad samasse sõnumisse. Kuna veebilehele sisestati mõlemad sõnumid, loendab see ka õigesti taastatud märkide arvu. Pealtkuulajal on seevastu ees vaid kaks rida ning otsustus, kas loetav tekst annab mõtte välja.

$train, K_{32..36} = bd fa 4b 25 be$

Õpitee

Kuidas koode murtakse

Allikad (2)

The first insight's perfect secrecy and its cost in keys, and the Vigenère link: C. E. Shannon, "Communication Theory of Secrecy Systems," Bell System Technical Journal 28(4), pp. 656–715, October 1949. §10 "Perfect Secrecy", Theorem 6 (pp. 679–682).
The second insight's Venona history: the additive key, the duplicate pages, Gardner's first message: "VENONA: An Overview," Cryptologic Almanac 50th Anniversary Series, Center for Cryptologic History, National Security Agency. DOCID 3575728, approved for release 2009.

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