UK 
EnglishТипова
Polski💻 Контрольна Сума CRC
Візуалізуйте, як циклічний надлишковий контроль виявляє помилки при передачі цифрових даних.
Схожі симуляції
Про контрольну суму CRC
Циклічний надлишковий контроль (CRC) — це код виявлення помилок, що обчислюється шляхом трактування блоку даних як полінома над GF(2) — двійковим полем, де вся арифметика виконується за модулем 2 (XOR), — та ділення його на фіксований породжуючий поліном. Залишок цього ділення додається до даних; отримувач перераховує ділення і позначає будь-яку розбіжність як помилку передачі. CRC-32, визначений породжуючим поліномом 0x04C11DB7, використовується в кадрах Ethernet, архівах ZIP, зображеннях PNG та стеку TCP/IP, гарантуючи виявлення всіх одиночних помилок бітів, усіх подвійних помилок бітів, усіх непарних кількостей помилок бітів і всіх пакетних помилок коротших за 32 біти.
Симулятор візуалізує довге XOR-ділення крок за кроком, показуючи кожен проміжний залишок і схему регістра зсуву, що виконує те саме обчислення в апаратурі. Ви можете перемикатися між пресетами CRC-8, CRC-16 та CRC-32, редагувати вхідне повідомлення та вносити одиночні або багатобітові помилки, щоб перевірити виявлення.
Часті запитання
Чому для CRC використовується арифметика над GF(2) (XOR)?
Арифметика GF(2) не має перенесень, що робить обчислення CRC надзвичайно ефективним в апаратному та програмному забезпеченні: додавання стає XOR, множення стає AND, а поліноміальне ділення можна реалізувати як регістр зсуву зі зворотним зв'язком (LFSR), що тактується один раз на біт. Алгебрична структура поліномів GF(2) також робить формальні докази виявлення помилок практичними за допомогою теорії кодування.
Які типи помилок гарантовано виявляє CRC-32?
CRC-32 виявляє: усі одиночні помилки бітів; усі подвійні помилки бітів (для повідомлень коротших за 2³² − 1 бітів); усі непарні кількості помилок бітів (оскільки 0x04C11DB7 ділиться на (x+1)); усі пакетні помилки довжиною ≤ 32 бітів; та велику частку (1 − 2⁻³²) довших пакетних помилок. Він НЕ гарантує виявлення всіх багатобітових випадкових помилок — для цього використовуються потужніші коди, такі як Ріда-Соломона.
Як регістр зсуву зі зворотним зв'язком (LFSR) обчислює CRC в апаратурі?
LFSR — це ланцюжок тригерів, чиї відводи зворотного зв'язку відповідають одиничним бітам породжуючого полінома. Кожен тактовий цикл зсуває один біт вхідних даних і виконує XOR зі зворотним зв'язком з відводів. Після того як усі біти даних пройшли через регістр, його вміст є залишком CRC. Це обробляє один біт за цикл на повній швидкості каналу — мільярди бітів за секунду в сучасних Ethernet-мікросхемах.
Чому різні реалізації CRC-32 дають різні результати?
Існує кілька варіантів CRC-32: варіант Ethernet/ZIP/PNG (поліном 0x04C11DB7, початкове значення 0xFFFFFFFF, віддзеркалений вхід/вихід, фінальний XOR 0xFFFFFFFF) і варіант Кастаньйолі CRC-32C (поліном 0x1EDC6F41), що використовується в iSCSI, SCTP та ext4. Змішування варіантів спричиняє розбіжності контрольних сум. Модель Rocksoft визначає 7 параметрів, що повністю задають алгоритм CRC.
Чи придатний CRC для криптографічної перевірки цілісності?
Ні. CRC — це простий код виявлення помилок, а не криптографічна хеш-функція. Зловмисник, здатний модифікувати повідомлення, може тривіально перерахувати CRC і підробити дійсну контрольну суму. Для виявлення підробки в контексті безпеки використовуйте код автентифікації повідомлення (MAC), наприклад HMAC-SHA256, або криптографічний хеш, як-от SHA-3. CRC придатний лише для виявлення випадкового пошкодження в довірених каналах.
Як програмне обчислення CRC використовує таблиці пошуку?
Обробка одного біта за раз повільна у програмному забезпеченні. Натомість заздалегідь обчислюється таблиця з 256 записів: table[b] = CRC одного байта b, за яким йдуть нулі. Обробка кожного байта вхідних даних потім вимагає лише одного пошуку в таблиці, одного XOR та одного зсуву — це дозволяє табличному CRC-32 обчислюватися зі швидкістю кілька ГБ/с на сучасних процесорах. Процесори x86 з набором інструкцій SSE4.2 мають спеціальну інструкцію CRC32 для CRC-32C.
Яка різниця між CRC-8, CRC-16 та CRC-32?
Число вказує на степінь породжуючого полінома і ширину контрольної суми в бітах. CRC-8 (8-бітний залишок) використовується у вбудованих протоколах на кшталт SMBus та 1-Wire, де розмір коду має значення. CRC-16 (16-бітний) поширений у послідовних протоколах (MODBUS, пакети даних USB) і виявляє всі пакетні помилки до 16 бітів. CRC-32 (32-бітний) дає ймовірність хибнонегативного результату 1 до 4 мільярдів і є стандартом для файлових систем і мережевих пакетів.
Чи можуть два різних повідомлення дати однаковий CRC (колізія)?
Так — колізії існують, оскільки CRC відображає повідомлення довільної довжини на контрольну суму фіксованої довжини (наприклад, 32 біти). Маючи дійсну пару повідомлення+CRC, завжди можна побудувати інше повідомлення з тим самим CRC, додавши ретельно підібрані біти. Ймовірність того, що випадкове пошкодження дасть той самий CRC-32, становить 2⁻³² ≈ 2,3×10⁻¹⁰, що незначно для зв'язку, але не для ворожих сценаріїв.
Що таке породжуючий поліном і як він обирається?
Породжуючий поліном g(x) визначає властивості виявлення помилок CRC. Хороший породжуючий поліном має бути примітивним (щоб виявляти всі непарні помилки бітів) або принаймні мати множник (x+1). Поліном CRC-32 0x04C11DB7 було розроблено для максимізації виявлення пакетних помилок для довжин кадрів Ethernet. Вибір оптимальних поліномів для конкретних довжин коду та моделей помилок — активна область досліджень теорії кодування.