---

Саня Бабаев:
Решения задач по теме «Алгоритм RSA»

---

Задача 1 (Базовый уровень)

Дано: p = 5, q = 13, M = 17

1. Генерация ключей

Модуль n:

n = p \cdot q = 5 \cdot 13 = 65

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

\varphi(n) = (p-1)(q-1) = 4 \cdot 12 = 48

Выбор открытой экспоненты e:
Нужно e: 1 < e < 48, НОД(e, 48) = 1.
Проверим: e = 3 (НОД(3,48)=3 — не подходит), e = 5 (НОД(5,48)=1 — подходит).
Выбираем e = 5.

Открытый ключ: (e=5, n=65)

Вычисление секретной экспоненты d:
Нужно: (d · 5) mod 48 = 1.

Перебор:

· d=1: 5 mod 48 = 5
· d=2: 10
· d=3: 15
· d=4: 20
· d=5: 25
· d=6: 30
· d=7: 35
· d=8: 40
· d=9: 45
· d=10: 50 mod 48 = 2
· d=11: 55 mod 48 = 7
· d=12: 60 mod 48 = 12
· d=13: 65 mod 48 = 17
· d=14: 70 mod 48 = 22
· d=15: 75 mod 48 = 27
· d=16: 80 mod 48 = 32
· d=17: 85 mod 48 = 37
· d=18: 90 mod 48 = 42
· d=19: 95 mod 48 = 47
· d=20: 100 mod 48 = 4
· d=21: 105 mod 48 = 9
· d=22: 110 mod 48 = 14
· d=23: 115 mod 48 = 19
· d=24: 120 mod 48 = 24
· d=25: 125 mod 48 = 29
· d=26: 130 mod 48 = 34
· d=27: 135 mod 48 = 39
· d=28: 140 mod 48 = 44
· d=29: 145 mod 48 = 1 ✓

d = 29

Закрытый ключ: (d=29, n=65)

2. Шифрование M = 17

C = M^e \bmod n = 17^5 \bmod 65

Вычисляем:

· 17² = 289; 289 mod 65 = 289 − 4·65 = 289 − 260 = 29
· 17⁴ = 29² = 841; 841 mod 65 = 841 − 12·65 = 841 − 780 = 61
· 17⁵ = 17⁴ · 17 = 61 · 17 = 1037
· 1037 mod 65: 65 · 15 = 975; 1037 − 975 = 62

Шифротекст: C = 62

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

M = C^d \bmod n = 62^{29} \bmod 65

Разложим 29 = 16 + 8 + 4 + 1.

· 62² = 3844; 3844 mod 65: 65·59 = 3835; 3844 − 3835 = 9
· 62⁴ = 9² = 81; 81 mod 65 = 16
· 62⁸ = 16² = 256; 256 mod 65 = 256 − 3·65 = 256 − 195 = 61
· 62¹⁶ = 61² = 3721; 3721 mod 65: 65·57 = 3705; 3721 − 3705 = 16

Теперь: 62²⁹ = 62¹⁶ · 62⁸ · 62⁴ · 62¹ = 16 · 61 · 16 · 62

· 16 · 61 = 976; 976 mod 65: 65·15 = 975; 976 − 975 = 1
· 1 · 16 = 16
· 16 · 62 = 992; 992 mod 65: 65·15 = 975; 992 − 975 = 17

M = 17 ✓

Ответ: Открытый ключ (5, 65), закрытый (29, 65), C = 62, M = 17.

---

Задача 2 (Средний уровень)

Дано: e = 7, n = 33, c = 5

1. Подбор p и q

n = 33 = 3 · 11, значит p = 3, q = 11.

2. Нахождение d

φ(n) = (3−1)(11−1) = 2 · 10 = 20

Нужно: (d · 7) mod 20 = 1.

Перебор:

· d=1: 7
· d=2: 14
· d=3: 21 mod 20 = 1 ✓

d = 3

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

M = c^d \bmod n = 5^3 \bmod 33 = 125 \bmod 33

