есть ли решение у такой вот задачи?
Решение, очевидно, есть. Конечное число хешей, для каждого есть наикратчайшая исходная последовательность, очевидно, у них есть конечная верхняя грань.
Или тебе алгоритм, как искать?
Или тебе алгоритм, как искать?
хотя бы чему равно Z но можно и в добавок алгоритм
Хочешь сэкономить на месте для пароля?
хочу прикинуть сколько места займет таблица всех паролей для всех значений md5
безотносительно задачи. верно ли утверждение?
Для любого Y найдется X такой что Y=md5(X) и length(X)<Zчто-то навскидку неочевидно. или я туплю?
думаю верно, например если z=10000000000000
хочу прикинуть сколько места займет таблица всех паролей для всех значений md5А заполнять её как планируешь при этом?
Вообще, можешь почитать про радужные таблицы. Возможно, это то, что тебе нужно.
Достаточно 17байт=16байт(длина md5)+1 доп. байт с вероятностью близкой к ~99%. Это следует из того, что md5 дает равномерное распределение результата.
При 17 байтах на каждое значение хэша приходится в среднем 256 значений данных. 18 байт - 65536 данных.
Для получения точной функции F1(кол-во доп.байты)=вероятность или F2(вероятность)=кол-во доп. байт стоит развить указанный подход в сторону построения более точной вероятностной модели.
При 17 байтах на каждое значение хэша приходится в среднем 256 значений данных. 18 байт - 65536 данных.
Для получения точной функции F1(кол-во доп.байты)=вероятность или F2(вероятность)=кол-во доп. байт стоит развить указанный подход в сторону построения более точной вероятностной модели.
А заполнять её как планируешь при этом?Вообще, можешь почитать про радужные таблицы. Возможно, это то, что тебе нужно.в них нужный хэш не нашёлся, они только для некоторого подмножества пока что сгенерены
z=17 ?
остаточно 17байт=16байт(длина md5)+1 доп. байт с вероятностью близкой к ~99%. Это следует из того, что md5 дает равномерное распределение результата.При 17 байтах на каждое значение хэша приходится в среднем 256 значений данных. 18 байт - 65536 данных.Для получения точной функции F1(кол-во доп.байты)=вероятность или F2(вероятность)=кол-во доп. байт стоит развить указанный подход в сторону построения более точной вероятностной модели.
z=17 ?Z = 17байт
а точно не z=5 ответ случайно?
а точно не z=5 ответ случайно?5 чего? Предположим, что речь идет о 5 байт(40бит). Это не может быть ответом, потому что длина самого MD5 - 8байт(128бит). Однозначная функция (которой является md5-hash) не может множество с меньшей мощностью преобразовать в множество с большей мощностью.
ну разве для любого значения Y не найдется такой X, что strlen(X) <5 ?
если нет, то приведи пример Y для которого не найдется strlen(X) <5 ?
если нет, то приведи пример Y для которого не найдется strlen(X) <5 ?
Не найдется.
В данном случае:
Различных Y-ков - 2^128 = 3*10^38
Различных X-ов только - 2^40 = 1*10^12
один X покрывает один Y (не больше одного, при переходе к множественному варианту)
Соответственно, останется не покрытыми 3*10^38/(1*10^12) =3*10^26 X-ов
В данном случае:
Различных Y-ков - 2^128 = 3*10^38
Различных X-ов только - 2^40 = 1*10^12
один X покрывает один Y (не больше одного, при переходе к множественному варианту)
Соответственно, останется не покрытыми 3*10^38/(1*10^12) =3*10^26 X-ов
если нет, то приведи пример Y для которого не найдется strlen(X) <5 ?Y = 0
ps
Это так, с вероятностью 1 - 1/(2^88)
ну вот скажем
mdX(s) = md5(s) if md5(s) != 42 else 43
тоже весьма равномерно распределена (не сильно хуже md5 но нет такого s, что mdX(s) == 42
mdX(s) = md5(s) if md5(s) != 42 else 43
тоже весьма равномерно распределена (не сильно хуже md5 но нет такого s, что mdX(s) == 42
тоже весьма равномерно распределена (не сильно хуже md5 но нет такого s, что mdX(s) == 42mdX равномерно распределена при анализе ее как черного ящика.
При анализе как белого ящика mdX неравномерно распределена из-за того, что mdX раскладывается на md5*f, где f -
Про md5 известно, что для неё неизвестен такой вариант раскладывания
хочу прикинуть сколько места займет таблица всех паролей для всех значений md5Если даже на каждое возможное значение md5 тебе придется хранить один байт, то тебе потребуется 2^128 т.е. порядка 3.4 * 10^29 гигабайт.
То есть твой вопрос имеет смысл только в том случае, если md5 может принимать существенно меньшее множество значений, чем весь отрезок [0..2^128-1], что маловероятно для такой распространенной и хорошо исследованной хэш-функции.
то тебе потребуется 2^256Почему 256, а не 128?
Потому что я туплю. Ща исправлю все вычисления, я там много где туплю...
Про md5 известно, что для неё неизвестен такой вариант раскладыванияпруф?
ЗЫ беглый гуглинг на предмет сюръективности md5 ничего не дал, т.ч, похоже, утверждение может быть и неверно
ЗЫ беглый гуглинг на предмет сюръективности md5 ничего не дал, т.ч, похоже, утверждение может быть и неверноДа, может быть неверно. Мы лишь полагаемся-на-её-сюръективность.
сюръективность=есть математическое доказательство сюръективности
полагаемся-на-сюръективность= отсутствует несюръективность (отсутствует доказательство несеръюктивности, после того как передовая математика потратила на это множество человеко и машино- часов)
ps
Утверждение о сюрьективности Md5 сделано в расширенной конструктивной логике.
Классическая логика - да, нет
Конструктивная логика - да, нет, не знаю
Расширенная конструктивная логика - на входе и внутри (да, нет, не знаю на выходе (да, нет). 'не знаю' сводится к 'да' или 'нет', в зависимости от доп. условий.
При анализе как белого ящика mdX неравномерно распределена из-за того, что mdX раскладывается на md5*f, где f - не равномерная функция, а md5 - равномерная.
mdX неравномерна не потому, что она явно выразима через md5, а потому, что явно не попадает в 42
а утверждение
для любого T
если mdXT = md5 if md5 != T else T + 1 (mod 2**128 то mdXT распределено "хуже", чем md5
вообще говоря может быть не верно (и, кажется, равносильно изначальному утверждению т.к. вполне может быть, что для любого s mdXT(s) == md5(s) (т.к. неизвестно, существует ли s: md5(s) == T)
отсутствует доказательство несеръюктивности, после того как передовая математика потратила на это множество человеко и машино- часовхз, кстати, заморачивался ли кто-то именно сюръективностью
mdX неравномерна не потому, что она явно выразима через md5, а потому, что явно не попадает в 42Поправлюсь: mdX - плохая hash-функция, потому что она теряет информацию и раскладывается на md5*f, где f - сужающая функция
Сужающая функция - на выходе кол-во значений меньше, чем на входе
Всякий hash (и md5, в частности) исследуется на то, чтобы в нем не было потерь информации (не было сужающих преобразований кроме исходного. Md5 = расчет*исходное_сужение. расчет - делает расчеты над 128-битными числами и в нем нет сужающих функций. Исходное сужение - разбивает исходный поток на последовательность 128-битных чисел.
Поправлюсь: mdX - возможно плохая hash-функция, потому что она возможно теряет информацию и раскладывается на md5*f, где f - сужающая функция
так правильнее, нет?
Всякий hash (и md5, в частности) исследуется на то, чтобы в нем не было потерь информации (не было сужающих преобразований кроме исходного.извини, но я не могу понять смысл этого высказывания. вот, например,
mdZ(s) = md5(md5(s) + md5(s+1 - плохая? неравномерная?
хочу прикинуть сколько места займет таблица всех паролей для всех значений md5Забьем еще один гвоздь в крышку гроба мертворожденной идеи:
http://en.wikipedia.org/wiki/Salt_%28cryptography%29
да что там забивать-то, давно уже md5 в здравом уме и по своей воле никто не использует для паролей - хоть с солью, хоть без
UPD точнее, не должен использовать
UPD точнее, не должен использовать
mdZ(s) = md5(md5(s) + md5(s+1 - плохая? неравномерная?Нет сужающих преобразований, и на основе этого критерия mdZ не получится зафейлить.
Придется копать глубже.
Afaik про md5 известно, что:
md5(md5(s - хорошая
md5(s0)+md5(s1) - хорошая, когда s0 и s1 - независимы. и где +:сложение по модулю 2^128
У MdZ есть сложение двух зависимых друг от друга md5. Это может приводить к "взаимопогашению". Для проверки этого необходимо раскрыть скобки в выражении md5(s)+md5(s+1) и его исследовать.
md5(s) + md5(s+1) лежит за пределами 128 бит, а результат в пределах, это разве не сужение?
UPD если нет, то дай строгое определение "сужения"
UPD2 (на удаленное сообщение) - сложение обычное, без взятия остатка или чего-то такого
UPD если нет, то дай строгое определение "сужения"
UPD2 (на удаленное сообщение) - сложение обычное, без взятия остатка или чего-то такого
md5(s) + md5(s+1) лежит за пределами 128 бит, а результат в пределах, это разве не сужение?В данном случае, критичны не всякие сужения, а сужения меньше 2^128. Сужения до 2^128 вполне устраивают, потому что суть md5 - это сузить большое число до 2^128
ты не сможешь доказать, что для произвольного T область значений mdXT меньше, чем у просто md5, так что она ни чем не хуже
ты не сможешь доказать, что для произвольного T область значений mdXT меньше, чем у просто md5, так что она ни чем не хуже
Да, Для произвольных не получится. Для конкретных получится.
Например, для функции mdX0(s) = md5(s)*0, доказательство тривиальное.
вообще-то mdX0(s) = md5(s) if (md5(s) == 0) else 1
не вижу тут тривиальности, разве что у тебя есть готовый прообраз от нуля
ЗЫ ты, возможно, как-то не так понял, что такое mdXT (что там есть какое-то умножение а я не так понял * в твоем посте (я понял как композицию, а не как умножение)
не вижу тут тривиальности, разве что у тебя есть готовый прообраз от нуля
ЗЫ ты, возможно, как-то не так понял, что такое mdXT (что там есть какое-то умножение а я не так понял * в твоем посте (я понял как композицию, а не как умножение)
Прошу прощения за предыдущее сообщение. Запутался в обозначениях.
Итого, mdXT хуже, чем md5.
ты не сможешь доказать, что для произвольного T область значений mdXT меньше, чем у просто md5, так что она ни чем не хужеПро mdXT доказывается, что она не лучше md5 в любом случае(при произвольном качестве md5 и хуже, чем md5 для случая, когда md5 имеет все 2^128 значений в результате
Итого, mdXT хуже, чем md5.
Однозначная функция (которой является md5-hash) не может множество с меньшей мощностьюпочему?
почему?Возьмем исходное множество A, однозначную функцию f и пустое множество B.
Начнем перебирать элементы A, помещая во множество B результат f(Ai).
На каждой итерации множество B прирастает не больше, чем 1. На 1, если такого элемента еще не было и на 0, если был.
Итераций всего по кол-ву элементов в A.
Итого: мощность B <= мощности A
Про mdXT доказывается, что она не лучше md5 в любом случае(при произвольном качестве md5 и хуже, чем md5 для случая, когда md5 имеет все 2^128 значений в результате
Итого, mdXT хуже, чем md5.
Итого, mdXT хуже, чем md5 если md5 имеет все 2^128 значений в результате, что не доказано. Так что пока что доказано, что mdXT не лучше (а я этого и не утверждал).
ну это понятно, но я чот не понял про md5.
у md5 хэш же 128 битный при любой длине входного сообщения.
у md5 хэш же 128 битный при любой длине входного сообщения.
если ты будешь хешировать 3-хсимвольные числа, то у тебя получится 1000 значений, хоть они и будут 128-битными
понял, что имелось в виду.
Оставить комментарий
Temach
Задача:------------------------------------------------------------
Допустим верно утверждение:
Для любого Y найдется X такой что Y=md5(X) и length(X)<Z
где length - длина строки.
Найдите Z.
-------------------------------------------------------------
имеет ли решение?