Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата

Тогда семейство H = { (a о х) Å b | a Î {0,1}n+m-1 , b Î {0,1}m} представляет собой универсальное семейство хэш-функций.

Семейства односторонних хэш-функций.

Пусть {n1i} и { n0i} -  две возрастающие последовательности натуральных чисел такие) что для всех i  n1i ³ n0i и существует такой полином q, что q(n0i,) ³ n1.

(такие последовательности полиномиально связаны).

Пусть Нk -  коллекция функций такая, что для всех h Î Hk

и пусть .

Предположим, что А  - вероятностный алгоритм, работающий за поли-номиальное время, который на входе k выдает строку x Î {0,1}n1k, называемую исходным значением, и затем для данной случайной h Î Hk пытается найти  у Î {0,1}n1k такое, что h{x) = h{y), но х ¹  у.

Определение 2. Семейство U называется универсальным семейством односторонних хэш-функций, если для всех полиномов р, для всех полиномиальных вероятностных алгоритмов А и всех достаточно больших k выполняются следующие условия:

x Î {0,1}n1k -  исходное значение для А, то

Рг[А(h,x) = у, h{x) - h(y), у ¹  х] < 1/p(n1k),

где вероятность берется по всем h из Hk и по всем случайным выборам алгоритма А.

2. Для любой h Î Hk существует описание h. полиномиальной (от n1k) длины такое, что по этому описанию и по х значение h(x) вычислимо за полиномиальное время.

3. Коллекция Hk доступна, т. е. существует алгоритм G, который на входе k равномерно по вероятности генерирует описание функции h Î Hk .

Заметим, что Hk рассматривается как набор описаний функций: два разных описания могут соответствовать одной и той же функции.

В данном определении А - это машина Тьюринга (однородная модель). Определение универсального семейства односторонних хэш-функций, а котором А - полиномиальная схема (неоднородная модель) формулируется аналогично, но в п. 1 вероятность берется только по выбору h из Hk.

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

Алгоритмы построения хэш-функций.

N –хэш.

Алгоритм разработан Nippon Telephone & Telegraph. N- хэш использует блоки длинной 128 бит, размешивающую функцию. На вход пошаговой  хэш-функции в качестве аргумента поступают очередной блок сообщения Mi длинной 128 бит и хэш-код hi-1 предыдущего шага.

h0 = I, где I – синхропосылка.

hi = g(Mi,hi-1) Å Mi Å hi-1.

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

Функция g вначале меняет местами старшие и младшие части (по 64 бита каждая) хэш-кода предыдущего шага, покоординатно складывая полученное значение с величиной 1010…..1010 и текущим блоком текста Mi. Полученная величина поступает на вход каскада из N (n = 8) преобразующих функций. Вторым аргументом каждой из преобразующих функций является хэш-код предыдущего шага, сложенный покоординатно с одной из восьми констант.

На рисунке 1 использованы следующие условные обозначения:

EXG –старшая и младшая части входного блока меняются местами;

Рекомендуем скачать другие рефераты по теме: ответы 10 класс, тесты для девочек.





Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата