Алгоритм CRC32 – перевірка цілісності даних

CRC32 (Cyclic Redundancy Check) – це алгоритм хешування, який застосовується для перевірки цілісності даних. Він широко застосовується в різних областях, таких як мережеві протоколи, зберігання даних, а також у комп'ютерних іграх та багатьох інших програмах. У цій статті я розповім детальніше про CRC32, його принципи роботи та надам приклади коду різними мовами програмування.

CRC32 використовує поліном як ключ, який визначає його характеристики. Поліном складається з послідовності бітів, де певні біти мають значення 1, інші - значення 0. Залежно від обраного полінома, характеристики алгоритму можуть відрізнятися. У випадку CRC32 поліном має стандартне значення 0xEDB88320.

Принцип роботи CRC32 заснований на розподілі бітно вхідних даних на поліном. Вхідні дані розглядаються як послідовність бітів, і кожного біта виконується певна операція. Якщо поточний біт дорівнює 1, відбувається побитное додавання з поліномом. Якщо ж біт дорівнює 0, відбувається пропуск операції. Цей процес повторюється для кожного біта даних, поки не буде перебрано всю послідовність.

Наприклад, давайте розглянемо такі дані у вигляді рядка: " Hello, World! " . Відправимо цей рядок на хешування за допомогою алгоритму CRC32.

import zlib data = b"Hello, World!" hash_value = zlib.crc32(data) print("CRC32:", hash_value)

При запуску цього коду ви отримаєте значення CRC32 у шістнадцятковому форматі. Для цього рядка "Hello, World!" значення CRC32 дорівнює 0xB698BEB9.

Тепер розглянемо приклад мовою C++, який розраховує CRC32 для блоку пам'яті:

 #include #include #include #include uint32_t crc32(uint32_t crc, const void *buf, size_t size) <static uint32_t crc_table[256]; if (!crc_table[1]) < for (uint32_t i = 0; i < 256; i++) < uint32_t c = i; for (int j = 0; j < 8; j++) c = c & 1? 0xEDB88320 ^ (c >> 1) : c >> 1; crc_table[i] = c; > > crc = ~ crc; uint8_t *data = (uint8_t *)buf; while (size--) crc = crc_table [(crc ^ *da++) & 0xFF] ^ (crc >> 8); return ~crc; > int main()

Цей приклад показує, як можна обчислити CRC32 за допомогою таблиці попередньо обчислених значень для оптимізації процесу. Результат буде таким самим, як у попередньому прикладі.

Після завершення хешування, CRC32 від рядка "Hello, World!" буде мати значення 0xB698BEB9 в обох випадках.

CRC32 є швидким та ефективним алгоритмом, який добре підходить для перевірки цілісності даних. Він добре відомий і широко застосовується у різних областях. Код, наданий у цій статті, допоможе вам зрозуміти, як можна реалізувати алгоритм CRC32 різними мовами програмування.

Як порахувати контрольну суму 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", то провадиться інверсія бітів (операція XOR, що виключає АБО) у тих розрядах регістру, які відповідають одиницям у поліномі.
Якщо ще є біти, переходимо до кроку 3).
Коли всі біти повідомлення надійшли в регістр і були оброблені цим алгоритмом, у регістрі залишається залишок від поділу, який є контрольною сумою 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, розраховану методом побитового зсуву. '''
 ''' Вхідна послідовність байтів (початкове повідомлення). ''' Утворюючий багаточлен розрядності 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 reverse an = True) As UInteger Dim widthInBytes As Integer = width \ 8 'Доповнюємо повідомлення width нулями (розрахунок у байтах): ReDim Preserve bytes(bytes.Length - 1 + widthInBytes) 'Створюємо чергу бітів з повідомлення: Dim msgFifo As New Queu. Count * 8 - 1) For Each b As Byte In bytes Dim ba As New BitArray() If reverseBytes The For I As Integer = 0 To 7 msgFifo. з бітів початкового заповнення регістру: Dim initBytes As Byte() = BitConverter. width - 1) For Each b As Byte In initBytesReversed Dim ba As New BitArray() If No reverseBytes Then For i As Integer = 0 To 7 initFifo. та 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 Маскуємо молодші розряди. 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 = reflect 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^mm 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 As UInteger = &H4 ''' Звертати байти повідомлення? ''' Зміна цієї властивості веде до перерахунку таблиці. '''
 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 = ''' Початковий вміст регістру. '''
 Public Property InitRegister As UInteger Get Return _InitRegister End Get Set(value As UInteger) ''' Звертати вихідне значення 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 xO) 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 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 ''' ''' Повертає значення CRC для обробленого повідомлення. '''
 ''' Значення регістру до фінального звернення та XOR. Private Function getFinalCrc(ByVal regContent As UInteger) As UInteger If ReflectOut The Dim res As UInteger = XorOut Xor reflect(regContent, CrcWidth) Return res 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 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 методом RocksoftTM 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 = новий 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 вкладається в 232 ~ 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 RocksoftCrcModel() на Visual Basic.NET і C#.

Вміст архіву "CRC calculator"

Отже, підіб'ємо підсумки. У цій статті ми:
- Довідалися, що таке контрольна сума CRC і які бувають її види;
– навчилися вважати CRC методом побітового зсуву та табличним методом;
- Дізналися алгоритми «злому» CRC і зробили висновок про область застосування контрольної суми типу CRC.

Завантажити програму «Калькулятор контрольної суми CRC»

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

Що таке CRC 32