Имеется хеш функция такого вида:

unsigned int hash(char *data, int len) {
unsigned int i1 = 0, i2 = 0;

for (int i=0;i<len;i++) {
i1 += data[i];
i2 += i1;
}

i1 %= 65521;
i2 %= 65521;

i2 <<= 16;
return i2 | i1;
}

В которой собственно

i1 %= 65521;
i2 %= 65521;

ОЧЕНЬ редко влияют на конечный результат
Поэтому смело упрощаем до:

unsigned int hash(char *data, int len) {
unsigned int i1 = 0, i2 = 0;

for (int i=0;i<len;i++) {
i1 += data[i];;
i2 += i1;
}

i2 <<= 16;
return i2 | i1;
}

Внимание вопрос знатокам
Надо из получившегося значения(назовём ключом) получить валидные данные, которые:
hash("полученные валидные данные") == hash("оригинал")
У меня получилось только получить оригинальные i1, i2:

int i1 = 0,i2 = 0;
i2 = key >> 16;
i1 = (short int)key;


Т.е. осталось по двум цифрам получить строку.

Какие будут соображения?

PS: Мне НЕ нужен оригинал от хеш-фукнции, а нужна валидная строка.

| Сообщение посчитали полезным:

Пока только бегло просмотрел, если не ошибаюсь, вот это

 
for (int i=0;i<len;i++) {
   i1 += data[ i ];
   i2 += i1;
}

можно записать следующим образом:
Sum_{i=1}^{len} x_{i} = i1 mod 65521
Sum_{i=1}^{len}(len+1-i)*x_{i} = i2 mod 65521

где data = x_{1}x_{2}x_{3}.........x_{len}
i1 = key & 0xFFFF
i2 = key >> 16

ну а это обыкновенная (даже переопределенная для len>2) линейная система из 2х уравнений, подставляй любое len>1 какое нравится и решай.

ОЧЕНЬ редко влияют на конечный результат

Смотря какой длины строка...

PS: Мне НЕ нужен оригинал от хеш-фукнции, а нужна валидная строка.

А оригинал получить и не удастся, если только угадать...

P.S. глюк форума: при правке [i] в data[i] интерпретируется как начало курсива, несмотря на то, что находится внутри [c][/c].

| Сообщение посчитали полезным:

Stiver
Ок, попробую. Только я не совсем уверен, что до конца понял.

| Сообщение посчитали полезным:

Paxan
1. Для начала хотелось бы услышать некоторое уточнение задачи, например, предполагаемый размер входных данных. Если это небольшая строка, то это одно, а если кейфайл ~> 0.5 кб, то это совсем другое, потому что тогда i1 может быть после цикла больше, чем 65521.
2. После выполнения этих строк
Paxan пишет:
i1 %= 65521;
i2 %= 65521;
i1 == i2, так что нам достаточно рассматривать только i1.

3. Это не совсем понятно:
Paxan пишет:
У меня получилось только получить оригинальные i1, i2:

int i1 = 0,i2 = 0;
i2 = key >> 16;
i1 = (short int)key;

Я правильно понимаю, что i1=i2 должно равняться 0?

4. В любом случае, необходимо уточнить, что подается на вход этой функции, то есть какой диапазон занимают байты из data.

5. Все это очень похоже на задачу об укладке ранца. Если я правильно понимаю (см. пункт 3), то нам надо найти такую строку (в случае, если данные подаются на вход не из кейфайла, и у нас всего лишь небольшая строка), сумма символов которой равна 65521. Это сделать просто, такой алгоритм придумай сам ;)

| Сообщение посчитали полезным:

geRC пишет:
1. Для начала хотелось бы услышать некоторое уточнение задачи, например, предполагаемый размер входных данных. Есрли это небольшая стока, то это одно, а если кейфайл ~> 0.5 кб, то это совсем другое, потомуо что тогда i1 мжет быть после цикла больше, чем 65521.
Если после цикла имеем i1 больше 65521, то "i1 %= 65521;" получаем всё равно два байта. Принципиальное значение это не имеет. Задача не стоит получить оригинал.

geRC пишет:
i1 == i2, так что нам достаточно рассматривать только i1.
Это еще почему?

geRC пишет:
4. В любом случае, необходимо уточнить, что подается на вход этой функции, то есть какой диапазон занимают байты из data.
Это бывает и ascii строка и набор бесмыссленных байт длинной до килобайта.

geRC пишет:
5. Все это очень похоже на задачу об укладке ранца. Если я правильно понимаю (см. пункт 3), то нам надо найти такую строку (в случае, если данные подаются на вход не из кейфайла, и у нас всего лишь небольшая строка), сумма символов которой равна 65521. Это сделать просто, такой алгоритм придумай сам ;)
Нет, ранца тут никого нет
У меня есть хеш, посчитанный от каких-то данных. Надо получить любой набор данных (только чтобы в них небыло \00), который бы удовлетворял хешу.

| Сообщение посчитали полезным:

Paxan пишет:
Это еще почему?
Согласен, не заметил += во второй строке ))

Paxan пишет:
Это бывает и ascii строка и набор бесмыссленных байт длинной до килобайта.
Так а что значит "бывает"? Вот у меня есть i1 и i2, надо найти подходящую строку. Есть ли ограничения на её длину?

| Сообщение посчитали полезным:

geRC
Если это небольшая строка, то это одно, а если кейфайл ~> 0.5 кб, то это совсем другое, потому что тогда i1 может быть после цикла больше, чем 65521.

65521 - простое число, мы находимся в поле Z_{65521}, размер данных не имеет значения.

| Сообщение посчитали полезным:

Stiver пишет:
в поле Z_{65521}
Я бы даже сказал GF(65521)

| Сообщение посчитали полезным:

geRC
Я бы даже сказал GF(65521)

а они изоморфны

| Сообщение посчитали полезным:

Stiver


Paxan
Итак:

Запишем систему (i1 = a, i2= b):

[1] + [2] + ... [3]		= a
[1]*n + [2]*(n-1) + ... + [n]*1 = b

или так:

[1] + [2] + ... [n]			 = a
[1] + ([1]+[2]) + ... + ([1]+[2]+..+[n]) = b

=>

[1] + ([1]+[2]) + ... + ([1]+[2]+..+[n-1]) = b-a

теперь ] [1] = (b-a) % (n-1) = c

вычитаем:

[2] + ([2]+[3]) + ... + ([2]+[3]+..[n-1]) = b - a - c*(n-1)

и так далее...

| Сообщение посчитали полезным:

geRC пишет:
Так а что значит "бывает"? Вот у меня есть i1 и i2, надо найти подходящую строку. Есть ли ограничения на её длину?
Нету.

| Сообщение посчитали полезным:

Paxan пишет:
Нету.
Ну тогда смотри выше.

| Сообщение посчитали полезным:

Обращаем adler32 хэш? ну-ну...

| Сообщение посчитали полезным:

DrGolova пишет:
adler32 хэш
Доктор, это у вас такое отличное знание всех криптографических функций, или вы просто набрали !google 65521+hash ? В любом случае - спасибо

ЗЫ. _http://koders.com/?s=65521&_%3Abtn=Search&_%3Ala=%2A&_%3Ali=%2A

| Сообщение посчитали полезным:

DrGolova пишет:
Обращаем adler32 хэш?

с каких это пор адлер стал хешем? вроде как по жизни он был контрольной суммой со всеми вытекающими

| Сообщение посчитали полезным:

Relayer пишет:
с каких это пор адлер стал хешем? вроде как по жизни он был контрольной суммой со всеми вытекающими
А разве есть строгое определение? Как мы можем отделить одно понятие от другого? Вот, например, что говорит wikipedia:
A hash function or hash algorithm is a function for summarizing or probabilistically identifying data.
или так:
A specialized type of function used to convert data with a large range to a smaller range.
Под это определение адлер32 вполне попадает. Другое дело, что любая хорошая хэш-функция должна удовлетворять некоторым требованиям. И вот тут у адлера имхо проблемы.

