хеш функция

Куда-то вас всех не в ту степь понесло. Под "необратимой" естественно имеется в виду "практически необратима", то есть так называемая one-way function (строгое определение можно найти например в Википедии). Ежу понятно, что перебором обращается любая функция на ограниченном пространстве значений.

UyTvGauG

Прежде чем утверждать что-либо с такой категоричностью, желательно думать головой. Простейший вариант: берешь достаточно большое простое p, группу Z_{p}, генератор a и вычисляешь f(x) := a^{x}.

Задача кстати интересная, сам бы с удовольствием на решение посмотрел.

 

хм... что же тут думать? на вход подается число размером всего 4 байта. На выходе тоже 4 байта (это я о CRC, раз уж MD5 - это длинный хеш). Все хэши должны быть уникальными. О чем тут думать???

 

MSoft

Это ты уже сам придумал. В условии размер выхода не оговаривается. Пример подходящей функции я привел.

 

1) он попросил меня привести код, который удовлетворяет условию необратимости и при этом маленький. Это однозначно CRC32. У него на выходе только 4 байта. Поэтому условие коллизии однозначно не соблюдается
2) md5, если верить автору, большой, а надо как можно меньше. Поэтому, я и "придумал" про 4 байта на выходе

 

это вовсе не обязательно должна быть хэш функция.
можно использовать симметричный шифр (например rc4).
берем исходные 4 байта и используем в качестве ключа
которым шифруем заранее известную постоянную строку.
Из зашифрованного значения ключ не вычислить (только перебором).
коллизий тоже не будет при достаточной длине шифруемой константы.

 

Судя по ответам мои условия не совсем полные (Жаль что мы не телепаты )

И так попробую внести некоторые коррективы в проблему.

Те первые три условия сохраняются - они базовые.

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

Если будут какие-нибудь вопросы по условию, то пишите

 

jeni

Ну вот например:

Code (Text):

1. unsigned __int64 hash(unsigned int x)
2. {
3.     unsigned __int64 result = 1;
4.     unsigned __int64 base = 2863371373;
5.     unsigned __int64 p = 4294967311;
6.  
7.     while(x) {
8.         if(x & 1) {
9.             result = (base * result) % p;
10.         }
11.         x >>= 1;
12.         base = (base * base) % p;
13.     }
14.  
15.     return result;
16. }

Надеюсь в числах не наврал, вычислял "на коленке". Если нужна более высокая устойчивость, просто соответственно выбирай числа.

P.S. Хотя вот этого я так и не понял: -Код(набор инструкций) этой функции будет отлаживаться/дизассемблироваться, так что алгоритмы (де)шифрования не подходят.

 

можно подробнее критерии для такого кода ?
имеется в виду что не подходят стандартные
алгоритмы и надо придумывать новый ?

 

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

И еще такой вопрос. Как проверить криптостойкость алгоритма на необратимость???

 

а в том алгоритме что я предложил тоже нет
ничего секретного.

1. key = входные данные (4 байта)
2. s = '1234ABCD'
3. result = RC4(s,key)
или так: result = RC4(s1,RC4(s2,k));

размер результата (значение хэш функции) = длина строки s.
восстановить key имея result можно только перебором (свойство rc4).
отсутсвие коллизий можно обеспечить выбором подходящей длины s.
код реализуюций rc4 занимает мало места.
в качестве строки s можно использовать сам код.

 

kropalik
А в rc4 зная key, и result можно восстановить исходную строку? Если да то не подходит. И еще отрезок у нас ограниченный от 0 до 0FFFFFFFFh(DWORD).

 

насколько я знаю, можно, т.к. это симметричный алгоритм

А что, если не секрет, требуется в итоге? Какая цель ставиться? А то мы тут гадаем, а все может быть намного проще?

 

kropalik

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

 

ее незачем узнавать таким методом т.к. она и так известна
в моем примере "1234ABCD" или фрагмент кода самой функции rc4().

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

да тоже неплохой вариант, особенно если важна скорость.

 

Stiver
Что означают вот ети команды на асме???
& - (and)
% - (or)
x >>= 1 - (циклический сдвиг вправо на 1)

 

А применить алгоритм генерации псевдослучайного числа?
mul <БОЛЬШОЕ ПРОСТОЕ ЧИСЛО>
add <ПРОСТОЕ ЧИСЛО ПОМЕНЬШЕ>

 

and = and
or = or
циклический сдвиг вправо на 1 = ror reg,1

 

циклический сдвиг вправо на 1 = ror reg,1
а это просто сдвиг вправо на 1 нециклический.

 

asmfan
ой, лапухнулся бейте меня, бейте в конце концов, я ж предупреждал - мнение автора может не совпадать с его точкой зрения!

П.С. да здравствует ссылочка "редактировать"