CRC — 순환 중복 검사, 처음부터 설명

한 문장으로: CRC는 데이터를 하나의 거대한 이진수로 취급해 고정된 "생성자" 수로 나누되 뺄셈 대신 XOR를 사용하고, 그 나머지를 보고합니다 — 입력의 단 한 비트가 뒤집혀도 격렬하게 변하는 간결한 지문으로, PNG 파일부터 Modbus 선로까지 모든 것이 하나씩 싣고 있는 이유입니다.

CRC가 실제로 무엇인가

나눗셈 그림. 바이트들을 하나의 긴 이진수로 늘어놓으세요. 나눗수 — 다항식, 예: CRC-32의 0x04C11DB7 — 를 고르고, "뺄셈"이 XOR 연산인 이진 긴 나눗셈을 수행합니다. 진행 중인 나머지의 최상위 비트가 1일 때마다 나눗수를 XOR하고 왼쪽으로 시프트하며 반복합니다. 전체 메시지가 지나가면 레지스터에 남은 것이 CRC입니다. 정의에 키도 테이블도 없습니다 — 그저 나머지 있는 나눗셈일 뿐입니다.

다섯 개의 파라미터. 두 시스템이 모두 "CRC-32"라고 말하면서도 서로 다를 수 있습니다. 이름만으로는 아무것도 확정되지 않기 때문입니다. 완전한 레시피에는 다섯 값이 필요합니다: poly(나눗수), init(레지스터의 시작값 — 전부 0이면 선행 0바이트가 사라지고, 전부 1이면 사라지지 않음), refin/refout(각 입력 바이트와 최종 레지스터를 비트 반전할지 — 최하위 비트부터 보내던 직렬 하드웨어의 유산), xorout(마지막 XOR 마스크로, 뒤에 0이 이어져도 답이 변하게 함). 이 페이지가 모든 결과 옆에 다섯 가지를 전부 인쇄하는 것은 정확히 이 때문입니다.

오류를 감지하는 이유. 잘 고른 나눗수는 메시지의 나머지와 몇 비트 뒤집힌 같은 메시지의 나머지가 압도적 확률로 달라지게 만듭니다. 좋은 CRC-32는 모든 1비트·2비트 오류, 모든 홀수 개 비트 오류, 32비트까지의 모든 연속 버스트 오류를 잡습니다 — 확률이 아니라 보장됩니다. 이 보장은 우발적 손상에 관한 것이며, CRC를 소음 있는 선로와 불안정한 디스크에 알맞은 도구로 만듭니다.

CRC가 아닌 것

암호학적 해시가 아닙니다. 비밀도 일방향성도 없습니다. 파라미터를 아는 사람은 누구나 수정 바이트 네 개를 덧붙여 밀리초 만에 원하는 어떤 CRC를 가진 메시지도 위조할 수 있습니다. CRC는 사고를 감지하지 적수를 결코 감지하지 못합니다. 모르는 상대와 검증하는 다운로드에는 서명이 중요합니다 — 해시 생성기(MD5/SHA/BLAKE2)를 대신 보세요. 그 페이지는 MD5와 SHA-1이 왜 적대적 환경에서 은퇴했고 SHA-256은 왜 버티는지도 설명합니다.

오류 정정 부호가 아닙니다. CRC는 무언가 바뀌었다는 것을 알려 줄 뿐 무엇이 바뀌었는지는 알려 주지 않습니다. 오류를 즉석에서 수리하는 것은 Reed–Solomon이나 Hamming 같은 부호의 일로, 디코더가 되돌릴 수 있는 여분 구조를 의도적으로 저장합니다.

압축이나 암호화가 아닙니다. 나머지는 입력 크기와 무관하게 몇 바이트일 뿐이고 그로부터 입력을 복구할 수 없습니다 — 그러나 암호학적 해시와 달리 그것은 단지 정보가 버려졌기 때문이지 되돌리기가 어렵기 때문이 아닙니다.

이 페이지의 계열

