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