Я видел 8-битные, 16-битные и 32-битные CRC.Длина данных против CRC Длина
В какой момент мне нужно перейти на более широкий CRC?
Моя инстинктивная реакция является то, что она основана на длине данных:
EDIT: Глядя на странице Википедии о правах ребенка и Лотт ответ, вот что мы имеем:
< 64 байта: 8-разрядный CRC
< 16K байт: 16-битный CRC
< 512M байт: 32-битный CRC
Это не тема исследования. Это действительно хорошо понято: 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.
Это точно и полезно, если CRC используется для обнаружения изменений в файле. Однако, если он используется в качестве дайджеста для обнаружения дубликатов среди файлов, то это сложнее. В частности, парадокс дня рождения требует от нас учета того, сколько различных ценностей мы ожидаем иметь. –
@Steven Sudit: Правильно. К сожалению, вопрос слишком расплывчатый, чтобы определить что-либо об использовании КПР. –
Я думаю, что * any * message loner, чем ширина CRC (r-1, а не 2^r-1), будет иметь несколько сообщений, сопоставленных с одной и той же контрольной суммой. IOW, любое сообщение длиной более байта, будет иметь перекрывающиеся CRC8-сопоставления. Я думаю, что (одна из) задача состоит в том, чтобы сконструировать отображение таким образом, чтобы распределение строк сообщений над хэшами было единообразным. – ysap
Я думаю, что размер CRC имеет больше общего с тем, как уникальный требуемого CRC, а не размера входных данных. Это связано с конкретным использованием и количеством элементов, на которых вы вычисляете CRC.
КПР должен быть выбран специально для длины сообщений, это не только вопрос размера CRC: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Эффективность CRC зависит от множества факторов. Вам нужно не только выбрать РАЗМЕР CRC, но и использовать GENERATING POLYNOMIAL. Существуют сложные и неинтуитивные компромиссы в зависимости от:
Бумага циклический избыточный код Выбор Полином для встраиваемых сетей, Филипп Купманом и Tridib Чакраварти, publised в работе Международной конференции по надежным системам и сетям 2004 дает очень хороший обзор и делает несколько Рекомендации. Он также предоставляет библиографию для дальнейшего понимания.
http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Выбор длина CRC по сравнению с размером файла в основном актуально в тех случаях, когда один, скорее всего, есть вход, который отличается от «правильного» входа три или меньшего количества бит, чем иметь один, который существенно отличается. Учитывая два входа, которые существенно различаются, вероятность ложного совпадения будет составлять около 1/256 при большинстве форм 8-битного контрольного значения (включая CRC), 1/65536 с большинством форм 16-битной контрольной величины (включая CRC) и т. д. Преимущество CRC происходит от его обработки входов, которые очень похожи.
С 8-разрядным CRC, полином которого генерирует два периода длины 128, доля одиночных, двойных или трехкратных ошибок в пакете короче, чем тот, который не обнаружен, не будет 1/256 - он будет равна нулю. Аналогично, с 16-битным CRC периода 32768, используя пакеты 32768 бит или меньше.
Если пакеты больше, чем период CRC, то двухбитовая ошибка будет не обнаружена, если расстояние между ошибочными битами будет кратно периоду CRC. Хотя это может показаться не очень вероятным сценарием, CRC8 будет несколько хуже в улавливании двойных битовых ошибок в длинных пакетах, чем при улавливании «пакетов полностью скремблированных» ошибок. Если двубитовые ошибки являются вторым наиболее распространенным режимом отказа (после однобитовых ошибок), это было бы плохо. Однако, если что-либо, что искажает некоторые данные, скорее всего, повредит многие из них, низкое поведение CRC с двубитными ошибками может быть проблемой без проблем.
Атака MD5 в конце 2008 года представляет собой пример учебника проблемы с CRC, который является слишком однородным или слишком маленьким: http://www.win.tue.nl/hashclash/rogue-ca/ – bzlm
CRC не является алгоритм хэширования. Это способ увидеть, случайно ли было перевернуто. Я не вижу связи с ссылкой MD5. Я еще раз посмотрю. – Robert
@bzlm MD5 не имеет к этому никакого отношения. CRC не будут противостоять таким атакам вообще, они используются для обнаружения случайных ошибок, а не для злонамеренных атак. – starblue