Современная криптография

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

В данной дипломной работе в качестве алгоритма построения хэш-функции использовался алгоритм Ривеста 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 соответственно.

Тогда

Н = {h == h2 о h1 | 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-я координата которого

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

Тогда семейство 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 –старшая и младшая  части входного блока меняются  местами;

V =1010…1010 (128 бит) в двоичной  записи.

Vj = d||Aj1||d||Aj2||d||Aj3||d||Aj4; здесь || обозначает конкатенацию бинарных строк;

d = 00…00 в двоичной записи;

Ajk = 4 * (j-1) + k (k = 1,2,3,4: Ajk длинной 8 бит);

PS – преобразующая функция.

На рисунке 2 представлена схема преобразующей функции. Каждый из аргументов при этом разбивается на 4 блока:X1||X2||X3||X4, P= P1||P2||P3||P4, схема вычисления функции f представлена на рисунке 3.

S0(a,b) = (левый циклический сдвиг на 2 бита) ((a+b)mod256):

S1(a,b) = (левый циклический сдвиг на 2 бита) ((a+b+1)mod256):

Результат действия преобразующей  функции PS предыдущего шага становится входным аргументом очередной преобразующей функции PS.

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

MD5.

В этом алгоритме размер хэш-кода равен 128 битам.

После ряда начальных действий MD5 разбивает текст на блоки длинной 512 битов, которые, в свою очередь делятся на 16 подблоков по 32 бита. Выходом алгоритма являются 4 блока по 32 бита, конкатенация которых образует 128-битовый хэш-код.

Сначала текст дополняется  таким образом, чтобы длина получаемого  текста, выраженная в битах, стала  на 64 меньше числа, кратного 512.

Дополнение осуществляется приписыванием к концу сообщения единицы и затем необходимого числа нулей (в бинарном представлении). Затем к тексту приписывается 64-битовое представление длины исходного сообщения. Таким образом, получается текст, длина которого кратна 512 битам. Инициализируются 4 переменных размером по 32 бита;

А = 01 23 45 67;

В = 89 AB CD EF;

С = FE DC BA 98;

D = 76 54 32 10.

Далее начинает работу основной цикл алгоритма. Основной цикл повторяется  столько раз, сколько блоков по 512 битов присутствует в хэшируемом сообщении.

Создаются копии инициализированных переменных: АА для А, ВВ для В, СС для С, DD для D.

Каждый основной цикл состоит  из 4 раундов. В свою очередь, каждый раунд состоит из 16 операторов. Все операторы однотипны и имеют вид:

u = v + ((F(v, w, z) + Mj + tj) << Sj).

Здесь: u, v, w и z суть А, В, С и. D в зависимости от номера раунда и номера оператора в раунде.

Mj обозначает j-тый подблок обрабатываемого блока. В каждом раунде порядок обработки очередным оператором подблоков определяется задаваемой в явном виде подстановкой на множестве всех подблоков (их, также как и операторов, 16).

ti обозначают зафиксированные случайные константы, зависящие от номера раунда и номера оператора в раунде.

<<si, обозначает левый циклический сдвиг аргумента на si, битов. Величины сдвигов также зависят от номера раунда и номера оператора в раунде.

F(v,w,z) - некоторая функция (фиксированная для каждого раунда), действующая покоординатно на биты своих трех аргументов..

В первом, раунде действует  функция F{X,Y,Z) = XY  \/  (not X)Z.

    Во втором раунде действует функция G(X,Y,Z) = XZ  \/ (not Z)Y.

    В третьем раунде действует функция Н{Х,Y,Z)Å = ХÅY ÅZ.

    В четвертом раунде действует функция I(Х,Y,Z) = YÅ(X \/ (not Z)).

 Функции подобраны таким образом, чтобы при равномерном и независимом распределении битов аргументов выходные биты были бы также распределены равномерно и независимо.

Основной цикл алгоритма  завершается суммированием полученных А, В, С и D и накапливаемых АА, ВВ, СС и DD, после чего алгоритм переходит к обработке нового блока данных. Выходом алгоритма является конкатенация получаемых после последнего цикла А, В, С и D.

Схемы хэширования, использующие алгоритмы блочного шифрования.

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

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

Однако при таком подходе  возникают две проблемы. Во-первых, размер блока большинства блочных шифров (для DESa — 64 бита) недостаточен для того, чтобы хэш-функция была устойчива против метода на основе парадокса дня рождения. Во-вторых, предлагаемый метод требует задания некоторого ключа, на котором происходит шифрование. В дальнейшем этот ключ необходимо держать в секрете, ибо злоумышленник, зная этот ключ и хэш-значение, может выполнить процедуру в обратном направлении. Следующим шагом в развитии идеи использовать блочный шифр для хэширования является подход, при котором очередной блок текста подается в качестве ключа, а хэш-значение предыдущего шага — в качестве входного блока. Выход алгоритма блочного шифрования является текущим хэш-значением (схема Рабина). Существует масса модификаций этого метода, в том числе хэш-функции, выход которых в два раза длиннее блока.

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

1) Hi = EMi(Hi-1) Å H i-1 (схема Дэвиса — Мейера);

2) Hi = Енi-1(Мi) Å H i-1 Å Mi (схема Миягучи);

3) Hi = Енi-1(Мi) ÅМi, (схема Матиаса, Мейера, Осиаса);

4) Hi = Енi-1(H i-1 Å Mi) Å H i-1 Å Mi;

5) Hi = Енi-1(H i-1 Å Mi)  Å Mi;

6) Hi = ЕMi(Mi Å H i-1) Å MiÅ H i-1;

7) Hi = ЕMi (H i-1) Å MiÅ H i-1;

8) Hi = ЕMi (Mi Å H i-1) Å H i-1;

9) Hi = Енi-1Å Mi(Mi)  Å Hi-1;

10) Hi = Енi-1Å Mi(Hi-1)  Å Hi-1;

11) Hi = Енi-1Å Mi(Mi)  Å Mi;

 12) Hi = Енi-1Å Mi(Hi-1)  Å Mi;

где Ek(M) обозначает результат применения алгоритма блочного шифрования с ключом k к блоку М.

Во всех подобных схемах полагают Н0 = Iн, где Iн — начальное значение. Для алгоритмов блочного шифрования с размером ключа в два раза большим чем размер шифруемого блока (например, IDEA) в 1992 году была предложена модифицированная схема Дэвиса—Мейера:

Н0 = Iн, где Iн — начальное значение;

Нi = Енi-1,Mi(Hi-1).

Стойкость подобных схем зависит от криптографических и иных свойств алгоритмов блочного шифрования, лежащих в их основе. В частности, даже если алгоритм шифрования является стойким, некоторые из предложенных схем обладают коллизиями [MOI]. К подобным эффектам могут приводить такие свойства алгоритма шифрования как комплиментарность

(шифрование инвертированного  открытого текста на инвертированном  ключе приводит к инвертированному  шифртексту), наличие слабых и  полуслабых ключей и т. п.

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

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

Схема Приниля — Босселэра — Гувертса — Вандервалле [PrBGV]

где Li, Ri, — левая и правая половины очередного блока хэшируемого текста. Хэш-кодом является конкатенация последних значений Gi, Hi.

Глава 4. Модернизация электронной подписи  Эль Гамаля. Задача дискретного логарифмирования.

Модернизация  электронной подписи Эль Гамаля.