Хэш-функция

Алгоритмы   11 Июль 2012  Автор статьи:  

Хэш-функция — функция, отображающая множество ключей в некоторое конечное множество(значений). Множество значений значительно меньше по мощности множества ключей. Множество ключей может быть неограниченным, но множество значений — всегда ограничено. Выражаясь математическим языком, хэш-функция — такая функция h: K\to H |K|>>|H|, где К и Н — множества ключей и значений соответственно.
Свойства хэш-функции:

  • Если  x=y \Rightarrow h(x)=h(y)
  • Если  x\ne y \Rightarrow h(x)=h(y)
  • Если  h(x)=h(y) \Rightarrowвелика вероятность, что  x=y, в противном случае такая ситуация называется коллизией

По своему назначению хэш-функции делятся на 3 вида:

  1. Хэш-функции, обеспечивающие проверку целостности данных. При передаче пакетов данных по сети используются функции, вычисляющие хэш от пакета, и результат этой хэш-функции также передается по сети. При приме пакета снова вычисляется его хэш и сравнивается с полученным по сети. Если во время передачи возникли ошибки и пакеты исказились, то с очень большой вероятностью хэш от пакета не совпадет с полученным хэшем, в результате чего испорченный пакет будет заново передан. Такие хэш-функции вычисляются очень быстро, имеют небольшое количество хэш-значений, но они очень неустойчивы. Примером такой хэш-функции является CRC32, имеющая 2^{32} различных значений
  2. Криптографические хэш-функции Данный функции применяются для защиты информации от несанкционированного доступа (НСД). Примером таких функций являются MD5, SH1 и SH2. Эти функции позволяют проверить наличие искажение данных при передачи по сети от НСД, в отличие от предыдущего случая, когда проверялось наличие искажений в результате ошибок передачи. Сравнивая хеш от полученных данных с истинным хэшем (он общедоступен с источника данных) можно судить, подверглись ли данные при передаче НСД или нет. Такие хэш-функции имеют долгое время работы и большое количество значений, поиск коллизий в них также осложнен.
    Еще хэш-функции используют в базах данных для хранения паролей. Так как всегда есть вероятность утечки информации, то пароли хранят не в открытом виде, а в виде хэшей, проверяя доступное значение хэша с результатом хэширования пароля при аутентификации. Как правило большинство пользователей будут пользоваться паролями «12345» или «0000», в результате чего пароль можно подобрать а затем и легко можно вскрыть саму хэш-функцию и узнать пароли других пользователей. Для защиты от этого пред каждым паролем пишется уникальные для данного пользователя несколько(как правило 2) дополнительных символов, которые называются солью, и только потом производится хэширование. Такой подход позволяет сохранить пароли других не взломанных пользователей.
  3. Организация эффективных структур данных.Использование хэш-функции позволяет компактно и довольно упорядоченно организовывать данные в специальных структурах, называемыми хэш-таблицами. Более подробно о хэш-таблицах будет рассмотрено в следующей статье.

Научиться программировать

  • на Delphi

  • на Java

  • на C++