Elgamal

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

Содержание

Принцип работы шифросистемы

В дальнейшем будем понимать под М — исходное сообщение.

Шифрование

1. Выбирается большое простое число р, р<M. Для проверки р на простоту чаще всего используется алгоритм Rabin-Miller.
Перед проверкой числа алгоритмом Rabin-Miller рекомендуется выполнить следующие действия:
1.1 В сгенерированном числе установить младший бит равным 1, это обеспечит нечетность числа.
1.2 Убедиться, что р не делится на небольшие простые числа 3, 5, 7, 11, и т. д. В некоторых реализациях проверяется делимость р на все простые числа, меньше 256. Проверка делимости р на простые числа 3, 5 и 7 отсекает 54 % нечетных чисел, проверка делимости р на простые числа, меньше 100, убирает 76 % нечетных чисел, а проверка делимости р на простые числа, меньше 256, убирает 80 % нечетных чисел.
1.3 Выполнить тест Rabin-Miller несколько раз. Если р не проходит хотя бы одной проверки — число не простое.
2. Выбираются числа x и g так, что 1<x<p, 1<g<p.
3. Вычисляется y =gx(mod p)
Таким образом, открытый ключ: p, g, y. Закрытый ключ: x.
4. Выбирается случайное секретное число k, взаимнопростое с (p — 1), то есть НОД (k, (p-1))= 1.
5. Вычисляется a = gk (mod p) >b = yk M (mod p)
Пара чисел a и b является шифротекстом. Причем, длина шифротекста длинней открытого текста вдвое.

Дешифрование

Для расшифрования a и b, вычисляем:
M = b/ax mod p

Доказательство

ax ≡ gkx (mod p) и b/ax ≡ ykM/ax ≡ gxkM/gxk ≡ M (mod p).
Стойкость данной схемы основана на сложности проблемы дискретного логарифмирования (по известным p, g и y приходится искать показатель степени х: y =gx(mod p))
Подписать документ m = 4 методом Эль-Гамаля, используя модуль р = 11, q = 2, и секретный ключ х =
Проверить достоверность цифровой подписи.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home