Krüptograafia

Krüptograafia on matemaatika ja arvutiteaduse haru, mis tegeleb informatsiooni salastamise ning kehtivuse ja omaniku kontrollimisega. Krüptograafias väljatöötatud meetodid võimaldavad selliseid laialdaselt kasutavaid funktsioone nagu autentimine, andmete krüpteerimine ja digitaalne allkirjastamine. Eelnimetatud funktsioonid on kriitilise tähtsusega kaasaegses infoühiskonnas toimivate andme- ja internetipõhiste teenuste toimimisel, nagu nt mobiilside ja e-post, krediitkaartid, pangaautomaadid ja internetipank, turvalised võrguühendused jne.

Eesti kodanike e-identiteet põhineb talle väljastatud ID-kaartil peituva avaliku sertifikaadi ja salajase võtme toimemehhhanismile. Eesti ID-kaartide sertifikaate haldab skidsolutions: https://www.skidsolutions.eu/ . Eesti kodaniku avaliku sertifikaadi nägemiseks piisab veebilehitseja aadressiribale kopeerida ldap://esteid.ldap.sk.ee:636/c=EE??sub?(cn=perenimi,eesnimi,isikukood) , kus perenimi, eesnimi ja isikukood tuleb asendada enda või huvipakkuva inimese vastavate andmetega. Seejärel avaneb sertifikaadi omaniku kontaktinfo. Navigeerides avanenud aknas isiku nimi --> Properties --> IDs --> [email protected] --> Properties, avaneb vastava inimese avalik sertifikaat.



Veebilehtedele on harilikult samuti väljastatud sertifikaat:
Vajutades tabalukule ning seejärel sõnale "Sertifikaat", avaneb sisuliselt sama ülesehitusega sertifikaat nagu ka inimese puhul:

Sertifikaatide turvalisuse seisukohalt on selle kõige olulisemad komponendid avalik võti (public key) ja salajane võti (private key). Avalikel sertifikaatidel on näha ainult avalik võti. Eesti kodanike sertifikaatide salajane võti on peidetud sellele inimesele väljastatud ID-kaartis, millele on ligipääs ainult PIN1 sisestamisel. Sertifikaadi avalik ja salajane võti on üksteisega matemaatiliselt seotud nii, et inimene saab tõendada avaliku sertifikaadi temale kuuluvust selle sertifikaadi avaliku võtme ja oma id-kaartil oleva salajase võtme kombineerimise teel, mille tulemusel vastav vertifitseerimine kas õnnestub või ebaõnnestub.

See võimaldab ID-kaarti ja selle sertifikaati kasutada autentimisteenustes, nagu näiteks sisselogimisel internetipanka ja avalikku teenust pakutavatesse asutuste kodulehtedele. Lisaks sellele on kasutaja salajase võtme väärtust mingi failiga võimalik kombineerida nii, et saadud tulemust vertifitseerib ainult selle sama kasutaja avalik võti, ja mitte kellegi teise avalik võti. Sellist tegevust ja avaliku-salajase võtmepaari omadust kasutatakse digitaalsel allkirjastamisel. Kolmandaks on mistahes inimesel võimalik kellegi teise sertifikaadi avaliku võtmega krüpteerida mingit infot, mida on võimalik dekrüpteerida ainult konkreetse inimese (kelle avaliku võtmega info krüpteeriti) salajase võtmega. Üldiselt on aga selline krüpteerimine aeglane protsess, ning krüpteeritakse ainult ühise salajase võtme väärtus, pärast mille jagamist hakkab info krüpteerimine toimuma ainult kokkulepitud sümmeetrilise võtme alusel.

Enamik krüpteerimisalgoritme põhineb raskestiarvutatavate ülesannete põhimõttel, s.t, et mingit salajast infot dekodeerida, kuluks arvutitel vajanimena arvutuse tegemiseks ebapraktiliselt kaua aega (tuhandeid aastaid). Üheks selliseks raskestilahendatavaks probleemiks on naturaalarvude tegurdamine, täpsemalt selliste naturaalarvude tegurdamine, mis on kahe suure algarvu korrutis. Siiamaani ei ole leitud efektiivset viisi selliste naturaalarvude tegurdamiseks.

