Comments 33
Спасибо, было интересно прочитать.
Хотелось бы увидеть конкретные примеры функции редукции. Есть ли какие-либо рекомендации по их выбору, кроме инъективности? В свое время искал и не нашел.
Хорошо, обязательно про это расскажу в продолжении. Это действительно вопрос не тривиальный — благодаря хитрому выбору функции редукции можно сильно повысить эффективность алгоритма, так что внимания заслуживает однозначно.
Чем равномернее — тем лучше. В идеале это обычная хеш-функция с заданной областью определения.
Ещё можно менять хеш-функцию (добавлять некоторую константу к её аргументу, например) в разных чейнах, таблицах и пр. Это снижает вероятность того, что циклы (на которые алгоритм неизбежно наталкивается) будут повторяться, а значит и эффективность таблицы. Собственно, это и отличает rainbow tables от прочих потомков таблиц Хеллмана.
Ещё можно менять хеш-функцию (добавлять некоторую константу к её аргументу, например) в разных чейнах, таблицах и пр. Это снижает вероятность того, что циклы (на которые алгоритм неизбежно наталкивается) будут повторяться, а значит и эффективность таблицы. Собственно, это и отличает rainbow tables от прочих потомков таблиц Хеллмана.
А перебрать нужно O(2^разрядности хеш-значения)
Пополам ещё, безотносительно далее идущего по тексту серого комментария. Потому что учитывается парадокс дней рождения.
Пополам ещё, безотносительно далее идущего по тексту серого комментария. Потому что учитывается парадокс дней рождения.
Как бы честнее сказать, тут и так некоторый подвох заключен, ибо разрядность хеш значения — константа, а O(константы) = O(1). Делить на два, или нет, не суть. Правильно читается это так — что за какое-то константное время можно перебрать все значения, но это константное время очень велико, и будет очень велико, даже если поделить его на 2, 22, и 2^64.
Да какой подвох… Выражение написано в универсальном виде для любой разрядности, не в константном. И написано не верно.
Про "константное время очень велико, и будет очень велико": у разных хэш функций может быть разная разрядность значения. Для 32-битных функций константное время очень мало.
Не для споров, а к сведению просто :)
Про "константное время очень велико, и будет очень велико": у разных хэш функций может быть разная разрядность значения. Для 32-битных функций константное время очень мало.
Не для споров, а к сведению просто :)
Так сложно поискать? =)
Парадокс дней рождения работает, если мы хотим найти произвольную коллизию (x1 и x2 такие, что f(x1)=f(x2) ). А тут мы хотим найти коллизию к конкретному хешу (x такое, что f(x)=y).
Парадокс дней рождения работает всегда, когда речь идёт о переборе элементов конечного множества.
В каком смысле?
В прямом. А коллизия «к конкретному хешу (x такое, что f(x)=y)» — это не коллизия, а прообраз. Разные вещи. Это к слову, опять же.
Извините, я просто позанудствовал. Просто если уж применять формулы и терминологию, то тогда применять надо грамотно.
Никого не хотел обидеть.
Извините, я просто позанудствовал. Просто если уж применять формулы и терминологию, то тогда применять надо грамотно.
Никого не хотел обидеть.
Так что он не так сказал про произвольную коллизию?
Я тут поработаю немного миротворцем, оке?
Где-то я читал, что коллизиями называются как прообразы, так и совпадения хеша для двух ключей. Эта досадная ошибка в терминологии в незапамятные разожгла лютые споры на vbnet.ru
Be wise.
Где-то я читал, что коллизиями называются как прообразы, так и совпадения хеша для двух ключей. Эта досадная ошибка в терминологии в незапамятные разожгла лютые споры на vbnet.ru
Be wise.
Коллизии называются коллизиями, прообразы прообразами. И не надо ничего оправдывать надумаными досадными ошибками в терминологии. Терминология совершенно чёткая и устоявшаяся. То, что было прочитано где-то — оно не так.
Общего между коллизиями и прообразом то, что они в конечном итоге сводятся к решению одной и той же задачи — для данного y найти x так что бы f(x) = y.
Разница в том, для коллизий y выражается через даное или произвольно выбраное z [f(z) = y] и через дифференциалы x и z можно существенно сократить пространство поиска.
Если кто-то считает иначе, то не надо здесь философски спорить и минусами самоутверждаться. Приезжайте с докладом на ближайшие Eurocrypt или Asiacrypt. Мы с коллегами вас там внимательно и с удовольствием послушаем.
Общего между коллизиями и прообразом то, что они в конечном итоге сводятся к решению одной и той же задачи — для данного y найти x так что бы f(x) = y.
Разница в том, для коллизий y выражается через даное или произвольно выбраное z [f(z) = y] и через дифференциалы x и z можно существенно сократить пространство поиска.
Если кто-то считает иначе, то не надо здесь философски спорить и минусами самоутверждаться. Приезжайте с докладом на ближайшие Eurocrypt или Asiacrypt. Мы с коллегами вас там внимательно и с удовольствием послушаем.
Вы очень упорны, но я все же советую обратить внимание на слова о «коллизии первого рода» и их прямое отношение к задаче о точном дне рождения. И это не парадокс дней рождения.
Ждём с докладом на конференции. С «коллизиями первого рода» и всем остальным :)
Тем не менее, википедия такую терминологию знает.
Говорить о том, что ссылаться на википедию, как на серьёзный источник даже неловко как-то.
Если попытаться найти англоязычные эквиваленты, то всё встанет на свои места.
Если попытаться найти англоязычные эквиваленты, то всё встанет на свои места.
Термин «хеш-коллизия первого рода» часто применятся в русскоязычной литературе. Терминология в русскоязычной и англоязычной литературе часто различается.
Ну и да, говорить о том, что придираться к терминологии вместо того чтобы признать свою ошибку это дурной тон даже неловко как-то)
В том месте было явно указано, что мы хотим сделать и вне зависимости от того, как это назвать, парадокс дней рождения там совсем не к месту
Ну и да, говорить о том, что придираться к терминологии вместо того чтобы признать свою ошибку это дурной тон даже неловко как-то)
В том месте было явно указано, что мы хотим сделать и вне зависимости от того, как это назвать, парадокс дней рождения там совсем не к месту
Когда не хватает знаний и нет желания понять, но есть острое желание обязательно доказать, тогда ВНЕЗАПНО и терминология начинает отличаться, и парадокс дней рождения начинает избирательно действовать, и подвохи с не сутью всплывают. Это всенепременно :)
На этом плодотворную дискуссию со своей стороны считаю законченой. Кто захотел понять и разобраться, тот, думаю, разобрался. Кому хотелось другого, тем без разницы что минусовать.
На этом плодотворную дискуссию со своей стороны считаю законченой. Кто захотел понять и разобраться, тот, думаю, разобрался. Кому хотелось другого, тем без разницы что минусовать.
Интересная тематика, но честно говоря вникать в весь математический аппарат не хочется. Может допишете абзац «просто о сложном»? :)
Хабраюзеры знают, кто написал UDC. Да, sic? =)
Кстати говоря, у меня есть кое-что сказать вам по поводу этих Hybrid Rainbow Tables, ради которых юзернеймы покупают ваш софт.
Все прогрессивные дядьки, как и вы, пользуют RT вкупе с фильтрами Блума и деревьями, но *сюрприз* самые прогрессивные генерируют пароли с помощью boost::spirit::karma. Ибо круто и быстро. Так-то.
Все прогрессивные дядьки, как и вы, пользуют RT вкупе с фильтрами Блума и деревьями, но *сюрприз* самые прогрессивные генерируют пароли с помощью boost::spirit::karma. Ибо круто и быстро. Так-то.
Но конкретно про UDC ничего не будет (кроме этих комментариев), тематика себя изжила.
Хеш функция это отображение множества строк в множество хешстрок.
Это отображения сюръективно, потому как одной хешстроке может соответствовать не одна исходная строка.
Качество хеш функции в этом и заключается, чтобы выбрать наиболее качественное отображение, чтобы коллизия была редкая.
Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тд
Это отображения сюръективно, потому как одной хешстроке может соответствовать не одна исходная строка.
Качество хеш функции в этом и заключается, чтобы выбрать наиболее качественное отображение, чтобы коллизия была редкая.
Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тд
что-то в субботу вечером ерунда кажется особенно ерундой :)
>Хеш функция это отображение множества строк в множество хешстрок.
с этим, пожалуй согласен, кроме новообразования «хешстрока»
>Это отображения сюръективно, потому как одной хешстроке может соответствовать не одна исходная строка.
Это не сюръективность, это отсутствие инъективности.
Сюръекция, это когда f: X -> Y и f (X) = Y
>Качество хеш функции в этом и заключается, чтобы выбрать наиболее качественное отображение, чтобы коллизия была редкая.
«Редкость коллизии» само по себе бесмысленное понятие, т.к. мы отображаем бесконечное множество строк в конечное множество хеш-значений, и количество коллизий всегда бесконечное.
>Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тд
из двух ошибочных утверждений можно вывести абсолютно все что угодно (простое правило импликации), но данное — еще и бессодержательно. Может поясните тогда?
>Хеш функция это отображение множества строк в множество хешстрок.
с этим, пожалуй согласен, кроме новообразования «хешстрока»
>Это отображения сюръективно, потому как одной хешстроке может соответствовать не одна исходная строка.
Это не сюръективность, это отсутствие инъективности.
Сюръекция, это когда f: X -> Y и f (X) = Y
>Качество хеш функции в этом и заключается, чтобы выбрать наиболее качественное отображение, чтобы коллизия была редкая.
«Редкость коллизии» само по себе бесмысленное понятие, т.к. мы отображаем бесконечное множество строк в конечное множество хеш-значений, и количество коллизий всегда бесконечное.
>Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тд
из двух ошибочных утверждений можно вывести абсолютно все что угодно (простое правило импликации), но данное — еще и бессодержательно. Может поясните тогда?
>Это отображения сюръективно, потому как одной хешстроке может соответствовать не одна исходная строка.Сюръекция, это когда элементу множества Y соответствует хотя бы 1 элемент множества X.
Это не сюръективность, это отсутствие инъективности.
Сюръекция, это когда f: X -> Y и f (X) = Y
>Качество хеш функции в этом и заключается, чтобы выбрать наиболее качественное отображение, чтобы коллизия была редкая.Согласен.
«Редкость коллизии» само по себе бесмысленное понятие, т.к. мы отображаем бесконечное множество строк в конечное множество хеш-значений, и количество коллизий всегда бесконечное.
Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тдЭто уже кал. Если не понимаете мое выражение — вот пример возможной хеш ф-ции: Strlen( str ), отображает строку в множество натуральных чисел (включая ноль)
из двух ошибочных утверждений можно вывести абсолютно все что угодно (простое правило импликации), но данное — еще и бессодержательно. Может поясните тогда?
Only those users with full accounts are able to leave comments. Log in, please.
Time-memory trade off и нерадужные таблицы