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