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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
SuperHero
Заблокирован
#1

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

19.06.2014, 10:59. Просмотров 961. Ответов 8
Метки нет (Все метки)

Всем привет! Есть небольшая серия вопросов по хэшам, к ому не сложно, дайте свои комменты по вопросам. Просьба не засирать тему флудом
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++ Найти максимальное число которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел
C++ Одинаковая сумма
C++ Одинаковая сумма строк в матрице
C++ Может ли быть ошибка при передаче данных?
Реализовать двусвязный список. В разных узлах одного списка может быть любой объект одного из допустимых типов (своих знаний не хватает) C++
Создать класс который может быть использован для хранения информации и студентах C++
C++ В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
uglyPinokkio
326 / 229 / 41
Регистрация: 30.05.2014
Сообщений: 682
19.06.2014, 11:17     Может ли быть одинаковая хэш-сумма для разных наборов данных? #2
Цитата Сообщение от SuperHero Посмотреть сообщение
1. Есть два различных набора байтов, может ли оказаться так, что хэш сумма для них окажется одинаковой?
Может, называется коллизия, для бытового применения вероятность этого события пренебрежимо мала.

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

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

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

Если набор данных предопределен заранее, то для такого набора можно построить набор уникальных хэшей с соотношением размеров порядка ~ 1 бит/символ.
8-BITOV
535 / 477 / 86
Регистрация: 05.05.2014
Сообщений: 1,101
19.06.2014, 11:23     Может ли быть одинаковая хэш-сумма для разных наборов данных? #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от SuperHero Посмотреть сообщение
может ли оказаться так, что хэш сумма для них окажется одинаковой?
Вспомните про принцип Дирихле. На бытовом уровне он звучит так. Если 100 носков разложены по 99 ящикам, то непременно найдется 2 ящика с одинаковым количеством носков.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
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
535 / 477 / 86
Регистрация: 05.05.2014
Сообщений: 1,101
19.06.2014, 13:40     Может ли быть одинаковая хэш-сумма для разных наборов данных? #7
Цитата Сообщение от SlavaSSU Посмотреть сообщение
не всегда количество ящиков на 1 меньше чем носков!
Я просто для наглядности привел крайний случай
Sergio Leone
2454 / 1099 / 402
Регистрация: 07.06.2014
Сообщений: 3,259
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++
C++ Обработка наборов однотипных данных
C++ Сортировка различных наборов данных
C++ дерево для разных типо данных
Сохранение данных хэш таблицы C++

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru