26-01-2024
Циклический избыточный код (англ. Cyclic redundancy check, CRC[1]) — алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных[2]. CRC является практическим приложением помехоустойчивого кодирования, основанном на определенных математических свойствах циклического кода.
Понятие циклические коды достаточно широкое[3]. В англоязычной литературе CRC расшифровывается двояко в зависимости от контекста: Cyclic Redundancy Code или Cyclic Redundancy Check[4]. Под первой расшифровкой понимают математический феномен циклических кодов, под второй — конкретное применение этого феномена как хэш-функции.
Первые попытки создания кодов с избыточной информацией начались задолго до появления современных ПК. К примеру, ещё в шестидесятых годах прошлого века Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекампа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих прием RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).
Но далеко не везде от кода требуется коррекция ошибок. Многие современные каналы связи обладают приемлемыми характеристиками, и зачастую достаточно лишь проверить, успешно ли прошла передача или возникли какие-нибудь сложности; структура же ошибок и конкретные позиции неверных символов совершенно не интересуют принимающую сторону. И в этих условиях очень удачным решением оказались алгоритмы, использующие контрольные суммы. CRC как нельзя лучше подходит для подобных задач: невысокие затраты ресурсов, простота реализации и уже сформированный математический аппарат из теории линейных циклических кодов обеспечили ей огромную популярность.
В самом общем своем виде контрольная сумма представляет собой некоторое значение, построенное по определенной схеме на основе кодируемого сообщения. Проверочная информация при систематическом кодировании дописывается в конец сообщения — после полезных данных. На принимающей стороне абонент знает алгоритм вычисления контрольной суммы: соответственно, программа имеет возможность проверить корректность принятых данных.
При передаче пакетов по реальному каналу, разумеется, могут возникнуть искажения исходной информации вследствие разных внешних воздействий: электрических наводок, плохих погодных условий и многих других. Сущность методики в том, что при хороших характеристиках хэш-функции в подавляющем числе случаев ошибка в сообщении приведет к изменению вычисленного на приеме значения CRC. Если исходная и вычисленная суммы не равны между собой, принимается решение о недостоверности принятых данных, и можно запросить повторную передачу пакета.
Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем . Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.
Каждой конечной последовательности битов взаимно однозначно сопоставляется двоичный полином , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:
Количество различных многочленов степени меньшей равно , что совпадает с числом всех двоичных последовательностей длины .
Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):
где
Умножение осуществляется приписыванием нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.
При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хэш-функции в контексте каждого конкретного применения.
Тем не менее, существует множество стандартизированных образующих многочленов, обладающих хорошими математическими и корреляционными свойствами (минимальное число коллизий, простота вычисления). В статье приведены некоторые из них, а также соответствующие реализации на языке Си.
Говоря о формировании контрольной суммы CRC, в первую очередь нужно упомянуть о полиноме-генераторе. Существует огромное множество многочленов, участвующих в формировании cyclic redundancy code; многие из них указаны в конце статьи.
Другим параметром конкретного алгоритма вычисления контрольной суммы является размер слова, или суммарное количество регистров — информационных ячеек, используемых для вычисления численного значения хэша. При этом обязательно учитывается то, что размер слова и степень образующего контрольную сумму полинома совпадают. На практике более всего распространены 8, 16 и 32 — битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.
И последний параметр, важный при описании определенной методики — начальные состояния регистров (стартовое слово). Это последняя из трех значимых характеристик; зная их в совокупности, мы можем восстановить алгоритм вычисления CRC, если данная модификация методики не имеет специфических особенностей, таких, как обратный порядок обработки битов.
Из файла берется первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старый старший бит, а младший бит освобождается — его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.
В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу.[1][5]
Этот парадокс касается и выбора многочлена-генератора: зачастую стандартизованные полиномы не являются самыми эффективными в плане статистических свойств соответствующего им check reduntancy code.
При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа учёных занималась исследованием порождающих многочленов разрядности до 16,[1] 24 и 32 бит,[6][7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния.[7] Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.
Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга[8]. Использование другого полинома — CRC-32C — позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше — поэтому в наши дни он тоже пользуется популярностью.[7] К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.
Ниже в таблице перечислены наиболее распространенные многочлены — генераторы CRC. На практике вычисление CRC может включать пре- и пост-инверсию, а также обратный порядок обработки битов. В проприетарных реализациях CRC для усложнения анализа кода применяют ненулевые начальные значения регистров.
Название | Полином | Представления:[9] нормальное / реверсированное / реверсированное от обратного |
---|---|---|
CRC-1 | (используется в аппаратном контроле ошибок; также известен как бит чётности) | 0x1 / 0x1 / 0x1 |
CRC-4-ITU | (ITU G.704[10]) | 0x3 / 0xC / 0x9 |
CRC-5-EPC | (Gen 2 RFID[11]) | 0x09 / 0x12 / 0x14 |
CRC-5-ITU | (ITU G.704[12]) | 0x15 / 0x15 / 0x1A |
CRC-5-USB | (USB token packets) | 0x05 / 0x14 / 0x12 |
CRC-6-ITU | (ITU G.704[13]) | 0x03 / 0x30 / 0x21 |
CRC-7 | (системы телекоммуникации, ITU-T G.707[14], ITU-T G.832[15], MMC, SD) | 0x09 / 0x48 / 0x44 |
CRC-8-CCITT | (I.432.1 (02/99) | 0x07 / 0xE0 / 0x83 |
CRC-8-Dallas/Maxim | (1-Wire bus) | 0x31 / 0x8C / 0x98 |
CRC-8 | (ETSI EN 302 307[16], 5.1.4) | 0xD5 / 0xAB / 0xEA[1] |
CRC-8-SAE J1850 | 0x1D / 0xB8 / 0x8E | |
CRC-10 | 0x233 / 0x331 / 0x319 | |
CRC-11 | (FlexRay[17]) | 0x385 / 0x50E / 0x5C2 |
CRC-12 | (системы телекоммуникации[18][19]) | 0x80F / 0xF01 / 0xC07 |
CRC-15-CAN | 0x4599 / 0x4CD1 / 0x62CC | |
CRC-16-IBM | (Bisync, Modbus, USB, ANSI X3.28[20], многие другие; также известен как CRC-16 и CRC-16-ANSI) | 0x8005 / 0xA001 / 0xC002 |
CRC-16-CCITT | (X.25, HDLC, XMODEM, Bluetooth, SD и др.) | 0x1021 / 0x8408 / 0x8810[1] |
CRC-16-T10-DIF | (SCSI DIF) | 0x8BB7[21] / 0xEDD1 / 0xC5DB |
CRC-16-DNP | (DNP, IEC 870, M-Bus) | 0x3D65 / 0xA6BC / 0x9EB2 |
CRC-16-Fletcher | Не CRC; см. Fletcher's checksum | Используется в Adler-32 A & B CRC |
CRC-24 | (FlexRay[17]) | 0x5D6DCB / 0xD3B6BA / 0xAEB6E5 |
CRC-24-Radix-64 | (OpenPGP) | 0x864CFB / 0xDF3261 / 0xC3267D |
CRC-30 | (CDMA) | 0x2030B9C7 / 0x38E74301 / 0x30185CE3 |
CRC-32-Adler | Не CRC; см. Adler-32 | См. Adler-32 |
CRC-32-IEEE 802.3 | (V.42, MPEG-2, PNG[22], POSIX cksum) | 0x04C11DB7 / 0xEDB88320 / 0x82608EDB[7] |
CRC-32C (Castagnoli) | (iSCSI, G.hn payload) | 0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0[7] |
CRC-32K (Koopman) | 0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B[7] | |
CRC-32Q | (aviation; AIXM[23]) | 0x814141AB / 0xD5828281 / 0xC0A0A0D5 |
CRC-64-ISO | (HDLC — ISO 3309) | 0x000000000000001B / 0xD800000000000000 / 0x800000000000000D |
CRC-64-ECMA | [24] | 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49 |
Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.
Одной из самых известных является методика Ross N. Williams[25]. В ней используются следующие параметры:
Name : CRC 16 Width : 16 Poly : 8005 Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : BB3D |
Name : CRC 16/IBM Width : 16 Poly : 8005 Init : FFFF RefIn : True RefOut : True XorOut : 0000 Check : 4B37 |
Name : CRC 32 Width : 32 Poly : 04C11DB7 Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF Check : CBF43926 |
Name : CRC 16/CITT Width : 16 Poly : 1021 Init : FFFF RefIn : False RefOut : False XorOut : 0000 |
Name : XMODEM Width : 16 Poly : 8408 Init : 0000 RefIn : True RefOut : True XorOut : 0000 |
Name : ARC Width : 16 Poly : 8005 Init : 0000 RefIn : True RefOut : True XorOut : 0000 |
Хеш-функции | |
---|---|
Общего назначения | |
Криптографические |
JH • HAVAL • Keccak (SHA-3) • LM-хеш • Luffa • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • Scrypt • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94 • ГОСТ Р 34.11-2012 |
Циклический избыточный код мкб, циклический избыточный код алгоритм python, циклический избыточный код онлайн, циклический избыточный код алгоритм.
Файл:ESDC 05 ru.png, Файл:Tommaso Salini - Still-Life - WGA20671.jpg, Negaprion acutidens, Томашек, Файл:Map of Lyaskovets municipality (Veliko Tarnovo Province).png.