Protichybové kódy, komprese a jak bluffovat o kryptografii"

Protichybové kódy, komprese a “jak bluffovat o kryptografii" ˇ Pˇrednáška pro SCS

Ing. Jakub Št’astný, Ph.D.1 1 FPGA

Laboratoˇr/Laboratoˇr zpracování biologických signálu˚ ˇ Katedra teorie obvodu, ˚ FEL CVUT Technická 2, Praha 6, 166 27

ˇ 21. kvetna 2014

Osnova pˇrednášky 1 Protichybové kódy

Úvod Lineární kódy Pˇríklady a aplikace 2 Komprese dat

Bezeztrátové kompresní techniky Ztrátová komprese 3 Jak bluffovat o kryptografii

ˇ 4 Razení

Varování

ˇ Pozor! Tato verze pˇrednášky obsahuje materiál chránený autorskými právy. Je urˇcena pouze k internímu použití a vystavení na WWW stránkách Laboratoˇre biologických signálu, ˚ ˇ Katedry teorie obvodu˚ CVUT FEL, Praha! http://amber.feld.cvut.cz/fpga/prednasky/scs/scs.html

Doporuˇcená literatura

• Jiˇrí Adámek, Kódování. SNTL Praha 1989 • Jan Hlaviˇcka,Diagnostika a spolehlivost. Praha,

ˇ Vydavatelství CVUT, 1998 • Steven W. Smith, The Scientist and Engineer’s Guide to

Digital Signal Processing. Dostupné na www.dspguide.com

Úvod do ˇ bezpecnostních kódu˚

Aplikace, základní definice • aplikace • pˇrenos dat v cˇ ase i prostoru • tolerance poruch • kódování: zobrazení K : A → B ∗ , kde • A – zdrojová abeceda, znaky • B – kódová abeceda, znaky • B ∗ – množina vsech slov nad danou abecedou • kód – množina všech slov K (A) • jednoznaˇcneˇ dekódovatelné: K ∗ : A∗ → B ∗ prosté

zobrazení • blokový kód – všechna kódová slova mají stejnou délku n

Bezpeˇcnostní kódy

• jistota bezpeˇcnosti neexistuje • umelé ˇ zvýšení redundance – zabezpeˇcení pˇred šumem • K (A) ⊂ B ∗ • pˇríjem kódového slova x – ? • pˇríjem nekódového slova x ∈ / K (A) – objevení chyby

Hammingova vzd. a vlastnosti kódu • definici známe... • DCv: dokažte že H.v. je metrika na kódu • Kód s minimální H.v. d objevuje všechny t-násobné chyby

pro t < d . • Kód je schopen opravovat t-násobné chyby má li H.v.

alesponˇ 2t + 1. • pˇríklad: opak. kód pro opravu dvojnásobné chyby • 0 → 00000 • 1 → 11111

Opakovaci kod pro opravu dvojnasobne chyby 00000 00001 00011 00111 01111 11111 0 1 H.v.=5

Typy kódu˚

• blokové (n, k) kódy: • k puvodních ˚ bitu˚ zdrojové zprávy • n − k bitu˚ redundance • konvoluˇcní kódy • generované kódové slovo závisí jak na aktuálním slove, ˇ tak na urˇcitém poˇctu pˇredchozích zpráv • terminologie • SEC = Single Error Correcting • DED = Double Error Detection • SEC-DED ? • TED ?

Systematický (n, k )kód • k puvodních ˚ bitu˚ zdrojové zprávy • n − k bitu˚ redundance • H.v. d ≤ n − k + 1 (proˇc?) k bitu puv. zpravy

n−k bezp. informace

Lineární kódy

• aritmetika modulo 2 (1+1=?) • blokový kód délky n je lineární iff kódová slova tvoˇrí

lineární podprostor prostoru T n , T = {0, 1} • kódová slova lze vyjádˇrit jako množinu všech ˇrešení

soustavy rovnic, • aplikace prostˇredku˚ lineární algebry • pˇríklad: sudá parita • KPE : v1 v2 v3 v4 → x1 x2 x3 x4 x5 • x1 x2 x3 x4 = v1 v2 v3 v4 • x5 aby poˇcet jedniˇcek v celém sloveˇ byl sudý • x1 + x2 + x3 + x4 + x5 = 0

Lineární kódy • pˇríklad: opakovací kód délky 5 pro opravu dvojnásobné

chyby 0 → 00000, 1 → 11111 • soustava rovnic které vyhovují všechna kódová slova • x1 + x2 = 0 (rce. 1) • x1 + x3 = 0 (rce. 2) • x1 + x4 = 0 (rce. 3) • x1 + x5 = 0 (rce. 4) • kódové slovo 00000 – všechny rce. splneny ˇ – OK • kódové slovo 11111 – všechny rce. splneny ˇ – OK • slovo 11011 – rce. 2 neplatí – chyba! • slovo 10101 – rce. 1 a 3 neplatí – chyba! Opakovaci kod pro opravu dvojnasobne chyby 00000 00001 00011 00111 01111 11111 0 1 H.v.=5

LinKódy – Kontrolní matice kódu H • matice soustavy rovnic které vyhovují všechna kódová

slova • Hx = 0, H ∈ Mn−k ,n pro (n, k) kód • pˇríklad: op.k. délky 5, 4 rc.–4 ˇrádky,5 bitu–5 ˚ sloupcu˚ • x1 + x2 = 0,x1 + x3 = 0,x1 + x4 = 0,x1 + x5 = 0   1 1 0 0 0  1 0 1 0 0   H=  1 0 0 1 0  1 0 0 0 1 • pˇríklad: sudá parita délky 5 • x1 + x2 + x3 + x4 + x5 = 0 H= 1 1 1

1 1

(1)

(2)

LinKódy – Generující matice kódu G

• popisuje kódování, x = vT G • báze kódového prostoru → všechna kódová slova jsou LK

slov z G • pro H = [B|E] je G = [E ′ |B T ] • pˇríklad: opakovací kód délky 5 G = [11111]

 

• pˇríklad: sudá parita délky 5 G =  

kóduji slovo v = [1101]T , x = vT G

1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 = [11011]T

 1 1   1  1

LinKódy – Oprava a detekce chyb • vyšleme x, získáme w = x + e • e – chybový vektor • Hw = H(w + e) = He • pro e nekódový chybový vektor objevíme chybu a mužeme ˚

ji i opravit • pˇríklad: opakovací kód délky 5  1 1 0 0 0  1 0 1 0 0   • H=  1 0 0 1 0  1 0 0 0 1 • pˇríjem slova w = [11111]T →Hw = [0000], OK • pˇríjem slova w = [11011]T →Hw = [0100], chyba! 

Pˇríklady a aplikace

Hammingovy kódy • perfektní blokový kód pro opravu jednoduchých chyb • tˇrída blokových (2m − 1, 2m − m − 1) kódu˚ • m = 3 . . . (7, 4) • m = 4 . . . (15, 11) • sloupce kontrolní matice jsou všechna nenulová slova

dané délky • pˇríklad pro (7, 4) kód 

 0 0 0 1 1 1 1 H= 0 1 1 0 0 1 1  1 0 1 0 1 0 1

(3)

• vyplatí se pˇreskupení do tvaru



 1 1 1 0 1 0 0 H= 1 1 0 1 0 1 0  1 0 1 1 0 0 1

(4)

Pˇríklad zabezpeˇcení NAND Flash • ST-Microelectronic, AN1823 App Note • SEC-DED po bloku 256 byte Figure 4. Parity Generation for a 256 Byte Input Byte 0

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP0

Byte 1

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP1

Byte 2

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP0

Byte 3

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP1

...

...

