To tylko jedna z 9 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Optymalizacja funkcji skrótu Jak wynika z poprzedniego wykładu, zadaniem funkcji skrótu, funkcji haszującej, jest utworzenie skróconego reprezentanta dokumentu podstawowego. Prawidłowo skonstruowana funkcja skrótu powinna uwzględniać wszystkie elementy dokumentu podstawowego oraz dawać rożne wartości przy dowolnej zmianie dokonanej w tym dokumencie. Najprostszym i jednocześnie rozwiązaniem maksymalnie skracającym jest bit parzystości ze wszystkich elementów dokumentu podstawowego. Rozwiązanie takie pozwala na wykrycie wszystkich zmian dokonanych na nieparzystych ilościach bitów i w umożliwia w łatwy sposób zamaskowanie dokonanej zmiany, czyli doprowadzenie do parzystej wartości funkcji skrótu. Rozwiązaniem optymalnym jest opracowanie takiego algorytmu tworzenia funkcji skrótu, który pozwoli na wykrycie zmian dokonanych w dokumencie podstawowym od jednego bitu do zmiany całej sekwencji treści. Tworzenie takiego algorytmu metodą „prób i błędów” jest bardzo uciążliwe i dla ułatwienia zadania zdecydowano na wykorzystanie mechanizmów wielomianów generujących i kodowania zgodnie z algorytmami opracowanymi dla kodowania nadmiarowego informacji. Wszystkie algorytmy kodowania nadmiarowego tworzą tzw. ciągi kodowe s(x) czyli elementy binarne o długości n = m+k (1)
gdzie: m - długość dokumentu podstawowego,
k - długość bloku wyznaczonych elementów nadmiarowych (skrótu).
Jak wspomniano wcześniej kodowanie takie ma doprowadzić do wyznaczenia nadmiarowego bloku czyli ma wykonać funkcję skrótu dokumentu podstawowego. Wykorzystując do tego celu mechanizmy wielomianów generujących uzyskuje się prosty mechanizm do sprawdzania wprowadzonych ewentualnie zmian. Chodzi mianowicie o to, że wszystkie ciągi kodowe są podzielne bez reszty przez wielomian generujący. Czyli
(2)
Wobec tego weryfikacja autentyczności dokumentu polega na wyznaczeniu reszty z dzielenia dokumentu odebranego. Gdy reszta z dzielenia jest niezerowa wiemy, że w dokumencie dokonano zmian, natomiast gdy reszta jest zerowa nie ma podstaw do takiego stwierdzenia. Ponieważ dokument odebrany to dokument wysłany s(x) oraz ewentualne zmiany e(x) (3)
można określić kiedy dokonane w dokumencie zmiany nie będą wykryte. Ponieważ reszta z dzielenia sumy równa jest sumie reszt, wyznaczana reszta z dzielenia to
(4)
Uwzględniając w (4) zależność (2) otrzymuje się (5)
co oznacza, że otrzymana reszta z dzielenia zależy tylko od dokonanych zmian w dokumencie i jest całkowicie niezależna od przesyłanych treści. Na podstawie tego można określić jakie zmiany dokumentu zostaną wykryte. (6)
Wynika z tego, że taka metoda nie pozwala na wykrycie tylko takich zmian w dokumencie, które odpowiadają innym możliwym do wysłania dokumentom.
(…)
…. Najbardziej znaczący sygnał reszty znajduje się w ostatniej komórce rejestru.
Układ dzielący zbudowany jest w układzie rejestru przesuwnego ze sprzężeniem zwrotnym. Długość rejestru równa jest stopniowi wielomianu dzielnika (generującego) i wynosi k. Sprzężenie zwrotne zrealizowane jest w układzie multiplikatorów odpowiadającym współczynników wielomianu dielnika. Istota działania takiego sprzężenia zwrotnego jest taka, że sygnał wysuwany w prawo poza obszar rejestru wracany jest modulo wielomian generującu na odpowiednie pozycje rejestru modyfikują jego zawartość.
Przykład 2
Rozpatruje się proces dzielenia wielomianu kodowego przez wielomian generujący . Schemat blokowy takiego układu dzielącego przedstawiono na rysunku 2. Przebieg układowej realizacji dzielenia zilustrowano w poniższej tabelce.
Numer impulsu
Sygnał…
… umieszczony jest skrót.
Druga procedura wyznaczania ciągów kodowych dla kodu rozdzielnego wykorzystuje w procesie kodowania wielomian kontrolny i w tym opracowaniu została pominięta.
Realizacja sprzętowa układu wyznaczania skrótu
Układ dzielący
Schemat blokowy układu dzielenia wprowadzonego na jego wejście ciągu współczynników wielomianu przez ciąg współczynników wielomianu przedstawiono na rysunku 1…
…. Najbardziej znaczący sygnał reszty znajduje się w ostatniej komórce rejestru.
Układ dzielący zbudowany jest w układzie rejestru przesuwnego ze sprzężeniem zwrotnym. Długość rejestru równa jest stopniowi wielomianu dzielnika (generującego) i wynosi k. Sprzężenie zwrotne zrealizowane jest w układzie multiplikatorów odpowiadającym współczynników wielomianu dielnika. Istota działania takiego sprzężenia zwrotnego…
... zobacz całą notatkę
Komentarze użytkowników (0)