Odcisk palca Rabina

Schemat odcisków palców Rabina to metoda implementacji odcisków palców przy użyciu wielomianów w skończonym polu . Został on zaproponowany przez Michaela O. Rabina .

Schemat

₀ Mając n -bitową wiadomość m ,..., m _n-1 , postrzegamy ją jako wielomian stopnia n -1 nad ciałem skończonym GF(2) .

{\ Displaystyle f (x) = m_ {0} + m_ {1} x + \ ldots + m_ {n-1} x ^ {n-1}}

Następnie wybieramy losowy nieredukowalny wielomian $r$ k na GF (2 $)}$ i definiujemy odcisk palca wiadomości m jako resztę $displaystyle$ $GF$ po podzieleniu przez ( które można postrzegać jako wielomian stopnia k $\ Displaystyle p (x)}$ ) − 1 lub jako liczba k -bitowa.

Aplikacje

Wiele implementacji algorytmu Rabina – Karpa wewnętrznie wykorzystuje odciski palców Rabina.

Sieciowy system plików o niskiej przepustowości (LBFS) z MIT wykorzystuje odciski palców Rabina do implementacji bloków odpornych na zmiany rozmiaru o zmiennej wielkości. Podstawową ideą jest to, że system plików oblicza kryptograficzny skrót każdego bloku w pliku. Aby zaoszczędzić na transferach między klientem a serwerem, porównują swoje sumy kontrolne i przesyłają tylko bloki, których sumy kontrolne są różne. Ale jeden problem z tym schematem polega na tym, że pojedyncze wstawienie na początku pliku spowoduje zmianę każdej sumy kontrolnej, jeśli używane są bloki o stałym rozmiarze (np. 4 KB). Pomysł polega więc na wybieraniu bloków nie na podstawie określonego przesunięcia, ale raczej na podstawie jakiejś właściwości zawartości bloku. LBFS robi to, przesuwając 48-bajtowe okno nad plikiem i obliczając odcisk palca Rabina każdego okna. Kiedy dolne 13 bitów odcisku palca wynosi zero, LBFS wywołuje te 48 bajtów jako punkt przerwania i kończy bieżący blok i rozpoczyna nowy. Od wyjścia Rabina są odciski palców pseudolosowe prawdopodobieństwo, że dowolne 48 bajtów będzie punktem przerwania, $1$ 8192). Daje to efekt odpornych na przesunięcie bloków o zmiennej wielkości. Dowolna funkcja skrótu może być użyta do podzielenia długiego pliku na bloki (o ile kryptograficzna funkcja skrótu jest następnie używana do znalezienia sumy kontrolnej każdego bloku): ale odcisk palca Rabina jest wydajnym haszem kroczącym , ponieważ obliczenie odcisku palca Rabina regionu B może ponownie wykorzystać część obliczeń odcisku palca Rabina regionu A , gdy regiony A i B nakładają się.

Zauważ, że jest to problem podobny do tego, z którym boryka się rsync . ^{[ potrzebny przykład ]}

Zobacz też

^ Michael O. Rabin (1981). „Odcisk palca przez losowe wielomiany” (PDF) . Centrum Badań nad Technologią Komputerową Uniwersytetu Harvarda. Raport techniczny TR-CSE-03-01 . Źródło 2007-03-22 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
^ Athicha Muthitacharoen, Benjie Chen i David Mazières „Sieciowy system plików o niskiej przepustowości”

Linki zewnętrzne

Andriej Z. Broder (1993). „Niektóre zastosowania metody pobierania odcisków palców Rabina” : 143–152 . Źródło 2011-09-12 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
Davida Andersena (2007). „Wykorzystywanie podobieństw do pobierania z wielu źródeł przy użyciu odcisków dłoni plików” . Źródło 2007-04-12 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
Ross N. Williams (1993). „ Bezbolesny przewodnik po algorytmach wykrywania błędów CRC ”.

[1] Michael O. Rabin (1981). „Odcisk palca przez losowe wielomiany” (PDF) . Centrum Badań nad Technologią Komputerową Uniwersytetu Harvarda. Raport techniczny TR-CSE-03-01 . Źródło 2007-03-22 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )

[2] Athicha Muthitacharoen, Benjie Chen i David Mazières „Sieciowy system plików o niskiej przepustowości”