Статья: Открытое шифрование Эль-Гамаля

Введение

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

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

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

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

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

Открытое шифрование Эль-Гамаля

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

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

1. Выбрать произвольное, но достаточно большое простое число р.
2. Для данного простого числа следует определить какой-либо образующий компонент, то есть, такое число «а», при неоднократном возведении которого в степень по модулю р (а^1 mod p, a^2 mod p, …), будет выполнен перебор (в произвольном порядке, но только однократно) всех чисел от единицы до (p-1) включительно.
3. Далее необходимо сгенерировать произвольное случайное число х $(0 \lt х \lt p)$, которое и будет закрытым ключом.
4. Затем следует вычислить значение b=a^x modp. Совокупность чисел (a, p, b) будет выступать в качестве открытого ключа получателя.

Этап шифрования состоит в осуществлении следующих действий:

1. Отправитель должен сгенерировать произвольное случайное число y $(0 \lt y \lt p)$.
2. Отправитель должен поместить в начале шифрограммы число (a^y modp).
3. Отправитель должен вычислить значение k = (b^y mod p) = ((a^x mod p)^y mod p).
4. Отправитель должен при помощи некоторой, предварительно оговоренной в данной реализации, части k в качестве симметричного ключа для любого блочного шифра, выполнить шифрование отправляемого сообщения.
5. Далее отправителю следует надежно стереть числа y и k из оперативной памяти компьютера и иных мест, куда они могли случайно попасть.

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

1. При получении шифрованного сообщения, получателю следует отделить от пакета значение (a^y mod p) и вычислить на его основе величину (a^y mod p)^x mod p). Можно математически доказать, что полученное значение будет равняться значению k, которое определил отправитель, поскольку в данном выражении операнды x и y можно менять местами.
2. Затем следует выделить из k такую же часть, что и отправитель, что позволит получателю выполнить дешифровку всего идущего далее пакета при помощи симметричного алгоритма.

Сложность дискретного логарифма заключается в том, что, имея основание степени и полученный после возведения итоговый результат по модулю простого числа, нельзя за разумный временной интервал вычислить, в какую конкретно степень было возведено основание. В схеме Эль-Гамаль потенциальные злоумышленники могут завладеть значениями a, p, (a^x mod p) и (a^y mod p). Тем не менее сложность определения чисел х и y «в чистом виде», по сути, блокирует возможность вычисления значения k = (a^xy mod p), которое необходимо знать, для того чтобы прочитать шифровку.

С точки зрения криптостойкости в схеме Эль-Гамаль 512-битное число p может быть приравнено к 56-битному симметричному ключу, размеры которого в настоящее время являются недостаточными, для того чтобы обеспечить надежное шифрование. По этой причине на практике используются р, длиной в 768, 1024 и 1536 бит.

Очевидно, что по подобной схеме могут передаваться сообщения от всех абонентов в сети. То есть, каждый абонент, которому известен открытый ключ принимающего абонента, может передавать ему сообщения, зашифрованные при помощи открытого ключа. Но только расшифровать эти сообщения сможет только тот абонент, которому известен также и секретный ключ.