Войти
Эффект типичной функции контрольной суммы (Unix cksum утилита) A контрольная сумма - это элемент данных небольшого размера, полученный из блока из цифровых данных с целью обнаружения ошибок, которые могли быть внесены во время его передачи или хранения. Сами по себе контрольные суммы часто используются для проверки целостности данных, но не используются для проверки данных подлинности.
. Процедура , которая генерирует эту контрольную сумму, называется функцией контрольной суммы или алгоритм контрольной суммы. В зависимости от целей разработки хороший алгоритм контрольной суммы обычно выводит существенно другое значение, даже при небольших изменениях, внесенных во входные данные. Это особенно верно для криптографических хэш-функций, которые могут использоваться для обнаружения многих ошибок повреждения данных и проверки общей целостности данных ; Если вычисленная контрольная сумма для текущего ввода данных совпадает с сохраненным значением ранее вычисленной контрольной суммы, существует очень высокая вероятность того, что данные не были случайно изменены или повреждены.
Функции контрольной суммы связаны с хэш-функциями, отпечатками пальцев, функциями рандомизации и криптографическими хэш-функциями. Однако каждая из этих концепций имеет разные приложения и, следовательно, разные цели проектирования. Например, функция, возвращающая начало строки, может предоставить хэш, подходящий для некоторых приложений, но никогда не будет подходящей контрольной суммой. Контрольные суммы используются как криптографические примитивы в более крупных алгоритмах аутентификации. Для криптографических систем с этими двумя конкретными целями разработки см. HMAC.
Контрольные цифры и биты четности - это особые случаи контрольных сумм, подходящие для небольших блоков данных (например, Номера социального страхования, номера банковских счетов, компьютерные слова, отдельные байты и т. Д.). Некоторые коды с исправлением ошибок основаны на специальных контрольных суммах, которые не только обнаруживают типичные ошибки, но также позволяют в определенных случаях восстанавливать исходные данные.
Простейшим алгоритмом контрольной суммы является так называемый продольный контроль четности, который разбивает данные на «слова» с фиксированным числом битов n, а затем вычисляет исключающее или (XOR) для всех этих слов. Результат добавляется к сообщению как дополнительное слово. Чтобы проверить целостность сообщения, получатель вычисляет исключающее или всех его слов, включая контрольную сумму; если результатом не является слово, состоящее из n нулей, получатель знает, что произошла ошибка передачи.
С этой контрольной суммой любая ошибка передачи, которая переворачивает один бит сообщения или нечетное количество битов, будет обнаруживаться как неправильная контрольная сумма. Однако ошибка, затрагивающая два бита, не будет обнаружена, если эти биты находятся в одной и той же позиции в двух разных словах. Также не будет обнаружена замена двух или более слов. Если затронутые биты независимо выбраны случайным образом, вероятность того, что двухбитовая ошибка не будет обнаружена, равна 1 / n.
Вариантом предыдущего алгоритма является сложение всех «слов» как двоичных чисел без знака, отбрасывание любых битов переполнения и добавление дополнения до двух из итог в качестве контрольной суммы. Чтобы проверить сообщение, получатель таким же образом складывает все слова, включая контрольную сумму; если результат не является словом, полным нулей, вероятно, произошла ошибка. Этот вариант также обнаруживает любую однобитовую ошибку, но промодульная сумма используется в SAE J1708.
Простые контрольные суммы, описанные выше, не позволяют обнаружить некоторые общие ошибки, которые влияют на многие биты один раз, например, изменение порядка слов данных или вставка или удаление слов со всеми битами, установленными в ноль. Алгоритмы контрольной суммы, наиболее часто используемые на практике, такие как контрольная сумма Флетчера, Adler-32 и циклическая проверка избыточности (CRC), устраняют эти недостатки, учитывая не только значение каждого слова, а также его положение в последовательности. Эта функция обычно увеличивает стоимость вычисления контрольной суммы.
Идея нечеткой контрольной суммы была разработана для обнаружения спама в электронной почте путем создания совместных баз данных от нескольких интернет-провайдеров электронной почты, подозреваемых в спаме. Содержание такого спама часто может отличаться по деталям, что делает обычное вычисление контрольной суммы неэффективным. Напротив, «нечеткая контрольная сумма» сокращает основной текст до характерного минимума, а затем генерирует контрольную сумму обычным образом. Это значительно увеличивает вероятность того, что несколько различающиеся спам-письма будут давать одинаковую контрольную сумму. Программное обеспечение для обнаружения спама от интернет-провайдеров, такое как SpamAssassin, сотрудничающих с интернет-провайдерами, отправляет контрольные суммы всех электронных писем в централизованную службу, такую как DCC. Если количество отправленных нечетких контрольных сумм превышает определенный порог, база данных отмечает, что это, вероятно, указывает на спам. Пользователи службы ISP аналогичным образом генерируют нечеткую контрольную сумму для каждого из своих электронных писем и запрашивают службу на предмет вероятности спама.
Сообщение длиной m бит можно рассматривать как часть m-мерный гиперкуб. Результатом алгоритма контрольной суммы, который дает n-битную контрольную сумму, является отображение каждого m-битного сообщения в угол большего гиперкуба с размером 
Тогда однобитовая ошибка передачи соответствует смещению от допустимого угла (правильное сообщение и контрольная сумма) к одному из m смежных углов. Ошибка, влияющая на k бит, перемещает сообщение в угол, который на k шагов удаляется из его правильного угла. Цель хорошего алгоритма контрольной суммы состоит в том, чтобы раздвинуть допустимые углы как можно дальше друг от друга, чтобы повысить вероятность того, что «типичные» ошибки передачи окажутся в недопустимом углу.
Общая тема
Исправление ошибок
Хеш-функции
Понятия, связанные с данным
 | В Викибуке Реализация алгоритма есть страница по теме : Контрольные суммы |
