Zpracování informací

Ústav automatizace a informatiky Fakulta strojního inženýrství Vysoké učení technické v Brně

Cvičení č. 2 z předmětu

Zpracování informací © Ing. Radek Poliščuk, Ph.D.

Zpracování informací, cvičení 2.

1/9

Téma cvičení Cvičení 2 – Přenos dat detekce a korekce chyb v přenášených datech minimalizace objemu přenášených dat metody šifrování dat

Realita

DATA

Informační systém

Informace Příjemce


2/9

Přenos dat K přenosu dat se používají různá média a modulace: spojité analogové signály jsou citlivé na rušení (šum, impulsní chyby,...) při jakékoliv modulaci digitální data je možné zabezpečit vhodnými detekčními a korekčními kódy Délku přenášeného (a narušitelného) kódu je možné zkrátit kompresními algoritmy „životně důležitá“ a časově kritická data NIKDY nepřenášet nespolehlivým kanálem!

Druhy používaných modulací


Morseova abeceda

RS 232/422/485

3/9

Přenos dat U „sériových“ linek (RS232, 422, 485) se při přenosu o dohodnuté frekvenci používá sdružování 7-8 bitů přenášených dat do bajtů (+start bit+případný „parity bit“+stop bit) RS 232/422/485

U ethernetových linek přenos probíhá po rámcích (paketech, datagramech) záhlaví - smluvní synchronizace 62 bitů (série 101010... + poslední dva bity 11) cílová a zdrojová unikátní MAC-adresa (á 48 bitů) 16-bitové číslo označující délku dat (a nebo typ pro hodnoty >1500) vlastní přenášená data minimální šířka 64 Bajtů (jsou-li přenášená data kratší, doplní se „Pad“ nulami) maximální šířka dat: 1500 Bajtů (u GLAN možnost „jumbo frames“ až 9000B)

kontrolní součet (CRC-32)

Ethernet paket (PAM-5 modulace)


4/9

Kontrola přenášených dat Smyslem bezpečnostních kódů je detekovat a dle možností i opravit nalezené chyby: „Kontrolní součet“ bývá doplňková informace, předávaná typicky s vlastní informací nejúčinnějším zabezpečením by bylo „zopakování zprávy“ (rozdíl=potenciální chyba), případně „zopakování 3×“ (dojde-li z každé bitu 2 ze 3 kopií správně, lze chyby opravit) ...ale to by znamenalo 2 resp. 3-násobný nárůst objemů přenášených dat (nevýhodné). => používají se různé postupy zhotovování „otisků“ (hashovací funkce), schopných při přepočtu a porovnání u příjemce najít/opravit určité množství chyb v přeneseném bloku: Parita (počet jedničkových bitů ve slově) - často se používá u sériových (RSxxx) rozhraní Hammingův kód, izokódy (data=určité vrcholy „kódovací krychle“ - schopnost korekce) - čarové kódy, modemové signály, ... Modulo+, Cyklický redundantní součet (CRC) – operace s binárními polynomy - Ethernet (CRC32), Modbus (CRC16),... Message-Digest algorithm (MD4, MD5) Secure Hash Algorithm (SHA1, SHA2,...) … bezpečnostní kódy jsou zaměřeny na náhodné chybové stavy, ne na úmyslné záměny ...CRC, MD4/5 i SHA 1 už byly prolomeny – buď hrubou silou a nebo matematicky. Zpracování informací, cvičení 2.

5/9

Kontrola přenášených dat Díky rozvoji Internetu a sítí typu Ethernet je nejčastěji používanou formou kontroly správnosti přenášených dat algoritmus CRC32 (postupné dělení binárních polynomů) Ukázka – Matlab (Matlab, Octave):

Ukázka – Pascal (Delphi, Lazarus,..):

#CRC32 – reverzní varianta

program crc32; {$APPTYPE CONSOLE} uses SysUtils; CONST crc := $FFFFFFFF; //pro CRC16: $FFFF polynom := $EDB88320; //crc16: $A001; vstup: string='Ahoj'; VAR i,j:integer;crc,polynom : Int64;

crc = 0xFFFFFFFF; #pro CRC16: $FFFF polynom = 0xEDB88320; #crc16: $A001 vstup = "Ahoj"; for i=(1:length(vstup)) znak= vstup(i)+0; begin crc = bitxor(crc,znak); for i:= 1 to length(vstup) do begin for j=(1:8) crc := crc XOR byte(vstup[i]); if (bitand(crc,1)== 1 ) crc= bitxor(bitshift(crc,-1), polynom); for j:= 1 to 8 do begin if (crc and 1) = 1 //and 1 ~ mod 2 elseif then crc:= (crc shr 1) XOR polynom crc= bitshift(crc,-1); else crc:= (crc shr 1); //shr1~div 2 endif end; endfor end; endfor crc:=crc xor $FFFFFFFF;//inverze (Ethernet) crc=bitxor(crc,0xFFFFFFFF); Writeln(inttohex(crc,8));readln; printf("%X\n",crc) end.