...

...

...

...

...

...

...

Byte 252

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP0

Byte 253

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP1

Byte 254

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP0

Byte 255

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP1

CP1

CP0

CP1

CP0

CP1

CP0

CP1

CP0

CP3

CP2 CP5

CP3

CP2 CP4

LP02 ... LP14 LP03

LP02 ... LP15 LP03

Pˇríklad zabezpeˇcení NAND Flash • ST-Microelectronic, AN1823 App Note • SEC-DED po bloku 256 byte • Hamminguv ˚ kód (2070, 2048) Figure 4. Parity Generation for a 256 Byte Input Byte 0

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP0

Byte 1

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP1

Byte 2

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP0

Byte 3

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP1

...

...

...

...

...

...

...

...

...

Byte 252

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP0

Byte 253

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP1

Byte 254

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP0

Bit 7

Bit 6

Bit 5

Bit 4

Bit 3

Bit 2

Bit 1

Bit 0

LP1

CP1

CP0

CP1

CP0

CP1

CP0

CP1

CP0

Byte 255

CP3

CP2 CP5

CP3

CP2 CP4

LP02 ... LP14 LP03

LP02 ... LP15 LP03

Další aplikace

• RAM pameti ˇ – výtežnost ˇ výroby • TMR systémy • safe FSMs • aritmetické kódy

Kontrolní souˇcet

• jednoduchá technika detekce chyby v datech • xs =

P

xi mod 2N , nakonec xs = −xs

• rychlý a snadný výpoˇcet • proti náhodné modifikaci • ne proti úmyslné zmen ˇ eˇ (vložení nul do dat, prohození

poˇradí slov, více chyb kde • pˇríklady aplikace

P

ei = 0).

• selftest ROM (kontr. souˇcet pameti), ˇ EEPROM s konfig.

daty cˇ ipu • RAM

Cyclic Redundancy Check

• kódy pro detekci a opravu chyb • vstup – tok dat libovolné velikosti • výstup – “kontrolní souˇcet" – blok dat fixní velikost • ochrana proti shlukum ˚ chyb • matematika kolem CRC dosti komplexní, viz [Adámek] • n-bitové CRC aplikované na blok dat libovolné délky

detekuje • jakýkoliv jeden shluk chyb o velikosti max. n • s p = 1 − 2−n libovolný vetší ˇ shluk chyb

Cyclic Redundancy Check

• definováno pomocí delení ˇ polynomem • výpoˇcet pomocí jednoduchého obvodu • normalizované polynomy s danými vlastnostmi • pˇr. x 8 + x 7 + x 6 + x 4 + x 2 + 1 • poˇcítáme vlastneˇ zbytek po delení ˇ polynomem • víme, že x 8 + x 7 + x 6 + x 4 + x 2 + 1 ≡ 0(modx 8 + x 7 + x 6 + x 4 + x 2 + 1) • x 8 ≡ −x 7 − x 6 − x 4 − x 2 − 1(modx 8 + x 7 + x 6 + x 4 + x 2 + 1) • sem pˇríští rok obrázek CRC generátoru – letos byl na vyžádání na tabuli

Komprese dat

ˇ Základní delení

• bezeztrátová (lossless) • spustitelný kód, textová data, numerické soubory, ... • pro daný soubor a algoritmus fixní kompresní pomer ˇ • ztrátová (lossy) • hudba, fotografie, ... • cˇ ím vetší ˇ kompresní pomer, ˇ tím horší kvalita • percepˇcní komprese • proˇc komprese? cena...

Run-Length Encoding

• nejjednodušší technika • základ dalších metod – JPG, MP3 • data cˇ asto obsahují sekvenci stejných slov • 17 8 54 0 0 0 97 5 16 0 45 23 0 0 0 0 0 ... • 17 8 54 0 3 97 5 16 0 1 45 23 0 5 • komprimovat lze sekvence libovolných znaku˚ • ˇrídící_znak opak_byte poˇcet • i jednoduchý výskyt ˇrídícího znaku je pak kódován

Huffmanovo kódování • základ daších metod – JPG, MP3 • prefixový kód: prefixem slova b1 b2 b3 . . . bn jsou... • prefixové kódování: prosté a žádné slovo není prefixem

jiného slova • Zde jsem letos na tabuli delal ˇ Huffmanuv ˚ strom, pˇríští rok jako slídu

Delta kódování • pro spojité signály • malé zmeny ˇ – malé hodnoty, kvantování • kombinuje se s Huffmanovým kódováním, nebo RLE

LZW Komprese

• Lempel-Ziv-Welch • text, spustitelné kódy na 50% • použití: NTFS, GIF, ... • (už ne)patentovaný algoritmus slovníkové komprese • více viz http://www.dspguide.com/ch27/5.htm

Ztrátová komprese

JPG komprese • Joint Photographers Expert group, 1992 • transformaˇcní komprese • základní myšlenka: po výpoˇctu spektra už si nejsou

ˇ všechna data "rovna", NF složky jsou duležit ˚ ejší

JPG komprese – postup 1

rozklad obr. na cˇ tvereˇcky 8 × 8

2

výpoˇcet 2D DCT ze "ˇctvereˇcku" ˚ – 2D spektra

JPG komprese – postup 1


2


3

aplikace kvantizaˇcní matice, vybrána podle kompresního ˇ pomeru

JPG komprese – postup

1


2


3

aplikace kvantizaˇcní matice

4

konverze 2D vzoru do lin. pole, VF komponenty blízké nule se dostanou “za sebe" což je výhodné pro RLE kompresi

JPG komprese – postup

1


2


3

aplikace kvantizaˇcní matice

4

konverze 2D vzoru do lin. pole

5

Run-Length Encoding

6

Huffman encoding

ˇ JPG komprese – kompresní pomer

MP3 komprese – psychoakustický model MPEG Layer III = MP3, SPL = Sound Pressure Level

Zdroj: Audio Coding: An Introduction to Data Compression http://www.digitaltvdesignline.com/howto/hdrecording/202601553

MP3 komprese – maskování ve frekvenci • práh slyšitelnosti není fixní • schováme q-šum tam, kde není slyšet


MP3 komprese – maskování v cˇ ase • maskování dokonce i pˇred! tónem

MP3 komprese – postup komprese 1 2 3 4 5

adaptivní segmentace výpoˇcet spektra identifikace sluchoveˇ významných harmonických složek výpoˇcet práhu slyšitelnosti ˇ všeho co “není" slyšet odstranení ˇ až 10:1 Kompresní pomer


Jak bluffovat o kryptografii

Terminologie • plaintext/otevˇrený text – originální zpráva • ciphertext/šiforvaný text – zašifrovaná zpráva • cipher/šifra – algoritmus pˇrevádející ˇ otevˇrený text na

šifrovaný text • key/klíˇc – informace použitá šifrou a známá jen odesílateli

a adresátovi • cryptography/kryptografie – hledání metod jak zajistit

bezpeˇcnost ŠT • cryptanalysis/kryptoanalýza – studium principu˚ a metod

ˇ et ˇ OT bez znalosti klíˇce jak se dozved • bloková šifra – po blocích • proudová šifra – kontinuálneˇ

K cˇ emu je kryptografie

• autentizace uživatele • autentizace dat (integrita a originalita puvodu) ˚ • potvrzení puvodu ˚ • utajení dat • aplikace • telekomunikace (GSM, etc.) • multimédia (DRM, DVD, SAT TV) • obecná komunikace (mail) • bankovní sektor

Implementaˇcní vlastnosti šifer

• náklady na prolomení úmerné ˇ ceneˇ kódované zprávy • Freshness/novost – pro stejný OT nikdy není stejný ŠT • implementace bez postranních kanálu˚ (ˇcasový útok, DPA,

SPA) • Kerckhoffuv ˚ princip (Shannonova formulace): “The enemy

knows the system."

Symetrické šifry

• odesílatel i adresát

používají stejný klíˇc • rychlost • nutnost distribuce

klíˇcu˚ • pro n osob

n(n−1) 2

klíˇcu˚ • DES, 3DES,

BlowFish, IDEA, AES,... Figure is copied from http://commons.wikimedia.org/wiki/Image:Symetrick%C3%A1_%C5%A1ifra.png

Asymetrické šifry

• odesílatel a adresát

mají odlišné klíˇce • jednoduché pˇredání

klíˇce • málo klíˇcu˚ • pomalost • oveˇ ˇ rení pravosti

klíˇce • RSA,... Figure is copied from http://upload.wikimedia.org/wikipedia/commons/f/f9/Public_key_encryption.svg

Digitální podpis • ekvivalent zaruˇceného podpisu • autenticita, nezfalšovatelnost, nezamenitelnost ˇ a

nepopiratelnost autorství dokumentu • algoritmus podpisu – podpisování – odesílatel: 1 2

výpoˇcet otisku (hash funkce) z dokumentu zašifrování otisku soukromým klíˇcem a pˇriložení k dokumentu

• algoritmus podpisu – oveˇ ˇ rení – adresát: 1 dešifrování pˇriloženého otisku veˇrejným klíˇ cem 2 výpoˇ cet skuteˇcného otisku z dokumentu 3 srovnání obou, rovnají se → potvrzení identity • oveˇ ˇ rení puvodu ˚ veˇrejného klíˇce 1 cerfifikaˇ cní autorita zašifruje veˇrejný klíˇc odesílatele svým privátním klíˇcem 2 adresát rozšifruje veˇrejný klíˇ c odesílatele veˇrejným klíˇcem certifikaˇcní autority

Kvantová kryptografie

• pozorování mení ˇ stav objektu – jistá detekce odposlechu • distribuce klíˇce

ˇ Razení dat

Základní pojmy • tˇrídení ˇ – podle relace ekvivalence • ˇrazení – podle relace uspoˇrádání • sekvenˇcní/pˇrímý pˇrístup k datum ˚ • pˇrirozenost – pˇredˇrazená data se seˇradí rychleji • stabilita – nemení ˇ se poˇradí shodných položek • prostorová a cˇ asová složitost (min. Nlog2 N kroku) ˚ • vnitˇrní – vnejší ˇ ˇrazení dat • ˇrazení s pˇresunem – bez pˇresunu položek (indexový

soubor) • existují hotové generické knihovny

Metody

• Bubble sort, Quick sort – “na tabuli" • Merge sort – rekurzivní skládání posloupností • Radix sort – ˇrazení podle ˇrádu˚

ˇ • Razení s pomocí rozptylovacích funkcí • Specielní paralelní algoritmy – Shear sort, Bitonix sort • atd...

ˇ ˇ Razení výberem maxima/minima

• ˇrazení postupným vyhledáváním min/max hodnoty • O(N 2 ) • stabilní algoritmus

ˇ ˇ Razení postupným zameˇ nováním • ˇrazení postupným vyhledáváním min/max hodnoty • O(N 2 ) • stabilní algoritmus procedure bubbleSort(A : list of sortable items) n := length(A) do swapped := false n := n - 1 for each i in 0 to n do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped

QuickSort

• ˇrazení technikou rozdel ˇ a panuj • O(N log N) • nestabilní algoritmus function quicksort(array) var list less, greater if length(array)≤1 return array select a pivot value pivot from array for each x in array if x ≤ pivot then append x to less if x > pivot then append x to greater return concatenate(quicksort(less), pivot, quicksort(greater))

Protichybové kódy, komprese a jak bluffovat o kryptografii"

Recommend Documents