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

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