Существуют ли «рефлексивные» алгоритмы хеширования?

Существует ли класс алгоритмов хеширования, теоретический или практический, такой, чтобы алгоритм в классе можно было считать «рефлексивным» согласно определению, данному ниже:

hash1 = algo1 ("текст ввода 1")
hash1 = algo1 («входной текст 1» + hash1)

Оператор + может быть конкатенацией или любой другой указанной операцией для объединения вывода (hash1) обратно во вход («input text 1»), так что алгоритм (algo1) даст точно такой же результат. т.е. столкновение на входе и на входе + выходе. Оператор + должен объединять все оба входа, и алгоритм не может отбрасывать часть ввода.

Алгоритм должен давать высокую энтропию на выходе. Может быть, но не обязательно, криптографически трудно преобразовать выход обратно в один или оба возможных входа.

Я не математик, но хороший ответ может включать доказательство того, почему такой класс алгоритмов не может существовать. Однако это не абстрактный вопрос. Я искренне заинтересован в использовании такого алгоритма в моей системе, если таковой существует.

Это дубликат вопроса, который был впервые опубликован по адресу /programming/4823680/reflexive-hash

ds.algorithms hash-function Сообщество
источник

Связанный: Ассоциативное смешивание хэша

Tsuyoshi Ito

Вас интересует это свойство для всего входного текста или для одного входного текста? Если вы хотите, чтобы он сохранялся для всего входного текста, то создание коллизий по конструкции тривиально, поэтому я не думаю, что это можно считать хорошей хэш-функцией.

Питер Тейлор

Кто-то хочет хэшировать файлы, которые содержат свои хэши! ;)

Рафаэль

@Peter Taylor - я ищу функцию, которая работает как описано для произвольного ввода текста. Каждый отдельный вход создает хеш, который, как правило, имеет высокую взаимную энтропию для любого другого возможного входа. Во многом как хорошая необратимая хеш-функция работает. Однако хеш-функция, которую я ищу, не обязательно должна иметь свойство необратимости. Высокая энтропия достаточна.

@ Рафаэль - Да, это краткий способ выразить это.

Ответы:

Я даю тривиальную конструкцию, которая удовлетворяет требованию. Я даю это просто, чтобы ответить на существование «рефлексивной» хэш-функции.

Пусть будет любой хеш-функцией, создающей высокую энтропию на выходе. Предположим, что хэширует двоичные строки произвольной длины в битные двоичные строки, где - любое положительное целое число. Пусть обозначим конкатенацию оператор, и пустьобозначим длину двоичной строки . $G$ $G$ $k$ $k$ $+$ $|x|$ $x$

Определите хеш-функцию на входе следующим образом: $H$ $x$

Если , то . $|x| \le k$ $H(x) \overset{\text{def}}{=} G(x)$
Если , пусть и - префикс -бит и суффикс -бит для соответственно. То есть и . Если (где вычисляется рекурсивно ), то ; в противном случае . $|x| > k$ $L$ $R$ $(|x|-k)$ $k$ $x$ $x = L + R$ $|R|=k$ $R = H(L)$ $H(L)$ $H(x) \overset{\text{def}}{=} R$ $H(x) \overset{\text{def}}{=} G(x)$

Как я уже сказал, это тривиальная конструкция. Он может применяться к любой хэш-функции, практической (например, MD5, SHA-1, ...) или теоретической.

М.С. Дусти
источник

Я не очень уверенный в области кодирования, но имеет ли

все еще высокую энтропию? По своей конструкции он, безусловно, имеет тот же хэш для двойного числа строк, что и раньше. И они приходят парами, которые очень близки друг к другу. (О, это должно быть

во второй строке 2.)

H

$H$

| R | = k

$|R|=k$

Рафаэль

@ Рафаэль: Спасибо за указание на опечатку (исправлено). H имеет ту же энтропию, что и G, за исключением случаев, когда R = G (L). По требованию, в этом условии H (x) должно равняться R. Здесь мы ничего не можем сделать, чтобы увеличить энтропию; поскольку требование «рефлексивности» не позволяет нам изменять результат.

MS Dousti

@Sadeq: Требуется ли, чтобы хеш-функция была вычислена рекурсивно? Я алгоритм извлек выгоду из этого факта никак?

Ясир Собхдел

H (M + H (M) + H (M) + \dots + H (M))

$H(M+H(M)+H(M)+\ldots+H(M))$

H (M)

$H(M)$

Садек, спасибо. Я считаю, что это может ответить на мой вопрос, как он был задан. Вы сформулировали ответ в подходящем предостережении. С прагматической точки зрения мне нравится тот факт, что это наложение для любого известного алгоритма, такого как SHA-1. Если я правильно понял, ваш алгоритм будет продолжать рекурсивно вычислять хеши, пока не достигнет требуемого столкновения, а затем остановится. В этом случае, возможно, мы можем назвать это наивным решением. Меня беспокоит то, что существует неявное предположение о том, что встроенный алгоритм (скажем, SHA-1) в конце концов достигнет необходимого хэша коллизий, учитывая