Шифроваание Эль-Гамаль_ для ДО

1. Алгоритм Шифрования

Эль-Гамаля

2. Схема алгоритма Эль Гамаля

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

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

4. Суть задачи

Имеется уравнение
gx mod p = y.
Требуется по известным g, y и p найти
целое неотрицательное
число x (дискретный логарифм).

5. Процедура создания ключей

Первообразный корень по модулю p – наименьшее
положительное число g такое, что
gφ(p) mod p = 1 и gi mod p ≠ 1,
для 1 ≤ i < φ (p)
где φ (p) – функция Эйлера (т.к. р – простое число, то φ(p) =
p - 1).

6.

Выбираем сообщение, которое будем шифровать
Сообщение: Вторник
Данное сообщение переведем в числовые значения:
Полученное сообщение : 3|20|16|18|15|10|12

7.

Составляем ключи:
p = 43
Для нахождения g сделаем проверку по
системе:
g^φ(p) mod p = 1
G^i mod p ≠ 1
При 1 ⩽ i <φ(p), где φ(p) = p-1 = 42.

8.

Проверка. При g = 11 и p = 43, φ (43) = 43 – 1 = 42.
11^42 mod p = 1
11^2 mod p =35 (≠ 1)
11^3 mod p =43 (≠ 1)
11^4 mod p =21 (≠ 1)
11^5 mod p=16 (≠ 1)
11^6 mod p =4 (≠ 1)
11^7 mod p =1
Значит, g = 11 нам не подходит.

9.

Проверка. При g = 5 и p = 43, φ (43) = 43 – 1 = 42.
5^42 mod p = 1
5^2 mod p =25 (≠ 1)
5^3 mod p =39 (≠ 1)
5^4 mod p =23 (≠ 1)
5^5 mod p=29 (≠ 1)
5^6 mod p =16 (≠ 1)
5^7 mod p =37 (≠ 1)
5^8 mod p =13 (≠ 1)
....
5^40 mod p =31 (≠ 1)
5^41 mod p =26 (≠ 1
Значит, g = 5 нам подходит.

10. Шифрование

Для шифрования каждого отдельного блока
исходного сообщения должно выбираться
случайное число k (1 < k < p – 1).
Шифрограмма генерируется по следующим
формулам:
a = gk mod p,
b = (yk Т) mod p,
где Т – исходное сообщение;
(a, b) – зашифрованное сообщение.

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

T = (b (ax)-1) mod p
где (ax)-1 – обратное значение числа ax по
модулю p.
T = (b ap-1-x) mod p,

12.

Выбираем х из диапазона 1 < x < p-1.
x = 13
Находим y по формуле
y = g^x mod p = 5^13 mod 43 = 33.
Открытые ключи p, g, y; закрытый ключ
– x.

13. Приступаем к шифрованию

Определим k из диапазона 1 < k < p-1.
k = 17
Для расшифровки найдем a по формуле:
a = gk mod p = 5^17 mod 43 = 28.

14. Приступаем к шифрованию

Для зашифровки букв запишем формулу:
b = (y^k * T) mod p,
где Т – числовое значение шифрующей
буквы.

15. Приступаем к шифрованию

Сообщение: Вторник
Числовое значение
3|20|16|18|15|10|12 это наше
значение T

16. Приступаем к шифрованию

b = (y^k * T) mod p
b(В) = (33^17*3) mod 43 = 16
b(т) = (33^17*20) mod 43 = 35
b(o) = (33^17*16) mod 43 = 28
b(р) = (33^17*18) mod 43 = 10
b(н) = (33^17*15) mod 43 = 37
b(и) = (33^17*10) mod 43 = 39
b(к) = (33^17*12) mod 43 = 21
Передаем числа {16,35,28,10,37,39,21}

17. Приступаем к расшифровки

16,35,28,10,37,39,21
T = (b*a^p-1-x) mod p
p-1-x = 43-1-13 = 29
T(16)= (16*28^29) mod 43 = 3 (В)
T(35)= (35*28^29) mod 43 = 20 (т)
T(28)= (28*28^29) mod 43 = 16 (о)
T(10)= (10*28^29) mod 43 = 18 (р)
T(37)= (37*28^29) mod 43 = 15 (н)
T(39)= (39*28^29) mod 43 = 10 (и)
T(21)= (21*28^29) mod 43 = 12 (к)