Шифр Эль-Гамаля

Шифр Эль-Гамаля

Схема Эль-Гамаля (Elgamal) — криптосистема, предложенная в 1984 году. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США и России.

Содержание

Генерация ключей

  1. Генерируется случайное простое число p длины n.
  2. Выбирается произвольное целое число g, являющееся первообразным корнем по модулю p.
  3. Выбирается случайное число x из интервала (1,p), взаимно простое с p-1.
  4. Вычисляется y = gxmod p.
  5. Открытым ключом является тройка (p,g,y), закрытым ключом — число x.

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

Шифрование

Сообщение М шифруется так:

  1. Выбирается случайное секретное число k, взаимно простое с p − 1.
  2. Вычисляется a = gkmod p, b = ykMmod p, где M — исходное сообщение.
  3. Пара чисел (a,b) является шифротекстом.

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

Расшифрование

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

M = b(a^x)^{-1}\,\bmod\,p.

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

a^x\equiv g^{kx}\pmod{p} и \frac{b}{a^x}\equiv \frac{y^kM}{a^x}\equiv \frac{g^{xk}M}{g^{xk}}\equiv M \pmod{p}.

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

При работе в режиме подписи предполагается наличие фиксированной хеш-функции h(), значения которой лежат в интервале (1,p − 1).

Подпись сообщений

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

  1. Вычисляется дайджест сообщения M: m = h(M).
  2. Выбирается случайное число 1 < k < p − 1 взаимно простое с p-1 и вычисляется r = g^k\,\bmod\,p.
  3. С помощью расширенного алгоритма Евклида вычисляется число s, удовлетворяющее сравнению:
    m \equiv xr + ks\pmod{p-1}.
  4. Подписью сообщения M является пара (r,s).

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

Зная открытый ключ (p,g,y), подпись (r,s) сообщения M проверяется следующим образом:

  1. Проверяется выполнимость условий: 0 < r < p и 0 < s < p − 1. Если хотя бы одно из них не выполняется, то подпись считается неверной.
  2. Вычисляется дайджест m = h(M).
  3. Подпись считается верной, если выполняется сравнение:
     y^r r^s \equiv g^m \pmod{p}.

Криптостойкость

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

y \equiv g^x \pmod{p}.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Шифр Эль-Гамаля" в других словарях:

  • Схема Эль-Гамаля — Данные в этой статье приведены по состоянию на ГОСТ Р 34.10 94. Вы можете помочь, обновив информацию в статье …   Википедия

  • Шифрование — Шифрование  преобразование информации в целях сокрытия от неавторизованных лиц, с предоставлением, в это же время, авторизованным пользователям доступа к ней. Главным образом, шифрование служит задаче соблюдения конфиденциальности… …   Википедия

  • Криптосистема с открытым ключом — Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр)  система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному …   Википедия

  • Криптографическая система с открытым ключом — (или Асимметричное шифрование, Асимметричный шифр)  система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для… …   Википедия

  • Открытый ключ — Криптографическая система с открытым ключом (или Асимметричное шифрование, Асимметричный шифр)  система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для… …   Википедия

  • Шифрование с открытым ключом — Криптографическая система с открытым ключом (или Асимметричное шифрование, Асимметричный шифр)  система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для… …   Википедия

  • Криптография — Немецкая криптомашина Lorenz использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от др. греч …   Википедия

  • Криптограф — Немецкая криптомашина Lorenz, использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от греч. κρυπτός  скрытый и γράφω  пишу)  наука о математических методах обеспечения конфиденциальности… …   Википедия

  • N-Hash — Криптографическая хеш функция Название N Hash Создан 1990 Опубликован 1990 Размер хеша 128 бит Число раундов 12 или 15 Тип хеш функция N Hash  криптографическая …   Википедия

  • PKCS12 — Правильный заголовок этой статьи  PKCS#12. Он показан некорректно из за технических ограничений. PKCS #12 Расширение .p12, .pfx Разработан RSA Security Опубликован 1996 (1996) …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»