Rabin-Fingerprint

Der Rabin-Fingerprint ist ein Verfahren zur Berechnung eines Fingerprints. Es wurde von Michael O. Rabin vorgeschlagen.

Motivation

Fingerprints sind kurze Etiketten für große Objekte. Unterschiedliche Fingerprints sollen unterschiedlichen Objekten entsprechen und unterschiedliche Objekte sollen nur mit geringer Wahrscheinlichkeit denselben Fingerprint haben.

Der Rabin-Fingerprint ist ein spezielles Verfahren, das auf der Arithmetik in ℤ2[x] modulo eines irreduziblen Polynoms mit Koeffizienten in ℤ2 beruht.

Methode

Verschlüsselt werden soll ein String (a1,…,am) aus Nullen und Einsen mit a1=1. Dieser wird als Polynom a1tm−1+…+a2tm−2+…+am mit Koeffizienten in ℤ2 aufgefasst, das Eingabe-Polynom A(x).

Für die Berechnung wird ein Schlüssel P(x), ebenfalls aus ℤ2[x], benötigt. Bei P(x) soll es sich um ein irreduzibles Polynom handeln.

Die Rabin-Fingerprintfunktion f ist als

f(A)(x)=A(x)modP(x)

definiert.

Verwendung

Besonders geeignet ist der Rabin-Fingerprint beim Einsatz zur Erkennung von identischen oder ähnlichen Abschnitten in unterschiedlichen Dateien, d. h. zur Erkennung von Redundanz. Diese kann dann zum Beispiel zur Optimierung von Dateitransferprozessen oder bei der Archivierung von Daten genutzt werden. So benutzt etwa das am Massachusetts Institute of Technology entwickelte Dateisystem LBFS (Low-Bandwidth File System) den Rabin-Fingerprint.