plik

��Podstawowe pojcia, wykrywanie bBd�w Poziom reprezentacji: inaczej warto[, jak przypisujemy ReguBa Nyquista: je[li sygnaBy maj skBadowe o DES Data Encryption Standard: symetryczny, opis wszystkim kwantyzowanym liczbom w danym przedziale. czstotliwo[ciach pomidzy f1 a f2 to, aby odtworzy dokBadnie opublikowany, zaprojektowane do dziaBania jako hardware, Wsp�Bczynnik informacji = log|k|*(1/n) Poziom decyzyjny: kraniec przedziaBu kwantyzatora, poziom�w sygnaB, musimy pr�bkowa z czsto[ci co najmniej 2(f2-f1) szyfruje bloki 64 bit�w, 56 bitowy klucz, dziaBa tylko brute force: OdlegBo[ Hamminga - d(a,b)= . tych jest o 1 mniej ni| poziom�w decyzyjnych. pr�bek na sekund. - szyfrowanie i deszyfrowanie skBada si z 16 rund, Minimalna odlegBo[ Hamminga = d => kod wykrywa d-1 Kwantyzacja adaptacyjna w prz�d: zakBadamy, |e warto[ Filtrowanie cyfrowe: suma wa|ona bie|cego i poprzednich - ka|da zawiera te same obliczenia na wyniku poprzedniej rundy i bBd�w i koryguje . [rednia wej[cia jest r�wna 0, na podst. bloku N kolejnych pr�bek wej[ filtra i ew. tak|e wyj[ filtra: , z innym podkluczem, Minimalna waga d (dla pewnego a0: d = d(a0,0)) = minimalna (w chwili t) szacujemy wariancj zr�dBa: , warto[ci {ai} i {bj} nazywamy wsp�Bczynnikami filtra. - podklucze generowane s z klucza gB�wnego za pomoc odlegBo[ d(a,b). Reakcja impulsowa: niezerowy cig wsp�Bczynnik�w na wyj[ciu przesuni cyklicznych, przesyBamy (skwantowan) informacj o wariancji do dekodera. Kod Hamminga: n=2m-1, k=2m-m-1, d=3. filtra (zazwyczaj dla cigu wej[ciowego: 1, 0, 0, & ). - blok tekstu jawnego jest permutowany na pocztku i koDcu Kwantyzacja adaptacyjna wstecz (kwantyzator Jayanta): Kod cykliczny (n,k) (n = stopieD g(x) musi by dzielnikiem xn-1, Filtry dzielimy na te o skoDczonej i nieskoDczonej reakcji. algorytmu (Batwe hardwarowo, trudne softwarowo), do zmiany wykorzystujemy wcze[niejsze dane (w postaci Wielomian parzysto[ci h(x) = . Filtry czsto Bczy si kaskady (str. drzewiaste), dobierane s do - dziki wykorzystaniu sieci Feistela, deszyfrowanie przebiega skwantyzowanej), ka|dy przedziaB ma przypisany mno|nik Mk, sygnaBu, pasma mog si nakBada lub nie, redukcja pr�bek na niemal identycznie jak szyfrowanie (tak sama funkcja f), mno|niki przedziaB�w wew. <� 1, a zewntrznych > 1, je|eli w wyj[ciu odpowiada redukcji rozmiaru czstotliwo[ci. deszyfrowania mo|na wic u|u do zaszyfrowania wiadomo[ci, Kompresja bezstratna kroku n-1 pr�bka wpadBa do przedziaBu l(n-a) to parametr � dla Zastosowania: w�wczas odszyfrowuje si j funkcj szyfrujc (wykorzystane nastpnego kroku: , je[li wej[cie jest dobrze Miara informacji - i(A)= . - kodowanie mowy G.722: tryby 64, 56 i 48 kbps, filtr 7kHz jest to np. w algorytmie 3DES). Entropia ([rednia informacja) H= . dopasowane to iloczyn kolejnych wsp. = 0. jako ochrona przed aliasingiem przy pr�bkowaniu 16000/s, ka|da Niekt�re rozwizania wprowadzone w DESie: Kwantyzacja z kompanderem: przed kwantyzacj Kod jednoznacznie dekodowalny, speBnia: L >= H, L [rednia pr�bka kodowana przy pomocy 14 bitowego jednolitego - permutacja rozszerzajca: permutuje wszystkie i dubluje dBugo[ kodu (podstawowe twierdzenie Shannona). przeksztaBcamy dane za pomoc jakiej[ funkcji(kompander), po kwantyzatora i przepuszczana przez bank 24-rzdowych filtr�w niekt�re bity, Test na jednoznaczn dekodowalno[: rekonstrukcji przeksztaBcamy za pomoc funkcji odwrotnej. FIR, ich wynik jest redukowany o wsp�Bczynnik 2 i kodowany - S-Boksy: dziel blok na cigi 6 bitowe i zastpuj ka|de 6 bit�w Kwantyzacja wektorowa: zamiast pojedynczych element�w 1. lista sB�w kodowych, ADPCM (6 bit�w na pr�bk z mo|liwo[ci odrzucenia 1 lub 2 4 wg. z g�ry okre[lonego schematu, 2. sprawdza pary a| znajdzie si prefiks, wtedy sufiks doda do kwantyzujemy caBe bloki, ni|sze pasmo i 2 bity wy|sze), - P-Boksy: perutacja bit�w wg. okre[lonego schematu Zredniokwadratowy bBd kwantyzacji: Q(X) = Yi �� "Yi " C listy, - kodowanie dzwiku MPEG: schematy kodowania Layer 1, 2, {adne z tych operacji nie s wyliczane, ale zamiast tego s one 3. gdy sBowo (sufiks) ju| jest na li[cie kod niejednoznaczny, ||X - Yj|| d" ||X - Yi||, C sBownik kwantyzatora, 3, ka|dy kolejny bardziej skomplikowany i dajcy lepsz przypisane na staBe do okre[lonych cig�w bit�w/ich pozycji. 4. osignicie koDca listy - kod jednoznaczny. (znieksztaBcenie liczymy po pr�bkach), kompresj, kodery zgodne w g�r, Layer 1 i 2 u|ywaj banku 32 Nier�wno[ Krafta-McMillana . Poziom kompresji: sBownik zawiera K element�w, wektor filtr�w (32 podpasma o szeroko[ci fs/64, fs cz. pr�bkowania Kody Shannon-Fano: dBugo[ kodu li= , [rednia dBugo[ r�wna 32k, 44,1k lub 48k), wyj[cie kwantyzowane przy u|yciu wej[cia ma wymiar L: d" H+1. - zakodowanie numeru wektora - bit�w, r�wnomiernego kwantyzatora ze zmienn liczb bit�w (model Konstrukcja kodu Shannon-Hano: - wektor zaw. rekonstruowane warto[ci z L pr�bek, psychoakustyczny wBasno[ci ludzkiego ucha), w Layer 1 i 2 - niech l1 d" l2 d" & d" lN, ramki zawieraj 384 i 1152 pr�bki (ma to wady przy du|ej - liczba bit�w na pr�bk: . - definiujemy pomocnicze w1, w2, & , wN jako w1=0, , zmienno[ci sygnaBu i zostaBo poprawione w 3), Algorytm Linndego-Buza-Graya: - binarna reprezentacja wj dla j > 1 zajmuje bit�w, - kodowanie obraz�w: obraz dzielimy za pomoc filtr�w 1. wybierz dowolny zbi�r rekonstruowalnych warto[ci , - liczba bit�w wj jest mniejsza lub r�wna lj, dla w1 to oczywiste, (najlepiej separowanych, aby mo|na byBo je stosowa oddzielnie ustal k=0, D(-1)=0, wybierz pr�g �, - w ka|dym z wymiar�w), g�rno i dolno przepustowych, a nastpnie 2. znajdz obszary kwantyzacji dziesitkujemy wyj[cie o czynnik 2, w ka|dym kroku rozkBadamy Kodowanie: " , tylko 1 z 4 podobraz�w (podobrazi o wysokiej czstotliwo[ci maj Kody Huffmana: wszystkie maj tak sam [redni dBugo[ dla 3. oblicz znieksztaBcenie wikszo[ wsp�Bczynnik�w blisk 0), danego cigu, kodowanie w czasie liniowym, optymalne kody prefiksowe, mo|liwo[ implementacji dynamicznej. , - kompresja wideo: czsto klatki niewiele si r�|ni, pewne znieksztaBcenia s sBabo widoczne (niewyraznie krawdzie), Kody Tunstalla: znak z najwikszym prawdopodobieDstwem np. 4. je[li zakoDcz obliczenia, niekt�re bardzo (zmiany jasno[ci pow. migotanie), w predykcji a zastepujemy aa,ab,ac 5. przyjmij k<�-k+1, za nowe przyjmij [rodki ci|ko[ci nastpnych klatek mo|na wykorzystywa poprzednie, predykcja Zrednia dBugo[ = , ei sBowo kodowe Rozszerzenia DESa: musi uwzgldnia ruch obiekt�w, aby unikn bBd�w, co jaki[ , wr� do korku 2. odpowiadajce i-temu kodowi. - DESX dodanie whiteningu, dwa dodatkowe klucze utrudniajce czas rezygnujemy z predykcji (co kilka klatek, albo gdy zmiany s Inicjalizacja LBG metoda podziaB�w: Kodowanie arytmetyczne: elementom przyporzdkujemy przeszukiwanie: C = KEXT XOR DESK(P XOR KINT). zbyt du|e), kompresja klatek opiera si na algorytmach kompresji przedziaB [F(i),F(i+1)), F(i) = . - rozpoczynamy z jednym punktem (rozmiar sBownika 1), - 3DES u|ywamy dwa 56 bitowe klucze K1 i K2 oraz trzykrotnie obrazu, bdcym [redni z caBego zbioru uczcego, algorytm DES: C = DESK1-1(DESK2(DESK1-1(P))). Kodowanie: - kompresja ruchu: obraz dzielimy na kratki, szukamy - dodajemy pewien ustalony wektor perturbacji e do ka|dego IDEA: opatentowany, ale bezpBatny do cel�w niekomercyjnych, - d <�- p-l, p <�- l+F(j+1)d, l <�- l+F(j)d, podobnych, po czym przypisujemy im wektor przesunicia. punktu sBownika i wykonujemy LBG, klucze 128 bitowe, bloki s 64 bitowe, algorytm ma 8 rund. znacznik liczba z przedziaBu [l,p) np. . W wideo klatki dzielimy na grupy obraz�w (GOP): - kontynuujemy a| do uzyskania zakBadanej liczby poziom�w Skalowanie: - co najmniej 1 ramka typu I (obraz podobny do JPEGa, (je|eli nie jest potg 2, to w ostatnim kroku nie wszystkie 1. je[li [l,p) �" [0;0,5): wymagane do rozpoczcia [de]kodowania), podwajamy). - [l,p) -> [2l,2p), - kilka klatek typu P (r�|nica pomidzy poprzedni ramk typu P Kwantyzatory o strukturze drzewiastej: - doBcz do kodu 01licznik, lub I a bie|c), - dzielimy przestrzeD na dwie cz[ci i uzyskujemy dla nich - wyzeruj licznik, - opcjonalne ramki typu B (obraz zakodowany z wykorzystaniem wektory reprezentacji, 2. je[li [l,p) �" [05;1): OBY ssiednich klatek typu P lub I, najci|sze obliczeniowo, bBdy - powtarzamy a| uzyskamy pewne drzewo binarne o wysoko[ci k, - [l,p) -> [2l-1,2p-1), nie propaguj si). - je[li zmniejszy to znieksztaBcenie przycinamy niekt�re - doBcz do kodu 10licznik, PrzykBad: I B B B P B B B P B B B P. poddrzewa, - wyzeruj licznik, Algorytmy symetryczne: wideokonferencji kompresja i - optymalne zwykle tylko dla kw. symetrycznych. 3. je[li l<�0.5<�p oraz [l,p) �" [0,25;0,75): dekompresja musz by szybkie. Kratowa kwantyzacja wektorowa: - [l,p) <�- [2l-0,5;2p-0,5), Algorytmy asymetryczne: kompresja mo|e by czaso- i Krata {a1, a2, & , aL} L niezale|nych wektor�w o L wymiarach, - licznik <�- licznik+1. zasobo|erna, ale dekompresja musi by szybka (MPEG-1, MPEG- jest krat je[li wszystkie ui s liczbami Mo|liwe usprawnienia: przej[cie na arytmetyk liczb 2, MPEG-4). caBkowitymi. caBkowitych: [0,1) -> [0,2m-1). Inne kwantyzacje wektorowe: piramidalne, sferyczne i AES Advanced Encryption Standard (Rinjadael): nastpca Kodowanie sBownikowe: sBowniki statyczne tekst kodujemy Kryptografia DESa, klucze w zale|no[ci od potrzeb 128, 192 lub 256, dBugo[ biegunowe, skala-ksztaBt, z usunit [redni, klasyfikowane, jako caBe sBowa ze sBownika, sBowa kt�rych nie ma mo|na wieloetapowe, adaptacyjne. Szyfry strumieniowe na podstawie klucza tworzymy cig bloku to 128 (mo|na zwikszy do 129 lub 256 bit�w), 10 rund umieszcza jako 1-literowe sBowa, wra|liwe na zmian char. Kodowanie r�|nicowe: obliczamy kwantyzacje nie element�w bit�w (potencjalnie nieskoDczony) za pomoc kt�rego szyfrujemy (lub 12, lub 14), szybki w implementacji programowej. danych. ale ich kolejnych r�|nic: tekst jawny np. przy pomocy XORa. kodowanie LZ77: 1. mamy cig {xn}, cig r�|nic {dn} generujemy biorc dn=xn-xn-1 , Efekt lawinowy zmiana jednego bitu szyfrogramu powoduje Wysylamy(w lewo, copy, nowy znak) kwantyzujemy d =Q[dn]=dn+qn otrzymujc {d } (qn - bBd zmian wielu bit�w kryptogramu. n n kodowanie LZ78: kwantyzacji), Szyfr Cezara: kluczem jest s, szyfrowanie c=(p+s) mod 26, (nr slowa, nowy znak) 2. u odbiorcy odtwarzamy {x }: x =x +d , deszyfrowanie p=(c+26-s) mod 26. n n n n LZW: sBownik zawiera na starcie wszystkie poj. Liter 3. std: , Szyfr Vigini�re a hasBo (klucz) dodajemy modulo do blokow (nr slowa) parujemy nowe slowa bBd akumuluje si z czasem zapobieganie: tekstu (mo|na te| XORem) uog�lnienie szyfru Cezara. PPM (Prediction by Partial Matching): u|ywamy dn=xn-x , wtedy x =xn+qn. System Playfair: klucz to kwadrat 5x5 zawierajcy 25 r�|nych n-1 n 1. dla bie|cej pozycji znajdz aktualny kontekst maks rzdu, Predykcja DPCM (Diffirential Pulse Code Modulation): zamiast liter (np. hasBo i cig kolejnych liter alfabetu w nim 2. je[li znak wystpowaB ju| w tym kontek[cie to zakoduj go z r�|nicy midzy kolejnymi elementami mamy funkcj predykcyjn niewystpujcych), w ha[le znaki (wystpujce w kluczu) nie prawdopodobieDstwem wyznaczonym na podstawie statystyk tego generujc {pn}, pn=f(x , & , x ), kodujemy xn-pn , szukamy mog si powtarza n-1 0 kontekstu, takiego f aby jak najmniejsze. Szyfrowanie: 3. w.p.p. zakoduj <�esc> z prawdopodobieDstwem wyznaczonym ZakBadamy, |e (N -rzd predyktora). 1. tekst jawny dzielimy na pary: dla ka|dej wyznaczamy w na podstawie statystyk oraz: Zamiast x u|ywamy xn (zaB. bBdy kw. maBe). kwadracie-kluczu prostokt, n - zakoduj kodowany symbol w kontek[cie o 1 kr�tszym (rzd Szukamy {ai}, aby jak najmniejsze. W 2. dla prostokt�w 1-wymiarowych bierzemy litery na prawo kontekstu > -1), RC4: szyfr strumieniowy, opracowany do cel�w komercyjnych, tym celu: (wsp�lny rzd)/poni|ej (wsp�lna kolumna) nich, - zakoDcz kodowanie symbolu (rzd = -1), implementacja ujawniona anonimowo na listach dyskusyjnych w 3. w.p.p. wybieramy przeciwne rogi prostokta. 1. obliczamy warto[ci oczekiwane N r�wnaD postaci: 94, na podstawie klucza generuje cig bit�w XORowany z 4. zaktualizuj statystyki wystpieD symboli. One-time pad: jednorazowo wylosowany klucz XORujemy z rzd -1 wprowadzony, aby ka|dy symbol daBo si zakodowa , otrzymujc ukBad tekstem jawnym. tekstem jawnym, wymaga osobnego przesyBu klucza. (rozkBad r�wny dla ka|dej litery). , gdzie Rxx(k)=E[xnxn+k] funkcja autokorelacji zmiennej xn. ECB Electronic Codebook: tekst jawny dzielony na bloki dla kontekst�w mo|na utworzy dynamicznie kod Huffmana lub Szyfrowanie asymetryczne 2. je[li znamy warto[ci autokorelacji mo|emy obliczy warto[ci ai. dBugo[ci n, ka|dy szyfrowany za pomoc tego samego klucza K. kod arytmetyczny. Odmiany DPCM: Klucze wystpuj w parach: 1 do szyfrowania 1 do deszyfrowania uszkodzenie/utrata bloku nie wpBywa na reszt, ale mo|liwa jest Zazwyczaj maksymalna dB. kontekstu to 5. - adaptacyjne DPCM (w prz�d i w tyB), (czasem nierozr�|nialne). Opublikowanie klucza szyfrujcego te| podmiana blok�w. CALIC (Context Adaptive Lossless Image Compression): - modulacja delta: dwustopniowy kwantyzator i odp. czsto[ (publicznego) nie zdradza drugiego z kluczy (prywatnego) CBC Cipher Block Chaining: C1=Ek(P1 XOR IV), Ci=Ek(Pi XOR pr�bkowania (2 razy wiksza ni| najwiksza czstotliwo[). (obliczenia zbyt kosztowne). Ci-1 . PrzekBamania 1 bloku ), P1=DK(C1) XOR IV, Pi=DK(Ci) XOR Ci-1 Zastosowanie: kodowanie mowy, obraz�w. Twierdzenie Eulera: a$(n) mod n = 1, dla a wzgldnie zmieniaj tylko 2 bloki po deszyfracji, takie same bloki maj Kodowanie transformujce: przeksztaBca informacj tak, aby pierwszego z n. zazwyczaj r�|ne kryptogramy, ten sam tekst jawny dla tego dh=|W-WW|+|N-NW|+|NE-N| mo|na byBo zrezygnowa z cz[ci element�w: Faktoryzacja liczb jest NP-trudna. samego klucza mo|e mie r�|ne kryptogramy dla r�|nych dv=|W-NW|+|N-NN|+|NE-NNE| 1. podziel sygnaB na bloki, RSA: wektor�w inicjujcych. Pseudokod: 2. oblicz przeksztaBcenie ka|dego bloku, Generowanie kluczy: CFB Cipher Feedback: C0=IV, Ci=EK(Ci-1 ) XOR Pi, Pi=Ci XOR 1. je|eli dh-dv > 80, to X <�- N, 3. skwantuj wsp�Bczynniki, - losowo wybieramy 2 du|e liczby pierwsze p i q (512, 1024 lub EK(Ci-1 ). Wady i zalety jak w CBC. 2. w.p.p., je|eli dv-dh > 80, to X <�- W, 4. skompresuj skwantowane wsp�B. bezstratnie. 2048 bit�w), OFB Output Feedback: S0=IV, Si=EK(Si-1 ), Ci=Si XOR Pi, Pi=Si 3. w.p.p.: Odkodowanie odwrotnie. XOR Ci. Mo|na wysyBa nawet pojedyncze bity, proces - losowo wybieramy e takie, |e e i (p-1)(q-1) wzgldnie pierwsze, - X <�- PrzeksztaBcenia liniowe: generowania cigu szyfrujcego zale|y tylko od cigu - znajdujemy d takie, |e ed mod (p-1)(q-1) = 1, - je|eli dh-dv > 32, to X <�- , 1. cig {x0,& ,xN-1 }: } przeksztaBcamy na {�0,& ,�N-1 pocztkowego i nie zale|y od tekstu jawnego, niebezpiecznie jest - obliczamy n=pq i zapominamy liczby p i q, , - para [e,n] jest kluczem publicznym a [d,n] kluczem prywatnym, - w.p.p., je|eli dv-dh > 32, to X <�- , u|ywa tego samego klucza i cigu inicjujcego. 2. oryginalny cig odtwarzamy: , - bez p i q nie mo|na obliczy d na podstawie e i n, a rozkBad n na - w.p.p., je|eli dh-dv > 8, to X <�- , 3. mo|na poszerzy przeksztaBcenia jednowymiarowe (dzwik) na p i q jest bardzo trudny obliczeniowo. Szyfrowanie symetryczne - w.p.p., je|eli dv-dh > 8, to X <�- . dwuwymiarowe (obrazy), Szyfrowanie: Schemat Feistela: Kodujemy cig r�|nic X-X . 4. wszystkie przeksztaBcenia s ortonormalne. C=E[e,n](m)=me mod n (m <� n). Sie Feistela pozwala na szyfrowanie i deszyfrowanie JPEG-LS: 7 schemat�w predykcji: X =W, X =N, X =NW, X =N+W- Dyskretne przeksztaBcenia kosinusowe (DCT): Deszyfrowanie: informacji tym samym algorytmem, mimo i| funkcja f nie macierz przeksztaBcenia NxN: m=D[d,n](C)=Cd mod n. NW, X = , X = , X = . jest odwracalna. Sie Feistela generuje z tekstu jawnego szyfrogram, a z szyfrogramu tekst jawny. W ten spos�b Poprawno[ wynika z Twierdzenia Eulera i ChiDskiego Nowy standard: konstruowanie algorytm�w szyfrujcych znacznie si upro[ciBo, Twierdzenia o Resztach. Szyfrowanie i deszyfrowanie s 1. je|eli NWe"max(W,N), to X <�-max(N,W), , poniewa| nie trzeba si troszczy o odwracalno[ funkcji f. symetryczne i mo|na je stosowa zamiennie. 2. w.p.p. je|eli NWd"max(W,N), to X <�-min(N,W), Tekst jawny dzieli si na dwa r�wne bloki Li, Ri. Funkcja f jest Algorytm ElGamala: ka|dorazowe szyfrowanie wykorzystuje 3. w.p.p. X <�-W+N-NW. wBa[ciwym algorytmem szyfrujcym. Jako wynik otrzymuje - Batwiejsza do policzenia i lepiej si sprawdza ni| transformata losowo wybran liczb, r�|ne szyfrogramy przy tym samym Poziomy rozdzielczo[ci: si szyfrogram. Numer kolejnej rundy oznaczany jest indeksem i; Fouriera (DFT), kluczu, klucz publiczny tylko szyfruj, prywatny tylko deszyfruje, to oznacza i| wynik szyfrowania jest ponownie i-krotnie 1. kodujemy najpierw [redni kolor kw. 2kx2k, a nast. r�|nic - u|ywana do obraz�w i dzwik�w. algorytm bazuje na trudno[ci obliczenia logarytmu dyskretnego szyfrowany, co polepsza jako[ szyfrowania. midzy t [redni a kw. 2k -1x2k -1, Dyskretne przeksztaBcenie sinusowe: Wykorzystanie: DES, 3DES, Twofish, FEAL. tzn. znalezienia takiego x, |e gx mod p = y na liczbach 2. koDczymy na pikselach (20x20), Szyfrowanie: Li=Ri-1 XOR f(Ri-1 naturalnych. , Ri=Li-1 ,Ki). macierz przeksztaBcenia NxN: , 3. r�|nice nie s du|e i Batwo si kompresuj. Deszyfrowanie: Ri-1 =Ri XOR f(Li,Ki). Generowanie kluczy: =Li, Li-1 Obrazy czarno-biaBe (faksy): linie obraz�w zaw. na przemian - lepsze ni| kosinusowe gdy wsp�Bczynnik korelacji jest - wybieramy liczb pierwsz p (512 bit�w) i liczb g bdc bloki biaBe i czarne, mo|na wic przesyBa tylko ich dBugo[ci generatorem grupy Zp, maBy, - dla danego u|ytkownika wybieramy losowo liczb x <� p 1 oraz - uzupeBnia przeksztaBcenie kosinusowe. Kompresja stratna obliczamy y = gx mod p, Dyskretne przeksztaBcenie Walsha-Hadamarda: Kryteria oceny znieksztaBceD: macierz przeksztaBcenia NxN: , dla potg dw�jki: - kluczem publicznym jest [y,p,g] a kluczem prywatnym [x,p,g]. - czynnik ludzki, Szyfrowanie: , macierz przeksztaBcenia uzyskujemy przez - kwadratowa miara bBdu: d(x,y)= , Szyfrujemy m <� p, wybieramy losowo i tajnie k <� p, obliczamy: a - bezwzgldna miara bBdu: d(x,y)= . normalizacj i ustawienie kolumn w porzdku ilo[ci zmian znak�w = gx mod p, b = m yk mod p. - bBd [redniokwadratowy (mean squared error - mse): (+ na i odwrotnie). Para liczb [a,b] jest kryptogramem dla m. , - proste do uzyskania i implementacji, Deszyfrowanie: - minimalizuje ilo[ obliczeD. b(ax)-1=m yk g-kx = m mod p. - SNR = , SNR (dB) = 10 log10 SNR. Kodowanie podpasmowe: rozBo|enie informacji na cz[ci Miary kwantyzacji: (pasma) i kodowanie ich oddzielnie: Funkcje hashujce i podpisy cyfrowe - [redniokwadratowy bBd kwantyzacji: kwantyzacja Q(x)=y 1. wybierz zbi�r filtr�w do rozkBadu zr�dBa {xn}, MD5: skonstruowana przez Rivesta w 1991, 128 bitowe warto[ci, �� bi-1 2. u|ywajc filtr�w oblicz sygnaBy podpasm {yk,n}, <�xd"bi, w�wczas Batwo implementowana na komputerach 32 bitowych, brak 3. zdziesitkuj wyj[cie filtra, , matematycznych podstaw poprawno[ci. 4. zakoduj zdziesitkowane wyj[cie. - [rednia bitowa kwantyzatora: [rednia liczba bit�w do SHA-1 (Secure Hash Algorithm): opublikowana w USA w 1994, Odkodowanie jest odwrotno[ci kodowania. zapisania jednej wynikowej kwantyzatora. powstaBa przy wsp�Bpracy z NSA, daje 160 bitowe warto[ci, jest Filtry rzeczywiste maj nieostre granice przej[cia (odcicia). cz[ci DSA (Digital Signature Algorithms), kt�ry jest amerykaDskim standardem podpis�w cyfrowych, brak podstaw skonstruuj kompresj stratn z sze[ciostopniowym matematycznych. - wszystkie czynno[ci poza logowaniem si do systemu jednostajnym kwantyzatorem skalarnym. U|ycie symetrycznych algorytm�w szyfrujcych: wykonywane s automatycznie, - dopasowujemy wsp�Bczynniki przy x do siebie(kompredator?), - Schemat Rabina: zakBadamy, |e mamy algorytm szyfrujcy z - wBasnych kluczy u|ywamy tylko do komunikacji z Serwerem tak |eby jedno nadal byBo przedluzeniem drugiego kluczem tej samej dBugo[ci co szyfrowany blok, dzielimy tekst M Kerberosa, a poza nim tylko kluczy sesyjnych, - tworzymy funkcje odwrotna na bloki M1, M2, & , Mt: H0=IV, Hi=EMi(Hi-1 warto[ funkcji - bilety maj okresy wa|no[ci, wic dostp do usBug koDczy si po ), Ht haszujcej dla M. pewnym czasie (system jest czuBy na zakB�cenia zegar�w). W systemie Kerberos przesunieto zegar: to serwer bdzie nadal - Schemat Daviesa: H0=IV, Hi=EMi(Hi-1 warto[ Protok�B SSH: pakiet zaprojektowany, jako bezpieczne zdalne wydawaB bilety, ale bd one miaBy kr�tsz wa|no[. Mo|e si ) XOR Hi-1 , Ht funkcji hashujcej dla M. logowanie, oparty na kryptografii asymetrycznej i [wiadomej zdarzy, |e bilety bd niewa|ne zaraz po ich wydaniu (zale|y jak - Schemat Matyas-Meyer-Oseasa: s funkcja, kt�ra z decyzji u|ytkownika akceptujcej klucze publiczne serwera, z bardzo byB cofnity zegar), co uniemo|liwi dostp. Ponadto, kiedy kryptogramu generuje klucz (mo|e usuwa r�|nic w kt�rym si Bczy. u|ytkownik wy[le pro[b o bilet, to bd one dochodziBy tak jakby dBugo[ciach): H0=IV, , Ht warto[ funkcji Przygotowania: z przyszBo[ci, a |e serwer ma okre[lony czas na wydanie biletu, to - ka|dy komputer w momencie zostania serwerem SSH otrzymuje zaburzony zostanie czas ich wydania, przez co u|ytkownik haszujcej dla M. Podpis RSA: podpisujemy nie sam dokument, a warto[ jego par kluczy (host keys): prywatny (mocno chroniony) i publiczny, otrzyma go p�zniej. funkcji skr�tu. - serwer co jaki[ czas tworzy dodatkow par kluczy (server Podpis: S=RSAKpriv(h(M))=(h(M))d mod n. keys), z kt�rych prywatny jest trzymany tylko w pamici Czy dla poBczenia SSH jest mo|liwy atak man-in-the-middle: Weryfikacja: RSAKpub(S)=Se mod n=(h(M))de mod n =h(M), komputera, PoBczenia SSH opieraj si na przekazywaniu kluczy. Nieznany podpis pod tym samym dokumentem jest zawsze taki sam. - u|ytkownik r�wnie| u|ywa pary kluczy czsto ich generacj, klucz publiczny musi by zaakceptowany przez u|ytkownika. Z Podpis ElGamal: p du|a liczba pierwsza, g generator Zp, obsBug zajmuje si program klienta. tego powodu atak man-in-the-middle nie jest mo|liwy, poniewa| Przebieg logowania: u|ytkownik powinien mie [wiadomo[ akceptacji nieznanego wybieramy x<�p-1 i obliczamy y=gx mod p, klucz publiczny [x,p,g], prywatny [y,p,g]. 1. klient t Baczy si z serwerem i pobiera jego publiczne host key i klucza publicznego (mo|e mie pewne podejrzenia co do Podpis: wybieramy losowe k wzg. pierwsze z p-1, obliczamy: server key, w przypadku pierwszego logowania klient musi autentyczno[ci). Ale z tego samego powodu atak jest - a = gk mod p, zaakceptowa klucze, a w przypadku kolejnych logowaD por�wna prawdopodobny, gdy| u|ytkownik mo|e nie zauwa|y, |e klucz - t = k-1 mod (p-1), klucze z zapamitanymi. Dodatkowo Klient otrzymuje losowy jest podBo|ony i atak dojdzie do skutku. - b = t(h(M)-xa) mod (p-1). identyfikator sesji (cookie), Podpisem jest para (a,b). 2. obie strony tworz cig skBadajcy si z cookie, host key i czy schemat elGamala bdzie skuteczny gdy zastpimy Weryfikacja: yaab = gaxgkb = gax+k t(h(M)-xa) = gh(M) mod p. server key i za pomoc funkcji hashujcej tworz session-id, losowe warto[ci kolejnymi liczbami naturalnymi, tj. k, k+1, k+2, Podpisy pod tym samym dokumentem mog by r�|ne. 3. klient tworzy losowy klucz sesyjny, wykonuje XOR klucza i itd. nie bdzie . Z kolejnych iteracji k bdzie mo|na wycign DSA (Digital Signature Algorithm): standard przyjty w USA, session-id i przesyBa do serwera zaszyfrowane oboma kluczami wnioski, kt�re mog prowadzi, do zBamania klucza. serwera, oparty na ElGamalu, zmieniony tak, aby podpisy byBy kr�tkie, podpisujemy warto[ funkcji SHA, dBugo[ podpisu to 320 bit�w, 4. serwer odszyfrowuje klucz sesyjny i u|ywa go do dalszej Policzmy b1 i b2 generowane kolejno z k i k+1. tylko do podpis�w, nie ma jego modyfikacji do szyfrowania. komunikacji, B1 = m1*yk 5. klient uwierzytelnia si teraz identyfikatorem i hasBem lub za B2 = m2*yk +1 pomoc wBasnej pary kluczy, Administracja kluczami i dzielenie sekret�w Protok�B SSL: protok�B zawierajcy bezpieczny kanaB Zauwa|my, |e kiedy zrobimy b1/b2 , to bdziemy mogli policzy z Uzgadnianie kluczy sesyjnych: tak aby niemo|liwy byBa atak komunikacji oparty na szyfrowaniu asymetrycznym i certyfikatach tego: b1/b2 = m1/(m2*y). Rozszyfrowali[my klucz. np. man-in-the-middle: wi|cych klucz publiczny z usBugodawc. - A i B maj wsp�lny klucz symetryczny k, Budowanie poBczenia w SSL: - A wybiera losowe rA i wysyBa do B EK(rA,t,n), gdzie t aktualny - Client Hello pro[ba do serwera zawierajca dane na temat czas, a numer uzgadnianego klucza, u|ywanych protokoB�w i algorytm�w szyfrowania oraz warto[ - B odbiera EK(rA,t,n), losuje rB i wysyBa do A EK(rB,t ,n), t losow CH.random. aktualny czas, - Server Hello odpowiedz serwera zawierajca podobne dane i - kluczem sesyjnym jest f(rA,rB,k,n). losow warto[ SH.random, mo|liwe jest tak|e przesBanie Podobnie dla szyfrowania asymetrycznego. Certyfikatu serwera. Certyfikat: podpisany elektronicznie przez zaufan stron trzeci - Certificate Request czasami serwer mo|e za|da (CA Certificate Authority) klucz publiczny z danymi wBa[ciciela i certyfikatu klienta. czasem wa|no[ci klucza, weryfikacja przez serwery zawierajce - Server/Client Key Exchange klient i serwer uzgadniaj klucz publiczny zaufanej strony. klucz sesyjny wykorzystujc klucze publiczne lub inny protok�B Protok�B Diffie-Helmana: jak uzgodni wsp�lny klucz przy uzgadniania kluczy, oraz losowe warto[ci otrzymane od siebie. braku szyfrowanego kanaBu: - Certyficate Verify sprawdzanie poprawno[ci certyfikat�w. - publicznie znane s p du|a liczba pierwsza i g generator Inne metody zabezpieczania komunikacji PGP ciaBa Zp, - A wybiera rA<�p-1 i wysyBa do B sA=gra mod p, Kodowanie uniwersalne, bzip2 - B wybiera rB<�p-1 i wysyBa do A sB=grb mod p, Kodowanie liczby naturalnej powinno by asymptotycznie - kluczem jest grarb = sArb = sBra mod p. ZBamanie klucza wymaga umiejtno[ci liczenia logarytmu proporcjonalne do kodowanej warto[ci �(log2n). dyskretnego. Zastosowanie: czasami konieczne jest przesBanie kilku liczb, Protok�B interlock: kt�rych wielko[ ci|ko oszacowa (wykorzystanie np. przez 1. B przesyBa A sw�j klucz publiczny, niekt�re odmiany LZ77 do kodowania przesuni). 2. A przesyBa B sw�j klucz publiczny, Kodowanie Eliasa (lata 70) wyr�|niamy 3 rodzaje kod�w 3. B szyfruje swoj pierwsz wiadomo[ i przesyBa do A jej Eliasa (co najmniej 3) r�|nice si konstrukcj �, �, �, og�lna idea jest nastpujca: pierwsz poBow, 4. A po otrzymaniu pierwszej poBowy wiadomo[ci od B szyfruje - kodujemy zadan liczb binarnie, swoj wiadomo[ i wysyBa do B jej pierwsz poBow, - doklejamy informacj o dBugo[ci tak, by powstaB kod 5. B po otrzymaniu pierwszej poBowy wiadomo[ci od A przesyBa do jednoznacznie dekodowalny. A drug poBow, Kodowanie �: kodowanie liczba x jest zapisana w kodzie 6. A po otrzymaniu drugiej poBowy wiadomo[ci od B odszyfrowuje binarnym, niech n oznacza liczb cyfr w zapisie binarnym, sBowo s i sprawdza jej poprawno[, je[li wszystko w porzdku to skBada si z (n-1) bit�w o warto[ci 0, liczby x zapisanej binarnie. przesyBa drug poBow swojej wiadomo[ci do B, Kodowanie �: liczba x jest zapisywana binarnie, liczba n oznacza 7. B, po otrzymaniu drugiej poBowy wiadomo[ci od A, liczb bit�w binarnej reprezentacji x, liczb n przedstawiamy w odszyfrowuje j i sprawdza jej poprawno[. kodzie �, z binarnej reprezentacji liczby x usuwamy najbardziej znaczc cyfr, niech k oznacza liczb bit�w znaczcych n, Osoba podszywajca si nie mo|e odszyfrowa wiadomo[ci przed przesBaniem jej drugiej poBowy. wynikiem jest: k-1 zer, binarna reprezentacja liczby n, binarna Dzielenie tajemnic przy pomocy XOR: reprezentacja liczby x bez pierwszej jedynki. 1. wybieramy losowo dla Ri dla i=1, & , n-1, |e |M|=|Ri|, Kodowanie �: 2. obliczamy Rn=M XOR R1 XOR & XOR Rn-1 , 1. zapisz bit 0 (znacznik koDca), 3. dla i=1, & , n osoba otrzymuje Ri. 2. k<�-x, Dzielenie tajemnic z progiem k: 3. while k>1: 1. wybieramy odpowiednio du| liczb pierwsz p, p>M, p>m, - zapisz dw�jkowo liczb k, 2. wybieramy losowo w1, & , wk-1 liczb mniejszych od p, - nowe k, to liczba bit�w z poprzedniego kroku pomniejszona o 1. 3. konstruujemy wielomian , Liczba bit�w wynosi: ( , n liczba krok�w). 4. dla i=1, & , n osoba Ai otrzymuje w(i). Dekodowanie �: k os�b jest w stanie odtworzy w(x) (interpolacja) i obliczy 1. n<�-1, w(0)=M. 2. while kolejny bit nie ma warto[ci 0 - n <�- warto[ zapisana na kolejnych n+1 bitach, 3. x<�-n. Uwierzytelnianie WBa[ciwo[ci liczb Fibonacciego: ka|da liczba caBkowita HasBa jednorazowe schemat Lamporta: dodatnia k mo|e by przedstawiona jednoznacznie jako: Przygotowanie: , gdzie ai jest r�wne 0 lub 1. Zawsze mo|emy zapisa ten - A bierze funkcj hashujc h, ilo[ haseB t i sekret w, cig w taki spos�b, |e nie wystpi obok siebie dwie jedynki! - do B dostarczamy w0=ht(w). Kody Fibonacciego: Uwierzytelnianie: przy k-atym uwierzytelnieniu A przesyBa do B - znajdujemy wsp�Bczynniki ai, (A,k,wk,ht-k(w)). - zapisujemy w kolejno[ci od najmniej znaczcego, Weryfikacja: B sprawdza czy h(wk)=wk-1 byBo , gdzie wk-1 - za koDcu dopisujemy jedynk. dostarczone w poprzednim uwierzytelnianiu. Za koDcu zawsze wystpi 2 jedynki! Protok�B challange and response silne uwierzytelnianie, bzip2: algorytm kompresji popularny w systemach Linuksowych, niemo|liwy atak man-in-the-middle, praktycznie niemo|liwy atak standardowa implementacja kompresuje bloki danych o powt�rzeniowy, ale administratorzy po stronie B mog mie rozmiarach od 100 do 900 kb, blok jest przeksztaBcany dostp do k i umo|liwi podszycie si za Z: A i B znaj wsp�lny transformat Burrowsa-Wheelera, nastpnie kodowany sekret k i funkcj f majc wBasno[ci funkcji hashujcej. algorytmem Move-To-Front i kompresowany algorytmem Uwierzytelnianie: Huffmana, osiga o 10-20% lepsze rezultaty ni| algorytmy 1. A przesyBa do B sw�j identyfikator, strumieniowe, ale nie mo|e by u|ywany do kodowania strumieni. 2. B losuje losowy cig r i przesyBa do A, Transformata Burrowsa-Wheelera: 3. A przesyBa do B f(k,r), - przygotowujemy list wszystkich przesuni cyklicznych 4. B tak|e oblicza f(k,r) i sprawdza, czy jest r�wny przesBanemu (rotacje) BaDcucha wej[ciowego, przez A. - sortujemy je leksykograficznie, Dowody z wiedz zerow: A przekonuje B, |e zna pewien - zwracamy: numer wiersza z pierwotnym tekstem i ostatni sekret tak, aby go nie zdradzi. kolumn tabeli. TA Trusted Authority: zaufana osoba/instytucja potrzebna w Odwracanie transformacji: trakcie tworzenia kluczy. - mamy numer wiersza k i tekst, Protok�B Fiata-Shamira: - dopisujemy do tekstu indeksy, Przygotowanie: - sortujemy tekst (stabilnie), 1. TA losowo wybiera dwie liczby pierwsze p i q (n=pq), - zaczynajc od pozycji k wypisujemy kolejno znaki zgodnie z 2. A otrzymuje od TA sekret s wzgldnie pierwszy z n, indeksami: posortowany [k]->litera i indexPierwotny0, 3. TA oblicza v=s2 mod n i publikuje par (v,n) jako identyfikator posortowany [indeksPierwotny0]->litera i indexPierwotny1, & A. Move-To-Front: transformacja mogca spowodowa Uwierzytelnianie: zmniejszenie entropii, zyski, gdy symbole wykazuj tendencj do 1. A wybiera losowe r wzgldnie pierwsze z n, oblicza x=r2 mod n lokalnego grupowania si, dane o takiej charakterystyce s czsto i przesyBa x do B, wynikiem transformaty Burrowsa-Wheelera. 2. B wybiera losowo b " {0,1} i przesyBa je do A, Transformacja: 3. A oblicza y=rsb mod n i przesyBa y do B, - na pocztku mamy tablic N posortowanych symboli, kodem 4. sprawcza czy y2=xvb mod n. symbolu jest numer pozycji w tablicy (numery od 0 do N-1), Osoba trzecia mo|e si podszy prawd. �: ma nadziej, |e b=0 i - w ka|dym kroku bierzemy pojedynczy symbol, wypisujemy jego s nie bdzie potrzebne, wysyBa x=y2/v mod n dla wcze[niej numer z tablicy i modyfikujemy tablic przesuwajc rozpatrywany wybranego y i ma nadziej, |e b=1. Dlatego protok�B powtarzamy symbol na pocztek tablicy, ok. 10 razy. - je[li symbole s lokalnie pogrupowane to s przesuwane na pocztek tablicy i w kodzie wynikowym pojawiaj si cz[ciej Zabezpieczenie komunikacji komputerowej maBe liczby, Kerberos: caBa komunikacja szyfrowana, dostp do ka|dego - odwr�cenie transformacji jest praktycznie identyczne jak elementu systemu tylko za pomoc biletu, krytyczne cz[ci algorytm transformacji. systemu na specjalnie chronionych serwerach, zabezpieczenie przed atakami przez podsBuchanie i przechwytywanie komunikacji. Serwer Kerberosa weryfikuje uprawnienia i przyznaje bilet ile bit�w informacji mo|e mie n-bitowy kod korygujcy t- potwierdzajcy autentyczno[ klienta, kt�ry jest okazywany Serwerowi Przyznajcemu Bilety. bBedy szukamy k! Serwer Przyznajcy Bilety (TGS) przyznaje bilety niezbdne do komunikacji z innymi klientami i urzdzeniami.

Wyszukiwarka

Podobne podstrony:
zagadneinia na kolosa
na kolosa
Pytania na kolosa
ORZECZENIA NA KOLOSA
matbudy na kolosa pyt2
gr 7 pytania z seminarium na kolosa 1
pomoce na laborki z MN ReadMe
Historia doktryn polityczno na kolosa
opracowanie na kolosa 1
mikro ( PYTANIA NA KOLOSA)
przykładowe zad na 1 kolosa

więcej podobnych podstron