ISSN 0351-6652 Letnik 30 (2002/2003) Številka 5 Strani 274-280 Martin Pecar: VIZUALNA KRIPTOGRAFIJA - ŠUM SKRIVNOSTI Ključne besede: računalništvo, matematika, informacijski sistemi, kri-pografija, delne slike. Elektronska verzija: http://www.presek.si/30/1524-Pecar.pdf © 2003 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo VIZUALNA KRIPTOGRAFIJA - Zagotovo k t c1 že kdaj brali zgodbo o zakopanem zakladu. Ta zaklad je običajno gusarski, kapitan, kriptograf samouk, pa dovolj premeten, da je zemljevid, ki vodi do zaklada, raztrgal na več kosov. Predstavljajte si, da ravno vi izhajate iz neupogljive rodbine kapitanov Sinjebradcev, katerim so legende pripisovale bajna bogastva. To bogastvo vas žal ni doseglo, saj ga je eden od Sinjebradcev kot zgleden gnsarski kapitan namesto v sef švicarske banke zaklad zakopal v nedrja zemlje enega od otokov. Na srečo pa na podstrešju najdete del zemljevida! Najprej si oglejmo, s čim se sploh ukvarja kriptografija. Pošiljatelj ima sporočilo, polno skrivnih informacij, zato ga po izbranem šifrirnem sistemu zašifrira (raztrga zemljevid) in dobi tajnopis. Ta tajnopis potem nekako pošlje naslovniku, ki ga. odšilrira (zloži kose zemljevida) in prebere sporočilo. Med pošiljanjem na tajnopis običajno prežijo napadalci, ki bi se radi dokopali do skrivnih informacij ali pa naslovniku podtaknili lažne informacije. Kriptografi ves čas seveda tekmujejo v sestavljanju in izboljševanju šifrirnih sistemov ter iskanju napadov na te sisteme. Vsi šifrirni sistemi, ki sc zanašajo na raamsko varnost, temeljijo na tem, da po določenem sistemu "premešajo" informacijo oziroma sporočilo. Ključ imenujemo podatke (parametre), ki v okviru danega šifrirnega sistema. (algoritma) natančno določajo, kako iz sporočila narediti tajnopis in kako potem vrniti premešano informacijo oziroma tajnopis v prvotna olilikfj. Ključ je običajno precej krajši od sporočila, sistem pa tem boljši, čim več možnih ključev mora napadalec preizkusiti na poti do rešitve. Ob tem je smiselno upoštevati Kcrckhoffov princip, ki predpostavlja, da napadalec pozna uporabljeni šifrirni sistem, ne pa tudi ključa. Napadalec ve, kdaj je prišel na cilj: ko dobi tajnopis, razvozlan po določenem sistemu, smiseln pomen, je to zelo verjetno izvirno sporočilo. Verjetnost, da bi dobil smiselno, a napačno sporočilo, je neznatna, če je le tajnopis dovolj dolg. Lahko pokažemo, da je pri sistemu, kjer vsako črko nadomestimo z neko drugo oziroma zamenjamo abecedo, za verodostojnost smiselnega angleškega sporočila potrebna dolžina približno 25 črk. ŠUM SKRIVNOSTI —■^jf---— . Vrnimo se k zakopanemu zakladu. Če je najdeni del zemljevida dovolj velik, boste lahko prepoznali otok. Na najdenem delu pa žal ni označenega mesta, kje točno je zaklad zakopan. Gotovo bi vam skrito bogastvo prišlo zelo prav, zato lahko vzamete kramp in lopato, se odpravite na pravi otok ter vsega prekopljete. Kriptograii bi to imenovali napad z grobo silo, saj morate v okviru informacije, ki jo imate (uporabljeni šifrirni sistem oziroma ime otoka), preizkusiti vse možnosti (uporabiti vse mogoče ključe, oziroma prekopati vsak kvadratni meter). Če boste problemu namenili dovolj najlepših let svojega življenja, boste zaklad prej ali slej našli. Vsi, ki želite zakopati zaklad na skrivnem mestu, pa lahko iskalcem še bolj otežite delo, če boste le prebrali nadaljevanje članka. Seveda ga lahko preberete tudi iz gole radovednosti. Ker nismo gusarji stare šole, bomo zemljevide namesto na. pergament risali na prosojnice. Neuki Sinjebradec bi zemljevid na prosojnici verjetno narisal takole (glej sliki 1 in 2): na eno prosojnim sliko otoka, na drugo pa križec, ki označuje zakopani zaklad. X Slika 1. Zemljevid otoka. Slika 2. Križec označuje skriti zaklad. Ko prosojnici poravnamo in prekrijemo, je skrivnost razkrita. Tudi vsaka prosojni ca zase razkrije nekaj informacije. Tako nam prva razkrije, na katerem otoku nas čaka zaklad. V nadaljevanju se bomo naučili, kako prosojnici porisati tako, da z vsake posebej nihče ne bo mogel pridobiti nikakršne informacije, obe skupaj pa bosta razkrili skrivnost (takorekoč 0 + 0 = 1). V prejšnjem stoletju so se kriptograii domislili, kitko informacijo zakriti tako, da je brez ključa nihče ne bo mogel razkriti. V kriptogra.fi j i teinu pravimo popolna varnost. Dosežemo jo tako, da informacijo "zli-jemo" s povsem naključnimi podatki. Tako onemogočimo napadalce, saj morajo le-1 i odstraniti naključne podatke, s čimer pa lahko dobijo povsem drugačno sporočilo (glej primer 1), Ob danem tajnopisu so vsa sporočila enake dolžine enako verjetna. V tajnopisu lahko najdeš, karkoli iščeš, zato ni več samo ene smiselne rešitve. Tajnopis pa odšifriramo tako, da odstranimo prej dodane naključne podatke. Primei' 1. Pravi ključ je ključnega pomena, četudi je naključen. k r u h = P (1. sporočilo) v i no = Pf (2. sporočilo) a« k f = K (1. ključ) 11 b s ž = K' = K + P - P' (2. ključ) lk li o = C = P + /f (tajnopis) 1 k h o — C — P' + K' (tajnopis) V primeru 1 se zlivanje istoležnih črk (navpično) izvede kot seštevanje zaporednih številk črk v abecedi (Lk7 + 'a' = 'l7, saj je 12 + 1 = 13), kjer se ta ciklično ponavlja (za 'ž' pride spet La1). Če napadalec prestreže tajnopis C, ne more določiti sporočila, saj sta oba ključa K in K' (s tem pa tudi sporočili P in P') enako verjetna, saj sta. naključna. Kdor pa pozna ključ, lahko odkrije sporočilo tako, da od tajnopisa odšteje ključ. Največji problem pri tern šifrirnem sistemu je dolžina ključa - ključ je enako dolg kot sporočilo samo. Pri drugih sistemih je ključ običajno bistveno krajši, npr. pri enoabecedni zamenjavi je potrebno poznati le zamenjavo za vsako črko, pa lahko s temi manj kot 30 podatki zašifriramo in odšifriramo celotno knjigo. Opisana sheina za dosego popolne varnosti se imenuje enkratni ščit (angj, one-time-pad), saj ključ kakor ščit prekrije podatke, uporabimo pa ga lahko samo enkrat (tudi vitezi so morali polomljene ščite zamenjati). Če bi ga uporabljali večkrat, bi napadalec lahko podtaknil njemu poznano sporočilo P, potem pa iz prest.reženega tajnopisa C izračunal ključ K = = C — P. Če je ključ razkrit, sistem ne ponuja nobene varnosti več. Vemo, da vsako sporočilo lahko zapišemo v dvojiškem zapisu, torej kot zaporedje ničel in enic. Prekrivanje z enkratnim ščitom se v dvojiškem zapisu na istoležnih bitih izvede kot dvojiški izključni (ekskluzivni) ali (XOR - glej tabelo ]). Izvorno sporočilo razkrijemo tako. da tajnopis še enkrat prekrijemo s ključem, saj je pri dvojiškem zapisu seštevanje enako odštevanju. Leta 1994 sta se znana kriptografa Adi Shamir, soiznajditelj sistema javne kriptografije RSA, in Moni Naor domislila vizualne kriptografije. Ideja je podobna enkratnemu ščitu, le da namesto zaporedja bitov uporabimo ravnino, tlakovano s črnimi in belimi ploščicami, ki predstavljajo vrednosti bitov. Poleg tega pa namesto operacije 'izključni ali' (XOR) uporabimo operacijo navadni ali (OR. - glej tabelo 2). XOR 0 1 0 0 1 1 1 0 OR 0 1 0 0 1 1 1 1 Tabela i. Izključni ali. Tabela 2. Ali. Na ta način slike zašifriramo, ko pa jih odšifriramo, so malce spremenjene, a še vedno prepoznavne. Najpomembneje pa je, da je vizualna kriptografija po sistemu enkratnega ščita podedovala popolno varnost. To pomeni, da napadalec ne more prepoznati zašifrirane slike, četudi ima še tako veliko časa in računske moči. Slaba stran popolne varnosti pa je, da je ključ prav tako dolg (obsežen) kot samo sporočilo; zaradi tega ni bistvene razlike med ključem in zašifriranim sporočilom (primerjaj sliki 3 in 4). Poglejmo si idejo malce podrobneje: sliko bomo razstavili na dve različni, a enako veliki delni sliki (glej sliki 3 in 4). Vsako točko (angl. pixel) originalne slike bomo na obeh delnih slikah na istoležnih mestih nadomestili s ploščicama, ki imata eno polovico belo, drugo pa črno (glej tabelo 3). Na prvi delni sliki bomo ploščico obrnili naključno, na drugi pa bo njena lega odvisna ob barve originalne točke in lege prve ploščice. Če je bila originalna točka bela, bo lega druge ploščice enaka legi prve, sicer pa jo položimo zrcalno. Z malo razmisleka ugotovimo, da sta legi obeh ploščic naključni, saj smo za prvo to privzeli, drugo pa smo položili glede na prvo, ki leži naključno. verjetnost p = 0.5 p = 0.5 na prvi delni sliki B n originalna slika črno belo črno belo na drugi delni sliki 1 D m [1 Tabela 3. Po shemi točko za točko postopno gradimo delni sliki. Dešifriranje poteka nekoliko drugače. Predstavljajmo si, da mrežo ploščic narišemo na prosojnico, nato pa, če je ploščica (oz. njen del) črna, ustrezajoči del na prosojnici pobarvamo s črno barvo. Potem obe prosojnici prekrijemo. Kjer je bila vsaj ena od prosojnic pobarvana, vidimo črno, drugje pa je prosojno. Kjer se prekrijeta enako obrnjeni ploščici (npr. prva v zgornji vrstici in druga v spodn ji vrstici tabele 3), tam oko majhno črno-belo polje vidi kot sivo. Kjer pa se prekrijeta različno obrnjeni ploščici (npr. prva v zgornji vrstici in prva v spodnji vrstici tabele 3), vidimo črno polje. Originalno sliko torej razbijemo na dve enako veliki delni sliki, na katerih jc vsaka točka naključno bela aH črna (to imenujemo šum). Ko obe delni sliki prekrijemo, zagledamo skrito podobo. Ta podoba je malce spremenjena (glej sliko 5), saj tam, kjer so bile na originalni sliki bele ploščice, dobimo napol črne. Ce so ploščice dovolj majhne (oziroma, če gledamo od daleč), oko napol črne ploščice vidi kot sive. Torej iz črno-bele slike dobimo črno-sivo sliko. Kljub tej izgubi kontrasta so enostavne slike še vedno prepoznavne. Slika f>. Originalna slika. Slika 5. Zlila slika oziroma prekriti delni sliki razkrijeta skrivnost. Opisali smo osnovno idejo vizualne kriptografije. Kmalu pa so se začele pojavljati nadgradnje te zamisli. Prvo sta podala že Naor in Shamir v svojem članku. Kako zašifrirati sliko, ki ni le črno-bela, ;\inpak vsebuje tudi sive tone? Lahko uporabimo okrogle ploščice. Na prvi delni sliki ploščico zavrtimo za naključen kot. Na drugi delni sliki jo položimo enako, če je originalna ploščica bela (prekriti prosojnici bi pokazali napol črn krog), nasprotno, če je originalna ploščica črna (prekriti prosojnici pokažeta črn krog), in ustrezno zavrtena (prosojnici pokažeta krog, katerega več kot polovica je črna) ob ustrezno sivi ploščici (glej tabelo 4). Na ta način dobimo novo prostostno stopnjo (zvezne tone sivine) Računalništvo 279 z (zveznim) vrtenjem ploščic, Žal pa je ta način, čeprav zelo eleganten, precej neprikladen za izvedbo s pomočjo računalnika, zato so nove ideje zelo dobrodošle. prvi del drugi del prekrito * O O Tabela 4. Okrogle ploščice nam omogočijo šifriranje sive slike. Deljenje skrivnosti Vizualna kriptografija je tesno povezana s področjem deljenja skrivnosti (glej Članek [1]). Spomnimo se zopet kapitana Sinjebradca; imel je tri sinove in namesto reutnega varčevanja jim je namenil del naropanega bogastva, ki ga je po stari gusarski šegi zakopal. Bal pa. se je njihovega pretiranega pohlepa. Ker je želel ohraniti vsaj nekaj družinske sloge, naj bi pri izkopavanju zaklada sodelovala vsaj dva brata. En sarn se ne bi mogel polastiti vsega bogastva. Zato je kapitan (proti koncu članka že bolj kriptografsko vešč) zemljevid razdelil na tri delne slike na prosojnicah tako, da se skrivnost razkrije, ko sta prekriti vsaj dve delni sliki. To je tako imenovana shema 2-od-3. Možno je skonstruirati tudi bolj zapletene sheme, ki so sestavljene iz več delnih slik, med katerimi so lahko nekatere bolj, druge pa manj pomembne. Oglejmo si preprost primer konstrukcije sheme 2-od-3 (glej tabeli 5 in 6): 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 Slika 7. Ploščica, ki prtxl-Tabela 5, Šifriranje črne stavlja drugo vrstico ta- Tabela 6. Šifriranje bele točke. bele 5 (0 1 0). točke. Ko gradimo tri delne slike, za vsako točko uporabimo tabelo 5, če je točka na originalni sliki črna (ima vrednost 1), oziroma tabelo 6, če je točka bela (ima vrednost 0); stolpce izbrane tabele naključno premešamo, vrstice premešane tabele pa, zaporedoma predstavljajo ploščice na posameznih delnih slikah (slika 7). Enostavno povedano: če je originalna točka bela, so na delnih slikah istoležni kosi ploščic etiaki, če pa je črna, se istoležni kosi razlikujejo. V vsakem primeru pa so naključno razporejeni. Tu gre po eni strani za varnost (vsaka ploščica na delni sliki je 1/3 črna), po rlrugi pa za kontrast (če prekrijemo ploščici na delnih slikali, ki predstavljata originalno belo točko, dobimo 1/3 črno ploščico, če pa predstavljata, originalno čruo točko, dobimo 2/3 črno ploščico - kontrast je t/3). Podrobnejše napotke je moč najti v članku [2], članki o barvni vizualni kriptografiji in drugih zanimivostih pa so dosegljivi l udi na spletu z iskanjem po ključnih besedah visuaJ iT.vptographv in srcrvl shnring. Ce bi kapitan Sinjebradec redno bral Presek, bi gotovo vedel, kako doseči popolno varnost za svoje skrivnosti. Morda pa bi ga branje tako prevzelo, da Iti tuu zmanjkalo časa za gusarske podvige. Martin Pečar Literatura; (1] A. Jurišič. Kako deliti skrivnosti. Presek 29 (2001-02), št. 6. str. 358-364. [2] D. Stinson, Visita/ cryptographv X- threshold sehemes, Dr. Dobb's Journal, april 1!J98, str. 3f> 43.