| Сообщение посчитали полезным:

DrGolova
А его можно обратить?

| Сообщение посчитали полезным:

geRC пишет:
любая хорошая хэш-функция должна удовлетворять некоторым требованиям

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

| Сообщение посчитали полезным:

[муть]
Всё ок =) Щастье есть

| Сообщение посчитали полезным:

Relayer пишет:
смотря для каких целей. если для заполнения хеш таблицы - одни требования, если для крипто - то более жесткие.
Совершенно согласен Никто и не станет использовать адлер в криптографии, это безумие
Relayer пишет:
хотя это возможно гдето терминологические ньюансы
Да, мы немного ушли в оффтоп Оставим этот философский вопрос ;)

Paxan пишет:
А его можно обратить?
А что по-твоему означает "обратить"? Понятно, что исходные данные восстановить никак нельзя. Так что именно "обратить" неполучится. Это отображение не биективное. Relayer абсолютно верно сказал, что адлер изначально задумывался как контрольная сумма. То есть для проверки целостности данных, скажем от случайного повреждения. Однако никто не утверждает, что для частного случая нельзя подобрать такие входные значения, что мы получим нужную чексумму. Кстати, это же самое касается и CRC32.


EDiTED>
Paxan
Paxan2 пишет:
Abd:32178439 - строка:хеш
если ставим в качестве рандомной буквы A - получаем оригинал.
Если взять допустим 50:
то http://paxan.clansiec.com/ddd.JPG http://paxan.clansiec.com/ddd.JPG
хеш от полученного: 13369351

муть
Как все это понимать? Если хочешь, чтобы тебе помогли, научись выражать свои мысли.
Я умываю руки.

EDiTED2>
Дата: Сен 24, 2005 23:51:18 · Поправил: Paxan2 New!
[муть]
Всё ок =) Щастье есть

пришло озарение!

| Сообщение посчитали полезным:

geRC пишет:
Если хочешь, чтобы тебе помогли, научись выражать свои мысли.
Это я чуть поторопился.

| Сообщение посчитали полезным:

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

как мне помнится с лекЦий криптографии, есть всего 4!!! условия, которым должен обладать "идеальный" хэш вне зависимости от его назна4ения (в этих 4 условия у4тено все)

-----
HOW MUCH BLOOD WOULD YOU SHED TO STAY ALIVE

| Сообщение посчитали полезным:

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

-----
HOW MUCH BLOOD WOULD YOU SHED TO STAY ALIVE

| Сообщение посчитали полезным:

ProTeuS

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

| Сообщение посчитали полезным:

Всё, проблема окончательно решена Отдельное спасибо Stiver, geRC. Тему можно закрывать.

| Сообщение посчитали полезным:

В аттаче програмка(вместе с исходниками), находящая к данному hashу коллизию заданной длины для adler32, если таковая вообще существует. То есть задаешь hash, желаемую длину строки и получаешь или какое-то из решений, или сообщение, что решения нет. При этом символы в строке берутся из диапазона 33-126, чтобы их можно было без особых проблем ввести с клавиатуры.

Сделано с помощью симплекс-алгоритма, реализация которого взята из lp_solve. В принципе таким же образом "обращается" и любой другой алгоритм этого типа, если его можно свести к системе линейных уравнений. Может кому пригодится.


4051_adler32rev.zip

| Сообщение посчитали полезным:

Stiver
Респект!

| Сообщение посчитали полезным:

> с каких это пор адлер стал хешем? вроде как по жизни он был
> контрольной суммой со всеми вытекающими

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

| Сообщение посчитали полезным:

http://encyclopedia.laborlawtalk.com/Checksum http://encyclopedia.laborlawtalk.com/Checksum

| Сообщение посчитали полезным: