Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Подземелье Магов
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
 
 02:43 inferno
 
 
Во Флориде и в Королевстве сейчас  02:45[Войти] | [Зарегистрироваться]

Контрольные суммы и CRC

Сергей Парунов
дата публикации 18-02-2003 12:25

Контрольные суммы и CRC

Недавно возникла у меня тут потребность в контроле блоков информации. В памяти сразу всплыла магическая фраза "CRC". Вроде эта CRC бывает и 16-, и 32-битной (да хоть 512-битной, но это, пожалуй, перебор). И есть понятие "контрольная сумма". Вот об этом и поговорим, не углубляясь в теорию, а упирая на практическое применение.

Вообще говоря, задача стоит так: нам из нашей информации (назовём её блоком) нужно получить число, которое однозначно идентифицирует эту информацию (назовём его хэшем). Так как блоки большие, а число маленькое, ясно, что блоков, в том числе и такой же длины, дающих то же число, очень много, гораздо больше, чем атомов в Галактике. Зачем же тогда нужно такое число? Целей может быть две:

  1. Нужно опознать блок. Опознавать его по образцу неэффективно и часто бессмысленно, а вот по маленькому числу… При этом, естественно, желательно, чтобы числа получались "послучайнее" - то есть были равномерно размазаны в диапазоне от нуля до максимума. Мы сможем узнать "свой" блок, до некоторой степени быть уверены в том, что он никак (умышленно или случайно) не изменён, вычислив его хэш и сравнив с образцом.
  2. Нужно найти блок - есть ли он у нас уже, и где? Ясно, что при тупом сравнении всех блоков с новым можно состариться. А вычислить хэш и сравнить его с известными хэшами имеющихся блоков можно быстро.

Речь пойдёт о первом вопросе. Второй гораздо сложнее и неоднозначнее; если хотите разобраться в нём - смотрите информацию по поиску при помощи хэш-таблиц. Кстати, в большинстве случаев это наибыстрейший вариант поиска информации.

Контроль данных - вопрос древний и проработанный. Есть два основных его варианта:
  1. Контрольная пломба… ой, сумма. Байты (слова, двойные слова…) просто складываются, складываются по модулю 2, вычитаются в различных комбинациях. Например, складываем все байты (а лучше слова или вообще двойные слова) блока и получаем хэш. Этот метод исторически первый и самый быстрый.
  2. CRC. Менее быстрый (раз в шесть в случае 32 бит на Intel32), но более хаотичный метод. "Хаотичный" он потому, что при его вычислении применяется не только сложение, но и сдвиги регистров, что даёт возможность данному биту блока повлиять не на один-два-три бита хэша, а на многие, и очень быстро, таким образом, что для предсказания этого не существует математического аппарата - можно только поставить эксперимент.

А теперь скажем Основную Истину: теоретическая вероятность того, что Вам во Вселенной встретится блок с таким же хэшем, как у вашего блока, равна единице, делённой на два в степени числа разрядов хэша, независимо от того, каким из этих двух способов он посчитан (но: контрольная сумма должна считаться из порций блока того же размера. Нельзя надеяться, что надёжность 32-битной суммы _байтов_, а не двойных слов, будет приемлемой.). Это достаточно очевидно. Однако на практике встречаются различные вариации и искажения блоков: одиночные, групповые, периодические, умышленно искажённые… это уже не полностью случайные блоки. И именно на этом оселке выявляются достоинства и недостатки упомянутых способов.

Итак, если сравнивать достоверность опознания, учитывая именно искажения исходного сообщения, особенно периодические и умышленные, CRC даёт фору контрольным суммам. Например, если поменять буквы в строке, побайтная контрольная сумма этого "не заметит" - от перестановки мест слагаемых, вычитаемых, xor-ящихся данных результат не меняется. То же будет, если поменять местами два бита на расстоянии, кратном размеру байта - собственно, это одно и то же - или прирастить одну букву и уменьшить другую в случае сложения. Есть более сложные варианты контрольных сумм, но все они страдают предсказуемостью и "обходимостью".

С другой стороны, встречаются области применения, где имеются только случайные, "размазанные" (не кусочные) искажения. Особенно часто это бывает в линиях связи. В таких областях для контроля ошибок часто используются именно контрольные суммы благодаря низким затратам. Кроме того, если иметь в виду заточенность CRC под регулярные искажения, можно сказать, что искажения нерегулярные она отлавливает несколько хуже - общая-то эффективность определяется только разрядностью.

А вот для борьбы с людьми :)… вернее, для уверенной верификации информации, защищённой от изменения, применяется CRC. Это не означает, что CRC только борется с мошенничеством - это означает, что два ПОХОЖИХ блока, что часто встречается в жизни людей, CRC обработает лучше, "случайнее", с меньшей вероятностью получения одинаковых хэшей. И сообщение, защищённое CRC32, "подделать" так, чтобы не превратить сообщение в подозрительную кучу байтов (а CRC64 - и без этого условия при длине сообщения больше десятка байт), и сейчас, и в обозримой перспективе невозможно. Разумеется, хэш должен идти по защищённому каналу, иначе следует обратиться к алгоритмам необратимого шифрования, которые тут не обсуждаются, замечу лишь, что они существенно медленнее.

Приведу два модуля для вычисления CRC32 и CRC64. Последний вдвое медленнее. Алгоритм не обсуждается - обсуждать без теории там нечего: с одной стороны, всё просто, с другой - а почему так, а не иначе?.. Неразрешимое противоречие. Желающим овладеть теорией кину линки:

Лирическое отступление:
многие программисты полагают, что переписывание кода на ассемблере способно существенно улучшить скорость. В общем случае это действительно так, но не стоит забывать, что "одна голова хорошо, а две лучше". Современные компиляторы, в том числе и Delphi, знают ассемблер существенно лучше среднего выпускника вуза компьютерной специальности :), и знать ассемблер сейчас нужно, в основном, только чтобы представлять, какой код создаётся из Ваших исходников, поднимая при желании именно их скорость, а не заниматься этим "врукопашную".
Что и показано моим модулем для CRC32 - он в полтора раза быстрее ассемблерного кода автора статьи "Почти всё, что вы хотели узнать, но боялись спросить о Crc32".

Скачать примеры : Crc.zip (4K)

Сергей Парунов
февраль 2003г,
Специально для Королевства Delphi

Смотрите по теме:


Смотрите также материалы по темам:
[Шифрование, контрольная сумма, хэш]

 Обсуждение материала [ 08-05-2007 03:46 ] 7 сообщений
  
Время на сайте: GMT минус 5 часов

Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
Функция может не работать в некоторых версиях броузеров.

Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

 
© При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
Все используемые на сайте торговые марки являются собственностью их производителей.

Яндекс цитирования