라빈 지문

라빈 지문채취 방식은 한정된 분야에 걸쳐 다항식을 이용해 지문을 구현하는 방식이다.그것은 마이클 O. 라빈에 의해 제안되었다.^[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}:{n-1}$

We then pick a random irreducible polynomial ${\displaystyle p(x)}$ of degree k over GF(2), and we define the fingerprint of the message m to be the remainder ${\displaystyle r(x)}$ after division of ${\displaystyle f(x)}$ by ${\displaystyle p(x)}$ over GF(2) which can be viewed as a polynomiak-1의 l 도 또는 k-비트 숫자로.

적용들

라빈-카프 알고리즘의 많은 구현은 내부적으로 라빈 지문을 사용한다.

MIT의 LBFS(Low Bandwidth Network Filesystem)는 Rabin 지문을 사용하여 가변 크기 이동 방지 블록을 구현한다.^[2]기본적인 생각은 파일시스템이 파일에 있는 각 블록의 암호 해시를 계산한다는 것이다.클라이언트와 서버 간의 전송을 절약하기 위해, 그들은 체크섬을 비교하고 체크섬이 다른 전송 블록만 비교한다.그러나 이 계획의 한 가지 문제는 고정 크기(예: 4KB) 블록을 사용할 경우 파일 시작 부분에 한 번 삽입하면 모든 체크섬이 변경된다는 것이다.따라서 특정 오프셋이 아닌 블록 콘텐츠의 일부 속성에 따라 블록을 선택하는 것이 목적이다.LBFS는 48바이트의 창을 파일 위로 미끄러뜨리고 각 창의 라빈 지문을 계산하여 이것을 한다.지문의 낮은 13비트가 0이면 LBFS가 48바이트를 중단점으로 호출하고 현재 블록을 종료하고 새 블록을 시작한다.라빈 지문의 출력은 사이비 무작위적이기 때문에 주어진 48바이트가 중단점이 될 확률은 $2{\displaystyle {\mathrm{}}^{}}$- ${\displaystyle {13}^{}}$ ${\$ 2$^{-13}($8192의 1개)$$이다.이는 이동 저항형 가변 크기 블록의 효과가 있다.어떤 해시함수라도 긴 파일을 블록으로 나누는 데 사용될 수 있지만(암호 해시함수를 사용하여 각 블록의 체크섬을 찾는 한), 라빈 지문은 효율적인 롤링 해시인데, 영역 B의 라빈 지문 계산은 영역 A의 라빈 지문 계산의 일부를 재사용할 수 있기 때문이다.지역 A와 B가 겹친다.

이것은 rsync가 직면한 것과 유사한 문제라는 점에 유의한다.

참고 항목

• W싱글링
• 롤링 해시

참조

외부 링크

• Andrei Z. Broder (1993). "Some applications of Rabin's fingerprinting method". Retrieved 2011-09-12. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
• David Andersen (2007). "Exploiting Similarity for Multi-Source Downloads using File Handprints". Retrieved 2007-04-12. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
• 로스 N. 윌리엄스(1993)"CRC 오류 감지 알고리즘에 대한 무통 가이드"