Форум программистов, компьютерный форум CyberForum.ru

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

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

3. Какова вместимость так сказать хеш суммы? Тоесть если хеш сумма какого - то алгоритма 128-и байтовая, то для какой максимальной длинны последовательности байт она подойдёт, чтоб она оставалась опять же уникальная для всех вариантов в рамках этой размерности?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.06.2014, 10:59     Может ли быть одинаковая хэш-сумма для разных наборов данных?
Посмотрите здесь:

C++ Обработка наборов однотипных данных
Создать класс который может быть использован для хранения информации и студентах C++
C++ дерево для разных типо данных
C++ Может ли быть ошибка при передаче данных?
Реализовать двусвязный список. В разных узлах одного списка может быть любой объект одного из допустимых типов (своих знаний не хватает) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
uglyPinokkio
325 / 228 / 41
Регистрация: 30.05.2014
Сообщений: 682
19.06.2014, 11:17     Может ли быть одинаковая хэш-сумма для разных наборов данных? #2
Цитата Сообщение от SuperHero Посмотреть сообщение
1. Есть два различных набора байтов, может ли оказаться так, что хэш сумма для них окажется одинаковой?
Может, называется коллизия, для бытового применения вероятность этого события пренебрежимо мала.

Хеш - алгоритм по определению возвращает уникальный отпечаток фиксированного размера для любой последовательности байт любого размера. Размер отпечатка фиксирован, зависит от алгоритма и не зависит от объема входных данных.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,921
Записей в блоге: 1
19.06.2014, 11:23     Может ли быть одинаковая хэш-сумма для разных наборов данных? #3
Цитата Сообщение от SuperHero Посмотреть сообщение
длиННы... не_возможен
Гм. С вашей орфографией...

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

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

Если набор данных предопределен заранее, то для такого набора можно построить набор уникальных хэшей с соотношением размеров порядка ~ 1 бит/символ.
8-BITOV
513 / 455 / 83
Регистрация: 05.05.2014
Сообщений: 1,077
19.06.2014, 11:23     Может ли быть одинаковая хэш-сумма для разных наборов данных? #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от SuperHero Посмотреть сообщение
может ли оказаться так, что хэш сумма для них окажется одинаковой?
Вспомните про принцип Дирихле. На бытовом уровне он звучит так. Если 100 носков разложены по 99 ящикам, то непременно найдется 2 ящика с одинаковым количеством носков.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
19.06.2014, 11:39     Может ли быть одинаковая хэш-сумма для разных наборов данных? #5
да, только вот с хешами не всегда количество ящиков на 1 меньше чем носков!)))

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

http://codeforces.ru/blog/entry/4898
SuperHero
Заблокирован
19.06.2014, 13:01  [ТС]     Может ли быть одинаковая хэш-сумма для разных наборов данных? #6
Всем спасибо. Понял, что закодировать к примеру 100 гигабайт кусками по 4 килобайта со 100% гарантии, что даже для кусков данных с разными данными не получится одинаковая контрольная сумма - нельзя.
8-BITOV
513 / 455 / 83
Регистрация: 05.05.2014
Сообщений: 1,077
19.06.2014, 13:40     Может ли быть одинаковая хэш-сумма для разных наборов данных? #7
Цитата Сообщение от SlavaSSU Посмотреть сообщение
не всегда количество ящиков на 1 меньше чем носков!
Я просто для наглядности привел крайний случай
Sergio Leone
2447 / 1092 / 398
Регистрация: 07.06.2014
Сообщений: 3,245
19.06.2014, 13:49     Может ли быть одинаковая хэш-сумма для разных наборов данных? #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от SuperHero Посмотреть сообщение
Понял, что закодировать к примеру 100 гигабайт кусками по 4 килобайта со 100% гарантии, что даже для кусков данных с разными данными не получится одинаковая контрольная сумма - нельзя.
нельзя.
Но,
1) Вас не смущает, что вероятность того, что прилетат инопланетяне и заберут ваш компьютер с одинаковыми кусками выше, чем вероятность появления коллизии
Как выше сказано, для SHA1 вероятность возникновения коллизии 1/2^64
это единица делённая на 18446744073709551616
подсчитайте, сколько раз Вам надо будет кусочков, чтобы вероятность хотя бы к одной миллиардной приблизилось.
чтобы число было легче представить, то вот это число прописью:
восемнадцать квинтиллионов четыреста сорок шесть квадриллионов семьсот сорок четыре триллиона
семьдесят три миллиарда семьсот девять миллионов пятьсот пятьдесят одна тысяча шестьсот шестнадцать

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

2) никто не мешает подсчитать два (три, четыре) пять разных хэшей. Вероятность совпадения будет равна произведению вероятностей коллизий. Т.е. вы можете вероятность совпадения ещё сильно уменьшить
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2014, 17:04     Может ли быть одинаковая хэш-сумма для разных наборов данных?
Еще ссылки по теме:

C++ Найти максимальное число которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел
C++ В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной
C++ Одинаковая сумма строк в матрице

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
SuperHero
Заблокирован
19.06.2014, 17:04  [ТС]     Может ли быть одинаковая хэш-сумма для разных наборов данных? #9
Цитата Сообщение от Sergio Leone Посмотреть сообщение
Вас не смущает
смущает, т.к. эти хеш суммы я хотел использовать в хард дисках нового поколения на несколько петабайт ... (точнее в специальной модели нейро памяти ... )
Yandex
Объявления
19.06.2014, 17:04     Может ли быть одинаковая хэш-сумма для разных наборов данных?
Ответ Создать тему
Опции темы

Текущее время: 22:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru