Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

Найти максимальное число которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел - C++
Найти максимальное число, меньшее заданного, которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел (минимальное такое...

Одинаковая сумма - C++
У меня окончательная сумма(вне зависимо от Х) всегда -9,25596е+061. Проблема С++, Visual Studio или моих рук? #include "stdafx.h" ...

Одинаковая сумма строк в матрице - C++
Подскажите, пожалуста! Какой код нужен для нахождения одинаковой суммы разных строк в матрице? Например, матрица: 1 2 3 3 2 1 1 1 1. ...

Может ли быть ошибка при передаче данных? - C++
есть функция: CalculateMovingAverage(&RMSSmoothLenghtM1, URMS.Channel1M, URMSSmooth.Channel1M); такая обработка правильная будет? ...

Реализовать двусвязный список. В разных узлах одного списка может быть любой объект одного из допустимых типов (своих знаний не хватает) - C++
Вобщем делаю тестовые задания. На одно мне даже ответили, результат отрицательный. Помогите понять если кто поймёт его не так как я или...

Создать класс который может быть использован для хранения информации и студентах - C++
создать класс который может быть использован для хранения информации и студентах

8
uglyPinokkio
326 / 229 / 41
Регистрация: 30.05.2014
Сообщений: 682
19.06.2014, 11:17 #2
Цитата Сообщение от SuperHero Посмотреть сообщение
1. Есть два различных набора байтов, может ли оказаться так, что хэш сумма для них окажется одинаковой?
Может, называется коллизия, для бытового применения вероятность этого события пренебрежимо мала.

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

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

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

Если набор данных предопределен заранее, то для такого набора можно построить набор уникальных хэшей с соотношением размеров порядка ~ 1 бит/символ.
1
8-BITOV
541 / 484 / 87
Регистрация: 05.05.2014
Сообщений: 1,107
19.06.2014, 11:23 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от SuperHero Посмотреть сообщение
может ли оказаться так, что хэш сумма для них окажется одинаковой?
Вспомните про принцип Дирихле. На бытовом уровне он звучит так. Если 100 носков разложены по 99 ящикам, то непременно найдется 2 ящика с одинаковым количеством носков.
2
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
19.06.2014, 11:39 #5
да, только вот с хешами не всегда количество ящиков на 1 меньше чем носков!)))

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

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

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

2) никто не мешает подсчитать два (три, четыре) пять разных хэшей. Вероятность совпадения будет равна произведению вероятностей коллизий. Т.е. вы можете вероятность совпадения ещё сильно уменьшить
1
SuperHero
Заблокирован
19.06.2014, 17:04  [ТС] #9
Цитата Сообщение от Sergio Leone Посмотреть сообщение
Вас не смущает
смущает, т.к. эти хеш суммы я хотел использовать в хард дисках нового поколения на несколько петабайт ... (точнее в специальной модели нейро памяти ... )
0
19.06.2014, 17:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2014, 17:04
Привет! Вот еще темы с ответами:

Могут ли быть одинаковые хэш-коды у двух разных элементов QSet? - C++ Qt
Добрый день. Подскажите, пожалуйста. Могут ли быть одинаковые хэш-коды у двух разных элементов QSet? И как обстоит дело в STL Set?

Обновление данных dataGridView в потоке ошибка BindingSource не может быть источником данных для самого себя - C#
Изучаю потихоньку C#, требуется в отдельном потоке обновлять данные dataGridView. Если не выбирать ячейку или не прокручивать полосу...

Хэш функция строк (строк в массиве может быть около 2 миллионов) - C#
Подскажите пожалуйста алгоритм хэш функции для строк , строк в массиве может быть около 2 миллионов, для быстрого поиска решил использовать...

bindingsource не может быть источником данных для самого себя - C#
Здравствуйте друзья. Я цыклом пропинговываю ip адреса, беру ip из базы (access). Выскакивают ошибки: 1) 20.04.2010 14:57:51В...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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