Инструменты пользователя

Инструменты сайта


examination:mszki:question27

Название ЕGSА происходит от слов Еl Gаmаl Signaturе Аlgorithm (алгоритм цифровой подписи Эль Гамаля). Идея ЕGSА основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа,- задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSА, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

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

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

Рассмотрим подробнее алгоритм цифровой подписи Эль Гамаля. Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G < Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10^308 или ~2^1024) и G (~10^154 или ~2^512), которые не являются секретными.

Отправитель выбирает случайное целое число X, 1 < Х £ (Р-1), и вычисляет Y =G^X mod Р.

Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов. Число Х является секретным ключом отправителя для подписывания документов и должно храниться в секрете. Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэш-функции h() в целое число m:

m = h(М), 1<m<(Р-1),

и генерирует случайное целое число К, 1 < К < (Р -1), такое, что К и (Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а:

а = G^K mod Р

и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения

m = Х * а + К * b (mod (Р-1)).

Пара чисел (а,b) образует цифровую подпись S:

S = (а, b),проставляемую под документом М.

Тройка чисел (М, а, b) передается получателю, в то время как пара чисел (Х, К).держится в секрете.

После приема подписанного сообщения (М, а, b) получатель должен проверить, соответствует ли подпись

S = (а, b)

сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число

m = h(М),т.е. хэширует принятое сообщение М.

Затем получатель вычисляет значение А = (Y^a)*(a^b) (mod Р)

и признает сообщение М подлинным, если, и только если А = Gm (mod Р).

Иначе говоря, получатель проверяет справедливость соотношения

Ya ab (mod Р) = Gm (mod Р).

Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(а, b) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправителем сообщения М был обладатель именно данного секретного ключа X, не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ М.

Следует отметить, что выполнение каждой подписи по методу Эль Гамаля требует нового значения К, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К, повторно используемое отправителем, то он сможет раскрыть секретный ключ Х отправителя.

Пример.

Выберем: числа Р=11, G=2 и секретный ключ Х = 8. Вычисляем значение открытого ключа:

Y = G^X mod Р = Y = 2^8 mod 11=3.

Предположим, что исходное сообщение М характеризуется хэш-значением m = 5.

Дпя того чтобы вычислить цифровую подпись для сообщения М, имеющего хэш-значение m = 5, сначала выберем случайное целое число К = 9. Убедимся, что числа К и (Р -1) являются взаимно простыми. Действительно, НОД (9,10)=1. Далее вычисляем элементы а и b подписи:

а = G^K mod Р = 2^9 mod 11 = 6,

элемент b определяем, используя расширенный алгоритм Евклида:

m = Х * а + К * b (mod(Р-1)).

При m = 5, а = 6, Х = 8, К = 9, Р = 11 получаем

5 = (6* 8+9* b)(mod 10) или 9* b=-43(mod 10).

Решение: b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3. Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 3, получатель вычисляет хэш-значение для сообщения М :

m = 5,

а затем вычисляет два числа:

1) (Y^a)*(a^b) (mod Р) = 3^6 * 6^3 (mod 11) =10 (mod 11);

2) G^m (mod Р) = 2^5 (mod 11) =10 (mod 11).

Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.

examination/mszki/question27.txt · Последние изменения: 2014/01/15 12:20 (внешнее изменение)