---

Практическое занятие: Применение различных асимметричных алгоритмов

Ниже — полное решение всех заданий, мини-теста и ответы на контрольные вопросы.

---

Задание 1. Шифрование по алгоритму RSA (ручной расчет)

Дано:

· p = 3
· q = 11
· e = 7
· M = 5

1. Модуль n

n = p \cdot q = 3 \cdot 11 = 33

2. Функция Эйлера φ(n)

\varphi(n) = (p-1)(q-1) = 2 \cdot 10 = 20

3. Проверка взаимной простоты e и φ(n)

· e = 7, φ(n) = 20
· Делители 7: 1, 7
· Делители 20: 1, 2, 4, 5, 10, 20
· НОД(7, 20) = 1 → взаимно просты ✅

4. Секретная экспонента d (расширенный алгоритм Евклида)

Решаем: d · 7 ≡ 1 (mod 20)

Алгоритм Евклида:

· 20 = 7 · 2 + 6
· 7 = 6 · 1 + 1
· 6 = 1 · 6 + 0 → НОД = 1

Обратный ход:

· 1 = 7 − 6 · 1
· 6 = 20 − 7 · 2
· 1 = 7 − (20 − 7 · 2) = 7 · 3 − 20

По модулю 20: d = 3

Проверка: 3 · 7 = 21 ≡ 1 (mod 20) ✅

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

C = M^e \bmod n = 5^7 \bmod 33

Промежуточные шаги:

· 5² = 25
· 5⁴ = 25² = 625; 625 mod 33 = 625 − 18·33 = 625 − 594 = 31
· 5⁷ = 5⁴ · 5² · 5¹ = 31 · 25 · 5
  · 31 · 25 = 775; 775 mod 33 = 775 − 23·33 = 775 − 759 = 16
  · 16 · 5 = 80; 80 mod 33 = 80 − 2·33 = 14

C = 14

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

M = C^d \bmod n = 14^3 \bmod 33

· 14² = 196; 196 mod 33 = 196 − 5·33 = 196 − 165 = 31
· 14³ = 31 · 14 = 434; 434 mod 33 = 434 − 13·33 = 434 − 429 = 5

M = 5 ✅ Совпадает с исходным сообщением.

Ответ: n = 33, φ(n) = 20, d = 3, C = 14, расшифрование даёт M = 5.

---

Задание 2. Цифровая подпись по алгоритму RSA (ручной расчет)

Дано:

· p = 13
· q = 7
· e = 5
· M = 15

1. Модуль n

n = 13 \cdot 7 = 91

2. Функция Эйлера φ(n)

\varphi(n) = 12 \cdot 6 = 72

3. Проверка НОД(e, φ(n))

· e = 5, φ(n) = 72
· 72 mod 5 = 2; 5 mod 2 = 1 → НОД = 1 ✅

4. Секретная экспонента d (расширенный алгоритм Евклида)

Решаем: d · 5 ≡ 1 (mod 72)

Алгоритм Евклида:

· 72 = 5 · 14 + 2
· 5 = 2 · 2 + 1
· 2 = 1 · 2 + 0 → НОД = 1

Обратный ход:

· 1 = 5 − 2 · 2
· 2 = 72 − 5 · 14
· 1 = 5 − (72 − 5 · 14) · 2 = 5 − 72 · 2 + 5 · 28 = 5 · 29 − 72 · 2

По модулю 72: d = 29

Проверка: 29 · 5 = 145; 145 mod 72 = 145 − 2·72 = 1 ✅

5. Создание подписи

S = M^d \bmod n = 15^{29} \bmod 91

Используем последовательное возведение в степень:

Шаг Степень Вычисление Результат mod 91
1 15¹ 15 15
2 15² 15·15 = 225 225 − 2·91 = 43
3 15⁴ 43² = 1849 1849 − 20·91 = 1849 − 1820 = 29
4 15⁸ 29² = 841 841 − 9·91 = 841 − 819 = 22
5 15¹⁶ 22² = 484 484 − 5·91 = 484 − 455 = 29

29 = 16 + 8 + 4 + 1 = 11101₂

S = 15^{16} \cdot 15^8 \cdot 15^4 \cdot 15^1 \bmod 91

· 29 · 22 = 638; 638 − 7·91 = 638 − 637 = 1
· 1 · 29 = 29
· 29 · 15 = 435; 435 − 4·91 = 435 − 364 = 71

S = 71

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

M' = S^e \bmod n = 71^5 \bmod 91

· 71² = 5041; 5041 − 55·91 = 5041 − 5005 = 36
· 71⁴ = 36² = 1296; 1296 − 14·91 = 1296 − 1274 = 22
· 71⁵ = 71⁴ · 71¹ = 22 · 71 = 1562; 1562 − 17·91 = 1562 − 1547 = 15

M' = 15 ✅ Совпадает с исходным M = 15.

