Длина данных против длины CRC

Question

Я видел 8-битные, 16-битные и 32-битные CRC.

В какой момент мне нужно перейти к более широкому CRC?

Моя внутренняя реакция заключается в том, что она основана на длине данных:

1. 1-100 байт: 8-битный CRC
2. 101 - 1000 байтов: 16-битный CRC
3. 1001 - ??? байт: 32-битный CRC

EDIT: Глядя на страницу Википедии о CRC и ответе Лотта, вот что мы имеем:

<64 байта: 8-битный CRC </p>

<16K байтов: 16-битный CRC </p>

<512M байтов: 32-битный CRC </p>

Answer 1

Это не тема исследования. Это действительно хорошо понято: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Математика довольно проста. 8-битный CRC сводит все сообщения к одному из 256 значений. Если длина вашего сообщения превышает несколько байтов, вероятность того, что несколько сообщений будут иметь одно и то же значение хеш-функции, будет увеличиваться.

Аналогично, 16-битный CRC дает одно из 65 536 доступных значений хеш-функции. Каковы шансы любых двух сообщений, имеющих одно из этих значений?

32-битный CRC дает вам около 4 миллиардов доступных значений хеш-функции.

Из статьи в Википедии: "максимальная общая длина блока равна 2**r − 1". Это в битах. Вам не нужно много изучать, чтобы увидеть, что 2**9 - 1 - это 511 бит. При использовании CRC-8 несколько сообщений длиной более 64 байтов будут иметь одинаковое значение контрольной суммы CRC.

Answer 2

Эффективность CRC зависит от множества факторов. Вам нужно не только выбрать РАЗМЕР CRC, но и ГЕНЕРАТОРНЫЙ ПОЛИНОМ для использования. Есть сложные и не интуитивные компромиссы в зависимости от:

• Ожидаемый коэффициент ошибок по битам канала.
• Независимо от того, возникают ли ошибки в пакетах или имеют тенденцию к распространению (пакет часто встречается)
• Длина данных, которые должны быть защищены - максимальная длина, минимальная длина и распределение.

В статье Филиппа Купмана и Тридиба Чакраварти, опубликованной в материалах Международной конференции по надёжным системам и сетям 2004 года, приводится полиноминальный выбор кода циклического избыточного кода для встраиваемых сетей. Он также предоставляет библиографию для дальнейшего понимания.

http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

Answer 3

Выбор длины CRC в зависимости от размера файла в основном важен в тех случаях, когда один из них с большей вероятностью будет иметь вход, который отличается от «правильного» ввода на три или менее бит, чем тот, который сильно отличается. Учитывая два входа, которые сильно различаются, вероятность ложного совпадения будет около 1/256 с большинством форм 8-битного контрольного значения (включая CRC), 1/65536 с большинством форм 16-битного контрольного значения (включая CRC) и т. д. Преимущество CRC заключается в его обработке входов, которые очень похожи.

В случае 8-битного CRC, полином из которого генерирует два периода длиной 128, доля одиночных, двойных или тройных ошибок в пакете короче, чем те, которые остаются незамеченными, не будет 1/256 - это будет нуль. Аналогично с 16-битным CRC периода 32768 с использованием пакетов 32768 бит или менее.

Однако если пакеты длиннее периода CRC, то двухбитовая ошибка останется незамеченной, если расстояние между ошибочными битами кратно периоду CRC. Хотя это может показаться не очень вероятным сценарием, CRC8 будет несколько хуже при перехвате двухбитовых ошибок в длинных пакетах, чем при перехвате ошибок «пакет полностью зашифрован». Если двухбитовые ошибки являются вторым наиболее распространенным режимом сбоя (после однобитовых ошибок), это будет плохо. Однако, если что-то, что повреждает некоторые данные, может повредить большую их часть, плохое поведение CRC с двухбитовыми ошибками может не являться проблемой.

Answer 4

Вот хорошая оценка "реального мира" CRC-N http://www.backplane.com/matt/crc64.html

Я использую CRC-32 и сравнение размеров файлов и НИКОГДА не проверяю совпадения CRC-32 и File-Size при проверке миллиардов файлов. Но я знаю, что некоторые существуют, когда не намеренно вынуждены существовать. (Взломанные трюки / подвиги)

При выполнении сравнения вы должны также проверять «размеры данных». У вас редко будет коллизия одного и того же размера данных с соответствующим CRC в правильных размерах.

Преднамеренно манипулировать данными, чтобы подделать совпадение, обычно делается путем добавления дополнительных данных до тех пор, пока CRC не достигнет цели. Однако это приводит к тому, что размер данных больше не соответствует. Попытка перебора или циклического перебора случайных или последовательных данных одного и того же точного размера приведет к реальной узкой частоте столкновений.

Вы также можете столкнуться в пределах размера данных, просто с помощью общих ограничений используемых формул и ограничений использования битов / байтов и систем с десятичной базой, которые зависят от значений с плавающей запятой, которые усекаются и обрезаются .

Точка, о которой вы хотели бы подумать о расширении, - это когда вы начинаете видеть множество коллизий, которые нельзя «подтвердить» как «оригиналы». (Когда они оба имеют одинаковый размер данных, и (при тестировании в обратном направлении они имеют соответствующий CRC. Обратный / байтный или обратный / битовый, или смещение битов)

В любом случае его НИКОГДА не следует использовать в качестве ЕДИНСТВЕННОЙ формы сравнения, просто для быстрой формы сравнения, для индексации.

Вы можете использовать CRC-8 для индексации всего интернета и деления всего на одну из N-категорий. Вы ХОТИТЕ тех столкновений. Теперь, с этими предварительно отсортированными, вам нужно только проверить один из N-каталогов, ища «размер файла» или «обратный CRC», или любое другое сравнение, которое вы можете сделать с этим меньшим набором данных, быстро. ..

Выполнение CRC-32 вперед и назад на одном и том же блоке данных более надежно, чем использование CRC-64 только в одном направлении. (Или MD5, если на то пошло.)

Answer 5

CRC следует выбирать специально для длины сообщений, речь идет не просто о размере CRC: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

Answer 6

Я думаю, что размер CRC больше связан с тем, насколько вам нужен уникальный CRC, а не размер входных данных. Это связано с конкретным использованием и количеством предметов, по которым вы рассчитываете CRC.