拉賓指紋

在有限域上使用多项式实现指纹的方法,由迈克尔·拉宾提出

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

方案

編輯

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

 

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

應用

編輯

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

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

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

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

參見

編輯

參考文獻

編輯
  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"頁面存檔備份,存於網際網路檔案館

外部連結

編輯