Модернизация электронной подписи Эль Гамаля.
Также, как и в обычной схеме, секретный ключ 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.