Kódování a šifrování

Kódování a šifrování

Problematika kódování a šifrování je rozsáhlá. Nelekejte se ovšem následujícího množství textu. Důležité je problematiku pochopit, nejlépe za pomoci příkladů. Pak je snadné si všechny informace zapamatovat. Naopak není k ničemu užitečné naučit se všechny definice a tvrzení nazpaměť a nemít ponětí, co znamenají.

Kódování

záznam informace pomocí známého, pokud možno všeobecně rozšířeného kódu (kódy jsou obvykle standardizovány, tj. zveřejněny a používány všude stejně) za účelem jejího praktického a jednoduchého uchovávání a přenosu

např.       Morseova abeceda               – optimalizováno pro přenos světelným signálem

Braillovo písmo    – optimalizováno pro četbu hmatem

informatika            – záznam textu, obrazu, zvuku optimalizovaný pro přenos elektrickým signálem

– dvě možné úrovně el. signálu – 0 (není) a 1 (je)

– využití polyadických soustav (binární, dekadická a hexadecimální)

Jednotky informace

bit (zkr. binary unit, angl. bit = kousek) – zkráceně 1 b

nejmenší jednotka informace, jeden záznam na záznamovém médiu, jeden impuls na přenosovém médiu, jedna binární číslice, nabývá hodnot 0 nebo 1

Více bitů za sebou lze považovat za binární číslo, které můžeme zapsat i pomocí jiných soustav.

např. 4 bity 1 1 0 0                = 1100 (binární číslo)

= 12 (dekadické číslo)

= 0xC (hexadecimální číslo, pozná se tak, že zápis začíná vždy 0x)

použití    – rychlost přenosu (např. 2048 b/s)

– výpočetní síla procesoru (např. 32 b procesor – dokáže zpracovat 32 binárních číslic najednou)

byte (= 8 bitů = 2³ bitů) – zkráceně 1 B

Lze pomocí něj zapsat 256 čísel od 0 (00000000) po 255 (11111111).

použití    – velikost souboru (např. 3 MB veliký soubor s fotografií)

Pozor při stahování souborů – velikost souboru je uvedena v bytech, rychlost přenosu v bitech.

např. Soubor o velikosti 875 MB = 8×875 Mb se při přenosové rychlosti 2 Mb/s bude stahovat 8×875/2 = 3500 s = 70 min.

méně používané

2 byte = 1 word (slovo)

2 word = 1 double word (dvojité slovo)

řecké předpony

kilo (k), mega (M), giga (G), tera (T) – někdy ve smyslu mocnin dvou, někdy ve smyslu mocnin deseti

např. kilo = 2¹⁰ = 1024 nebo 10³ = 1000, mega = 2²⁰ = 1048576 nebo 10⁶ = 1000000

Někdy zneužíváno např. výrobci disků – 100 GB disk by měl mít 100×2³⁰ B = 107374182400B, ale ve skutečnosti může mít jen 100000000000 B = jen 93% velikosti

Kódování informace v informatice

veškeré informace uloženy v souborech, kódovány pomocí číslic0 a1

Soubory s informací kódovanou známým způsobem jsou opatřeny známou příponou a zpracovávány programy, které toto kódování znají (pokud neurčíte jinak).

Existují programy, které umí zobrazit přímo jednotlivé bity jakéhokoliv souboru, např. Pspad.

