Открыть главное меню

Схема Эль-Гамаля

(перенаправлено с «Elgamal»)

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1985 году.[1] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Генерация ключейПравить

  1. Генерируется случайное простое число  .
  2. Выбирается целое число  первообразный корень  .
  3. Выбирается случайное целое число   такое, что  .
  4. Вычисляется  .
  5. Открытым ключом является  , закрытым ключом — число  .

Работа в режиме шифрованияПравить

Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

ШифрованиеПравить

Сообщение   должно быть меньше числа  . Сообщение шифруется следующим образом:

  1. Выбирается сессионный ключ — случайное целое число   такое, что  .
  2. Вычисляются числа   и  .
  3. Пара чисел   является шифротекстом.

Нетрудно увидеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения   вдвое.

РасшифрованиеПравить

Зная закрытый ключ  , исходное сообщение можно вычислить из шифротекста   по формуле:

 

При этом нетрудно проверить, что

 

и поэтому

 .

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

 

Схема шифрованияПравить

 

ПримерПравить

  • Шифрование
    1. Допустим, что нужно зашифровать сообщение  .
    2. Произведем генерацию ключей:
      1. Пусть  . Выберем   - случайное целое число   такое,что  .
      2. Вычислим  .
      3. Итак, открытым ключом является тройка  ,а закрытым ключом - число  .
    3. Выбираем случайное целое число   такое, что 1 < k < (p − 1). Пусть  .
    4. Вычисляем число  .
    5. Вычисляем число  .
    6. Полученная пара   является шифротекстом.
  • Расшифрование
    1. Необходимо получить сообщение   по известному шифротексту   и закрытому ключу  .
    2. Вычисляем M по формуле:  
    3. Получили исходное сообщение  .

Так как в схему Эль-Гамаля вводится случайная величина  ,то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа   такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение   и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины   для шифровки различных сообщений   и  . Если использовать одинаковые  , то для соответствующих шифротекстов   и   выполняется соотношение  . Из этого выражения можно легко вычислить  , если известно  .

Работа в режиме подписиПравить

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

Подпись сообщенийПравить

Для подписи сообщения   выполняются следующие операции:

  1. Вычисляется дайджест сообщения  :  (Хеш функция может быть любая).
  2. Выбирается случайное число   взаимно простое с   и вычисляется  
  3. Вычисляется число  , где   в степени минус 1 это мультипликативное обратное.
  4. Подписью сообщения   является пара  .

Проверка подписиПравить

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

  1. Проверяется выполнимость условий:   и  .
  2. Если хотя бы одно из них не выполняется,то подпись считается неверной.
  3. Вычисляется дайджест  
  4. Подпись считается верной, если выполняется сравнение:
     

Корректность проверкиПравить

Рассматриваемый алгоритм корректен в том смысле, что подпись, вычисленная по указанным выше правилам, будет принята при ее проверки.

Преобразуя определение  , имеем

 

Далее, из Малой теоремы Ферма следует, что

 

ПримерПравить

  • Подпись сообщения.
    1. Допустим,что нужно подписать сообщение  .
    2. Произведем генерацию ключей:
      1. Пусть     переменные, которые известны некоторому сообществу.
      2. Секретный ключ   — случайное целое число   такое, что  .
      3. Вычисляем открытый ключ  :  .
      4. Итак,открытым ключом является тройка  .
    3. Теперь вычисляем хеш-функцию:  .
    4. Выберем случайное целое число   такое, что выполняется условие  . Пусть  .
    5. Вычисляем  .
    6. Находим число  . Такое   существует, так как НОД(k,p-1)=1. Получим
    7. что  .
    8. Итак, мы подписали сообщение:  .
  • Проверка подлинности полученного сообщения.
    1. Вычисляем хеш-функцию:  .
    2. Проверяем сравнение  .
    3. Вычислим левую часть по модулю 23:  .
    4. Вычислим правую часть по модулю 23:  .
    5. Так как правая и левая части равны, то это означает что подпись верна.

Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле  . Следует сделать несколько комментариев:
  • Случайное число   должно сразу после вычисления подписи уничтожаться, так как если злоумышленник знает случайное число   и саму подпись, то он легко может найти секретный ключ по формуле:   и полностью подделать подпись.

Число   должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.

  • Использование свертки   объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа  ,удовлетворяющие условиям  , НОД(j,p-1)=1 и предположить что
     
     
     

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

  • Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения:  , в котором тройка   принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при  ,  ,  .На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения  ,  ,  , а в Российском стандарте:  ,  ,  .
  • Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел   на пару чисел  ),где   является каким-то простым делителем числа  . При этом сравнение для проверки подписи по модулю   нужно заменить на новое сравнение по модулю  :  . Так сделано в американском стандарте DSS (Digital Signature Standard).

Криптостойкость и особенностиПравить

В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:

 

ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.

Сравнение некоторых алгоритмов:

Алгоритм Ключ Назначение Криптостойкость, MIPS Примечания
RSA До 4096 бит Шифрование и подпись 2,7•1028 для ключа 1300 бит Основан на трудности задачи факторизации больших чисел; один из первых асимметричных алгоритмов. Включен во многие стандарты
ElGamal До 4096 бит Шифрование и подпись При одинаковой длине ключа криптостойкость равная RSA, т.е. 2,7•1028 для ключа 1300 бит Основан на трудной задаче вычисления дискретных логарифмов в конечном поле; позволяет быстро генерировать ключи без снижения стойкости. Используется в алгоритме цифровой подписи DSA-стандарта DSS
DSA До 1024 бит Только подпись Основан на трудности задачи дискретного логарифмирования в конечном поле; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ.
ECDSA До 4096 бит Шифрование и подпись Криптостойкость и скорость работы выше, чем у RSA Современное направление. Разрабатывается многими ведущими математиками

ПримечанияПравить

ЛитератураПравить