stringtranslate.com

Контрольная сумма

Эффект типичной функции контрольной суммы ( cksumутилита Unix)

Контрольная сумма — это небольшой блок данных, полученный из другого блока цифровых данных с целью обнаружения ошибок , которые могли возникнуть во время его передачи или хранения . Сами по себе контрольные суммы часто используются для проверки целостности данных , но на них не полагаются для проверки аутентичности данных . [1]

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

Функции контрольной суммы связаны с хэш-функциями , отпечатками пальцев , функциями рандомизации и криптографическими хэш-функциями . Однако каждая из этих концепций имеет разные применения и, следовательно, разные цели проектирования. Например, функция, возвращающая начало строки, может предоставить хэш, подходящий для некоторых приложений, но никогда не будет подходящей контрольной суммой. Контрольные суммы используются в качестве криптографических примитивов в более крупных алгоритмах аутентификации. Для криптографических систем с этими двумя конкретными целями проектирования [ необходимы пояснения ] см. HMAC .

Контрольные цифры и биты четности — это особые случаи контрольных сумм, подходящие для небольших блоков данных (таких как номера социального страхования , номера банковских счетов , компьютерные слова , отдельные байты и т. д.). Некоторые коды, исправляющие ошибки, основаны на специальных контрольных суммах, которые не только обнаруживают распространенные ошибки, но и позволяют в определенных случаях восстановить исходные данные.

Алгоритмы

Байт четности или слово четности

Самый простой алгоритм контрольной суммы — это так называемая продольная проверка четности , которая разбивает данные на «слова» с фиксированным числом n бит, а затем вычисляет побитовое исключающее ИЛИ (XOR) всех этих слов. Результат добавляется к сообщению как дополнительное слово. Проще говоря, для n = 1 это означает добавление бита в конец битов данных, чтобы гарантировать четное количество единиц. Чтобы проверить целостность сообщения, получатель вычисляет поразрядное исключение всех его слов, включая контрольную сумму; если результатом не является слово, состоящее из n нулей, получатель знает, что произошла ошибка передачи. [3]

С помощью этой контрольной суммы любая ошибка передачи, которая меняет один бит сообщения или нечетное количество битов, будет распознаваться как неправильная контрольная сумма. Однако ошибка, затрагивающая два бита, не будет обнаружена, если эти биты лежат в одной и той же позиции в двух разных словах. Также не будет обнаружена замена двух или более слов. Если затронутые биты выбираются случайным образом независимо друг от друга, вероятность того, что двухбитовая ошибка не будет обнаружена, равна 1/ n .

Сумма дополнения

Вариант предыдущего алгоритма состоит в том, чтобы сложить все «слова» как беззнаковые двоичные числа, отбросив все биты переполнения, и добавить дополнение до двух к сумме в качестве контрольной суммы. Чтобы проверить сообщение, получатель добавляет все слова таким же образом, включая контрольную сумму; если результат не является словом, полным нулей, возможно, произошла ошибка. Этот вариант тоже обнаруживает любую однобитовую ошибку, но в SAE J1708 используется промодульная сумма . [4]

Зависит от позиции

Простые контрольные суммы, описанные выше, не позволяют обнаружить некоторые распространенные ошибки, которые влияют на множество битов одновременно, например, изменение порядка слов данных или вставку или удаление слов, в которых все биты установлены в ноль. Алгоритмы контрольной суммы, наиболее используемые на практике, такие как контрольная сумма Флетчера , Adler-32 и проверки циклическим избыточным кодом (CRC), устраняют эти недостатки, рассматривая не только значение каждого слова, но и его положение в последовательности. Эта функция обычно увеличивает стоимость вычисления контрольной суммы.

Нечеткая контрольная сумма

Идея нечеткой контрольной суммы была разработана для обнаружения спама в электронной почте путем создания совместных баз данных от нескольких интернет-провайдеров электронной почты, предположительно являющейся спамом. Содержание такого спама часто может различаться в деталях, что делает обычное подсчет контрольных сумм неэффективным. Напротив, «нечеткая контрольная сумма» сводит основной текст к характерному минимуму, а затем генерирует контрольную сумму обычным способом. Это значительно увеличивает вероятность того, что несколько разные спам-сообщения дадут одну и ту же контрольную сумму. Программное обеспечение ISP для обнаружения спама, такое как SpamAssassin , сотрудничающих интернет-провайдеров отправляет контрольные суммы всех электронных писем в централизованную службу, такую ​​как DCC . Если количество отправленных нечетких контрольных сумм превышает определенный порог, база данных отмечает, что это, вероятно, указывает на спам. Пользователи услуг интернет-провайдера аналогичным образом генерируют нечеткую контрольную сумму для каждого своего электронного письма и запрашивают у службы вероятность спама. [5]

Общие Соображения

Сообщение длиной m бит можно рассматривать как угол m -мерного гиперкуба . Эффект алгоритма контрольной суммы, который дает n -битную контрольную сумму, состоит в том, чтобы сопоставить каждое m -битное сообщение с углом большего гиперкуба с размерностью m + n . Углы этого гиперкуба размером 2 m + n представляют все возможные полученные сообщения. Действительные полученные сообщения (те, которые имеют правильную контрольную сумму) составляют меньший набор, с углами всего 2 метра .

Однобитовая ошибка передачи тогда соответствует смещению из допустимого угла (правильного сообщения и контрольной суммы) в один из m соседних углов. Ошибка, затрагивающая k бит, перемещает сообщение в угол, удаленный на k шагов от правильного угла. Цель хорошего алгоритма контрольной суммы — разнести допустимые углы как можно дальше друг от друга, чтобы увеличить вероятность того, что «типичные» ошибки передачи окажутся в недопустимом углу.

Смотрите также

Общая тема

Исправление ошибки

Хэш-функции

Файловые системы

Связанные понятия

Рекомендации

  1. ^ «Определение КОНТРОЛЬНОЙ СУММЫ». www.merriam-webster.com . Архивировано из оригинала 10 марта 2022 г. Проверено 10 марта 2022 г.
  2. Хоффман, Крис (30 сентября 2019 г.). «Что такое контрольная сумма (и почему вас это должно волновать)?». Как компьютерщик . Архивировано из оригинала 9 марта 2022 г. Проверено 10 марта 2022 г.
  3. ^ Фэйрхерст, Горри (2014). «Контрольные суммы и проверки целостности». Архивировано из оригинала 8 апреля 2022 года . Проверено 11 марта 2022 г.
  4. ^ "SAE J1708". Квасер.com. Архивировано из оригинала 11 декабря 2013 года.
  5. Ссылки _ Апач. Архивировано из оригинала 31 августа 2020 года . Проверено 7 января 2020 г.

дальнейшее чтение

Внешние ссылки