Обзор современных алгоритмов подсчета контрольной суммы

Сложно переоценить важность такого устройства, как персональный компьютер. Компьютер превратился  в широко распространённое и гибкое средство для решения разнообразных  задач.Одной из таких задач является передача данных. И вот здесь возникают разные трудности. Допустим, осуществилась передача файла. Есть вероятность, что в пути произойдёт неприятность, и файл будет испорчен. Как удостовериться, что файл был передан верно. На помощь приходят контрольные суммы. Именно с помощью них можно удостовериться, правильно ли был передан файл или с ошибками. Цель работы: рассмотреть современные алгоритмы подсчета контрольной суммы.Задачи:  1. Изучить литературу по данному вопросу.

               2. Рассмотреть каждый алгоритм  в отдельности.

               3. Выявить достоинства и недостатки  алгоритмов.

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

Циклический избыточный код (англ. Cyclic redundancy check, CRC) — алгоритм вычисления контрольной суммы, предназначенный для проверки целостности данных.

Программы-архиваторы включают CRC исходных данных в созданный архив  для того, чтобы получающий мог  удостовериться в корректности полученных данных. Такая контрольная сумма  проста в реализации и обеспечивает низкую вероятность возникновения  коллизий.

Коллизией хеш-функции   называется два различных входных блока данных   и   таких, что  Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму.

Основная идея алгоритма CRC состоит в представлении сообщения  в виде огромного двоичного числа, делении его на другое фиксированное  двоичное число и использовании  остатка от этого деления в  качестве контрольной суммы. Получив  сообщение, приёмник должен выполнить аналогичное действие и сравнить полученный результат с принятой контрольной суммой. Сообщение считается достоверным, если выполняется это равенство.

Алгоритм CRC базируется на полиномиальной арифметике, а это означает, что  сообщение, делитель и остаток могут  быть представлены в виде полиномов  с двоичными коэффициентами или  в виде строки битов, каждый из которых  является коэффициентом полинома.

В CRC алгоритме используется полиномиальная арифметика по модулю 2. Это означает, что действия, выполняемые  во время вычисления CRC, являются арифметическими  операциями без учёта переноса. То есть сложение и вычитание выполняются  побитово без учёта переноса, благодаря чему эти две операции дают эквивалентный результат. Операции сложения и вычитания в этом случае идентичны операции XOR (исключающее ИЛИ).

1. MD5-алгоритм.

MD5 (англ. Message Digest 5) — 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института в 1991 году. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Зная MD5-образ (называемый также MD5-хеш или MD5-дайджест), невозможно восстановить входное сообщение, так как одному MD5-образу могут соответствовать разные сообщения.  Используется для проверки подлинности опубликованных сообщений путём сравнения дайджеста сообщения с опубликованным. Эту операцию называют «проверка хеша» (hashcheck).

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

Ниже приведены 5 шагов алгоритма:

Шаг 1. Выравнивание потока.

Шаг 2. Добавление длины сообщения.

Шаг 3. Инициализация буфера.

Шаг 4. Вычисление в цикле.

Шаг 5. Результат вычислений.

2. Adler-32-Алгоритм

Adler-32 — хеш-функция, разработанная Марком Адлером. Является модификацией контрольной суммы Fletcher. Вычисляет значение контрольной суммы в соответствии для массива байт или его фрагмента. Данный алгоритм расчёта контрольной суммы отличается от CRC32 производительностью.

Так же как и  в случае контрольной суммы Fletcher, при разработке суммы Adler стояла задача получения контрольной суммы с эффективностью обнаружения ошибок сравнимой с CRC. Хотя показатели поиска ошибок контрольных сумм Adler и Fletcher практически такие же как и у относительно слабых CRC, они ведут себя гораздо хуже, чем хорошие CRC, в некоторых важных случаях

3. Достоинства и недостатки алгоритмов  подсчета контрольной  суммы