"Цикличность" (кольца) хэш-функции

Тема в разделе "WASM.CRYPTO", создана пользователем PSR1257, 7 авг 2009.

  1. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Заинтересовался как ведет себя хэш-функция если выполнять последовательно вычисления:

    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 или теоретические предсказания) или же просто за краткий рассказ.
     
  2. Ustus

    Ustus New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2005
    Сообщения:
    834
    Адрес:
    Харьков
    PSR1257
    Ты уверен, что имеется ввиду именно хэш? Хэш-функция, результатом которой является тот же тип данных, что и на входе, вообще-то не имеет смысла.
     
  3. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Да, именно так. md5(...md5(md5(md5(a)))...) - типа такого. Многократный хэш. Встречал несколько раз.
     
  4. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    ++ Интересно, что длина "кольца" для преобразования h=A*17h+33h для 8-ми битных числен равна 64. Это какое-то свойство?...
     
  5. r90

    r90 New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2005
    Сообщения:
    898
    Д. Кнут рассматривает линейный конгруэнтный генератор во всех подробностях. В частности раскрывает вопрос подбора таких констант, чтобы циклы были как можно больше. Собственно надо просто брать два простых числа, разница между которыми равна 2. Будет один цикл.
     
  6. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    Для несложных функций, имеющих совпадающие множества определения и значений, твой вопрос изучен довольно подробно.
    Для линейного конгруэнтного генератора (как указано выше) вообще "вдоль и поперек".

    Для таких сложных функций, как криптостойкие хеш-суммы, такой теории нет. Поэтому можешь рассматривать такое преобразование как случайный граф переходов (т.е. ориентированный граф, из каждой вершины которого выходит строго одна дуга) из 2^128 вершин, и честно применять все известные о них (в общем виде) результаты : среднее количество элементов связности, средняя длина цикла, вероятность сразу попасть на цикл, среднее количество переходов до цикла в случае попадания не на цикл, а на "тропинку" к нему, и т.д.

    Некоторые авторы программ боятся циклов в многократном применений хеш-функций, и поэтому, разбавляют их разнообразной (главное меняющейся в цикле) солью (как например в архиваторе RAR при установке ключа из пароля) : MD5(00000001,MD5(00000002,MD5(00000003,MD5(...))))