Tôi đã thấy CRC 8 bit, 16 bit và 32 bit.Chiều dài dữ liệu so với chiều dài CRC
Tại thời điểm nào tôi cần chuyển sang CRC rộng hơn?
phản ứng ruột của tôi là nó được dựa trên độ dài dữ liệu:
EDIT: Nhìn vào trang Wikipedia về CRC và Lott của câu trả lời, đây là những gì chúng ta có:
< 64 byte: 8-bit CRC
< 16K byte: 16-bit CRC
< 512M byte: 32-bit CRC
Đây không phải là chủ đề nghiên cứu. Nó thực sự được hiểu rõ: http://en.wikipedia.org/wiki/Cyclic_redundancy_check
Toán học khá đơn giản. CRC 8 bit bao gồm tất cả thư xuống đến một trong 256 giá trị. Nếu thư của bạn dài hơn vài byte, khả năng nhiều thư có cùng giá trị băm sẽ tăng lên cao hơn và cao hơn.
CRC 16 bit, tương tự, cung cấp cho bạn một trong 65.536 giá trị băm có sẵn. Tỷ lệ cược của hai thông điệp có một trong các giá trị này là bao nhiêu?
CRC 32 bit cung cấp cho bạn khoảng 4 tỷ giá trị băm có sẵn.
Từ bài viết wikipedia: "tổng chiều dài blockle tối đa bằng 2**r − 1". Đó là số bit. Bạn không cần phải nghiên cứu nhiều để thấy rằng 2**9 - 1 là 511 bit. Sử dụng CRC-8, nhiều thư dài hơn 64 byte sẽ có cùng giá trị tổng kiểm tra CRC.
Điều này là chính xác và hữu ích nếu CRC đang được sử dụng để phát hiện các thay đổi đối với tệp. Tuy nhiên, nếu nó đang được sử dụng như một thông báo để phát hiện các bản sao trong các tập tin, thì nó phức tạp hơn. Cụ thể, nghịch lý sinh nhật yêu cầu chúng ta phải tính đến số lượng giá trị khác biệt mà chúng ta mong đợi có. –
@Steven Sudit: Đúng. Đáng buồn là câu hỏi quá mơ hồ để xác định bất cứ điều gì về việc sử dụng CRC. –
Tôi nghĩ rằng * bất kỳ tin nhắn nào cô đơn hơn chiều rộng CRC (r-1 và không phải 2^r-1) sẽ có nhiều thông báo được ánh xạ tới cùng một kiểm tra. IOW, bất kỳ thông báo nào dài hơn một byte, sẽ có ánh xạ CRC8 trùng lặp. Tôi nghĩ (một trong những) thách thức là thiết kế ánh xạ sao cho việc phân phối các chuỗi thông điệp trên băm là thống nhất. – ysap
tôi nghĩ rằng kích thước của CRC có nhiều việc phải làm với cách độc đáo của CRC bạn cần thay vì kích thước của dữ liệu đầu vào. Điều này liên quan đến việc sử dụng cụ thể và số lượng mục mà bạn tính CRC.
CRC nên được lựa chọn đặc biệt cho chiều dài của bài viết, nó không chỉ là một vấn đề kích thước của CRC: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Hiệu quả của một CRC là phụ thuộc vào nhiều yếu tố. Bạn không chỉ cần chọn SIZE của CRC mà còn là GENERATING POLYNOMIAL để sử dụng. Có các giao dịch phức tạp và không trực quan tùy thuộc vào:
Các giấy Cyclic Redundancy Mã Polynominal Selection Đối Networks Embedded, bởi Philip Koopman và Tridib Chakravarty, publised trong quá trình tố tụng của Hội nghị quốc tế năm 2004 về hệ thống tin cậy và Networks đưa ra một cái nhìn tổng quan rất tốt và làm cho một số recomendations. Nó cũng cung cấp một thư mục để hiểu thêm.
http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Sự lựa chọn chiều dài CRC so với kích thước tập tin là chủ yếu có liên quan trong trường hợp một là nhiều khả năng có một đầu vào mà lại khác với "sửa" đầu vào bởi ba hoặc ít bit hơn để có một mà là ồ ạt khác nhau. Với hai đầu vào khác nhau rất lớn, khả năng kết hợp sai sẽ là khoảng 1/256 với hầu hết các dạng giá trị kiểm tra 8 bit (bao gồm CRC), 1/65536 với hầu hết các dạng giá trị kiểm tra 16 bit (bao gồm CRC) , vv Lợi thế của CRC đến từ việc xử lý các yếu tố đầu vào rất giống nhau.
Với CRC 8 bit có đa thức tạo ra hai khoảng thời gian 128, phần bit lỗi đơn, đôi hoặc ba trong gói ngắn hơn không bị phát hiện sẽ không là 1/256 - nó sẽ bằng không. Tương tự như vậy với CRC 16 bit của giai đoạn 32768, sử dụng gói 32768 bit hoặc ít hơn.
Nếu gói dài hơn thời gian CRC, tuy nhiên, lỗi kép bit sẽ không bị phát hiện nếu khoảng cách giữa các bit sai là bội số của khoảng thời gian CRC. Trong khi đó có thể không có vẻ giống như một kịch bản khủng khiếp, một CRC8 sẽ có phần tồi tệ hơn trong việc bắt lỗi đôi bit trong các gói tin dài hơn là bắt các lỗi "gói hoàn toàn bị xáo trộn". Nếu lỗi đôi bit là chế độ lỗi phổ biến thứ hai (sau các lỗi một bit), điều đó sẽ là xấu. Nếu bất cứ điều gì làm hỏng một số dữ liệu có khả năng làm hỏng rất nhiều dữ liệu, tuy nhiên, hành vi kém hơn của CRC với lỗi đôi bit có thể không phải là vấn đề.
Cuộc tấn công MD5 vào cuối năm 2008 là một ví dụ về sách giáo khoa về vấn đề với CRC quá thống nhất hoặc quá nhỏ: http://www.win.tue.nl/hashclash/rogue-ca/ – bzlm
CRC không phải là một thuật toán băm. Đó là một cách để xem liệu một chút đã vô tình bị đảo lộn hay không. Tôi không thấy kết nối với liên kết MD5. Tôi sẽ nhìn lại. – Robert
@bzlm MD5 không liên quan gì đến nó. CRC sẽ không chống lại các cuộc tấn công như vậy cả, chúng được sử dụng để phát hiện các lỗi ngẫu nhiên, không tấn công nguy hiểm. – starblue