Введение
Данные, используемые для обнаружения ошибок в других данных.
Контрольная сумма — это небольшой блок данных, вычисленный на основе другого блока цифровых данных с целью обнаружения ошибок, которые могли возникнуть при его передаче или хранении. Сами по себе контрольные суммы часто используются для проверки целостности данных, но не предназначены для проверки их подлинности. Процедура, генерирующая контрольную сумму, называется функцией контрольной суммы или алгоритмом контрольной суммы. В зависимости от целей разработки, хороший алгоритм контрольной суммы обычно выдает существенно отличающееся значение даже при незначительных изменениях входных данных. Это особенно верно для криптографических хеш-функций, которые могут использоваться для обнаружения множества ошибок повреждения данных и проверки общей целостности данных; если вычисленная контрольная сумма для текущих входных данных совпадает с сохраненным значением ранее вычисленной контрольной суммы, существует очень высокая вероятность того, что данные не были случайно изменены или повреждены. Функции контрольной суммы связаны с хеш-функциями, цифровыми отпечатками, функциями рандомизации и криптографическими хеш-функциями. Однако каждое из этих понятий имеет различные области применения и, следовательно, различные цели разработки. Например, функция, возвращающая начало строки, может предоставить хеш, подходящий для некоторых приложений, но никогда не будет являться подходящей контрольной суммой. Контрольные суммы используются в качестве криптографических примитивов в более сложных алгоритмах аутентификации. Для криптографических систем с этими двумя конкретными целями разработки обратитесь к HMAC. Контрольные цифры и биты четности — это частные случаи контрольных сумм, подходящие для небольших блоков данных (таких как номера социального страхования, номера банковских счетов, машинные слова, отдельные байты и т. д.). Некоторые коды коррекции ошибок основаны на специальных контрольных суммах, которые не только обнаруживают распространенные ошибки, но и позволяют восстановить исходные данные в определенных случаях.
Бата или слова с паритетом
Самый простой алгоритм проверки контрольной суммы — это так называемая продольная проверка чётности, которая разбивает данные на "слова" фиксированной длины n бит, а затем вычисляет побитовую операцию исключающего ИЛИ (XOR) для всех этих слов. Результат добавляется к сообщению в виде дополнительного слова. Проще говоря, при n=1 это означает добавление бита в конец битов данных для обеспечения чётного количества единиц ("1"). Для проверки целостности сообщения получатель вычисляет побитовую операцию исключающего ИЛИ для всех слов сообщения, включая контрольную сумму; если результат не является словом, состоящим из n нулей, получатель понимает, что произошла ошибка при передаче. При использовании этой контрольной суммы любая ошибка передачи, изменяющая один бит сообщения или нечётное количество бит, будет обнаружена как неверная контрольная сумма. Однако ошибка, затрагивающая два бита, останется незамеченной, если эти биты находятся в одинаковой позиции в двух разных словах. Также не будет обнаружен обмен местами двух или более слов. Если затронутые биты выбираются независимо и случайным образом, вероятность того, что двухбитовая ошибка останется незамеченной, равна 1/n.
Дополнительная сумма
Вариант предыдущего алгоритма состоит в сложении всех "слов" как беззнаковых двоичных чисел, отбрасывая биты переполнения, и добавлении двух дополнительного кода от общей суммы в качестве контрольной суммы. Для проверки сообщения принимающая сторона складывает все слова таким же образом, включая контрольную сумму; если результат не представляет собой слово, состоящее только из нулей, значит, произошла ошибка. Этот вариант также обнаруживает любую однобитовую ошибку, однако в SAE J1708 используется просуммирование по модулю.
Зависит от позиции
Простые контрольные суммы, описанные выше, не обнаруживают некоторые распространенные ошибки, затрагивающие сразу несколько битов, например, изменение порядка слов данных или вставка/удаление слов, состоящих целиком из нулей. Наиболее часто используемые на практике алгоритмы контрольных сумм, такие как контрольная сумма Флетчера, Adler 32 и циклические избыточные коды (CRC), решают эти проблемы, учитывая не только значение каждого слова, но и его позицию в последовательности. Эта особенность, как правило, увеличивает вычислительные затраты на получение контрольной суммы.
Нечеткая контрольная сумма
Идея нечеткой контрольной суммы была разработана для обнаружения спама в электронной почте путем создания общих баз данных от нескольких интернет-провайдеров, содержащих электронные письма, подозреваемые в спаме. Содержание такого спама часто может незначительно отличаться, что делает обычное контрольное суммирование неэффективным. В отличие от этого, "нечеткая контрольная сумма" сводит текст сообщения к его существенным элементам, а затем генерирует контрольную сумму стандартным образом. Это значительно повышает вероятность того, что слегка различающиеся спам-сообщения будут иметь одинаковую контрольную сумму. Программное обеспечение интернет-провайдеров для обнаружения спама, такое как SpamAssassin, от сотрудничающих провайдеров отправляет контрольные суммы всех электронных писем в централизованную службу, например DCC. Если количество представленных нечетких контрольных сумм превышает определенный порог, база данных отмечает это как вероятный признак спама. Пользователи услуг интернет-провайдера аналогично генерируют нечеткую контрольную сумму для каждого своего электронного письма и запрашивают у службы оценку вероятности того, что письмо является спамом.
Общие соображения
Сообщение длиной в m битов можно рассматривать как вершину m-мерного гиперкуба. Эффект алгоритма контрольной суммы, выдающего контрольную сумму длиной n бит, заключается в отображении каждого m-битного сообщения в вершину большего гиперкуба размерности m + n. Все возможные полученные сообщения представлены 2^(m + n) вершинами этого гиперкуба. Действительные полученные сообщения (те, у которых правильная контрольная сумма) составляют меньшее множество, содержащее только 2^m вершин. Однобитовая ошибка в передаче соответствует смещению из действительной вершины (правильного сообщения и контрольной суммы) в одну из m соседних вершин. Ошибка, затрагивающая k битов, перемещает сообщение в вершину, отстоящую на k шагов от его правильной вершины. Цель хорошего алгоритма контрольной суммы – распределить действительные вершины как можно дальше друг от друга, чтобы повысить вероятность того, что "типичные" ошибки передачи приведут к недействительной вершине.