ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Значение хеш-функции Adler-32

ВВЕДЕНИЕ

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

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

Хеширование (иногда пишется хэширование, англ. hashing) – преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения.

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

Существует множество алгоритмов хеширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшим примером хеш-функции может служить контрольная сумма. Примером такого алгоритма является деление сообщения на 32или 16битные слова и их суммирование, что примняется, например, в протоколе TCP/IP. По скорости вычисления такие алгоритмы в сотни раз быстрее, чем алгоритмы для вычисления криптографических хеш-функций, и значительно проще в аппаратной реализации.

Платой за столь высокую скорость является отсутствие криптостойкости –легкая возможность подогнать сообщение под заранее известную сумму. Поэтому такие быстрые и простые алгоритмы используются только для защиты от непреднамеренного искажения информации.

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

- необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо, чтобы найти блок данных X, для которого H(X) =m;

- стойкость к коллизиям первого рода: для заданного сообщения Mдолжно быть вычислительно неосуществимо подобрать другое сообщение N, для которого H(N) =H(M);

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

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

Значение хеш-функции Adler-32

Одна из самых простых хеш-функций, которую можно придумать - сумма всех байт (или слов) по какому-то модулю (например, значению, ограниченному разрядной сеткой). Несмотря на высокую производительность, такая хеш-сумма дает много коллизий. И объяснение тому просто: «От перемены мест слагаемых сумма не меняется». Алгоритм Adler'а почти настолько же прост, только учитывает расположение слагаемых. Хеш-сумма Adler32 состоит из двух 16-разрядных слов. Первое слово — это сумма всех байт по модулю. Второе — сумма значений первого слова на каждой итерации по этому же модулю.

Если длина входной последовательности - N, то второе слово можно представить как сумму произведений i-го байта на (N i + 1). Например, для последовательности 1, 2, 3, второе слово будет равным 1 + (1 + 2) + (1 + 2 + 3), или же 1•3 + 2•2 + 3•1. Таким образом, если переставить два байта во входной последовательности, то сумма поменяется из-за изменения коэффициентов при слагаемых.

Модуль для Adler32 выбран как наибольшее простое число, которое меньше 216. Пока я тут это пишу, читатель, должно быть, уже успел прикинуть, что это число — 65521. Такой выбор должен улучшить вероятностные характеристики хеш-функции. Начальное значение суммы (первого слова) — 1.

Следует заметить, что данный хеш не является достаточно надежным. Вероятность коллизий у него даже выше, чем у CRC32. При этом Adler32 быстрее CRC32 в несколько раз. Это может дать преимущество в задачах, в которых после сравнения хеша на равенство в случае успеха производится более надежное сравнение (например, по криптографическому хешу или побайтовое сравнение).

Прямая реализация алгоритма выглядит следующим образом, приложение 1.

Основная оптимизация здесь — это выполнения операции остатка от деления каждые NMAX байт вместо одного. NMAX — это максимальное число, при котором не происходит переполнение sum2. Вычислить его можно, исходя из того, что sum2 является суммой арифметической прогрессии с разностью d=255 (берем наихудший случай). Так, при 32-разрядном представлении чисел, получаем

(1 • 2 + 255 • (NMAX 1)) • NMAX/2 = 232 1

Решая квадратное уравнение, получаем NMAX = 5552 с учетом того, что оно должно быть кратно 16.

Макрос DO16(buf) разворачивается в следующее выражение:

adler += buf[0]; sum2 += adler; adler += buf[1]; sum2 += adler; ...

adler += buf[15]; sum2 += adler;

Данная реализация алгоритма работает в 5-6 раз быстрее, чем реализация «в лоб».

Превращаем Adler32 в кольцевой хеш.

Как изменится хеш-сумма, если из последовательности байт убрать первый, а в конец добавить новый? Очевидно, что первое слово «увеличится» на разность нового байта и старого. Что касается второго слова, то значение первого байта учтено в хеше то количество раз, каким является размер блока. Отняв от предыдущего значения слова произведение длины последовательности и значения первого байта, мы получим хеш, соответствующий последовательности без первого байта. Теперь добавим новое значение первого слова, отнимем единицу (иначе она будет учтена дважды) и получим новый хеш блока, смещенного на 1 байт вправо. При этом берем полученные значения по модулю, приложение 2.

Тут возможны отрицательные промежуточные значения, поэтому при операциях сравнения и модуля приходится приводить переменные и константы к числам со знаком. Для избежания переполнения на 32-разрядной архитектуре при перемножении длины блока на старый байт длина блока не должна превышать 8МБ. Функцию желательно объявить как inline, чтобы не расходовать дополнительное время на вызов функции и передачу аргументов.

Очевидно, у процесса оптимизации нет предела. И данная реализация тому не исключение. Например, можно изменить тип результата, возвращаемый функцией adler32 на структуру, содержащую два 32-разрядных слова, что может уменьшить количество ненужных операций по упаковке и распаковке хеш-суммы.