拉賓指紋

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

拉賓指紋是一種在有限體上使用多項式實現指紋英語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"頁面存檔備份,存於互聯網檔案館

外部連結