Что такое crc32 в winrar

Как посчитать контрольную сумму CRC32, CRC16, CRC8

В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разберёмся. А заодно напишем программу, которая будет рассчитывать CRC с заданными параметрами.

1 Теория, лежащая в основе расчёта CRC

Но такой способ определения наличия ошибок – очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более «продвинутых» проверок, в том числе CRC.

По сути, CRC – это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее – остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют «контрольная сумма». В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.

Что такое исходное сообщение – понятно. Это непрерывная последовательность битов произвольной длины.

Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту – 8, 16 или 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.

Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: 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. Для начала мы рассмотрим именно базовый метод.

В общем виде деление числа на многочлен выполняется по такому алгоритму. Алгоритм вычисления контрольной суммы CRC:

1. Создаётся массив (регистр), заполненный нулями, равный по длине разрядности (степени) полинома.
2. Исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома.
3. В младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит.
4. Если выдвинутый бит равен «1», то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме.
5. Если в сообщении ещё есть биты, переходим к шагу 3).
6. Когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.

Назовём этот метод расчёта CRC метод побитового сдвига или простой метод.

Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x 8 + x 2 + x 1 + x 0 .

Схематичное представление вычисления CRC на примере деления на многочлен x 8 + x 2 + x 1 + x 0

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

Осталась ещё пара моментов, о которых стоит сказать. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.

Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число. (И это рекомендуется делать: так повышается надёжность определения начала передачи сообщения, если, например, сообщение имеет в начале нулевые биты).

Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC можно поделить на какое-то другое число.

И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом «вперёд», так и наоборот, младшим. И результирующая CRC также может выдаваться, начиная со старшего бита или с младшего.

Изменение порядка битов в байте на обратный назовём «обращение», «реверс» или «отзеркаливание» байта.

Итого имеются 6 параметров, которые влияют на значение контрольной суммы:

• порядок CRC;
• образующий многочлен (его иногда называют «генераторный полином», переводя с английского буквально);
• начальное содержимое регистра;
• значение, с которым производится финальное XOR;
• реверс байтов информационного сообщения;
• реверс байтов CRC перед финальным XOR.

2 Расчёт контрольной суммы CRC методом побитового сдвига

На основании всего вышеизложенного, давайте напишем функцию на языке Visual Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.

Код расчёта CRC методом побитового сдвига на языке VB.NET

Как вы могли заметить, в данной реализации расчёта CRC используется LINQ , так что соответствующая ссылка должна быть добавлена в проект.

Предлагаемая программа плохо масштабируема. То есть она работает хорошо при вычислении контрольной суммы CRC для коротких сообщений, длиной до нескольких десятков килобайтов. Я писал её с целью только продемонстрировать работу простого алгоритма, и не занимался оптимизацией. При расчёте CRC для длинного сообщения, размером десятки или сотни мегабайтов, программа будет сильно загружать процессор и память, т.к. всё сообщение целиком загружается в очередь. Этому способствует метод преобразования числа в битовую последовательность, используя Queue(Of Boolean). Для работы с такими большими сообщениями желательно реализовать промежуточный буфер, который будет передавать сообщение в программу небольшими порциями.

Зато у этой программы есть одно преимущество: она может быть использована для расчёта CRC любого порядка, не обязательно 8, 16 или 32. Это может быть CRC5 или CRC49. Только для чисел больше 32-х разрядов нужно изменить соответствующим образом входные параметры – допустим, poly передавать не как UInteger, а как ULong, или передавать его в виде битового массива (тогда теоретически порядок CRC вообще будет неограничен).

3 Расчёт контрольной суммы CRC табличным методом

Для сокращения числа вычислений из предыдущего метода – метода побитового сдвига – придуманы некоторые оптимизации.

В частности, сдвигают не по одному биту за раз, а сразу по несколько. Наибольшую популярность снискали варианты, в которых сообщение сдвигается на число битов, кратное числу битов в байте: 8, 16 или 32, т.к. с байтами легче работать (не нужны дополнительные преобразования). При этом идея алгоритма осталась та же: сдвиг и исключающее ИЛИ с содержимым регистра.

Кроме того, оказывается, что часть расчётов можно провести заранее и записать в массив – таблицу, из которой по мере необходимости будет браться нужное число. Такой метод расчёта назвали табличный метод расчёта CRC.

Я не буду здесь вдаваться в теорию, она довольно сложна и много раз описана в других статьях. В частности, очень хорошее и подробное описание бинарной арифметики, лежащей в основе расчёта CRC, и описание табличного метода, даётся в статье Ross N. Williams: «A Painless Guide to CRC Error Detection Algorithms». Рекомендую к прочтению обязательно! Оригинальный текст – в приложении к статье, а русский перевод легко найти в интернете.

Ну что же, пришло время для самой программы. Она будет несколько длиннее предыдущей. По сути, это реализация алгоритма из указанной статьи в стиле объектно-ориентированного программирования. Опять же будем писать программу на моём любимом языке программирования VB.NET. Я назвал этот класс RocksoftCrcModel, по названию компании, в которой работал автор указанной статьи.

