Podstawowe pojęcia, wykrywanie błędów
Współczynnik informacji = log|k|*(1/n)
Odległość Hamminga - d(a,b)=
.
Minimalna odległość Hamminga = d => kod wykrywa d-1
błędów i koryguje
.
Minimalna waga d (dla pewnego a
0
: d = d(a
0
,0)) = minimalna
odległość d(a,b).
Kod Hamminga: n=2
m
-1, k=2
m
-m-1, d=3.
Kod cykliczny (n,k) (n = stopień g(x) musi być dzielnikiem x
n
-1,
Wielomian parzystości h(x) =
.
Kompresja bezstratna
Miara informacji - i(A)= .
Entropia (średnia informacja) H=
.
Kod jednoznacznie dekodowalny, spełnia: L >= H, L – średnia
długość kodu (podstawowe twierdzenie Shannona).
Test na jednoznaczną dekodowalność:
1. lista słów kodowych,
2. sprawdzać pary aż znajdzie się prefiks, wtedy sufiks dodać do
listy,
3. gdy słowo (sufiks) już jest na liście – kod niejednoznaczny,
4. osiągnięcie końca listy - kod jednoznaczny.
Nierówność Krafta-McMillana
.
Kody Shannon-Fano: długość kodu l
i
=
, średnia długość
≤ H+1.
Konstrukcja kodu Shannon-Hano:
- niech l
1
≤ l
2
≤ … ≤ l
N
,
- definiujemy pomocnicze w
1
, w
2
, …, w
N
jako w
1
=0,
,
- binarna reprezentacja w
j
dla j > 1 zajmuje
bitów,
- liczba bitów w
j
jest mniejsza lub równa l
j
, dla w
1
to oczywiste,
-
Kodowanie:
Kody Huffmana: wszystkie mają taką samą średnią długość dla
danego ciągu, kodowanie w czasie liniowym, optymalne kody
prefiksowe, możliwość implementacji dynamicznej.
Kody Tunstalla: znak z największym prawdopodobieństwem np.
‘a’ zastepujemy aa,ab,ac
Średnia długość =
, e
i
– słowo kodowe
odpowiadające i-temu kodowi.
Kodowanie arytmetyczne: elementom przyporządkujemy
przedział [F(i),F(i+1)), F(i) =
.
Kodowanie:
- d <- p-l, p <- l+F(j+1)d, l <- l+F(j)d,
znacznik – liczba z przedziału [l,p) np.
.
Skalowanie:
1. jeśli [l,p) ⊆ [0;0,5):
- [l,p) -> [2l,2p),
- dołącz do kodu 01
licznik
,
- wyzeruj licznik,
2. jeśli [l,p) ⊆ [05;1):
- [l,p) -> [2l-1,2p-1),
- dołącz do kodu 10
licznik
,
- wyzeruj licznik,
3. jeśli l<0.5<p oraz [l,p) ⊆ [0,25;0,75):
- [l,p) <- [2l-0,5;2p-0,5),
- licznik <- licznik+1.
Możliwe usprawnienia: przejście na arytmetykę liczb
całkowitych: [0,1) -> [0,2
m
-1).
Kodowanie słownikowe: słowniki statyczne – tekst kodujemy
jako całe słowa ze słownika, słowa których nie ma można
umieszczać jako 1-literowe słowa, wrażliwe na zmianę char.
danych.
kodowanie LZ77:
Wysylamy(w lewo, copy, nowy znak)
kodowanie LZ78:
(nr slowa, nowy znak)
LZW: słownik zawiera na starcie wszystkie poj. Liter
(nr slowa) parujemy nowe slowa
PPM (Prediction by Partial Matching):
1. dla bieżącej pozycji znajdź aktualny kontekst maks rzędu,
2. jeśli znak występował już w tym kontekście to zakoduj go z
prawdopodobieństwem wyznaczonym na podstawie statystyk tego
kontekstu,
3. w.p.p. zakoduj <esc> z prawdopodobieństwem wyznaczonym
na podstawie statystyk oraz:
- zakoduj kodowany symbol w kontekście o 1 krótszym (rząd
kontekstu > -1),
- zakończ kodowanie symbolu (rząd = -1),
4. zaktualizuj statystyki wystąpień symboli.
rząd -1 wprowadzony, aby każdy symbol dało się zakodować
(rozkład równy dla każdej litery).
dla kontekstów można utworzyć dynamicznie kod Huffmana lub
kod arytmetyczny.
Zazwyczaj maksymalna dł. kontekstu to 5.
CALIC (Context Adaptive Lossless Image Compression):
d
h
=|W-WW|+|N-NW|+|NE-N|
d
v
=|W-NW|+|N-NN|+|NE-NNE|
Pseudokod:
1. jeżeli d
h
-d
v
> 80, to X’ <- N,
2. w.p.p., jeżeli d
v
-d
h
> 80, to X’ <- W,
3. w.p.p.:
- X’ <-
- jeżeli d
h
-d
v
> 32, to X’ <-
,
- w.p.p., jeżeli d
v
-d
h
> 32, to X’ <-
,
- w.p.p., jeżeli d
h
-d
v
> 8, to X’ <-
,
- w.p.p., jeżeli d
v
-d
h
> 8, to X’ <-
.
Kodujemy ciąg różnic X-X’.
JPEG-LS: 7 schematów predykcji: X’=W, X’=N, X’=NW, X’=N+W-
NW, X’=
, X’=
, X’=
.
Nowy standard:
1. jeżeli NW≥max(W,N), to X’<-max(N,W),
2. w.p.p. jeżeli NW≤max(W,N), to X’<-min(N,W),
3. w.p.p. X’<-W+N-NW.
Poziomy rozdzielczości:
1. kodujemy najpierw średni kolor kw. 2
k
x2
k
, a nast. różnicę
między tą średnią a kw. 2
k-1
x2
k-1
,
2. kończymy na pikselach (2
0
x2
0
),
3. różnice nie są duże i łatwo się kompresują.
Obrazy czarno-białe (faksy): linie obrazów zaw. na przemian
bloki białe i czarne, można więc przesyłać tylko ich długości
Kompresja stratna
Kryteria oceny zniekształceń:
- czynnik ludzki,
- kwadratowa miara błędu: d(x,y)=
,
- bezwzględna miara błędu: d(x,y)=
.
- błąd średniokwadratowy (mean squared error - mse):
,
- SNR =
, SNR (dB) = 10 log
10
SNR.
Miary kwantyzacji:
- średniokwadratowy błąd kwantyzacji: kwantyzacja Q(x)=y
b
i-1
<x≤b
i
,
wówczas
,
- średnia bitowa kwantyzatora: średnia liczba bitów do
zapisania
jednej
wynikowej
kwantyzatora.
Poziom reprezentacji: inaczej wartość, jaką przypisujemy
wszystkim kwantyzowanym liczbom w danym przedziale.
Poziom decyzyjny: kraniec przedziału kwantyzatora, poziomów
tych jest o 1 mniej niż poziomów decyzyjnych.
Kwantyzacja adaptacyjna w przód: zakładamy, że wartość
średnia wejścia jest równa 0, na podst. bloku N kolejnych próbek
(w chwili t) szacujemy wariancję źródła:
,
przesyłamy (skwantowaną) informację o wariancji do dekodera.
Kwantyzacja adaptacyjna wstecz (kwantyzator Jayanta):
do zmiany wykorzystujemy wcześniejsze dane (w postaci
skwantyzowanej), każdy przedział ma przypisany mnożnik M
k
,
mnożniki przedziałów wew. < 1, a zewnętrznych > 1, jeżeli w
kroku n-1 próbka wpadła do przedziału l(n-a) to parametr Δ dla
następnego kroku:
, jeśli wejście jest dobrze
dopasowane to iloczyn kolejnych wsp. = 0.
Kwantyzacja
z
kompanderem:
przed
kwantyzacją
przekształcamy dane za pomocą jakiejś funkcji(kompander), po
rekonstrukcji przekształcamy za pomocą funkcji odwrotnej.
Kwantyzacja wektorowa: zamiast pojedynczych elementów
kwantyzujemy całe bloki,
Średniokwadratowy błąd kwantyzacji: Q(X) = Yi ∀Y
i
∈ C
||X − Y
j
|| ≤ ||X − Y
i
||, C – słownik kwantyzatora,
(zniekształcenie liczymy po próbkach),
Poziom kompresji: słownik zawiera K elementów, wektor
wejścia ma wymiar L:
- zakodowanie numeru wektora - bitów,
- wektor zaw. rekonstruowane wartości z L próbek,
- liczba bitów na próbkę:
.
Algorytm Linndego-Buza-Graya:
1. wybierz dowolny zbiór rekonstruowalnych wartości
,
ustal k=0, D
(-1)
=0, wybierz próg ε,
2. znajdź
obszary
kwantyzacji
∀
,
3. oblicz
zniekształcenie
,
4. jeśli
zakończ obliczenia,
5. przyjmij k<-k+1, za nowe
przyjmij środki ciężkości
, wróć do korku 2.
Inicjalizacja LBG – metoda podziałów:
- rozpoczynamy z jednym punktem (rozmiar słownika 1),
będącym średnią z całego zbioru uczącego,
- dodajemy pewien ustalony wektor perturbacji e do każdego
punktu słownika i wykonujemy LBG,
- kontynuujemy aż do uzyskania zakładanej liczby poziomów
(jeżeli nie jest potęgą 2, to w ostatnim kroku nie wszystkie
podwajamy).
Kwantyzatory o strukturze drzewiastej:
- dzielimy przestrzeń na dwie części i uzyskujemy dla nich
wektory reprezentacji,
- powtarzamy aż uzyskamy pewne drzewo binarne o wysokości k,
- jeśli zmniejszy to zniekształcenie przycinamy niektóre
poddrzewa,
- optymalne zwykle tylko dla kw. symetrycznych.
Kratowa kwantyzacja wektorowa:
Krata – {a
1
, a
2
, …, a
L
} – L niezależnych wektorów o L wymiarach,
jest kratą jeśli wszystkie u
i
są liczbami
całkowitymi.
Inne kwantyzacje wektorowe: piramidalne, sferyczne i
biegunowe, skala-kształt, z usuniętą średnią, klasyfikowane,
wieloetapowe, adaptacyjne.
Kodowanie różnicowe: obliczamy kwantyzacje nie elementów
ale ich kolejnych różnic:
1. mamy ciąg {x
n
}, ciąg różnic {d
n
} generujemy biorąc d
n
=x
n
-x
n-1
,
kwantyzujemy d’
n
=Q[d
n
]=d
n
+q
n
otrzymując {d’
n
} (q
n
- błąd
kwantyzacji),
2. u odbiorcy odtwarzamy {x’
n
}: x’
n
=x’
n
+d’
n
,
3. stąd:
,
błąd akumuluje się z czasem – zapobieganie:
używamy d
n
=x
n
-x’
n-1
, wtedy x’
n
=x
n
+q
n
.
Predykcja DPCM (Diffirential Pulse Code Modulation): zamiast
różnicy między kolejnymi elementami mamy funkcję predykcyjną
generującą {p
n
}, p
n
=f(x’
n-1
, …, x’
0
), kodujemy x
n
-p
n
, szukamy
takiego f aby
jak najmniejsze.
Zakładamy, że
(N -rząd predyktora).
Zamiast x’
n
używamy x
n
(zał. błędy kw. małe).
Szukamy {a
i
}, aby
jak najmniejsze. W
tym celu:
1. obliczamy wartości oczekiwane N równań postaci:
, otrzymując układ
, gdzie R
xx
(k)=E[x
n
x
n+k
] funkcja autokorelacji zmiennej x
n
.
2. jeśli znamy wartości autokorelacji możemy obliczyć wartości a
i
.
Odmiany DPCM:
- adaptacyjne DPCM (w przód i w tył),
- modulacja delta: dwustopniowy kwantyzator i odp. częstość
próbkowania (2 razy większa niż największa częstotliwość).
Zastosowanie: kodowanie mowy, obrazów.
Kodowanie transformujące: przekształca informację tak, aby
można było zrezygnować z części elementów:
1. podziel sygnał na bloki,
2. oblicz przekształcenie każdego bloku,
3. skwantuj współczynniki,
4. skompresuj skwantowane współ. bezstratnie.
Odkodowanie odwrotnie.
Przekształcenia liniowe:
1. ciąg
{x
0
,…,x
N-1
}
przekształcamy
na
{θ
0
,…,θ
N-1
}:
,
2. oryginalny ciąg odtwarzamy:
,
3. można poszerzyć przekształcenia jednowymiarowe (dźwięk) na
dwuwymiarowe (obrazy),
4. wszystkie przekształcenia są ortonormalne.
Dyskretne przekształcenia kosinusowe (DCT):
macierz przekształcenia NxN:
,
- łatwiejsza do policzenia i lepiej się sprawdza niż transformata
Fouriera (DFT),
- używana do obrazów i dźwięków.
Dyskretne przekształcenie sinusowe:
macierz przekształcenia NxN:
,
- lepsze niż kosinusowe gdy współczynnik korelacji
jest
mały,
- uzupełnia przekształcenie kosinusowe.
Dyskretne przekształcenie Walsha-Hadamarda:
macierz przekształcenia NxN:
, dla potęg dwójki:
, macierz przekształcenia uzyskujemy przez
normalizację i ustawienie kolumn w porządku ilości zmian znaków
(+ na – i odwrotnie).
- proste do uzyskania i implementacji,
- minimalizuje ilość obliczeń.
Kodowanie podpasmowe: rozłożenie informacji na części
(pasma) i kodowanie ich oddzielnie:
1. wybierz zbiór filtrów do rozkładu źródła {x
n
},
2. używając filtrów oblicz sygnały podpasm {y
k,n
},
3. zdziesiątkuj wyjście filtra,
4. zakoduj zdziesiątkowane wyjście.
Odkodowanie jest odwrotnością kodowania.
Filtry rzeczywiste mają nieostre granice przejścia (odcięcia).
Reguła
Nyquista:
jeśli
sygnały
mają
składowe
o
częstotliwościach pomiędzy f
1
a f
2
to, aby odtworzyć dokładnie
sygnał, musimy próbkować z częstością co najmniej 2(f
2
-f
1
)
próbek na sekundę.
Filtrowanie cyfrowe: suma ważona bieżącego i poprzednich
wejść filtra i ew. także wyjść filtra:
,
wartości {a
i
} i {b
j
} nazywamy współczynnikami filtra.
Reakcja impulsowa: niezerowy ciąg współczynników na wyjściu
filtra (zazwyczaj dla ciągu wejściowego: 1, 0, 0, …).
Filtry dzielimy na te o skończonej i nieskończonej reakcji.
Filtry często łączy się kaskady (str. drzewiaste), dobierane są do
sygnału, pasma mogą się nakładać lub nie, redukcja próbek na
wyjściu odpowiada redukcji rozmiaru częstotliwości.
Zastosowania:
- kodowanie mowy G.722: tryby 64, 56 i 48 kbps, filtr 7kHz
jako ochrona przed aliasingiem przy próbkowaniu 16000/s, każda
próbka kodowana przy pomocy 14 bitowego jednolitego
kwantyzatora i przepuszczana przez bank 24-rzędowych filtrów
FIR, ich wynik jest redukowany o współczynnik 2 i kodowany
ADPCM (6 bitów na próbkę z możliwością odrzucenia 1 lub 2
niższe pasmo i 2 bity wyższe),
- kodowanie dźwięku MPEG: schematy kodowania Layer 1, 2,
3, każdy kolejny bardziej skomplikowany i dający lepszą
kompresję, kodery zgodne w górę, Layer 1 i 2 używają banku 32
filtrów (32 podpasma o szerokości f
s
/64, f
s
– cz. próbkowania
równa 32k, 44,1k lub 48k), wyjście kwantyzowane przy użyciu
równomiernego kwantyzatora ze zmienną liczbą bitów (model
psychoakustyczny – własności ludzkiego ucha), w Layer 1 i 2
ramki zawierają 384 i 1152 próbki (ma to wady przy dużej
zmienności sygnału i zostało poprawione w 3),
- kodowanie obrazów: obraz dzielimy za pomocą filtrów
(najlepiej separowanych, aby można było je stosować oddzielnie
w każdym z wymiarów), górno i dolno przepustowych, a następnie
dziesiątkujemy wyjście o czynnik 2, w każdym kroku rozkładamy
tylko 1 z 4 podobrazów (podobrazi o wysokiej częstotliwości mają
większość współczynników bliską 0),
- kompresja wideo: często klatki niewiele się różnią, pewne
zniekształcenia są słabo widoczne (niewyraźnie krawędzie),
niektóre bardzo (zmiany jasności pow. migotanie), w predykcji
następnych klatek można wykorzystywać poprzednie, predykcja
musi uwzględniać ruch obiektów, aby uniknąć błędów, co jakiś
czas rezygnujemy z predykcji (co kilka klatek, albo gdy zmiany są
zbyt duże), kompresja klatek opiera się na algorytmach kompresji
obrazu,
- kompresja ruchu: obraz dzielimy na kratki, szukamy
podobnych, po czym przypisujemy im wektor przesunięcia.
W wideo klatki dzielimy na grupy obrazów (GOP):
- co najmniej 1 ramka typu I (obraz podobny do JPEGa,
wymagane do rozpoczęcia [de]kodowania),
- kilka klatek typu P (różnica pomiędzy poprzednią ramką typu P
lub I a bieżącą),
- opcjonalne ramki typu B (obraz zakodowany z wykorzystaniem
OBY sąsiednich klatek typu P lub I, najcięższe obliczeniowo, błędy
nie propagują się).
Przykład: I B B B P B B B P B B B P.
Algorytmy symetryczne: wideokonferencji – kompresja i
dekompresja muszą być szybkie.
Algorytmy asymetryczne: kompresja może być czaso- i
zasobożerna, ale dekompresja musi być szybka (MPEG-1, MPEG-
2, MPEG-4).
Kryptografia
Szyfry strumieniowe – na podstawie klucza tworzymy ciąg
bitów (potencjalnie nieskończony) za pomocą którego szyfrujemy
tekst jawny – np. przy pomocy XORa.
Efekt lawinowy – zmiana jednego bitu szyfrogramu powoduje
zmianę wielu bitów kryptogramu.
Szyfr Cezara: kluczem jest s, szyfrowanie c=(p+s) mod 26,
deszyfrowanie p=(c+26-s) mod 26.
Szyfr Viginiére’a – hasło (klucz) dodajemy modulo do blokow
tekstu (można też XORem) uogólnienie szyfru Cezara.
System Playfair: klucz to kwadrat 5x5 zawierający 25 różnych
liter (np. hasło i ciąg kolejnych liter alfabetu w nim
niewystępujących), w haśle znaki (występujące w kluczu) nie
mogą się powtarzać
Szyfrowanie:
1. tekst jawny dzielimy na pary: dla każdej wyznaczamy w
kwadracie-kluczu prostokąt,
2. dla prostokątów 1-wymiarowych bierzemy litery na prawo
(wspólny rząd)/poniżej (wspólna kolumna) nich,
3. w.p.p. wybieramy przeciwne rogi prostokąta.
One-time pad: jednorazowo wylosowany klucz XORujemy z
tekstem jawnym, wymaga osobnego przesyłu klucza.
ECB – Electronic Codebook: tekst jawny dzielony na bloki
długości n, każdy szyfrowany za pomocą tego samego klucza K.
uszkodzenie/utrata bloku nie wpływa na resztę, ale możliwa jest
też podmiana bloków.
CBC – Cipher Block Chaining: C
1
=E
k
(P
1
XOR IV), C
i
=E
k
(P
i
XOR
C
i-1
), P
1
=D
K
(C
1
) XOR IV, P
i
=D
K
(C
i
) XOR C
i-1
. Przekłamania 1 bloku
zmieniają tylko 2 bloki po deszyfracji, takie same bloki mają
zazwyczaj różne kryptogramy, ten sam tekst jawny dla tego
samego klucza może mieć różne kryptogramy dla różnych
wektorów inicjujących.
CFB – Cipher Feedback: C
0
=IV, C
i
=E
K
(C
i-1
) XOR P
i
, P
i
=C
i
XOR
E
K
(C
i-1
). Wady i zalety jak w CBC.
OFB – Output Feedback: S
0
=IV, S
i
=E
K
(S
i-1
), C
i
=S
i
XOR P
i
, P
i
=S
i
XOR C
i
. Można wysyłać nawet pojedyncze bity, proces
generowania ciągu szyfrującego zależy tylko od ciągu
początkowego i nie zależy od tekstu jawnego, niebezpiecznie jest
używać tego samego klucza i ciągu inicjującego.
Szyfrowanie symetryczne
Schemat Feistela:
Sieć Feistela pozwala na szyfrowanie i deszyfrowanie
informacji tym samym algorytmem, mimo iż funkcja f nie
jest odwracalna. Sieć Feistela generuje z tekstu jawnego
szyfrogram, a z szyfrogramu tekst jawny. W ten sposób
konstruowanie algorytmów szyfrujących znacznie się uprościło,
ponieważ nie trzeba się troszczyć o odwracalność funkcji f.
Tekst jawny dzieli się na dwa równe bloki L
i
, R
i
. Funkcja f jest
właściwym algorytmem szyfrującym. Jako wynik otrzymuje
się szyfrogram. Numer kolejnej rundy oznaczany jest indeksem i;
to oznacza iż wynik szyfrowania jest ponownie i-krotnie
szyfrowany, co polepsza jakość szyfrowania.
Wykorzystanie: DES, 3DES, Twofish, FEAL.
Szyfrowanie: L
i
=R
i-1
, R
i
=L
i-1
XOR f(R
i-1
,K
i
).
Deszyfrowanie: R
i-1
=L
i
, L
i-1
=R
i
XOR f(L
i
,K
i
).
DES – Data Encryption Standard: symetryczny, opis
opublikowany, zaprojektowane do działania jako hardware,
szyfruje bloki 64 bitów, 56 bitowy klucz, działa tylko brute force:
- szyfrowanie i deszyfrowanie składa się z 16 rund,
- każda zawiera te same obliczenia na wyniku poprzedniej rundy i
z innym podkluczem,
- podklucze generowane są z klucza głównego za pomocą
przesunięć cyklicznych,
- blok tekstu jawnego jest permutowany na początku i końcu
algorytmu (łatwe hardwarowo, trudne softwarowo),
- dzięki wykorzystaniu sieci Feistela, deszyfrowanie przebiega
niemal identycznie jak szyfrowanie (tak sama funkcja f),
deszyfrowania można więc użuć do zaszyfrowania wiadomości,
wówczas odszyfrowuje się ją funkcją szyfrującą (wykorzystane
jest to np. w algorytmie 3DES).
Niektóre rozwiązania wprowadzone w DESie:
- permutacja rozszerzająca: permutuje wszystkie i dubluje
niektóre bity,
- S-Boksy: dzielą blok na ciągi 6 bitowe i zastępują każde 6 bitów
4 wg. z góry określonego schematu,
- P-Boksy: perutacja bitów wg. określonego schematu
Żadne z tych operacji nie są wyliczane, ale zamiast tego są one
przypisane na stałe do określonych ciągów bitów/ich pozycji.
Rozszerzenia DESa:
- DESX – dodanie whiteningu, dwa dodatkowe klucze utrudniające
przeszukiwanie: C = K
EXT
XOR DES
K
(P XOR K
INT
).
- 3DES – używamy dwa 56 bitowe klucze K
1
i K
2
oraz trzykrotnie
algorytm DES: C = DES
K1
-1
(DES
K2
(DES
K1
-1
(P))).
IDEA: opatentowany, ale bezpłatny do celów niekomercyjnych,
klucze 128 bitowe, bloki są 64 bitowe, algorytm ma 8 rund.
AES – Advanced Encryption Standard (Rinjadael): następca
DESa, klucze w zależności od potrzeb 128, 192 lub 256, długość
bloku to 128 (można zwiększyć do 129 lub 256 bitów), 10 rund
(lub 12, lub 14), szybki w implementacji programowej.
RC4: szyfr strumieniowy, opracowany do celów komercyjnych,
implementacja ujawniona anonimowo na listach dyskusyjnych w
’94, na podstawie klucza generuje ciąg bitów XORowany z
tekstem jawnym.
Szyfrowanie asymetryczne
Klucze występują w parach: 1 do szyfrowania 1 do deszyfrowania
(czasem nierozróżnialne). Opublikowanie klucza szyfrującego
(publicznego) nie zdradza drugiego z kluczy (prywatnego)
(obliczenia zbyt kosztowne).
Twierdzenie Eulera: a
Ф(n)
mod n = 1, dla a względnie
pierwszego z n.
Faktoryzacja liczb jest NP-trudna.
RSA:
Generowanie kluczy:
- losowo wybieramy 2 duże liczby pierwsze p i q (512, 1024 lub
2048 bitów),
- losowo wybieramy e takie, że e i (p-1)(q-1) względnie pierwsze,
- znajdujemy d takie, że ed mod (p-1)(q-1) = 1,
- obliczamy n=pq i zapominamy liczby p i q,
- para [e,n] jest kluczem publicznym a [d,n] kluczem prywatnym,
- bez p i q nie można obliczyć d na podstawie e i n, a rozkład n na
p i q jest bardzo trudny obliczeniowo.
Szyfrowanie:
C=E
[e,n]
(m)=m
e
mod n (m < n).
Deszyfrowanie:
m=D
[d,n]
(C)=C
d
mod n.
Poprawność wynika z Twierdzenia Eulera i Chińskiego
Twierdzenia o Resztach. Szyfrowanie i deszyfrowanie są
symetryczne i można je stosować zamiennie.
Algorytm ElGamala: każdorazowe szyfrowanie wykorzystuje
losowo wybraną liczbę, różne szyfrogramy przy tym samym
kluczu, klucz publiczny tylko szyfruj, prywatny tylko deszyfruje,
algorytm bazuje na trudności obliczenia logarytmu dyskretnego
tzn. znalezienia takiego x, że g
x
mod p = y na liczbach
naturalnych.
Generowanie kluczy:
- wybieramy liczbę pierwszą p (512 bitów) i liczbę g będącą
generatorem grupy Z
p
,
- dla danego użytkownika wybieramy losowo liczbę x < p – 1 oraz
obliczamy y = g
x
mod p,
- kluczem publicznym jest [y,p,g] a kluczem prywatnym [x,p,g].
Szyfrowanie:
Szyfrujemy m < p, wybieramy losowo i tajnie k < p, obliczamy: a
= g
x
mod p, b = m y
k
mod p.
Para liczb [a,b] jest kryptogramem dla m.
Deszyfrowanie:
b(a
x
)
-1
=m y
k
g
-kx
= m mod p.
Funkcje hashujące i podpisy cyfrowe
MD5: skonstruowana przez Rivesta w 1991, 128 bitowe wartości,
łatwo implementowana na komputerach 32 bitowych, brak
matematycznych podstaw poprawności.
SHA-1 (Secure Hash Algorithm): opublikowana w USA w 1994,
powstała przy współpracy z NSA, daje 160 bitowe wartości, jest
częścią DSA (Digital Signature Algorithms), który jest
