拉賓指紋

拉賓指紋是一種在有限域上使用多項式實現指紋（英語：Fingerprint (computing)）的方法。它是由邁克爾·拉賓提出的。 ^[1]

方案

給定一個n位消息m₀,...,m_n-1，我們將其視為在有限域 GF(2)上的n-1次多項式。

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

然後，我們隨機選擇一個在GF(2)上的k次不可約多項式 $p(x)$ ，我們將消息m的指紋定義為在GF（2）上 $f(x)$ 除以 $p(x)$ 的餘數 $r(x)$ ，它可以看作是一個k-1次多項式或k位數字。

應用

拉賓-卡普算法的許多實現，在內部是使用的拉賓指紋。

麻省理工學院的低帶寬網絡文件系統（LBFS）使用拉賓指紋來實現可變大小的抗移位塊。^[2]

其基本思想是，文件系統計算文件中每個塊的加密哈希。為了節省客戶端和服務器之間的傳輸，它們比較其校驗和，只傳輸校驗和不同的塊。但是這種方案有一個問題，就是如果使用固定大小（例如4KB）的塊，那麼在文件開頭的一次插入將導致每個校驗和都發生變化。因此，我們的想法是不基於特定的偏移量，而是根據塊內容的某些屬性來選擇塊。LBFS通過在文件上滑動48個字節的窗口並計算每個窗口的拉賓指紋來做到這一點。當指紋的低13位為零時，LBFS將這48個字節稱為斷點，並結束當前塊、開始一個新的。由於拉賓指紋的輸出是偽隨機的，因此任何給定的48個字節為斷點的概率為 $2^{-13}$ （8192分之1）。這就有了抗移位可變尺寸塊的效果。任何哈希函數都可以用於將一個長文件分成多個塊（只要隨後使用加密哈希函數查找每個塊的校驗和即可）：但是拉賓指紋是一種高效的旋轉哈希，因為當區域A和B重疊時，區域B的拉賓指紋的計算可以重複使用區域A的拉賓指紋的部分計算。

請注意，這與rsync面臨的問題相似。

參見

W-重迭（英語：W-shingling）
旋轉哈希

參考文獻

^ 邁克爾·拉賓. Fingerprinting by Random Polynomials (PDF). Center for Research in Computing Technology, Harvard University. 1981 [2007-03-22]. Tech Report TR-CSE-03-01. （原始內容存檔 (PDF)於2007-02-21）（英語）.
^ Athicha Muthitacharoen, Benjie Chen, and David Mazières "A Low-bandwidth Network File System" （頁面存檔備份，存於網際網路檔案館）

外部連結

Andrei Z. Broder. Some applications of Rabin's fingerprinting method. 1993 [2011-09-12]. （原始內容存檔於2016-03-04）.
David Andersen. Exploiting Similarity for Multi-Source Downloads using File Handprints. 2007 [2007-04-12]. （原始內容存檔於2007-05-16）.
Ross N. Williams (1993). "A painless guide to CRC Error detection algorithms（頁面存檔備份，存於網際網路檔案館）".

[1] 邁克爾·拉賓. Fingerprinting by Random Polynomials (PDF). Center for Research in Computing Technology, Harvard University. 1981 [2007-03-22]. Tech Report TR-CSE-03-01. （原始內容存檔 (PDF)於2007-02-21）（英語）.

[2] Athicha Muthitacharoen, Benjie Chen, and David Mazières "A Low-bandwidth Network File System" （頁面存檔備份，存於網際網路檔案館）

[1]

[2]