6/9

Metody komprese dat Data často obsahují velký objem nadbytečné (redundantní) informace ⇒ Komprese dat (při přenosu a nebo archivaci) může přinést významné úspory objemové (menší objem dat=stačí levnější médium, na stávající se vejde víc) časové (přenesení menšího množství dat trvá kratší dobu) úspory přenosového pásma (nižší nároky na přenos danou rychlostí) ...cenou za kompresi bývají zvýšené nároky na výpočetní výkon, potřebný při kompresi i expanzi! Bezeztrátové metody (schopnost 100% rekonstrukce přenášených dat): Morseův princip (1837, frekvenčně uspořádaná tabulka, 3-stavová logika) Huffmanovy „minimální“ kódy (binární stromy;uzly umožňují rekonstruovat kódová slova) Metoda potlačení nul („RLE“ + rozdílové a prefixové varianty - PCX) Slovníkové metody (LZx – adaptivně vytvářený slovník pro rekonstrukci dat - GIF) nejčastěji: kombinované metody (Fanon-Shanon, BWT(BZIP), PNG,...) Ztrátové kompresní algoritmy (tam kde k pochopení zprávy není nutná 100% shoda) Komprese zvukových souborů (MPEG1 Layer 3, WMA, Vorbis Ogg,...) Komprese statického obrazu (JPEG/JFIF - DCT, JPEG2000 - waveletová fce) Kodeky (KODér/DEKodér) pro kompresi videa (MJPEG, DV, MPEGx, DivX,..), postupy pro mezisnímkovou kompresi, GOP – Group of Pictures (IPB snímky) Fraktálová komprese (zatím spíš teoreticky...) Zpracování informací, cvičení 2.

7/9

Metody šifrování dat V situacích kde obsah přenášených dat je důvěrný a jejich bezpečnost není možné zajistit „hardwarově“ (vyhrazená linka uvnitř areálu s ostrahou, trezor,..) je možné k jejich utajení použít vhodné kombinace metod utajení obsahu: „Historické“ přístupy (při zachycení více zpráv obvykle málo odolné kryptoanalýze): Steganografie: ukrytí zprávy do jiného objektu (mikrotečky, vodotisky,...) Substituční kódy: Nahrazení elementů zprávy jinými, dle dohodnutého klíče (náhradní abecedy, kódovací knihy a stroje - ENIGMA, „cizí“ jazyky – kód Navajo) Transpoziční šifry: Přeházení obsahu zprávy dle dohodnutého schématu Moderní postupy (bezpečnost nesmí záviset na utajení technologie šifrování, ale na utajení hesla): Symetrické šifry: kombinace kódu znaků textu s 1 tajným heslem (DES, AES) ...problém s bezpečnou distribucí klíčů, odolnost proti prolomení lze zvýšit delším klíčem Asymetrické šifry: kódování veřejným/dekódování soukromým klíčem (RSA) ...oba klíče jsou založeny veřejném exponentu a na „velkých“ tajných prvočíslech (100míst?) ...bez znalosti těchto prvočísel je zašifrovaná zpráva nečitelná (nalezení je extrémně náročné) ...soukromý klíč příjemce nemusí nikam posílat, je tedy „v bezpečí“. Digitální podpisy: Kombinace hashovacích funkcí s asymetrickým přístupem


8/9

Metody šifrování dat Asymetrický šifrovací algoritmus RSA Publikováno v roce 1978 - Ron Rivest, Adi Shamir a Leonard Adleman (identický ale nepublikovaný postup byl už v 60. letech vyvinut u britské MI5) Průmyslový standard pro šifrovaný přenos dat po internetu a pro elektronický podpis Obvyklý postup (podrobnosti viz např. http://en.wikipedia.org/wiki/rsa) Vygenerujeme 2 dostatečně velká prvočísla p, q Vypočítáme jejich součin n=p×q Vypočítáme hodnotu Eulerovy funkce φ(n)=(p-1)×(q-1) Zvolíme přirozené (celé) číslo e, aby 1 < e < φ(n) nesoudělné s φ(n) K němu určíme „multiplikativní inverzi“ d, kde (d×e) mod φ(n) = 1 e a n odteď budou tvořit veřejný klíč (obě lze publikovat) d a n pak budou tvořit soukromý klíč (d je nutno utajit) Šifruje-li klient ve zprávě znak s kódem m, pak c(m,e,n)=me mod n je šifrou; Majitel soukromého klíče ji pak dekóduje: m(c,d,n)=cd mod n (kód m obvykle nebývá přímo ASCII kód, ale výsledek „padding“ šifry PSS) Příklad: Zkuste provést postup RSA krok za krokem v programu který máte a zvládáte! Zpracování informací, cvičení 2.

9/9

Zpracování informací

Recommend Documents