md5 -- чо опять не так?

Любые обсуждения, не нарушающие правил форума.

Модератор: Модераторы

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 21:24:38

runewalsh писал(а):Упростим до 4-битного хэша, пусть это первые 4 бита MD5. Слабо дополнить его индексом, который позволит хэшировать файлы без коллизий и при этом будет меньше размера файла?

Ага хитрый какой... сократить хэш невозможно. Его минимальная длинна вот
Код: Выделить всё
1 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2


Код: Выделить всё
f6fde3fce37b211d2e4991adedf50c62c6c3a63d4edf83d426a0b1f230e87d2b3dcfcc2e463e215c885e7f74d7f40d42d6a6af882e08da5c249c6d417b068579

Это когда хэшируется одна буква. Но при этом нужно учитывать что вышеприведённый хэш возвращаемый sha512 - намного длиннее и его тоже нельзя сократить!

А? Есть выгода? Или нет выгоды в нескольких десятках байт?

Добавлено спустя 5 минут 55 секунд:
При этом устойчивость нового хэша намного выше чем у sha 512
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 21:31:22

Кто тебе сказал, что его нельзя сократить (вырезать кусочек)? В хэш-таблицах постоянно именно этим и занимаются, когда берут hash mod len.
Если бы ты прочитал про лавинный эффект, как тебе предлагали, ты бы знал, что все биты хэша непредсказуемы, т. е. взаимозаменяемы, можно взять любые из них и рассматривать как отдельный, маленький хэш. Всё, что справедливо для маленьких хэшей, справедливо и для больших с точностью до масштаба.
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 579
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 21:38:53

runewalsh писал(а):можно взять любые из них и рассматривать как отдельный, маленький хэш.

Можно и кусочек взять, но тогда устойчивость падает, т.к. он превращается в 8-ми битное слово. Но и тут художники не сдадуться, т.к. можно заменить md5 на 4 и sha на 8 битные слова и тогда устойчивость нового хэша - останется прежней, а размер sha512 - сократится в много много байт. Но самое главное что устойчивость нового очень короткого хэша будет выше чем у sha512!
Последний раз редактировалось vitaly_l 07.03.2018 21:41:34, всего редактировалось 1 раз.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 21:41:02

Почему твоё решение с индексами якобы работает для полноценного MD5 или чего-то ещё, но вдруг перестаёт работать на их упрощённом варианте?
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 579
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 21:43:08

runewalsh писал(а):вдруг перестаёт работать на их упрощённом варианте?

Не перестаёт. Почему перестаёт? Работает. Проверьте, 8 битный и 16 битные варианты, вместо md5 и sha256.

Добавлено спустя 1 минуту 5 секунд:
Я имел ввиду что ГОЛЫЙ хэш sha512 теряет устойчивость, при сокращении.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 21:48:40

Окей. Упростим до предела: 8-битный хэш. Хэшируем произвольный файл в 1 байт хэша. Сколько займёт индекс, чтобы пара индекс+хэш была заведомо уникальной? (Подсказка: столько же, сколько файл, в лучшем случае на 1 байт меньше.)
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 579
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 22:01:20

runewalsh писал(а):Окей. Упростим до предела: 8-битный хэш. Хэшируем произвольный файл в 1 байт хэша. Сколько займёт индекс, чтобы пара индекс+хэш была заведомо уникальной? (Подсказка: столько же, сколько файл, в лучшем случае на 1 байт меньше.)

Вот этого, я не понимаю. Пример можно?
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 22:09:21

Представь файл размером 2 байта. Всего таких файлов возможно 256 (первый байт) × 256 (второй байт) = 65536. Каждому из них сопоставляется один из 256 хэшей. Если хэши распределены равномерно, каждому хэшу соответствует = 65536÷256 = 256 файлов. Чтобы записать индекс среди этих 256, нужно число от 0 до 255, то есть 1 байт.

То же самое для файла размером 3 байта. Всего таких файлов 256^3 = 16777216. Если все они равномерно распределены по хэшам от 0 до 255, каждому хэшу соответствуют 16777216÷256 = 65536 файлов. Чтобы записать индекс среди этих 65536 и однозначно определить файл, нужны 2 байта.

И т. д.
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 579
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 22:21:42

runewalsh писал(а):Представь файл размером 2 байта. Всего таких файлов возможно 256 (первый байт) × 256 (второй байт) = 65536. Каждому из них сопоставляется один из 256 хэшей. Если хэши распределены равномерно, каждому хэшу соответствует = 65536÷256 = 256 файлов. Чтобы записать индекс среди этих 256, нужно число от 0 до 255, то есть 1 байт.

runewalsh - что-то не то считаешь. Я как-то совсем по другому всё это вижу и понимаю. Именно поэтому я прошу пример. Дело не в количестве файлов, а в длине слова в файле. Точнее в размере файла. А количество файлов, не имеет значения, но при этом естественно ограничивается возможными вариантами длины слова в файле.

В хэш-индексе должно быть три значения.
1 - длинна слова.
2 - md5 хэш
3 - sha хэш
_____________________________________
Если нужно, то их можно сократить, обрезав до сколько-то там байт. Но алгоритм шифрования хэшей должен сохраниться, т.к. это не линейное число и там вовсе не ровно 65536 вариантов, а намного меньше.

Добавлено спустя 21 минуту 21 секунду:
Суть в том что когда хэшируется слово "привет" силами md5 и sha256, то получаются два сильных хэша, благодаря которым технически невозможно подобрать слово из 6 букв, у которго будут единовременно совпадать: md5 + sha256 + 6 знаков.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение olegy123 » 07.03.2018 22:53:33

елы факен палы.. спецы собрались..
покажите мне красивые графики размера массива и скорости поиска значения... где быстрее будет? школьная задачка..
когда индекс в байт,в word, в integer, в int64, в 16byte, в 32byte, в 64byte.. в 128byte ..

вот у вас array [0..Max] of [индекс в ..], вам нужно построить график зависимости скорости поиска значения от размера битности индекса. https://www.youtube.com/watch?v=LqKepKigBJI
спецы блин...
olegy123
долгожитель
 
Сообщения: 1643
Зарегистрирован: 25.02.2016 12:10:20

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 23:02:44

olegy123 писал(а):покажите мне красивые графики размера массива и скорости поиска значения... где быстрее будет? школьная задачка..
когда индекс в байт,в word, в integer, в int64, в 16byte, в 32byte, в 64byte.. в 128byte ..

Так в том то весь и прикол, что этот ТРОЙНОЙ индекс и в поиске будет быстрее по сравнению с sha512, т.к. вначале проверяется 128 битный md5 вместо сравнения sha 512 и это сильно сокращает время поиска. А устойчивость тройного-хэша выше чем у sha512 и размер меньше.
olegy123 писал(а):спецы блин

Ну в общем: да - 100% настоящие и неподдельные спецы, т.к. я точно знаю что runewalsh очень сильный программист, который решает очень сложные задачи по программированию. И он смотрит со своей колокольни, с которой видно только ему и он по своему прав, т.к. смотрит всё это изнутри, в то время как я смотрю изнаружи.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение Mirage » 08.03.2018 01:10:28

vitaly_l писал(а):В общем глубоко задумался и пришёл к выводу, что это получился именно уникальный и БЕСКОНЕЧНЫЙ индекс


Это же как минимум Нобелевка! Пишите в соотв. комитет.

vitaly_l писал(а):в то время как я смотрю изнаружи.


"Я так вижу!". Теперь в программировании! :D
Mirage
энтузиаст
 
Сообщения: 881
Зарегистрирован: 06.05.2005 20:29:07
Откуда: Russia

Re: md5 -- чо опять не так?

Сообщение RusMikle » 08.03.2018 03:24:41

Разбивай файл на 2 части и бери md5 от каждой. Ключ получится из 2х md5, длиннее, зато вероятность совпадения уменьшится в разы.
RusMikle
новенький
 
Сообщения: 46
Зарегистрирован: 03.01.2017 00:12:44

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 08.03.2018 07:07:52

RusMikle писал(а):Разбивай файл на 2 части и бери md5 от каждой. Ключ получится из 2х md5, длиннее, зато вероятность совпадения уменьшится в разы.

Безусловно это повысит устойчивость хэша.

