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

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

Предположим, у вас есть увесистый дистрибутив софта в формате .iso, гигабайт на 5, например, и вы хотите передать его через сеть партнеру. Вы загружаете его на FTP сервер и даете ссылку партнеру, мол «На, скачивай, дружище!». Ваш партнер скачивает его и работает с ним. Думаете этого достаточно? Нет. Сейчас объясним почему.

Зачем сверять контрольную сумму?

Дело в том, что при загрузке файла из сети файл может прилететь к вам побитым. Да –да, вы не ослышались. Любой .iso это так или иначе, набор блоков данных. И при скачивании, а особенно по нестабильному FTP, он может «крашнуться».

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

1. Владелец файла считает контрольную сумму рабочего файла (по MD5, например);
2. Загружает файл на публичное хранилище и передает контрольную сумму получателю файла;
3. Получатель файла скачивает файл, считает его контрольную сумму на своей стороне и сверяет ее с оригинальной, которую посчитал владелец файла;
4. Получатель и Владелец кидают смешные стикеры в Telegram друг другу из стикерпака про лягушку Пепе.

Как работает контрольная — простым языком

Контрольная сумма — результат некой хэш – функции. Запомнили. Далее, что такое хэш – функция? Это функция, которая получает на вход массив данных, «прокручивает» эти данные по определенному алгоритму и дает на выходе битовую строку, длина которой задана заранее.

Не вдаваясь в подробности сложных алгоритмов, так это и работает:

1. Массив данных на вход (файл);
2. Магия внутри;
3. Контрольная сумма на выходе!

Как рассчитать контрольную сумму?

Будем использовать криптографическую функцию MD5. Скачиваем утилиту WinMD5Sum по ссылке: https://sourceforge.net/projects/winmd5sum/. Установите ее и идем дальше.

Итак, вот мой заветный дистрибутив. Лежит в папке:

Запускаем WinMD5Sum:

Тут все предельно просто. Просто в поле File Name выбираем наш дистрибутив и нажимаем кнопку Calculate.

Зачастую, как только вы выберите файл в поле File Name через кнопку поиску (три точки), то подсчет хэша начнется без нажатия на кнопку Calculate.

Огонь. Копируйте значение из поля MD5 Sum и сохраняйте себе отдельно. Теперь, по легенде, мы берем этот файл и отправляем другу/партнеру/коллеге. Выкладываем файл на FTP, а контрольную сумму передаем ему отдельно – по смс, емаил, в чате. Далее, давайте рассмотрим процесс с точки зрения получателя файла.

Как сверить контрольную сумму?

Мы получили файл и его контрольную сумму. Как ее проверить? Все так же, как и при расчете контрольной суммы! Сначала считаем контрольную сумму скачанного файла:

С одним лишь отличием. Теперь мы берем контрольную сумму которая была посчитана ранее, вставляем ее в поле Compare и нажимаем кнопку Compare:

Вот и все. Наша контрольная сумма совпала, а это значит, что файл во время загрузки поврежден не был. Иначе, мы бы получили вот такое значение:

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

Алгоритм MD5 Message-Digest, широко используемая криптографическая хэш-функция, которая создает 128-битное (16-байтовое) хеш-значение, используя для обеспечения полной и последовательной передачи информации.

MD5 был разработан американским криптографом Рональдом Линном Ривестом и опубликован в 1992 году для замены алгоритма MD4. Процедура для этого алгоритма указана в RFC 1321. (например, фрагмент текста) операция становится другой фиксированной длины значение, которое является основным принципом алгоритмов хеширования.

Что может онлайн-инструмент расчета MD5?

• Онлайн-расчет значения файла MD5

Будет ли файл сохранен нашим сайтом?

• Процесс расчета онлайн-инструмента расчета запускается в вашем браузере и не будет загружен на наш веб-сайт, пожалуйста, используйте его с уверенностью.

Как использовать?

• 1) Нажмите, чтобы выбрать файл и дождитесь завершения расчета
• 2) Нажмите кнопку Копировать

Сравнение функций семейства SHA

Сравнение функций семейства SHA

Алгоритмы и их варианты		Длина вывода (bit)	Размер внутреннего состояния (bit)	Размер блока (bit)	Максимальная длина сообщения (bit)	Цикл	Операция	Безопасность (bit)	Производительность MiB/s)
MD5 (Для справки)		128	128 (4 × 32)	512	2 64 − 1	64	Побитовое И, побитовое исключающее ИЛИ, циклический сдвиг, заполнение(Модуль 2 32 ), Побитовое ИЛИ	(Обнаружено столкновение)	335
SHA-0		160	160 (5 × 32)	512	2 64 − 1	80	Побитовое И, побитовое исключающее ИЛИ, циклический сдвиг, заполнение(Модуль 2 32 ), Побитовое ИЛИ	(Обнаружено столкновение)	—
SHA-1		160	160 (5 × 32)	512	2 64 − 1	80		(Обнаружено столкновение )	192
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	2 64 − 1	64	Побитовое И, побитовое исключающее ИЛИ, циклический сдвиг, заполнение(Модуль 2 32 ), Побитовое ИЛИ, Сдвиг	Да 112/128	139
	SHA-384 SHA-512 SHA-512/224 SHA-512/256	384 512 224 256	512 (8 × 64)	1024	2 128 − 1	80	Побитовое И, побитовое исключающее ИЛИ, циклический сдвиг, заполнение(Модуль 2 64 ), Побитовое ИЛИ, Сдвиг	Да 192/256/112/128	154
SHA-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	Неограниченно	24	Побитовое И, побитовое исключающее ИЛИ, циклический сдвиг, отрицание	Да 112/128/192/256	—
	SHAKE128 SHAKE256	d (Переменная длина) d (Переменная длина)		1344 1088				Да min (d/2, 128) min (d/2, 256)	—

Copyright © 2024 StrErr

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

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

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

Для начала давайте немного разберёмся в теории. Итак, что же такое CRC ? Если кратко, это одна из разновидностей подсчёта контрольной суммы. Контрольная сумма – это метод проверки целостности принятой информации на стороне приёмника при передаче по каналам связи. Например, одна из простейших проверок – использование бита чётности. Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной – то 1. При приёме также подсчитывается сумма битов сообщения, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче возникли ошибки, и передаваемая информация была искажена.

