Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эффект типичной функции контрольной суммы ( утилита Unix cksum )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общая тема

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

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

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

Хеш-функции

  • Список хеш-функций
  • Алгоритм Луна
  • Бит четности
  • Подвижная контрольная сумма
  • Алгоритм Верхоффа
  • ZFS  - файловая система, которая выполняет автоматическую проверку целостности файлов с использованием контрольных сумм.

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

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

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

  1. ^ "SAE J1708" . Kvaser.com. Архивировано из оригинального 11 декабря 2013 года.
  2. ^ «IXhash» . Apache . Дата обращения 7 января 2020 .

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

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