Các dòng có dạng “THUẬT_TOÁN giá trị” theo sau là một dòng tham số thụt vào, nên kết quả được sao chép luôn cho biết bộ tham số nào đã tạo ra nó.
CRC — kiểm tra dư thừa vòng, giải thích từ đầu
Trong một câu: CRC coi dữ liệu của bạn như một số nhị phân khổng lồ, chia nó cho một số “sinh” cố định bằng phép XOR thay vì trừ, và báo cáo phần dư — một dấu vân tay gọn thay đổi mạnh khi chỉ một bit đầu vào bị lật, đó là lý do mọi thứ từ tệp PNG đến dây Modbus đều mang một CRC.
CRC thực sự là gì
Hình ảnh phép chia. Xếp các byte của bạn thành một số nhị phân dài. Chọn một số chia — đa thức, ví dụ 0x04C11DB7 cho CRC-32. Thực hiện phép chia nhị phân dài trong đó “phép trừ” là phép XOR: mỗi khi bit đầu của phần dư đang chạy là 1, XOR với số chia, dịch trái, lặp lại. Khi toàn bộ thông điệp đã đi qua, phần còn lại trong thanh ghi chính là CRC. Không có khóa, không có bảng trong định nghĩa — chỉ là phép chia với phần dư.
Năm tham số. Hai hệ thống đều có thể nói “CRC-32” và vẫn bất đồng, vì riêng tên thì không cố định gì cả. Công thức đầy đủ cần năm giá trị: poly (số chia), init (thanh ghi bắt đầu từ đâu — toàn số 0 khiến các byte 0 đứng đầu biến mất, toàn số 1 thì không), refin/refout (mỗi byte đầu vào — và thanh ghi cuối — có bị đảo bit hay không, một di sản của phần cứng nối tiếp gửi bit từ ít quan trọng nhất trước), và xorout (mặt nạ XOR cuối để một chuỗi byte 0 ở cuối vẫn làm thay đổi kết quả). Trang này in cả năm tham số cạnh mỗi kết quả chính vì lý do đó.
Vì sao nó phát hiện lỗi. Một số chia được chọn tốt làm cho phần dư của một thông điệp và phần dư của cùng thông điệp với vài bit bị lật khác nhau với xác suất áp đảo: một CRC-32 tốt bắt được mọi lỗi 1 bit và 2 bit, mọi số lẻ lỗi bit, và mọi chùm tối đa 32 bit bị hỏng liên tiếp — được đảm bảo, không phải theo xác suất. Sự đảm bảo đó là về hỏng ngẫu nhiên, và đó là điều khiến CRC trở thành công cụ đúng cho dây nhiễu và đĩa hỏng.
CRC không phải là gì
Không phải hash mật mã. Không có bí mật và không có tính một chiều: bất kỳ ai biết tham số đều có thể giả mạo một thông điệp với bất kỳ CRC nào họ muốn, trong vài mili giây, bằng cách thêm bốn byte hiệu chỉnh. CRC phát hiện tai nạn, không bao giờ phát hiện kẻ thù. Với tải xuống mà bạn kiểm chứng với người lạ, chữ ký mới quan trọng — xem Bộ tạo hash (MD5/SHA/BLAKE2) thay thế. Trang đó cũng giải thích vì sao MD5 và SHA-1 bị loại bỏ trong môi trường thù địch còn SHA-256 vẫn đứng vững.
Không phải mã sửa lỗi. CRC cho bạn biết có thứ gì đó thay đổi, không phải cái gì đã thay đổi. Sửa lỗi ngay lập tức là việc của các mã như Reed–Solomon hoặc Hamming, chúng cố ý lưu cấu trúc dư thừa mà bộ giải mã có thể đảo ngược.
Không phải nén hay mã hóa. Phần dư là vài byte bất kể kích thước đầu vào, và từ đó bạn không thể khôi phục đầu vào — nhưng khác với hash mật mã, đó chỉ vì thông tin đã bị bỏ đi, không phải vì đảo ngược khó.
Các họ trên trang này
Bộ ba CRC-32. Bốn mục của trang này dùng chung đa thức 0x04C11DB7 nhưng vẫn cho các giá trị khác nhau: ISO-HDLC (đảo, init/xorout toàn số 1) là “CRC-32” của zlib, gzip, PNG và ZIP; BZIP2 là cùng toán học nhưng không đảo; MPEG-2 là BZIP2 không có XOR cuối; POSIX bắt đầu từ số 0 và là nền của lệnh cksum (lệnh này còn thêm độ dài tệp vào phép chia, nên cksum của một tệp và CRC-32/POSIX của cùng byte khác nhau). CRC-32C (Castagnoli, đa thức 0x1EDC6F41) là thành viên thứ năm của họ: một đa thức khác được chọn để phát hiện lỗi tốt hơn, và là loại mà CPU x86 và ARM hiện đại tính được ở tốc độ bộ nhớ chỉ với một lệnh.
Bộ bốn CRC-64. XZ dùng đa thức ECMA-182 ở dạng đảo với init toàn số 1 và xorout; bản ECMA-182 gốc là dạng không đảo, init bằng 0 từ tiêu chuẩn băng DLT-1; GO-ISO là crc64.ISO của Go, đa thức nhỏ 0x1B, vẫn đảo; REDIS dùng một đa thức được chọn để có hiệu ứng tuyết lở tốt trong việc gán slot hash. Sáu mươi bốn bit là kích thước mà CRC bắt đầu được dùng làm hàm băm (phân nhóm) thay vì chỉ là tổng kiểm tra thuần túy.
Adler-32 là kẻ ngoài cuộc: nó hoàn toàn không phải phép chia. Nó cộng các byte (A, bắt đầu từ 1) và cộng các tổng đó (B), cả hai modulo 65521, rồi nối hai tổng 16-bit. Nó nhanh hơn CRC-32 khi chạy bằng phần mềm và zlib dùng nó cho luồng deflate — nhưng với đầu vào ngắn (dưới vài trăm byte) tổng mang quá ít thông tin, đó chính xác là lý do zlib quay lại CRC-32 cho các khối nhỏ.
CRC-8 và CRC-16 còn tồn tại ở nơi byte đắt đỏ: CRC-8/CCITT (đa thức 0x07) bảo vệ từng byte tiêu đề trong các giao thức SMBus và radio di động; CRC-16/CCITT-FALSE bảo vệ các khối thẻ thông minh; CRC-16/MODBUS là tổng kiểm tra của mọi khung Modbus RTU trên các dây chuyền sản xuất khắp thế giới.
Mỗi loại được dùng ở đâu
| Bộ tham số | Được dùng trong |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), nhiều định dạng lưu trữ |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, lệnh CRC32C phần cứng SSE4.2/ARMv8 |
| CRC-32/BZIP2 | Luồng lưu trữ .bz2 |
| CRC-32/MPEG-2 | Luồng truyền tải MPEG-2 |
| CRC-32/POSIX & cksum | Đầu ra lệnh POSIX cksum (cksum file.txt) |
| CRC-16/MODBUS | Khung Modbus RTU (PLC công nghiệp, đồng hồ đo, biến tần) |
| CRC-16/CCITT-FALSE | thẻ thông minh, các liên kết gần X.25, một số giao thức GPS |
| CRC-8/CCITT | SMBus (byte PEC), tiêu đề radio di động |
| CRC-64/XZ | Kiểm tra toàn vẹn container .xz |
| CRC-64/ECMA-182 | Tiêu chuẩn băng ECMA-182 / DLT-1 |
| CRC-64/GO-ISO | Thư viện chuẩn Go crc64.ISO |
| CRC-64/REDIS | Gán slot hash cụm Redis |
| Adler-32 | Luồng zlib (deflate), các ngữ cảnh tổng kiểm tra nhanh khác |
Bảng neo — check(“123456789”)
Quy ước danh mục CRC là công bố kết quả cho chuỗi ASCII 123456789 (9 byte). Mọi giá trị dưới đây đều tái tạo được trên trang này: gõ 123456789 vào ô Văn bản, đánh dấu thuật toán, nhấn Tính.
| Bộ tham số | Độ rộng | Giá trị kiểm tra (hex) |
|---|
| 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 |
Nguồn: mỗi giá trị được đối chiếu chéo bằng một triển khai tham chiếu bit độc lập và, khi có, với thư viện hệ thống có chứa thuật toán đó (zlib cho CRC-32 và Adler-32; danh mục CRC của Greg Cook cho các loại còn lại).
Những lỗi thường gặp
- “CRC-32” không có tham số. Giữa ISO-HDLC, BZIP2, MPEG-2, POSIX và CRC-32C, năm giá trị khác nhau được lưu hành dưới cùng một tên. Luôn ghi poly/init/refin/refout/xorout cùng kết quả — trang này in chúng cho bạn.
- So sánh CRC-32 của một tệp với đầu ra
cksum. Các thuật toán khác nhau: cksum thêm độ dài và dùng init khác. Các con số sẽ không khớp, và cả hai đều “đúng”.
- Tin CRC để chống giả mạo. Giả mạo một CRC khớp là bài tập kinh điển (sửa 4 byte cuối). Dùng MAC có khóa (HMAC) hoặc chữ ký khi bên kia có thể là kẻ thù.
- Kỳ vọng hiệu ứng tuyết lở. CRC là tuyến tính: các thông điệp liên quan cho CRC liên quan. Tốt cho nhiễu, sai cho băm — nếu bạn cần phân nhóm, CRC-64 hoặc một hash thật an toàn hơn CRC-32.
- Văn bản hex so với byte. Chuỗi
"123456789" (9 byte ASCII, 31 32 33 34 35 36 37 38 39) và số 0x123456789 là các đầu vào khác nhau với CRC khác nhau. Dùng tab Byte hex khi dữ liệu nguồn thật sự là nhị phân.
Câu hỏi thường gặp
Vì sao CRC-32 của tôi không khớp với CRC trong tệp ZIP? CRC-32 của ZIP là ISO-HDLC trên dữ liệu chưa nén. Hãy chắc chắn bạn đã băm cùng các byte (không phải luồng đã nén), cùng chế độ (Văn bản hoặc Hex), và cùng bộ tham số — dòng tham số in dưới mỗi kết quả giúp kiểm tra điều này ngay lập tức.
Loại nào tốt hơn, CRC-32C hay CRC-32? Với phát hiện lỗi ngẫu nhiên, cả hai đều bắt được mọi chùm lỗi tối đa 32 bit; CRC-32C hoạt động tốt hơn với một số dạng lỗi và là loại có lệnh CPU riêng — thực tế gần như miễn phí ở tốc độ gigabit. Lý do CRC-32/ISO-HDLC còn tồn tại là tương thích: ba mươi năm lưu trữ dùng nó.
CRC-64 có mạnh hơn CRC-32 không? Nó phát hiện chùm lỗi dài hơn (tối đa 64 bit) và va chạm ít hơn nhiều khi dùng để phân nhóm, nhưng vẫn có thể giả mạo như nhau — độ rộng mua được sự đảm bảo phát hiện, không phải bảo mật.
Có thể đảo ngược CRC để tìm đầu vào không? Không — vô số đầu vào chung một CRC. Nhưng không giống hash mật mã, kẻ tấn công có thể tạo một đầu vào với bất kỳ CRC nào họ chọn, đó là nghĩa mà nó hoàn toàn không một chiều.
