Rabin fingeravtryck

Rabins fingeravtrycksschema är en metod för att implementera fingeravtryck med polynom över ett ändligt fält . Det föreslogs av Michael O. Rabin .

Schema

₀ Givet ett n -bitars meddelande m ,..., m _n-1 ser vi det som ett polynom med graden n -1 över det finita fältet GF(2) .

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

Vi väljer sedan ett slumpmässigt irreducerbart polynom $p(x)$ av grad k över GF(2), och vi definierar fingeravtrycket för meddelandet m att vara resten $r( x)$ efter division av $f(x)$ med $p(x)$ över GF(2) som kan ses som ett polynom med graden k − 1 eller som ett k -bit nummer.

Ansökningar

Många implementeringar av Rabin-Karp-algoritmen använder internt Rabin-fingeravtryck.

Low Bandwidth Network Filesystem (LBFS) från MIT använder Rabin-fingeravtryck för att implementera skiftbeständiga block med variabel storlek. Grundidén är att filsystemet beräknar den kryptografiska hashen för varje block i en fil. För att spara på överföringar mellan klienten och servern jämför de sina kontrollsummor och överför bara block vars kontrollsummor skiljer sig åt. Men ett problem med detta schema är att en enda infogning i början av filen kommer att göra att varje kontrollsumma ändras om block med fast storlek (t.ex. 4 KB) används. Så tanken är att välja block inte baserat på en specifik offset utan snarare utifrån någon egenskap hos blockinnehållet. LBFS gör detta genom att föra ett 48 byte-fönster över filen och beräkna Rabin-fingeravtrycket för varje fönster. När de låga 13 bitarna i fingeravtrycket är noll kallar LBFS dessa 48 byte en brytpunkt och avslutar det aktuella blocket och börjar ett nytt. Eftersom utmatningen av Rabins fingeravtryck är pseudoslumpmässiga är sannolikheten för att varje given 48 byte är en brytpunkt $2^{-13}$ (1 av 8192). Detta har effekten av skiftbeständiga block med variabel storlek. Vilken hashfunktion som helst kan användas för att dela upp en lång fil i block (så länge som en kryptografisk hashfunktion sedan används för att hitta kontrollsumman för varje block): men Rabin-fingeravtrycket är en effektiv rullande hash , eftersom beräkningen av Rabin-fingeravtrycket av region B kan återanvända en del av beräkningen av Rabin-fingeravtrycket för region A när regionerna A och B överlappar varandra.

Observera att detta är ett problem som liknar det som rsync möter .

Se även

• W-shingling
• Rullande hash

externa länkar

• Andrei Z. Broder (1993). "Några tillämpningar av Rabins fingeravtrycksmetod" : 143–152 . Hämtad 2011-09-12 . {{ citera journal }} : Citera journal kräver |journal= ( hjälp )
• David Andersen (2007). "Utnyttja likheter för nedladdningar med flera källor med filhandavtryck" . Hämtad 2007-04-12 . {{ citera journal }} : Citera journal kräver |journal= ( hjälp )
• Ross N. Williams (1993). " En smärtfri guide till CRC-feldetekteringsalgoritmer" .