Код расчёта CRC табличным методом на языке VB.NET

Этот код полностью готов к использованию, можно брать и применять. Пользоваться данной программой так:

• создать экземпляр класса RocksoftCrcModel(), передав в конструктор параметры модели CRC;
• для расчёта контрольной суммы, вызвать метод данного объекта ComputeCrc() или ComputeCrcAsBytes(), передав в качестве параметра информационное сообщение, для которого необходимо посчитать контрольную сумму;
• если меняются параметры модели CRC, таблица автоматически пересчитывается, и новый экземпляр класса можно не создавать.

Приведу пример использования данного класса для алгоритма CRC16. В качестве сообщения message будем использовать массив байтов, который представляет собой строку «123456789» в коде ASCII, которая используется во многих онлайн-калькуляторах CRC:

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

Для любителей C# перепишем данный класс таким образом:

Код расчёта CRC табличным методом на языке C# (разворачивается)

Данная программа на C# не тестировалась мной, в отличие от предыдущей, написанной на VB.NET. Этот код получен через декомпиляцию предыдущего. Если в нём обнаружатся какие-то ошибки, то пишите в комментариях или мне на почту, исправлю.

Прикладываю к статье полностью рабочий и готовый к использованию файл RocksoftCrcModel.vb с реализацией расчёта контрольной суммы CRC, который мы тут рассмотрели, а также RocksoftCrcModel.cs на C#.

Полную и самую последнюю версию кода можно скачать с репозитория на 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 . Внешний вид окна приведён на рисунке. Программа работает под ОС Windows и требует .NET версии 3.5 .

Интерфейс программы для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8

Программа позволяет рассчитывать CRC массива байтов (введённого в поле «Сообщение») или указанного файла. Все рассмотренные выше параметры контрольной суммы настраиваются через интерфейс программы.

Ну и напоследок выкладываю ссылки на архив, в архиве лежат: программа «Калькулятор CRC», оригинальная статья «A Painless Guide to CRC Error Detection Algorithms», класс RocksoftCrcModel() на Visual Basic.NET и на C#.

Содержимое архива «CRC calculator»

Итак, подведём итоги. В этой статье мы:
– узнали, что такое контрольная сумма CRC и какие бывают её виды;
– научились считать CRC методом побитового сдвига и табличным методом;
– узнали алгоритмы «взлома» CRC и сделали вывод об области применимости контрольной суммы типа CRC.

Что такое CRC?

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

Расшифровывается эта аббревиатура как cyclic redundancy check, или, говоря по-русски, циклический избыточный код. Может показаться, что за таким сложным и громоздким названием кроется что-то очень сложное, но на самом деле, с точки зрения конечного пользователя, всё предельно просто. CRC — это просто контрольное значение, которое способно служить подтверждением целостности данных.

Ключи CRC могут быть разной длины. Как правило, наиболее широко используются 16-, 32- и 64-битные ключи. Впрочем, также достаточно часто применяются и ключи другой длины — например, 12-битные. Существует множество различных алгоритмов вычисления CRC, которые, кстати, как ни странно, до сих пор до конца не стандартизованы. По сути, все алгоритмы заключаются в делении с остатком многочлена, соответствующего входным данным, на некоторый заранее известный делитель. Степень полинома, генерируемого из входных данных, должна быть равна длине контрольной суммы, то есть, например, при использовании CRC16 нужно генерировать многочлен 16-й степени.

Суть использования CRC заключается в том, что вероятность получения точно такого же CRC при какой-либо перестановке в исходных данных исчезающе мала, то есть, фактически, в обычной жизни CRC стопроцентно гарантирует сохранность и уникальность полученных данных. Например, вероятность того, что случайно измененные данные будут иметь такое же CRC, как и исходные, в случае с использованием 64-битной контрольной суммы будет равна 5•10 -20 .

Контрольная сумма файла: что это такое и как проверить

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

Что такое контрольная сумма

Контрольная сумма или хеш-сумма – это значение, которое было рассчитано по некоторому алгоритму на основе имеющихся файлов или данных. Особенностью контрольной суммы является то, что ее алгоритм, при одинаковых входных данных всегда выдает одинаковое значение. При этом малейшее изменение входных данных кардинально меняет значение контрольной суммы.

Эта особенность позволяет использовать контрольную сумму для проверки целостности файлов или данных. Например, вам нужно отправить какой-то файл, и вы хотите убедиться, что он не будет поврежден или изменен на своем пути к получателю. Для решения этой задачи можно использовать контрольную сумму. Высчитываете контрольную сумму и отправляете ее вместе с файлом. После чего получатель файла повторно высчитывает контрольную сумму файла и сравнивает ее с вашей контрольной суммой. Если значения совпадают, значит файл оригинальный, если нет, значит он получил какие-то изменения.

Также нужно упомянуть, что контрольную сумму нельзя использовать для получения исходных данных. То есть нельзя «расшифровать» хеш-сумму и получить данные которые были хешированы, хеш-сумму можно только сравнить с другой хеш-суммой. Это особенность открывает дополнительные возможности. Например, хеш-суммы используются для хранения паролей. Когда вы регистрируетесь на каком-то сайте и вводите свой пароль, то он не хранится на сервере в открытом виде. Вместо этого хранится только его контрольная сумма. А когда вы входите в свой аккаунт с использованием пароля, система получается ваш пароль, высчитывает его хеш-сумму и сравнивает с хеш-суммой, которая хранится на сервере. Если хеш-суммы совпали, значит пароль верный и вы можете войти в аккаунт, если хеш-суммы не совпадают, значит пароль не верный и вас перенаправляют на страницу для восстановления пароля.

Для высчитывания контрольной суммы существует множество различных алгоритмов или так называемых хеш-функций. Самыми известными и популярными алгоритмы являются: CRC32, MD5, SHA-1 и SHA-2. Но, есть и множество других алгоритмов, некоторые из которых имеют широкое применения, а некоторые используются только для специфических задач. При этом часть существующих алгоритмов признаны устаревшими или уязвимыми и больше не используются. Так, алгоритм MD5 практически полностью перестал использоваться поскольку выяснилось, что он может выдавать одинаковые значения для разных входных значений.

Для примера продемонстрируем, как выглядит контрольная сумма на практике. Например, возьмем строку «Hello, world!» и высчитаем ее контрольную сумму с использованием нескольких популярных алгоритмов.

Как видно, каждый алгоритм выдает значение, которое не имеет совершенно ничего общего с исходными данными. И сколько раз мы бы не высчитывали контрольную сумму строки «Hello, world!», мы каждый раз будем получать одни и те же значения.

Проверка контрольных сумм онлайн

Если нужно проверить контрольную сумму какой-то строки (например, пароля), то проще всего воспользоваться онлайн сервисами. Найти такие онлайн сервисы можно в любом поисковике по запросу «hash online».

Для примера рассмотрим сайт http://www.sha1-online.com. На этом сайте есть строка, в которую нужно ввести исходные данные, и выпадающий список, где нужно выбрать какой алгоритм вы хотите использовать для получения хеш-суммы.

Чтобы проверить приведенную выше таблицу введем строку «Hello, world!», выберем алгоритм MD5 и нажмем на кнопку «hash».

В результате на экране появится строка со значением хеш-функции MD5.

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

Проверка контрольной суммы файла

Если вам нужно проверить контрольную сумму файла (например, образа диска или программы), то вам понадобится специальная программа, которая умеет высчитывать контрольные суммы. Самой популярной программой такого рода является HashTab.

После установки данной программы в свойствах файла появится новая вкладка «Хеш-суммы файлов», в которой будет отображаться хеш-сумма выбранного вами файла.

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

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

Также HashTab позволяет сравнивать файлы. Для этого нужно нажать на кнопку «Сравнить файл» и выбрать другой файл.

Программа HashTab является бесплатной для личного пользования, некоммерческих организаций и студентов. Скачать программу можно на официальном сайте http://implbits.com/products/hashtab/.

• Чем открыть MDF файл в Windows 7 или Windows 10
• Чем открыть mkv
• Чем открыть fb2
• Как отправить файл большого размера
• Массовое переименование файлов

Создатель сайта comp-security.net, автор более 2000 статей о ремонте компьютеров, работе с программами, настройке операционных систем.

Задайте вопрос в комментариях под статьей или на странице «Задать вопрос» и вы обязательно получите ответ.

How to calculate CRC of a WinRAR file?

I know CRC calculation algorithm from Wikipedia. About structure of RAR file I read here. For example, there was written:

The file has the magic number of:

Which is a break down of the following to describe an Archive Header:

If I understand correctly, the HEAD_CRC (0x6152) is CRC value of Marker Block (MARK_HEAD). Somewhere I read, that CRC of a WinRAR file is calculated with standard polynomial 0xEDB88320, but when size of CRC is less than 4 bytes, it’s necessary to use less significant bytes. In this case (of course if I undestand correctly) CRC value is 0x6152, so it has 2 bytes. Now I don’t know, which bytes I have to take as less significant. From the standard polynomial (0xEDB88320)? Then 0x8320 probably are less significant bytes of this polynomial. Next, how to calculate CRC of the Marker Block (i. e. from the following bytes: 0x 52 61 72 21 1A 07 00), if we have already right polynomial?

2 Answers 2

There was likely a 16-bit check for an older format that is not derived from a 32-bit CRC. The standard 32-bit CRC, used by zip and rar, applied to the last five bytes of the header has no portion equal to the first two bytes. The Polish page appears to be incorrect in claiming that the two-byte check is the low two-bytes of a 32-bit CRC.

It does appear from the documentation that that header is constructed in a standard way as other blocks in the older format, so that the author, for fun, arranged for his format to give the check value «Ra» so that it could spell out «Rar!» followed by a text-terminating control-Z.

I found another 16-bit check in the unrar source code, but that check does not result in those values either.

Oh, and no, you can’t take part of a CRC polynomial and expect that to be a good CRC polynomial for a smaller check. What the page in Polish is saying is that you would compute the full 32-bit CRC, and then take the low two bytes of the result. However that doesn’t work for the magic number header.