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

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

Контрольная сумма — это небольшой блок данных, полученный из другого блока цифровых данных с целью обнаружения ошибок , которые могли возникнуть во время его передачи или хранения . Сами по себе контрольные суммы часто используются для проверки целостности данных , но на них не полагаются для проверки аутентичности данных . ^[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 $ м + н$ углы этого гиперкуба представляют все возможные полученные сообщения. Действительные полученные сообщения (те, которые имеют правильную контрольную сумму) составляют меньший набор, всего $2 м$ углы.

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

См. также

Общая тема

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

Хэш-функции

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

ZFS — файловая система, выполняющая автоматическую проверку целостности файлов с использованием контрольных сумм.

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

Ссылки

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

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

Купман, Филип; Дрисколл, Кевин; Холл, Брендан (март 2015 г.). «Код циклической избыточности и алгоритмы контрольной суммы для обеспечения целостности критически важных данных» (PDF) . Федеральное управление гражданской авиации. DOT/FAA/TC-14/49. Архивировано (PDF) из оригинала 18 мая 2015 г.
Купман, Филип (2023). «Алгоритмы модульного сложения контрольной суммы с большими блоками». arXiv : 2302.13432 [ cs.DS ].

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

[1] «Определение КОНТРОЛЬНОЙ СУММЫ» . www.merriam-webster.com . Архивировано из оригинала 10 марта 2022 г. Проверено 10 марта 2022 г.

[2] Хоффман, Крис (30 сентября 2019 г.). «Что такое контрольная сумма (и почему вас это должно волновать)?» . Как компьютерщик . Архивировано из оригинала 9 марта 2022 г. Проверено 10 марта 2022 г.

[3] Фэрхерст, Горри (2014). «Контрольные суммы и проверки целостности» . Архивировано из оригинала 8 апреля 2022 года . Проверено 11 марта 2022 г.

[4] «САЭ J1708» . Квасер.com. Архивировано из оригинала 11 декабря 2013 года.

[5] «IXхэш» . Апач. Архивировано из оригинала 31 августа 2020 года . Проверено 7 января 2020 г.

[1]

[2]

[3]

[4]

[5]