Криптографическая система Эль-Гамаля

Помимо RSA есть другая криптосистема с открытым ключом Эль-Гамаля (ElGamal), которая названа по имени ее изобретателя, Тахира Эль-Гамаля (Taher ElGamal).

Если p – очень большое простое число, e₁ – первообразный корень в группе и r – целое число, тогда e₂ = e₁^r mod p просто вычисляется с использованием быстрого показательного алгоритма (метод «возведения в квадрат и умножения»). Но по данным e₂, e₁ и p, невозможно вычислить r = log_e1e2 mod p (проблема дискретного логарифма).

Рис. 8 показывает генерацию ключей, шифрование и дешифрование в криптосистеме Эль-Гамаля.

Рис. 8 Генерация ключей, шифрование, и дешифрование в криптосистеме Эль-Гамаля

Определение общедоступного и частного ключей

• Выбор двух взаимно простых чисел p и e₁, e₁<p

• Выбор значения секретного ключа d, d<p

• Определение значения открытого ключа e₂ из выражения:

e₂=e₁^d (mod p)

• Общедоступный ключ (e₁,e₂,p) может быть объявлен публично

Боб использует данный алгоритм, чтобы создать свой общедоступный и частный ключи. Любой может передавать сообщение Бобу, используя открытый ключ. Процесс шифрования сообщения представлен ниже.

Алгоритм шифрования сообщения P

• Выбор случайного числа r, удовлетворяющего условию:

0≤r<p-1 и НОД(r,p-1)=1

• Определение значения C₁ из выражения: C₁=e₁^r (mod p)

• Определение значения C₂ из выражения: C₂=e₂^r P(mod p)

• Криптограмма С, состоящая из C₁ и C₂, отправляется получателю

• Получатель расшифровывает криптограмму с помощью выражения:

P = [C₂(C₁^d)^-1]mod p

Пример 6

Боб выбирает 11 в качестве p. Затем он выбирает e₁ = 2. Обратите внимание, что 2 – первообразный корень в Z_11* (см. приложение J). Затем Боб выбирает d = 3 и вычисляет e₂ = e₁^d = 8. Получены открытые ключи доступа – (2, 8, 11) и секретный ключ – 3. Алиса выбирает r = 4 и вычисляет C₁ и C₂ для исходного текста 7.

Исходный текст: 7

C₁ = e₁^r mod 11 = 16 mod 11= 5 mod 11

C₂ = (P × e₂^r) mod 11 = (7 × 4096) mod 11 = 6 mod 111

Зашифрованный текст: (5, 6)

Боб получает зашифрованные тексты (5 и 6) и вычисляет исходный текст.

Зашифрованный текст: [C₁ × (C₂^d)^-1] mod 11 = 6 × (5³)^-1 mod 11 = 6 × 3 mod 11 = 7 mod 11

Исходный текст: 7