Вывод: подпись корректна.

---

Задание 3. Цифровая подпись по алгоритму Эль-Гамаля (ручной расчет)

Дано:

· p = 11
· g = 2
· x = 8 (закрытый ключ)
· k = 9
· M = 5

Проверка НОД(k, p−1)

· p − 1 = 10
· НОД(9, 10) = 1 ✅

1. Открытый ключ y

y = g^x \bmod p = 2^8 \bmod 11

· 2⁴ = 16 ≡ 5 (mod 11)
· 2⁸ = 5² = 25 ≡ 3 (mod 11)

y = 3

2. Обратный элемент k⁻¹ по модулю (p−1) = 10

Решаем: 9 · k⁻¹ ≡ 1 (mod 10)

Подбором: 9 · 9 = 81 ≡ 1 (mod 10)

k⁻¹ = 9

3. Компоненты подписи a и b

a = g^k mod p:
a = 2^9 \bmod 11

· 2⁸ = 256 ≡ 3 (mod 11)
· 2⁹ = 3 · 2 = 6

a = 6

b = k⁻¹ · (M − x·a) mod (p−1):

· M − x·a = 5 − 8·6 = 5 − 48 = −43
· −43 mod 10 = −43 + 5·10 = 7
· b = 9 · 7 = 63
· 63 mod 10 = 3

b = 3

Подпись: (a, b) = (6, 3)

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

Проверяем: (y^a · a^b) mod p == g^M mod p

Левая часть:

· y^a = 3⁶ mod 11
  · 3² = 9; 3³ = 27 ≡ 5; 3⁶ = 5² = 25 ≡ 3
· a^b = 6³ mod 11
  · 6² = 36 ≡ 3; 6³ = 3 · 6 = 18 ≡ 7
· Произведение: 3 · 7 = 21 ≡ 10 (mod 11)

Правая часть:

· g^M = 2⁵ mod 11 = 32 mod 11 = 10

10 = 10 ✅ Подпись верна.

---

Мини-тест (5 вопросов)

№ Вопрос Ответ
1 Открытый ключ в RSA состоит из: б) (e, n)
2 Число k в алгоритме Эль-Гамаля должно быть: в) Взаимно простым с р−1
3 Цифровая подпись в RSA создается с помощью: б) Закрытого ключа отправителя
4 Стойкость RSA основана на сложности: в) Разложения большого числа на простые множители
5 При проверке подписи Эль-Гамаля (y^a · a^b) mod p должно быть равно: в) g^M mod p

---

Контрольные вопросы

1. В чем состоит основная идея асимметричного шифрования?
Используются два разных ключа: открытый (публикуется) и закрытый (хранится в секрете). То, что зашифровано открытым ключом, может расшифровать только владелец закрытого ключа. Это решает проблему распространения ключей, присущую симметричным системам.

2. Почему в RSA можно использовать один ключ для шифрования, а другой — для расшифрования?
Потому что математически операции возведения в степень по модулю n с показателями e и d взаимно обратны: (M^e)^d ≡ M (mod n). Это следует из теоремы Эйлера, так как e·d ≡ 1 (mod φ(n)).

3. Что такое хеш-образ сообщения и зачем он используется в механизме цифровой подписи?
Хеш-образ — это результат применения однонаправленной хеш-функции к сообщению (значение фиксированной длины). Используется для сокращения объёма подписываемых данных и обеспечения целостности: подписывается не само сообщение, а его хеш.

4. Перечислите основные этапы генерации цифровой подписи по алгоритму Эль-Гамаля.

1. Выбрать случайное k (1 < k < p−1), взаимно простое с p−1.
2. Вычислить a = g^k mod p.
3. Вычислить b = k⁻¹ · (M − x·a) mod (p−1).
4. Подпись — пара (a, b).

5. Назовите преимущества и недостатки асимметричных криптосистем по сравнению с симметричными.

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

6. Почему в RSA числа p и q должны быть большими и различными?
Большие простые числа обеспечивают стойкость: сложность факторизации n растёт экспоненциально с размером чисел. Различные p и q нужны, чтобы φ(n) была корректной и n не был полным квадратом (иначе факторизация упрощается).

7. Что произойдет, если в алгоритме Эль-Гамаля использовать одно и то же число k для подписи двух разных сообщений?
Это критическая уязвимость: зная две подписи (a, b₁) и (a, b₂) с одинаковым k, можно вычислить k = (M₁ − M₂)/(b₁ − b₂) mod (p−1), а затем восстановить закрытый ключ x.

8. Для чего в схемах цифровой подписи используется однонаправленная хеш-функция перед самим подписыванием?
Для сжатия сообщения до фиксированного размера, обеспечения целостности и защиты от атак на основе мультипликативных свойств RSA (например, подпись произведения). Хеш делает подпись компактной и безопасной.