Процедура создания ключей

№ п/п	Описание операции	Пример
	Выбираются простое число p и два любых случайных числа g и x меньше p.	p=23, g=3, x=5
	Вычисляется y = gx mod p	y = 35 mod 23 = 243 mod 23 = 13
	Открытый ключ - y, g и p. Причем g и p можно сделать общими для группы пользователей. Закрытый ключ - x.

Перед шифрованием вначале выбирается k взаимно простое с p-1, после чего шифрограмма генерируется по следующим формулам

a = g^k mod p, (10)

b = (y^k mod p) Å T, (11)

где a, b – зашифрованное сообщение.

Дешифрование сообщения выполняется по следующей формуле

T = (a^x mod p) Å b. (12)

Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k=7 приведен в таблице. Первая часть шифрованного сообщения - a = 37 mod 23 = 2.

Таблица 8

Пример шифрования по алгоритму Эль-Гамаля

Открытое сообщение, символ	А	Б	Р	А	М	О	В
Код символа
Вторая часть шифрограммы, b = (137 mod 23) Å T = 9 Å T
Открытое сообщение, T = (25 mod 23) Å b = 9 Å b

Алгоритм на основе задачи об укладке ранца.

Проблема укладки ранца формулируется следующим образом. Дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению?

Более формально задача формулируется так: дан набор значений M₁, M₂,..., М_n и суммарное значение S; требуется вычислить значения b_i такие что

S = b₁М₁+b₂М₂ +... + b_nМ_n, (13)

где n – количество предметов;

b_i - бинарный множитель. Значение b_i = 1 означает, что предмет i кладут в рюкзак, b_i = 0 - не кладут.

Например, веса предметов имеют значения 1, 5, 6, 11, 14, 20, 32 и 43. При этом можно упаковать рюкзак так, чтобы его вес стал равен 22, использовав предметы весом 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его вес стал равен 24.

В основе алгоритма, предложенного Мерклом и Хеллманом, лежит идея шифрования сообщения на основе решения серии задач укладки ранца.

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

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

Таблица 9