CRC-32 사중주. 이 페이지의 네 항목이 다항식 0x04C11DB7을 공유하면서도 다른 값을 냅니다: ISO-HDLC(반전형, init/xorout 전부 1)가 zlib, gzip, PNG, ZIP의 "그" CRC-32이고, BZIP2는 같은 수학을 비반전으로, MPEG-2는 BZIP2에서 마지막 XOR를 뺀 것이며, POSIX는 0에서 시작해 cksum 명령의 기반입니다(추가로 나누기 전에 파일 길이를 덧붙이므로 파일의 cksum과 같은 바이트의 CRC-32/POSIX는 다릅니다). CRC-32C(Castagnoli, 다항식 0x1EDC6F41)는 다섯 번째 형제입니다. 더 나은 오류 감지 성능을 위해 고른 다른 다항식이며, 현대 x86과 ARM CPU가 한 명령으로 메모리 속도에 계산하는 것이 바로 이것입니다.

CRC-64 사중주. XZ는 ECMA-182 다항식을 반전형으로, init과 xorout을 전부 1로 사용합니다. ECMA-182 자체는 DLT-1 테이프 표준의 비반전형 0-init 원본입니다. GO-ISO는 Go의 crc64.ISO로, 작은 다항식 0x1B을 여전히 반전형으로 씁니다. REDIS는 해시 슬롯 배정에서 좋은 Avalanche를 위해 고른 다항식을 씁니다. 64비트는 CRC가 순수 체크섬이 아니라 해시 함수(버킷팅)로 쓰이기 시작하는 크기입니다.

Adler-32는 이방인입니다. 전혀 나눗셈이 아닙니다. 바이트를 합하고(A, 1에서 시작) 그 합들을 다시 합하며(B) 둘 다 65521로 나눈 나머지를 취해 두 개의 16비트 합을 이어 붙입니다. 소프트웨어에서 CRC-32보다 빠르고 zlib이 deflate 스트림에 사용하지만, 짧은 입력(수백 바이트 미만)에서는 합이 너무 적은 정보를 담습니다. zlib이 작은 블록에서 CRC-32로 되돌아가는 이유가 정확히 이것입니다.

CRC-8과 CRC-16은 바이트가 비싼 곳에서 살아남습니다. CRC-8/CCITT(다항식 0x07)는 SMBus와 이동통신 프로토콜의 단일 헤더 바이트를 보호하고, CRC-16/CCITT-FALSE는 스마트카드 블록을 지키며, CRC-16/MODBUS는 전 세계 공장 바닥의 모든 Modbus RTU 프레임의 체크섬입니다.

각각이 쓰이는 곳

파라미터 집합	사용처
CRC-32/ISO-HDLC	zlib, gzip, PNG, ZIP, 이더넷(FCS), 수많은 아카이브 형식
CRC-32C	iSCSI, ext4, btrfs, ZFS, SSE4.2/ARMv8 하드웨어 CRC32C 명령
CRC-32/BZIP2	.bz2 아카이브 스트림
CRC-32/MPEG-2	MPEG-2 전송 스트림
CRC-32/POSIX & cksum	POSIX `cksum` 명령 출력 (`cksum file.txt`)
CRC-16/MODBUS	Modbus RTU 프레임 (산업용 PLC, 계량기, 인버터)
CRC-16/CCITT-FALSE	스마트카드, X.25 계열 링크, 일부 GPS 프로토콜
CRC-8/CCITT	SMBus(PEC 바이트), 이동통신 라디오 헤더
CRC-64/XZ	.xz 컨테이너 무결성 검사
CRC-64/ECMA-182	ECMA-182 / DLT-1 테이프 표준
CRC-64/GO-ISO	Go 표준 라이브러리 `crc64.ISO`
CRC-64/REDIS	Redis 클러스터 해시 슬롯 배정
Adler-32	zlib 스트림(deflate), 그 외 빠른 체크섬 맥락

앵커 표 — check("123456789")

CRC 카탈로그의 관례는 ASCII 문자열 123456789(9바이트)의 결과를 공개하는 것입니다. 아래의 모든 값은 이 페이지에서 재현 가능합니다. 텍스트 상자에 123456789를 입력하고 알고리즘에 체크한 뒤 계산을 누르세요.

파라미터 집합	폭	체크 값 (16진수)
CRC-8/CCITT	8	0xf4
CRC-16/CCITT-FALSE	16	0x29b1
CRC-16/MODBUS	16	0x4b37
CRC-32/ISO-HDLC	32	0xcbf43926
CRC-32C	32	0xe3069283
CRC-32/BZIP2	32	0xfc891918
CRC-32/MPEG-2	32	0x0376e6e7
CRC-32/POSIX	32	0x765e7680
cksum (POSIX command)	32	0x377a6011
CRC-64/XZ	64	0x995dc9bbdf1939fa
CRC-64/ECMA-182	64	0x6c40df5f0b497347
CRC-64/GO-ISO	64	0xb90956c775a41001
CRC-64/REDIS	64	0xe9c6d914c4b8d9ca
Adler-32	32	0x091e01de

출처: 각 값은 독립적인 비트 단위 참조 구현으로 교차 검증되었고, 해당 알고리즘을 제공하는 시스템 라이브러리가 있는 경우(zlib의 CRC-32와 Adler-32, 나머지는 Greg Cook CRC 카탈로그) 그것과도 대조했습니다.

흔한 실수

파라미터 없는 "CRC-32". ISO-HDLC, BZIP2, MPEG-2, POSIX, CRC-32C 사이에서 같은 이름으로 서로 다른 다섯 값이 유통됩니다. 결과와 함께 항상 poly/init/refin/refout/xorout을 기록하세요 — 이 페이지가 대신 인쇄해 줍니다.
파일의 CRC-32와 cksum 출력 비교. 다른 알고리즘입니다. cksum은 길이를 덧붙이고 다른 init을 씁니다. 숫자는 일치하지 않을 것이고 둘 다 "옳습니다".
변조에 대한 CRC 신뢰. 일치하는 CRC 위조는 교과서 연습입니다(마지막 4바이트 패치). 상대가 적대적일 수 있다면 키가 있는 MAC(HMAC)이나 서명을 쓰세요.
Avalanche 기대. CRC는 선형입니다. 관련된 메시지는 관련된 CRC를 냅니다. 소음에는 괜찮고 해싱에는 틀렸습니다 — 버킷팅이 필요하면 CRC-32보다 CRC-64나 진짜 해시가 안전합니다.
16진 텍스트 vs 바이트. 문자열 "123456789"(ASCII 9바이트, 31 32 33 34 35 36 37 38 39)와 숫자 0x123456789는 다른 CRC를 가진 다른 입력입니다. 원본 데이터가 진짜 바이너리라면 16진 바이트 탭을 쓰세요.

FAQ

제 CRC-32가 ZIP 파일의 것과 왜 안 맞나요? ZIP의 CRC-32는 압축되지 않은 데이터에 대한 ISO-HDLC입니다. 같은 바이트(압축 스트림이 아님), 같은 모드(텍스트 vs 16진), 같은 파라미터 집합으로 계산했는지 확인하세요 — 각 결과 아래 인쇄되는 파라미터 줄이 그 확인을 즉시 만들어 줍니다.

CRC-32C와 CRC-32 중 무엇이 낫나요? 우발적 오류 감지에는 둘 다 32비트까지의 모든 버스트를 잡습니다. CRC-32C는 일부 오류 패턴에서 더 잘 나오고 CPU 명령을 가진 쪽입니다 — 기가비트 속도에서 사실상 무료. CRC-32/ISO-HDLC가 살아남는 이유는 호환성입니다. 30년치 아카이브가 그것을 쓰고 있습니다.

CRC-64가 CRC-32보다 강한가요? 더 긴 버스트(64비트까지)를 감지하고 버킷팅에 쓸 때 충돌이 훨씬 적지만, 위조 가능성은 같습니다 — 폭은 감지 보장을 살 뿐 보안을 사지 않습니다.

CRC를 역방향으로 돌려 입력을 알아낼 수 있나요? 아니요 — 무한히 많은 입력이 하나의 CRC를 공유합니다. 그러나 암호학적 해시와 달리 공격자는 원하는 어떤 CRC를 가진 입력을 구성할 수 있습니다. 일방향이 전혀 아닌 것이 바로 이 의미에서입니다.

CRC 계산기