Контрольные суммы и CRC.
й Парунов, дата публикации 18 февраля 2003г. |
Недавно возникла у меня тут потребность в контроле блоков информации. В памяти сразу всплыла магическая фраза "CRC". Вроде эта CRC бывает и 16-, и 32-битной (да хоть 512-битной, но это, пожалуй, перебор). И есть понятие "контрольная сумма". Вот об этом и поговорим, не углубляясь в теорию, а упирая на практическое применение.
Вообще говоря, задача стоит так: нам из нашей информации (назовём её блоком) нужно получить число, которое однозначно идентифицирует эту информацию (назовём его хэшем). Так как блоки большие, а число маленькое, ясно, что блоков, в том числе и такой же длины, дающих то же число, очень много, гораздо больше, чем атомов в Галактике. Зачем же тогда нужно такое число? Целей может быть две:
- Нужно опознать блок. Опознавать его по образцу неэффективно и часто бессмысленно, а вот по маленькому числу… При этом, естественно, желательно, чтобы числа получались "послучайнее" - то есть были равномерно размазаны в диапазоне от нуля до максимума. Мы сможем узнать "свой" блок, до некоторой степени быть уверены в том, что он никак (умышленно или случайно) не изменён, вычислив его хэш и сравнив с образцом.
- Нужно найти блок - есть ли он у нас уже, и где? Ясно, что при тупом сравнении всех блоков с новым можно состариться. А вычислить хэш и сравнить его с известными хэшами имеющихся блоков можно быстро.
Речь пойдёт о первом вопросе. Второй гораздо сложнее и неоднозначнее; если хотите разобраться в нём - смотрите информацию по поиску при помощи хэш-таблиц. Кстати, в большинстве случаев это наибыстрейший вариант поиска информации.
Контроль данных - вопрос древний и проработанный. Есть два основных его варианта:
- Контрольная пломба… ой, сумма. Байты (слова, двойные слова…) просто складываются, складываются по модулю 2, вычитаются в различных комбинациях. Например, складываем все байты (а лучше слова или вообще двойные слова) блока и получаем хэш. Этот метод исторически первый и самый быстрый.
- CRC. Менее быстрый (раз в шесть в случае 32 бит на Intel32), но более хаотичный метод. "Хаотичный" он потому, что при его вычислении применяется не только сложение, но и сдвиги регистров, что даёт возможность данному биту блока повлиять не на один-два-три бита хэша, а на многие, и очень быстро, таким образом, что для предсказания этого не существует математического аппарата - можно только поставить эксперимент.
А теперь скажем Основную Истину: теоретическая вероятность того, что Вам во Вселенной встретится блок с таким же хэшем, как у вашего блока, равна единице, делённой на два в степени числа разрядов хэша, независимо от того, каким из этих двух способов он посчитан (но: контрольная сумма должна считаться из порций блока того же размера. Нельзя надеяться, что надёжность 32-битной суммы _байтов_, а не двойных слов, будет приемлемой.). Это достаточно очевидно. Однако на практике встречаются различные вариации и искажения блоков: одиночные, групповые, периодические, умышленно искажённые… это уже не полностью случайные блоки. И именно на этом оселке выявляются достоинства и недостатки упомянутых способов.
Итак, если сравнивать достоверность опознания, учитывая именно искажения исходного сообщения, особенно периодические и умышленные, CRC даёт фору контрольным суммам. Например, если поменять буквы в строке, побайтная контрольная сумма этого "не заметит" - от перестановки мест слагаемых, вычитаемых, xor-ящихся данных результат не меняется. То же будет, если поменять местами два бита на расстоянии, кратном размеру байта - собственно, это одно и то же - или прирастить одну букву и уменьшить другую в случае сложения. Есть более сложные варианты контрольных сумм, но все они страдают предсказуемостью и "обходимостью".
С другой стороны, встречаются области применения, где имеются только случайные, "размазанные" (не кусочные) искажения. Особенно часто это бывает в линиях связи. В таких областях для контроля ошибок часто используются именно контрольные суммы благодаря низким затратам. Кроме того, если иметь в виду заточенность CRC под регулярные искажения, можно сказать, что искажения нерегулярные она отлавливает несколько хуже - общая-то эффективность определяется только разрядностью.
А вот для борьбы с людьми :)… вернее, для уверенной верификации информации, защищённой от изменения, применяется CRC. Это не означает, что CRC только борется с мошенничеством - это означает, что два ПОХОЖИХ блока, что часто встречается в жизни людей, CRC обработает лучше, "случайнее", с меньшей вероятностью получения одинаковых хэшей. И сообщение, защищённое CRC32, "подделать" так, чтобы не превратить сообщение в подозрительную кучу байтов (а CRC64 - и без этого условия при длине сообщения больше десятка байт), и сейчас, и в обозримой перспективе невозможно. Разумеется, хэш должен идти по защищённому каналу, иначе следует обратиться к алгоритмам необратимого шифрования, которые тут не обсуждаются, замечу лишь, что они существенно медленнее.
Приведу два модуля для вычисления CRC32 и CRC64. Последний вдвое медленнее. Алгоритм не обсуждается - обсуждать без теории там нечего: с одной стороны, всё просто, с другой - а почему так, а не иначе?.. Неразрешимое противоречие. Желающим овладеть теорией кину линки:
Лирическое отступление:
многие программисты полагают, что переписывание кода на ассемблере способно существенно улучшить скорость. В общем случае это действительно так, но не стоит забывать, что "одна голова хорошо, а две лучше". Современные компиляторы, в том числе и Delphi, знают ассемблер существенно лучше среднего выпускника вуза компьютерной специальности :), и знать ассемблер сейчас нужно, в основном, только чтобы представлять, какой код создаётся из Ваших исходников, поднимая при желании именно их скорость, а не заниматься этим "врукопашную".
Что и показано моим модулем для CRC32 - он в полтора раза быстрее ассемблерного кода й Парунов
февраль 2003г,
Специально для
Смотрите по теме: