Dr inż. Robert Wójcik


Tryby pracy algorytmu DES



Pobieranie 2,08 Mb.
Strona11/13
Data14.02.2018
Rozmiar2,08 Mb.
1   ...   5   6   7   8   9   10   11   12   13

Tryby pracy algorytmu DES
Algorytm DES standardowo jest przeznaczony do szyfrowania krótkich bloków tekstu złożonych z 8 znaków ASCII (ciąg 64-bitowy). Aby był on użyteczny w praktyce trzeba rozszerzyć jego działanie na teksty o dowolnej długości.
Tryb elektronicznej książki kodowej (ECB - Electronic Codebook)
W trybie ECB tekst jawny M jest dzielony na bloki o równej długości q, a następnie każdy z tych bloków M1, M2, …, Mn jest oddzielnie szyfrowany za pomocą tego samego klucza K, tj.
EK(M) = EK(M1) EK(M2) … EK(Mn).
W szyfrach blokowych następuje propagacja błędów transmisyjnych o zakresie jednego bloku, ale błędy te nie mają wpływu na inne bloki. W szczególności, uszkodzenie lub utrata pojedynczych bloków nie ma wpływu na możliwość deszyfrowania pozostałych części kryptogramu.
Tryb ECB jest najłatwiejszy do implementacji. Brak związków między blokami ułatwia szyfrowanie w bazach danych i transmisji pracującej w trybie datagramowym. W trybie datagramowym pakiety wiadomości są przekazywane niezależnie, a stacja odbiorcza układa je w odpowiedniej kolejności.
Słabą stroną ECB jest możliwość zgromadzenia przez kryptoanalityka takiej ilości materiałów, która umożliwia złamanie szyfru, gdy nie znamy klucza. W tym celu kryptoanalitycy wykorzystują powtarzające się fragmenty dokumentów, np. w poczcie elektronicznej.
Szyfry blokowe można uodpornić na kryptoanalizę, stosując technikę wiązania bloków.

Tryb wiązania bloków zaszyfrowanych (CBC)
W trybie wiązanie bloków wykorzystano technikę sprzężenia zwrotnego, w której blok poprzedni służy do modyfikacji szyfrowania bloku następnego.
W ten sposób każdy blok szyfrogramu zależy nie tylko od bieżącego bloku tekstu jawnego, ale również od wszystkich poprzednich bloków. Istnieją różne tryby wiązania bloków, lecz najczęściej korzysta się z wiązania bloków zaszyfrowanych (Cipher Block Chaining − CBC) i jego modyfikacji.

Schemat szyfrowania z wiązaniem bloków zaszyfrowanych pokazano na rysunku.
Grube linie oznaczają połączenia dla bloków wiadomości. W układzie sprzężenia zwrotnego znajdują się rejestry przesuwne umożliwiające zapamiętanie bloku kryptogramu.
Kolejny blok wiadomości Mi jest sumowany modulo dwa z poprzednim blokiem kryptogramu Ci, a następnie szyfrowany za pomocą klucza K w szyfratorze. Szyfrowanie wyraża zależność:
Ci = EK( Mi + Ci-1).
Deszyfrowanie wykonuje się obliczając:
DK( Ci ) + Ci-1 = DK( EK( Mi + Ci-1) ) + Ci-1 = (Mi + Ci-1) + Ci-1 = Mi.
W celu rozpoczęcia pracy systemu stosuje się wektor początkowy, który jest zwykle ciągiem losowym.
Ponieważ każdy zaszyfrowany blok ma powiązanie z blokiem poprzednim, dlatego jeden błąd transmisyjny wpływa najwyżej na dwa bloki wyjściowe.
System ten jest wrażliwy na błędy synchronizacji, gdyż przesunięcie szyfrogramu nawet o jeden bit powoduje błędną pracę systemu.
Jednocześnie każdy zaszyfrowany blok zależy od wszystkich poprzednich bloków zaszyfrowanych, więc cechy statystyczne tekstu jawnego rozprzestrzeniają się na cały zaszyfrowany tekst, co znacznie utrudnia kryptoanalizę.
Tryb wiązania bloków zaszyfrowanych opracowano w IBM i zastosowano w Systemie Ochrony Informacji (Information Protection System − IPS). System ten pracuje z algorytmem DES.
Tryb wiązania bloków zaszyfrowanych jest najlepszy do szyfrowania

