Хеш-функции: от А до Б.

Discussion in 'Безопасность и Анонимность' started by c0n Difesa, 18 Nov 2009.

  1. c0n Difesa

    c0n Difesa Member

    Joined:
    1 Jan 2009
    Messages:
    133
    Likes Received:
    66
    Reputations:
    18
    Введение. Зачем все это?


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

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

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


    Используемые термины.

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

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

    Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение i = hash(key) играет роль индекса в массиве H. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива H.

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


    Какой должна быть хорошая хеш-функция?

    Хорошая хеш-функция должна (приближенно) удовлетворять предположениям равномерного хеширования: для очередного ключа все m хеш-значений должны быть равновероятны. Чтобы предположение имело смысл, фиксируем распределение вероятностей P на множестве U; будем предполагать, что ключи выбираются из U независимо друг от друга, и каждый распределен в соответствии с P. Тогда равномерное хеширование означает, что:
    Code:
    SUM(P(k)) = 1/m  (1)
    К сожалению, распределение P обычно неизвестно, так что проверить это невозможно (да и ключи не всегда разумно считать независимыми).
    Изредка распределение Р бывает известно. Пусть, например, ключи — случайные действительные числа, независимо и равномерно распределённые на про¬межутке [0,1). В этом случае легко видеть, что хеш-функция h(k) = [km] удовлетворяет условию (1).

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

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

    Ключи как натуральные числа.

    Обычно предполагают, что область определения хеш-функции (ключи) — множество целых неотрицательных чисел. Если ключи не являются натуральными числами, их обычно можно преобразовать к такому виду (хотя числа могут получиться большими). Например, последовательности символов можно интерпретировать как числа, записанные в системе счисления с подходящим основанием: идентификатор pt —это пара чисел (112,116) (таковы ASCII-коды букв р и t), или же число (112 * 128) + 116 = 14452 (в системе счисления по основанию 128). Далее мы всегда будем считать, что ключи — целые неотрицательные числа.

    Деление с остатком.

    Построение хеш-функции методом деления с остатком (division method) состоит в том, что ключу k ставится в соответствие остаток от деления k на m, где m— число возможных хеш-значений:

    Code:
    h(k) = k mod m
    Например, если размер хеш-таблицы равен m = 12 и ключ равен 100, то хеш-значение равно 4.
    При этом некоторых значений m стоит избегать. Например, если m = 2^p то h(k) — это просто р младших битов числа k. Если нет уверенности, что все комбинации младших битов ключа будут встречаться с одинаковой частотой, то степень двойки в качестве числа то не выбирают.

    Хорошие результаты обычно получаются, если выбрать в качестве т простое число, далеко отстоящее от степеней двойки. Пусть, например, нам надо поместить примерно 2000 записей в хеш-таблицу с цепочками, причем нас не пугает возможный перебор трёх вариантов при поиске отсутствующего в таблице элемента. Что ж, воспользуемся методом деления с остатком при длине хеш-таблицы m = 701. Число 701 простое, 701 =(прибл.) 2000/3, и до степеней двойки от числа 701 тоже далеко. Стало быть, можно выбрать хеш-функцию вида
    Code:
    h(k) = k mod 701
    На всякий случай можно ещё поэкспериментировать с реальными данными предмет того, насколько равномерно будут распределены их хеш-значения.

    Умножение.

    Построение хеш-функции методом умножения (multiplication method) состоит в следующем. Пусть количество хеш-значений равно m. Зафиксируем константу А в интервале 0 < А < 1, и положим
    Code:
    h(k) = [m(kA mod 1)]
    , где (k A mod 1)—дробная часть kА.

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

    Метод умножения работает при любом выборе константы А, но некоторые значения А могут быть лучше других. Оптимальный выбор зависит от того, какого рода данные подвергаются хешированию.
    В своей книге Кнут детально рассматривает эту особенность и приходит к выводу, что значение
    A = 0,61 является довольно удачным.


    Универсальное хеширование.

    Если недоброжелатель будет специально подбирать данные для хеширования, то (зная функцию h) он. может устроить так, что все m ключей будут соответствовать одной позиции в таблице, в результате чего время поиска будет равно O(m). Любая фиксированная хеш-функция может быть дискредитирована таким образом. Единственный выход из положения — выбирать хеш-функцию случайным образом, не зависящим от того, какие именно данные вы хешируете. Такой подход называется универсальным хешированием (universal hashing). Что бы ни предпринимал ваш недоброжелатель, если он не имеет информации о выбранной хеш-функции, среднее время поиска останется хорошим.

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

    При случайном выборе хеш-функции вероятность коллизии между двумя данными ключами должна равняться вероятности совпадения двух случайно выбранных хеш-значении (которая равна 1/m).


    От себя.

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

    Источник: "Алгоритмы: построение и анализ" (Кормен Т., Лейзерсон Ч., Ривест Р.)
     
    #1 c0n Difesa, 18 Nov 2009
    Last edited: 20 May 2010
    3 people like this.
  2. scrat

    scrat кодер

    Joined:
    8 Apr 2007
    Messages:
    625
    Likes Received:
    541
    Reputations:
    3
    Топик скорее в раздел программирования, чем безопасности.

    Данный материал очень ок изложен в виде видео-лекций автором книги-источника.
     
Loading...