Algarvuks nimetatakse ühest suuremat naturaalarvu $p$, mille ainsateks jagajateks on arvud 1 ja $p$.
Aritmeetika põhiteoreemi kohaselt on mistahes naturaalarv $n$ kas algarv või esitatav algarvude astmete korrutisena, s.t iga naturaalarvu $n \in \mathbb{N}$ korral leiduvad algarvud $p_1,...,p_m \in \mathbb{P}$ ja nende algarvud astendajad $k_1,...,k_m$ nii, et $n = p_{1}^{k_1} \cdot ... \cdot p_{m}^{k_m}$.

Kuigi naturaalarvude tegurdamiseks on välja arendatud mõningaid algoritme, mis selle ülesande lahendamist kiirendavad, ei ole nad kokkuvõttes oluliselt kiiremad kui algtegurite leidmine jõumeetodil, kus arvuti jagab vaadeldavat naturaalarvu järjestike paaritute arvudega nii kaua, kuni jõuab arvuni, mis seda naturaalarvu jagab. Seetõttu vaatleme näitena, kui palju kulub ühel tavapärasel arvutil aega jõumeetodil ühe suure algarvulise teguri leidmiseks.

Kahendsüsteemis esitatud $n$-bitiseid paarituid naturaalarve on kokku $2^{n-1} = 10^{(n-1) \cdot \log 2}$. Üks 8-tuumaline 3GHz taktsagedusega protsessor suudab 24 tunni jooksul teostada $24 \cdot 60 \cdot 60 \cdot 8 \cdot \frac{ \cdot 3 \cdot 10^9}{N} = \frac{2.0736 \cdot 10^{15}}{N}$ tehet, kus $N$ on tehte sooritamiseks vajalik protsessori tsüklite arv, mis sõltub nii teostatavast tehtest kui ta protsessori arhitektuurist. See protsessor suudab $10^{(n-1) \cdot \log 2}$ tehet sooritada seega $\frac{N}{2.0736} \cdot 10^{(n-1) \cdot \log 2-15}$ päevaga. Näiteks 8-tuumalisel 3GHz taktsagedusega protsessoril, mis teostab jagamistehte kahe tsükliga (N=2), kulub 128-bitise (n = 128) algarvulise teguri leidmiseks maksimaalselt $\frac{2}{2.0736} \cdot 10^{(128-1) \cdot \log 2 - 15} \approx 1 \cdot 10^{127 \cdot 0.3 - 15} \approx 10^{23}$ päeva ehk $\frac{1}{3.56} \cdot 10^{21}$ aastat ning tõenäosus, et algtegur leitakse $\frac{1}{3.56} \cdot 10^{19}$ aasta jooksul on 1%. Tänapäevase standardi järgi näiteks 1024-bitise algarvulise teguri leidmiseks kuluks sellel protsessoril maksimaalselt ligikaugu $\frac{1}{3.56} \cdot 10^{1314}$ aastat.

Suurte algarvude genereerimine

Et moodustada turvalisi krüptograafilisi võtmeid, on vaja esmalt leida suuri algarve. Antud naturaalarvu korral on erinevaid meetodeid kontrollimaks, kas ta on algarv.

Üks praktilisemaid viise algarvulisust testida on kasutades Fermat' väikest teoreemi:

Naturaalarv $p$ on algarv, kui iga naturaalarvu $a \in [2, p-1]$ korral kehtib implikatsioon \[ (a,p) = 1 \Rightarrow a^{p-1} \equiv 1 \; (\text{mod} \; p), \] kus $(a,p)$ on täisarvu $a$ ja algarvu $p$ suurim ühistegur.

Jäeldus: Olgu $p \gt 2$ algarv ja $a$ täisarv ning $p \nmid a$. Esitame paarisarvu $p-1$ kujul $p-1 = 2^s \cdot t$, kus $s \ge 0$ ja $t$ on paaritu arv. Siis kas $a^t \equiv 1 \; (\text{mod} \; p)$ või leidub $0 \leq r \lt s$ nii, et $a^{2^r \cdot t} \equiv -1 \; (\text{mod} \; p)$.

Fermat' väikest teoreemi kasutatakse Miller-Rabini algarvulisuse testis.

Kui naturaalarvu $n$ korral leidub täisarv $a$ nii, et $(a,n) = 1$ ja $n-1 = 2^s \cdot t$, kus $t$ on paaritu arv ning $a^t \neq 1 \; (\text{mod} \; p)$ ja $a^{2^i \cdot t} \neq -1 \; (\text{mod} \; p)$ iga $i = 0,1,...,s-1$ korral, siis $n$ on kordarv.

Seega algarvulisuse testimiseks anname arvule $a$ erinevaid täisarvulisi väärtusi lõigust $[2,n-1]$. Kui $n$ on paarisarv või $(a,n) \gt 1$, siis $n$ on ilmselt kordarv. Vastasel korral avaldame $n$ kujul $n-1 = 2^s \cdot t$ ja leiame järjest $a^t, \; (a^t)^2 = a^{2t}, a^{2^2t}, \; ... \; a^{2^{s-1} \cdot t} \; (\text{mod} \; n)$. Kui $a^t$ ei ole kongruentne arvuga $1$ mooduli $p$ järgi ja $a^{2^i \cdot t}$ ei ole kongruentne arvuga $-1$ iga $i = 0,1,...,s-1$ korral, siis $a$ on Miller-Rabini tunnistaja ja $n$ on kordarv. Vastasel korral, testides mitmete erinevate $a$ väärtustega, on $n$ tõenäoliselt algarv.

Olgu $n$ paaritu kordarv. Siis vähemalt 75% täisarvude $1 \lt a \lt n$ korral on $n$ kordarv.

Autentimine

RSA on asümmeetriline avaliku võtme krüptosüsteem. Asümmeetriline tähendab siin seda, et kodeerimine ja dekodeerimine toimuvad erinevate võtmetega. Muuhulgas kasutab RSA krüptosüsteemi Eesti ID-kaart, millele on talletatud digitaalallkirjastamisel kasutatavad avalik ja salajane võti. Asümmeetria tõttu saab viimaseid kasutada ka tekstide kodeerimiseks, aga see ei ole eriti otstarbekas ega levinud.

RSA algoritm töötab järgmise skeemi aluse. Kodeerimiseks ja dekodeerimiseks on vajalikud avalik ja salajane võti. Kuna iga digitaalset suurust saab esitada naturaalarvuna, siis need ongi lihtsalt kaks naturaalarvu. Võtmete leidmiseks kasutatakse järgmist skeemi:

1. valime kaks algarvu $p$ ja $q$ (siin on kasulikud algarvulisuse testid), mis praktilistel kaalutlustel peaksid olema umbkaudu samas suurusjärgus
2. arvutame mooduli $n = p \cdot q$
3. leiame $\varphi(n) = (p-1) \cdot (q-1)$
4. valime sellise avaliku astendaja $1 \lt e \lt \varphi(n)$, et $(e,\varphi(n)) = 1$
5. leiame salajase astendaja $1 \lt d \lt \varphi(n)$ nii, et $ed \equiv 1 \; (\text{mod} \; \varphi(n))$

Avalik võti on arvupaar $(n,e)$ ja salajane võti on paar $(n,d)$. Kuna $d$ arvutati $\varphi(n), \; p$ ja $q$ abil, siis tuleb ka viimased salajas hoida. Avalik võti tehakse järgmistes protsessides osalejatele teatavaks, salajane võti peab jääma ainult kodeerija enda teada.

Salajase võtme edastamine

Diffie-Hellmani võtmevahetus on meetod salajase informatsiooni (üldiselt on selleks mingi krüptosüsteemi salajased võtmed või nende osad) jagamiseks üle ebaturvalise kanali (näiteks avalik internet). Skeem on iseenesest järgmine:

