拉賓指紋

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

方案

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

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

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

應用

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

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

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

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

參見

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