Шифрование ElGamal

Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения Mсначала выбирается случайное число k, взаимно простое с p- 1. Затем вычисляются

a= g^kmod p

b= y^k Mmod p

Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого текста. Для дешифрирования (a,b) вычисляется

M= b/a^xmod p

Так как a^xº g^kx(mod p) и b/a^xº y^k M/a^x º g^xk M / g^kx = M (mod p), то все работает (см. Табл. 19-6). По сути это то же самое, что и обмен ключами Диффи-Хеллмана (см. раздел 22.1)за исключением того, что y- это часть ключа, а при шифровании сообщение умножается на y^k.

Табл. 19-6.
Шифрование ElGamal

Открытый ключ:

p	простое число (может быть общим для группы пользователей)
g	<p (может быть общим для группы пользователей)
y	= gx mod p

Закрытый ключ:

x

<p

Шифрование:

k	выбирается случайным образом, взаимно простое с p-1
a	(шифротекст) = gk mod p
b	(шифротекст)= yk Mmod p

Дешифрирование:

M (открытый текст) = b/axmod p

Скорость

Некоторые примеры скорости работы программных реализаций EIGamal приведены в Табл. 19-7 [918].

Табл. 19-7.
Скорости EIGamal для различных длин модулей при 160-битовом показателе степени (на SPARC II)

	512 битов	768 битов	1024 битов
Шифрование	0.33 с	0.80 ñ	1.09 ñ
Дешифрирование	0.24 ñ	0.58 ñ	0.77 ñ
Подпись	0.25 ñ	0.47 ñ	0.63 ñ
Проверка	l.37 ñ	5.12 ñ	9.30 c

Патенты

ElGamal незапатентован. Но, прежде чем двигаться вперед и реализовывать алгоритм, нужно знать, что PKP считает, что этот алгоритм попадает под действие патента Диффи-Хеллмана [718]. Однако срок действия патента Диффи-Хеллмана заканчивается 29 апреля 1997 года, что делает ElGamal первым криптографическим плгоритмом с открытыми ключами, пригодным для шифрования и цифровых подписей и несвязанным в Соединенных Штатах патентами. Я не могу дождаться этого момента.

McEliece

В 1978 году Роберт МакЭлис (Robert McEliece) разработал криптосистему с открытыми ключами на основе теории алгебраического кодирования [1041]. Этот алгоритм использует существование определенного класса исправляющих ошибки кодов, называемых кодами Гоппа (Goppa).Он предлагал создать код Гоппа и замаскировать его как обычный линейный код. Существует быстрый алгоритм декодирования кодов Гоппа, но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной. Хорошее описание этого алгоритма можно найти в [1233], см. также [1562]. Ниже приведен только краткий обзор.

Пусть d_H(x,y) обозначает расстояние Хэмминга между xи y. Числа n, k и tслужат параметрами системы.

Закрытый ключ состоит из трех частей: G'- это матрица генерации года Гоппа, исправляющего tошибок. P-это матрица перестановок размером n*n. S- это nonsingular матрица размером k*k.

Открытым ключом служит матрица G размером k*n: G= SG'P.

Открытый текст сообщений представляет собой строку kбитов в виде k-элементного вектора над полем GF(2).

Для шифрования сообщения случайным образом выбирается n-элементный вектор z над полем GF(2), для которого расстояние Хэмминга меньше или равно t.

c = mG+ z

Для дешифрирования сообщения сначала вычисляется c'= cP^-1. Затем с помощью декодирующего алгоритма для кодов Гоппа находится m', для которого d_H(m'G,c) меньше или равно t.Наконец вычисляется m = m'S^-1.

В своей оригинальной работе МакЭлис предложил значения n= 1024, t= 50 и k= 524. Это минимальные значения, требуемые для безопасности.

Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и вне появлялось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографическом сообществе. Схема на два-три порядка быстрее, чем RSA, но у нее есть ряд недостатков. Открытый ключ огромен: 2¹⁹ битов. Сильно увеличивается объем данных - шифротекст в два раза длиннее открытого текста.

Ряд попыток криптоанализа этой системы можно найти в [8, 943, 1559, 306]. Ни одна из них не достигла успеха для общего случая, хотя сходство между алгоритмом МакЭлиса и алгоритмом рюкзака немного волнует.

В 1991 два русских криптографа заявили, что взломали систему МакЭлиса с некоторыми параметрами [882]. В их статье это утверждение не было обосновано, и большинство криптографов не приняли во внимание этот результат. Еще одно выполненное русскими вскрытие, которое нельзя непосредственно использовать против системы МакЭлиса, описано в [1447, 1448]. Расширения McEliece можно найти в [424, 1227, 976].