1. valime lõpliku tsüklilise rühma $G$ ja selle moodustaja $g$ (sageli $G = \mathbb{Z}_{p}^{\ast}$ ja $g$ on algjuur mooduli $p$ järgi)
2. osapool $A$ valib juhusliku naturaalarvu $k$ ja saadab teisele osapoolele $B$ elemendi $g^k$
3. osapool $B$ valib juhusliku naturaalarvu $l$ ja saadab $A$-le tagasi $g^l$
4. $A$ arvutab $(g^l)^k$ ja $B$ arvutab $(g^k)^l$
5. kuna mistahes rühmas $(g^l)^k = g^{kl} = (g^k)^l$, siis on mõlemal osapoolel nüüd jagatud saladus $g^{kl}$.

Digitaalne allkirjastamine

Algoritmi parameetrid:
1. Vali krüptograafiline räsifunktsioon $H$, mille väljund on $H$-bitine.
2. Vali võtme pikkus, harilikult suurusega $512 \le 64*n \le 1024$, kus $n$ on naturaalarv.
3. Vali mooduli pikkus $N$ nii, et $N < L$ ja $N \le |H|$. Harilikult on $N$ ja $L$ paarid (1024,160), (2048,224), (2048, 256) või (3072, 256).
4. Vali $N$-bitine algarv $q$.
5. Vali $L$-bitine algarv $p$ nii, $q$ jagab $p-1$.
6. Vali juhuslik arv $h \in \{ 2,...,p-2 \}$.
7. Arvuta $g:= h^{(p-1)/q} \mod p$.

Algoritmi parameetrid on $(p,q,g)$.

Kasutajaspetsiifilised võtmed:
1. Vali juhuslik täisarv $x$ hulgast $\{ 1,...,q-1 \}$;
2. Arvuta $y:= g^x \mod p$;

$x$ on privaatne võti ja $y$ on avalik võti.

Digitaalne allkirjastamine:
1. Vali juhuslik arv $k$ hulgast $\{1,...,q-1\}$;
2. Arvuta $r := (g^k \mod p) \mod q$. Juhul kui $r=0$, vali uus $k$ ja korda $r$ arvutamist;
3. Arvuta $s := (k^{-1} (H(m) + xr)) \mod q$, kus $m$ on allkirjastatav sõnum ja $H$ on räsifunktsioon. Juhul, kui $s = 0$, vali uus $k$ ja alusta 2. sammust uuesti.
Saadud allkirjaks on $(r,s)$.

Allkirja $(r,s)$ kontrollimine sõnumi $m$ jaoks toimib järgnevalt:
1. Veendu, et $0 < r < q$ ja $0 < s < q$;
2. Arvuta $w := s^{-1} \mod q$;
3. Arvuta $u_1 := H(m) \cdot w \mod q$;
4. Arvuta $u_2 := r \cdot w \mod q$;
5. Arvuta $v := (g^{u_1} y^{u_2} \mod p) \mod q$;
Kui $v = r$, siis digitaalallkiri on kehtiv, vastasel juhul mitte.

Krüpteerimine

Enimkasutatud krüpteerimisalgoritm on täiustatud krüpteerimisstandard (Advanced Encryption Standard - AES).
AES spetsifikatsioon: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf .

Selle algoritmi implementeerimiseks läheb vaja matemaatilisi eelteadmisi lõplikest korpustest.

Ühte baiti (8 bitti) $b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0$ saab esitada polünoomina $b_7 x^8 + b_6 + x^7 + b_5 x^6 + b_4 x^5 + b_3 x^4 + b_2 x^3 + b_1 x^2 + b_0 x^1$, kus $b_i \in \{ 0,1 \} \; i = 0,...,7$.
Tehteid baitidega viiakse läbi lõplikus korpuses GF$(2^8)$ mooduli $x^8 + x^4 + x^3 + x + 1$, mis on taandumatu polünoom.
Baitide liitmine ehk $xor$ operatsioon viiakse läbi vastavate polünoomidega, mille vastavad kordajad liidetakse mooduli 2 järgi.

