Adler-32 체크섬 알고리즘에서 모듈로 65521이 필요한 이유는 무엇입니까?

Question

Adler-32 체크섬 알고리즘은 모듈로 65521의 합계를 수행합니다.65521이 16비트에 맞는 가장 큰 소수라는 것은 알고 있는데, 이 알고리즘에서 소수를 사용하는 것이 왜 중요한가요?

(누군가가 나에게 말하면 대답이 분명해 보일 것이라고 확신하지만 내 뇌의 정수론 부분이 작동하지 않습니다.체크섬 알고리즘에 대한 전문 지식이 없어도 책을 읽는 똑똑한 사람 http://en.wikipedia.org/wiki/Fletcher%27s_checksum 아마도 나에게 설명할 수 있을 것이다.)

Answer 1

Adler32에 Mod Prime을 사용한 이유는 무엇입니까?

Adler의 자체 웹사이트에서 http://zlib.net/zlib_tech.html

그러나 Adler-32는 바이트보다 상당히 큰 합을 사용하고 모듈러스에 프라임 (65521)을 사용하여 동일한 체크 값을 초래하는 데이터를 작은 변경 방법을 최소화하기 위해 구성되었습니다. 이 분야에서는 일부 분석이 가치가 있지만 아직 수행되지 않았습니다.

Adler-32의 주된 이유는 물론 소프트웨어 구현 속도 때문입니다.

Adler-32의 대안은 65521의 모듈로를 65535로 대체하는 Fletcher-32입니다.이 논문에서는 Fletcher-32가 낮은 비율의 무작위 비트 오류가 있는 채널에 대해 우수함을 보여줍니다.

소수가 더 나은 혼합 특성을 갖는 경향이 있기 때문에 사용되었습니다.정확히 얼마나 좋은지에 대해서는 논의가 남아 있습니다.

기타 설명

이 스레드의 다른 누군가는 소수 모듈러스가 비트 스와핑을 감지하는 데 더 좋다는 다소 설득력 있는 주장을 합니다.그러나 이것은 가능성이 가장 높습니다. 그렇지 않다 비트 교환은 극히 드물기 때문입니다.가장 널리 퍼진 두 가지 오류는 다음과 같습니다.

1. 무작위 비트플립(1 <-> 0)은 어디에서나 일반적입니다.
2. 네트워킹에서 일반적인 비트 이동(1 2 3 4 5 -> 2 3 4 5 또는 1 1 2 3 4 5)

대부분의 비트 스와핑은 비트 스와핑처럼 보이는 임의의 비트 플립으로 인해 발생합니다.

실제로 오류 수정 코드는 n비트의 편차를 견디도록 설계되었습니다.Adler의 웹사이트에서:

올바르게 구성된 CRC-N은 N 비트 미만의 오류가 항상 감지 할 수있는 멋진 특성을 가지고 있습니다.Adler-32의 경우 항상 사실은 아닙니다. 모든 1 또는 2 바이트 오류를 ​​감지 할 수 있지만 일부 3 바이트 오류를 ​​놓칠 수 있습니다.

프라임 모듈러스 사용의 효율성

나는 본질적으로 같은 질문에 대해 긴 글을 썼습니다.왜 소수를 모듈로로 사용하나요?

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

짧은 대답

우리는 합성수보다 소수에 대해 아는 것이 훨씬 적습니다.그래서 Knuth와 같은 사람들이 그것을 사용하기 시작했습니다.

소수가 우리가 해시하는 많은 데이터와 덜 관계가 있다는 것이 사실일 수 있지만, 테이블/모듈로 크기를 늘리면 충돌 가능성도 줄어듭니다(때로는 가장 가까운 소수로 반올림하여 얻는 이점보다 더 많음).

다음은 모드 65521과 65535를 비교하여 암호화된 무작위 정수 1천만 개를 사용한 버킷당 충돌 그래프입니다.

Answer 2

Adler-32 알고리즘은 계산하는 것입니다

A = 1 + b1 + b2 + b3 + ...

그리고

B = (1 + b1) + (1 + b1 + b2) + (1 + b1 + b2 + b3) + ... = 1 + b1 + 2 * b2 + 3 * b3 + ...

그리고 그들을 모듈로보고하십시오. m이 프라임이면, 숫자 modulo m은 수학자들이 부르는 것을 형성합니다. 필드. 필드는 0이 아닌 C의 경우 C * a = C * B 인 경우에만 A = B를 갖는 편리한 속성을 가지고 있습니다. Times Table Modulo 5와 Times Table Modulo 6을 비교하십시오.

* 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

* 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

이제 우리가 두 바이트를 교류 할 때마다 A 부품이 바보가됩니다. 결국 추가는 통근 적입니다. B 부분은 이러한 종류의 오류를 감지해야하지만 M이 주요한 경우 더 많은 위치가 취약합니다. Adler Checksum Mod 6을 고려하십시오

1 3 2 0 0 4

우리는 a = 4와 b = 1이 있습니다. 이제 b2와 b4 교환을 고려하십시오.

1 0 2 3 0 4

2 * 3 = 4 * 0 = 2 * 0 = 4 * 3 (모듈로 6)이기 때문에 A와 B는 변경되지 않습니다. 또한 2와 5를 동일한 효과로 바꿀 수도 있습니다. 이것은 Times 테이블이 불균형 일 때 가능성이 높습니다. 모듈로 5, 이러한 변화가 감지됩니다. 실제로, 프라임 모듈러스가 단일 스왑을 감지하지 못하는 유일한 시간은 두 개의 동일한 인덱스 모드 m이 교환 될 때 (그리고 m이 크면, 멀리 떨어져 있어야합니다!)^이 논리는 상호 교환 된 하위 문자열에도 적용될 수 있습니다.

작은 계수를 사용하는 데있어 단점은 임의의 데이터에서 약간 더 자주 실패한다는 것입니다. 그러나 실제 세계에서는 부패가 거의 무작위가 아닙니다.

^ 증거 : INDEX를 I 및 J를 값 A 및 B로 바꾸는다고 가정 해 봅시다. 그 다음에i + bj = aJ + b나, 그래서 ai -aJ + bJ -bI = 0 및 (a -b)*(i -j) = 0. 필드는 적분 도메인이므로 a = b (값이 일치) 또는 i = j (인덱스가 일치)를 따릅니다.

편집 : 알 수없는 웹 사이트 (http://www.zlib.net/zlib_tech.html)는 Adler-32의 디자인이 전혀 원칙적이지 않았 음을 분명히합니다. Deflate 스트림의 Huffman 코드로 인해 작은 오류조차도 프레임이 변경 될 수 있으며 (데이터 의존적이기 때문에) 출력에 큰 오류가 발생할 수 있습니다. 이 대답은 사람들이 특정 속성에 대한 특정 속성을 프라임에 묘사하는 이유에 대한 약간 고안된 예를 고려하십시오.

Answer 3

짧은 이야기 :

Prime의 모듈로는 최고의 비트 셔플 링 특성을 가지고 있으며, 이것이 우리가 해시 가치에 대해 원하는 것입니다.

Answer 4

완벽하게 임의의 데이터의 경우 버킷이 많을수록 좋습니다.

데이터가 어떤 식 으로든 비 랜덤이라고 가정 해 봅시다. 이제 비 랜덤이 알고리즘에 영향을 줄 수있는 유일한 방법은 일부 버킷이 다른 버킷보다 사용할 확률이 높은 상황을 만드는 것입니다.

모듈로 수가 비 프라임 인 경우 모듈로를 구성하는 숫자 중 하나에 영향을 미치는 패턴은 해시에 영향을 줄 수 있습니다. 따라서 15를 사용하는 경우 3 ~ 5 개마다 패턴과 15 개마다 충돌을 일으킬 수있는 반면 13을 사용하는 경우 충돌을 일으키려면 패턴이 13 개마다 있어야합니다.

65535 = 3*5*17*257, 따라서 3 또는 5를 포함하는 패턴은이 모듈로를 사용하여 충돌을 일으킬 수 있습니다. 잘 활용하십시오.

이제 현실적으로 이것이 문제 일 수 있는지 확실하지 않습니다. 유형 1의 실제 데이터와 함께 충돌 속도를 경험적으로 결정하는 것이 좋을 것입니다. (예를 들어, http://en.wikipedia.org/wiki/benford's_law"> Benford의 법칙 또는이 알고리즘에 영향을 줄 수있는 일부 불규칙성 원인 패턴과 관련된 수치 데이터는 현실적인 텍스트에 ASCII 코드를 사용하는 방법에 어떻게 영향을 미칩니 까?)

Answer 5

체크섬은 일반적으로 두 가지가 다르다는 것을 감지하려는 의도로 일반적으로 사용됩니다. 다른 장소 (예 : 전송 된 정보 패킷, 수신 된 정보 패킷) 또는 다른 시간 (예 : 저장된 정보 블록, 다시 읽을 때 정보 블록)에서 사용할 수 있습니다. . 경우에 따라, 한 장치에서 다른 장치에서 다른 장치에서 실제 데이터를 다른 장치로 보내지 않고도 두 개의 다른 장소에 독립적으로 저장되는 두 가지가 일치 할 가능성이 있는지 확인하는 것이 바람직 할 수 있습니다 (예 :로드 된 코드 이미지 또는 구성 비교).

일치하지 않는 유일한 이유가 그들 중 하나의 무작위 손상이라면 Adler-32 체크섬에 프라임 계수를 사용하는 것이 특히 도움이되지 않을 것입니다. 그러나 사물 중 하나가 '고의적 인'변경이 있었을 가능성이 있다면 비 프라임 계수를 사용하면 특정 변경 사항이 눈에 띄지 않을 수 있습니다. 예를 들어, 바이트를 00에서 FF로 변경하고 FF에서 257 바이트 중 일부 중 일부 인 다른 바이트를 변경하는 효과는 Fletcher의 체크섬을 사용할 때 취소되지만 Adler-32 체크섬을 사용할 때는 그렇지 않습니다. 그러한 시나리오가 무작위 손상으로 인해 발생할 가능성은 없지만 프로그램을 변경할 때 이러한 상쇄 변경이 발생할 수 있습니다. 정확히 257 바이트의 정확한 배수가 발생할 가능성은 없지만 프라임 모듈러스를 사용하여 피할 수있는 위험입니다 (적어도 파일의 바이트 수가 모듈러스)

Answer 6

대답은 현장 이론에 있습니다. N이 프라임 인 경우 작업과 UND 시간이있는 세트 Z/Z_N은 필드입니다 (즉, Modulo N과의 곱하기 곱하기).

다시 말해, 다음 방정식은 다음과 같습니다.

m * x = (in Z/Z_n) 

모든 값에 대한 솔루션이 하나뿐 이어 (즉, x = 0)

이 예를 고려하십시오 :

2 * x = 0 (mod 10)

이 방정식에는 x = 0과 x = 5의 두 가지 솔루션이 있습니다. 이는 10이 프라임이 아니며 2 * 5로 쓸 수 있기 때문입니다.

이 속성은 해시 값의 더 나은 분포를 담당합니다.