Но мы в этом топике придумали уникальный индекс из хэшей, который ПРЕДПОЛОЖИТЕЛЬНО никогда не повторяется, т.к. L-длинна слова, стремиться к бесконечности и повторы в обсуждаемых числовых пределах - технически невозможны, а если и станут возможны, то на каких-то очень громадных длинах строки, состоящих из мульти-миллиардов символов.

Mirage писал(а):vitaly_l писал(а): В общем глубоко задумался и пришёл к выводу, что это получился именно уникальный и БЕСКОНЕЧНЫЙ индекс
Mirage иронизировал(а): Это же как минимум Нобелевка! Пишите в соотв. комитет.

vitaly_l писал(а): в то время как я смотрю изнаружи.
Mirage иронизировал(а): "Я так вижу!". Теперь в программировании!

Я не понимаю в чём ирония юмора, в такой ответственный момент?

Иронизируя, Вы противоречите сами себе, постольку поскольку вот Ваши слова, в соседнем топике: http://www.freepascal.ru/forum/viewtopic.php?p=130385#p130385
Mirage писал(а):Не то чтобы я рекомендовал использовать md5 для чего-либо, кроме разве что, контроля целостности, но, к сожалению, вероятность сбоя на АЭС несопоставимо выше, чем вероятность совпадения 128-битных хэшей. Потому как последняя с практической точки зрения нулевая. Но при наличии злого умысла может стать единичной.

Вы там утверждаете, дословно: к сожалению, вероятность сбоя на АЭС несопоставимо выше, чем вероятность совпадения 128-битных хэшей. Потому как последняя с практической точки зрения нулевая..

А здесь, в этой ветке, предлагается сократить эту 128-битную вероятность, многократно умножив варианты хэширования за счёт хэширования строк одинаковой длины string и плюс добавить ещё 256 хэширование на все string ОДИНАКОВОЙ длинны. Соответственно устойчивость хэша увеличится многократно. И при этом гигантском увеличении устойчивости хэша Вы начинаете ВДРУГ иронизировать и высмеивать художников, мол: "Я так вижу!". Теперь в программировании!. И этим высмеиванием художников, Вы противоречите своему же высказыванию, мол: вероятность сбоя на АЭС несопоставимо выше, чем вероятность совпадения 128-битных хэшей. Потому как последняя с практической точки зрения нулевая. и этим Вы противоречите - любой возможной здравомыслящей логике (и это помимо того что Вы абсолютно некомпетентны в 128-битных хэшах).

Вы как-то не серьёзно относитесь к серьёзному вопросу. Ещё раз Вам объясняю: Гибель этой планеты неизбежна. Мы тут мульти-народные сказки спасаем, от неизбежной гибели, а Вы иронизируете в такой ответственный момент! Как Вам не стыдно, противоречить самому себе?!

Где Ваша-то логика и здравомыслие?
Что с ней ВДРУГ стало?

Вот Ваши абсолютно некомпетентные в программировании слова, которыми Вы ввели в заблуждение ТС и ещё миллионы программистов: вероятность сбоя на АЭС несопоставимо выше, чем вероятность совпадения 128-битных хэшей..... Потому как последняя с практической точки зрения нулевая....

Это у 128 битных-то хэшей нулевая вероятность совпадения?
И Вы это мне на форуме программистов говорите?
Вы серьёзно? Нулевая вероятность? Правда?
Точно уверены, что нулевая?

И кстати, если бы взрывы на АЭС, были бы так же часты, как совпадения 128-битных хэшей, то у нас бы уже все АЭС взорвались. Я искренне надеюсь, что Вам - никогда не доверят программировать управление АЭС и самолётами, с Вашей: противоречивой, поверхностной и абсолютно некомпетентной - логикой! :wink:
Последний раз редактировалось vitaly_l 08.03.2018 08:23:05, всего редактировалось 1 раз.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение azsx » 08.03.2018 08:21:04

в заблуждение ТС

Чур ТС не трогать. У меня был вопрос, мне его объяснили, я знаю, что Вы Виталий не прав.
Это ваша война -- вы и боритесь.
azsx
энтузиаст
 
Сообщения: 959
Зарегистрирован: 16.11.2015 06:38:32

Пред.След.

Вернуться в Потрепаться

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11

Рейтинг@Mail.ru