홍라이프 계산기체크섬 계산기 쉽게 이해하기 — 개념과 원리
체크섬은 데이터에서 짧은 값을 계산해 두었다가, 나중에 다시 계산해 비교함으로써 우연한 변경을 찾아내는 값입니다. 저장하거나 전송하는 동안 데이터가 바뀌면 다시 계산한 체크섬이 거의 확실히 달라집니다. 이 도구는 입력한 글의 UTF-8 바이트로 CRC-32(이더넷, ZIP, gzip, PNG에 사용), Adler-32(zlib 형식에 사용), 바이트 합 mod 256 세 가지를 계산합니다. 테스트 벡터 확인이나 구현 비교에 쓸 수 있습니다.
계산 방법
- CRC-32: 레지스터를 0xFFFFFFFF로 시작합니다. 바이트마다 하위 비트에 XOR한 뒤, 여덟 번 오른쪽으로 한 칸씩 밀면서 밀려난 비트가 1이면 0xEDB88320(생성 다항식 0x04C11DB7의 비트 역순)과 XOR합니다. 끝으로 모든 비트를 뒤집어 16진수 8자리로 나타냅니다.
- Adler-32: A는 1에서 시작해 바이트 값을 더하고, B는 바이트마다 그때의 A를 더합니다. 둘 다 2¹⁶보다 작은 가장 큰 소수 65521로 나눈 나머지를 쓰며, 결과는 B × 65536 + A입니다.
- 바이트 합 mod 256: 모든 바이트 값을 더해 256으로 나눈 나머지입니다.
원리
CRC는 메시지를 계수가 0과 1인 긴 다항식으로 보고, 정해진 생성 다항식으로 나눈 나머지를 구합니다. 이때 뺄셈 대신 XOR를 씁니다. 이런 대수적 구조 덕분에 32비트 CRC는 모든 1비트 오류와 길이 32비트 이하의 모든 연속 오류를 검출합니다. Adler-32는 계산이 더 빠릅니다. A는 단순 합이고, B는 각 바이트에 끝에서부터의 거리만큼 가중치를 주므로 두 바이트의 순서가 바뀌면 A는 같아도 B가 달라집니다. 단순 바이트 합은 가장 약해서 순서 바뀜을 전혀 알아채지 못합니다.
예제 풀이
- 입력 'The quick brown fox'는 ASCII 19자로 UTF-8 19바이트입니다.
- 바이트 값의 합은 1811이고 1811 = 7 × 256 + 19이므로 바이트 합은 19입니다.
- Adler-32에서 A = 1 + 1811 = 1812 = 0x0714, 바이트마다 A를 누적한 B = 17710 = 0x452E이므로 결과는 452E0714입니다.
- CRC-32는 19바이트에 위 절차를 적용하고 뒤집어 B74574DE를 얻습니다.
결과 해석
체크섬이 다르면 데이터가 바뀌었다는 확실한 증거입니다. 체크섬이 같으면 같은 데이터일 가능성이 매우 높지만 증명은 아닙니다. 32비트 값은 약 43억 가지라 한 번 비교에서는 우연한 일치가 드물지만, 아주 많은 파일을 비교하면 충돌이 생길 수 있습니다.
흔한 실수
- UTF-16이나 윈도 줄바꿈처럼 다른 바이트로 계산한 값과 비교하는 것
- CRC-32C(Castagnoli) 등 다른 CRC 변형과 섞어 쓰는 것
- 의도적인 위조를 막는 데 체크섬을 쓰는 것
자주 묻는 질문
CRC-32는 해시입니까?
넓은 의미의 해시이지만 선형적이라 쉽게 위조되므로 암호학적 해시는 아닙니다.
빈 입력의 결과는 무엇입니까?
CRC-32는 00000000, Adler-32는 A = 1, B = 0이라 00000001입니다.
출처: IETF RFC 1952, GZIP file format specification (CRC-32) · IETF RFC 1950, ZLIB Compressed Data Format Specification (Adler-32) · W. W. Peterson and D. T. Brown, Cyclic Codes for Error Detection, Proceedings of the IRE, 1961