Kaip veikia asimetrinė kriptografija arba kaip maišydami spalvas, du nepažįstami žmonės gali slaptai bendrauti visiems matant

Kokia mintis šauna į galvą, išgirdus žodžių junginį „asimetrinė kriptografija“? Turbūt, kad yra ir simetrinė kriptografija. Kalbant supaprastintai, kriptografija yra mokslas apie įvairių pranešimų kodavimą, kad be leidimo niekas jų negalėtų perskaityti, ir – kas ne mažiau svarbu – dekodavimą, kad adresatui siunčiama informacija būtų naudinga. Simetrinėje kriptografijoje užkodavimui ir atkodavimui naudojamas tas pats raktas. Asimetrinėje kriptografijoje užkodavimui naudojamas vienas raktas, o atkodavimui – kitas. Atrodo, kaip taip gali būti – užrakini vienokiu raktu, o atrakini kitokiu, – tačiau būtent tokiu principu paremtas, pavyzdžiui, elektroninės bankininkystės internete saugumas. O ir pastaraisiais metais išgarsėjusios decentralizuotos virtualios kriptovaliutos be asimetrinės asimetrinės kriptografijos neegzistuotų.

Glaustai apie simetrinę kriptografiją

Turbūt visi vaikystėje esame žaidę šnipus ir siųsdavome vienas kitam užkoduotus pranešimus, kodavimui naudodami tokį algoritmą:

1. Parašome norimą užšifruoti frazę, pvz. „kamuoliukas paslėptas krūmuose“.
2. Tada vietoje kiekvienos raidės parašome raidę, kuri stovi abėcėlėje per tris pozicijas už esamos raidės, t.y. raidė „k“ virsta „n“, nes abėcėlės fragmente …y, j, k, l, m, n, o,… „n“ yra per tris pozicijas už „k“.
3. Jei raidė yra arti abėcėlės krašto pvz. raidė „z“, taip, kad išeiname iš abėcėlės ribų, tada vėl pradedame nuo abėcėlės pradžios. Mokslininkai pasakytų, kad naudojame periodines kraštines sąlygas. Šiuo atveju „z“ pastūmus per tris pozicijas, ji taptų „ą“.
4. Tokiu būdu mūsų frazė virsta į „ncpvsojvncu šcuohšūcu ntžpvsuf“.
5. Iš užkoduotos frazės lengva atkurti originalų pranešimą, jei žinome per kiek pozicijų reikia pastumti atgal kiekvieną raidę.

Toks šifravimo algoritmas vadinamas Cezario šifru)

Nors užkoduotas tekstas drastiškai skiriasi nuo originalo, toks šifras lengvai „nulaužiamas“. Lietuvių kalboje žodžiai dažnai baigiasi „s“ raide, ir pažiūrėjus į užkoduotą tekstą, nesunku suprasti, kad „u“ raidė koduotame tekste greičiausiai atitinka originalo raidę „s“. Taip iš karto iššifruojamos ne vien tik visos „s“ raidės, bet ir visas originalus pranešimas. Kaip mūsų užšifravimą pasunkinti? Kiekvienai raidei naudojant skirtingą postūmį! Raidę „a“ užkoduosime, atlikdami postūmį per tris pozicijas (gausime raidę „c“), o, pavyzdžiui, „k“ užkoduosime, atlikdami postūmį per 5 pozicijas (gausime raidę „p“). Dar papildę sąlygą, kad kiekviena raidė koduotame tekste atitiktų tik vieną raidę originale, gausime patobulintą Cezario algoritmą. Panašų šifrą XX amžiaus septintajame ir aštuntajame dešimtmetyje naudojo JAV Kalifornijos valstijoje siautėjęs Zodiaku pasivadinęs serijinis žudikas.

