Šī raksta mērķis ir populārzinātniskā valodā paskaidrot kriptogrāfijas pamatjēdzienus tieši asimetrisko kriptosistēmu kontekstā. Šeit ietvertā informācija ir ļoti ierobežota, tādēļ, lai dziļāk izprastu aprakstīto iedeju tieši matemātisko pusi, noteikti jāsmeļas zinības speciālā literatūrā un jāseko jaunumiem nozares attīstībā. Šis raksts domāts plašam interesentu lokam, taču, to rakstot, tika pieņemts, ka lasītājam tomēr ir elementāras zināšanas diskrētajā matemātikā un algoritmu teorijā.
[b]Ievads[/b]
Jau kopš seniem laikiem cilvēki ir centušies ierobežot nesankcionētu piekļuvi konfidenciālai informācijai. Attīstoties civilizācijai un uzkrājoties zināšanām un pieredzei, cilvēkiem arvien svarīgāka kļuva informācijas drošība: sākumā militāra un politiska rakstura informācijai, vēlāk arī komerciāliem un privātiem noslēpumiem. Jau tajos senajos laikos tika meklētas metodes, kā ērti un ātri padarīt informāciju nepieejamu citiem arī tad, ja tā nokļuvusi nevēlamu personu rokās. Tā radās pati primitīvākā kriptogrāfija, no kuras dažas atziņas izmantojam vēl šobaltdien. Dažādos vēstures posmos kriptogrāfiskās (šifrēšanas) metodes bijušas dažādas, tomēr par klasiskām uzskata Cēzara šifru, Hilla shēmu, kā arī citu (mainītu) alfabētu izmantošanu. Tomēr vairumu šos kriptosistēmu pat mūsdienu vidusskolēns spētu uzlauzt dažu stundu laikā.
Pievērsīsim uzmanību vispārīgai šāda veida kriptosistēmas darbībai. Lai sistēma darbotos, ir nepieciešamas trīs pamatlietas: šifrējamā informācija (turpmāk to dēvēsim par atklātu tekstu), šifra atslēga un pats šifrēšanas princips likums, pēc kura notiek šifrēšanas process, respektīvi, atslēgas iedarbība uz atklāto tekstu. Šifrējot atklāto tekstu, iegūst šifrētu tekstu, ko iespējams atšifrēt, izmantojot to pašu atslēgu. Lai arī šāda veida kriptosistēmas jūtami palielina informācijas drošību, tomēr pastāv kāds ļoti būtisks trūkums kā lai nogādā atslēgu droši? Ir nepieciešams kaut kāds pilnīgi drošs sakaru kanāls šīs (slepenās) atslēgas sūtīšanai. Ja ir pieejams šāds kanāls, tad kāpēc informāciju būtu vispār jāšifrē? To visu būtu iespējams nosūtīt pa šo drošo kanālu. Visas kriptosistēmas, kurām piemīts šāds trūkums, mēdz dēvēt par slepenās atslēgas jeb simetriskās atslēgas kriptosistēmām.
Gāja laiks, un cilvēki sāka aizdomāties par šo problēmu. Cik nedroši gan ir sūtīt lādīti kopā ar atslēgu jebkurš, ar šo pašu atslēgu var atslēgt lādīti; jāiegūst tikai pati lādīte un tās atslēga. Pagājušā gadsimta 70-to gadu sākumā radās atklājums, kam bija milzīga ietekme uz visu kriptogrāfijas attīstību. Tikai radīts kriptosistēmas princips, kurā tiek lietotas divas atslēgas ar pirmo iespējams lādīti aizslēgt, bet ne vairs atslēgt; ar otru tikai atslēgt. Tas nozīmē, ka nav vairs jāuztraucas par pirmās atslēgas likteni; to var pat dot visiem gribētājiem, kas arī vēlas nosūtīt aizslēgtu lādīti saņēmējam. Citiem vārdiem sakot, tikai radīta asimetriskās atslēgas kriptosistēmas koncepcija. Sistēmas darbību nodrošina divas atslēgas publiskā un slepenā -, pie tam no publiskās ir gandrīz neiespējami iegūt privāto atslēgu, kaut arī abas šīs atslēgas, protams, ir matemātiski saistītas. Publisko atslēgu var brīvi darīt zināmu citiem, tāpēc jebkurš var aizsūtīt saņēmējam šifrētu informāciju, taču tikai saņēmējs ar savu slepeno atslēgu spēj atšifrēt šo informāciju.
1973. gadā tika izstrādāta pirmā ne-slepenās atslēgas kriptosistēma, ko paveica Lielbritānijas Valdības Telekomunikācija galvenās pārvaldes speciālisti, tomēr šī sistēma, (vēlāk pazīstama kā Diffie-Hellman atslēgu apmaiņas shēma) tika turēta slepenībā; par tās eksistenci sabiedrība uzzināja tikai 90-to gadu beigās.
Neatkarīgi no Britu valdības 1977. gadā trīs zinātnieki – Ronald Lorin Rivest, Adi Shamir un Leonard Max Adleman – radīja asimetriskās atslēgas metodi, ko, saīsinot viņu uzvārdu pirmos burtus, nodēvēja par RSA.
Taisnības labad jāatzīst, ka idejas par vienpusīgām funkcijām bija jau sastopamas pat 19. gadsimta beigās angļu ekonomista William Stanley Jevons darbos. Tieši viņš bija pirmais, kas saprata tādu darbību eksistenci, kuras ir viegli izpildīt tiešā virzienā, bet ļoti grūti apgrieztā, savā darbā pretnostatot skaitļu reizināšanas un sadalīšanu pirmreizinātājos (faktorizēšanu). Līdz pat mūsu dienām asimetrisko kriptosistēmu darbības princips ir saglabājies nemainīgs.
[b]Matemātiskie pamatprincipi[/b]
Gandrīz jebkurš cilvēks vēl no sākumskolas laikiem atceras reizināšanas paņēmienu stabiņā. Redzams, ka šādā pat veidā iespējams sareizināt pat ļoti lielus skaitļus. Diemžēl apgrieztā darbība skaitļa sadalīšana pirmreizinātājos jeb faktorizēšana prasa nesalīdzināmi vairāk pūļu. Visa problēma slēpjas apstāklī, ka mums ir zināms efektīvs algoritms reizināšanai, bet līdz šim tāds nav zināms sadalīšanai reizinātājos, tādēļ reizināšanu var uzskatīt par vienvirziena darbību. To pašu var pasacīt arī citādi: pārbaudīt, vai dotie skaitļi ir konkrētā skaitļa pirmreizinātāji, ir pavisam viegli, taču, ejot pretējā virzienā, būtu jāpārbauda katrs iespējamais pirmreizinātājs, kas prasītu veikt neaprakstāmi daudz darbību. Kā piemēru apskatīsim divu (vienāda garuma) [img]/images/upload/rsaimage001.gif[/img] ciparu garu pirmskaitļu sareizināšanu. Pieņemsim, ka reizinājums ir [img]/images/upload/rsaimage002.gif[/img] ciparu skaitlis. Visneizdevīgākajā gadījumā būs jāveic aptuveni [img]/images/upload/rsaimage003.gif[/img] darbību (jeb vispārīgi [img]/images/upload/rsaimage004.gif[/img], kur [img]/images/upload/rsaimage005.gif[/img] ir reizinājuma skaitļa ciparu skaits), kas mūsdienu tehnikai ir smieklīgi viegls uzdevums. Apgrieztai darbībai, izmatojot vienkārši rupja spēka piemeklēšanu, nepieciešams ap [img]/images/upload/rsaimage006.gif[/img] darbību; redzams, ko reālā laikā principā nav iespējams realizēt. Runājot matemātiski, reizināšanas algoritmu sauc par polinomiāla izpildes laika; faktorizēšanas par eksponenciāla. Atšķirība starp šiem diviem algoritmu tipiem izpaužas pie lielākiem ievada parametriem [img]/images/upload/rsaimage005.gif[/img] – eksponenciāla laika pieaug ļoti strauji (kā jau eksponentfunkcija) un ir par pamatu asimetriskajām kritposistēmām.
RSA algoritms par pamatu izmanto liela salikta skaitļa faktorizēšanas neiespējamību reālā laikā. Pieņemsim, ka esam izvēlējušies divus lielus, atšķirīgus un vienāda garuma pirmskaitļus, ko apzīmēsim ar [img]/images/upload/rsaimage007.gif[/img] un [img]/images/upload/rsaimage008.gif[/img]. Aprēķināsim [img]/images/upload/rsaimage009.gif[/img]. Pēc tam aprēķināsim skaitļa [img]/images/upload/rsaimage010.gif[/img] Eilera funkciju [img]/images/upload/rsaimage011.gif[/img], ko definē kā to naturālo skaitļu, kas mazāki vai vienādi ar [img]/images/upload/rsaimage010.gif[/img] un ir savstarpēji pirmskaitļi ar to, skaitu. Tā kā skaitlim [img]/images/upload/rsaimage010.gif[/img] ir tikai divi pirmreizinātāji [img]/images/upload/rsaimage007.gif[/img] un [img]/images/upload/rsaimage008.gif[/img] -, tad [img]/images/upload/rsaimage013.gif[/img]. Pēc tam jāizvēlas kāds naturāls skaitlis, lai [img]/images/upload/rsaimage014.gif[/img] un [img]/images/upload/rsaimage015.gif[/img] ar būtu [img]/images/upload/rsaimage011.gif[/img] savstarpēji pirmskaitļi. Nākamajā solī jāatrod tāds skaitlis [img]/images/upload/rsaimage016.gif[/img], kas apmierinātu kongruenci [img]/images/upload/rsaimage017.gif[/img].
Šeit nedaudz jāiepazīstas ar dažiem matemātiskiem aspektiem. Pirmkārt, ar [img]/images/upload/rsaimage018.gif[/img] operatoru, kas atrod dalījuma atlikumu. Kā triviālu piemēru apskatīsim izteiksmi [img]/images/upload/rsaimage019.gif[/img]. 10 nedalās ar 3, taču tuvākais skaitlis, kas dalās, ir 9; tātad atlikums ir 1. Ievērosim sakarību: ja 10 pieskaita 3, 6, 9, 12,… (vispārīgi [img]/images/upload/rsaimage020.gif[/img]), kur [img]/images/upload/rsaimage021.gif[/img] naturāls skaitlis, tad atlikums, dalot ar 3, nemainās. Mēs varam rakstīt, ka [img]/images/upload/rsaimage022.gif[/img], ar to saprotot, ka gan 10 dalot ar 3, gan 13 dalot ar 3, iegūs vienādu atlikumu: 1. Šo īpašību tad arī sauc par kongruenci pēc moduļa. Jāpiebilst arī, ka no sakarības [img]/images/upload/rsaimage022.gif[/img] var iegūt [img]/images/upload/rsaimage023.gif[/img], kur šajā gadījumā [img]/images/upload/rsaimage024.gif[/img].
Atgriezīsimies pie kongruences piemēra [img]/images/upload/rsaimage017.gif[/img]. To iespējams pārveidot kā [img]/images/upload/rsaimage025.gif[/img], kur [img]/images/upload/rsaimage021.gif[/img] naturāls skaitlis; citiem vārdiem sakot, [img]/images/upload/rsaimage026.gif[/img] ir jādalās ar [img]/images/upload/rsaimage027.gif[/img].
Skaitli [img]/images/upload/rsaimage015.gif[/img] sauc par publisko eksponentu un [img]/images/upload/rsaimage005.gif[/img] – par moduli; tos abus padara pieejamus ikvienam. Skaitli [img]/images/upload/rsaimage016.gif[/img] sauc par privāto eksponentu; to tur slepenībā. Abus pirmskaitļus – [img]/images/upload/rsaimage007.gif[/img] un [img]/images/upload/rsaimage008.gif[/img] – drošā veidā iznīcina (izdzēš) kopā ar visām starpvērtībām.
Šifrēšanu izpilda kā [img]/images/upload/rsaimage028.gif[/img]; apgriezto darbību atšifrēšanu kā [img]/images/upload/rsaimage029.gif[/img], kur [img]/images/upload/rsaimage030.gif[/img] ir nešifrētais skaitlis (atklātais teksts) ([img]/images/upload/rsaimage031.gif[/img]); [img]/images/upload/rsaimage032.gif[/img] – šifrētais.
Kā piemēru izveidosim RSA modeli, kas darbosies ar ļoti mazām parametru vērtībām.
1) Pieņemsim, ka [img]/images/upload/rsaimage033.gif[/img], [img]/images/upload/rsaimage034.gif[/img]; [img]/images/upload/rsaimage035.gif[/img].
2) Eilera funkcija skaitlim [img]/images/upload/rsaimage005.gif[/img] ir [img]/images/upload/rsaimage036.gif[/img].
3) Par [img]/images/upload/rsaimage015.gif[/img] izvēlēsimies, piemēram, skaitli 13, jo[img]/images/upload/rsaimage037.gif[/img] un [img]/images/upload/rsaimage038.gif[/img].
4) Par [img]/images/upload/rsaimage016.gif[/img] izvēlēsimies, piemēram, skaitli 325, jo[img]/images/upload/rsaimage039.gif[/img] dalās ar 352.
5) Pēdējais solis ir publicēt skaitļus [img]/images/upload/rsaimage015.gif[/img] un [img]/images/upload/rsaimage010.gif[/img].
Pieņemsim, ka jānošifrē skaitlis [img]/images/upload/rsaimage040.gif[/img]. Lai to veiktu, aprēķināsim [img]/images/upload/rsaimage041.gif[/img] , izmantojot publisko eksponenta [img]/images/upload/rsaimage042.gif[/img] vērtību un moduli [img]/images/upload/rsaimage010.gif[/img]. Veikt pretējo darbību atšifrēšanu izdara kā [img]/images/upload/rsaimage043.gif[/img], šoreiz izmantojot slepenā eksponenta vērtību [img]/images/upload/rsaimage044.gif[/img]. Redzams, ka iegūts sākotnējais skaitlis.
[b]RSA drošība[/b]
Pirmais apstāklis, par kuru būtu jārunā asimetrisko kriptosistēmu drošības kontekstā, neapšaubāmi ir fakts, ka vēl līdz šim nav izdevies pierādīt tāda algoritma neesamību, kas spētu risināt tādus uzdevumus kā, piemēram, skaitļu faktorizēšanu polinomiālā laikā. Tiesa, 30 gadu laikā, kopš asimetrisko kripstositēmu radīšanas, vēl nevienam nav arī izdevies šādu algoritmu radīt un vairums sliecas domāt, ka tas principā nav iespējams. Tās ir tikai hipotēzes, kas rada dažādas spekulācijas par asimetrisko kriptosistēmu drošību nākotnē. Attīstoties zinātnei, var pienākt brīdis, kad šāds algoritms tiešām tiek atklāts, un, ja tajā mirklī plaši tiek pielietotas aprakstītās kriptogrāfiskās metodes, tas var radīt milzīgu sajukumu un zaudējumus pasaulē.
No šī brīža viedokļa raugoties, RSA var atzīt par ļoti drošu, taču ar noteikumu, ka tiek nodrošināta atbilstoša sistēmas implementācija un atslēgu garums. Praktiskās implementācijas detaļās un RSA darbības principā no skaitļu teorijas viedokļa neiedziļināsimies tas prasītu vismaz 10 reižu lielāku raksta apjomu, bet atslēgu garumu gan apskatīsim, lai sniegtu aptuvenu priekšstatu. Tiek uzskatīts, ka minimālais [img]/images/upload/rsaimage010.gif[/img] parametra lielums ir vismaz 1024 biti (~309 cipari decimālajā sistēmā) pilnīgi pietiekami elementārai informācijas aizsardzībai. Teorētiski [img]/images/upload/rsaimage010.gif[/img] parametra lielums nav ierobežots, un, palielinoties tehnikas veiktspējai, jau tiek lietotas arī 2048 un pat 4096 bitu atslēgas. Saprotams, ka pirmreizinātājus [img]/images/upload/rsaimage007.gif[/img] un [img]/images/upload/rsaimage008.gif[/img] arī jāizvēlas aptuveni vienāda garuma, pie tam tādi, lai tie nebūtu tuvi viens otram. Publisko eksponentu [img]/images/upload/rsaimage015.gif[/img] parasti izvēlas relatīvi mazu; mazākais iespējamais ir 3 (to parasti izmanto viedkartēs), taču standartā izvēlas vērtību 65537. Privātā eksponenta garums parasti ir salīdzināms ar moduļa [img]/images/upload/rsaimage010.gif[/img] garumu.
Kā jau tikai minēts, RSA ir jāuzskata par drošu, kaut arī teorētiski ir vismaz divas fundamentālas iespējas to uzlauzt. Pirmkārt, acīmredzami, pietiek sadalīt moduli [img]/images/upload/rsaimage010.gif[/img] tā pirmreizinātājos [img]/images/upload/rsaimage007.gif[/img] un [img]/images/upload/rsaimage008.gif[/img], no kā iespējams viegli iegūt privāto eksponentu [img]/images/upload/rsaimage016.gif[/img]. Līdz pat šai dienai nav publiski nav zināms neviens pietiekami efektīvs algoritms vispārīgam gadījumam.
Otra iespēja ir izmatot sakarību [img]/images/upload/rsaimage028.gif[/img]. Zinot šifrēto tekstu [img]/images/upload/rsaimage032.gif[/img], publisko eksponentu [img]/images/upload/rsaimage015.gif[/img] un moduli [img]/images/upload/rsaimage010.gif[/img], teorētiski ir iespējams iegūt atklāto testu [img]/images/upload/rsaimage030.gif[/img]. Tas dotu iespēju lasīt šifrētu informāciju, nemaz nezinot privāto eksponentu [img]/images/upload/rsaimage016.gif[/img]. Tiesa, arī šajā gadījumā nav zināms efektīvs algoritms šāda uzdevuma veikšanai.
[b]Elektroniskais paraksts[/b]
Latvijā jau kādu laiku ir pieejama elektroniskā paraksta iespēja. Daudzi cilvēki, iespējams, nezina, bet arī šeit tiek izmantota asimetriskā krisptosistēmu darbības teorija. Pieņemsim, ka vēlamies parakstīt kādu informāciju, teiksim, skaitli, 19 (izmantosim tos pašus parametrus no RSA darbības piemēra):
1) Aprēķinām [img]/images/upload/rsaimage045.gif[/img]. Citiem vārdiem sakot, parakstāmā informācija tiek šifrēta, izmantojot privāto eksponentu [img]/images/upload/rsaimage016.gif[/img].
2) Tiek publicēts gan skaitlis 19, gan 389.
Lai pārbaudītu paraksta autentiskumu, jāaprēķina [img]/images/upload/rsaimage046.gif[/img], izmantojot publisko eksponentu. Redzams, ka jebkurš parakstu var pārbaudīt, bet tikai privātās atslēgas zinātājs arī parakstīt. Šeit šifrētais skaitlis, gan nešifrētais sakrīt, tāpēc parakstu var uzskatīt par autentisku. Tieši pēc šādas shēmas arī darbojas elektroniskais paraksts.
[b]Nobeigums[/b]
Vairāk nekā 30 gadus cilvēkiem ir iespēja relatīvi droši aizsargāt sev piederošu informāciju no nesankcionētas piekļuves; elektroniskais paraksts, kas Latvijā vēl ir jaunums un līdz šim nav guvis plašu popularitāti, sniedz jaunas iespējas, bet visam šai pasaulē piemīt savi trūkumi. Ja papīra parakstu vēl aizsargā tas, ka eksperti tomēr spēj atšķirt autentisku no viltojuma, tad elektroniskā gadījumā šādas iespējas nav, kas sevī slēpj potenciālas briesmas. Teorētiskā iespēja radīt viltotu parakstu, ko nekādi nav iespējams atšķirt no oriģināla, patiešām liek aizdomāties…
Šeit varētu uzdot retorisku jautājumu vai Jūs esat gatavi uzticēties kam tādam, kā drošība nav pierādīta?
Avoti:
http://www.ladlass.com/intel/archives/010256.html;
http://www.di-mgt.com.au/rsa_alg.html;
Ç . K. Koç, High-Speed RSA Implementation, Technical Report TR 201, RSA Laboratories, November 1994.