Olgu $a,b \in \mathbb{Z}$ ja $n \in \mathbb{N}$. Öeldakse, et $a$ ja $b$ on kongruentsed mooduli $n$ järgi ja tähistatakse $a \equiv b \; (\text{mod } n)$, kui $n \lvert b-a$.
Mistahes täisarvude $a$ ja $b$ korral $a \equiv b \; (\text{mod } n)$ parajasti siis, kui $a$ ja $b$ annavad arvuga $n$ jagades sama jäägi.

Tähistame sümboliga $\bar{a}$ kõigi selliste täisarvude hulka, mis on kongruentsed täisarvuga $a$ mooduli $n$ järgi, s.t \[ \bar{a} = \{ b \in \mathbb{Z} \lvert a \equiv b \; (\text{mod} \; n) \} = \{ a+kn \lvert k \in \mathbb{Z} \} \] ja nimetame selliseid hulki jäägiklassideks mooduli $n$ järgi. Ringi elementi nimetatakse pööratavaks, kui tal leidub korrutamise suhtes pöördelement. Kui $ax = xa = 1$ ringis $R$, siis elemente $a$ ja $x$ nimetatakse teineteise pöördelementideks ja tihti kirjutatakse $x = a^{-1}$ või $a = x^{-1}$. Jäägiklassiringi, mille iga nullelemendist (s.o jäägiklassist $\bar{0}$) erinev element on pööratav, nimetatakse jäägiklassikorpuseks. Jäägiklassiring $\mathbb{Z}_n$ on korpus parajasti siis, kui $n$ on algarv.


Täiustatud krüpteerimisstandardis toimub info krüpteerimine 16-baidiste maatriksite kaupa: \[ \begin{pmatrix} b_0 & b_4 & b_8 & b_{12} \\ b_1 & b_5 & b_9 & b_{13} \\ b_2 & b_6 & b_{10} & b_{14} \\ b_3 & b_7 & b_{11} & b_{15} \\ \end{pmatrix} \] Täiustatud krüpteerimisstandardis koosneb viiest tegevusest antud olekumaatriksil:
1.Võtmemaatriksi moodustamine.



2. mittelineaarne tabelasendus, igale olekumaatriksi elemendi $b$ korral leitakse tema multiplikatiivne pöördelement lõplikus korpuses GF$(2^8) = GC(2)[x] / (x^8 + x^4 + x^3 + x + 1)$. Selles korpuses on nulli pöördelement null. Pöördelemendile bitikujul $b_0 b_1 b_2 b_3 b_4 b_5 b_6 b_7$ rakendatakse afiinset teisendust: \[ \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix} \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} s_0 \\ s_1 \\ s_2 \\ s_3 \\ s_4 \\ s_5 \\ s_6 \\ s_7 \end{bmatrix} \] või lühidalt $s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4) \oplus 63_{16}$. Selle teisenduse pöördteisendus on $b = (s \lll 1) \oplus (s \lll 3) \oplus (s \lll 6) \oplus 5_{16}$.

3. Olekumaatriksi reanihked, kus $n$-nda rea elemendid nihutatakse tsükliliselt $n-1$ kohta vasakule.

4. Veergude segamine. Olekumaatriksi igale veeruvektorile rakendatakse teisendust \[ \begin{bmatrix} 2 & 3 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \end{bmatrix} \begin{bmatrix} a_{0,j} \\ a_{1,j} \\ a_{2,j} \\ a_{3,j} \end{bmatrix} = \begin{bmatrix} b_{0,j} \\ b_{1,j} \\ b_{2,j} \\ b_{3,j} \end{bmatrix} \] Igat veergu käsitletakse kui neljaliikmelist polünoomi $b(x) = b_3 x^3 + b_2 x^2 + b_1 x + b_0$, mille kordajad $b_i$ on $GF(2^8)$ elemendid. Vastavaid polünoome korrutatakse polünoomiga $a(x) = 3x^3 + x^2 + x + 2$ mooduli $x^4 + 1$ järgi. Selle polünoomi pöördelement on $a^{-1}(x) = 11x^3 + 13x^2 + 9x + 14$.

5. Vooruvõtme lisamine. Olekumaatriksi iga bait lisatakse XOR võtmemaatriksi vastava elemendiga.

Järgnevalt on toodud AES implementeeriv kood (kirjutatud Javas):