Что именно (и точно) является «хешем»?

38

Я слышал, что слово «хэш» используется в разных контекстах (все в мире вычислений) с разными значениями. Например, в книге «Изучите Python трудный путь» в главе о словарях говорится, что «Python называет их» диктами. «В других языках они называются хешами». «Итак, словари хешей являются?

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

Так что же это такое?

Может ли кто-нибудь (со временем и кто обладает знаниями) любезно объяснить мелкие мелочи "хеша (или хешей)"?

gracedlamb
источник
8
В Википедии есть подробные статьи о хеш-таблицах и криптографических хеш-функциях . Что вы ищете, чего нет в тех?
Дэвид Ричерби
1
Вы уже перечислили многократное использование термина "хэш", и это еще не все. Итак, как именно вы ожидаете получить ответ на вопрос «что именно?»
Рафаэль
4
В этом смысле «хэши» - это сокращение «хеш-таблиц», например таблиц, которые используют хеш-коды для организации ключей. Это все равно что называть бензин "газом" - вы не ожидаете, что "газ" будет газообразным или газы будут иметь бензоподобные свойства, не так ли? Это происходит постоянно с языком - сокращение, в частности, является очень распространенным источником совпадения слов.
Luaan
1
«Для этого слова нет определения - никто не знает, что такое хеш». - Словарь дьявола
jpmc26
Что касается различных направлений мысли о том, что такое хеш-функция: хеш-функция - это просто некая функция со множеством свойств, но она важна не по определению, а по свойствам, которые мы хотим получить, - которые мы получаем из того, как хотим использовать функцию - это актуально. Поскольку мы хотим использовать его для быстрого доступа к материалам, мы хотим, чтобы он был эффективно вычисляемым. Поскольку у нас нет доступного бесконечного пространства, мы хотим, чтобы кодомен был конечным. Поскольку мы хотим избежать коллизий настолько хорошо, насколько это возможно, мы хотим, чтобы хэш-функция равномерно распределяла хэши.
Г. Бах

Ответы:

44

Статья в Википедии о хэш-функциях очень хороша, но здесь я дам свое мнение.


Что такое хеш?

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

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

  1. Это должно быть легко вычислить и
  2. Выходы должны быть относительно небольшими.

Пример:

Скажем, мы хотим хешировать числа в диапазоне от 0 до 999 999 999 до нумерации от 0 до 99. Одна простая хеш-функция может быть .час(Икс)знак равноИксмодификация100

Общие дополнительные свойства:

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

  1. Однородность : часто мы хотим, чтобы хеши объектов были различимы. Более того, мы можем захотеть, чтобы хэши были «распространяющимися». Если я хочу хэшировать некоторые объекты до 100 сегментов (поэтому выходные данные моей хэш-функции представляют собой числа от 0 до 99), то я обычно надеюсь, что около 1/100 объектов попадут в сегмент 0, а около 1/100 - в ведро 1 и тд.

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

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

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


Некоторые приложения

Одним из распространенных приложений является структура данных, такая как хеш-таблица, которая является способом реализации словарей. Здесь вы выделяете некоторую память, скажем, 100 «ведер»; затем, когда вас попросят сохранить пару (ключ, значение) в словаре, вы хешируете ключ в число 0-99 и сохраните пару в соответствующем сегменте в памяти. Затем, когда вас просят найти ключ, вы хэшируете ключ на число 0-99 с той же хэш-функцией и проверяете этот сегмент, чтобы увидеть, есть ли этот ключ там. Если это так, вы возвращаете его значение.

Обратите внимание, что вы также можете реализовать словари другими способами, например, с помощью бинарного дерева поиска (если ваши объекты сопоставимы).

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

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

усул
источник
1
Хорошее объяснение, но я не согласен с «очень маловероятным». См: programmers.stackexchange.com/questions/49550/... : столкновение сделать происходят, а иногда и на удивление часто.
Оливье Дюлак
8
Также обратите внимание, что в контексте цитографии термин «хеш» очень сильно подразумевает «одностороннюю» операцию, которую на практике нельзя легко отменить. Когда его можно легко перевернуть, это называется «шифрование». Вот почему сотрудники Security.SE скажут вам всегда хэшировать пароли ваших клиентов, а не шифровать их.
Ixrec
4
Хэш, который не «распространяется», по-прежнему является хешем, но, возможно, не очень хорошим для вашего приложения.
Стоп Harm Monica
1
Конечно, это все хорошие моменты.
усул
10

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

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

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

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

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

