Алгоритм шифрования Эль Гамаля

Система, предложенная Эль Гамалем, является, как и RSA системой с открытым ключом. Ее криптостойкость основана на трудоемкости вычисления дискретного логарифма (т. е. трудоемкости операции логарифмирования в целых числах по модулю N).

Ключи строятся так:

Выбирается целое число P;

Выбирается число W меньшее P-1, тогда W^P-1 = 1 mod P, при этом, W^D¹1 mod P при любом 1<D<(P-1);

Выбирается 1 < X < P-1; Y:= W^X mod P;

Секретный ключ -- (X,P);

Открытый ключ -- (Y,W,P).

Шифрование блока B протекает следующим образом (открытый ключ):

1. Берется случайное число 1 < K < P-1;

2. R:= Y^K mod P;

3. Z:= W^K;

4. C:= BÅR;;

5. Результат -- пара (C,Z).

Расшифрование протекает следующим образом (секретный ключ):

1. R:= Z^X;

2. B:= CÅR.

Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость[5].

В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно, поскольку поиск решения ведётся методом перебора аргументов.

Ключом может быть любое число меньшее P потому что если P - простое число, то для любого X выполняется равенство (теорема Ферма)

Исследование цифровой подписи на примере алгоритма RSA

Цель работы

Изучить основные принципы генерации цифровой подписи. Освоить цифровую подпись на основе алгоритма RSA.

Домашнее задание

Изучить цифровую подпись на основе алгоритма RSA в соответствии с пунктом 4.6 данного методического руководства.

Записать вариант, соответствующий двум младшим цифрам номера студенческого билета.

По таблице простых чисел (ז) выбрать 2 простых числа. Номер числа P = 9+последняя цифра студенческого билета, номер числа Q = 17 + предпоследняя цифра студенческого билета.

Вычислить произведение этих чисел N=P´Q и функцию Эйлера j(N)=M=(P-1)(Q-1);

Используя алгоритм Евклида найти такое число D, взаимно простое с M, которое не является простым.

Подписать сообщение и проверить подпись (сообщение = 143) по алгоритму RSA

Все вычисления должны быть занесены в протокол в виде ה

Таблица 4.1 Цифровая подпись по алгоритму RSA

Исследуемая величина	Домашнее задание	Лабораторное задание
Простое число Р
Простое число Q
N=PQ
M=(P-1)(Q-1)
D взаимно простое с M
E=1/D (mod M)
Секретный ключ (E, N)
Открытый ключ (D, N)
Исходное сообщение B
Подпись C=B^E(mod N)
Проверка подписи B'=C^D(mod N)