double arrow
Схема шифрования Эль Гамаля

Схема Эль Гамаля, предложенная в 1985 г., может быть использована как для шифрования, так и для цифровых подписей. Безопасность схемы эль гамаля обусловлена сложностью вычисления дискретных логарифмов в конечном поле.

Для того чтобы генерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < P. Числа Р и G могут быть распространены среди группы пользователей.

Затем выбирают случайное целое число X, причем X<P. Число X является секретным ключом и должно храниться в секрете.

Далее вычисляют Y = GX mod P. Число Y является открытым ключом.

Для того чтобы зашифровать сообщение M, выбирают случайное целое число k, 1< k< p –1, такое, что числа к и (P –1) являются взаимно простыми.

Затем вычисляют числа

a = GK mod P,

b = YK M mod P.

Пара чисел (a,b) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста М.

Для того чтобы расшифровать шифртекст (a,b), вычисляют

M = b/aX mod P. (*)

Поскольку

aX º GKX mod P,

b/aX ºYKM/aX º GKXM/GKX º M (mod P),

то соотношение (*) справедливо.

В реальных схемах шифрования необходимо использовать в качестве модуля P большое целое простое число, имеющее в двоичном представлении длину 512…1024 бит.

При программной реализации схемы Эль Гамаля [123] скорость ее работы (на SPARC-II) в режимах шифрования и расшифрования при 160-битовом показателе степени для различных длин модуля P определяется значениями, приведенными в табл.4.2.

Таблица 4.2

Скорости работы схемы Эль Гамаля

Режим работы Длина модуля, бит
Шифрование 0,33 с 0,80 с 1,09 с
Расшифрование 0,24 с 0,58 с 0,77 с





Сейчас читают про: