Kriptografinio šifravimo matematika

Kodėl šifruoti reikia matematikos?

Kai siunčiate žinutę draugui per WhatsApp arba perkate prekes internetu, jūsų duomenys keliauja per daugybę kompiuterių ir serverių. Kaip užtikrinti, kad niekas pakeliui jų neperskaitys? Čia į pagalbą ateina kriptografija – mokslas apie informacijos slėpimą. O jos pagrindas yra matematika, tik ne tokia, kokią mokėtės mokykloje.

Šiuolaikinė kriptografija remiasi labai sudėtingomis matematinėmis problemomis, kurias lengva išspręsti viena kryptimi, bet beveik neįmanoma – kita. Įsivaizduokite, kad lengvai sudauginate du didelius pirminius skaičius, tarkime 7919 ir 6421, ir gausite 50 852 399. Bet dabar pabandykite atvirkščiai – turėdami tik rezultatą 50 852 399, raskite tuos du pirminius skaičius. Tai užtruks gerokai ilgiau. O jei tie skaičiai būtų ne keturženkliai, o šimtų skaitmenų ilgio? Kompiuteriui prireiktų tūkstančių metų.

Būtent tokios matematinės problemos ir sudaro šiuolaikinės kriptografijos pagrindą. Jos leidžia sukurti sistemas, kuriose šifravimas yra greitas ir paprastas, o laužymas – praktiškai neįmanomas be specialaus rakto.

Simetriniai šifrai: tas pats raktas abiem pusėms

Paprasčiausia šifravimo forma veikia taip: turite vieną raktą, kuriuo ir užšifruojate, ir iššifruojate žinutę. Tai vadinasi simetriniu šifravimu. Klasikinis pavyzdys – Cezario šifras, kur kiekviena raidė pakeičiama kita, pastūmėta abėcėlėje per tam tikrą pozicijų skaičių. Jei raktas yra „3”, tai A tampa D, B tampa E ir taip toliau.

Žinoma, šiuolaikiniai simetriniai šifrai yra nepalyginamai sudėtingesni. Populiariausias iš jų – AES (Advanced Encryption Standard). Jis naudoja 128, 192 arba 256 bitų raktus ir atlieka sudėtingas matematines operacijas su duomenų blokais.

AES veikia taip: jūsų duomenys padalijami į 128 bitų blokus. Kiekvienas blokas pereina per kelis transformacijos raundus (10, 12 arba 14, priklausomai nuo rakto ilgio). Kiekviename raunde atliekamos keturios operacijos: baitų pakeitimas pagal specialią lentelę, eilučių poslinkis, stulpelių maišymas ir rakto pridėjimas. Šios operacijos remiasi Galois laukų algebra – matematikos šaka, kuri veikia su baigtinėmis skaičių aibėmis.

Kas įdomu – AES yra toks greitas, kad šiuolaikiniai procesoriai turi specialias instrukcijas jam pagreitinti. Jūsų kompiuteris gali užšifruoti gigabaitus duomenų per sekundes.

Asimetrinis šifravimas: matematikos magija

Dabar įsivaizduokite situaciją: norite gauti užšifruotą laišką iš nepažįstamo žmogaus. Kaip perduoti jam raktą saugiai? Jei siųsite jį internetu, kas nors gali jį perimti. Čia ir prasideda tikroji matematikos magija – asimetrinis šifravimas.

1977 metais trys mokslininkai – Rivest, Shamir ir Adleman – sukūrė RSA algoritmą, kuris išsprendė šią problemą. Jų idėja: turėti du raktus – vieną viešą, kurį gali žinoti visi, ir vieną privatų, kurį žinote tik jūs. Kas nors gali užšifruoti žinutę jūsų viešuoju raktu, bet iššifruoti ją gali tik jūs su privačiuoju.

Kaip tai veikia? RSA remiasi pirminių skaičių faktorizacijos problema. Štai supaprastinta versija:

1. Pasirenkate du didelius pirminius skaičius (p ir q)
2. Juos sudauginate: n = p × q
3. Apskaičiuojate Eulerio funkciją: φ(n) = (p-1)(q-1)
4. Pasirenkate viešąjį eksponentą e (dažniausiai 65537)
5. Apskaičiuojate privatųjį eksponentą d, kuris tenkina: (d × e) mod φ(n) = 1

Viešasis raktas yra (n, e), o privatusis – (n, d). Kai kas nors nori jums atsiųsti žinutę m, jie apskaičiuoja: c = m^e mod n. Jūs iššifruojate: m = c^d mod n.

Kodėl tai saugu? Nes norint rasti d, reikia žinoti φ(n), o tam reikia žinoti p ir q. Bet turint tik n, surasti p ir q (t.y. faktorizuoti n) yra nepaprastai sudėtinga, kai n yra 2048 ar 4096 bitų skaičius.

Elipsinės kreivės: efektyvesnis kelias

RSA veikia puikiai, bet turi trūkumą – reikia labai didelių raktų. 2048 bitų RSA raktas užtikrina gerą saugumą, bet užima nemažai vietos ir reikalauja daug skaičiavimų. Čia į sceną ateina elipsinių kreivių kriptografija (ECC).

