Mokslo ir technologijų pasaulis

Žmonės smalsūs, jiems paslaptys patinka – tiek turėti savas, tiek šniukštinėti svetimas. Nenuostabu, kad per civilizacijos tūkstantmečius žmonės šiuos užsiėmimus ištobulino. Ir dabar netgi kasdieniame gyvenime, to net nepastebėdami, kuriame paslaptis, kurių įminimui neužtektų ir visatos gyvavimo amžiaus.

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.

Maišos funkciją naudojame beveik kasdien to net neįtardami. Pavyzdžiui, kodų generatoriai, naudojami jungiantis prie elektroninės bankininkystės, pagrįsti maišos funkcija: sugeneruojama atsitiktinė bitų seka x₀, iš jos paskaičiuojamas x₁=H(x₀), tada x₂=H(x₁) ir taip iki x₁₀₀₀=H(x₉₉₉). Taip sugeneruotos sekos x₀, … , x₉₉₉ turi tokią savybę: jei žinomas x_m, tai galima nesunkiai apskaičiuoti x_m+1 arba x_m+2 ir t.t., bet gauti x_m-1 nepavyks. Visi x₀, …, x₉₉₉ surašomi į kodų generatorių, o į banko serverį perduodamas x₁₀₀₀. Kodų generatorius rodo sekas atbuline tvarka: pradžioje x₉₉₉, paskui x₉₉₈ ir t.t. Jungiantis prie savo paskyros, serveriui nusiunčiamas kuris nors x_m, tada serveris skaičiuoja maišą x_m+1=H(x_m) ir tikrina ar rezultatas sutampa su x₁₀₀₀. Sutapimo atveju autentifikavimas patvirtinamas, nesutapus – vėl skaičiuojama rezultato maiša x_m+2=H(x_m+1)=H(H(x_m)) ir vėl lyginama su x₁₀₀₀. Taip kartojama 1000 kartų. Jei sutapimo neįvyko, autentifikavimas atšaukiamas, jei įvyko, vietoje x₁₀₀₀serveryje įrašomas x_m ir kito autentifikavimo atveju atliekamas palyginimas su x_m. Taip užtikrinama, kad tas pats x_m nebūtų naudojamas antrą kartą, todėl vieno autentifikavimo metu nutekinta slapta prisijungimo seka x_m negali būti panaudota antrą kartą. Iš kitos pusės, 1000 kartų galima jungtis prie serverio ir nereikia po kiekvieno prisijungimo eiti į banką naujo slaptažodžio.

Bendros paslapties sukūrimas maišant spalvas

Įsivaizduokime tokią situaciją: stovite viename upės krante, o kitame krante stovi žmogus, kuriam norite perduoti kažkokią paslaptį. Plaukti nei jūs, nei kitas žmogus nemoka. Bet jūs ir jūsų likimo draugas galite garsiai šaukti. Taip garsiai, kad girdisi net kitame krante. Aišku, visi jūsų šauksmai kaip mat tampa vieši. Ar galima panaudojus kriptografiją perduoti paslaptį? Simetrinė kriptografija čia nepagelbės, nebent jūsų likimo draugas yra jūsų senas pažįstamas ir jūs turite su juo bendrų paslapčių. Kadangi mūsų atveju taip nėra, čia į pagalbą mums ateina Diffie‒Hellman'o bendros paslapties sukūrimo algoritmas. Kad nelįstume į matematiką, panaudosime spalvas. Iš pradžių viešai susitariate dėl bazinės spalvos. Tarkime, tai bus geltona. Tada iš visos spalvų paletės išsirenkate savo slaptą spalvą ir sumaišote ją su bazine spalva. Tarkime, tai yra mėlyna spalva, o po sumaišymo su geltona gausime žalią. Tą patį padaro ir jūsų draugas. Tarkime, jis išsirinko raudoną ir sumaišęs su geltona gavo oranžinę. Dabar jūs abu siunčiate vienas kitam gautas spalvas: jums iš draugo atkeliauja oranžinė spalva, o jis gauna žalią. Atspėti, kokia spalva buvo įmaišyta į geltoną, jei buvo gauta oranžinė arba žalia – nesunku, bet kol kas tarkime, kad sumaišymas yra lengvai atliekamas, bet atvirkštinis veiksmas ‒ neįmanomas. Taigi, turėdami iš draugo gautą oranžinę spalvą, į ją primaišote savo slaptą spalvą, t.y. mėlyną, ir gaunate negražią žaliai-rudą spalvą.

Kodėl gavome tą pačią spalvą? Ogi todėl, kad abiem atvejais tiesiog sumaišėme tris spalvas: geltoną, mėlyną ir raudoną. Tačiau paviešintos buvo tik geltona, oranžinė ir žalia. Jei kas nors bandytų atkurti bendrą slaptą žaliai-rudą spalvą, tai sumaišęs, pavyzdžiui, oranžinę su žalia, negautų tos pačios žaliai-rudos spalvos tiesiog todėl, kad tai būtų du kartus geltonos, mėlynos ir raudonos spalvų mišinys. Vienos geltonos neutralizuoti niekaip nepavyktų, ypač jei naudojame vienkryptes funkcijas. Taigi, mūsų gautą slaptą spalvą dabar galime naudoti kaip raktą bet kokiame saugiame simetriniame šifre ir siųsti vienas kitam užkoduotus pranešimus. Asimetrinė kriptografija sukūrė bendrą paslaptį, o naudojant vien simetrinę kriptografiją, to padaryti negalėtume.

Dviejų argumentų vienkryptė funkcija su komutatyvumo ir adityvumo savybėmis

Žaidimas su spalvomis buvo tik patogi iliustracija, tačiau dabar tą patį atliksime su rimta matematika. Na gerai, gal ne tokia jau rimta, bet procesą šiek tiek matematizuosime. Naudosime, pavyzdžiui, 256 bitų sekas. Įsivaizduokime, kad turime viešai paskelbtą saugią dviejų argumentų vienkryptę funkciją z=H(x,y), kuri grąžina 256 bitų seką, kai jai pateikiamos dvi 256 bitų sekos. Kaip ir anksčiau, ji yra deterministinė, bei neapgręžiama, t.y. žinant rezultatą z bei vieną iš argumentų, x arba y, kito argumento atkurti neįmanoma (bent jau per visatos amžių). Taigi, jei žinome z ir x, atkurti y nepavyks. Tačiau jei žinome x ir y, z apskaičiavimas yra juokų darbas. Maišydami spalvas, turėjome tokią savybę, kad sumaišius geltoną su mėlyna gauname tą patį, ką ir sumaišius mėlyną su geltona. Kitaip tariant, nėra svarbus spalvų eiliškumas. Matematiškai tokia savybė vadinama komutatyvumu. Laikysime, kad H(x,y) rezultatas tas pats, kaip ir H(y,x). Taip pat spalvų maišymo operacija yra adityvi: pirmą spalvą sumaišę su antra ir po to įmaišę trečią, gausime tą patį, ką ir antrą sumaišę su trečia ir įmaišę pirmą. Uch…, lengviau užrašyti formulę: H(H(x,y),z)=H(x,H(y,z)). Apsiginklavę šiomis savybėmis, galime atkartoti spalvų maišymo protokolą. Pasikviesime dar tradiciškai kriptografijoje naudojamus veikėjus: Alisą ir Bobą. Taigi, jie viešai susitaria dėl bazinės sekos g, tada Alisa sugeneruoja slaptą seką a ir suskaičiavusi A=H(g,a) rezultatą siunčia Bobui. Bobas atitinkamai sugeneruoja slaptą seką b ir suskaičiavęs B=H(g,b) rezultatą siunčia Alisai. Dabar Alisa, gavusi Bobo B sumiksuoja jį su savo slapta seka a, t.y. paskaičiuoja H(a,B). O Bobas atitinkamai skaičiuoja H(b,A). Nesunku įsitikinti, kad abu rezultatai sutampa: H(a,H(g,b))=H(b,H(g,a)).

Alisa ir Bobas ši bendrą rezultatą gali saugiai naudoti simetriniame šifre, nes niekas negalės atkurti jų bendros paslapties iš viešai prieinamų duomenų, t.y. g, A ir B.

Jei atkreipėte dėmesį, naršant kai kuriuose puslapiuose naršyklėje prie adresų juostos atsiranda spynelės ikona, o adresas prasideda raidėmis https. Tai informuoja, kad jūsų kompiuteris su puslapio serveriu bendrauja saugiu ryšiu, susikūrę bendrą paslaptį.

Privatus ir viešas raktas

Kriptografijoje slapta seka a turi savo pavadinimą ‒ tai Alisos privatus raktas, o A=H(g,a) yra Alisos viešas raktas. Įsivaizduokime miestelį, kuriuo visi gyventojai susitarė dėl viešos bazinės sekos g. Kiekvienas gyventojas susigeneravo savo privatų raktą, o apskaičiuotą viešą raktą užrašė ant savo pašto dėžutės. Alisa atėjo pas Bobą, bet jo šiuo metu nėra namie. Ji nori palikti jam pranešimą, kuris yra 256 bitų seka m, bet nėra tikra, ar tiesiog įmetus pranešimą į pašto dėžutę, jo neperskaitys piktoji Eva (dar vienas klasikinis kriptografijos protokolų veikėjas). Ką daryti? Nors Bobo ir nėra namie, ji gali susikurti su juo bendrą paslaptį ir iš karto ją panaudoti pranešimo kodavimui. Alisa pasiima Bobo viešą raktą, sumiksuoja su savo privačiu raktu ir rezultatą „suksorina“ su pranešimu: M=XOR(H(B,a),m). Dar ant lapelio Alisa užrašo savo viešą raktą A ir kartu su užšifruotu pranešimu M įmeta į Bobo pašto dėžutę. Dabar Alisa ramiai miegos, nes tik Bobas galės apskaičiuoti H(b,A), rezultatą „suksorinti“ užšifruotu pranešimu M, ir taip atkurti originalų pranešimą XOR(H(b,A),M)=m.

Čia abi Bobui paliktas sekas M ir A galima interpretuoti kaip užšifruotą pranešimą, nes A Alisa galėjo nenurašinėti nuo savo pašto dėžutės, bet sugeneruoti tik pamačiusi, kad Bobo nėra namie. Taigi, įvyko štai kas: Alisa, panaudojusi Bobo viešą raktą, užkodavo pranešimą taip, kad jį atkoduoti galėjo tik Bobas su savo privačiu raktu. Net pati Alisa, jei netyčia pamirštų pranešimą, ir turėdama tik Bobui perduodamus duomenis M ir A, negalėtų jo atkoduoti.

Čia iškyla natūralus klausimas: o ar galima daryti atvirkščiai ‒ užkoduoti pranešimą savo privačiu raktu, o atkoduoti galės kiekvienas su viešai žinomu viešu raktu?

Elektroninis parašas

Jei pranešimą užkoduoti galiu tik aš, o atkoduoti ir įsitikinti, kad užkodavau tikrai šį, o ne kitą pranešimą, gali kiekvienas, panaudojęs mano viešą raktą, tai toks dalykas gali vadintis parašu. Įsivaizduokime: Alisa susilaužė koją, todėl negali nueiti pas Bobą. Bet nori jam perduoti žinutę, kaip visada, 256 bitų seką m. Todėl įduoda žinutę Evai, kad ji nuneštų Bobui. Bet kaip užtikrinti, kad Eva pranešimo nesuklastos? Eva tik ir laukia, kada galės Alisos vardu įduoti Bobui sukompromituotą pranešimą ir išdidžiai pareikšti „štai ką apie tave galvoja Alisa!“. Taigi, gudrioji Alisa prie pranešimo m prideda jo elektroninį parašą s=H(a,m), apskaičiuotą kaip Alisos privataus rakto ir pranešimo mišinį. Bobas, gavęs iš Evos m ir s, bei žinodamas Alisos viešą raktą A, patikrina, ar galioja lygybė H(s,g)=H(m,A). Jei pranešimas buvo pakeistas, lygybė negalios. Iš kitos pusės, sugeneruoti tokį s, kad galiotų lygybė konkrečiam pranešimui m, gali tik Alisa. O patikrinti gali kiekvienas. Todėl ši procedūra ir vadinama elektroniniu parašu.

Patikslinimas

Asimetrinėje kriptografijoje naudojamos vieno argumento vienkryptės funkcijos, bet nėra žinomų saugių dviejų argumentų vienkrypčių funkcijų su komutatyvumo ir adityvumo savybėmis. Tačiau tai nereiškia, kad asimetrinė kriptografija neveikia. Tiesiog matematinės operacijos naudojamos asimetrinėje kriptografijoje veikia šiek tiek kitokiu būdu, bet realizuoja tą patį rezultatą, kuris čia aprašytas.

Kaip minėta, vienintelis matematiškai įrodytas saugus šifras yra Vernamo šifras. Kitaip tariant, šiuolaikinėje kriptografijoje naudojamos vienkryptės funkcijos gali būti ir nesaugios. Problema – norint įrodyti, kad egzistuoja saugi vienkryptė funkcija, reikia įrodyti vieną iš matematikos šimtmečio problemų, susijusių su taip vadinamu P ir NP sudėtingumo klasių nelygumu. Jei būtų įrodyta, kad P=NP, būtų įmanoma sukurti algoritmus, kuriais būtų galima per protingą laiką išspręsti iki šiol tik apytiksliai spręstas problemas, pavyzdžiui, tokias kaip keliaujančio pirklio uždavinys. Tačiau kartu tai reikš, kad negalima sukurti saugios vienkryptės funkcijos. Antra vertus, jei bus parodyta, kad P nelygu NP, tai reikš saugios vienkryptės funkcijos egzistavimą.

V. Novičenko