Секретная система Эль-Гамаля

Формирование системы

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

Криптосистеми з публічними ключами Ель-Гамаля

В [6] описаны две системы с публичными ключами, основанные на проблеме дискретных логарифмов. Одна из них используется для шифрования, другая — как схема подписи. В обеих системах передаваемый текст длиннее исходного открытого.

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

Довольно часто встречается вариация: рассматривают с простым, а вместо примитивного элемента берут элемент большого простого порядка, скажем,. Отметим, что число должно делить.

Каждый участник случайным образом выбирает целое число,, вычисляет, объявляет публичным, а держит в секрете.

Как вариация, каждый участник вместо общесистемных параметров может выбрать свои собственные конечное поле и примитивный элемент, но, видимо, большого смысла в этом нет.

Итак, Алиса случайным образом выбирает целое число, вычисляет, объявляет публичным, а держит в секрете. Боб случайным образом выбирает целое число, вычисляет, объявляет публичным, а держит в секрете.

Шифрование сообщения для Боба.

Предположим, что Алиса хочет послать Бобу секретное сообщение. Сообщение представлено целым числом из. Алиса выбирает случайное секретное число и вычисляет.

Затем Алиса вычисляет, где, и посылает Бобу пару.

Дешифрование сообщения Бобом.

Боб получает пару и, используя свое секретное вычисляет, и легко восстанавливает сообщение и путем следующего вычисления по модулю:

Пример 8.5 (часть 2)

Продолжаем пример 8.5. Наши публичные параметры:,,. Число известно только Бобу.

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

p=197; a=2; cB=82;

r=Random[Integer,{0,p-2}]

u=123;

R=PowerMod[a,r,197]

S=Mod[PowerMod[cB,r,197]*u,p]

|| 191

|| 117

|| 175

При дешифровании Боб вычисляет, используя свое секретное и функции Mod, PowerMod пакета "Mathematica". Заметим, что вычисляет мультипликативный обратный элемент к по модулю.

mB = 111;

Mod[S*PowerMod[PowerMod[R, mB, p], -1, p], p]

|| 123

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

Дата добавления: 2013-12-12