RAČUNA LNIŠTVO Vizualna kriptografija -Šum skrivnosti MARTIN PEČAR • Predstavljajte si, da izhajate iz rodbine kapitanov Sinjebradcev, ki so jim legende pripisovale bajna bogastva. To bogastvo pa žal vas ni doseglo, saj je eden od Sinjebradcev, kot zgleden gusarski ka^ta^ zaklad namesto v sef švicarska banke za-lcopal v nedrja zemlje enega od otokov. Na sreco pa na podstresju najdete del zemljevida... Najprej si oglejmo, s cim se sploh ukvarja kriptografija. Pošiljatelj (Sinjebradec) ima sporočilo, polno skrivnih informacij, zato ga po šifrirnem sistemu za-šifrira (raztrga zemljevid) in dobi tajnopis. Ta tajno-pis pošlje naslovniku (svojim potomcem), ki ga od-šifrira (zloži kose1 zemljevida) in prebrre sporočilo. Ves čas pa na tajnopis prežijo tudi napadalci, ki bi se radi dokopali do skrivnih informacij ali pa naslovniku podtaknili lažne informacije. Krlptografi pa so tisti, ki tekmujejo v sestavljanju in izboljševanju šifrirnih sistemov ter iskanju napadov na te sisteme. Vsi šifrirni sistemj, ki se zanašajo na računsko varnost, temellijo na tem, da po dolocenem sistemu „premešajo" informacijo oz. tposocilo, Kljuc imenujemo podrvke (parametjpj, ki v okviru danega šifrirnega sistema (algoritma) natancno Volocajo, kako iz sporocila narediti tajnopts in kako potem vrniti premešane informacijo oz. tajnopis v jsrvoVno obliko. Kljuv se obicadno precej krajši od sporoiila, vistem pa je jem brSsši, cim veS možnih kljucev mora napadalec preizkusiti na voti do rešitve. Ob tem je smiselno upoštevat. Ktrdkroffov prmcip, ki predpostavlja, da napadalec pozna uporrbljeni Sjfrjrni aistem, ne pa tudi kljuna. Napadalec ve, kdaj je prišel na cilj: ko ima tajnopis, razvozlan po dolocenem sisdemu, 26 presek 40 (2012/2013)6 RAČUNA LNIŠTVO SLIKA 1. Zem lj evitdotc^ka SLIKA. 2. r^žec ozr^a^^uje s kriti zaklad smiseln pomen, ja to zalo verjetno izvorno sporočilo. Verjetnost, da bi dobil smiselno, a napačno sporočilo, je neznatna, če je le tajnopis dovolj dolg. Mogoče je pokazati, da je pri sistemu, kjer vsako črko nadomestimo z neko drugo črko oz. zamenjamo abe-čedo, za angleško sporočilo potrebna dolžina približno 25 črk. 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 otok ter ga vsega preko-pljete. Kriptografibi to imenovali napad z grobo silo, saj morate v okviru informačije, ki jo imate (uporabljeni šifrirni sistem oz. ime otoka), preizkusiti vse možnosti (uporabiti vse mogoče ključe o z. prekopati vsak kvadratni meter). Če boste problemu namenili bovolj najlepših let svojega življenja, boste zaklad prej ali slej našli. Vsi, ki želite zakopati zaklad na skrivnem mestu, pa lahke iskalcem Ve bolj otežite delo, ce boste le prebrali nadalievanje Članka. Seveda pa ga lahko preberete tudi lo iz radovednosti. Ker nismo gusarji stare šole, bomo zemljevide namesto na pergament risali na prosojnice. Neuki Si-njebradec bi zemljevid na prosojnici verjetno narisal takole: na eno prosojnico sliko otoka, na drugo pa križec, ki oznacuje zakopani zaklad (slika 1, slika 2). Kž pržsžjnizi poravnamo lo prebrijemž, ja sbrie-nžst razbrita. Tudi eetbt pržsžjoiza atea razbrije nekaj ioform2zije. Tabž nam prea razbrije, na bata-ram žtžbu nas zaba aablad. V nadaljevanju se bžmž naučili, kako prosojnici porisati tako, da z vsake po-dvbvj nihcv nv bo mogvl pridobiti nikakršne informacij v, obe skupzj pa bosta razkrili skrivnost idako-pvaoč 0 + 0 = 1). V prvjšnjvm stolvtju so sv kriptografi domislili, kako ineormacijo zakriai tako, dk jv brez kljuZa nihcv ta bo mzgvl razkriti. V kriptkarafiji tvmu pravimo pepoZnp varnort. Dosvšvmo jo tako, de informacijo "zlijvmo" s povsvm nekljucnjmi podatkL Tako onv-mogocimo napadalcv, saj morajo lv-ti rdstraniti ne-pljucnv podkev, s cimvr pa lahko dzbijo povstm trugacno sporocilo (primvr k). Ob danvm tajnoplsu jv veakn sporocilo istv doliinv vnako vvrjvtno. V taj-nopiru lahko najdvi, akr]akld IšOtr, zato ni vvc samo tnv smisvlnv rvšttvv. Tajnopis pa odšZfriramo taPo, da odstranim o pn"i^j d odrnv oakljucnv podatkz. Primer 1. Pravi kljuc jv kljucnvga pomvna, cvtudi jv nakljucen. k r u h = P (1. sporočilo) v i n o = P1 (2. sporočilo) a s k f = K (1. ključ) n b s ž = K = K + P - P (2. ključ) l k h o = C ( tajnopis) l k h o = C ( tajnopis) V poimeoa 1 se zlivanje istzležnih cok (navpični presek 40 (2012/2013)6 27 RAČUNA LNIŠTVO izvede kot seštevanje zaporednih številk crk v abecedi ('k' + 'a' = 'l', saj je 12 + 1 = 13), kjer se ta ciklično ponavlja (za ,'ž' pride spet 'a'). Ce napadalec prestreže tajnopis C, ne more dolociti sporocila, ker sta oba kljuca K in K' (s tem pa tudi sporocili P in P') enako verjetna, saj sta nakljucna. Kdor pa pozna kljuc, lahko odkrije sporocilo tako, da od tajnopisa odšteje kljuc. Najvecji problem pri tem šifrirnem sistemu je dolžina kljuca — kljuc je enako dolg kot sporocilo samo. Pri drugih sistemih je kljuc obicajno bistveno krajši. Pri enoabecedni zamenjavi je potrebno npr. poznati le zamenjavo za vsako crko, pa lahko s temi manj kot 30-imi podatki zašifriramo in odšifriramo celotno knjigo. Opisana shema za dosego popolne varnosti se imenuje enkratni šcit (angl. one-time-pad), saj kljuc kakor šcit prekrije podatke, uporabimo pa ga lahko samo enkrat (tudi vitezi so morali polomljene šcite zamenjati). Ce bi ga uporabljali veckrat, bi napadalec lahko podtaknil njemu poznano sporocilo P, potem pa iz prestreženega tajnopisa C izračunal kljuc K = C - P. Ce 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 dvoeiškem zapisu na istoležnih bitih izvedekot dvojiški izeZ/ušnj (ek-skluzivni) aliXOh (tabela 1). X0R 0 1 0 0 X 1 1 n ou 10 1 0 0 1 1 1 1 rabimo operacijo navadni ali OR (tabela 2). Na ta nacin slike zašifriramo, ko pa jih odšifriramo, so malce spremenjene, a še vedno prepoznavna. Najpomembneje pa je, da je vizualna kriptogra-fija po sistemu enkratnega šcita podedovala popolno varnost. To pomeni, da napadalec ne more prepo-znaii zašifrirane elike, cetudi ima še tako veliko časa in racunske moci. Slaba str an popelne var nosti pa je, da je kljuc prav tako delg (obsežen- iot samo sporocilo; zaradi tege ni bistvene razlike medkljucem in zašifriranimrporoiilem (primerjaj sliko 3 in sliko 4). Poglejme si idejo malce podrobneje: slikobomo razstavili na dve razlicni, a enako veliki dalni sliki jslika 3, slika 4). Vrako tecko (angl. pixel) originalne zlike bomo na obeh delnih slikah na istoležnih mestih nadomesjili s plošcicama, ki imaia eno polovice belo, drugo pa crno (tabela 3). Na prvi delni slig) bomo p^šcico obrnili nakljucne, na drugi pa bo njena leea odvisna ob barve originalne tec je in lege prve plošcice. Ce je bila originalna tocka bela, bo lega druge plošcice enaka legi prve, sicer pa jo položimo zrcalno. Z malo razmisleka ugotovimo, da sta legi obrh plošcic nakljucni, saj smo za prvo to privzeli, drugo pa smo položili glede na prvo, ki leži naklju-cno. Dešifriranje peteka nejejije drugače. Predrlaa-ljajme r), da mreže pješčic narišeme na prerejnice, Tate pa, če je pleščica (ea. njen del) črna, urtreza-ječi del na prerejnici pebaraame r črne barae. Petem ebe prerejnici prearijeme. Kjer je bila araj ena ed prerejnic pobarvana, aidime črne, drujjje pa je prerejne. Kjer re prekrijeca enake ebrnjeni pleščici (npr. praa a agernji arrtici in druga a rpodnji vrstici sivo. Kjer pp se prekrijeta razlicco obrnjeni ploščici TABELA P TABELA 2. Izključni ali Ali Izvorno sporočilo razkrijemo tako, dč tajnopis še enkrat prekrijemo s Cljučem, saj je pri dvojiškem zapisu seštevanje enako odštevanju. Leta 1994 sta se znana kriptografa A di Shamir, so-jzgajpitelj sistema pavne kriptografije RSA, in Moni Naom domislila vinua^dn kriptografije. Ideja je podobna ennr atnemu ščitu, le d a nomesto zaporedja bitov uporabimo ravnino, tlakovano s dirnimi in belimi nloščičami, ki predstavljajo vrednosti bitov. Poleg; tega pa namesto operacije 'izključm ali' (XOR) upo- oe^etnoct p = 0.5 p = o.s na prvi aelni sliloi 1 i originalna slika črno | belo črno belo nadrugidelnisliki okc) ao D [J TABELA3. Po shemi točko zatočkopostopno gradimo delni sliki tabele 3), tam oko majhno crno-belo polje vidi kot 28 presek 40 (2012/2013)6 RAČUNA LNIŠTVO SLIKA 3. Prva delna slika SLIKA 4. Druga delna slika SLIKA 5. Zlita slika oziroma prekriti delnislikiraz-krijeta skrivnost SLIKA 6. Originalna slika (npr. prva v zgornji vrstici in prva v spodnji vrstici tabele 3), pa vidimo crno polje. Torej: originalno pliko razbijemo na dvr enako veliki delni rliki, na katerih je vraka tocka naključno bela ali crna (to imenujemo šum). Ko obe delni sliki prekrijemo, zagledamo skrito podobo. Ta podoba ie malce spremonpsna (slika 5), saj tam, kjer so bile na originalni sliki bele ploščice, dobimo napol crne. Če so plošcice dovolj majhne, oko napol crne plošcice vidi kot sive. Torej iz crno-bele slike dobimo crno-sivo sliko. Kljub tej izgubi kontrasta so enostavne slike še vedno prepoznavne. Opisali smo osnoano idejo vizualne ksiptogsafije. Kmalu pa so se začele pojavljati nadgradnje te zamisli. Psao sta podala že Naos in Shamis a saojem članku. Kako zašifsisati sliko, ki ni le čsno-bela, ampak asebgje tudi siae tone? Možen odgoaos je: gpo-sabimo oksogle ploščice. Na psai delni kliki ploščico zaastimo za naključen kot. iN a dsggi delni sliki jo moložimo enako, če je osiginalna ploščica bela (pse-ksiti psosoknici bi pokazali napol čsn ksog), naspso-tno, če je osigmalna ploščica črna (pseksiti psosoinici pokmžeta čm ksog), in ustsezno zaasteno (psosojnici pokažeta ksoga katesega aeč kot poloaica je čsna) ob uotoezno siai ploščici (tabela 4). Na ta način dobimo noao psostostno stopnjo (zaezne tone sipine) z (pae- znim) vrtenjem plošAUc. Žal pa je ta način, čeprav zelo eleganten, precej nepriAleden za izvedbo s pomočjo rečunalniAa, zato so nove ideje zelo dobrodo-Ale. prvidnl Al^lz¡del O o ® tabela 4. Okrogle ploščice nam omogočijo šifriranje sive slike Deljenjeskrivnosti Vizualna kriptografija je tesno povezana s podčo-Zjem deljenja skrivnosti (glej Zlanek [1]). Spomnimo se zopet kapitana Sinjebčadca; imel je tči sinove in namesto aentnega vačZevanja jim je namenil del na-čopanega bogastva, lei ga le po stači gusačski šegi zakopal. Bal pa se je pčetičanega pohlepa sinov. Keč pe želzl oličaniti vsdj nekaj dčueinske sloge, naj lbi pči izkapavanju zaklada sodelovala vsaj dva bčata; en sam sc ne bi mogel polastiti vsega bogastva. Zato je jpčoti konzu Zlenka že bolj kIiztogčafsko sešZ) ka- presek 40 (2012/2013)6 2 9 RAČUNA LNIŠTVO pitan zemljevid razdelil na tri delne slike na prosoj-nicah tako, da s e skrivnost razkrije, ko sta pr ekriti vsaj dve delni sliki. To je t. i. shema 2-od-3. Možno je skonstruirati tudi bolj zapletene sheme, ki so sestavljene iz vec delnih slik, med katerimi so lahko nekatere bolj, druge pa manj pomembne. Oglejmo si preprost primer konstrukcije sheme 2-od-3 (tabela 5, tabela 6). Ko gredimo tri delne slike, ze vseko točko uporabimo tabelo 5, ce je tocke ne originelni sliki črne (ime vrednost 1), oz. tebelo 6, ce je tocke bele (ime vrednost 0); stolpce izbrene tebele nekljucno pre-mešemo, vrstice premešene tebele pe zeporedome predstavljejo ploščiee ne posemeznih delnih slikeh (slike 7). Enostevno povedano: ce je originelne točke bele, so na delnih slikah istoležni kosi ploščic enekt, 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 □E TABELA5. Šifriranječrne točke. TABELA 6. Šifriranje Eele Tocke. SLIKA7. Ploščica,kipresta-vlja drugo vrstico tabele5(010). [2] D. Stinson, Visual cryptography & threshold schemes, Dr. Dobb's Journal, april 1998, 36-43. _ XXX www.presek.si www.dmfa.si www.dmfa-zaloznistvo.si xxx čk pe jk Aile Trne, se istolkžni kosi razlikujejo. "V vsakem premkru pa so naključno rezporkšknš. Tu gre po eni strani ze varnosB (vsake ploščfce ne dklni sliki jk 1/3 Ttne), po Arugi pe za kontrast. Čk prkkri-jkmo ploščici ne dklnih slikah, ki prkdsOavljata originalno Ael o točko, nemrkč doAimo 1/3 Trn o ploščico, čkpa jerkdsOavliata originalno črno točko, doAimo 2Š3 črno ploščičo - kontrast jk 1/3. PodroAnkjšk ne-potkk jk moč najti v članku [2], Cdlenki o Aarvni vizualni kriptografiji in drugih zanimivostih pe so dosk-gljivi tudi ne splktu z iskanjkm po ključnih Akskdah visual cryptography in secret sharing. Čk Ai kapitan SinjkAradkč rkdno Aral Prkskk, Ai gotovo vkdkl, kako doskči popolno vernost ze svojk skrivnosti. Morda pe Ai ga Arenjk teko prkvzklo, de Ai mu zmanjkalo časa ze gusarskk podvigk. Literatura [1] A. Jurišic, Kako deliti skrivnosti, Presek 29 2002, 6, 358-364. sLiKE K CLANKu pregled prispevkov ¡f*-^ v 2. 1 3. r ~ . t3s? -- 30 presek 40 (2012/2013) 6