Elipsinė kreivė – tai matematinė kreivė, apibrėžta lygtimi y² = x³ + ax + b. Ant šios kreivės galima apibrėžti specialią sudėties operaciją: jei paimsite du taškus ant kreivės ir nubrėžsite per juos tiesę, ji kirš kreivę trečiame taške. Atspindėkite jį per x ašį – ir gausite šių dviejų taškų „sumą”.

Dabar įsivaizduokite, kad paimsite tašką G ant kreivės ir sudėsite jį su savimi daug kartų: G + G + G + … (n kartų). Tai vadinama skaliarinio dauginimo operacija. Lengva apskaičiuoti rezultatą žinant n, bet turėdami tik rezultatą, surasti n yra labai sunku. Tai vadinama diskrečiojo logaritmo problema elipsinėse kreivėse.

ECC privalumas – 256 bitų ECC raktas yra lygiavertis 3072 bitų RSA raktui saugumo požiūriu. Tai reiškia mažesnius raktus, greitesnius skaičiavimus ir mažesnį energijos suvartojimą. Todėl ECC ypač populiarus mobiliuose įrenginiuose ir IoT sistemose.

Maišos funkcijos: skaitmeniniai pirštų atspaudai

Kriptografijoje svarbu ne tik slėpti informaciją, bet ir patikrinti, ar ji nebuvo pakeista. Tam naudojamos maišos funkcijos (hash functions). Jos paima bet kokio dydžio duomenis ir sugeneruoja fiksuoto ilgio „pirštų atspaudą”.

Populiariausia šiandien yra SHA-256 (Secure Hash Algorithm). Ji paima jūsų duomenis ir išveda 256 bitų (32 baitų) maišą. Pavyzdžiui, žodžio „labas” SHA-256 maiša būtų: 3f39d5c348e5b79d06e842c114e6cc571583bbf44e4b0ebfda1a01ec05745d43.

Pakeiskite nors vieną raidę į „Labas”, ir maiša bus visiškai kitokia: 8f434346648f6b96df89dda901c5176b10a6d83961dd3c1ac88b59b2dc327aa4.

Geros maišos funkcijos savybės:

– Deterministiškumas: tie patys duomenys visada duoda tą pačią maišą
– Speed: maišą turi būti greitai apskaičiuoti
– Lavinos efektas: mažas pokytis įvestyje drastiškai keičia išvestį
– Vienakryptiškumas: turėdami maišą, negalite atkurti pradinių duomenų
– Kolizijų atsparumas: praktiškai neįmanoma rasti dviejų skirtingų įvesčių, duodančių tą pačią maišą

SHA-256 veikia per kelis etapus. Duomenys papildomi iki ilgio, kuris dalijasi iš 512 bitų. Tada jie apdorojami 512 bitų blokais, kiekvienas blokas pereina per 64 raundus sudėtingų loginių operacijų (AND, OR, XOR, NOT) ir sudėties modulo 2³² operacijų. Naudojamos specialios konstantos, išvestos iš pirminių skaičių kvadratinių ir kubinių šaknų.

Kvantinė grėsmė ir ateities sprendimai

Viskas, apie ką kalbėjome iki šiol, veikia puikiai… kol kas. Bet horizonte jau matoma grėsmė – kvantiniai kompiuteriai. Jie veikia visiškai kitokiais principais nei įprasti kompiuteriai ir gali išspręsti kai kurias matematines problemas neįtikėtinai greitai.

1994 metais matematikas Peteras Shoras sukūrė algoritmą, kuris kvantiniame kompiuteryje gali faktorizuoti didelius skaičius per polinominį laiką. Tai reiškia, kad pakankamai galingas kvantinis kompiuteris galėtų nulaužti RSA šifravimą per valandas ar minutes, o ne tūkstančius metų.

ECC taip pat pažeidžiama Shoro algoritmo. Tačiau simetriniai šifrai kaip AES yra atsparesni – kvantiniai kompiuteriai juos susilpnina, bet nelaužo visiškai. 256 bitų AES raktas tampa lygiavertis 128 bitų raktui, o tai vis dar pakankamai saugu.

Todėl kriptografai jau dabar kuria post-kvantinę kriptografiją – algoritmus, kurie būtų atsparūs ir kvantiniams kompiuteriams. NIST (Nacionalinis standartų ir technologijų institutas) jau pradėjo standartizuoti tokius algoritmus. Jie remiasi kitomis matematinėmis problemomis:

Grotelių kriptografija (lattice-based) – remiasi problemomis daugiamačiuose grotelių erdvėse. Pavyzdžiui, rasti trumpiausią vektorių grotelėse yra sunku net kvantiniams kompiuteriams.

Kodų kriptografija – remiasi klaidų taisymo kodų teorija. Iššifruoti žinutę reiškia išspręsti NP-sunkią problemą.

Daugianarių kriptografija – remiasi daugianarių lygčių sistemų sprendimu, kuris yra sunkus net kvantiniams kompiuteriams.

