Заинтересовался как ведет себя хэш-функция если выполнять последовательно вычисления: h(h0)->h1, h2=h(h1), h3=h(h2)... - т.е. на каждом следующем шаге вычисляется хэш от предидущего хэша. Что будет в этом случае? "Кольцо" (не специалист в криптографии поэтому это наверное самопальное название) - те на определенном шаге хэш совпадет с одним из предшествующих? Понятно что одно кольцо точно будет, но вот сколько их на самом деле и какой они длины для хэша разрядностью n бит? sqrt(n) или что-то другое? Допустим, простейшая хэш-функция в пространстве 4-х битных чисел: H=(ROL(A,1)) XOR 5. Вычисления дают несколько несвязанных "колец": 0000->0101->1111->1010->0000 ; 0->5->F->A->0 0001->0111->1011->0010->0001 ; 1->7->B->2->1 0110->1001->0110 ; 6->9->6 0011->0011 ; 3->3 1100->1100 ;C->C Благодарю (если будут) за ссылки по данной теме (в первую очередь интересны результаты для известных таких как md5 или теоретические предсказания) или же просто за краткий рассказ.
PSR1257 Ты уверен, что имеется ввиду именно хэш? Хэш-функция, результатом которой является тот же тип данных, что и на входе, вообще-то не имеет смысла.
++ Интересно, что длина "кольца" для преобразования h=A*17h+33h для 8-ми битных числен равна 64. Это какое-то свойство?...
Д. Кнут рассматривает линейный конгруэнтный генератор во всех подробностях. В частности раскрывает вопрос подбора таких констант, чтобы циклы были как можно больше. Собственно надо просто брать два простых числа, разница между которыми равна 2. Будет один цикл.
Для несложных функций, имеющих совпадающие множества определения и значений, твой вопрос изучен довольно подробно. Для линейного конгруэнтного генератора (как указано выше) вообще "вдоль и поперек". Для таких сложных функций, как криптостойкие хеш-суммы, такой теории нет. Поэтому можешь рассматривать такое преобразование как случайный граф переходов (т.е. ориентированный граф, из каждой вершины которого выходит строго одна дуга) из 2^128 вершин, и честно применять все известные о них (в общем виде) результаты : среднее количество элементов связности, средняя длина цикла, вероятность сразу попасть на цикл, среднее количество переходов до цикла в случае попадания не на цикл, а на "тропинку" к нему, и т.д. Некоторые авторы программ боятся циклов в многократном применений хеш-функций, и поэтому, разбавляют их разнообразной (главное меняющейся в цикле) солью (как например в архиваторе RAR при установке ключа из пароля) : MD5(00000001,MD5(00000002,MD5(00000003,MD5(...))))
