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

Электронная подпись RSA

Система электронной подписи RSA получается при "смене мест" ключей e и d, т.е. шифрование сообщения для получения подписи производится с помощью ключа KR = {d,n}.
Цифровой подписью сообщения является число s: S = M ^d mоd (n), которое передается вместе с сообщением.

Проверка подлинности подписанного сообщения [M,S]: M =S^e mod (n)

Равенство чисел принятого сообщения и расшифрованной подписи доказывает, что сообщение M было подписано обладателем секретного ключа d, соответствующего ключу проверки подписи e, т.е. авторизует сообщение.

Протокол работы пары абонентов сети общей связи с алгоритмом RSA выглядит так.

1. Абоненты A (отправитель) и B (получатель) генерируют независимо друг от друга пары простых чисел: p_a, q_a и p_b, q_b

2. Вычисляют произведение больших простых чисел: N_a = p_a * q_a и N_b = p_b * q_b

3. Вычисляют ключи: E_a и D_a и E_b и D_b

4. Числа N_a, N_b и E_a, E_b помещаются в общедоступный справочник и получают статус открытых ключей; числа D_a, D_b сохраняются в качестве закрытых ключей;

5. Обмен зашифрованными сообщениями:

А посылает В C _a = M_a ^Eb mоd(N_b),зашифрованное открытым ключом пользователя B.

В посылает А C_b = M_в ^Ea mоd(N_a),зашифрованное открытым ключом пользователя A.

6. Расшифрование:пользователь А → M_в = C_b ^Da mоd(N_a)

пользователь В → M_a = C_a ^Db mоd(N_b)

Формирование цифровой подписи:

1. Абоненты подписывают и шифруют сообщения:

А → S_a = M_a ^Da mоd(N_a)C _a = M_a ^Eb mоd(N_b);

В → S_b = M_b ^Db mоd(N_b)C_b = M_b ^Ea mоd(N_a).

2. ПередаютА → В: S_a,C _a В → А: S_b,C_b.

3.РасшифровываютА: M_b = С_b ^Da mоd(N_a), В: M_a = С_a ^Db mоd(N_b)

4. Проверяют подлинность подписи

В: M_a = S_a ^Ea mоd(N_a), А: M_b = S_b ^Eb mоd(N_b)

В случае равенства значений принятых и расшифрованных M_a и M_b сообщения считаются переданными без искажения, а пользователи А и В аутентифицированы.

Алгоритм Эль-Гамаля может использоваться для формирования электронной подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется простое число p и два случайных числа g и x, каждое из которых меньше p. Затем вычисляется:

y = g^x mod p

Открытым ключом являются y, g, и p. при этом числа g и p можно сделать общими для группы пользователей. Секретным ключом является x.

Схема шифрования

Модификация алгоритма позволяет шифровать сообщения. Для шифрования сообщения M, выбираем случайное секретное число k, взаимно простое с p – 1 (т.е. НОД этих чисел равен 1). После этого вычисляем:

a = g^k mod p

b = y^k M mod p

Пара чисел a и b является шифротекстом. Причем, длина шифротекста вдвое длинней открытого текста.

Для расшифрования a и b, вычисляем:

M = b/a^x mod p

Учитывая тот факт, что:

a^x ≡ g^kx (mod p)

и

b/a^x ≡ y^k M/a^x ≡ g^xk M/g^xk ≡ M (mod p),

то вышеприведенные формулы верны.

Схема подписи.

Для подписания сообщения M, вначале выберем случайное число k, такое, что k взаимно простое с p – 1. После чего вычисляем:

a = g^k mod p

и, используя расширенный алгоритм Евклида, решаем уравнение относительно числа b:

M = (xa + kb) mod (p – 1)

Подписью является пара чисел: a и b. Случайное число k должно держаться в строгом секрете и являться уникальным для каждого подписываемого сообщения М.

Для проверки правильности подписи, проверяется следующее равенство:

y^a a^b mod p = g^M mod p

В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.

Дата добавления: 2014-01-07