125 − 3·33 = 125 − 99 = 26

M = 26

Ответ: p=3, q=11, d=3, M=26.

---

Задача 3 (Уровень повышенной сложности)

Дано: e = 3, n = 55, c₁ = 4, c₂ = 39

1. Нахождение закрытого ключа

n = 55 = 5 · 11, значит p = 5, q = 11.

φ(n) = 4 · 10 = 40

Нужно: (d · 3) mod 40 = 1.

Перебор:

· d=1: 3
· d=2: 6
· d=3: 9
· d=4: 12
· d=5: 15
· d=6: 18
· d=7: 21
· d=8: 24
· d=9: 27
· d=10: 30
· d=11: 33
· d=12: 36
· d=13: 39
· d=14: 42 mod 40 = 2
· d=15: 45 mod 40 = 5
· d=16: 48 mod 40 = 8
· d=17: 51 mod 40 = 11
· d=18: 54 mod 40 = 14
· d=19: 57 mod 40 = 17
· d=20: 60 mod 40 = 20
· d=21: 63 mod 40 = 23
· d=22: 66 mod 40 = 26
· d=23: 69 mod 40 = 29
· d=24: 72 mod 40 = 32
· d=25: 75 mod 40 = 35
· d=26: 78 mod 40 = 38
· d=27: 81 mod 40 = 1 ✓

d = 27

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

Для c₁ = 4:

M_1 = 4^{27} \bmod 55

· 4² = 16
· 4⁴ = 16² = 256; 256 mod 55 = 256 − 4·55 = 256 − 220 = 36
· 4⁸ = 36² = 1296; 1296 mod 55: 55·23 = 1265; 1296 − 1265 = 31
· 4¹⁶ = 31² = 961; 961 mod 55: 55·17 = 935; 961 − 935 = 26

4²⁷ = 4¹⁶ · 4⁸ · 4² · 4¹ = 26 · 31 · 16 · 4

· 26 · 31 = 806; 806 mod 55: 55·14 = 770; 806 − 770 = 36
· 36 · 16 = 576; 576 mod 55: 55·10 = 550; 576 − 550 = 26
· 26 · 4 = 104; 104 mod 55 = 104 − 55 = 49

M₁ = 49

Для c₂ = 39:

M_2 = 39^{27} \bmod 55

· 39² = 1521; 1521 mod 55: 55·27 = 1485; 1521 − 1485 = 36
· 39⁴ = 36² = 1296; 1296 mod 55 = 31
· 39⁸ = 31² = 961; 961 mod 55 = 26
· 39¹⁶ = 26² = 676; 676 mod 55: 55·12 = 660; 676 − 660 = 16

39²⁷ = 39¹⁶ · 39⁸ · 39² · 39¹ = 16 · 26 · 36 · 39

· 16 · 26 = 416; 416 mod 55: 55·7 = 385; 416 − 385 = 31
· 31 · 36 = 1116; 1116 mod 55: 55·20 = 1100; 1116 − 1100 = 16
· 16 · 39 = 624; 624 mod 55: 55·11 = 605; 624 − 605 = 19

M₂ = 19

3. Бонусный вопрос

Ответ: При малой экспоненте e = 3 и коротком сообщении M, если M³ < n, то шифротекст C = M³ (без взятия остатка), и сообщение легко восстанавливается извлечением кубического корня.

---

Задача 4: Шифрование слова «KEY»

Дано: p = 3, q = 11, e = 7

1. Генерация закрытого ключа

n = 3 · 11 = 33
φ(n) = 2 · 10 = 20

Нужно: (d · 7) mod 20 = 1.

Перебор:

· d=1: 7
· d=2: 14
· d=3: 21 mod 20 = 1 ✓

d = 3

Закрытый ключ: (d=3, n=33)

2. Шифрование слова «KEY»

K = 11, E = 5, Y = 25

K = 11:
C₁ = 11⁷ mod 33

· 11² = 121; 121 mod 33 = 121 − 3·33 = 121 − 99 = 22
· 11⁴ = 22² = 484; 484 mod 33: 33·14 = 462; 484 − 462 = 22
· 11⁷ = 11⁴ · 11² · 11¹ = 22 · 22 · 11 = 484 · 11 = 5324
· 5324 mod 33: 33·161 = 5313; 5324 − 5313 = 11

C₁ = 11 (интересно, но верно: 11⁷ mod 33 = 11)

E = 5:
C₂ = 5⁷ mod 33

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

C₂ = 14

Y = 25:
C₃ = 25⁷ mod 33

· 25² = 625; 625 mod 33 = 31
· 25⁴ = 31² = 961; 961 mod 33: 33·29 = 957; 961 − 957 = 4
· 25⁷ = 25⁴ · 25² · 25¹ = 4 · 31 · 25
· 4 · 31 = 124; 124 mod 33 = 124 − 3·33 = 124 − 99 = 25
· 25 · 25 = 625; 625 mod 33 = 31

C₃ = 31

Шифротексты: C = (11, 14, 31)

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

C₁ = 11:
M₁ = 11³ mod 33 = 1331 mod 33
33·40 = 1320; 1331 − 1320 = 11 → M₁ = 11 = K ✓

C₂ = 14:
M₂ = 14³ mod 33 = 2744 mod 33
33·83 = 2739; 2744 − 2739 = 5 → M₂ = 5 = E ✓

C₃ = 31:
M₃ = 31³ mod 33 = 29791 mod 33
31 ≡ −2 (mod 33), поэтому 31³ ≡ (−2)³ = −8 ≡ 25 (mod 33)
→ M₃ = 25 = Y ✓

Ответ: Закрытый ключ (3, 33); шифротексты (11, 14, 31); расшифровка даёт «KEY».

---

Задача 5: Шифрование слова «CODE»

Дано: p = 7, q = 5, e = 5

1. Генерация закрытого ключа

n = 7 · 5 = 35
φ(n) = 6 · 4 = 24

Нужно: (d · 5) mod 24 = 1.

Перебор:

· d=1: 5
· d=2: 10
· d=3: 15
· d=4: 20
· d=5: 25 mod 24 = 1 ✓

d = 5

Закрытый ключ: (d=5, n=35)

2. Шифрование слова «CODE»

C = 3, O = 15, D = 4, E = 5

C = 3:
C₁ = 3⁵ mod 35 = 243 mod 35
35·6 = 210; 243 − 210 = 33
C₁ = 33

O = 15:
C₂ = 15⁵ mod 35

· 15² = 225; 225 mod 35 = 225 − 6·35 = 225 − 210 = 15
· 15⁴ = 15² = 225 mod 35 = 15
· 15⁵ = 15⁴ · 15 = 15 · 15 = 225 mod 35 = 15
  C₂ = 15

D = 4:
C₃ = 4⁵ mod 35 = 1024 mod 35
35·29 = 1015; 1024 − 1015 = 9
C₃ = 9

E = 5:
C₄ = 5⁵ mod 35 = 3125 mod 35
35·89 = 3115; 3125 − 3115 = 10
C₄ = 10

Шифротексты: C = (33, 15, 9, 10)

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

C₁ = 33:
M₁ = 33⁵ mod 35
33 ≡ −2 (mod 35), поэтому (−2)⁵ = −32 ≡ 3 (mod 35)
M₁ = 3 = C ✓

C₂ = 15:
M₂ = 15⁵ mod 35 = 15 (так как 15² ≡ 15 mod 35)
M₂ = 15 = O ✓

C₃ = 9:
M₃ = 9⁵ mod 35

· 9² = 81; 81 mod 35 = 11
· 9⁴ = 11² = 121; 121 mod 35 = 121 − 3·35 = 16
· 9⁵ = 16 · 9 = 144; 144 mod 35 = 144 − 4·35 = 4
  M₃ = 4 = D ✓

C₄ = 10:
M₄ = 10⁵ mod 35 = 100000 mod 35

· 10² = 100; 100 mod 35 = 30
· 10⁴ = 30² = 900; 900 mod 35: 35·25 = 875; 900 − 875 = 25
· 10⁵ = 25 · 10 = 250; 250 mod 35: 35·7 = 245; 250 − 245 = 5
  M₄ = 5 = E ✓

Ответ: Закрытый ключ (5, 35); шифротексты (33, 15, 9, 10); расшифровка даёт «CODE».

---

Задача 6: Шифрование слова «RSA»

Дано: e = 3, n = 55

1. Подбор закрытого ключа

n = 55 = 5 · 11, значит p = 5, q = 11.
φ(n) = 4 · 10 = 40

Нужно: (d · 3) mod 40 = 1.
d = 27 (из задачи 3).

Закрытый ключ: (d=27, n=55)

2. Шифрование слова «RSA»

R = 18, S = 19, A = 1

R = 18:
C₁ = 18³ mod 55 = 5832 mod 55
55·106 = 5830; 5832 − 5830 = 2
C₁ = 2

S = 19:
C₂ = 19³ mod 55 = 6859 mod 55
55·124 = 6820; 6859 − 6820 = 39
C₂ = 39

A = 1:
C₃ = 1³ mod 55 = 1
C₃ = 1

Шифротексты: C = (2, 39, 1)

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

C₁ = 2:
M₁ = 2²⁷ mod 55

· 2² = 4
· 2⁴ = 16
· 2⁸ = 16² = 256; 256 mod 55 = 36
· 2¹⁶ = 36² = 1296; 1296 mod 55 = 31
  2²⁷ = 2¹⁶ · 2⁸ · 2² · 2¹ = 31 · 36 · 4 · 2
· 31 · 36 = 1116; 1116 mod 55 = 16
· 16 · 4 = 64; 64 mod 55 = 9
· 9 · 2 = 18
  M₁ = 18 = R ✓

C₂ = 39:
M₂ = 39²⁷ mod 55 = 19 (из задачи 3)
M₂ = 19 = S ✓

C₃ = 1:
M₃ = 1²⁷ mod 55 = 1
M₃ = 1 = A ✓

Ответ: Закрытый ключ (27, 55); шифротексты (2, 39, 1); расшифровка даёт «RSA».

---

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

1.

Почему в алгоритме RSA для генерации ключей используются именно простые числа p и q, а не любые другие?

Потому что для простых p и q легко вычислить функцию Эйлера φ(n) = (p−1)(q−1). Если p и q составные, вычисление φ(n) требует знания их разложения на множители, что сложно. Кроме того, сложность факторизации произведения двух больших простых чисел обеспечивает криптостойкость RSA.

2. Что произойдёт, если для шифрования выбрать сообщение M, которое больше или равно модулю n?

Шифрование и расшифрование будут работать с M mod n, то есть исходное сообщение будет потеряно (восстановится только остаток по модулю n). Поэтому на практике сообщение разбивают на блоки, каждый из которых меньше n.

3. Объясните, почему открытая экспонента e должна быть взаимно простой со значением функции Эйлера φ(n).

Это необходимо для существования обратного элемента d по модулю φ(n), то есть чтобы уравнение (d · e) mod φ(n) = 1 имело решение. Если НОД(e, φ(n)) ≠ 1, такого d не существует, и расшифрование становится невозможным.

4. В чём состоит основная вычислительная сложность («сила») алгоритма RSA для криптоаналитика, который пытается его взломать?

Основная сложность — факторизация большого числа n на простые множители p и q. Зная p и q, можно легко вычислить φ(n) и найти d. Однако для достаточно больших n (2048 бит и более) задача факторизации практически неразрешима за разумное время современными средствами.

5. Какая главная практическая проблема мешает использованию RSA для непосредственного шифрования длинных сообщений, например, больших файлов?

RSA работает медленно и может шифровать только сообщения, длина которых меньше n (обычно 1024–4096 бит). Для шифрования больших объёмов данных RSA используют в гибридных схемах: RSA шифрует симметричный ключ, а сам файл шифруется быстрым симметричным алгоритмом (например, AES).