(ke stažení na http://www.pspad.com/cz/download.php)

Kódování textu (znaků)

Princip

K zakódování X různých znaků potřebujeme X různých dvojkových čísel. Základní anglická abeceda se skládá z 26 znaků, tj. k jejímu zakódování potřebujeme nejméně 26 dvojkových čísel, nejlépe 0 (00000) až 25 (11001), neboli nejméně 5 bitů, přičemž čísla 26 (11010) až 31 (11111) jsou nevyužita.

Anglická abeceda s rozlišením velkých a malých písmen se skládá z 52 znaků, tj. k jejímu zakódování potřebujeme nejméně 52 dvojkových čísel, nejlépe 0 (000000) až 51 (110011), neboli nejméně 6 bitů, přičemž čísla 52 (110100) až 63 (111111) jsou nevyužita.

Potřebujeme-li zakódovat ještě číslice od 0 do 9, interpunkční a jiná znaménka, zvláštní znaky (mezera, procento, zavináč apod.) a netištitelné znaky (tab, enter), potřebujeme již 8 bitové číslo, které nám dává 255 různých možností od 0 (00000000) po 255 (11111111). Běžně se tedy jeden znak textu zakóduje pomocí 1 bytu. Velikost souboru s neformátovaným textem kódovaným tímto způsobem je pak v bytech rovna počtu znaků textu. Např. soubor Ahoj.txt, který obsahuje slovo Ahoj, má velikost 4 B.

Existuje obrovské množství možností, jak jednotlivým existujícím znakům přiřadit jednotlivá čísla od 0 do 255. V praxi se ovšem používají standardizované převodní tabulky, nejčastěji ASCII (American Standard Code for Information Interchange) tabulka.

ASCII kódovací tabulka

Kódy 0-31 jsou přiřazeny netištitelným znakům (např. 9 = tab, 10 = enter). Kódy 48-57 jsou přiřazeny číslicím 0-9 (kód číslice se dá tedy určit jako 48 + číslice, např. číslice 5 bude kódována jako 48+5 = 53 = 110101). Význam kódů 128-255 závisí na použitém typu písma. V českém písmu budou mít tato čísla jiný význam než v řeckém. Pokud v elektronickém textu uvidíte neznámé znaky tam, kde evidentně nemají co dělat, může to být způsobeno právě špatně vybraným písmem. Autor textu např. zakódoval český znak č pomocí českého písma jako kód 190, zatímco prohlížeč textu kód 190 dekódoval pomocí řeckého písma jako řecký znak alfa. Např. u html stránky většinou stačí v prohlížeči zvolit správné písmo pro dekódování obsahu stránky (menu Zobrazit, Kódování).

Osmibitové kódování znaků již dnes není dostačující, neboť je potřeba moci jedním kódem zakódovat i znaky všech národních abeced (včetně azbuky nebo asijských písem), aby je bylo možno v jednom textu kombinovat. Proto bylo vyvinuto 16tibitové kódování Unicode, kterým je možno zakódovat až 2¹⁶ (přibližně 64 tisíc) znaků. Význam kódů 0-128 je stejný jako ve standardu ASCII. Velikost souboru s neformátovaným textem kódovaným pomocí Unicode je v bytech rovna dvojnásobku počtu znaků textu. Některé dnešní programy ještě nepodporují kódování Unicode (nebo musíte tuto možnost nejdříve ručně povolit), takže znak kódovaný pomocí Unicode zobrazí jako dva jiné znaky.

Textové soubory kódované uvedenými způsoby lze vytvářet, ukládat a otevírat pomocí textových editorů, např. Notepadu (poznámkový blok). Notepad pracuje tak, že bity jakéhokoliv souboru, který v něm otevíráte (vč. souborů, které text neobsahují, ale přesto si vyberete, že je chcete otevírat v Notepadu) rozdělí po osmi a každou osmici přeloží podle ASCII tabulky na příslušný znak, který pak zobrazí.

Mezi tyto textové soubory patří především neformátovaný text (přípona txt) a zdrojové kódy programů (např. přípona cpp pro C++, vbs pro Visual Basic Script, html, php nebo asp pro webové stránky). Některé další soubory (např. formátovaný text s příponami doc, rtf apod.) jsou částečně kódovány jako text, částečně úplně jinak (obsahují formátovací značky, lze si prohlédnout v pspadu). Samotné programy (např. přípony dll, exe, com) obsahují již přímo instrukce pro procesor a jako text nejsou kódovány vůbec

Příklad

Text = Ahoj!123

Kódování podle ASCII

A      h               o               j                 !        1                2                3

binárně                       = 0100 0001 0110 1000 0110 1111 0110 1010 0010 0001 0011 0001 0011 0010 0011 0011

dekadicky                   = 65    104            111            106       33         49              50              51

hexadecimálně          = 0x41               0x68          0x6F         0x6A      0x21    0x31          0x32          0x33

Kódování obrazu

Princip

Vektorový záznam

Zaznamenává se způsob, jakým lze obraz vytvořit, např. kruh o poloměru R se středem na souřadnicích X,Y nakreslete barvou B a tloušťkou čáry T, úsečku veďte z bodu A do bodu B přerušovaně atd. Příslušný program pak podle instrukcí zrekonstruuje obraz. Výhodou tohoto záznamu jsou velice nízké nároky na paměť, nelze jej ovšem pochopitelně použít pro fotografie a reálné kresby, pouze pro jednoduchou grafiku. Vektorovou grafiku ovládají pouze specializované programy (např. Corel Draw), běžné prohlížeče a zobrazovače s ní nepracují, proto se s ní běžně nesetkáte.

Rastrový záznam

Zaznamenává se jakási šachovnice jednotlivých barevných bodů (pixel = zkr. picture element, angl. obrazový prvek), na níž lze obraz rozložit. Čím více je řádků a sloupců, na které obraz rozložíme, tím větší je jeho rozlišení a kvalita, zároveň však také velikost. Např. obrázek o rozlišení 640×480 se skládá z 307200 pixelů, pro každý pixel je potřeba zaznamenat informaci o jeho barvě, soubor s obrázkem tedy bude veliký. Při příliš malém rozlišení však zase bude obraz nepřirozeně rasterizovaný (viditelné čtverečky). Snažíme se volit nejmenší takové rozlišení, při němž je rasterizace pro lidské oko nerozpoznatelná.

Způsob kódování barvy závisí na počtu barev, kterých můžou pixely nabývat. V černobílém obrázku mohou pixely mít pouze jednu ze dvou barev, každý pixel tedy stačí zakódovat pouze jedním bitem, kde např. 0 znamená černá a 1 znamená bílá. Obrázek pak bude mít takovou velikost v bitech, jaké má rozlišení.

Příklad

0000000000111110000000000

0000000000111110000000000

0000000000111110000000000

0000000000111110000000000

0000000000111110000000000

1111111111111111111111111

1111111111111111111111111

1111111111111111111111111

1111111111111111111111111

1111111111111111111111111

0000000000111110000000000

0000000000111110000000000

0000000000111110000000000

0000000000111110000000000

0000000000111110000000000

Rozlišení obrázku – 15×25 = 375

Velikost obrázku – 375×1 = 375 b = 47 B

Může-li každý pixel obrázku nabývat některou ze 16 barev, pak je třeba každý pixel zakódovat čtyřmi bity, neboť pomocí nich lze zapsat 16 různých čísel od 0 (0000) do 15 (1111). Tzv. barevná paleta pak určuje, která barva je kódována kterým číslem. Všechny programy, které s takovým obrazem pracují, však musí mít tuto paletu nastavenu stejně, aby výsledný obraz byl stejně barevný. U 256 barevné palety je každý pixel potřeba zakódovat osmi bity, neboť pomocí nich lze zapsat 255 různých čísel od 0 (00000000) do 255 (11111111). Obdobně lze odvodit vztahy pro libovolně velikou paletu. Velikost souboru s obrázkem je pak v bitech rovna součinu rozlišení obrazu a počtu bitů, který je potřeba na zakódování barvy jednoho pixelu.

Příklad

Soubor s obrázkem, velikost 36 b

binárně                  010 111 000 010

011 101 001 100

111 010 110 000

tj. totéž jako           0101 1100 0010

0111 0100 1100

1110 1011 0000

hexadecimálně     0x5  0xC  0x2

0x7  0x4  0xC

0xE  0xB  0x0

a) 8-mi barevná paleta – 1 pixel = 3 bity

