Kódovanie a modelovanie

Táto sekcia ilustruje základné princípy kódovania na jednoduchých príkladoch:

• Kódovanie informácií obrázkom –⁠ dopravné značky, turistické značky, ikonky, symboly na predpoveď počasia
• Emodži a Unicode symboly – kódovanie textu, symbolov a malých ikoniek
• Kódovanie informácií textom aj inak – pohľad na text (a ďalšie spôsoby zápisu informácií) ako na kódovanie informácie

Nadväzujúce témy potom už detailnejšie preberajú technické princípy kódovania:

• Kódovanie textu a šifrovanie
• Kódovanie obrazu a zvuku
• Kódovanie čísel

Informácie o svete potrebujeme nejako zaznamenávať (kódovať). Typický spôsob takého záznamu je pomocou písma. Ak máme napríklad ísť v utorok o 9:00 k zubárovi, zakódujeme si túto informáciu do diára pomocou slova „zubár“. To ale nie je jediný možný spôsob. Namiesto písania slova by sme si mohli do diára nakresliť obrázok zubára.

Kódovanie informácií pomocou obrázkov sa používalo ako predstupeň písma. Ale obrázky nie sú iba pre praľudí, ktorí si do svojho kamenného diára potrebujú vytesať obrázok zubára. Aj dnes, keď už veľa používame písmo, má stále kódovanie informácií pomocou obrázkov svoj zmysel. Obrázky sú totiž často prehľadnejšie.

Medzi typické príklady kódovania informácie obrázkom patria:

• dopravné značky
• turistické mapové značky
• symboly označujúce predpoveď počasia
• symboly označujúce športy na olympiáde
• ikonky v počítačových programoch

Jeden z najjednoduchších spôsobov kódovania informácií je pomocou textu. Napríklad ak máme ísť k zubárovi, bude pravdepodobne jednoduchšie napísať si do kalendára „zubár“ namiesto kreslenia obrázka zubára. Nakresliť obrázok bude trvať o niečo dlhšie a rozlúštiť obrázok môže byť ťažšie, ak sme kreslenie zubárov zatiaľ veľmi netrénovali.

Spôsoby kódovania pomocou textu

Zakódovať jednu informáciu do textu je možné mnohými rôznymi spôsobmi. Napríklad by sme si namiesto jednoduchého hesla zubár mohli zapísať Nezabudni, že zajtra máš ísť na kontrolu k zubárovi. Často si stačí zaznamenať iba zásadné informácie, ostatné môžeme väčšinou odvodiť z kontextu alebo našich vedomostí o svete. Vďaka tomu je často kód (zápis) výrazne stručnejší než samotná informácia, ktorú zaznamenáva.

Je ale treba dobre určiť, ktoré informácie ešte môžeme vynechať a ktoré už nie. Napríklad ak si do kalendára zapíšeme DÚ Staré povesti, za týždeň si už nemusíme pamätať, čo presne bolo vlastne treba spraviť. A ak by tento zápis po nás čítal niekto iný, nebude ani vedieť, o aké povesti presne ide.

Ďalšie spôsoby kódovania

Text sám o sebe ale občas nestačí, takže sa často hodí ho kombinovať s inými spôsobmi kódovania. Dôležitú informáciu v zošite môžeme od ostatných farebne odlíšiť alebo ju podčiarknuť. V mapách sa kombinuje text s rôznymi značkami a farbami. A ak k nápisu „Núdzový východ“ pridáme aj obrázok, môže byť lepšie vidieť a navyše ho môžu nájsť aj cudzinci, ktorí by nerozumeli slovenským slovám.

Kódovanie aj šifrovanie majú spoločné to, že menia podobu textu. Majú však iný účel. Cieľom šifrovania je uchovanie tajomstva. Cieľom kódovania nie je utajenie, iba spoľahlivý záznam alebo prenos správy.

Základné kódovanie textu bolo využívané ešte pred príchodom počítačov. Napríklad Morseova abeceda sa používala na prenos správ telegrafom a Braillove písmo kóduje text na čítanie hmatom. Na kódovanie textu v počítačoch sa používajú metódy založené na binárnych číslach (nuly a jednotky).

Kódovanie správu neutají. Ak zapíšeme správu PES pomocou Morseovej abecedy (.–.|.|…), tak každý, kto túto abecedu pozná, si môže správu ľahko prečítať. Na utajenie správy slúži šifrovanie. Ľudia radi niečo taja, takže šifrovanie sa používa skoro tak dlho ako písanie. Už v staroveku sa šifrovanie hojne používalo, známa je napríklad Cézarova šifra. Šifrovanie hralo veľakrát dôležitú rolu v dejinách, kľúčovou udalosťou bolo napríklad prelomenie nemeckého šifrovacieho stroja Enigma v priebehu druhej svetovej vojny .

Šifrovanie hrá dôležitú rolu aj dnes. Bez kvalitných šifier by napríklad nebolo možné elektronické obchodovanie. Každý používateľ internetu pravidelne používa šifrovanie, aj keď o tom možno vôbec nevie, pretože šifrovanie vykonáva automaticky webový prehliadač.

Tému šifrovanie si môžete precvičiť niekoľkými spôsobmi:

• Základné šifry – základné princípy šifrovania (transpozícia, substitúcia) ilustrované na jednoduchých príkladoch.
• Šifry s nápadom – tieto šifry sa nepoužívajú pre praktické účely, ale dobre poslúžia ako tréning myslenia a test základných kryptoanalytických zručností.
• Šifrovanie: pojmy a princípy – pokročilejšia téma, ktorá sa zaoberá presnejšie spôsobmi použitia šifrovania a hlavnými pojmami.

Ak si chcete vygenerovať vlastné šifry, môžete využiť šifrátor.

Informácie bežne kódujeme ako text, ktorý zapisujeme na papier pomocou písmen abecedy. Zápis pomocou písmen na papier ale nie je jediný spôsob, ako môžeme text zakódovať.

• Morseova abeceda priraďuje každému písmenu kód, ktorý sa skladá z bodiek a čiarok. Používala sa kedysi predovšetkým na prenos informácií telegrafom.
• V námornej vlajkovej abecede má každé písmeno svoju vlajku. Text sa kóduje ako rad vlajok.
• V semaforovej abecede vysielajúci kóduje písmená pomocou rôznych pozícií rúk, v ktorých drží farebné vlajočky. Rovnako ako námorná vlajková abeceda má využitie napríklad medzi námorníkmi na komunikáciu na diaľku.
• Braillove písmo kóduje písmená pomocou hrboľčekov v mriežke 2×3. Toto písmo je určené pre ľudí s postihnutím zraku na čítanie hmatom.
• Počítače ukladajú písmená pomocou číselných kódov. Kódovaniu textu v počítačoch sa venuje samostatná téma.

V počítači sú všetky informácie uložené ako nuly a jednotky. Na uloženie textovej informácie teda potrebujeme kódovanie, ktoré text prevedie na nuly a jednotky. V 60. rokoch 20. storočia za týmto účelom vznikla ASCII tabuľka, ktorá znakom priraďovala čísla od 0 do 255 a tieto čísla sa následne zapísali v binárnej sústave do jedného bytu.

ASCII kódovanie však umožňovalo kódovať iba písmená anglickej abecedy a niektoré ďalšie základné znaky. Preto bol neskôr vyvinutý štandard Unicode, ktorý umožňuje zápis nielen základných písmen, ale aj iných svetových abecied a mnohých ďalších symbolov (napr. snehuliaka: ☃). Aké ďalšie znaky sa v Unicode nachádzajú, si môžete pozrieť tu. Kým Unicode priraďuje znakom čísla, rôzne kódovania (napr. UTF-8) určujú, ako tieto čísla previesť na jednotky a nuly, ktoré sa uložia v počítači. Napr. Unicode kóduje snehuliaka ako číslo 2603 v šestnástkovej sústave. UTF-8 toto číslo zakóduje do troch bytov s hodnotami 1110⁠0010, 1001⁠1000 a 1000⁠0011.

Transpozičné šifry

Transpozičné šifry menia iba poradie písmen, nie ich vzhľad. Základné transpozičné šifry sú založené na prepísaní textu do riadka alebo do mriežky podľa jednoduchého princípu. Príklady:

• zápis odzadu (TRNAVA → AVANRT)
• zápis ob jedno písmeno (TRNAVA→ TARVNA)
• prehadzovanie susedných písmen (TRNAVA → RTANAV)
• šifrovacia mriežka

Existujú aj zložitejšie transpozičné šifry, ktoré umožňujú šifrovať podľa hesla.

Substitučné šifry

Substitučné šifry naopak zachovávajú poradie písmen, ale menia ich podobu. Základnou substitučnou šifrou je posun v abecede (nazývaný tiež Cézarova šifra), kedy písmená nahradzujeme za iné písmená, napr. pri posune o jedna zašifrujeme BRATISLAVA → CSBUJTMBWB (B sa posunie na C, R sa posunie na S a tak ďalej). Zložitejším príkladom substitučnej šifry je šifrovanie podľa hesla (Vigenèrova šifra).

Podobné substitučným šifrám je kódovanie, napr. Morseova abeceda, Braillove písmo alebo ASCII tabuľka. Kódovanie samo osebe však nie je šifrou, pretože správu neutají. Keď zapíšeme správu pomocou Morseovej abecedy, tak každý, kto túto abecedu pozná, si ju môže ľahko prečítať.

Pri praktických aplikáciách šifrovania je typicky základný šifrovací princíp známy a bezpečnosť šifry je založená na utajení kľúča. V nasledujúcich cvičeniach si môžete skúsiť šifry, na vylúštenie ktorých musíte odhaliť ich šifrovací princíp. Také šifry slúžia predovšetkým pre zábavu, využívajú sa napríklad hojne v šifrovacích hrách, pokladovkách a súťažiach. Aj napriek tomu, že tieto šifry nemajú priame praktické použitie, môžete si na nich dobre precvičiť princípy základných šifier, ale aj logické myslenie, hľadanie vzorov a trpezlivosť.

Základné situácie

Účelom šifrovania je utajiť správu. Obrázok znázorňuje základnú situáciu: Alica chce poslať Bobovi správu. Text tejto správy nazývame čistý text. Tento čistý text Alica zašifruje pomocou vopred dohodnutého šifrovacieho postupu a tajného kľuča. Tým vznikne zašifrovaný text, ktorý Alice pošle Bobovi. Bob zašifrovaný text pomocí kľúča rozšifruje a môže si prečítať správu.

Šifrovaný text môže niekto zachytiť (na obrázku je to Eva). Eva sa môže pokúsiť správu odhaliť, má to ale ťažké, pretože nepozná tajný kľúč (a prípadne ani použitý šifrovací princíp). Vykonáva teda lúštenie, ktoré je o dosť náročnejšie než rozšifrovanie.

Pojmy

• Kryptológia je odborný názov pre šifrovanie a lúštenie šifier. Dve hlavné časti kryptológie sú kryptografia a kryptoanalýza.
• Kryptografia sa zaoberá samotnými šifrovacími postupmi, ktoré používajú tí, ktorí spolu chcú utajene komunikovať (na obrázku Alica a Bob).
• Kryptoanalýza sa zaoberá tým, čo robí na obrázku Eva, teda ako vylúštiť zachytenú správu, ktorej šifrovací kľúč alebo spôsob zašifrovania nepoznáme.

Typy šifier

• Transpozícia mení iba poradie písmen, nie ich vzhľad.
• Substitúcia zachováva poradie písmen, ale mení ich podobu.
  • Monoalfabetická substitúcia nahrádza jedno písmeno vždy za rovnaký znak. Príkladom je Cézarova šifra (posun v abecede).
  • Polyalfabetická substitúcia nahrádza písmeno za rôzne znaky v závislosti od polohy v textu. Príkladom je Vigenèrova šifra
• Steganografia je snaha o úplné utajenie existencie správy, napríklad pomocou neviditeľného atramentu alebo nenápadného skrytia textu v obrázku.

Metódy kryptoanalýzy (odhalenia šifier)

Útok hrubou silou spočíva vo vyskúšaní všetkých možných kľúčov.

Frekvenčná analýza spočíva v analýze frekvencií (početnosti) znakov v správe. Tento spôsob analýzy šifier je založený na využití toho, že písmená v jazyku sú zastúpené veľmi nerovnomerne, napr. v slovenčine je písmeno E veľmi časté, kým F málo časté.

Moderné šifry

Moderné šifry sú výrazne zložitejšie než zápis pospiatky alebo posun v abecede, typicky využívajú pokročilú matematiku a zložité algoritmy. Príkladom modernej šifry je RSA.

Moderné šifry sú dvoch základných typov:

• Symetrické šifry využívajú na šifrovanie aj dešifrovanie rovnaký tajný kľúč (rovnako ako na vyššie uvedenom obrázku s Alicou a Bobom).
• Asymetrické šifry využívajú na zašifrovanie verejný kľúč a na dešifrovanie tajný súkromný kľúč. Tieto šifry je možné využiť aj na realizáciu elektronického podpisu.

Farbený model RGB je spôsob reprezentácie farieb pomocou troch zložiek: červená (red, R), zelená (green, G), modrá (blue, B). Ide o aditívny spôsob miešania farieb – jednotlivé zložky farieb sa sčítajú a vytvárajú svetlo väčšej intenzity (svetlejšiu farbu).

Pri použití RGB modelu teda farbu zapisujeme ako trojicu čísel. Na zápis hodnoty jednotlivých zložiek sa používa veľa rôznych zápisov. Napríklad oranžovú farbu môžeme zapísať ako:

• RGB(255, 160, 64) = dekadický zápis osmibitového čísla
• #FFA040 = hexadecimálny zápis
• RGB(100%, 63%, 25%) = farebné zložky v percentách
• RGB(1, 0.63, 0.25) = farebné zložky ako čísla od 0 do 1

Často používaný zápis je dekadický zápis osmibitového čísla, teda číslice od 0 do 255.

V bežnom živote sme zvyknutí zapisovať čísla v desiatkovej sústave, v ktorej používame desať rôznych cifier a ich pozícia zodpovedá mocninám desiatky. Teda napríklad 358 značí osem jednotiek, päť desiatok a tri stovky. To je jeden z mnohých možných spôsobov kódovania.

Ako by sme mohli zakódovať 358 inak? Napríklad tak, že by sme urobili tristopäťdesiatosem čiarok vedľa seba. Alebo by sme sa mohli dohodnúť, že drak bude znamenať sto, prasiatko päťdesiat a zajac dvojku. Potom by sme 358 mohli znázorniť obrázkom, na ktorom budú tri draky, prasiatko a štyri zajace.

Počítače však draky a prasiatka nepoužívajú. Pre počítače nie je vhodná ani desiatková sústava, pretože počítače nemajú desať prstov. No vedia dobre rozlišovať medzi dvomi stavmi (aktívny a neaktívny). Preto sa na kódovanie čísel v počítači používa predovšetkým binárna (dvojková) sústava, v ktorej sa používajú iba dve cifry: 0 a 1.

Základný princíp binárnej sústavy nie je nijako špecifický pre počítače. Ide o matematický princíp „pozičnej sústavy“, ktorá funguje všeobecne. Môžete ju použiť napríklad na počítanie na prstoch, čo vám umožní na prstoch jednej ruky počítať od 0 až do 31. Tiež počítanie v binárnej sústave (sčítanie, odčítanie, násobenie) je všeobecný princíp, ktorý funguje podobne ako počítanie v našej obvyklej desiatkovej sústave.

Na kódovanie záporných a desatinných čísel už je treba zájsť do detailov, ktoré sú trochu špecifické pre počítače (koľko bitov pamäti pre čísla vyčleníme, ako ich presne využijeme).

Okrem binárnej sústavy v informatike občas narazíme aj na sústavy založené na mocninách dvojky, napríklad osmičkovú alebo šestnástkovú sústavu. Konkrétne s hexadecimálnou (šestnástkovou) sústavou sa môžeme často stretnúť pri práci s RGB farbami.

Princíp binárnej sústavy

V binárnej (dvojkovej) sústave zapisujeme čísla iba pomocou dvoch číslic: 0 a 1. Pozícia každej číslice v zápise zodpovedá určitej mocnine dvojky. Mocniny sa vždy začínajú nultou mocninou v prípade číslice najviac vpravo a zvyšujú sa smerom doľava. Hodnotu binárneho čísla potom vypočítame ako súčet týchto mocnín. Každú mocninu započítame, ak je na príslušnej pozícii 1 alebo nezapočítame, ak je na danom mieste 0.

Značenie sústav

Aby sme odlíšili, či hovoríme o čísle v binárnej alebo v desiatkovej sústave, pridávame k číslam dolné indexy značiace sústavu. Napríklad číslo 5 v desiatkovej sústave budeme písať ako 5_{10}, binárne číslo s hodnotou 5 napíšeme ako 101_2. Potom môžeme jasne rozlíšiť, že napríklad zápisom 11_{10} myslíme desiatkové číslo 11, kým zápis 11_2 budeme interpretovať ako binárne číslo 11 a teda desiatkové číslo 3.

Intuitívna pomôcka

Pre základnú predstavu o binárnych číslach môžeme použiť pomôcku, ktorú máme vždy poruke – totiž ruku samotnú. Predstavme si, že si na prsty ruky napíšeme mocniny dvojky:

Potom môžeme na prstoch jednej ruky počítať nielen do päť, ale až do tridsaťjeden. Každé číslo je totiž možné vyjadriť (jednoznačne) ako súčet mocnín dvojky. Ak polohu prstov zaznačíme pomocou núl a jednotiek, dostaneme zápis v binárnej sústave.

V počítači často potrebujeme pracovať so zápornými alebo desatinnými číslami. Keďže však počítače používajú iba nuly a jednotky, je treba tieto čísla nejakým spôsobom zapisovať bez použitia mínusu alebo desatinnej čiarky.

Záporné čísla

Existuje viac spôsobov, ako zapisovať záporné čísla. Väčšinou máme daný určitý počet bitov, s ktorými môžeme pracovať, často jeden byte.

V priamom kóde slúži prvý bit zľava na uchovanie znamienka čísla. Obsahuje 0, ak je číslo kladné, a 1, ak je záporné. Na ostatných 7 bitov sa zapíše absolútna hodnota čísla. Číslo 5_{10} sa teda v jednom byte zakóduje ako 0000 0101 a -5_{10} ako 1000 0101.

V inverznom kóde najskôr zapíšeme absolútnu hodnotu čísla. Ak je číslo kladné, ďalej nerobíme nič. Ak je záporné, obrátime hodnotu všetkých bitov (vymeníme 0 za 1 a naopak). Číslo 5_{10} sa teda v jednom byte napíše ako 0000 0101 a -5_{10} ako 1111 1010.

Kódovanie v doplnkovom kóde (dvojkovom doplnku) sa začína podobne ako v inverznom. Najskôr napíšeme absolútnu hodnotu čísla a ak je číslo kladné, ďalej nepokračujeme. Pre záporné čísla vykonáme obrátenie (inverziu) bitov a následne ešte pripočítame jednotku. Číslo 5_{10} teda v jednom byte zapíšeme ako 0000 0101 a -5_{10} ako 1111 1010 + 1 = 1111 1011. Ak chceme získať hodnotu záporného čísla alebo obrátiť znamienko späť do plusu, vykonáme ten istý sled operácií. Najskôr obrátime všetky bity a potom pripočítame 1. Pre číslo -5_{10} by to vyzeralo nasledovne: inverzia bitov: 1111 1011 → 0000 0100, pripočítanie jednotky: 0000 0100 + 1 = 0000 0101. Získali sme číslo 5_{10}.

Vo všetkých troch kódoch poznáme záporné číslo podľa toho, že má na prvom mieste zľava 1. Kladné čísla na tejto pozícii vždy obsahujú 0.

Desatinné čísla

Desatinné čísla môžu byť veľmi dlhé, občas majú dokonca nekonečný zápis. Počítače však majú obmedzený priestor v pamäti, preto sa aj desatinné čísla ukladajú na obmedzený počet bitov. Tento spôsob reprezentácie sa nazýva zápis s pohyblivou desatinnou čiarkou a kvôli zmenšenému priestoru môže byť občas trochu nepresný.

V zápise s pohyblivou desatinnou čiarkou sa číslo ukladá pomocou dvoch hodnôt: mantisy a exponentu. V špeciálnom bite sa navyše uchováva znamienko čísla, pre kladné sa uloží 0 a pre záporné 1.

Mantisa predstavuje základ čísla – v podstate sú to číslice použité v zápise. Desatinná čiarka sa v mantise nachádza vždy na vopred dohodnutej pozícii, často napríklad za prvou číslicou zľava. Čím väčší priestor (počet bitov) máme na mantisu, tým presnejšie môžeme číslo uložiť.

Exponent je počet miest, o ktoré sa má desatinná čiarka v mantise posunúť, aby sme dostali pôvodné číslo. Kladný exponent znamená posun smerom doprava, čím sa číslo zväčšuje. Záporný exponent značí posun desatinnej čiarky doľava, tým sa číslo viac približuje nule. Čím viac miesta máme na exponent, tým väčší rozsah hodnôt môžeme ukladať.

Napríklad číslo 1101{,}001_2 bude mať mantisu 1{,}101 001_2 a exponent 3_{10}. V znamienkovom bite bude 0.

Na obrázku je príklad, ako môže byť jedno číslo uložené v pamäti počítača na 32 bitoch (4 bytoch).

Ak zvládame základný princíp binárnej sústavy, môžeme sa pustiť do aritmetických operácií.

Sčítanie binárnych čísel

Binárne čísla môžeme sčítať pod sebou veľmi podobne, ako sme zvyknutí sčítavať čísla v desiatkovej sústave. Jediný rozdiel nastáva, ak sčítame dve jednotky. Pretože 1_2 + 1_2 = 10_2, v takom prípade zapíšeme 0 a prenášame 1 do vyššieho rádu.

Odčítanie binárnych čísel

Odčítanie binárnych čísel funguje obdobne. K prenosu dochádza iba pri počítaní rozdielu 0_2 - 1. V takom prípade si „požičiame“ jednotku z vyššieho rádu – ako keby sme počítali 10_2 - 1_2. Potom zapíšeme 1 a v ďalšom ráde navyše odčítame jednotku, ktorú sme si požičali.

Násobenie binárnych čísel

Násobení binárnych čísel je tiež takmer rovnaké ako pri desiatkových číslach. Násobíme tak, ako keby sme mali dve desiatkové čísla zložené iba z núl a jednotiek. Sčítanie riadkov vzniknutých násobením potom prebieha ako binárne sčítanie, ktoré je popísané vyššie.

Ak máme binárne číslo násobiť mocninou dvojky, môžeme si prácu veľmi uľahčiť. Stačí iba pridať na koniec čísla toľko núl, koľkou mocninou dvojky násobíme. Napríklad pri násobení dvojkou pridávame 1 nulu (2 = 2^1), pri násobení osmičkou pridávame 3 nuly (8 = 2^3). Celočíselné delenie mocninou dvojky je tiež jednoduché, stačí odstrániť toľko posledných číslic z delenca, koľkou mocninou dvojky delíme.

Hexadecimálne čísla sú čísla zapísané v šestnástkovej (hexadecimálnej) sústave. Táto sústava využíva 16 symbolov (0 – 9 a A – F, kde A – F predstavujú desiatku až pätnástku).

Hexadecimálne čísla sú úzko prepojené s binárnou sústavou. Každý symbol v šestnástkovej sústave predstavuje štyri bity v binárnej sústave, čo uľahčuje prevody medzi týmito sústavami. Každé číslo v hexadecimálnej sústave je možné previesť na binárne tým, že každému hexadecimálnemu symbolu priradíme štyri bity.

Hexadecimálne čísla sú často využívané v oblasti farebného zobrazenia, napríklad v RGB modeli. Každá zložka farby (červená, zelená, modrá) je vyjadrená ôsmimi bitmi, čo zodpovedá dvom hexadecimálnym čísliciam. Napríklad červená farba s plnou intenzitou by bola zapísaná ako #FF0000, kde FF reprezentuje maximálnu hodnotu červenej zložky.