plików. Do szyfrowania baz danych wygodniejszy jest tryb bezpośredniego szyfrowania bloków.


Algorytmy asymetryczne – z kluczem publicznym
Algorytmy z kluczem jawnym lub publicznym są nazywane algorytmami asymetrycznymi w odróżnieniu od algorytmów symetrycznych z kluczem tajnym.
Pierwsze algorytmy z kluczem jawnym opublikowano w tym samym czasie, kiedy dyskutowano o algorytmie DES (1977) jako o proponowanym standardzie. Od 1976 r. zaproponowano wiele algorytmów z kluczem jawnym. Tylko kilka z nich jest bezpiecznych i praktycznych.
Większość algorytmów z kluczem jawnym bazuje na jednym z trzech problemów trudnych obliczeniowo, którymi są:

• problem plecakowy,

• problem logarytmu dyskretnego,

• problem faktoryzacji (rozkładu liczby na czynniki pierwsze).

Siła dowolnego algorytmu z kluczem jawnym zależy od złożoności obliczeniowej problemu, na którym on bazuje.
Pierwszy algorytm kryptograficzny z kluczem jawnym lub publicznym opracowali Merkle i Hellman w 1978 r. Zaproponowali oni szyfr, którego bezpieczeństwo opiera się na problemie plecaka, będącego problemem NP-zupełnym.
Pojęcie NP pochodzi z teorii złożoności obliczeniowej. Teoria ta umożliwia analizowanie złożoności obliczeniowej algorytmów kryptograficznych. Zwykle algorytmy klasyfikuje się w zależności

od ich złożoności czasowej lub przestrzennej wyrażonej jako funkcja argumentu n.


Algorytm jest liniowy, jeśli jego złożoność rośnie liniowo ze wzrostem n. Podobnie algorytmy mogą być kwadratowe, sześcienne, wykładnicze itd. Algorytmy z kluczem jawnym zwykle mają złożoność wykładniczą.
Trudność obliczenia logarytmu dyskretnego wykorzystano, między innymi, w algorytmie ElGamala, a problem faktoryzacji w algorytmie RSA.
Z bezpiecznych i praktycznych algorytmów z kluczem jawnym niektóre nadają się do szyfrowania danych, inne zaś do podpisów cyfrowych.
Tylko dwa algorytmy, tj. RSA i ElGamala, są odpowiednie zarówno do szyfrowania danych, jak i podpisów cyfrowych.
Do podpisów cyfrowych preferowany jest algorytm DSA (Digital Signature Algorithm).
Wszystkie algorytmy z kluczem jawnym są w realizacji algorytmami wolnymi w porównaniu z algorytmami symetrycznymi.

Algorytm Merklego–Hellmana
W algorytmie z kluczem jawnym Merklego–Hellmana wykorzystano problem plecaka. Problem plecakowy, zwany też problemem upakowania, jest następujący. Mamy nieuporządkowany zbiór przedmiotów, każdy o innej wadze. Z tego zbioru należy wybrać podzbiór o zadanej z góry łącznej wadze.
Na podstawie tego problemu opracowano schemat szyfrowania wiadomości z użyciem klucza jawnego oraz deszyfrowania wiadomości z użyciem klucza tajnego.
Szyfr Merklego–Hellmana został złamany cztery lata po jego opublikowaniu. Okazało się, że na podstawie klucza jawnego można znaleźć klucz zbliżony do tajnego i umożliwiający zdeszyfrowanie zaszyfrowanych wiadomości.
Oprócz szyfru Merklego-Hellmana opracowano inne szyfry plecakowe, które zostały również złamane.
Obecnie bezpieczną odmianą szyfru plecakowego jest algorytm Chora–Rivesta. Jednak realizacja tego algorytmu wymaga tylu obliczeń, że jest on mało przydatny w praktyce.

Algorytm ElGamala
Algorytm ElGamala może być używany zarówno do szyfrowania danych, jak i podpisów cyfrowych.
Moc algorytmu wynika z trudności obliczania logarytmów dyskretnych. Problem ten można sformułować w następujący sposób.
Jeśli p jest liczbą pierwszą, a liczby g i m są liczbami całkowitymi, to należy znaleźć takie x, że:
gx = m mod p.
Schemat blokowy algorytmu ElGamala, zastosowanego do podpisywania dokumentów, pokazano na rysunku.
Algorytm ElGamala do podpisów cyfrowych

Aby wygenerować parę kluczy, jawny i tajny, losujemy liczbę pierwszą p oraz dwie liczby g i x mniejsze od p (g < p i x < p).
Następnie obliczamy: y = gx mod p.
Klucz publiczny stanowią liczby: p, g i y.
Klucz tajny stanowi tajna liczba x, oraz jawne liczby p i g.
Liczby p i g mogą być wykorzystywane przez grupę użytkowników.
W celu podpisania wiadomości m ∈ {0, p−1} nadawca losuje liczbę k względnie pierwszą z liczbą p−1, tj. NWD(k, p-1) = 1 i oblicza:
a = gk mod p.

Następnie oblicza on liczbę b z następującego równania:


m = (x a + k b) mod ( p − 1).
Do rozwiązana równania stosuje się rozszerzony algorytm Euklidesa.
Podpis stanowi para liczb a i b.
Liczba k musi być utrzymywana w tajemnicy, gdyż stanowi ona razem z liczbą x prywatny klucz podpisującego dokument.
Odbiorca dokumentu weryfikuje podpis, sprawdzając równość:
ya ab mod p = gm mod p.
P r z y k ł a d.
Algorytm ElGamala do podpisów cyfrowych.
Zakładamy p = 11, g = 2 oraz x = 8. Obliczamy liczbę y z równania:
y = gx mod p = 28 mod 11 = 3.
Kluczem jawnym są liczby: p = 11, g = 2 i y = 3.
Klucz tajny stanowi liczba x = 8.
Aby podpisać wiadomość m = 5, wybieramy liczbę k = 9 i

sprawdzamy, że NWD(k, p −1) = NWD(9,10) = 1.


Obliczamy liczbę a z równania: a = gk mod p = 29 mod 11 = 6,

a następnie liczbę b z równania:


m = (a x + b k) mod (p −1);
5 = (6 ⋅ 8 + 9b ) mod 10, b = 3.

Liczbę b można znaleźć numerycznie, rozwiązując równanie:


8 ⋅ 6 + 9 b − 10 x = 5 w dziedzinie liczb całkowitych.
Podpis wiadomości m = 5 stanowią liczby a = 6 oraz b = 3.
Aby sprawdzić podpis, potwierdzamy, że jest spełnione równanie:
ya ab mod p = gm mod p,
36 63 mod 11 = 25 mod 11 = 10.
729 * 216 mod 11 = 10.

Algorytm ElGamala do szyfrowania wiadomości
Algorytm ElGamala można stosować również do szyfrowania wiadomości m wyrażonych w postaci liczb należących do zbioru

{0, p − 1}.


Algorytm szyfrowania jest podobny do algorytmu podpisywania. Różnica polega na tym, że zamiast podpisywania i weryfikacji podpisu stosuje się operacje szyfrowania i deszyfrowania, a generator klucza jest umieszczony po stronie szyfrującej.
Kryptogram złożony z liczb a i b obliczamy z zależności:
a = gk mod p ,
b = m yk mod p.
Do wyznaczenia postaci jawnej wiadomości m z kryptogramu stosuje się wyrażenie:
m = b a-x mod p.
Odwrotność liczby a-x modulo p obliczamy z rozszerzonego algorytmu Euklidesa.
Poprawność algorytmu wynika z przekształcenia:
b a-x = ( myk ) a-x = (m gxk ) g-kx = m mod p.



1   ...   5   6   7   8   9   10   11   12   13


©operacji.org 2019
wyślij wiadomość

    Strona główna