Хеш-функция


Хеш-функция

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

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

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

Содержание

Контрольные суммы

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

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

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

Платой за столь высокую скорость является отсутствие криптостойкости — легкая возможность подогнать сообщение под заранее известную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.

Простейшим случаем такого алгоритма является деление сообщения на 32- или 16- битные слова и их суммирование, что применяется, например, в TCP/IP.

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

Криптографические хеш-функции

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

  • Стойкость к коллизиям первого рода: для заданного сообщения ~M должно быть практически невозможно подобрать другое сообщение ~M', имеющее такой же хеш. Это свойство также называется необратимостью хеш-функции.
  • Стойкость к коллизиям второго рода: должно быть практически невозможно подобрать пару сообщений ~(M, M'), имеющих одинаковый хеш.

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

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

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

Применение хеширования

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

  • хорошая перемешиваемость данных
  • быстрый алгоритм вычисления

Сверка данных

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

Проверка на наличие ошибок

Например, контрольная сумма может быть передана по каналу связи вместе с основным текстом. На приёмном конце, контрольная сумма может быть рассчитана заново и её можно сравнить с переданным значением. Если будет обнаружено расхождение, то это значит, что при передаче возникли искажения и можно запросить повтор.

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

Проверка парольной фразы

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

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP. В них хранятся лишь хеш-значения парольных фраз из учётных записей пользователей.

Ускорение поиска данных

Основная статья: Хеш-таблица

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

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

Список алгоритмов

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "Хеш-функция" в других словарях:

  • хеш-функция — Функция, которая при различных размерах входного значения имеет выход фиксированного размера. [http://www.morepc.ru/dict/] хэш функция — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики информационные технологии в… …   Справочник технического переводчика

  • хеш-функция — хеш фу/нкция, хеш фу/нкции …   Слитно. Раздельно. Через дефис.

  • хеш-функция — хеш ф ункция, и …   Русский орфографический словарь

  • Хеш функция Дженкинса — Криптографическая хеш функция Название Хэш функции Дженкинса Впервые опубликован 1997 Тип хеш функция Хэш функции Дженкинса представляют собой семейство хэш функций общего назначения для ключей переменной длины разработанных Бобом Дженкинсом.… …   Википедия

  • Криптографическая хеш-функция — Криптографической хеш функцией называется всякая хеш функция, являющаяся криптостойкой, то есть, удовлетворяющая ряду требований специфичных для криптографических приложений. Содержание 1 Требования 2 Принципы построения …   Википедия

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

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

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

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

  • Tiger (хэш-функция) — Tiger  хеш функция, разработанная Росом Андерсоном и Эли Бихамом в 1995 году. Tiger был предназначен для особенно быстрого выполнения на 64 разрядных компьютерах. Tiger не имеет патентных ограничений, может использоваться свободно как с… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.