Но такой способ определения наличия ошибок – очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более «продвинутых» проверок, в том числе 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-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. Создаётся массив (регистр), заполненный нулями, равный по длине разрядности (степени) полинома.
2. Исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома.
3. В младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит.
4. Если выдвинутый бит равен «1», то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме.
5. Если в сообщении ещё есть биты, переходим к шагу 3).
6. Когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.

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

Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен 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, рассчитанную методом побитового сдвига. '''
 ''' Входная последовательность байтов (исходное сообщение). ''' Образующий многочлен разрядности width. ''' Порядок CRC в битах, 8/16/32. Public Shared Function GetCrc_Simple(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 'Дополняем сообщение width нулями (расчёт в байтах): ReDim Preserve bytes(bytes.Length - 1 + widthInBytes) 'Создаём очередь битов из сообщения: Dim msgFifo As New Queue(Of Boolean)(bytes.Count * 8 - 1) For Each b As Byte In bytes Dim ba As New BitArray() If reverseBytes Then For i As Integer = 0 To 7 msgFifo.Enqueue(ba(i)) Next Else For i As Integer = 7 To 0 Step -1 msgFifo.Enqueue(ba(i)) Next End If Next 'Создаём очередь из битов начального заполнения регистра: 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 > (32 - width)) 'маскируем младшие разряды. Return crc End Function ''' 
''' Обращает заданное число младших битов переданного числа. '''
 ''' Число, которое требуется «отзеркалить». ''' Сколько младших битов обратить, 0..32. ''' ''' Например: reflect(&H3E23, 3) == &H3E26. Private Shared Function reflect(ByVal inpValue As UInteger, Optional ByVal bitsToReflect As Integer = 32) As UInteger Dim t As UInteger = inpValue Dim reflected As UInteger = inpValue For i As Integer = 0 To bitsToReflect - 1 Dim bm As UInteger = bitMask(bitsToReflect - 1 - i) If (t And 1) = 1 Then reflected = reflected Or bm Else reflected = reflected And Not bm End If t >>= 1 Next Return reflected End Function ''' 
''' Возвращает наибольший разряд числа. '''
 ''' Число, разрядность которого следует определить. ''' Private Shared Function bitMask(ByVal number As Integer) As UInteger Dim res As UInteger = (1UI End Function 

Как вы могли заметить, в данной реализации расчёта 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

''' 
''' Реализует алгоритм расчёта CRC методом Rocksoft^tm Model CRC. '''
 Public Class RocksoftCrcModel #Region "PROPS AND FIELDS" ''' 
''' Таблица предвычисленных значений для расчёта контрольной суммы. '''
 Public ReadOnly CrcLookupTable(255) As UInteger ''' 
''' Порядок CRC, в битах (строго 8, 16 или 32). ''' Изменение этого свойства ведёт к пересчёту таблицы. '''
 Public Property CrcWidth As Integer Get Return _CrcWidth End Get Set(value As Integer) If _CrcWidth <> value Then _CrcWidth = value _TopBit = getBitMask(_CrcWidth - 1) _WidMask = (((1UI ''' Образующий многочлен. ''' Изменение этого свойства ведёт к пересчёту таблицы. ''' Public Property Polynom As UInteger Get Return _Polynom End Get Set(value As UInteger) If _Polynom <> value Then _Polynom = value generateLookupTable() End If End Set End Property Private _Polynom As UInteger = &H4C11DB7 ''' 
''' Обращать ли байты сообщения? ''' Изменение этого свойства ведёт к пересчёту таблицы. '''
 Public Property ReflectIn As Boolean Get Return _ReflectIn End Get Set(value As Boolean) If _ReflectIn <> value Then _ReflectIn = value generateLookupTable() End If End Set End Property Private _ReflectIn As Boolean = True ''' 
''' Начальное содержимое регистра. '''
 Public Property InitRegister As UInteger Get Return _InitRegister End Get Set(value As UInteger) If _InitRegister <> value Then _InitRegister = value End If End Set End Property Private _InitRegister As UInteger = &HFFFFFFFFUI ''' 
''' Обращать выходное значение CRC? '''
 Public Property ReflectOut As Boolean Get Return _ReflectOut End Get Set(value As Boolean) If _ReflectOut <> value Then _ReflectOut = value End If End Set End Property Private _ReflectOut As Boolean = True ''' 
''' Значение, с которым XOR-ится выходное значение CRC. '''
 Public Property XorOut As UInteger Get Return _XorOut End Get Set(value As UInteger) If _XorOut <> value Then _XorOut = value End If End Set End Property Private _XorOut As UInteger = &HFFFFFFFFUI #End Region '/PROPS AND FIELDS #Region "READ-ONLY PROPS" ''' 
''' Возвращает старший разряд полинома. '''
 ReadOnly Property TopBit As UInteger Get Return _TopBit End Get End Property Private _TopBit As UInteger = getBitMask(CrcWidth - 1) ''' 
''' Возвращает длинное слово со значением (2^width)-1. '''
 Private ReadOnly Property WidMask As UInteger Get Return _WidMask End Get End Property Private _WidMask As UInteger = (((1UI ''' Конструктор, инициализированный параметрами по умолчанию для алгоритма CRC32. ''' Public Sub New() generateLookupTable() End Sub ''' 
''' Инициализирует новый экземпляр параметрической модели CRC с настраиваемыми параметрами. '''
 ''' Разрядность контрольной суммы в битах. ''' Полином. ''' начальное содержимое регистра. ''' Обращать ли входящие байты сообщения? ''' Обратить ли CRC перед финальным XOR. ''' Конечное значение XOR. Public Sub New(ByVal width As Integer, ByVal poly As UInteger, Optional ByVal initReg As UInteger = &HFFFFFFFFUI, Optional ByVal isReflectIn As Boolean = True, Optional ByVal isReflectOut As Boolean = True, Optional ByVal xorOut As UInteger = &HFFFFFFFFUI) Me.CrcWidth = width Me.Polynom = poly Me.InitRegister = initReg Me.ReflectIn = isReflectIn Me.ReflectOut = isReflectOut Me.XorOut = xorOut generateLookupTable() End Sub #End Region '/CTOR #Region "ВЫЧИСЛЕНИЕ CRC" ''' 
''' Вычисляет значение контрольной суммы переданного сообщения. '''
 ''' Исходное сообщение, для которого нужно посчитать контрольную сумму. Public Function ComputeCrc(ByRef message As Byte()) As UInteger Dim registerContent As UInteger = InitRegister 'Содержимое регистра в процессе пересчёта CRC. For Each b As Byte In message registerContent = getNextRegisterContent(registerContent, b) Next Dim finalCrc As UInteger = getFinalCrc(registerContent) Return finalCrc End Function ''' 
''' Вычисляет значение контрольной суммы переданного сообщения и возвращает его в виде массива байтов. '''
 ''' Исходное сообщение, для которого нужно посчитать контрольную сумму. Public Function ComputeCrcAsBytes(ByRef message As Byte()) As Byte() Dim crc As UInteger = ComputeCrc(message) Dim crcBytes As Byte() = BitConverter.GetBytes(crc) Dim crcBytesOrdered(crcBytes.Length - 1) As Byte For i As Integer = 0 To crcBytes.Length - 1 crcBytesOrdered(i) = crcBytes(crcBytes.Length - 1 - i) Next Return crcBytesOrdered End Function ''' 
''' Обрабатывает один байт сообщения (0..255). '''
 ''' Содержимое регистра на предыдущем шаге. ''' Значение очередного байта из сообщения. Private Function getNextRegisterContent(ByVal prevRegContent As UInteger, ByVal value As Byte) As UInteger Dim uValue As UInteger = value If ReflectIn Then uValue = reflect(uValue, 8) End If Dim reg As UInteger = prevRegContent reg = reg Xor (uValue End Function ''' 
''' Возвращает значение CRC для обработанного сообщения. '''
 ''' Значение регистра до финального обращения и XORа. Private Function getFinalCrc(ByVal regContent As UInteger) As UInteger If ReflectOut Then Dim res As UInteger = XorOut Xor reflect(regContent, CrcWidth) Return res Else Dim res As UInteger = XorOut Xor regContent Return res End If End Function #End Region '/ВЫЧИСЛЕНИЕ CRC #Region "РАСЧЁТ ТАБЛИЦЫ" ''' 
''' Вычисляет таблицу предвычисленных значений для расчёта контрольной суммы. '''
 Private Sub generateLookupTable() For i As Integer = 0 To 255 CrcLookupTable(i) = generateTableItem(i) Next End Sub ''' 
''' Рассчитывает один байт таблицы значений для расчёта контрольной суммы ''' по алгоритму Rocksoft^tm Model CRC Algorithm. '''
 ''' Индекс записи в таблице, 0..255. Private Function generateTableItem(ByVal index As Integer) As UInteger Dim inbyte As UInteger = CUInt(index) If ReflectIn Then inbyte = reflect(inbyte, 8) End If Dim reg As UInteger = inbyte End Function #End Region '/РАСЧЁТ ТАБЛИЦЫ #Region "ВСПОМОГАТЕЛЬНЫЕ" ''' 
''' Возвращает наибольший разряд числа. '''
 ''' Число, разрядность которого следует определить, степень двойки. Private Function getBitMask(ByVal number As Integer) As UInteger Dim res As UInteger = 1UI End Function ''' 
''' Обращает заданное число младших битов переданного числа. '''
 ''' Число, которое требуется обратить («отзеркалить»). ''' Сколько младших битов числа обратить, 0..32. ''' Например: reflect(0x3E23, 3) == 0x3E26. Private Function reflect(ByVal value As UInteger, Optional ByVal bitsToReflect As Integer = 32) As UInteger Dim t As UInteger = value Dim reflected As UInteger = value For i As Integer = 0 To bitsToReflect - 1 Dim bm As UInteger = getBitMask(bitsToReflect - 1 - i) If (t And 1) = 1 Then reflected = reflected Or bm Else reflected = reflected And Not bm End If t >>= 1 Next Return reflected End Function #End Region '/ВСПОМОГАТЕЛЬНЫЕ End Class 

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

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

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

Dim crcModel As New RocksoftCrcModel(16, &H8005, 0, True, True, 0) Dim message as Byte() = Dim crc As UInteger = crcModel.ComputeCrc(message)

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

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

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

using System; namespace CRC < /// 
Реализует алгоритм расчёта CRC методом Rocksoft^tm Model CRC.
 public class RocksoftCrcModel < /// 
Таблица предвычисленных значений для расчёта контрольной суммы.
 public readonly uint[] CrcLookupTable; private int _CrcWidth; private uint _Polynom; private bool _ReflectIn; private uint _InitRegister; private bool _ReflectOut; private uint _XorOut; private uint _TopBit; private uint _WidMask; /// 
/// Порядок CRC, в битах (8/16/32). /// Изменение этого свойства ведёт к пересчёту таблицы. ///
 public int CrcWidth < get < return this._CrcWidth; >set < if (this._CrcWidth == value) return; this._CrcWidth = value; this._TopBit = this.getBitMask(checked (this._CrcWidth - 1)); this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 > /// 
/// Образующий многочлен. /// Изменение этого свойства ведёт к пересчёту таблицы. ///
 public uint Polynom < get < return this._Polynom; >set < if ((int) this._Polynom == (int) value) return; this._Polynom = value; this.generateLookupTable(); >> /// 
/// Обращать байты сообщения? /// Изменение этого свойства ведёт к пересчёту таблицы. ///
 public bool ReflectIn < get < return this._ReflectIn; >set < if (this._ReflectIn == value) return; this._ReflectIn = value; this.generateLookupTable(); >> /// 
Начальное содержимое регистра.
 public uint InitRegister < get < return this._InitRegister; >set < if ((int) this._InitRegister == (int) value) return; this._InitRegister = value; >> /// 
Обращать выходное значение CRC?
 public bool ReflectOut < get < return this._ReflectOut; >set < if (this._ReflectOut == value) return; this._ReflectOut = value; >> /// 
Значение, с которым XOR-ится выходное значение CRC.
 public uint XorOut < get < return this._XorOut; >set < if ((int) this._XorOut == (int) value) return; this._XorOut = value; >> /// 
Возвращает старший разряд полинома.
 public uint TopBit < get < return this._TopBit; >> /// 
Возвращает длинное слово со значением (2^width)-1.
 /// /// private uint WidMask < get < return this._WidMask; >> /// 
/// Конструктор, инициализированный параметрами по умолчанию для алгоритма CRC32. ///
 public RocksoftCrcModel() < base..ctor(); this.CrcLookupTable = new uint[256]; this._CrcWidth = 32; this._Polynom = 79764919U; this._ReflectIn = true; this._InitRegister = uint.MaxValue; this._ReflectOut = true; this._XorOut = uint.MaxValue; this._TopBit = this.getBitMask(checked (this.CrcWidth - 1)); this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 /// 
/// Инициализирует новый экземпляр параметрической модели CRC с настраиваемыми параметрами. ///
 /// Разрядность контрольной суммы в битах. /// Полином. /// начальное содержимое регистра. /// Обращать ли входящие байты сообщения? /// Обратить ли CRC перед финальным XOR. /// Конечное значение XOR. public RocksoftCrcModel(int width, uint poly, uint initReg = 4294967295, bool isReflectIn = true, bool isReflectOut = true, uint xorOut = 4294967295) < base..ctor(); this.CrcLookupTable = new uint[256]; this._CrcWidth = 32; this._Polynom = 79764919U; this._ReflectIn = true; this._InitRegister = uint.MaxValue; this._ReflectOut = true; this._XorOut = uint.MaxValue; this._TopBit = this.getBitMask(checked (this.CrcWidth - 1)); this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 /// 
Вычисляет значение контрольной суммы переданного сообщения.
 /// Исходное сообщение, для которого нужно посчитать контрольную сумму. /// public uint ComputeCrc(ref byte[] message) < uint num1 = this.InitRegister; byte[] numArray = message; int index = 0; while (index < numArray.Length) < byte num2 = numArray[index]; num1 = this.getNextRegisterContent(num1, num2); checked < ++index; >> return this.getFinalCrc(num1); > /// 
/// Вычисляет значение контрольной суммы переданного сообщения и возвращает его в виде массива байтов. ///
 /// Исходное сообщение, для которого нужно посчитать контрольную сумму. /// public byte[] ComputeCrcAsBytes(byte[] message) < byte[] bytes = BitConverter.GetBytes(this.ComputeCrc(ref message)); byte[] numArray = new byte[checked (bytes.Length - 1 + 1)]; int num1 = 0; int num2 = checked (bytes.Length - 1); int index = num1; while (index > return numArray; > /// 
Обрабатывает один байт сообщения (0..255).
 /// Содержимое регистра на предыдущем шаге. /// Значение очередного байта из сообщения. private uint getNextRegisterContent(uint prevRegContent, byte value) < uint num1 = (uint) value; if (this.ReflectIn) num1 = this.reflect(num1, 8); uint num2 = prevRegContent ^ num1 > while (num3 /// 
Возвращает значение CRC для обработанного сообщения.
 /// Значение регистра до финального обращения и XORа. /// private uint getFinalCrc(uint regContent) < if (this.ReflectOut) return this.XorOut ^ this.reflect(regContent, this.CrcWidth); return this.XorOut ^ regContent; >/// 
Вычисляет таблицу предвычисленных значений для расчёта контрольной суммы.
 private void generateLookupTable() < int index = 0; do < this.CrcLookupTable[index] = this.generateTableItem(index); checked < ++index; >> while (index /// 
/// Рассчитывает один байт таблицы значений для расчёта контрольной суммы /// по алгоритму Rocksoft^tm Model CRC Algorithm. ///
 /// Индекс записи в таблице, 0..255. private uint generateTableItem(int index) < uint num1 = checked ((uint) index); if (this.ReflectIn) num1 = this.reflect(num1, 8); uint num2 = num1 > while (num3 /// 
Возвращает наибольший разряд числа.
 /// Число, разрядность которого следует определить, степень двойки. /// private uint getBitMask(int number) < return (uint) (1 /// 
Обращает заданное число младших битов переданного числа.
 /// Число, которое требуется обратить ("отзеркалить"). /// Сколько младших битов числа обратить, 0..32. /// /// Например: reflect(0x3E23, 3) == 0x3E26. private uint reflect(uint value, int bitsToReflect = 32) < uint num1 = value; uint num2 = value; int num3 = 0; int num4 = checked (bitsToReflect - 1); int num5 = num3; while (num5 >= 1; checked < ++num5; >> return num2; > > >

Данная программа на 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.

+-----------------+-----+---------+ | c1 | x | c2 | +-----------------+-----+---------+

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

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

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

На основе приведённого алгоритма была написана программа – калькулятор для расчёта контрольных сумм по алгоритмам CRC32, CRC16 и CRC8 . Внешний вид окна приведён на рисунке. Программа работает под ОС Windows и требует .NET версии 3.5 .

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

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

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

Скачать программу «Калькулятор контрольной суммы CRC»

2023.05. Добавил версию 1.2 калькулятора. Пароль на архив – soltaurus.

Скачать вложения:

• Калькулятор контрольной суммы CRC (8806 Скачиваний)
• Калькулятор контрольной суммы CRC v1.2 (731 Скачиваний)

Как проверить MD5 хеш-сумму файла в Windows

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

Вариант через расширение для проводника

Для проводника Windows существует замечательная программа Hashtab, которая бесплатна для некоммерческого использования. Скачать ее можно с официального сайта. Выбираем бесплатную (Free) версию и жмем на кнопку «Download». После установки программы, в контекстном меню проводника появится новая вкладка «Хеш-суммы файлов», выбрав которую, программа автоматически посчитает хеш-суммы для выбранного файла в зависимости от того, какие алгоритмы выбраны в ее настройках.

Вариант через командную строку (без установки программ)

В том случае, если вам не хочется устанавливать какие-либо программы, то можно обойтись встроенными средствами Windows, для этого можно воспользоваться утилитой CertUtil. Для проверки MD5 хеша, достаточно ввести следующую команду:

certutil -hashfile C:\Users\Admin\Downloads\HashTab_v6.0.0.34_Setup.exe MD5

C:\Users\Admin\Downloads\HashTab_v6.0.0.34_Setup.exe — это путь к тому файлу, хеш-сумму которого мы хотим посчитать. Как видно на скриншоте, хеш-сумма нашего файла 62130c3964. полностью идентична той, которую мы получили с помощью первого способа.

Вариант через командную строку (с установкой программы)

В случае, если необходимо посчитать хеш-сумму файла через командную строку, мы можем воспользоваться утилитой от Microsoft, которая годится как раз для таких случаев. Скачиваем ее с официального сайта Microsoft и устанавливаем. Для этого надо будет создать какую-либо папку на жестком диске и указать ее в процессе установки. В нашем примере, программа была установлена в папку C:\Program Files (x86)\FCIV. Для того, чтобы посчитать MD5 хеш-сумму файла, нам необходимо запусить командную строку и в ней набрать следующую команду:

"C:\Program Files (x86)\FCIV\fciv.exe" -md5 C:\Users\Admin\Downloads\HashTab_v6.0.0.34_Setup.exe 

Как видите, MD5 хеш-сумма одинакова как для всех трех способов, которые рассмотрены в данной статье.

«C:\Program Files (x86)\FCIV\fciv.exe» — это путь к файлу fciv.exe
-md5 — указание алгоритма по которому fciv.exe будет считать хеш-сумму
C:\Users\Admin\Downloads\HashTab_v6.0.0.34_Setup.exe — путь к файлу, для которого мы считаем хеш-сумму.