Pakaitinis šifras: apibrėžimas, pavyzdžiai (Cezario) ir dažnių analizė

Pakaitinis šifras yra kriptografijos rūšis.

Pakaitiniame šifre kiekviena pranešimo raidė keičiama pagal taisyklę. Taisyklėje sakoma, kad kiekvieną raidę reikia pakeisti (arba "pakeisti") kita abėcėlės raide.

Pavyzdžiui, šioje lentelėje pateikiama pakeitimo šifro taisyklė:

Pagal šią taisyklę sakinys "Džekas ir Džilė ėjo į kalną" pakeičiamas į "Etar tzn Evmm gkzc dw cuk uvmm". Cezario šifras yra vienas iš pakeitimo šifro pavyzdžių.

Pakaitiniai šifrai nėra pakankamai saugūs, kad juos būtų galima naudoti svarbiems pranešimams. Pakaitinius šifrus galima nulaužti taikant dažnių analize vadinamą idėją. Kai kurios raidės anglų kalbos sakiniuose pasitaiko dažniau nei kitos: E yra dažniausia, tada T, tada A ir taip toliau. Pranešime, kuris buvo pakeistas pakeitimo šifru, bus kitokių bendrinių raidžių, tačiau tai duoda užuominą apie taisyklę. Tikėtina, kad pakeistame pranešime dažniausios raidės bus dažniausios raidės anglų kalboje. Kriptogramų (pakeitimo šifru paslėptų pranešimų) laužymas yra įprastas galvosūkis, dažnai sutinkamas laikraščiuose.

Kaip veikia pakaitinis šifras — papildomi paaiškinimai

Pakaitinis šifras priskiriamas simetriniams šiframs, nes taisyklė (raktas) yra vienoda tiek šifravimo, tiek iššifravimo metu. Paprasčiausias pakaitinis šifras vadinamas vienkartiniu arba tiesioginiu pakeitimu: kiekviena aiškiojo teksto raidė visada pakeičiama ta pačia užšifruota raide. Yra ir sudėtingesnių variantų:

Vieno abėcėlės pakeitimas (simple substitution) — kiekviena raidė pakeičiama kita, bet visur ta pati taisyklė.
Homofoninis pakeitimas — dažnoms raidėms priskiriama daugiau užšifruotų simbolių, kad būtų išlyginti dažniai.
Polialfabetinis pakeitimas — naudojami keli pakeitimo raktai (pvz., Vigenère šifras), todėl ta pati aiškiojo teksto raidė kartais pavirsta skirtingomis raidėmis.

Cezario šifras — paprastas pavyzdys

Cezario šifras yra klasikinis pakaitinio šifro pavyzdys. Jis veikia kaip abėcėlės poslinkis: kiekvieną raidę pakeičiame raide, esančia tam tikru skaičiumi pozicijų toliau abėcėlėje. Pavyzdžiui, su poslinkiu 3 (tai buvo Julijaus Cezario naudojamas poslinkis) abėcėlė A→D, B→E, C→F ir t. t.

Pavyzdys su anglų/lotyniška abėcėle (26 raidės): aiškus tekstas "HELLO" po poslinkio 3 tampa "KHOOR". Panašiai lietuvišką žodį "LABAS" (naudojant bazinę lotynišką abėcėlę) su poslinkiu 3 galima užšifruoti taip: L→O, A→D, B→E, A→D, S→V — gauname "ODEDV".

Cezario šifras yra labai paprastas ir greitai sulaužomas, bet jis dažnai naudojamas kaip mokomasis pavyzdys ar galvosūkis.

Dažnių analizė ir kaip nulaužti pakaitinius šifrus

Dažnių analizė remiasi tuo, kad skirtingos raidės tekste pasitaiko nevienodai. Kaip taisyklė:

Skaičiuojama, kurios užšifruoto teksto raidės pasirodo dažniausiai.
Dažniausios užšifruoto teksto raidės bandomos priskirti dažniausioms raidėms natūralioje kalboje (pvz., anglų E, T, A; lietuvių kalboje dažniausios raidės yra šiek tiek kitokios — A, I, S, E ir pan.).
Taip gaunami pradiniai spėjimai, kuriuos patikrinus pagal trumpus žodžius, pasikartojančius raštus ir kontekstą galima palaipsniui ištaisyti ir gauti aiškų tekstą.

Be vienoračių raidžių dažno analizė naudoja ir dviračius/triračius (digrams, trigrams) – populiarias raidžių poras ar tripletus, pvz., anglų "TH", "HE", "IN". Taip pat svarbi žodžių struktūra: vienaračiai žodžiai, pasikartojantys žodžiai, raidžių pasikartojimų modeliai (pvz., 3 raidžių žodai, kurių pirmos ir paskutinės yra tokios pačios) duoda užuominų.

Praktiniai patarimai ir apribojimai

Dažnių analizė gerai veikia ilgiems tekstams. Trumpas pranešimas gali būti nelaužiamas vien tik pagal dažnius, todėl reikia naudoti papildomas užuominas (kontekstas, žinomų frazių paieška).
Kalba turi reikšmės: raidžių pasiskirstymas skiriasi tarp kalbų — taigi analizuokite pagal atitinkamos kalbos statistikas.
Kompiuteriai labai pagreitina laužymą: automatizuotos programos išbando sutapimus tarp dažnių, modelių ir žodynų įrašų.
Norint padaryti pakaitinį šifrą saugesnį, istorijoje naudoti polialfabetiniai metodai (pvz., Vigenère) arba homofoniniai pakaitalai; tačiau šiuolaikinė kriptografija remiasi visiškai kitokiais algoritmais, kurie nepasikliauja tik paprastu pakeitimu.

Apibendrinant: pakaitinis šifras yra paprasta ir aiški šifravimo idėja — viena raidė pakeičiama kita pagal raktą. Tai puikus įvadas į kriptografiją ir loginius galvosūkius, bet nepakankamai saugus rimtai informacijai. Dažnių analizė suteikia veiksmingą įrankį šiems šiframs sulaužyti, ypač turint ilgą tekstą ir žinant kalbą.

Pavyzdys

Tarkime, kad pakeistas pranešimas yra:

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM WQLMGLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMXXLIYSPH KTY

Šiame pavyzdyje didžiosiomis raidėmis žymimos nežinomos raidės, o mažosiomis raidėmis - žinomos arba numanomos raidės.

Suskaičiavę raides matome, kad dažniausiai pasitaikanti yra I, kuri, kaip spėjame, yra e. X taip pat gana dažna, o XLI randama daug kartų; spėjame, kad tai dažniausia trijų raidžių grupė anglų kalboje.

E yra antra pagal dažnumą raidė. Jau turime spėjimą apie e ir t, todėl spėjame, kad E yra a. Dabar turime:

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM . WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMttheYSPH KTY

Dabar galime padaryti dar keletą spėjimų: heVe gali būti čia; Rtate gali būti valstybė, o atthattMZe gali būti atthattime. Užpildę šiuos spėjimus, gausime:

čiaTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei . WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYittheYSPH KTY

Tai leidžia mums daryti daugiau spėjimų, o šie - dar daugiau, kol atspėjame viską:

čiapagallegrandosgrožįsugraviruirstatybineatstovybeirprisivežėbukąišstiklinėsvitrinos,įkuriąjisbuvouždarytas,irtuometnebuvožinomasnatūralistai,žinoma,irpagalmokslinįpavyzdį,irbuvopasakyta,kadkiekvienasnuoextr. emitavimopagalgūbrįirpagalkitąpagalgūbrįbuvopaprastaitvirtasirblizgantis,ožmogusbuvopaprastaipaprastas,oatsižvelgiantįvisusaplinkybes,vargu argalėtųbūtikaltinamasJupiteris,kadjispagalvojoapiežmogų,kadjisbuvopasakėapie auksinį vabalą

Šiuo metu galime įterpti tarpus ir skyrybos ženklus:

Čia le grand pakilo rimtai ir didingai ir atnešė man vabalą iš
stiklinės vitrinos, kurioje jis buvo uždarytas. Tai buvo gražus skarabėjus, tuo metu
gamtininkams, žinoma, nežinomas vabalas; moksliniu požiūriu tai buvo didelis prizas
. Prie vieno nugaros galo buvo
dvi apvalios juodos dėmės, o
prie kito - ilga. Žvyneliai buvo nepaprastai kieti ir blizgantys,
atrodė kaip išpuoselėto aukso. Vabzdžio svoris buvo labai įspūdingas,
ir, atsižvelgdamas į viską, vargu ar galėčiau kaltinti Jupiterį dėl
jo nuomonės apie vabzdį. (Auksinis vabalas)

Jei būtume neteisingai atspėję, kažkuriuo metu būtume tai sužinoję ir galėtume grįžti atgal bei atlikti naują spėjimą.

Klausimai ir atsakymai

K: Kas yra pakaitinis šifras?

A: Pakeitimo šifras yra kriptografijos rūšis, kai kiekviena pranešimo raidė pakeičiama kita abėcėlės raide.

K: Kaip veikia pakeitimo šifras?

A: Pakaitiniame šifre kiekviena pranešimo raidė pakeičiama kita abėcėlės raide po vieną.

K: Koks yra pakeitimo šifre naudojamos lentelės pavyzdys?

Atsakymas: Tekste pateiktoje lentelėje nurodyta pakeitimo šifro taisyklė, kuri gali būti naudojama kiekvienai raidei pakeisti kita abėcėlės raide.

K: Kas yra Cezario šifras?

A: Cezario šifras yra pakeitimo šifro pavyzdys.

K: Ar pakaitiniai šifrai yra pakankamai saugūs svarbiems pranešimams?

Atsakymas: Ne, pakaitiniai šifrai nėra pakankamai saugūs, kad juos būtų galima naudoti svarbiems pranešimams.

K: Kaip galima nulaužti pakaitinius šifrus?

A: Pakaitinius šifrus galima išlaužti naudojant dažnių analizę, kurios metu ieškoma bendrų raidžių pakeistame pranešime, kurios gali būti dažniausios raidės anglų kalboje.

K: Koks yra įprastas galvosūkis, susijęs su šifrų laužymu?

A: Kriptogramų, t. y. pranešimų, paslėptų pakeitimo šifru, laužymas yra įprastas galvosūkis, dažnai sutinkamas laikraščiuose.