imported>회기-로: /* Methode */

2021-07-20T06:09:20Z

Methode

Neue Seite

Der '''Rabin-Fingerprint''' ist ein Verfahren zur Berechnung eines [[Fingerprint (Hashfunktion)|Fingerprints]]. Es wurde von [[Michael O. Rabin]] vorgeschlagen.<ref name="rabin1981" />

== 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 <math>\Z_2\left[x\right]</math> modulo eines irreduziblen Polynoms mit Koeffizienten in <math>\Z_2</math> beruht.

== Methode ==
Verschlüsselt werden soll ein String <math>(a_1,\ldots,a_m)</math> aus Nullen und Einsen mit <math>a_1=1</math>. Dieser wird als [[Polynom]] <math>a_1t^{m-1}+\ldots+a_2t^{m-2}+\ldots+a_m</math> mit Koeffizienten in <math>\Z_2</math> aufgefasst, das Eingabe-Polynom <math>A(x)</math>.

Für die Berechnung wird ein Schlüssel <math>P(x)</math>, ebenfalls aus [[Z2 (Gruppe)|<math>\mathbb{Z}_2[x]</math>]], benötigt. Bei <math>P(x)</math> soll es sich um ein irreduzibles Polynom handeln.

Die Rabin-Fingerprintfunktion <math>f</math> ist als
:<math>f(A)(x) = A(x) \mod P(x)</math>
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.<ref name="kulkarni:usenix2004" />

== Weblinks ==
* A. Broder: [https://www.researchgate.net/profile/Andrei-Broder/publication/2688260_Some_applications_of_Rabin%27s_fingerprinting_method/links/0912f51487bc1b7e39000000/Some-applications-of-Rabins-fingerprinting-method.pdf?origin=publication_detail Some applications of Rabin‘s fingerprinting method]

== Einzelnachweise ==
<references>
<ref name="rabin1981">
{{Literatur
|Autor=[[Michael O. Rabin]]
|Titel=Fingerprinting by Random Polynomials
|Verlag=Center for Research in Computing Technology, Harvard University
|Datum=1981
|Sprache=en
|Online=http://www.xmailserver.org/rabin.pdf
|Format=PDF
|KBytes=465
|Abruf=2014-12-09}}
</ref>
<ref name="kulkarni:usenix2004">
{{Internetquelle
|autor=Purushottam Kulkarni, Fred Douglis, Jason D. LaVoie, John M. Tracey
|url=https://www.usenix.org/legacy/event/usenix04/tech/general/full_papers/kulkarni/kulkarni_html/paper.html
|titel=Redundancy Elimination Within Large Collections of Files
|werk=[[USENIX]] Annual Technical Conference, General Track
|datum=2004-05-12
|seiten=59–72
|abruf=2015-02-21
|sprache=en}}
</ref>
</references>

[[Kategorie:Kryptologie]]

Rabin-Fingerprint - Versionsgeschichte

imported>회기-로: /* Methode */