Хеши целых чисел в Python

#python #криптография #хеширование #структуры_данных

Добрый день.

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

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

В чём же дело? Я что-то неправильно понимаю о концепции хорошей хеш-функции? Или
в питоновских словарях и множествах не используется напрямую результат функции hash(),
а как-то дополнительно обрабатывается?
    

Ответы

Ответ 1

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


  Hash values are integers. They are used to quickly compare dictionary
  keys during a dictionary lookup. Numeric values that compare equal
  have the same hash value (even if they are of different types, as is
  the case for 1 and 1.0).


По поводу идущих подряд ключей:

In [37]: hash('aaaa')
Out[37]: 5927745366728125705

In [38]: hash('aaab')
Out[38]: 3762861188151674483

In [39]: hash('aaac')
Out[39]: -5197229166136799781


Для "криптографических" целей стоит обратить внимание на модуль hashlib:

In [35]: hashlib.sha512(b'aaa').hexdigest()
Out[35]: 'd6f644b19812e97b5d871658d6d3400ecd4787faeb9b8990c1e7608288664be77257104a58d033bcf1a0e0945ff06468ebe53e2dff36e248424c7273117dac09'

In [36]: hashlib.sha512(b'123').hexdigest()
Out[36]: '3c9909afec25354d551dae21590bb26e38d53f2173b8d3dc3eee4c047e7ab1c1eb8b85103e3be7ba613b31bb5c9c36214dc9f14a42fd7a2fdb84856bca5c44c2'


Пример из доки с использованием "соли":

>>> import os
>>> from hashlib import blake2b
>>> msg = b'some message'
>>> # Calculate the first hash with a random salt.
>>> salt1 = os.urandom(blake2b.SALT_SIZE)
>>> h1 = blake2b(salt=salt1)
>>> h1.update(msg)
>>> # Calculate the second hash with a different random salt.
>>> salt2 = os.urandom(blake2b.SALT_SIZE)
>>> h2 = blake2b(salt=salt2)
>>> h2.update(msg)
>>> # The digests are different.
>>> h1.digest() != h2.digest()
True