Pharap
источник
2
Я не уверен, что действительно неправильно называть хеш-таблицу или хеш-функцию «хешем» (это не выглядит хуже, чем, например, использование «Вашингтона» в значении «Соединенные Штаты», как в « Вашингтон осторожно приветствовал заявление Китая "). Но я согласен, что это сбивает с толку, и это хорошо, что вы очень ясно об этом в своем ответе.
Дэвид Ричерби
1
@DavidRicherby Формально, я бы сказал, что "хэш" работы не определен. «Хэш-функция», «хэш-значение», «хэш-таблица» и «хэширование строки» имеют точные математические определения, но «хэш» неоднозначен. Точно так же я знаю, что вы подразумеваете под «Вашингтоном», но ваше предложение по-прежнему имеет смысл, если я интерпретирую «Вашингтон» в значении «Джордж Вашингтон» или «Дензел Вашингтон», а не «Город Вашингтон», что весьма неформально. обратиться к федеральному правительству. Итог: будьте осторожны, чтобы не перепутать «зная, что вы имеете в виду» для строгого формального определения.
Майк Оунсворт
@DavidRicherby Это не совсем аналогия. Неверность спорна, а неформальность - нет.
Pharap
2

Хеш-функция - это, в общем, любая функция, в которой изображение меньше домена . Вывод такой функции f(x)можно назвать «хешем x».

В информатике мы обычно сталкиваемся с двумя приложениями хеш-функций.

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

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

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

Стоп Харминг Моника
источник
И у меня все еще есть возражения против вашего первого предложения, потому что при хешировании 32-символьных паролей с помощью SHA-512 пространство ввода фактически меньше, чем пространство вывода. При объединении хеш-функций домен и диапазон совпадают; размер входного пространства не имеет значения. Ответ Фарапа имеет правильное определение: «Хеш-функция - это любая функция с выходом фиксированной длины». Вот и все, что вам нужно, все остальные условия, о которых вы говорите, вытекают из этого.
Майк Оунсворт
@MikeOunsworth, но доменом SHA-512 являются двоичные строки произвольной длины. Полагаю, я мог бы украсть формулировку Фарапса, но я пытался сделать условия явными для выгоды ОП. Я на самом деле не уверен, что «с фиксированной длиной» необходимо, ни однозначно определены.
Стоп Harm Monica
@OrangeDog Хорошо, но я могу обернуть SHA-512 внутри функции, MikesHash()которая вызывает строки длиной 12, передает их в SHA-512 и возвращает результат. Я почти уверен, что MikesHash()все еще соответствует определению хэш-функции. (На практике вы правы, хеш-функции, которые мы используем, принимают входные данные произвольной длины, но я не думаю, что что-то не может быть хеш-функцией, если это не так.)
Майк Оунсворт,
@MikeOunsworth в равной степени я могу обернуть его так, чтобы вывод был усеченным или дополненным, если msb равен единице. Выход больше не имеет фиксированной длины, но это все еще хэш-функция?
Стоп Harm Monica
@OrangeDog Я бы сказал нет. Я всегда говорил, что хеш-функция должна отображаться на вывод фиксированного размера, но размер ввода не имеет значения. Мы очень далеко отошли от темы. В вашем ответе есть хорошие вещи, просто будьте осторожны с вашим формальным определением ;-)
Майк Оунсворт,
0

Отличный вопрос Василий Аджит,

Вот моя точка зрения на то, что хэш-то для чего я работаю сегодня.

*

Используйте контрольную сумму, чтобы убедиться, что тарболл соответствует странице загрузки.

*

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

hash - это значение / строка / что угодно /, убедитесь, что оно совпадает на вашем компьютере с источником загрузки.

Джесси МакДугалл
источник
3
Это только одно использование для хэша. Есть много других применений.
Юваль Фильмус
Добро пожаловать на сайт! Использование криптографических хэшей в качестве контрольных сумм уже охватывается принятым ответом, поэтому ваш ответ не добавляет ничего нового, занимая при этом много места на экране.
Дэвид Ричерби
-1

Я постараюсь просто добавить краткое изложение того, что говорят другие.

Хэш-функция

Существует особый вид функций, называемых хэш-функциями.

«SHA256 - это широко известная хеш-функция, которая криптографически безопасна»

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

Хеш-таблица

Хеш-таблица - это структура данных для быстрого поиска. Он использует хеш-функции внутри, отсюда и название.

«Базы данных используют хеш-таблицы и деревья поиска для ускорения выполнения поисковых запросов»

гашиш

  1. словарь абстрактный тип данных

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

  1. результат применения хэш-функции для некоторого ввода

Msgstr "MD5 хэши образов .iso предоставляются для проверки их целостности после загрузки".

nponeccop
источник