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

В ряде криптографических приложений, особенно в схемах электронной цифровой подписи, необходимым элементом является криптографически стойкая

хэш-функция.

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

Наиболее эффективной с точки зрения программной реализации, оказываются хэш-функции построенные "с нуля".

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

Универсальные семейства хэш-функций.

Понятие универсального семейства хэш-функций было введено в 1979 г. Картером и Вегманом [CW].

Определение 1. Пусть А и В - два конечных множества и H - семейство функций из А в В. H называется универсальным семейством хэш-функций если для любых х1 ¹ х2 Î А и y1,y2 Î В

Вероятность берется по случайному равновероятному выбору функции h из семейства Н.

Обычно предполагается, что мощность образа (множества В) меньше, чем мощность прообраза (А), и что хэш-функции "сжимают" входные слова. Как правило, рассматриваются семейства хэш-функций, которые переводят множество всех двоичных строк длины п в множество всех двоичных строк длины m, где m < п. Говоря неформально, универсальное семейство хэш-функций — это метод "перемешивания" с сокращением длины строк, при котором выходные значения распределены равномерно.

Семейство хэш-функций из определения 1 принято назвать 2-универсалъным семейством. Если в этом определении заменить пары значений x и y на наборы из k значений, то получим определение k-универсального семейства хэш-функций .

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

Тогда

Н = h1 Î H1, h2 Î H2,

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

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

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

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

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

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

В-третьих, для криптографических приложений иногда требуется так называемое свойство доступности коллизий (collision accessibility). Оно требует существования эффективного алгоритма, который по данным х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-я координата которого

определяется по формуле

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



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

Поделитесь этой записью или добавьте в закладки