Программная реализация RSA примерно в 100 раз медленнее программной реализации DES

С развитием технологии эти оценки могут несколько изменяться, но асимметричная криптосистема RSA никогда не достигнет быстродействия симметричных криптосистем.

Следует отметить, что малое быстродействие криптосистем RSA ограничивает область их применения, но не перечеркивает их ценность.

7. Схема шифрования Полига – Хеллмана

Схема шифрования Полига – Хеллмана сходна со схемой шифрования RSA. Она представляет собой несимметричный алгоритм, поскольку используются различные ключи для шифрования и расшифрования.

В то же время эту схему нельзя отнести к классу криптосистем с открытым ключом, так как ключи шифрования и расшифрования легко выводятся один из другого. Оба ключа (шифрования и расшифрования) нужно держать в секрете.

Аналогично схеме RSA криптограмма Сиоткрытый текст Р определяются из соотношений:

С = Р^е mod n,

P = C^d mod n,

где e*d º1(по модулю некоторого составного числа).

В отличие от алгоритма RSA в этой схеме числоn не определяется через два больших простых числа; число n должно оставаться частью секретного ключа. Если кто-либо узнает значения eиn, он сможет вычислить значение d.

Не зная значений eилиd, противник будет вынужден вычислять значение

e = log_P C (mod n).

Известно, что это является трудной задачей.

Схема шифрования Полига – Хеллмана запатентована в США и Канаде.

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

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

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

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

Затем выбирают случайное целое число X, причем X<P.

Число X является секретным ключом и должно храниться в секрете.

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

Для того чтобы зашифровать сообщение M, выбирают случайное целое число K, 1< 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^KM/a^X º G^KXM/G^KX º M (mod P),

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

Пример.Выберем P = 11, G = 2, секретный ключ X = 8.

Вычисляем

Y = G^X mod P = 2⁸ mod 11 = 256 mod 11 = 3.

Итак, открытый ключ Y = 3.

Пусть сообщение М = 5.

Выберем некоторое случайное число К = 9.

Убедимся, что НОД (К, Р–1) =1. Действительно, НОД (9, 10) =1. Вычисляем пару чисел aи b:

a = G^K mod P = 2⁹ mod 11 = 512 mod 11 = 6,

b =Y^K M mod P = 3⁹ * 5 mod 11 = 19683 * 5 mod 11 = 9.

Получим шифртекст (a, b) = (6, 9).

Выполним расшифрование этого шифртекста.

Вычисляем сообщение М, используя секретный ключ X:

M = b/a^X mod P = 9/6⁸ mod 11.

Выражение M = 9/6⁸ mod 11 можно представить в виде

6⁸ * M 9 mod 11

или 1679616 * M 9 mod 11.

Решая данное сравнение, находим М = 5.

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

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

Таблица 2