Программа для расчета контрольной суммы файла crc16
При скачивании ISO образов и архивов больших размеров всегда есть вероятность получить «битый» файл. Во времена Dial-UP такое было сплошь и рядом. И хотя сейчас такое случается намного реже, чтобы убедиться, что перед вами «оригинальный» файл придумали контрольные суммы, которые вычисляются на основе содержимого и позволяют заметить несоответствие даже одного байта.
То есть, если вы измените один байт в проверяемом файле, то и контрольная сумма такого файла так же изменится.
Для чего нужны контрольные суммы
У контрольных сумм две задачи:
- Убедиться, что файл скачался корректно.
- Убедиться, что файл не был изменен злоумышленниками.
Зная контрольную сумму оригинала, можно проверить является ли ваша копия подлинной.
Как вычислить контрольную сумму он-лайн
Контрольную сумму можно проверить он-лайн. Но я не буду рекомендовать этот способ, так как если размер вашего файла несколько ГигаБайт, то это займет много времени и всегда есть вероятность ошибки при передаче файла. Кроме того делиться своими файлами со сторонними сервисами не правильно.
Как узнать контрольную сумму файла в Windows
Разумнее вычислить контрольную сумму локально на своем компьютере. Это быстро и конфиденциально. В этой статье я опишу несколько способов получения контрольных сумм, как с помощью сторонних программ, так и непосредственно с помощью самой операционной системы Виндовс.
Файловый менеджер Total Commander
Total Commander — это популярный файловый менеджер, работающий на платформах Microsoft Windows и Android. В нем есть встроенная функция вычисления контрольных сумм.
После чего вы можете выбрать один из алгоритмом вычисления контрольных сумм.
По-умолчанию Total Commander создает файл с именем проверяемого и с расширением по имени выбранного алгоритма расчета контрольной суммы.
Файловый архиватор 7-Zip
7-Zip — свободный, бесплатный файловый архиватор с высокой степенью сжатия данных. Он поддерживает несколько алгоритмов сжатия и множество форматов данных, включая собственный формат 7z c высокоэффективным алгоритмом сжатия LZMA.
Этот архиватор имеет встроенную функцию вычисления контрольных сумм. Запустить ее можно прямо из контекстного меню Windows:
Если выбрать «звездочку», то программа подсчитает сразу несколько контрольных сумм:
Полученные данные можно выделить и скопировать в текстовый документ.
Как подсчитать контрольную сумму файла из консоли Windows
Чтобы посчитать контрольную сумму совсем не обязательно устанавливать специальные программы. И если вы не пользуетесь упомянутыми выше, то можете рассчитать контрольную сумму прямо из командной строки операционной системы.
Например, чтобы посчитать контрольную сумму SHA1 с помощью утилиты CertUtil нужно запустить командную строку Windows 10, 8 или Windows 7 и ввести следующую команду:
Вот пример ее работы через несколько минут:
Считаем контрольную сумму в PowerShell
PowerShell — это средство автоматизации от Microsoft, с интерфейсом командной строки и языка сценариев, работает и включена в состав Windows 8 и новее.
Чтобы вычислить контрольную сумму файла необходимо выполнить команду Get-FileHash указав через пробел имя файла и алгоритм вычисления контрольной суммы:
Обратите внимание, что полный путь и имя файла лучше заключить в двойные кавычки.
По-умолчанию, если не указать тип контрольной суммы, то будет посчитана SHA-256.
Для алгоритмов вычисления контрольной суммы в Windows PowerShell поддерживаются следующие значения:
- SHA1
- SHA256 (по умолчанию)
- SHA384
- SHA512
- MD5
Для оформления вывода в виде списка можно использовать параметр | Format-List. Например:
Тогда результат работы будет выглядеть так:
Какой алгоритм вычисления контрольных сумм самый правильный
MD5, SHA-1, SHA-256 и прочие – это разные алгоритмы хеш-функции. Хэши являются результатом работы криптографических алгоритмов, и представляют собой строку символов. Часто эти строки имеют фиксированную длину, независимо от размера входных данных.
MD5 самый быстрый, считается устаревшим, а SHA-256 имеет наименьшую вероятность коллизии, когда два разных файла имеют одинаковую контрольную сумму.
Для проверки целостности файла вам следует использовать тот, который предоставляет издатель. Если у вас на выбор есть несколько контрольных сумм, то лучше выбрать в следующей последовательности MD5, SHA-1, SHA-256, последний вариант является более предпочтительным.
Выводы
Если вы сомневаетесь в целостности скаченных файлов из интернета, особенно когда это касается оригинальных образов операционных систем, то проверьте их контрольную сумму. Сделать это можно как с помощью уже имеющихся у вас программ, так и воспользовавшись встроенными средствами операционной системы Windows.
В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разберёмся. А заодно напишем программу, которая будет рассчитывать CRC с заданными параметрами.
1 Теория, лежащая в основе расчёта CRC
Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x 8 + x 2 + x 1 + x 0 . Здесь степень числа "x" означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число – это не что иное как 100000111 в двоичной системе счисления.
Обычно при записи многочлена старший разряд подразумевается, но не пишется. То есть вышеуказанный многочлен можно было бы записать в двоичной системе как (1)00000111. В скобках я указал подразумеваемый старший разряд числа. Поэтому говорят, что многочлен равен 7 в десятичной системе счисления (111b = 7d).
Вот ещё пример: (x 16 +) x 15 + x 2 + x 0 = (1)1000000000000101 = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC. Вот некоторые из них:
Алгоритм CRC | Образующий многочлен |
---|---|
CRC-16 | 0x8005 |
CRC-16-CCITT | 0x1021 |
CRC-16-DNP | 0x3D65 |
CRC-32-IEEE 802.3 | 0x04C11DB7 |
CRC-32C | 0x1EDC6F41 |
CRC-32K | 0x741B8CD7 |
В посвящённой расчёту CRC статье на Википедии есть большая таблица образующих полиномов.
В общем виде деление числа на многочлен выполняется по такому алгоритму. Алгоритм вычисления контрольной суммы CRC:
Назовём этот метод расчёта CRC метод побитового сдвига или простой метод.
Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x 8 + x 2 + x 1 + x 0 .
Схематичное представление вычисления CRC на примере деления на многочлен x 8 + x 2 + x 1 + x 0
Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC можно поделить на какое-то другое число.
Изменение порядка битов в байте на обратный назовём «обращение», «реверс» или «отзеркаливание» байта.
Итого имеются 6 параметров, которые влияют на значение контрольной суммы:
2 Расчёт контрольной суммы CRC методом побитового сдвига
Как вы могли заметить, в данной реализации расчёта CRC используется LINQ , так что соответствующая ссылка должна быть добавлена в проект.
Зато у этой программы есть одно преимущество: она может быть использована для расчёта CRC любого порядка, не обязательно 8, 16 или 32. Это может быть CRC5 или CRC49. Только для чисел больше 32-х разрядов нужно изменить соответствующим образом входные параметры – допустим, poly передавать не как UInteger, а как ULong, или передавать его в виде битового массива (тогда теоретически порядок CRC вообще будет неограничен).
3 Расчёт контрольной суммы CRC табличным методом
Для сокращения числа вычислений из предыдущего метода – метода побитового сдвига – придуманы некоторые оптимизации.
Кроме того, оказывается, что часть расчётов можно провести заранее и записать в массив – таблицу, из которой по мере необходимости будет браться нужное число. Такой метод расчёта назвали табличный метод расчёта CRC.
Я не буду здесь вдаваться в теорию, она довольно сложна и много раз описана в других статьях. В частности, очень хорошее и подробное описание бинарной арифметики, лежащей в основе расчёта CRC, и описание табличного метода, даётся в статье Ross N. Williams: "A Painless Guide to CRC Error Detection Algorithms". Рекомендую к прочтению обязательно! Оригинальный текст – в приложении к статье, а русский перевод легко найти в интернете.
Этот код полностью готов к использованию, можно брать и применять. Пользоваться данной программой так:
Полную и самую последнюю версию кода можно скачать с репозитория на GitHub.
4 «Взлом» контрольной суммы CRC32 и CRC16
Кратко затронем вопрос «взлома» CRC32. И прежде всего давайте определимся с понятием «взлом» применительно к данному вопросу.
Если задача определения контрольной суммы некоторого массива данных – прямая задача, то «взлом» – это обратная задача, а именно: подгонка контрольной суммы под определённый массив данных.
Допустим, вы имеете файл и рассчитали его контрольную сумму. Вам нужно изменить в нём произвольное число байтов, сохранив при этом контрольную сумму. Сделать это совсем не сложно.
Для начала нужно посчитать обычным образом контрольную сумму CRC32, CRC16 или любую другую, какая вам нужна, для этого изменённого файла. Пусть это будет C1. Теперь нужно добавить такое же число нулевых байтов в конец файла, которое содержится в контрольной сумме (для CRC32 – 4 байта, для CRC16 – 2 байта, и т.д.). Можно простым перебором подобрать такое число C2, которое мы и запишем в эти нулевые байты. Ведь понятно, что полный диапазон всех допустимых значений CRC32 укладывается в 2 32 ~ 4,295 млрд. То есть за 4 с небольшим миллиарда итераций расчёта контрольной суммы с начальным содержимым регистра, равным С1, мы брутфорсом («в лоб», методом грубой силы) подберём нужное значение. При современных вычислительных мощностях это не составит проблемы. А уж «взломать» с помощью перебора CRC16 вообще дело нескольких секунд.
Можно ли разместить нулевые байты в середине или начале файла? Можно. К операции XOR применим сочетательный закон: a XOR (b XOR c) = (a XOR b) XOR c, поэтому можно с успехом разбить файл на 3 части: до вставки, после вставки, и сама вставка. Посчитать CRC для первых двух частей (C1 и C2 на иллюстрации), объединить их операцией XOR, заполнить этим числом начальное содержимое регистра, а затем «сбрутфорсить» CRC оставшейся третьей части X.
Есть более интеллектуальный и изящный способ подогнать CRC под нужное значение. Суть его в том, что вместо последовательного перебора всех подряд значений мы «прокручиваем назад» несколько раз (по числу байтов или битов контрольной суммы) наш табличный алгоритм или алгоритм побитового сдвига до тех пор, пока CRC не будет желаемой. На эту тему есть подробные и качественные материалы в сети.
Таким образом, напрашивается вывод: контрольная сумма типа CRC хорошо подходит для проверки целостности данных при случайных искажениях информации в канале передачи данных, но совершенно не подходит для защиты от намеренного взлома.
5 Программа для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8
Интерфейс программы для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8
Содержимое архива "CRC calculator"
Итак, подведём итоги. В этой статье мы:
– узнали, что такое контрольная сумма CRC и какие бывают её виды;
– научились считать CRC методом побитового сдвига и табличным методом;
– узнали алгоритмы «взлома» CRC и сделали вывод об области применимости контрольной суммы типа CRC.
В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разберёмся. А заодно напишем программу, которая будет рассчитывать CRC с заданными параметрами.
1 Теория, лежащая в основе расчёта CRC
Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x 8 + x 2 + x 1 + x 0 . Здесь степень числа "x" означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число – это не что иное как 100000111 в двоичной системе счисления.
Обычно при записи многочлена старший разряд подразумевается, но не пишется. То есть вышеуказанный многочлен можно было бы записать в двоичной системе как (1)00000111. В скобках я указал подразумеваемый старший разряд числа. Поэтому говорят, что многочлен равен 7 в десятичной системе счисления (111b = 7d).
Вот ещё пример: (x 16 +) x 15 + x 2 + x 0 = (1)1000000000000101 = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC. Вот некоторые из них:
Алгоритм CRC | Образующий многочлен |
---|---|
CRC-16 | 0x8005 |
CRC-16-CCITT | 0x1021 |
CRC-16-DNP | 0x3D65 |
CRC-32-IEEE 802.3 | 0x04C11DB7 |
CRC-32C | 0x1EDC6F41 |
CRC-32K | 0x741B8CD7 |
В посвящённой расчёту CRC статье на Википедии есть большая таблица образующих полиномов.
В общем виде деление числа на многочлен выполняется по такому алгоритму. Алгоритм вычисления контрольной суммы CRC:
Назовём этот метод расчёта CRC метод побитового сдвига или простой метод.
Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x 8 + x 2 + x 1 + x 0 .
Схематичное представление вычисления CRC на примере деления на многочлен x 8 + x 2 + x 1 + x 0
Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC можно поделить на какое-то другое число.
Изменение порядка битов в байте на обратный назовём «обращение», «реверс» или «отзеркаливание» байта.
Итого имеются 6 параметров, которые влияют на значение контрольной суммы:
2 Расчёт контрольной суммы CRC методом побитового сдвига
Как вы могли заметить, в данной реализации расчёта CRC используется LINQ , так что соответствующая ссылка должна быть добавлена в проект.
Зато у этой программы есть одно преимущество: она может быть использована для расчёта CRC любого порядка, не обязательно 8, 16 или 32. Это может быть CRC5 или CRC49. Только для чисел больше 32-х разрядов нужно изменить соответствующим образом входные параметры – допустим, poly передавать не как UInteger, а как ULong, или передавать его в виде битового массива (тогда теоретически порядок CRC вообще будет неограничен).
3 Расчёт контрольной суммы CRC табличным методом
Для сокращения числа вычислений из предыдущего метода – метода побитового сдвига – придуманы некоторые оптимизации.
Кроме того, оказывается, что часть расчётов можно провести заранее и записать в массив – таблицу, из которой по мере необходимости будет браться нужное число. Такой метод расчёта назвали табличный метод расчёта CRC.
Я не буду здесь вдаваться в теорию, она довольно сложна и много раз описана в других статьях. В частности, очень хорошее и подробное описание бинарной арифметики, лежащей в основе расчёта CRC, и описание табличного метода, даётся в статье Ross N. Williams: "A Painless Guide to CRC Error Detection Algorithms". Рекомендую к прочтению обязательно! Оригинальный текст – в приложении к статье, а русский перевод легко найти в интернете.
Этот код полностью готов к использованию, можно брать и применять. Пользоваться данной программой так:
Полную и самую последнюю версию кода можно скачать с репозитория на GitHub.
4 «Взлом» контрольной суммы CRC32 и CRC16
Кратко затронем вопрос «взлома» CRC32. И прежде всего давайте определимся с понятием «взлом» применительно к данному вопросу.
Если задача определения контрольной суммы некоторого массива данных – прямая задача, то «взлом» – это обратная задача, а именно: подгонка контрольной суммы под определённый массив данных.
Допустим, вы имеете файл и рассчитали его контрольную сумму. Вам нужно изменить в нём произвольное число байтов, сохранив при этом контрольную сумму. Сделать это совсем не сложно.
Для начала нужно посчитать обычным образом контрольную сумму CRC32, CRC16 или любую другую, какая вам нужна, для этого изменённого файла. Пусть это будет C1. Теперь нужно добавить такое же число нулевых байтов в конец файла, которое содержится в контрольной сумме (для CRC32 – 4 байта, для CRC16 – 2 байта, и т.д.). Можно простым перебором подобрать такое число C2, которое мы и запишем в эти нулевые байты. Ведь понятно, что полный диапазон всех допустимых значений CRC32 укладывается в 2 32 ~ 4,295 млрд. То есть за 4 с небольшим миллиарда итераций расчёта контрольной суммы с начальным содержимым регистра, равным С1, мы брутфорсом («в лоб», методом грубой силы) подберём нужное значение. При современных вычислительных мощностях это не составит проблемы. А уж «взломать» с помощью перебора CRC16 вообще дело нескольких секунд.
Можно ли разместить нулевые байты в середине или начале файла? Можно. К операции XOR применим сочетательный закон: a XOR (b XOR c) = (a XOR b) XOR c, поэтому можно с успехом разбить файл на 3 части: до вставки, после вставки, и сама вставка. Посчитать CRC для первых двух частей (C1 и C2 на иллюстрации), объединить их операцией XOR, заполнить этим числом начальное содержимое регистра, а затем «сбрутфорсить» CRC оставшейся третьей части X.
Есть более интеллектуальный и изящный способ подогнать CRC под нужное значение. Суть его в том, что вместо последовательного перебора всех подряд значений мы «прокручиваем назад» несколько раз (по числу байтов или битов контрольной суммы) наш табличный алгоритм или алгоритм побитового сдвига до тех пор, пока CRC не будет желаемой. На эту тему есть подробные и качественные материалы в сети.
Таким образом, напрашивается вывод: контрольная сумма типа CRC хорошо подходит для проверки целостности данных при случайных искажениях информации в канале передачи данных, но совершенно не подходит для защиты от намеренного взлома.
5 Программа для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8
Интерфейс программы для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8
Содержимое архива "CRC calculator"
Итак, подведём итоги. В этой статье мы:
– узнали, что такое контрольная сумма CRC и какие бывают её виды;
– научились считать CRC методом побитового сдвига и табличным методом;
– узнали алгоритмы «взлома» CRC и сделали вывод об области применимости контрольной суммы типа CRC.
В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разберёмся. А заодно напишем программу, которая будет рассчитывать CRC с заданными параметрами.
1 Теория, лежащая в основе расчёта CRC
Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x 8 + x 2 + x 1 + x 0 . Здесь степень числа "x" означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число – это не что иное как 100000111 в двоичной системе счисления.
Обычно при записи многочлена старший разряд подразумевается, но не пишется. То есть вышеуказанный многочлен можно было бы записать в двоичной системе как (1)00000111. В скобках я указал подразумеваемый старший разряд числа. Поэтому говорят, что многочлен равен 7 в десятичной системе счисления (111b = 7d).
Вот ещё пример: (x 16 +) x 15 + x 2 + x 0 = (1)1000000000000101 = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC. Вот некоторые из них:
Алгоритм CRC | Образующий многочлен |
---|---|
CRC-16 | 0x8005 |
CRC-16-CCITT | 0x1021 |
CRC-16-DNP | 0x3D65 |
CRC-32-IEEE 802.3 | 0x04C11DB7 |
CRC-32C | 0x1EDC6F41 |
CRC-32K | 0x741B8CD7 |
В посвящённой расчёту CRC статье на Википедии есть большая таблица образующих полиномов.
В общем виде деление числа на многочлен выполняется по такому алгоритму. Алгоритм вычисления контрольной суммы CRC:
Назовём этот метод расчёта CRC метод побитового сдвига или простой метод.
Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x 8 + x 2 + x 1 + x 0 .
Схематичное представление вычисления CRC на примере деления на многочлен x 8 + x 2 + x 1 + x 0
Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC можно поделить на какое-то другое число.
Изменение порядка битов в байте на обратный назовём «обращение», «реверс» или «отзеркаливание» байта.
Итого имеются 6 параметров, которые влияют на значение контрольной суммы:
2 Расчёт контрольной суммы CRC методом побитового сдвига
Как вы могли заметить, в данной реализации расчёта CRC используется LINQ , так что соответствующая ссылка должна быть добавлена в проект.
Зато у этой программы есть одно преимущество: она может быть использована для расчёта CRC любого порядка, не обязательно 8, 16 или 32. Это может быть CRC5 или CRC49. Только для чисел больше 32-х разрядов нужно изменить соответствующим образом входные параметры – допустим, poly передавать не как UInteger, а как ULong, или передавать его в виде битового массива (тогда теоретически порядок CRC вообще будет неограничен).
3 Расчёт контрольной суммы CRC табличным методом
Для сокращения числа вычислений из предыдущего метода – метода побитового сдвига – придуманы некоторые оптимизации.
Кроме того, оказывается, что часть расчётов можно провести заранее и записать в массив – таблицу, из которой по мере необходимости будет браться нужное число. Такой метод расчёта назвали табличный метод расчёта CRC.
Я не буду здесь вдаваться в теорию, она довольно сложна и много раз описана в других статьях. В частности, очень хорошее и подробное описание бинарной арифметики, лежащей в основе расчёта CRC, и описание табличного метода, даётся в статье Ross N. Williams: "A Painless Guide to CRC Error Detection Algorithms". Рекомендую к прочтению обязательно! Оригинальный текст – в приложении к статье, а русский перевод легко найти в интернете.
Этот код полностью готов к использованию, можно брать и применять. Пользоваться данной программой так:
Полную и самую последнюю версию кода можно скачать с репозитория на GitHub.
4 «Взлом» контрольной суммы CRC32 и CRC16
Кратко затронем вопрос «взлома» CRC32. И прежде всего давайте определимся с понятием «взлом» применительно к данному вопросу.
Если задача определения контрольной суммы некоторого массива данных – прямая задача, то «взлом» – это обратная задача, а именно: подгонка контрольной суммы под определённый массив данных.
Допустим, вы имеете файл и рассчитали его контрольную сумму. Вам нужно изменить в нём произвольное число байтов, сохранив при этом контрольную сумму. Сделать это совсем не сложно.
Для начала нужно посчитать обычным образом контрольную сумму CRC32, CRC16 или любую другую, какая вам нужна, для этого изменённого файла. Пусть это будет C1. Теперь нужно добавить такое же число нулевых байтов в конец файла, которое содержится в контрольной сумме (для CRC32 – 4 байта, для CRC16 – 2 байта, и т.д.). Можно простым перебором подобрать такое число C2, которое мы и запишем в эти нулевые байты. Ведь понятно, что полный диапазон всех допустимых значений CRC32 укладывается в 2 32 ~ 4,295 млрд. То есть за 4 с небольшим миллиарда итераций расчёта контрольной суммы с начальным содержимым регистра, равным С1, мы брутфорсом («в лоб», методом грубой силы) подберём нужное значение. При современных вычислительных мощностях это не составит проблемы. А уж «взломать» с помощью перебора CRC16 вообще дело нескольких секунд.
Можно ли разместить нулевые байты в середине или начале файла? Можно. К операции XOR применим сочетательный закон: a XOR (b XOR c) = (a XOR b) XOR c, поэтому можно с успехом разбить файл на 3 части: до вставки, после вставки, и сама вставка. Посчитать CRC для первых двух частей (C1 и C2 на иллюстрации), объединить их операцией XOR, заполнить этим числом начальное содержимое регистра, а затем «сбрутфорсить» CRC оставшейся третьей части X.
Есть более интеллектуальный и изящный способ подогнать CRC под нужное значение. Суть его в том, что вместо последовательного перебора всех подряд значений мы «прокручиваем назад» несколько раз (по числу байтов или битов контрольной суммы) наш табличный алгоритм или алгоритм побитового сдвига до тех пор, пока CRC не будет желаемой. На эту тему есть подробные и качественные материалы в сети.
Таким образом, напрашивается вывод: контрольная сумма типа CRC хорошо подходит для проверки целостности данных при случайных искажениях информации в канале передачи данных, но совершенно не подходит для защиты от намеренного взлома.
5 Программа для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8
Интерфейс программы для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8
Содержимое архива "CRC calculator"
Итак, подведём итоги. В этой статье мы:
– узнали, что такое контрольная сумма CRC и какие бывают её виды;
– научились считать CRC методом побитового сдвига и табличным методом;
– узнали алгоритмы «взлома» CRC и сделали вывод об области применимости контрольной суммы типа CRC.
В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разбираться.
- Как просто посчитать контрольную сумму CRC (CRC32 - CRC16 - CRC8)
- Как узнать контрольную сумму файла
- Как проверить контрольную сумму файла
Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x^8 + x^2 + x^1 + x^0. Здесь степень числа "x" означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число - это не что иное как (1)00000111 в двоичной системе счисления, или 7 в десятичной. В скобках я указал подразумеваемый старший разряд числа.
Вот ещё пример: x^16 + x^15 + x^2 + x^0 = (1)1000000000000101" = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC.
Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x^8 + x^2 + x^1 + x^0.
Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC могут делить на какое-то другое число.
Public Shared Function GetCrc(ByVal bytes As Byte(), ByVal poly As UInteger, Optional ByVal width As Integer = 32, Optional ByVal initReg As UInteger = &HFFFFFFFFUI, Optional ByVal finalXor As UInteger = &HFFFFFFFFUI, Optional ByVal reverseBytes As Boolean = True, Optional ByVal reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width \ 8
'Создаём очередь из битов начального заполнения регистра:
Dim initBytes As Byte() = BitConverter.GetBytes(initReg)
Dim initBytesReversed As IEnumerable(Of Byte) = (From b As Byte In initBytes Take widthInBytes).Reverse
Dim initFifo As New Queue(Of Boolean)(width - 1)
For Each b As Byte In initBytesReversed
Dim ba As New BitArray()
If Not reverseBytes Then
For i As Integer = 0 To 7
initFifo.Enqueue(ba(i))
Next
Else
For i As Integer = 7 To 0 Step -1
initFifo.Enqueue(ba(i))
Next
End If
Next
'Сдвиг и XOR:
Dim register As UInteger = 0 'заполняем width-разрядный регистр нулями.
Do While msgFifo.Count > 0
Dim poppedBit As Integer = CInt(register >> (width - 1)) And 1 'определить перед сдвигом регистра.
Dim shiftedBit As Byte = Convert.ToByte(msgFifo.Dequeue)
If initFifo.Count > 0 Then
Dim b As Byte = Convert.ToByte(initFifo.Dequeue)
shiftedBit = shiftedBit Xor b
End If
register = register register = register Or shiftedBit
If poppedBit = 1 Then
register = register Xor poly
End If
Loop
'Финальные преобразования:
Dim crc As UInteger = register 'Регистр содержит остаток от деления == контрольную сумму.
If reverseCrc Then
crc = reflect(crc, width)
End If
crc = crc Xor finalXor
crc = crc And (&HFFFFFFFFUI >> (32 - width)) 'маскируем младшие разряды.
Читайте также: