Возможно ли дехеширование при определенных условиях?
Здравствуйте. Недавно возник вопрос, можно ли осуществить дехеширование. Перелазив кучу сайтов понял, что "хеширование необратимый процесс", "дехеширование невозможно" и так далее, но нигде не объяснялось почему. Начал копать глубже и узнал, что хеширование необратимо по той причине, что "начальный набор символов" больше конечного. То есть при хешировании набор символов уменьшается до 16-ти (от 0 до f) и при попытке возвращения выходит, что на каждый символ хеша (от 0 до f) приходится чуть ли не шесть возможных исходных символов (0-9, a-z, а-я и т.д.). Вопрос: если точно известно, что захеширован был хеш h1 (sha-256 например) и из него получили хеш h2 (тот же sha-256 - т.е. количество символов в начале равно количеству символов в конце, более того набор символов в первом выражении равен набору символов во втором выражении (короче известно, что и там и там 64 символа каждый из которых принимает значения от 0 до f)) можно ли, имея на руках h2, вернуть значение хеша h1?
P. S. Да, я знаю, хеширование основано на методах необратимой математики по типу "нельзя найти число, зная только, что его остаток от деления на 3 равен 1", но я разбирался в процессе самого хеширования (статья на Хабре майнинг биткоинов вручную) и понял, что в теории, зная, что конечный набор символов равен начальному (от 0 до f) и более того равен по длине (64 символа), можно, так сказать, нанести ограничение, что это неизвестное число например не больше 10 (это абстрактный пример, я знаю, что в алгоритме все по другому), и на основе этого сгенерировать четыре возможных хеша h1 (опять же абстрактно).
Не 16 символов 0-9a-f, а N бит (для sha-256 N=256, внезапно). А символы это просто способ записи.
Итого у тебя бескончное число возможных входных данных отображается в конечное число выходов. Очевидно, что коллизии существуют и значит по хешу нельзя однозначно восстановить исходные данные.
Если ограничить поле исходных данных (только 256-битные), то в теории восстановление возможно. Однако функции хеширования специально сделаны такими, что никакого способа кроме полного перебора в лоб нет.
Нет, нельзя, конечно. Они для этого были придуманы, чтобы нельзя это было сделать. Символы не маппятся один в другой, в общем случае никаких там "чуть ли не шесть возможных исходных символов" нет. Бесконечное множество маппится в конечное.
Денис Загаевский, 11 триллионов хешей в век это 1000 хешей в секунду. Думаю на сегодняшний день это довольно неплохой результат в пределах одного ПК с неплохим процессором. Но мне нравится ваш серьёзный настрой)))
Для правильного вопроса надо знать половину ответа
Хэширование, в общем случае, необратимо, потому что сам алгоритм хэширования не гарантирует взаимно-однозначного соответствия исходных данных и их хэша.
Если исходные данные по размеру больше хэша, то очевидно, что найдётся несколько различных исходных данных с одинаковыми хэшами. Например, хэш-функция выдаёт 0 или 1 (один бит), а на вход поступили цифры от 0 до 7 (три бита).
Если размер данных меньше или равен размеру хэша, то зависит от алгоритма. Промышленные алгоритмы строятся с хорошей равномерностью распределения хэшей, поэтому можно допустить, что на таких данных функция хэширования имеет примерно однозначное соответствие.
Но, в любом случае, у функции хэширования нет простого алгоритма обратного преобразования.
Хэширование — необратимый процесс. Но никто не мешает перебирать все варианты до тех пор, пока не найдёшь совпадение. Правда это очень долго.
То есть при хешировании набор символов уменьшается до 16-ти (от 0 до f) и при попытке возвращения выходит, что на каждый символ хеша (от 0 до f) приходится чуть ли не шесть возможных исходных символов (0-9, a-z, а-я и т.д.).
Враньё. Алфавит хэша — нули и единицы. Алфавит входных данных — нули и единицы. Мощность хэша определяется только количеством бит, которые он порождает. А как ты эти биты представляешь – в виде HEX, в бинарном виде или в виде солнышек и тучек — дело твоё и никак не влияет на процесс.
можно ли, имея на руках h2, вернуть значение хеша h1
Можно, достаточно перебрать все возможные значения h1, пока не получишь h2. Для sha256 это 2^256 варианта.
Да знаю я, что это не так работает (про враньё). Я абстрактно максимально понятно попытался объяснить, чтобы ответ на вопрос был доступен всем.
P. S. Дополнил в конце.
P. P. S. В виде звездочек
если точно известно, что захеширован был хеш h1 и из него получили хеш h2, количество символов в начале равно количеству символов в конце, более того набор символов в первом выражении равен набору символов во втором выражении, можно ли, имея на руках h2, вернуть значение хеша h1?
Можно, если хеш биективный. Но для хорошего алгоритма хеширования нет возможности сделать это существенно быстрее перебора всех возможных значений h1.
Простой
Простой
Средний
