Модернизация электронной подписи Эль-Гамаля - (диплом)
p>где вероятность берется по всем 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)
Здесь: u, v, w и z суть А, В, С и. D в зависимости от номера раунда и номера оператора в раунде. Mj обозначает j-тый подблок обрабатываемого блока. В каждом раунде порядок обработки очередным оператором подблоков определяется задаваемой в явном виде подстановкой на множестве всех подблоков (их, также как и операторов, 16).
tiобозначают зафиксированные случайные константы, зависящие от номера раунда и номера оператора в раунде.
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. Модернизация электронной подписи Эль Гамаля. Задача дискретного логарифмирования.
Модернизация электронной подписи Эль Гамаля.
Также, как и в обычной схеме, секретный ключ x ОR Z*p-1 и открытый ключ y = g-x mod p. Пространством сообщений в данной схеме является Zp-1 . Подписывающие выбирают случайные u1, …un , так, чтобы они были взаимно простые (т. е gcd (un, p-1) = 1). Тогда
Подписью в этом случае является набор (r1, …, rn, s) .
Для проверки подписи (r1, …, rn, s) для сообщения m необходимо сначала проверить условия r1, …, rn О Z*p и s О Zp-1 . Если хотя бы одно из них ложно, то подпись отвергается. В противном случае подпись принимается и только тогда, когда .
Идея метода состоит в том, что можно подписывать коллективом из n человек, что значительно усложнит задачу раскрытия этой подписи т. к. нам неизвестны всеu1, …un .
Задача дискретного логарифмирования.
Задача дискретного логарифмирования –одно из наиболее популярных задач, используемых в целях криптографии. Это объясняется высокой сложностью ее решения в некоторых группах. Постановка задачи.
Пусть G – некоторая мультипликативно записываемая группа, а a и b – некоторые элементы этой группы, связанные равенством b = an при некотором целом n. Любое целое x, удовлетворяющее уравнению b = ax, называется дискретным логарифмом элемента b по основанию a. Задача дискретного логарифмирования в группе G состоит в отыскании по данным a и b вышеуказанного вида некоторого дискретного логарифма b по основанию a. Если a имеет бесконечный порядок, то дискретный логарифм любого элемента по основаниюa определен однозначно. В противном случае все дискретные логарифмы b по основаниям a можно получить из некоторого такого дискретного логарифма x0 по формуле x = x0 + km, где km – порядок элемента a, а параметр k пробегает Z. Для криптографических приложений наиболее важна задача дискретного логарифмирования в мультипликативных группах конечных полейGF(q) и колец Zn Как известно, группа GF(q)* циклическая и имеет порядок q –1, поэтому если в качестве aберется некоторый порождающий этой группы, то дискретный логарифм любого элементаGF(q)* по основанию aсуществует и определен однозначно. Если логарифмировать по фиксированному основанию, которое является порождающимg группы GF(q)*, то можно находить дискретные логарифмы по произвольному основанию. Действительно, чтобы найти дискретный логарифмx элемента b по основанию a, достаточно вычислить дискретные логарифмы y и z элементов a и b по основанию a и решить уравнение xy = z(mod q – 1) относительно z. Для краткости обозначим дискретный логарифм y произвольного элемента gОGF(q)* по основанию a, удовлетворяющий неравенству 0 < y < q – 2, через log. Очевидно, что log – взаимно однозначное отображение GF(q)* на Zq-1, удовлетворяющее обычному свойству логарифма: log gh = (log g + log h) mod (q-1) для произвольных g, h ОGF(q)*.
Алгоритм Гельфонда.
В настоящее время не известно полиномиальных алгоритмов дискретного логарифмирования в произвольной группеGF(q)*. Изложенный ниже алгоритм применим к произвольной группе GF(q)* и имеет сложность O(q0, 5+e) Положить
Вычислить c = aH .
Построить наборы (cu|uО{0, 1, …, H}) и (bav|uО{0, 1, …, H}) элементов GF(q)*. Найти некоторый элемент, входящий в оба набора. Если cu = bav – такой элемент, то это значит, что и log b = (Hu –v) mod (q – 1) – искомый дискретный логарифм b по основанию a. Отметим, что любой элемент xО{0, 1, …, q-2} представим в виде x = Hu-v при некоторых u, vО{0, 1, …, H}. Поэтому элемент входящий в оба набора из этапа 3 алгоритма, существуют.
Заключение
Выбор для конкретных ИС должен быть основан на глубоком анализе слабых и сильных сторон тех или иных методов защиты. Обоснованный выбор той или иной системы защиты, в общем-то, должен опираться на какие-то критерии эффективности. К сожалению, до сих пор не разработаны подходящие методики оценки эффективности криптографических систем. Наиболее простой критерий такой эффективности - вероятность раскрытия ключа или мощность множества ключей. По сути, это то же самое, что и криптостойкость. Для ее численной оценки можно использовать также и сложность раскрытия шифра путем перебора всех ключей.
Однако этот критерий не учитывает других важных требований к криптосистемам: невозможность раскрытия или осмысленной модификации информации на основе анализа ее структуры, совершенство используемых протоколов защиты,
минимальный объем используемой ключевой информации, минимальная сложность реализации (в количестве машинных операций), ее стоимость, высокая оперативность.
Желательно конечно использование некоторых интегральных показателей, учитывающих указанные факторы. Часто более эффективным при выборе и оценке криптографической системы является использование экспертных оценок и имитационное моделирование. В любом случае выбранный комплекс криптографических методов должен сочетать как удобство, гибкость и оперативность использования, так и надежную защиту от злоумышленников циркулирующей в ИС информации.
Автор выражает благодарность своему научному руководителю Блинкову Юрию Анатольевичу за неоценимую помощь в написании данной работы. Литература:
Diffie W. , Hellman M. E. New directions in cryptography. IEEE transactions on Information Theory IT-22. 1976. 644-654 p.
Buchberger B. Groebner Bases: on Algorithmic Method in Polynomial Ideal Theory. In: Recent Trends in Multidimensional System Theory, Bose, N. K. (ed. ), Reidel, Dordrecht. 1985. 184-232 p.
Rivest R. L. , Shamir A. , Adleman L. , method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, v. 21, №2, 1978, 120-126 Rivest R. L. , The MD5 messege digest algorythm, RFC 1321, April, 1992 Блинков Ю. А. , Мыльцин В. Л. Использование базисов полиномиальных идеалов при построении односторонних функций. В кн. : Современные проблемы теории функций и их приложения. – Саратов: Изд-во Сарат. ун-та, 1997.