pixely obrázku:

zelený, bílý, černý, zelený

modrý, oranžový, hnědý, červený

bílý, zelený, žlutý, černý

rozlišení 4×3 = 12 pixelů

b) 16-ti barevná paleta – 1 pixel = 4 bity

pixely obrázku:

světle zelený, tmavě žlutý, tmavě hnědý

světle modrý, tmavě zelený, tmavě žlutý

béžový, oranžový, černý

rozlišení 3×3 = 12 pixelů

Chceme-li se vyhnout omezením daným paletou a používat všechny možné okem rozlišitelné barvy, pak použijeme tzv. barevný model RGB (red, green, blue). Podle něj je každá barva složená z určitého množství červené, modré a žluté (existují ovšem i jiné podobné modely se stejným výsledkem). Lidské oko dokáže nejvýše rozlišit, že každá z těchto tří barev přispěla do výsledné barvy 0 až 255 díly, množství každé přísady tedy lze zakódovat osmi bity. Výsledná barva je pak kódována 3×8, tedy 24 bity. Velikost souboru s obrázkem 640×320 pixelů je v tomto kódování 640x320x24 = 38400 b = 4800 B = přibližně 5 MB.

Rastrový záznam kódovaný uvedenými způsoby je použitelný pro jakýkoliv druh obrazu vč. fotografií. Čím detailnější je informace o barvě, tím kvalitnější je obraz, ale i větší velikost souboru. Rastrové obrázky všech uvedených typů mají příponu bmp (informace o kódování barvy je uvedena v hlavičce souboru) a lze je vytvářet, ukládat a otevírat pomocí grafických editorů, např. Paintbrushe (malování).

Chceme-li zmenšit velikost souborů s obrázky, aniž bychom snížili rozlišení, je třeba použít některý komprimovaný formát. Komprese (komprimace) je způsob, jak z něčeho velkého nějakým způsobem udělat něco menšího. Bezeztrátová komprese používá způsoby, které umožňují soubor zrekonstruovat do přesně stejné podoby, jakou měl před kompresí. Ztrátová komprese nevratně zbaví soubor části informace, která je ovšem obvykle zanedbatelná, tudíž nepotřebná. Pro různé typy dat jsou vhodné různé typy kompresí.

Formát png

Jedná se o bezeztrátovou kompresi, která je použitelná pro obrázky s ostrými hranami a velkými plochami stejné barvy. Není pak třeba např. pixel po pixelu vypisovat dvacet bílých řádků obrazu, do souboru stačí pouze zapsat, že bude následovat např. 200 bílých pixelů.

Příklad pro zájemce

zjednodušený zápis                                                                                           komprimovaný záznam

(10 x 1 10  x 0 10  x 1)

10×1 5×0 10×1                       01010 1 00101 0 01010 1 – 18b            010101001010010101

10×1 5×0 10×1                                                                                      010101001010010101

10×1 5×0 10×1                       x 5                                                          010101001010010101

10×1 5×0 10×1                                                                                      010101001010010101

10×1 5×0 10×1                       (25 x 1)                                                  010101001010010101

25×1                                       11001 1   – 6b                                         110011

25×1                                                                                                      110011

25×1                                       x 5                                                          110011

25×1                                                                                                      110011

25×1                                       (10 x 1 10  x 0 10  x 1)                          110011

10×1 5×0 10×1                       01010 1 00101 0 01010 1 – 18b            010101001010010101

10×1 5×0 10×1                                                                                      010101001010010101

10×1 5×0 10×1                       x 5                                                          010101001010010101

10×1 5×0 10×1                                                                                      010101001010010101

10×1 5×0 10×1                                                                                      010101001010010101

Velikost komprimovaného obrázku – 5×18 + 5×6 + 5×18 = 210 b oproti 375 b, tj. zmenšení na 56% původní velikosti

Formát jpg

Jedná se o ztrátovou kompresi, která využívá podobnosti sousedních pixelů u obrazů s přirozeným přechodem barev, např. fotografií. Zanedbání barevných rozdílů mezi sousedními pixely je pro oko nepostřehnutelné.

Formát gif

