Хеш-функция

Хеш-функция, отображающая имена в целые числа . Имена «Джон Смит» и «Сандра Ди» совпадают.

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

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

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

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

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

определение

Отображение называется хеш-функцией, если оно выполняется. В частности, хэш - таблица содержит размер . Набор представляет данные для хеширования и также называется набором ключей; сумма - это количество возможных значений хеш-функции. Как правило, количество значений хэша выбрано в качестве начального сегмента натуральных чисел: . Этот набор также называется адресным пространством . ${\ displaystyle h \ двоеточие K \ rightarrow S}$${\ Displaystyle | К | \ geq \ | S |}$${\ displaystyle h}$${\ displaystyle | S |}$${\ displaystyle K}$${\ displaystyle S}$${\ Displaystyle S \ substeq \ влево \ {0, \ dotsc, м-1 \ вправо \}}$

Как правило, на практике, только небольшое подмножество ключа всегда с отображается. Сумма - это фактически используемые хеш-значения. ${\ displaystyle K '{} \ substeq {} K}$${\ displaystyle h}$${\ Displaystyle S ': = \ {h (k) | k \ in K' \}}$

Соотношение обеспечивает коэффициент занятости. ${\ Displaystyle \ бета = {\ гидроразрыва {\ left | S '\ right |} {\ left | S \ right |}}}$

Падение известно как столкновение. Инъективны хэш - функция называется совершенным, отчасти потому , что он не создает каких - либо столкновений. ${\ Displaystyle к \ не = к '\ земля ч (к) = ч (к')}$

критерии

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

Следующие критерии играют разную роль в зависимости от приложения:

• если хэш функция а укомплектованный для обеспечения доступа в хэш - таблице базы данных: Обрезка консервирование
• для криптологических хеш-функций: хаос или лавинный эффект - хеш-функция должна иметь хорошее распространение ; Подобные исходные элементы (входные значения) должны приводить к совершенно разным хеш-значениям. В идеале изменение бита на входе изменяет в среднем половину всех битов в результирующем хэш-значении.
• С криптологическими хэш-функциями: Путаница - по хеш-значению нельзя сделать никаких выводов о входном значении.
• на Криптолоджик хэш - функций: Un необратимости - Должна быть возможность не практический метод , который определяет значение хеш - значение входного сигнала.

Приложения

Хеш-функции обычно используются для

• назначить адрес памяти сложному объекту . Например, «Джон Доу» можно поместить в папку M по первой букве фамилии.
• вычислить короткую контрольную сумму по объекту. Примерами являются контрольная сумма ISBN и циклическая проверка избыточности для обнаружения ошибок передачи файлов.
• Идентифицируйте контент почти однозначно, но с небольшим пространством для хранения , не раскрывая ничего о контенте, например, в криптографии .

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

Одна цифра контрольная сумма является очень простой хэш - функции. Он присваивает однозначное число любому числу, например, 25 отображается на 2 + 5 = 7. Однако эта контрольная сумма плохо подходит в качестве контрольной суммы, поскольку перестановка цифр - типичный случай при вводе длинных чисел - не распознается. Число 52 имеет ту же контрольную сумму 2 + 5 = 7. Контрольные суммы как для ISBN книги или контрольной суммы CRC-32 файла, например Б. При проверке файла, загруженного из Интернета, на наличие ошибок передачи, лучше подходят для обнаружения таких ошибок.

Bei der Identifikation von Inhalten mit kryptologischen Hashfunktionen ist es nicht nur wichtig, dass sich der gesamte Hashwert mit allen Bits bei jeder kleinen Modifikation scheinbar zufällig ändert und dass es fast unmöglich ist, einen zweiten Inhalt mit demselben Hashwert zu erzeugen, um einen Komplettaustausch des Inhaltes избегать. Не менее важно, чтобы контент нельзя было восстановить по хеш-значению . Если вы обменялись двумя документами и хотите проверить успешность передачи, например, по телефону, достаточно проверить правильность значения хеш-функции по телефону. Если разговор прослушивается , ничего не раскрывается о содержании сообщения, даже если его части уже известны.

Базы данных

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

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

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

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

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

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

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

Примеры

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

Пошаговые хэш-функции в основном используются в P2P-сетях, в которых значение хеш-функции вычисляется для меньших частей файла, а затем на основе этих значений вычисляется общее значение. В сетях Gnutella G2, Shareaza и Direct Connect это, например, хэш- функции Tiger Tree .

Поиск файлов на основе хэш-значения их содержимого защищен патентом на программное обеспечение, по крайней мере, в США. Владелец преследует программы и компании, которые позволяют искать файлы на основе этой системы, включая компании, которые хотят идентифицировать поставщиков нелицензионного контента от имени RIAA или MPA .

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

Криптология

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

Алгоритмы хеширования

На практике для создания хорошей хеш-функции часто можно использовать эвристические методы. Качественная информация о распределении ключей может быть полезна в этом процессе проектирования. В общем, хеш-функция должна зависеть от каждого отдельного бита ключа, так что два ключа, которые отличаются только одним битом или битовой последовательностью, независимо от того, находится ли последовательность в начале, в конце или в середине key или присутствует, отображает весь хэш ключа на разные значения. Поэтому хеш-функция, которая просто извлекает часть ключа, не подходит. Если два ключа представляют собой просто перестановки друг друга, например B. 256 и 625, они также должны быть хешированы в разные значения.

Эвристические методы - это хеширование путем деления и хеширование путем умножения.

Хеширование по делению

Этот метод назначает ключ хэш-значению, вычисляя остаток ключа при делении на размер хеш-таблицы . То есть хеш-функция определяется как ${\ displaystyle h}$

${\ Displaystyle ч (\ mathrm {ключ}) = \ mathrm {ключ} \ \ mathrm {мод} \ \ mathrm {tableize}}$

Поскольку требуется только одна операция деления, хеширование делением выполняется довольно быстро. При использовании метода деления следует избегать определенных значений размера хеш-таблицы. Это не должно быть степень числа. Если есть, то значение хеш-функции всегда равно последним битам . Если мы не знаем, что все низкоразрядные шаблоны равновероятны, лучше сделать хеш-функцию так, чтобы она зависела от всех битов ключа. Было обнаружено, что метод деления дает наилучшие результаты, когда размер хеш-таблицы является простым числом . Простое число, не слишком близкое к степени двойки , часто бывает хорошим выбором с учетом размера хеш-таблицы.${\ displaystyle \ mathrm {tableize} = r ^ {p}}$${\ Displaystyle ч (\ mathrm {ключ})}$${\ displaystyle \ mathrm {ключ}}$${\ displaystyle p}$

Хеширование умножением

В этом методе ключ умножается на постоянное действительное число в диапазоне, а десятичные разряды берутся из. Затем это значение умножается на размер хеш-таблицы, и целая ее часть вычисляется с помощью функции округления . Хеш-функцию можно представить как ${\ displaystyle k}$ ${\ displaystyle c}$${\ displaystyle 0 <c <1}$ ${\ Displaystyle к \ cdot c}$${\ displaystyle h}$

${\ displaystyle h (\ mathrm {key}) = \ mathrm {floor} (\ mathrm {tablesize} \ cdot (\ mathrm {key} \ cdot c \ \ mathrm {mod} \ 1))}$

Одним из преимуществ является то, что размер хеш-таблицы не критичен. Обычно это степень двойки, потому что в этом случае хеш-функция может быть реализована быстрее. Хотя этот метод работает с любыми действительными числами , с некоторыми значениями он работает лучше, чем с другими.${\ displaystyle c}$

Известные хэш-функции

Например, хорошо известные хэш-функции:

• Brent хеширование
• Метод остатка от деления
• Двойное хеширование
• Кукушка хеширования
• Мультипликативный метод
• Метод центрального квадрата
• Метод разложения
• Анализ цифр

Хеш-функции на основе решеток

• Аджтай
• Micciancio
• Розы пайкерта
• Быстрое преобразование Фурье (хеш-функция БПФ)
• Плеть

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

• Контрольная сумма Флетчера
• Орел-32
• CRC (циклический контроль избыточности)
• паритет
• Контрольная сумма

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

• MD2 , MD4 , MD5
• Алгоритм безопасного хеширования (SHA)
• РИПЭМД-160
• тигр
• HAVAL
• Водоворот

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

Хеш-функции паролей

• LM хеш
• PBKDF2
• Bcrypt
• Scrypt
• Аргон 2

литература

• Дональд Э. Кнут : Искусство программирования . 2-е издание. Том 3. Эддисон-Уэсли, 1998, ISBN 0-201-89685-0 , стр. 513 ff . 
• Томас Х. Кормен, Чарльз Э. Лейзерсон , Рональд Л. Ривест , Клиффорд Штайн: алгоритмы. Введение . 2-е издание. Ольденбург, Мюнхен / Вена 2007, ISBN 978-3-486-58262-8 , стр. 221 ff . 
• Ляньхуа Чи, Синцюань Чжу: Методы хеширования: обзор и таксономия . В: ACM Computing Surveys (CSUR) . Лента 50 , нет. 1 , апрель 2017, 11, DOI : 10,1145 / 3047307 . 

веб ссылки

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

• CRC Press - Справочник по прикладной криптографии (глава 9) (PDF; 471 kB)
• Построение хеш-функций (PDF; 841 kB)
• Онлайн-генератор для вычислений хешей (md, sha, ripemd, whirlpool, tiger, snefru, gost, adler, cc, salsa, haval)

Индивидуальные доказательства

1. ↑ ^{a b c} GeeksforGeeks: что такое хеш-функции и как выбрать хорошую хеш-функцию?
2. ↑ CP Schnorr, Serge Vaudenay: Параллельное хеширование БПФ . В: Fast Software Encryption, стр. 149-156, 1993.
3. ↑ К. Бентахар, Д. Пейдж, Дж. Х. Сильверман, М.-Дж. Сааринен, NP Smart: LASH . 2-й семинар NIST по криптографическому хешированию, 2006 г.
4. ↑ github.com