ISSN 0351-6652 Letnik 22 (1994/1995) Številka 6 Strani 354-357
Marija Vencelj:
ŠIFRIRANJE Z JAVNIM KLJUČEM
Ključne besede: matematika, kriptologija, kriptografija, kriptoana-liza, javni ključ, RSA metoda.
Elektronska verzija: http://www.presek.si/22/1238-Vencelj.pdf
© 1995 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
ŠIFRIRANJE Z JAVNIM KLJUČEM
V prejšnji številki Preseka smo spoznali nekaj preprostih tajnopisnih metod. Za večino med njimi je eden največjih problemov prenos šifrirnega ključa Ta pomembni podatek, ki ga potrebuje prejemnik za dešifriranje sporočila, moramo pri teh metodah pogosto menjati, da bi zmedli nepoklicano osebo, ki bi prestregla sporočilo; vsakokrat je treba poskrbeti za varen prenos ključa med pošiljateljem in prejemnikom.
V poznih sedemdesetih letih pa so razvili kriptografske metode, ki ne zahtevajo nikakršnega prenosa ključa. Pravimo jim metode šifriranja z javnim ključem. Srž metode je v tem, da lahko prejemnik povsem javno objavi nekaj števil, ki predstavljajo ključ za šifriranje sporočil, ki bi mu jih kdo želel poslati Samo on pa pozna skrivna števila, s katerimi je moč ta sporočila dešifrirati.
Med metodami šifriranja z javnim ključem je najbolj znana RSA metoda. Za uspešno (varno) delo s to metodo uporabljajo zelo velika števila, zato so tako za šifriranje kot za dešifriranje potrebni računalniki. Tudi z računalniki pa je praktično nemogoč vdor v šifrirni sistem Edini način za zlom šifre je namreč odkritje skrivnih dešifrirnih števil, kijih pozna le prejemnik. V principu je ta števila sicer moč dobiti iz javno objavljenih šifrirnih števil, v praksi pa bi to zahtevalo mesece dela z računalnikom.
Metoda RSA
Metoda nosi ime po začetnicah priimkov Ronalda Rivesta, Adija Shamirja in Leonarda Adlemana s Tehnološkega inštituta Massachusetts v ZDA, ki sojo razvili leta 1978. Njena varnost temelji na dejstvu, da je razmeroma lahko najti zelo velika praštevila in zelo težko razstaviti na prafaktorje števila, ki so produkti velikih praštevil (če poznamo samo produkt). V praksi uporabljajo praštevila, ki se dajo zapisati z najmanj petdeset desetiškimi števkami, njihovi produkti torej z vsaj sto desetiškimi števkami.
Samo težavnost faktoriziranja lahko opazimo celo že pri zelo majhnih številih. Poskusite na primer brez računalnika razstaviti na prafaktorje Število 54 053. Videli boste, da je precej teže priti do rezultata 54 053 = 191 • 283, kot pa ugotoviti, da sta 191 in 283 praštevili in ju zmnožiti.
Kot pri metodah, ki smo jih spoznali zadnjič, tudi pri metodi RSA nadomestimo besedila sporočif s števili. Vsako črko lahko npr. nadomestimo s številom, ki pomeni njeno mesto v abecedi. Pri tem priredimo črkam od A do I števila 00 do 09 namesto 0 do 9. Brez tega previdnostnega ukrepa
bi, denimo, ne vedeli, ali pomeni število 12 Črko M ali par črk BC (ki bo tako predstavljen z 0102). Besedilo z n črkami tako nadomestim z zlepkom n dvomestnih števil, na katerega lahko gledamo kot na 2n— mestno število.
Prejemnikova skrivna števila sta dve veliki praštevili p in q ter število A/, ki je tuje s produktom (p— l)(q — 1). števili, kiju prejemnik javno objavi, sta produkt pq in pozitivno število M z lastnostjo, da je ostanek deljenja števila MN s številom (p — 1}(<7 — 1) enak 1, torej
MN 3 l(mod {p~l)(g- 1))
Javno objavi tudi postopek šifriranja. Vsak, ki mu želi poslati tajno sporočilo, katerega predstavlja število x, naj mu posreduje Število /, ki je ostanek deljenja števila xM s produktom pq. Šifra y je torej najmanjše nenegativno Število, ki ustreza kongruenci
y = xM(mod pq)_
Pri tem mora število x izpolnjevati pogoj 0 < x < pq. (Ta pogoj izpolnjuje tudi y.) Če je sporočilo predolgo, ga je potrebno razbiti na kose, ki predstavljajo Števila, manjša od pq, in izvesti navedeni račun za vsak kos posebej.
Prejemnik deŠifrira sporočilo tako, da izračuna ostanek deljenja števila yN s produktom pq: kjer je N njegovo skrivno število. Originalno število x (sporočilo) je torej najmanjše nenegativno Število, za katerega velja
x = yW{mod pq).
Primer, Za ilustracijo metode ne bomo uporabiti velikih števil, ki so v navadi v praksi; potek bomo lahko pregledneje predstavili z majhnimi števili. Zaradi preglednosti se bomo tudi izognili podrobnemu računanju, ki ga lahko opravite sami.
Naj si je prejemnik za skrivna števila izbral p = 11, q = 13 in N — 1. Ne spreglejmo, da je število IV tuje s številom (p — l)(q — 1) = 120. iz teh števil izračuna (z uporabo Evklidovega algoritma ali kako drugače), da je 103 najmanjše pozitivno število M, ki izpolnjuje pogoj 7M = l(mod 120).
Nato prejemnik objavi naslednje sporočilo: "Kdor mi Želi poslati tajno sporočilo, ki ga na običajni način (zamenjava črk z dvomestnimi števili) predstavlja število X, naj mi posreduje ostanek deljenja števila x103 s številom 143."
Sedaj je na vrsti pošiljatelj. Recimo, da želi poslati prejemniku sporočilo
SOS, ki ga predstavlja število 181518 (S=18, 0=15). Ker je število preveliko, ga mora razbiti na tri kose, manjše od 143, to je na števila 18, 15, 18. Nato izračuna, da je 18103 = 112(mod 143) in 15103 = 141(rnod 143). (S tem je kar nekaj dela, če boste računali peš, z računalnikom pa boste hitro gotovi.) Odposlati mora torej števila 112, 141, 112,
Ko pride to sporočilo v roke prejemniku, ta izračuna 1127 = 18(mod 143) in 1417 = 15{mod 143) in v nizu 18, 15, 18 prepozna klic na pomoč.
Gotovo ste se ob tem vprašali, zakaj metoda deluje. Kako to, da opisano zaporedje šifrirnega m dešifrirnega postopka vrne na koncu originalno sporočilo7 Podrobnejša razlaga razlogov bi bila za večino Presekovih bralcev pretežka Za tiste radovednejše pa le povejmo, da je skrita v naslednjem izreku
tzrek. Če sta p in q različni praštevili in je
MN = l(mod (p - l)(q - 1)).
potem velja
{xM)W = x(mod pq).
Podpisovanje
Pomemben del tajnega sporočila pa tudi vsakega drugega dokumenta je podpis, ki potrjuje njegovo verodostojnost Ker pri pošiljanju sporočil po elektronski pošti ne moremo prenašati fizičnega podpisa, je potrebno poskrbeti za drugačno potrjevanje pristnosti.
Ena dodatnih lastnosti metode RSA je prav varno prenašanje podpisa pošiljatelja. Glede na to, da so javna šifrirna števila prejemnika splošno znana, bi npr. lahko kdo prejemniku poslal lažno šifrirano sporočilo, podpisal pa verodostojno drugo osebo in s tem prejemnika zavedel.
Spet si kar na primeru oglejmo, kako lahko z metodo RSA kaj takega preprečimo.
Denimo, da si Urša in Vinko izmenjujeta tajna sporočila. Označimo z M(j in a\j = (pq)u ter My in ay = (pq)\/ Uršini oziroma Vinkovi javni Šifrirni števili Nadalje naj bosta Ny in N\y njuni skrivni dešifrlrni števili. Pa naj želi Vinko poslati Urši svoj podpis, ki ga predstavlja število v. V ta namen šifrira podpis s svojim skrivnim številom N\/ in svojim javnim številom a\/, to je, izračuna najmanjše nenegativno število z, ki izpolnjuje pogoj z = v^fmod a\/). Urša dobljeno sporočilo dešifrira s ključem, ki ga predstavljata Vinkovi javni šifrirni števili M\y in a\/, to je, poišče najmanjše
nenegativno število w, ki izpolnjuje pogoj w = zMv(mod av). Ker je IV)MV _ {VMV^NV ;n zarad| ¡zreka na koncu prejgnjega razdelka, je w ~ v. Urša torej ve, da je sporočilo posla! Vinko, saj bt uporaba vsakega drugega ključa kot ki ga pozna fe Vinko, dala rezultat, različen od v.
Vendar tako Šifriran podpis lahko prebere še kdo drug razen Urše. Da bi se temu izognit, lahko Šifrira Vinko svoj podpis dvakrat; najprej s ključem (A/y, av) in nato še z Uršinim javnim ključem (My, ay). Le Urša lahko prebere podpis z zaporedno uporabo ključev (Ny, 3y) in (Mv, av).
Varnost metode RSA
Iz vsega, kar smo izvedeli o metodi RSA, sledi, da je zlom šifre mogoč, če vsiljivcu uspe faktorizirati javno objavljeno število pq. Potem lahko najde (p —l)(g —1} in, z uporabo Evklidovega algoritma za par števil {p — l)(q — 1} ter javni eksponent M, izračuna skrivno dešifrirno stevifo N. Z njim pa lahko na enak način kot prejemnik dešifrira tajnopis. Torej je pomembno, da sta uporabljeni praštevili pin q dovolj veliki, daje faktorizacija produkta pq praktično nemogoča.
Zaenkrat v praksi velja, da morata imeti uporabljeni praštevili vsaj petdeset desetiških mest, hitri razvoj računalniških metod za razstavljanje pa sicer trenutno zagotavlja resnično varnost, če imata števili p in q vsaj po petinosemdeset mest. Vendar predstavlja že samo Šifriranje in desifriranje s tako velikimi števili izredno zamudno delo, celo za najhitrejše računalnike.
Razvitje RSA metode je povzročilo mrzlično iskanje hitrih algoritmov za razcep števil na prafaktorje.
Kakršnekoli napovedi za bodoče so seveda nehvaležne. Vsekakor se obe strani, iskalci metod za generiranje velikih praštevil in iskalci metod za hitro razstavljanje velikih števil, trudita premagati druga drugo. Svoje pa prispevajo tudi čedalje hitrejši računalniki.
Marija Vencelj