О стойкости криптосистемы Эль-Гамаля

Сформулируем задачу криптоанализа системы Эль-Гамаля: при заданных значениях ,,и найти такие целые и , чтобы выполнялось и , и далее вычислить .

Такая задача сводится к дискретному логарифмированию по модулю, что для больших чисел, практично нерешаемо.

Отметим:

1. При выборе модуля надо исключать случаи, когда логарифмирование может быть эффективно – нельзя выбирать модуль , для которого число имеет большой простой делитель (иначе логарифм можно найти по алгоритму Силвера – Полига – Хеллмана). Рекомендована длина 1024 бита (300 десятичных цифр).

2. В схему Эль-Гамаля вводится случайный рандомизатор, поэтому шифр можно назвать шифром многозначной замены. Из-за случайности выбора рандомизатора схему еще называют схемой вероятностного шифрования. Это преимущество шифра, так как открытый текст и ключ не задают криптограмму однозначно.

3. В системе Эль-Гамаля с модулем из 150 знаков достигается такая же стойкость, как и в RSA с модулем длиной 200 знаков. Результат: увеличение скорости обработки информации в 5 – 7 раз.

§18. Атака на основе использования

одинаковых рандомизаторов

Пусть два пользователя криптосистемы Эль-Гамаля зашифровали два открытых текста и на одинаковых открытых и закрытых ключах и с одинаковым рандомизатором :

– криптограмма текста , где ;

– криптограмма текста ,.

Тогда . Поэтому зная открытый текст , и обе криптограммы, криптоаналитик может провести такую атаку:,

1. Вычислить .

2. Найти .

Вывод: шифровать разные открытые тексты надо с помощью разных рандомизаторов.

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