EIGamal незапатентован. Но, прежде чем двигаться вперед и реализовывать алгоритм, нужно знать, что РКР считает, что этот алгоритм попадает под действие патента Диффи-Хеллмана [718]. Однако срок действия патента Диффи-Хеллмана заканчивается 29 апреля 1997 года, что делает EIGamal первым криптографическим плго-ритмом с открытыми ключами, пригодным для шифрования и цифровых подписей и несвязанным в Соедине н-ных Штатах патентами. Я не могу дождаться этого момента.
19.7 МсЕМесе
В 1978 году Роберт МакЭлис (Robert McEliece) разработал криптосистему с открытыми ключами на основе теории алгебраического кодирования [1041]. Этот алгоритм использует существование определенного класса исправляющих ошибки кодов, называемых кодами Гоппа(Goppa). Он предлагал создать код Гоппа и замаскировать его как обычный линейный код. Существует быстрый алгоритм декодирования кодов Гоппа, но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной.Хорошее описание этого алгоритма можно найти в [1233], см. также [1562]. Ниже приведен только краткий обзор.
Пусть ddx,y) обозначает расстояние Хэмминга между хну. Числа п, ки t служат параметрами системы.
Закрытый ключ состоит из трех частей: G' - это матрица генерации года Гоппа, исправляющего t ошибок. Р -это матрица перестановок размером п*п. S - это nonsingular матрица размером к*к.
Открытым ключом служит матрица G размером k*n: G = SGP.
Открытый текст сообщений представляет собой строку к битов в виде ^-элементного вектора над полем GF(2).
Для шифрования сообщения случайным образом выбирается и-элементный вектор z над полем GF(2), для которого расстояние Хэмминга меньше или равно t.
c = mG + z
Для дешифрирования сообщения сначала вычисляется с' = сР' Затем с помощью декодирующего алгоритма для кодов Гоппа находится т' , для которого ddjn'G,c) меньше или равно L Наконец вычисляется m^m'ST1.
В своей оригинальной работе МакЭлис предложил значения п = 1024, t = 50 и к = 524. Это минимальные значения, требуемые для безопасности.
Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и вне появлялось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографическом с о-обществе. Схема на два-три порядка быстрее, чем RSA, но у нее есть ряд недостатков. Открытый ключ огромен: 219 битов. Сильно увеличивается объем данных - шифротекст в два раза длиннее открытого текста .
Ряд попыток криптоанализа этой системы можно найти в [8, 943, 1559, 306]. Ни одна из них не достигла успеха для общего случая, хотя сходство между алгоритмом МакЭлиса и алгоритмом рюкзака немного волнует.
В 1991 два русских криптографа заявили, что взломали систему МакЭлиса с некоторыми параметрами [882]. В их статье это утверждение не было обосновано, и большинство криптографов не приняли во внимание этот результат. Еще одно выполненное русскими вскрытие, которое нельзя непосредственно использовать против системы МакЭлиса, описано в [1447, 1448]. Расширения McEliece можно найти в [424, 1227, 976].