Почему взятие соленого хэша мода хэша приводит к очень неравномерному распределению?

Question

У меня есть миллион случайно сгенерированных уникальных идентификаторов.

Если я сделаю:

result = int(hash(id + 'some_salt')) % 1000

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

Если я добавлю немного соли к этому и снова возьму хеш:

x = int(hash(id)) % 1000
result = int(hash(str(x) + 'some_salt') % 1000)

Тогда полученное распределение совершенно неравномерно. Для каждого идентификатора результат, конечно, находится в диапазоне [0,999], но некоторые целые числа в этом диапазоне имеют нулевые идентификаторы, сопоставленные с ними, в то время как другие имеют несколько тысяч.

Почему это приводит к очень неравномерному распределению значений?

Как я могу изменить это, чтобы получить равномерное распределение целых чисел в диапазоне [0,999] для моих миллионов идентификаторов и любой заданной соли? Я хочу сохранить промежуточный шаг сокращения потенциально очень большого входного пространства до некоторого намного меньшего пространства (например, размера 1000).

Я использую хеширование SHA-256.

Вот некоторый код Python, который демонстрирует очень неоднородные результаты:

import numpy as np
import hashlib

OUTPUT_RANGE_SIZE = 1000

unique_ids = xrange(1000000) # sequential here, but could be any kind of unique ids
frequencies = np.zeros(OUTPUT_RANGE_SIZE, dtype='int')

for idx in xrange(len(unique_ids)):
    id = unique_ids[idx]
    hash_mod = int(hashlib.sha256(str(id)).hexdigest(), 16) % 1000
    result = int(hashlib.sha256(str(hash_mod) + 'some_salt').hexdigest(), 16) % OUTPUT_RANGE_SIZE
    frequencies[result] = frequencies[result] + 1

print frequencies

Answer 1

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

[1, 0, 2, 1, 0, 0, 0, ...]

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

Обязательный постскриптум: не изобретайте свои собственные криптосистемы. Если это критично для безопасности, ознакомьтесь с лучшими практиками и реализуйте их.