Практическое занятие №9 по дисцеплине Основы криптографии и стеганографии

Асимметричный алгоритм шифрования Эль-Гамаля
.
Кафедра "ИБ"

включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема

Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).
Данная система является альтернативой алгоритму RSA и при равном значении ключа обеспечивает ту же криптостойкость. Метод Эль-Гамаля основан на трудности вычисления дискретных логарифмов в конечном поле. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно.

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

Алгоритм работы Эль-Гамаля

Для генерации пары ключей сначала генерируется такое простое число p чтобы выполнялось равенство g=2q+1, где q также простое число, и выбирается число g удовлетворяющее условиям 1gp-1и gq(modp)1, и число x, удовлетворяющее условию 1xp-1. Затем вычисляется y=gx(mod p).
Открытым ключом являются y, g и p. И g, и p можно сделать общими для группы пользователей. Закрытым ключом является x.
Для шифрования сообщения M сначала выбирается случайное число k, взаимно простое с p–1. Затем вычисляются a=gk(mod p), b=ykM(mod p).
Пара (a,b) является шифротекстом. Получаемый шифротекст в два раза длиннее открытого текста.
Для расшифровывания (a,b) вычисляется M=(b(ax)-1)modp или M=bap-1-x(modp), где (ax)-1 – обратное значение числа ax по модулю p.

Использованная в таблице запись =(mod()) означает, что при целочисленном делении

числа  на число  остаток равен. Например, 7=1(mod(3)).
Примечание 2. Рекомендуемый размер числа p : 21024 , числа g - 2515, причем g

по следующим формулам:
a=gk(mod p), b=ykM(mod p);
M=bap-1-x(modp),
где a, b – числовые

эквиваленты символов шифрованного сообщения, М - числовой эквивалент символов открытого сообщения.
Абонент А решил послать сообщение абоненту В. Допустим, что требуется переслать число 2. Для шифрования сообщения сначала выбирается случайное число k, удовлетворяющее условию НОД(р-1,k)=1, k=5. Далее вычисляется пара шифр текста (a,b) то есть:
a=55(mod23)=3125(mod23)=20,
b=105*2(mod23)=200000(mod23)=15,
(a,b)=(20,19)
Напомним, что числа y=10, g=5, p=23 являются открытым ключом абонента В. В линию передается пара чисел (20,19), которое является шифром исходного числа 2.
Получив шифрограмму, абонент В использует свой секретный ключ x=3. Вычисляет M:
M=15*2023-1-3(mod23)=15*5242880000000000000000000(mod23)=
=78643200000000000000000000(mod23)=2
В данном случае остаток от деления равен 2, значит, шифрация и дешифрирование произошли правильно. Было передано число 2, и это же число было принято после всех преобразований.
Предположим, что абонент В решил ответить абоненту А число 3, то абонент В выбирает k=3, такое что НОД(р-1,k) и вычисляет пару (a,b):
a=33(mod7)=6, b=23*3(mod7)=3, (a,b)=(7,3).
В линию передается пара чисел (7,3), которое является шифром исходного числа 3.
Получив шифрограмму, абонент А использует свой секретный ключ x=2. Вычисляет M:
M=3*64(mod7)=3.
В результате дешифрации на приемной стороне получено число 3, которое отправил абонент В.
Понятно, что таким образом последовательно передается целое сообщение, но преобразование над каждым символом происходит по рассмотренной схеме. Заметим, что для использования этого метода необходимо сообщение предварительно преобразовать в набор чисел, например, с помощью кодовой таблицы.

схеме: А передал зашифрованное сообщение В, В передал зашифрованное сообщение

А. Перед началом шифрования сообщение предварительно преобразовать в набор чисел, с помощью "квадрата Полибия".
Рассмотреть следующие ассиметричные алгоритмы: DSA, ECDSA, Криптосистема Рабина, CEILIDH.