чем ломать CRC32, необходимо научиться
Прежде, чем ломать CRC32, необходимо научиться его считать. Из всех учебников и статей мне больше всего нравится "a painless guide to crc error detection algorithms", которое я настоятельно рекомендую для изучения. Имеется так же и русскоязычный перевод. Адреса обоих можно найти во врезке по ссылкам. Кстати говоря, в последнее время набирает силу CRC64, который рассчитывается аналогичным образом, но, естественно, другим полиномом. Кое-где используется даже CRC128, но пока он не стандартизован, а поэтому здесь не затрагивается.
Аббревиатура CRC расшифровывается как "Cyclic Redundancy Check" (проверка избыточности циклической суммы) и стягивает под свою крышу целую кучу самых разных алгоритмов, разработанных в "геральдические" времена с ориентацией на воплощение в железо. В практическом плане это означает, что большинство CRC алгоритмов представляют собой тривиальный подсчет контрольной суммы в стиле а-ля: "for(a=0,CRC=INIT_VALUE;a< len;a++) CRC+=DATA[a];", лишь с той оговоркой, что сложение выполняется не алгебраическим путем, а происходит в полях Галуа в тесном сотрудничестве с полиномиальной арифметикой. В "железе" все это хозяйство реализуется на сдвиговых регистрах и логических вентилях, что очень дешево стоит и еще быстрее работает.
Программная "эмуляция" CRC на IBM PC мягко говоря... неоправданна. Приходится прибегать к табличным алгоритмам или сложным математическим преобразованиям, но первое требует памяти, второе — времени (процессорного) и в конечном счете мы раздуваем муху до размеров слона. Почему же тогда CRC пользуется такой популярностью? Его можно найти в zip, arj, различных защитных механизмах…. Такое впечатление, что кому-то некуда девать свои курсовые работы, а кто-то просто использует готовые библиотеки, пропуская теорию кодирования мимо ушей. Зачем она ему? Ведь все и так "работает"!
Но это все лирика. Вернемся к нашим баранам. Никакого единого стандарта на CRC не было и нет! Даже когда говорят о CRC16 или CRC32, то подразумевают всего лишь разрядность контрольной суммы, для вычисления которой необходимо знать два фундаментальных параметра: полином (poly) и начальное значение контрольной суммы (init).
А два других параметры: reflection — указывает на то, используется ли зеркальное битовое отражение или нет. Отражаться могут как входные данные, так и выходные. Если байт отражен, то нумерация в нем ведется слева направо, то есть наименее значимый бит располагается по меньшему адресу (как, например, на x86), и, соответственно, наоборот. Наиболее быстрыми будут те алгоритмы, которые соответствуют выбранной "железной" архитектуре, в противном случае, приходится прибегать к довольно дорогостоящей в плане процессорных ресурсов эмуляции.
Параметр XorOut — это то значение, которым XOR'ится рассчитанная контрольная сумма. Обычно она равна 0 или -1 (то есть FFFFh для CRC16 и FFFFFFFFh для CRC32).
Различные схемы (программы, защитные механизмы, аппаратные устройства) используют различные параметры подсчета контрольной суммы, отсутствие информации о которых существенно затрудняет взлом, поэтому ниже приводятся данные об основных алгоритмах, которые мне только удалось открыть.
|
название |
разрядность, бит |
poly |
init |
отражение |
xorout |
|
|
init |
out |
|||||
|
CRC-16 |
16 |
8005h |
0000h |
да |
да |
0000h |
|
CRC-16/CITT |
16 |
1021h |
FFFFh |
нет |
нет |
0000h |
|
XMODEM |
16 |
8408h |
0000h |
да |
да |
0000h |
|
ARC |
16 |
8005h |
0000h |
да |
да |
0000h |
|
CRC-32 |
32 |
04C11DB7h |
FFFFFFFFh |
да |
да |
FFFFFFFFh |
|
CRC-64 |
64 |
60034000F050Bh |
FAC432B10CD5E44Ah |
да |
да |
FFFFFFFFFFFFFFFFh |
Постойте! Но ведь "стандартный" полиномом для CRC32 равен EDB88320h, а совсем не 4C11DB7h. Это каждый студент знает! Все правильно, никакого противоречия здесь нет, закройте забрало и не высаживайтесь! Число EDB88320h представляет собой зеркально отраженный полином 4C11DB7h, в соответствии со словом "да" в колонке "отражение" (см. таблицу 1). Давайте переведем его к битовую виду и посмотрим, что получится.А получится у нас вот что:
04C11DB7h: 00000100110000010001110110110111
EDB88320h: 11101101101110001000001100100000
Листинг 1 стандартный CRC-32 полином и его общепринятая отображенная версия
Готовую процедуру расчета СRC приводить не будем, поскольку ее можно найти в любой книжке и в ссылках, приведенных ниже. Как уже говорилась, ее программная эмуляция на IBM PC крайне ненаглядна.
