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

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью , добавив ссылки на дополнительные источники . Найти источники:  «Checksum»  -  новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2018 г. )

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

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

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

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

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

Алгоритмы [ править ]

Байт четности или слово четности [ править ]

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

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

Дополнение суммы [ править ]

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

В зависимости от позиции [ править ]

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

Нечеткая контрольная сумма [ править ]

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

Общие соображения [ править ]

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

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

См. Также [ править ]

Общая тема

• Алгоритм
• Контрольная цифра
• Алгоритм дамма
• Гниль данных
• Проверка файла
• Контрольная сумма Флетчера
• Последовательность проверки кадра
• cksum
• md5sum
• sha1sum
• Parchive
• Сумма (Unix)
• Контрольная сумма SYSV
• Контрольная сумма BSD
• xxHash

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

• Код Хэмминга
• Контрольная сумма заголовка IPv4

Хеш-функции

• Список хеш-функций
• Алгоритм Луна
• Бит четности
• Скользящая контрольная сумма
• Алгоритм Верхоффа

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

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

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

• Изопсефия
• Гематрия

Ссылки [ править ]

Внешние ссылки [ править ]

Реализация алгоритма Викибука имеет страницу по теме: Контрольные суммы

• Аддитивная теория контрольных сумм (C) от Barr Group
• Практическое применение криптографических контрольных сумм