Znate li razliku između kodiranja i šifriranja? Iako se često ti pojmovi poistovjećuju, radi se potpuno različitim procesima sa različitom namjenom u svakodnevnom životu. Upustite se s nama u priču o kodovima i priču o šiframa.
PRIČA O KODOVIMA
Matematička priča o kodiranju započinje sredinom 20. stoljeća. Priča započinje dolaskom matematičara Richarda Hamminga u Laboratorij Bell. Hamming je bio član odjela koji se je bavio matematičkim istraživanjima. Iako je, kako sam kaže, bio prvorazredni “troublemaker” te nije pristupao rješavanju problemima na do tada uobičajene načine imao je značajne rezultate te ga je uprava tolerirala. Iako je prvenstveno bio angažiran za rješavanje problema vezanih za elastičnost, provodio je mnogo vremena razmišljajući o problemima kojima se prethodno bavio, a koji su vezani uz IBM stroj za računanje rješenja diferencijalnih jednadžbi koje su proizašle iz fizikalnih problema.
Priča o kodovima započinje sasvim slučajno jednog petka popodne 1947. godine. Tog je petka Hamming namjestio svoj stroj za računanje da preko vikenda odradi dugačak i zahtjevan slijede izračuna. Ali… u ponedjeljak je shvatio da je došlo do pogreške u ranoj fazi izračuna i posao od cijelog vikend je propao. Stoj je zapisivao informaciju u obliku niza nula i jedinica te ako je na bilo kojoj poziciji došlo do promjene 0 u 1 ili obrnuto cijela je informacija, pa samim time i cijeli izračun, bila kriva. Prvi pokušaj detektiranje pogreške je bio bitom za provjeru parnosti.
Hamming je razmišljao na sljedeći način: ako bi stroj znao da je do pogreške došli sigurno bi se mogao smisliti i neki način da se ta pogreška ispravi. Hamming si je zadao zadatak da riješi taj problem. Bio je svjestan da bi rješenje takvog problema zasigurno imalo brojne primjene za posljedicu.
Već 1950. godine Hamming je objavio rad u kojem uvodi osnovne pojmove teorije kodiranja (npr. udaljenost između dva niza koja se njemu u čast zove Hammingova udaljenost) i familiju kodova koji mogu detektirati i ispraviti pogreške koji se njemu u čast zovu Hammingovi kodovi. Taj se rad smatra začetkom teorije kodiranja.
Primjeri:
1. Kod s ponavljajućim bitovima. Pretpostavimo da želimo prenijeti informaciju zapisanu binarnim nizom duljine jedan, npr. 1. S ciljem efikasnog otkrivanja i ispravljanja greške, pošaljimo niz duljine osam: 11111111. Na ovaj način moći ćemo otkriti najviše 7 pogrešaka te ispraviti najviše 3 pogreške.
2. Kod s provjerom parnosti. Pretpostavimo da želimo prenijeti informaciju zapisanu binarnim nizom duljine sedam, npr. 1110001. Pri prijenosu ćemo dodati i 8. član niza a: a = 0 ako početni niz ima paran broj jedinica, a = 1 ako početni niz ima neparan broj jedinica. U primjeru to znači da šaljemo niz: 11100010. Na ovaj način moći ćemo otkriti neparan broj pogrešaka u prijenosu ali nećemo moći ispraviti niti jednu pogrešku.
U dva smo primjera koristili binarne nizove duljine 8 u prijenosu informacija. U prvom smo prenijeli manje informacija uz veću mogućnost otkrivanja i ispravljanja greške dok smo u drugom primjeru prenijeli više informacija uz manju mogućnost otkrivanja i ispravljanja greške.
Osnovni problem teorije kodiranja je naći kod kojim možemo prenijeti zadovoljavajuću količinu informacije uz zadovoljavajuću mogućnost detekcije i ispravljanja greške.
Hammingov kolega u Laboratoriju Bell je bio Clauda Shannon, matematičar, inženjer, kriptograf, čiji rad A Mathematical Theory of Communication iz 1948. godine se smatra začetkom teorije informacija. Shannon je dokazao da za dani epsilon > 0 i R konačan broj postoji kod koji prenosi R informacija uz vjerojatnost greške manju od epsilon te je na matematičarima da osmišljavaju kodove koji će nam omogućiti svakodnevnu nesmetanu komunikaciju.
Od tada se teorija kodiranja brzo razvija, a sve s ciljem konstrukcija kodova s dobrim svojstvima, kodova koji mogu prenijeti puno informacija, detektirati i ispraviti što veći broj riječi, brzo dekodirati primljenu poruku… Razvoj teorije kodiranja motiviranje je i njezinom veliko primjenom u svakodnevnom životu: svakodnevna komunikacija, prijenos informacija iz svemira, pohranjivanje podataka….
Što je zapravo kod? Kod je skup riječi (nizova simbola) koje koder kreira i šalje u komunikacijski kanal. Svaka riječ koda nastala je od ulazne poruke (informacije) koju zapravo želimo poslati. Iako ova naša priča o kodiranju započinje tek sredinom 20. stoljeća, ljudi su se susreli sa sličnim problemima i njihovim rješenjima puno, puno prije toga… Primjer: Morsov kod: 1835. konstruiran je Morsov telegraf koji je koristio Morsov kod.
Ali još puno, puno prije toga ljudi su počeli razvijati jezik za međusobnu komunikaciju. Naši su jezici napravljeni tako da naš mozak, najbolji dekoder koji postoji, uspije detektirati i ispraviti brojne pogreške koje se događaju u komunikaciji (npr. gutanje slova u izgovoru, frfljanje, lapsusi u pisanom tekstu, ….). Uočimo da bi se sve riječi u hrvatskom jeziku, kojih ima oko pola milijuna, mogle napisati sa 4 ili manje slova. Međutim, u tom slučaju jako puno riječi bi se razlikovalo samo za jedno slovo (kao npr. KIST i LIST) te bi bilo jako lako dolazilo do pogreške, npr. pri pisanju, te bi se te pogreške teško ispravljale. Puno bismo lakše uočavali i ispravljali lapsuse kad bi svaka riječ imala npr. 10 ili više slove. Međutim, to bi nam bilo jako nepraktično kako u pisanju tako i u govoru.
PRIČA O ŠIFRAMA
Šifriranje je postupak kojim skrivamo naše poruke tako da ih ne može bilo tko pročitati. Dvije osobe koje žele komunicirati dogovore postupak skrivanja i otkrivanja poruka. Važno je da dogovoreni postupak ostane tajan. U nastavku ove priče opisat ćemo neke značajne događaje u povijesti koji su povezani sa šifriranjem.
Otkada je civilizacije, ljudi imaju tajne te postoji potreba za skrivanje tajni. Jednu od prvih naprava za šifriranje koristili su Spartanci. Ta se naprava zvala skital.
Skital je štap oko kojeg je namotana vrpca od pergamenta na koju se zapisivala poruka duž štapa. Nakon što se vrpca odmotala, sadržaj poruke je bio skriven za svakoga tko nije imao isti štap.
Veliki rimski vojskovođa Gaj Julije Cezar koristio je šifre kako bi skrivao poruke od svojih neprijatelja. Cezar je poruke skrivao tako da je svako slovo u poruci zamijenio slovom koje je tri mjesta nakon njega u abecedi (A je zamijenio sa D, B sa E, itd.). U to je vrijeme jako malo ljudi znalo čitati i pisati pa je Cezar ovim jednostavnim šiframa uspješno čuvao svoje tajne.
Za sifriranje Cezarovom sifrom mozemo se posluziti i Cezarovim diskom.
Vidimo da se onda NOCISTRAZIVACA sifrira u QRFLVWUDCLYDFD.
Skoro 2000 godina nakon Cezara ljudi su uspješno skrivali tajne različitim šiframa, na sličan način kako je to i Cezar radio. Kroz vrijeme postupci šifriranja postajali su sve složeniji.
Prije oko 200 godina engleski matematičar Charles Babbage izradio je mehanički stroj na temelju kojega su se razvila današnja računala. Prvo pravo računalo osmislila je i izradila grupa matematičara i inženjera predvođena velikim matematičarom Alanom Turingom. Oni su izradili računalo kako bi mogli s njim čitati tajne koje su skrivane poznatom napravom za šifriranje koja se zove Enigma. Opis prvog pravog računala objavljen je 1946. godine. Prvo osobno računalo nastalo je 17 godina nakon toga.
Nakon pojave prvih računala ljudi su morali smisliti nove načine skrivanja tajni koje se ne mogu otkriti uz pomoć računala.
Vizualno šifriranje
Kako sakriti odnosno na siguran nacin sifrirati sliku? Je li moguce na siguran nacin podijeliti tajnu sliku prijateljima koji ju nece moci samostalno vidjeti vec tek nakon sto se svi sastanu na jednom mjestu? Vizualno sifriranje je metoda dijeljenja tajne slike na odgovarajuci broj sudionika tako da niti jedan sudionik samostalno ne moze otkriti tajnu. Kod vizualnog sifriranja tajna se informacija na siguran nacin sifrira tako da se njezino desifriranje moze izvrsiti koristeci iskljucivo ljudski vid. Ljepota i jednostavnost takvog sifriranja je u nacinu sifriranja i desifriranja tajnih podataka koje ne zahtijeva posebno znanje o sifriranju niti zahtjevno racunanje. Vizualno sifriranje uveli su Adi Shamir i Moni Naor 1994. godine nakon cega se ubrzano razvija. Osim za distribuciju i zastitu tajnih podataka, vizualno sifriranje danas se koristi za identi kaciju/autenti kaciju, sprecavanje plagiranja materijala, izradu i citanje QR kodova i slicno.
Matematičari su osmislili mnoge načine šifriranja koji danas uspješno čuvaju naše tajne. Pred matematičarima danas stoji izazov osmišljavanja načina šifriranja koje kvantno računalo ne može lako probiti.
