Курсовая работа: Современная криптография

Лемма о композиции [DeSY]. Пусть H1 и Н2 - 2-универсальные семейства, хэш-функций, действующих из C1 в C2 и из С2 в С3 соответственно.

Тогда

Н = {h == h2 о h1 | h1 ÎH1, h2 ÎH2},

где o обозначает композицию, является 2-универсальным семейством хэш-функции, действующих из C1 в C3.

Нас эти семейства интересуют в основном как инструмент для определения и построения семейств односторонних хэш-функций.

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

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

У каждой хэш-функции hÎH имеется достаточно короткое описание h и существуют два эффективных алгоритма, первый из которых по запросу и выдает случайное hÎH, а второй по h аргументу x вычисляет h{x).

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

В-третьих, для криптографических приложений иногда требуется так называемое свойство доступности коллизий (collisionaccessibility). Оно требует существования эффективного алгоритма, который по данным х1 и х2 выбирает hÎH такую, что

h(х1) = h(х2), равновероятным образом среди всех функций из Н, удовлетворяющих этому свойству.

Пусть F = GF(2k) и chop: {0,1}k ® {0,1}k-1 - функция, которая просто отбрасывает последний бит. Тогда семейство хэш-функций {chop(ax+b)} является 2-универсальным и удовлетворяет свойству доступности коллизий.

Пусть А = {0,1}n и В {0,1}m. Для х Î {0,1}n и у Î {0,1}n+m-1 определим конволюцию у о х элементов у и х как вектор длины m, i-я координата которого

???????????? ?? ???????

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

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

Пусть {n1i} и { n0i} - две возрастающие последовательности натуральных чисел такие) что для всех in1i³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.

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

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