Jis išsiuntė laišką su trimis šifrogramomis (viena iš šifrogramų pavaizduota paveiksliuke) trims vietiniams laikraščiams, ir prižadėjo nužudyti 12 žmonių, jei laikraščiai nepublikuos jo užšifruotų pranešimų. Jau po savaitės po publikavimo, viena šeima iš Salino miesto Kalifornijoje sugebėjo iššifruoti visas tris Zodiako šifrogramas. Nors Zodiakas ir apsunkino šifrą, ištrindamas tarpus iš originalaus pranešimo bei kartais naudodamas skirtingus simbolius tai pačiai raidei užkoduoti, šifras buvo įveiktas, padarius prielaidą, kad tekste bus žodis „kill“, kuriame dvi iš eilės „l“ raidės. Kaip matosi iš paveiksliuko, pirmoje eilutėje eina du iš eilės pusiau užpildyti kvadratukai. Pasinaudojus tokiu spėjimu, kruopelytė po kruopelytės jo pranešimas buvo iššifruotas. Deja, iššifruotas tekstas nepadėjo jo sugauti, o tik parodė, kad jam „ne visi namie“.

O dabar galime pagalvoti, kaip dar labiau patobulinti mūsų šifrą. Iki šiol aptarti pavyzdžiai turėjo akivaizdų trūkumą ‒ jei šifrogramoje dviejuose vietose matome tą patį simbolį, tai galime daryti išvadą, kad originalo tekste šiose vietose irgi bus tas pats atitinkamas simbolis. O ką, jei raides pastumtume vis skirtingai, priklausomai nuo pozicijos originaliame tekste. Dabar jau dvi iš eilės einančios „l“ raidės pavirs nebūtinai tais pačiais simboliais. Postūmių lentelės ilgis bus toks pat, kaip ir pats pranešimas. Be to, postūmiai turi būti atsitiktiniai taip, kad postūmio nebuvimas taip pat dažnai pasitaikytų postūmio lentelėje kaip ir postūmis, pavyzdžiui, per vieną simbolį. Šių dviejų reikalavimų neatitiko, ir dėl to buvo iššifruoti nacistinės Vokietijos kariuomenės Antrojo pasaulinio karo metu naudoti šifrai, sukurti garsiosiomis Enigma šifravimo mašinomis.

Kad geriau suprastume tokį šifravimą, panagrinėkime konkretų pavyzdį. Tarkime, mūsų abėcėlėje (tiek originaliame tekste, tiek užšifruotame) yra tik du simboliai: nulis ir vienetas – bitai. Planuojame užšifruoti ir perduoti dešimties bitų seką. Prieš tai susikuriame raktą ‒ 10-ies bitų seką, kur kiekvienas bitas yra sugeneruotas atsitiktinai, su 1/2 kiekvieno bito reikšmės tikimybe. Pavyzdžiui, toks raktas: [0,0,1,0,1,1,0,1,0,1]. Tarkime, norime užšifruoti pranešimą [1,0,1,1,1,1,0,0,0,1]. Raktas sako, kad dviejų pirmųjų pranešimo simbolių turime nekeisti, o trečią simbolį pastumti per vieną poziciją. Kadangi trečias pranešimo simbolis yra 1, tai jo postūmis per vieną poziciją duos 0, nes naudojame periodines kraštines sąlygas. Taip atrodys užšifruotas tekstas: [1,0,0,1,0,0,0,1,0,0]. Įgudęs informatikas iš karto pasakys, kad mes su dviem sekomis atlikome XOR (“iksor“) loginę operaciją

Dar kartą su raktu atlikę tokią operaciją, atkurtume originalią seką. Toks šifras vadinamas Vernamo Vienkartiniu bloknotu ir tai yra vienintelis iki šiol žinomas šifras, kurio saugumas įrodytas matematiškai! Claude'as Shannon'as savo garsiajame darbe įrodė, kad naudojant raktą tik vienam pranešimui užkoduoti, nėra galimybės ištraukti informaciją apie užkoduotą pranešimą, net jei užkoduoto pranešimo dalis yra iš anksto žinoma. Jei planuojame perduoti daugiau nei vieną pranešimą, rakto perdavimo metu iškarto perduodame tiek skirtingų raktų, kiek pranešimų planuojame siųsti.

Taigi apibendrinant, simetrinėje kriptografijoje šifravimui ir dešifravimui naudojamas tas pats raktas, kuris turi būti perduotas saugiu informacijos kanalu prieš šifravimą. Tokiu metodu „nepažįstami“ kompiuteriai internete bendrauti negali.

Asimetrinė kriptografija

Asimetrinės kriptografijos pradžia galima laikyti 1976 m., kai du JAV mokslininkai Diffie'is ir Hellman'as publikavo savo garsųjį darbą „Naujos kriptografijos kryptys“, kuriame pirmą kartą buvo pasiūlytas, atrodytų sveikam protui prieštaraujantis algoritmas, kaip du nepažįstami žmonės, visiems girdint, gali bendrauti slaptai.

2013 m. vyko teismas tarp kompanijų „TQP Development“ ir „Newegg“. Pirmoji kompanija, spaudoje vadinama patentų troliu, padavė į teismą antrąją už jos patento pažeidimą. 1989 m. pateiktas patentas aprašo asimetrinės kriptografijos algoritmų kombinaciją, kuri tuo metų buvo akivaizdi, bei ne kartą aprašyta kriptografijos vadovėliuose. Į teismą kaip ekspertas liudyti buvo iškviestas pats Whitfield'as Diffie'is. Tarp teisėjo ir Diffie'io įvyko maždaug toks dialogas:

‒ Šiame teismo procese mes daug girdėjome apie asimetrinę kriptografiją. Ar jūs esate su ja susipažinęs?

‒ Taip, esu.

‒ Kaip gerai jūs esate su ja susipažinęs? ‒ teisėjas uždavė patikslinantį klausimą.

‒ Aš ją sukūriau, ‒ atsakė Diffie'is.

Deja, nors Diffie'is ir liudijo prieš patentų trolį, teikdamas, kad jų patentas aprašo tai, kas tuo metu jau buvo ne kartą aprašyta net vadovėliuose, kompanija „Newegg“ teismo procesą pralaimėjo.

Savo ekskursiją po asimetrinės kriptografijos labirintus pradėsime ne nuo Diffie‒Hellman'o bendros paslapties sukūrimo algoritmo, bet nuo paprastesnio dalyko ‒ vienkryptes funkcijos.

Vieno argumento vienkryptė funkcija

Du žmonės žaidžia žaidimą: vienas išmeta monetą, ją pagauna ir uždengęs delnu padeda ant stalo, kitas spėja, iškrito herbas ar skaičius. Atspėjus, tašką gauna antras žmogus, neatspėjus ‒ pirmas. Kaip sužaisti tokį žaidimą internetu? Filmavimą iš karto atmesime kaip netinkamą sprendimą dėl įvairių galimybių piktnaudžiauti. Paprasčiausia būtų pasikviesti trečią asmenį, kuriuo pasitiki abu žaidėjai, ir jam siųsti monetos iškritimo rezultatą bei spėjimą. Tačiau ar gali trečio asmens vaidmenį atlikti matematika? Ja visi pasitiki todėl, kad ji veikia visiems vienodai, su ja negalima susitarti ar jos papirkti. Pasirodo, tam reikalui galime panaudoti vienkryptę funkciją. Kas tai yra ir su kuo valgoma? Vienkryptė funkcija yra deterministinis algoritmas, nusakantis, kaip iš fiksuoto ilgio bitų sekos paskaičiuoti naują to paties ilgio bitų seką. Tarkime, x yra 256 bitų seka, o y=H(x) yra naujai apskaičiuota 256 bitų seka, gauta, panaudojus vienkryptę funkciją H. Funkcija deterministinė, tai reiškia, kad jei du skirtingi asmenys, turėdami tą patį x, skaičiuos H(x), tai gaus tą patį y. Tačiau paėmus truputi kitokią seką x', besiskiriančią nuo x vos vienu bitu, rezultatas bus visiškai kitokia seka y'=H(x'), kuri atrodys kaip atsitiktinė ir su prieš tai apskaičiuota seka y nieko bendro neturinti. Toks „jautrumas“ pradinėms sąlygoms yra gerai žinomas reiškinys chaoso teorijoje, dar vadinamas drugelio efektu.

Kita vienkryptės funkcijos savybė, kaip matome iš pavadinimo, yra neapgręžiamumas. Tarkime, mums pateikiamas funkcijos H skaičiavimo rezultatas y ir liepiama surasti tokį x, kuris tenkintų sąlygą y=H(x). Neapgręžiamos funkcijos atveju nėra geresnio būdo kaip tik patikrinti visas įmanomas sekas. Kiek užtruktų visų įmanomų rezultatų perrinkimas? Įvairių x sekų yra 2^256. Jei turime po ranka galingiausią pasaulyje superkompiuterį, kurio skaičiavimo greitis apie 10^17 FLOPSų – slankiojo kablelio operacijų per sekundę) ir, tarkime, vienai H(x) funkcijai apskaičiuoti pakanka vienos tokios operacijos, tai sugaištume apie 10^60 sekundžių. Hmm… įdomu, ar tai daug? Remiantis Didžiojo Sprogimo teorija, visatos amžius yra apie 14 milijardų metų arba maždaug 10^17 sekundžių. Taigi mes užtruktume maždaug 10^43 visatos amžių! Aišku, mums gali ir pasisekti ir x aptiktume jau, pavyzdžiui, po 10-to bandymo. Tačiau tokio įvykio tikimybė yra baisiai maža, apie 10^(-76). Taigi sugrįžkime prie monetos mėtymo žaidimo. Pirmas žaidėjas sudaro seką x, kurioje pirmas bitas koduoja herbą (jam koduoti naudosime 0) arba skaičių (jam koduoti naudosime 1), o likę bitai sugeneruojami atsitiktinai su vienodom tikimybėm pasirodyti kiekvienai bito reikšmei. Tada pirmas žaidėjas skaičiuoja y=H(x) ir siunčia rezultatą antram žaidėjui. Tokia procedūra vadinama skaitmeniniu įsipareigojimu. Nors antras žaidėjas dėl vienkryptės funkcijos neapgręžiamumo negali pasakyti kas iškrito, pirmas žaidėjas metimo rezultato pakeisti negali, nes antras žaidėjas žino y. Kai antrasis žaidėjas, gavęs y, nusiunčia savo spėjimą pirmajam, šis privalo pateikti x, kad antrasis, paskaičiavęs iš jo y=H(x), įsitikintų pirmojo žaidėjo sąžiningumu.

Pačių vienkrypčių funkcijų yra prikurta gana daug, tačiau saugia laikoma daug saugumo testų praėjusi vienkryptė funkcija, pavyzdžiui SHA256, kuri taip ir išsišifruoja SHA ‒ Secure Hash Algorithm (saugus maišos algoritmas). Vienkryptės bitų maišos funkcijos kuriamos taip, kad į jas galima būtų dėti bet kokio ilgio bitų sekas, – nebūtinai tokio ilgio, kokio jos pateikia rezultatą. Tuomet patogu sutikrinti dviejuose kompiuteriuose esančių dviejų didelių failų tapatumą: jei failai dideli, siuntinėti juos ir lyginti būtų labai nepraktiška, galima tiesiog apskaičiuoti jų maišas ir palyginti jas. Taip pat maišos funkcijos naudojamos pseudoatsitiktinių skaičių generavimui. Internete yra daug puslapių, kur įrašius duomenis, galima paskaičiuoti jų maišas.