Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | | | | |
хе.. 14.12.01 17:47 Число просмотров: 3404
Автор: zelych Статус: Member
|
|
<theory>
|
hash 13.12.01 13:29
Автор: nimrod Статус: Незарегистрированный пользователь
|
Вчера ковырял одну ламерскую программку и наткнулся вот на такую штуку
int fu(int x1,int x2)
{ int a,b,c,d,i,j=0;
do{ a=0;
b=x1&0x80000057;
for(i=0;i<0x20;i++) {if(b&1)a++; b>>=1;}
x1=(x1>>1)&0x7fffffff;
if(a&1)x1|=0x80000000;
a=0; c=x2&x1;
for(i=0;i<0x20;i++) {if(c&1)a++; c>>=1;}
d=(d<<1)a&1);
}while(++j!=0x20);
return d;
}
int hash(int *b)
{ int x,y,i=0;
x=b[0];
do{y=b[++i]; x=fu(x,y);}while(i!=0x100);
return x;
}
Что с этим можно сделать? Не пхоже что алгоритм стойкий.
Спасибо если кто ответит
|
|
hash 13.12.01 15:06
Автор: iddqd <Юрий> Статус: Member
|
> Вчера ковырял одну ламерскую программку и наткнулся вот на > такую штуку > > int fu(int x1,int x2) > { int a,b,c,d,i,j=0; > do{ a=0; > b=x1&0x80000057; > for(i=0;i<0x20;i++) {if(b&1)a++; > b>>=1;} > x1=(x1>>1)&0x7fffffff; > if(a&1)x1|=0x80000000; > a=0; c=x2&x1; > for(i=0;i<0x20;i++) {if(c&1)a++; > c>>=1;} > d=(d<<1)a&1); > }while(++j!=0x20); > return d; > } > int hash(int *b) > { int x,y,i=0; > x=b[0]; > do{y=b[++i]; x=fu(x,y);}while(i!=0x100); > return x; > } > > Что с этим можно сделать? Не пхоже что алгоритм стойкий. > Спасибо если кто ответит
долго разбираться не стал, но, на первый взгляд, у нее будет очень много повторяющихся результатов, слишком уж много" и "&", а они необратимы. возможно, я ошибаюсь
попробуй просто в лоб. перебери пару десятков тысяч вариантов и посмотри, какой результат чаще всего повторяется и при каких значениях
|
| |
hash 13.12.01 16:59
Автор: nimrod Статус: Незарегистрированный пользователь
|
> долго разбираться не стал, но, на первый взгляд, у нее > будет очень много повторяющихся результатов, слишком уж > много" и "&", а они необратимы. возможно, я ошибаюсь
Не похоже, заполнял b[i]=(rand()<<16)|rand(), посчитал полторы тыщи хешей, количество нулей и единиц в каждом бите ОЧЕНЬ близко к половине
Единственное что заметил, если в b есть шесть или больше идущих подряд нулей - тогда хеш всегда равен нулю
> попробуй просто в лоб. перебери пару десятков тысяч > вариантов и посмотри, какой результат чаще всего > повторяется и при каких значениях
|
| | |
hash 13.12.01 17:24
Автор: iddqd <Юрий> Статус: Member
|
> Не похоже, заполнял b[i]=(rand()<<16)|rand(), > посчитал полторы тыщи хешей, количество нулей и единиц в > каждом бите ОЧЕНЬ близко к половине > Единственное что заметил, если в b есть шесть или больше > идущих подряд нулей - тогда хеш всегда равен нулю ну это уже хорошо ;)
а если сделать по-другому: составить булеву матрицу, по которой идет хеширование и по-немногу изменять ее (достроив до квадратной), пока у нее определитель не станет ненулевой, т.е. когда ей можно найти обратную, а там, может быть, проще будет. по крайней мере, можно будет прикинуть (на глаз) как она перемешивает. а потом применить что-то вроде дифференциального криптоанализа, она же (эта матрица) получается перемножением нескольких простых матриц.
З.Ы. С криптоанализом знаком только поверхностно, а потому могу сильно ошибаться
|
| | | |
hash 13.12.01 17:42
Автор: nimrod Статус: Незарегистрированный пользователь
|
> > Не похоже, заполнял b[i]=(rand()<<16)|rand(), > > посчитал полторы тыщи хешей, количество нулей и единиц > в > > каждом бите ОЧЕНЬ близко к половине > > Единственное что заметил, если в b есть шесть или > больше > > идущих подряд нулей - тогда хеш всегда равен нулю > ну это уже хорошо ;) > > а если сделать по-другому: составить булеву матрицу, по > которой идет хеширование и по-немногу изменять ее (достроив > до квадратной), пока у нее определитель не станет > ненулевой, т.е. когда ей можно найти обратную, а там, может > быть, проще будет. по крайней мере, можно будет прикинуть > (на глаз) как она перемешивает. а потом применить что-то > вроде дифференциального криптоанализа, она же (эта матрица) > получается перемножением нескольких простых матриц. > > З.Ы. С криптоанализом знаком только поверхностно, а потому > могу сильно ошибаться
Не особо понял что ты сказал, но если хешируемый блок изменить на один бит, то хеш в меняется на 13- 20 бит..
|
| | | | |
hash 13.12.01 17:59
Автор: iddqd <Юрий> Статус: Member
|
> Не особо понял что ты сказал, но если хешируемый блок да я уже сам запутался %)
> изменить на один бит, то хеш в меняется на 13- 20 бит.. ну, вообще, так и должно быть
другое дело, по какому закону все это меняется, я же говорю: матрицу построй, вдруг она там из кучи диагоналий состоит
а вообще, лучше применить дифференциальный криптоанализ, IMHO
|
| | | | | |
hash 13.12.01 18:09
Автор: nimrod Статус: Незарегистрированный пользователь
|
> > Не особо понял что ты сказал, но если хешируемый блок > да я уже сам запутался %) > > изменить на один бит, то хеш в меняется на 13- 20 > бит.. > ну, вообще, так и должно быть > другое дело, по какому закону все это меняется, я же > говорю: матрицу построй, вдруг она там из кучи диагоналий > состоит > а вообще, лучше применить дифференциальный криптоанализ, > IMHO
а если порусски?
я наверное не настолько умный, потому и обращаюсь к вам..
|
| | | | | | |
hash 13.12.01 18:33
Автор: iddqd <Юрий> Статус: Member
|
> а если порусски? ну, постораюсь ;)
> я наверное не настолько умный, потому и обращаюсь к вам.. да я, собственно, тоже не настоко умный в этом деле ;)
короче, я бы сделал так:
составил вектор, где верхняя часть разрядов состоит из х1, а нижняя из х2 (или наоборот)
представил каждое действие, например "x1=(x1>>1)&0x7fffffff", как матрицу
из всех этих матриц, в соответствии с алгоритмом, составил одну большую, на которую умножается вектор, и возвел бы ее в 32-ю степеть
то, что из нее получится, а получится, соответствено, матрица, и нужно смотреть
или расковырять сам текст проги и подставить туда вместо каждого бита, какую-нибудь метку,
а все действия заменить на конкатенацию меток и самих действий("&"," и т.п.)
проще, говоря сделать из нее простенький компилятор матриц
можно попробовать нагенерить кучу хешей и по аргументам и результатам, решив систему уравнений сгенерить эту злосчастную матрицу
|
| | | | | | | |
hash 14.12.01 12:34
Автор: zelych Статус: Member
|
всё значительно проще..
если тебе надо поменять хешируемый блок и получить определённое значение хеша, тогда вот:
int hash(int *b)
{ int x,y,i=0;
x=b[0];
do{y=b[++i]; x=fu(x,y);}while(i!=0x100);
return x;
}
если поменять b[a] на b`[a], то поменяется x начиная с i-ой итерации, соответственно надо найти такое у, что fu( b`[a], y ) = fu( b[a], b[a+1] ) и поставить его вместо b[a+1]..
получается уравнение:
дано - x и fu( x, y )
найти - y
int fu(int x1,int x2)
{ int a,b,c,d,i,j=0;
do{ a=0;
b=x1&0x80000057;
for(i=0;i<0x20;i++) {if(b&1)a++; b>>=1;}
//
x1=(x1>>1)&0x7fffffff;
// не совсем понятно зачем нужно &0x7ffff
if(a&1)x1|=0x80000000;
/* а вообще очень смахивает на регистр сдвига с полиномом обратной связи 0x80000057 и начальным заполнением x1
однако это не важно
*/ a=0; c=x2&x1;
for(i=0;i<0x20;i++) {if(c&1)a++; c>>=1;}
// а вот здесь a&1 - это скалярное произведение x2 и x1
d=(d<<1)a&1);
}while(++j!=0x20);
return d;
}
что из этого следует:
d(32-i) = <x2, x1(i+1)>, для i=0..31.
d(i) - i-й бит из d;
<.,.> - скалярное произведение;
x1(i) - регистр сдвига сдвинутый i раз.
получается 32 уравнения и 32 неизвестных..
решается очень просто:
пишем матричное уравнение
(D) = (X2)(X1)
d - строка из 32-х элементов
x2 - столбец
x1 - матрица 32х32, в которой i-я строка равна x1(i+1)
решаем матричное уранение:
(X2) = (D)(X1`), где X1` - матрица обратная к X1..
вот и всё..
P.S. глядя на исходник подумалось: "а зачем вообще люди пробелы придумали?"
|
| | | | | | | | |
А может программку напишешь, ато я не совсем разобрался?. 14.12.01 16:20
Автор: nimrod Статус: Незарегистрированный пользователь
|
|
| | | | | | | | | |
если ты всё ещё не разобрался, и если оно тебе всё ещё надо, то попробую что-нибудь написать.. 19.12.01 11:10
Автор: zelych Статус: Member
|
|
| | | | | | | | | |
хе.. 14.12.01 17:47
Автор: zelych Статус: Member
|
|
| | | | | | | | |
hash 14.12.01 13:02
Автор: iddqd <Юрий> Статус: Member
|
> всё значительно проще.. > если тебе надо поменять хешируемый блок и получить > определённое значение хеша, тогда вот: > > int hash(int *b) > { int x,y,i=0; > x=b[0]; > do{y=b[++i]; x=fu(x,y);}while(i!=0x100); > return x; > } > > если поменять b[a] на b`[a], то поменяется x начиная с i-ой > итерации, соответственно надо найти такое у, что fu( > b`[a], y ) = fu( b[a], b[a+1] ) и поставить его вместо > b[a+1].. > получается уравнение: > дано - x и fu( x, y ) > найти - y > > int fu(int x1,int x2) > { int a,b,c,d,i,j=0; > do{ a=0; > b=x1&0x80000057; > for(i=0;i<0x20;i++) {if(b&1)a++; > b>>=1;} > // > x1=(x1>>1)&0x7fffffff; > // не совсем понятно зачем нужно &0x7ffff > if(a&1)x1|=0x80000000; > /* а вообще очень смахивает на регистр сдвига с полиномом > обратной связи 0x80000057 и начальным заполнением x1
я тормоз %) это же он и есть (регистр сдвига)!!
до какого-то времени считался достаточно стойким алгоритмом
в принципе это уже можно считать ответом, если не учитывать 0x80000057 (непонятно какой у него период)
> однако это не важно
не, помоему это важно, изначально вопрос ставился о стойкости алгоритма
> */ a=0; c=x2&x1; > for(i=0;i<0x20;i++) {if(c&1)a++; > c>>=1;} > // а вот здесь a&1 - это скалярное произведение x2 и x1
если я правильно понял, это умножение на строку матрицы, или я опять что-то перепутал?
> d=(d<<1)a&1); > }while(++j!=0x20); > return d; > } > > что из этого следует: > > d(32-i) = <x2, x1(i+1)>, для i=0..31. > d(i) - i-й бит из d; > <.,.> - скалярное произведение; > x1(i) - регистр сдвига сдвинутый i раз. > > получается 32 уравнения и 32 неизвестных.. > > решается очень просто: > пишем матричное уравнение > > (D) = (X2)(X1) > d - строка из 32-х элементов > x2 - столбец > x1 - матрица 32х32, в которой i-я строка равна x1(i+1) > > решаем матричное уранение: > (X2) = (D)(X1`), где X1` - матрица обратная к X1.. > вот и всё.. > > P.S. глядя на исходник подумалось: "а зачем вообще люди > пробелы придумали?" да там, видимо, тег "pre" забыли поставить ;)
>
а вообще, классный ответ!!!! ;)
|
| | | | | | | | | |
Urix, a ты не автор статьи Гипотеза о стойкости RSA ? 14.12.01 18:54
Автор: Alban Статус: Незарегистрированный пользователь
|
Ну и как, ты разобрался со своими заблуждениями относительно RSA,
если это ты конечно? :)))
|
| | | | | | | | | | |
Urix, a ты не автор статьи Гипотеза о стойкости RSA ? 17.12.01 09:29
Автор: iddqd <Юрий> Статус: Member
|
> Ну и как, ты разобрался со своими заблуждениями > относительно RSA, > если это ты конечно? :))) не, это не я ;) меня постоянно путают с тем URIX'ом ;))))
а по поводу недостаточной стойкости RSA у меня несколько другое мнение, видимо, тоже ошибочное ;)
|
| | | | | | | | | |
hash 14.12.01 13:21
Автор: zelych Статус: Member
|
[..skip..]
> > /* а вообще очень смахивает на регистр сдвига с >> полиномом
> > обратной связи 0x80000057 и начальным заполнением x1 > я тормоз %) это же он и есть (регистр сдвига)!! > до какого-то времени считался достаточно стойким алгоритмом > в принципе это уже можно считать ответом, если не учитывать > 0x80000057 (непонятно какой у него период)
а хрен его знает, но я думаю что не проблема найти примитивный полином, так что скорее всего период максимальный (2^32-1)..
> > однако это не важно > не, помоему это важно, изначально вопрос ставился о > стойкости алгоритма
ну дырка, как мне кажется, здесь не в этом, а в том, что вся матрица (X1) запросто генерируется при известном х1..
> > // а вот здесь a&1 - это скалярное произведение x2 и > >x1 > если я правильно понял, это умножение на строку матрицы, > или я опять что-то перепутал?
точно-точно, <X,Y> = X1Y1+X2Y2+...+XnYn
|
| | | | | | | | | | |
hash 14.12.01 13:37
Автор: iddqd <Юрий> Статус: Member
|
> [..skip..] > > > /* а вообще очень смахивает на регистр сдвига с > >> полиномом > > > обратной связи 0x80000057 и начальным заполнением > x1 > > я тормоз %) это же он и есть (регистр сдвига)!! > > до какого-то времени считался достаточно стойким > алгоритмом > > в принципе это уже можно считать ответом, если не > учитывать > > 0x80000057 (непонятно какой у него период) > > а хрен его знает, но я думаю что не проблема найти > примитивный полином, так что скорее всего период > максимальный (2^32-1).. > > > > однако это не важно > > не, помоему это важно, изначально вопрос ставился о > > стойкости алгоритма > > ну дырка, как мне кажется, здесь не в этом, а в том, что > вся матрица (X1) запросто генерируется при известном х1..
т.е., по идее, можно нагенерить кучу уникальных матриц, если они часто повторяются.
а повторяться они должны. по крайней мере можно взять тот факт, что при шести нулях подряд, хэш возвращает ноль
или смысл не в этом?
> > > > // а вот здесь a&1 - это скалярное произведение > x2 и > > >x1 > > если я правильно понял, это умножение на строку > матрицы, > > или я опять что-то перепутал? > > точно-точно, <X,Y> = X1Y1+X2Y2+...+XnYn
|
| | | | | | | | | | | |
hash 14.12.01 13:54
Автор: zelych Статус: Member
|
> т.е., по идее, можно нагенерить кучу уникальных матриц, > если они часто повторяются. > а повторяться они должны. по крайней мере можно взять тот > факт, что при шести нулях подряд, хэш возвращает ноль > или смысл не в этом?
ну количество таких матриц (X1) равно 2^32 (т.к. существует прямое отображение x1 -> (X1) посредством регистра сдвига)..
а на самом деле, я хотел сказать, что если матрица (X1) не генерировалась так легко из х1, то получилась бы система с неизвестными переменными и коэффициентами при них..
тоесть сама схема изначально дырявая..
|
| | | | | | | | | | | | |
hash 14.12.01 15:41
Автор: iddqd <Юрий> Статус: Member
|
теперь вроде понял ;)
|
| | | | | | | | | | | | | |
2ALL: люди вопрос на ящик пива.. 14.12.01 19:23
Автор: zelych Статус: Member
|
собственно говоря, почти та же самая прога, только чуть-чуть по-другому:
int fu( int x1, int x2 )
{
int a, b, c, d, i, j=0;
int x1_, x2_;
x1_ = x1;
x2_ = x2;
do{
a = 0;
b = x1_&0x80000057;
for( i = 0; i < 32; i++ ) {
if( b&1 ) a++
b >>= 1;
}
x1_ = (x1_>>1) & 0x7fffffff;
if( a&1 ) x1_ |= 0x80000000;
a = 0;
b = x2_ & 0x80000057;
for( i = 0; i < 32; i++ ) {
if( b&1 ) a++
b >>= 1;
}
x2_ = (x2_>>1) & 0x7fffffff;
if( a&1 ) x2_ |= 0x80000000
a=0;
b = x1_ & x2;
for( i=0; i < 32; i++ ) {
if( b&1 ) a++;
b >>= 1;
}
c = 0;
b = x2_ & x1;
for( i=0; i < 32; i++ ) {
if( b&1 ) c++;
b >>= 1;
}
d = (d<<1) | ((a&1) ^ ~(c&1));
} while( ++j != 0x20 );
return d;
}
int hash(int *b)
{ int x,y,i=0;
x=b[0];
do{y=b[++i]; x=fu(x,y);}while(i!=0x100);
return x;
}
вообщем кто сломает тому ящик пива..
P.S. не то что бы мне это очень надо, просто пива не с кем попить..
|
|
|