Praktinis šifravimas kasdieniame gyvenime

Visa ši matematika gali skambėti abstrakčiai, bet ji veikia jūsų kišenėje kiekvieną dieną. Kai naršote svetainę su HTTPS, jūsų naršyklė ir serveris atlieka šį šokį:

1. Serveris atsiunčia savo viešąjį raktą (dažniausiai ECC arba RSA) kartu su sertifikatu
2. Jūsų naršyklė patikrina sertifikatą (naudodama maišos funkcijas ir skaitmeninius parašus)
3. Naršyklė sugeneruoja atsitiktinį simetrinį raktą
4. Šis raktas užšifruojamas serverio viešuoju raktu ir išsiunčiamas
5. Nuo šiol visa komunikacija vyksta su simetriniu šifru (AES), kuris yra daug greitesnis

Tokiu būdu išnaudojamos abiejų metodų stiprybės: asimetrinis šifravimas saugiai perduoda raktą, o simetrinis – greitai šifruoja didelius duomenų kiekius.

Jūsų telefone saugomi slaptažodžiai taip pat apsaugoti matematika. Jie nėra saugomi tiesiogiai – vietoj to saugoma jų maiša (dažniausiai su „druska” – atsitiktiniu priedu, kad vienodi slaptažodžiai turėtų skirtingas maišas). Kai įvedate slaptažodį, sistema apskaičiuoja jo maišą ir palygina su saugoma.

Kriptovaliutos kaip Bitcoin naudoja elipsines kreives skaitmeniniams parašams. Kai pervedate bitcoinus, jūs pasirašote transakciją savo privačiuoju raktu. Bet kas gali patikrinti parašą su jūsų viešuoju raktu, bet niekas negali suklastoti parašo be privataus rakto.

Kai matematika susiduria su realybe

Teoriškai saugi kriptografija gali būti nesaugi praktikoje dėl įgyvendinimo klaidų. Štai keletas realių problemų:

Atsitiktinių skaičių generavimas – visa kriptografija remiasi gerais atsitiktiniais skaičiais. Jei jūsų sistema generuoja nuspėjamus „atsitiktinius” skaičius, visa sistema tampa nesaugi. 2012 metais tyrėjai rado, kad daugelis interneto serverių naudojo silpnus atsitiktinius skaičius RSA raktams, todėl milijonai raktų galėjo būti nulaužti.

Šoniniai kanalai – net jei algoritmas matematiškai saugus, užpuolikas gali išgauti informaciją stebėdamas, kiek laiko užtrunka operacija, kiek energijos suvartoja procesorius, ar net kokius garsus skleidžia kompiuteris. Pavyzdžiui, RSA iššifravimas gali užtrukti skirtingai priklausomai nuo privataus rakto bitų, todėl tikslūs laiko matavimai gali atskleisti raktą.

Žmogiškasis faktorius – stipriausias šifravimas nenaudoja nieko, jei slaptažodis yra „123456”. Arba jei kas nors paspaudžia ant phishing nuorodos ir atiduoda savo raktus.

Kriptografai tai supranta ir kuria sistemas, kurios yra atsparios šiems dalykams. Pavyzdžiui, „konstantinio laiko” algoritmai, kurie visada užtrunka tą patį laiką nepriklausomai nuo įvesties. Arba aparatiniai saugumo moduliai (HSM), kurie atlieka kriptografines operacijas izoliuotoje aplinkoje.

Kodėl visa tai veikia ir kas laukia ateityje

Grįžkime prie pagrindinio klausimo: kodėl visa ši matematika veikia? Atsakymas slypi asimetrijos principo – lengva viena kryptimi, sunku kita. Šiuolaikinė kriptografija remiasi matematinėmis problemomis, kurioms nėra žinomi efektyvūs sprendimo algoritmai. Tai nereiškia, kad jų neįmanoma išspręsti – tiesiog reikia tiek daug laiko, kad tai praktiškai neįmanoma.

Kriptografijos grožis tas, kad ji nuolat evoliucionuoja. Kai atrandami nauji atakų būdai, kuriami nauji gynybos mechanizmai. Kai technologijos tobulėja (kaip kvantiniai kompiuteriai), matematikai ieško naujų sunkių problemų, ant kurių galima pastatyti saugias sistemas.

Jūsų kasdienė komunikacija, bankinės operacijos, sveikatos duomenys – visa tai apsaugota šių matematinių principų. Ir nors matematika gali atrodyti sudėtinga, rezultatas yra paprastas: galite saugiai naudotis internetu, žinodami, kad jūsų duomenys yra apsaugoti matematikos, kuri veikia jau dešimtmečius ir tęs veikti dar ilgai į ateitį.

Ateitis atneš naujų iššūkių – kvantiniai kompiuteriai, dirbtinis intelektas, galbūt net visiškai nauji skaičiavimo modeliai. Bet principas išliks tas pats: rasti matematines problemas, kurios yra pakankamai sunkios užpuolikams, bet pakankamai paprastos teisėtiems vartotojams. Ir kol matematika turi tokių problemų, jūsų duomenys bus saugūs.