Может ли быть одинаковая хэш-сумма для разных наборов данных?

Всем привет! Есть небольшая серия вопросов по хэшам, к ому не сложно, дайте свои комменты по вопросам. Просьба не засирать тему флудом
1. Есть два различных набора байтов, может ли оказаться так, что хэш сумма для них окажется одинаковой? В данном вопросе не рассматриваем размерности данных и хеш сумм, а так же алгоритмы хеш сумм, чисто теория.
2. Если в п.1 такой вариант возможен, то нет ли какого - то типа (алгоритма) хеш суммы, повтор которой для любых различных наборов байт одинаковой длинны (ну скажем 4096 байт в наборе А и такое же кол-во других байт в наборе Б) не возможен? То есть мне нужно получить уникальный ключ/ код/ сумму... да что угодно... для определённого набора байт, которая бы выполняла следующие условия:
2.a.) данный ключ был бы уникальным в заранее известной и постоянной длине байт, то есть есть допустим блок данных размером 4096 байт, я хочу, чтоб при любом раскладе байт этой размерности для каждого набора был уникальный ключ.
2.б.) данный ключ должен быть намного меньшей размерности, чем сами данные, в идеале намнОООго меньше, допустим блок данных 1 гигабайт, а уникальный ключ всего навсего 128 байт ...

3. Какова вместимость так сказать хеш суммы? Тоесть если хеш сумма какого - то алгоритма 128-и байтовая, то для какой максимальной длинны последовательности байт она подойдёт, чтоб она оставалась опять же уникальная для всех вариантов в рамках этой размерности?

0

Сообщение от SuperHero 1. Есть два различных набора байтов, может ли оказаться так, что хэш сумма для них окажется одинаковой?

Может, называется коллизия, для бытового применения вероятность этого события пренебрежимо мала.

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

1

Сообщение от SuperHero длиННы... не_возможен

Гм. С вашей орфографией...

Коротко. Хэш неуникален. По определению.

Но для хорошего алго, вероятность коллизий мала. Например, для SHA1 - 1/(2^64).

Если набор данных предопределен заранее, то для такого набора можно построить набор уникальных хэшей с соотношением размеров порядка ~ 1 бит/символ.

1

Сообщение от SuperHero может ли оказаться так, что хэш сумма для них окажется одинаковой?

Вспомните про принцип Дирихле. На бытовом уровне он звучит так. Если 100 носков разложены по 99 ящикам, то непременно найдется 2 ящика с одинаковым количеством носков.

2

да, только вот с хешами не всегда количество ящиков на 1 меньше чем носков!)))

вот ссылка, там ломают хеши для строк

http://codeforces.ru/blog/entry/4898

1

Всем спасибо. Понял, что закодировать к примеру 100 гигабайт кусками по 4 килобайта со 100% гарантии, что даже для кусков данных с разными данными не получится одинаковая контрольная сумма - нельзя.

0

Сообщение от SlavaSSU не всегда количество ящиков на 1 меньше чем носков!

Я просто для наглядности привел крайний случай

0

Сообщение от SuperHero Понял, что закодировать к примеру 100 гигабайт кусками по 4 килобайта со 100% гарантии, что даже для кусков данных с разными данными не получится одинаковая контрольная сумма - нельзя.

нельзя.
Но,
1) Вас не смущает, что вероятность того, что прилетат инопланетяне и заберут ваш компьютер с одинаковыми кусками выше, чем вероятность появления коллизии
Как выше сказано, для SHA1 вероятность возникновения коллизии 1/2^64
это единица делённая на 18446744073709551616
подсчитайте, сколько раз Вам надо будет кусочков, чтобы вероятность хотя бы к одной миллиардной приблизилось.
чтобы число было легче представить, то вот это число прописью:
восемнадцать квинтиллионов четыреста сорок шесть квадриллионов семьсот сорок четыре триллиона
семьдесят три миллиарда семьсот девять миллионов пятьсот пятьдесят одна тысяча шестьсот шестнадцать

Недостоточно для практического использования?!

2) никто не мешает подсчитать два (три, четыре) пять разных хэшей. Вероятность совпадения будет равна произведению вероятностей коллизий. Т.е. вы можете вероятность совпадения ещё сильно уменьшить

1

Сообщение от Sergio Leone Вас не смущает

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

0