Патенты. EIGamal незапатентован. Но, прежде чем двигаться вперед и реализовывать алгоритм, нужно знать, что РКР считает

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'ST¹.

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

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

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