Як порахувати контрольну суму 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" означає позицію біта-одиниці в числі, починаючи з нульової, а старший розряд вказує на ступінь полінома і відкидається при інтерпретації числа. Тобто записане раніше число - це не що інше як (1) 00000111 в двійковій системі числення, або 7 в десяткової. В дужках я вказав Автоматичне виведення старший розряд числа, його не прийнято писати.
Ось ще приклад: x 16 + x 15 + x 2 + x 0 = (1) 1000000000000101 = 0x8005 = 32773.
Зазвичай використовуються якісь стандартні многочлени для різних типів CRC. Ось деякі з них:
У статті Вікіпедії, присвяченій розрахунку CRC, є велика таблиця утворюють поліномів.
Так як же вважати контрольну суму? Існує базовий метод - розподіл повідомлення на поліном «в лоб» - і його модифікації з метою зменшення кількості обчислень і, відповідно, прискорення розрахунку CRC. Для початку ми розглянемо саме базовий метод.
У загальному вигляді розподіл числа на многочлен виконується за таким алгоритмом. Алгоритм обчислення контрольної суми CRC:
- Створюється масив (реєстр), заповнений нулями, рівний по довжині розрядності (ступеня) полінома.
- Оригінал тексту доповнюється нулями в молодших розрядах, в кількості, що дорівнює числу розрядів полінома.
- В молодший розряд регістра заноситься один старший біт повідомлення, а з старшого розряду регістра висувається один біт.
- Якщо висунутий біт дорівнює "1", то проводиться інверсія бітів (операція XOR, що виключає АБО) в тих розрядах регістру, які відповідають одиницям в поліномі.
- Якщо в повідомленні ще є біти, переходимо до кроку 3).
- Коли все біти повідомлення надійшли в регістр і були оброблені цим алгоритмом, в регістрі залишається залишок від ділення, який і є контрольною сумою 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 для коротких повідомлень, довжиною до декількох десятків кілобайт. Я писав її з метою тільки продемонструвати роботу простого алгоритму, і не займався оптимізацією. При розрахунку CRC для довгого повідомлення, розміром десятки або сотні мегабайтів, програма буде сильно завантажувати процесор і пам'ять, тому що все повідомлення повністю завантажується в чергу. Цьому сприяє метод перетворення числа в бітову послідовність, використовуючи Queue (Of Boolean). Для роботи з такими великими повідомленнями бажано реалізувати проміжний буфер, який буде передавати повідомлення в програму невеликими порціями.
Зате у цієї програми є одна перевага: вона може бути використана для розрахунку CRC будь-якого порядку, не обов'язково 8, 16 або 32. Це може бути CRC5 або CRC49. Тільки для чисел більше 32-х розрядів потрібно змінити відповідним чином вхідні параметри - припустимо, poly передавати не як UInteger. а як ULong. або передавати його у вигляді бітового масиву (тоді теоретично порядок CRC взагалі буде необмежений).
3 Розрахунок контрольної суми CRC табличним методом
Для скорочення числа обчислень з попереднього методу - методу побітового зсуву - придумані деякі оптимізації.
Зокрема, зрушують не по одному біту за раз, а відразу по кілька. Найбільшу популярність здобули варіанти, в яких повідомлення зсувається на число бітів, кратне числу бітів в байті: 8, 16 або 32, тому що з байтами легше працювати (не потрібні додаткові перетворення). При цьому ідея алгоритму залишилася та ж: зрушення і виключає АБО з вмістом регістра.
Крім того, виявляється, що частина розрахунків можна провести заздалегідь і записати в масив - таблицю, з якої по мірі необхідності буде братися потрібне число. Такий метод розрахунку назвали табличний метод розрахунку CRC.
Цей код повністю готовий до використання, можна брати і застосовувати. Користуватися даною програмою так:
- створити екземпляр класу RocksoftCrcModel (). передавши в конструктор параметри моделі CRC;
- для розрахунку контрольної суми, викликати метод даного об'єкта ComputeCrc () або ComputeCrcAsBytes (). передавши як параметр інформаційне повідомлення, для якого необхідно порахувати контрольну суму;
- якщо змінюються параметри моделі CRC, таблиця автоматично перераховується, і новий екземпляр класу можна не створювати.
Наведу приклад використання даного класу для алгоритму CRC16. Як повідомлення message будемо використовувати масив байтів, який представляє собою рядок "123456789" в коді ASCII, яка використовується в багатьох онлайн-калькуляторах CRC:
Дана реалізація розрахунку CRC була перевірена мною шляхом звірення з багатьма онлайн-калькуляторами CRC (назвемо це «слабкою» перевіркою, саме таке визначення дано в вищевказаної статті, коли перевірка здійснюється на підставі порівняння розрахованої контрольної суми з еталонною, при однакових вихідних параметрах і повідомленні) .
Для любителів C # перепишемо даний клас таким чином:
Прикладаю до статті повністю робочий і готовий до використання файл RocksoftCrcModel.vb з реалізацією розрахунку контрольної суми CRC, який ми тут розглянули, а також RocksoftCrcModel.cs на C #.
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 добре підходить для перевірки цілісності даних при випадкових викривлення інформації в каналі передачі даних, але абсолютно не підходить для захисту від навмисного злому.
Отже, підіб'ємо підсумки. У цій статті ми:
- дізналися, що таке контрольна сума CRC і які бувають її види;
- навчилися рахувати CRC методом побітового зсуву і табличним методом; - дізналися алгоритми «злому» CRC і зробили висновок про межі застосування контрольної суми типу CRC.