Jedná se o bezeztrátovou kompresi, která omezuje množství použitých barev na nejvýše 256. Je podobně jako formát png vhodná pro uměle vytvořené obrazy. Mezi přednosti tohoto formátu patří existence tzv. průhledné barvy (při překrytí dvou obrazů prosvítá pod průhlednou barvou spodní obraz) a možnost gif animace (vytvoření pohybového efektu střídáním podobných obrázků, použijte například Zoner GIF Animator, http://www.stahuj.cz/grafika_a_design/animace/zoner-gif-animator). Formát gif je z uvedených důvodů velmi oblíbený mezi autory webových stránek.

Kódování zvuku

Princip

Analogový záznam

Jedná se o jakýsi přirozený otisk fyzikální reality (zvukové vlny) do elektrických impulsů. Analogový záznam postihuje realitu plynule. Nevýhodou analogového záznamu zvuku je náchylnost k záznamu šumů a velké nároky na velikost (viz malá kapacita Audio CD). Obdobou analogového záznamu zvuku (např. nahrávání na kazetový magnetofon) je analogová fotografie (chemická reakce vyvolaná světlem na povrchu filmu).

Digitální záznam

Zvuk není zaznamenáván plynule, ale vzorkován, tj. mnohokrát za vteřinu se změří a zapíše jeho frekvence a hlasitost. Z těchto vzorků je pak možné zvuk kvalitně rekonstruovat. Výhodou digitálního záznamu zvuku je menší nárok na velikost souboru a možnost přidání doplňujících informací do souboru (např. titulky, texty, obraz).

Soubory s digitálním zvukem bývají dále komprimovány některou z mnoha existujících metod. Komprese využívá obvykle nedokonalosti lidského ucha, kdy ořeže (nezachovává) frekvence zvuku, které jsou nižší nebo vyšší, než může ucho zaznamenat. Čím užší škála frekvencí se v záznamu zachovává, tím nižší je kvalita výsledné nahrávky. Kvalitu obvykle volíme podle účelu, např. nižší kvalitu může mít mluvené slovo (telefonní hovor, rádiové vysílání), vyšší kvalitu budeme požadovat např. od nahrávky klasické hudby.

Formát vaw

U tohoto formátu firmy Microsoft nedochází ke kompresi, zvuk je dokonalý, avšak klade velké nároky na paměť. Používá se proto především pro krátké zvukové předěly a znělky operačního systému.

Formáty mpg, mpeg, mp3

Tyto formáty dovolují různý stupeň komprese. Kódování a dekódování těchto souborů klade zvýšené nároky na procesor, avšak při dnešních parametrech procesorů se nejedná o nic kritického, proto jsou velice oblíbené.

Formát wma

Formát firmy Microsoft, který má podobné vlastnosti jako mp3, avšak Microsoft nezveřejňuje jeho strukturu, proto s ním umí zacházet především jeho programy.

Formát ogg

Obdoba předchozích formátů, která je dobře dokumentovaná a oblíbená mezi příznivci alternativních operačních systémů a otevřeného softwaru.

Srovnání uvedených formátů

Formát midi

Tento formát se od předchozích velmi liší svým principem. Zde totiž není přenášen záznam frekvencí a hlasitostí, ale pouze předpis, jak příslušný zvuk vyrobit (podobně jako u vektorových obrázků), např. zahraj půlové tóny C,D,E na klavír a celé tóny Cis, F na housle. Program, který rekonstruuje zvukový záznam, pak musí být schopen vydávat zvuk příslušných nástrojů. Výhodou tohoto přenosu je minimum nároků na paměť, neboť se přenáší v podstatě pouze notový zápis zvuku. Proto je velmi oblíbený např. u mobilních telefonů. Formát midi nelze pochopitelně použít pro mluvené slovo.

Kódování videa

Video můžeme považovat za kombinaci obrazu a zvuku. Metody k jeho záznamu jsou proto také kombinací předchozích metod. Jedná se např. o formáty mpeg, wmv nebo avi. Velmi důležitá je zde samozřejmě komprese. Obvyklé je využití tzv. asymetrické komprese, kdy zakódování je výpočetně náročné (ale to nevadí, protože se provádí pouze jednou), zatímco dekódování je podstatně jednodušší (což je důležité, protože se provádí při každém pouštění videa). Je to podobné jako u opačných matematických operací umocňování (jednoduché, jde i zpaměti) a odmocňování (složité, trvá to dlouho).

Šifrování

Proces změny otevřené (čitelné) informace pomocí známého postupu (šifry) a tajného hesla na informaci šifrovanou. Šifrovat lze na úrovni bitů nebo celých znaků. Čím složitější šifra, tím větší nároky klade šifrování na procesor, ale zároveň je tím těžší šifru prolomit. Informaci je třeba zabezpečit tak složitou šifrou, aby její prolomení pomocí výpočetní techniky (zkoušením všech možných hesel) bylo finančně náročnější než je hodnota této informace. Nejslabším článkem šifrování je pak vždy lidský faktor, útočník se snaží tajné heslo vylákat z člověka, který ho zná (např. falešnými e-maily – tzv. phishing).

Šifrováním a vším souvisejícím se zabývá věda zvaná kryptografie.

Symetrická šifra

Obdobný postup pro šifrování i dešifrování. Všichni účastníci komunikace musí znát stejné tajné heslo, které si musí před jejím zahájením bezpečně předat.

Transpozice (posun)

Každý znak se posune o určitý, tajný počet. V případě bitového zápisu dojde pouze k záměně nul za jedničky.

Příklad

posun o 1

a->b, b->c, c->d …

0->1, 1->0

ahoj -> bipk

ahoj pomocí ASCII = 0100 0001 0110 1000 0110 1111 0110 1010 0010 0001 -> 1011 1110 1001 0111 1001 0000 1001 0101 1101 1110

Substituce (náhrada)

Každý znak se změní na jiný znak podle tajné kódovací tabulky.

Příklad

kódovací tabulka

a->x, b->d, c->f, d->i …

abcd -> xdfi

Asymetrická šifra

K šifrování je třeba jedno heslo, tzv. soukromý klíč (private key), k dešifrování druhé heslo, tzv. veřejný klíč (public key). Oba klíče jsou mnohamístná čísla odvozená složitými matematickými postupy. Každý účastník komunikace zná a chrání si svůj soukromý klíč, zatímco svůj veřejný klíč dá k dispozici ostatním účastníkům. Klíčový pár vygeneruje účastníkům důvěryhodná instituce (např. Česká pošta, 1. Certifikační autorita). Veřejnému klíči spolu s informacemi o jeho vlastníkovi se říká certifikát.

Digitální podpis

Odesilatel zprávy připojí ke zprávě její kopii a zašifruje ji svým tajným klíčem. Adresát zprávy tuto kopii dešifruje veřejným klíčem adresáta a porovná ji s obsahem zprávy. Pokud jsou stejné, získává adresát jistotu, že zpráva pochází skutečně od odesilatele a nebyla po cestě nikým změněna. Obsah zprávy ovšem šifrovaný není, zpráva je čitelná pro každého.

Příklad

zpráva    -> zpráva se svou kopií       -> zpráva s kopií zašifrovanou tajným klíčem odesilatele

-> zpráva s kopií dešifrovanou veřejným klíčem odesilatele         -> zpráva

ahoj         -> ahojahoj           -> ahojbipk            -> ahojahoj            -> ahoj

Šifrování zpráv

Odesilatel zprávy zašifruje zprávu veřejným klíčem adresáta. Zprávu pak může dešifrovat pouze adresát svým tajným klíčem, pro kohokoliv jiného (včetně odesilatele) je nečitelná. Odesilatel zprávy ovšem není zaručen, stejně jako není zaručeno, že zpráva nebyla po cestě někým změněna.

Příklad

zpráva    -> zpráva zašifrovaná veřejným klíčem adresáta             -> zpráva dešifrovaná tajným klíčem adresáta

ahoj        -> bipk    -> ahoj

V reálném prostředí se používá kombinace obou těchto metod a zprávy procházející nezabezpečeným prostředím jsou tak zabezpečené a důvěryhodné.