Загрузка данных

Решение задач по теме «Алгоритм RSA»

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

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

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

· n = p·q = 5·13 = 65
· φ(n) = (p−1)(q−1) = 4·12 = 48
· Выбираем e взаимно простое с 48. Возьмём e = 5 (НОД(5,48)=1).
· Ищем d: (d·5) mod 48 = 1.
  Перебор: d=1→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=29→145 mod 48 = 145−144=1. d = 29.

Ответ: Открытый ключ (e=5, n=65), закрытый (d=29, n=65).

2. Шифрование M = 17
C = 17⁵ mod 65.

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

C = 62

3. Расшифрование C = 62
M = 62²⁹ mod 65. Считаем по шагам:

· 62² = 3844; 3844 mod 65: 65·59 = 3835; ост. 9
· 62⁴ = 9² = 81 mod 65 = 16
· 62⁸ = 16² = 256 mod 65 = 256−195 = 61
· 62¹⁶ = 61² = 3721; 3721 mod 65: 65·57 = 3705; ост. 16
· 29 = 16+8+4+1 → 62²⁹ = 16·61·16·62
  · 16·61 = 976 mod 65 = 976−975 = 1
  · 1·16 = 16
  · 16·62 = 992 mod 65: 65·15 = 975; ост. 17

M = 17 ✔

---

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

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

1. Подбор p и q: n = 33 = 3 · 11.

2. Закрытая экспонента d:

· φ(n) = (3−1)(11−1) = 2·10 = 20
· (d·7) mod 20 = 1. Перебор: d=3 → 21 mod 20 = 1. d = 3.

3. Расшифрование:
M = 5³ mod 33 = 125 mod 33 = 125 − 99 = 26

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

---

Задача 3 (повышенная сложность)

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

1. Закрытый ключ:

· n = 55 = 5 · 11
· φ(n) = 4·10 = 40
· (d·3) mod 40 = 1: d=27 → 81 mod 40 = 1. d = 27.

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

· M₁ = 4²⁷ mod 55. 4²=16; 4⁴=256 mod 55 = 256−220=36; 4⁸=36²=1296 mod 55: 55·23=1265, ост. 31; 4¹⁶=31²=961 mod 55: 55·17=935, ост. 26. 27=16+8+2+1 → 26·31·16·4.
  · 26·31 = 806 mod 55: 55·14=770, ост. 36
  · 36·16 = 576 mod 55: 55·10=550, ост. 26
  · 26·4 = 104 mod 55 = 49
· M₂ = 39²⁷ mod 55. 39²=1521 mod 55: 55·27=1485, ост. 36; 39⁴=36²=1296 mod 55=31; 39⁸=31²=961 mod 55=26; 39¹⁶=26²=676 mod 55: 55·12=660, ост. 16.
  · 16·26 = 416 mod 55: 55·7=385, ост. 31
  · 31·36 = 1116 mod 55: 55·20=1100, ост. 16
  · 16·39 = 624 mod 55: 55·11=605, ост. 19

Ответ: d = 27; M₁ = 49; M₂ = 19.

Бонус: При малой e и отсутствии паддинга одинаковые фрагменты сообщения дают одинаковые шифротексты, а при e=3 и небольших M шифротекст можно восстановить простым извлечением кубического корня (без знания ключа) — это «атака малой экспоненты».

---

Задача 4: слово «KEY»

Дано: p = 3, q = 11, e = 7. K=11, E=5, Y=25.

1. Ключи: n=33, φ=20, (d·7) mod 20 = 1 → d = 3 (7·3=21).

2. Шифрование:

· K (11): 11³ mod 33 = 1331 mod 33: 33·40 = 1320, ост. 11
· E (5): 5³ = 125 mod 33 = 26
· Y (25): 25³ = 15625 mod 33. 25²=625 mod 33 = 625−594=31; 31·25=775 mod 33: 33·23=759, ост. 16

3. Расшифрование (возводим в d=3):

· 11³ mod 33 = 11 = K
· 26³ mod 33: 26²=676 mod 33 = 676−660=16; 16·26=416 mod 33 = 416−396=20 ❌

Проверка: здесь d·e = 21, но φ=20, значит 21 ≡ 1 (mod 20) — верно. Пересчитаем 26³: 26² = 676; 676 mod 33 = 16; 16·26 = 416; 416 mod 33 = 416 − 396 = 20. Но исходное E=5. Ошибка в шифровании: 5³ = 125; 125 mod 33 = 125 − 99 = 26 — верно. Тогда 26³ mod 33 должно дать 5. Проверим: 26 ≡ −7 (mod 33). (−7)³ = −343. 343 mod 33 = 343−330 = 13, значит −343 ≡ −13 ≡ 20. Противоречие.

Причина: e=7 и φ=20 не взаимно просты? НОД(7,20)=1 — всё верно. Но d·e = 21 ≡ 1 (mod 20) — тоже верно. Однако RSA требует, чтобы M было взаимно простым с n. 5 и 33 взаимно просты. Проверим 5²¹ mod 33: 5²=25; 5⁴=25²=625 mod 33=31; 5⁸=31²=961 mod 33=4; 5¹⁶=4²=16; 21=16+4+1 → 16·31·5 = 16·155 = 2480; 2480 mod 33: 33·75=2475, ост. 5. ✔

Значит, ошибка в промежуточном вычислении 26³. Пересчитаем: 26³ = 26·26·26 = 17576. 17576 / 33 = 532,66…; 33·532 = 17556; 17576 − 17556 = 20. Всё равно 20, а не 5. Парадокс?

Разгадка: 26 ≡ −7, (−7)³ = −343, −343 + 363 = 20. Но 5³ = 125, 125 − 99 = 26. Тогда 26³ должно быть ≡ 5²¹? Нет: (5³)³ = 5⁹, а не 5²¹. Для расшифрования нужно возводить C в степень d=3: (5³)³ = 5⁹. 5⁹ mod 33: 5⁴=31, 5⁸=4, 5⁹=4·5=20. Действительно 20, а не 5!

Ошибка в d: нужно d·e ≡ 1 (mod φ), где φ=20. 7·3=21 ≡ 1 (mod 20) — верно. Но тогда C^d = M^(e·d) = M^(21) ≡ M (mod n) по теореме Эйлера, если M взаимно просто с n. 5²¹ mod 33 = 5 (мы проверили). А (5³)³ = 5⁹ ≠ 5²¹. Значит, d=3 не подходит?! Но 7·3=21 ≡ 1 (mod 20), и 21 = 1 + 20. По теореме Эйлера M²⁰ ≡ 1, значит M²¹ ≡ M. Всё сходится: (M^e)^d = M^(e·d) = M²¹ ≡ M. Но (5³)³ = 5⁹, а не 5²¹. Здесь ошибка: (M^e)^d = M^(e·d) — это верно только если возводить последовательно: сначала M^e, потом результат в степень d. (5³)³ = 5^(3·3) = 5⁹. Но e·d = 21, а не 9! Потому что e=7, d=3: e·d = 21. Значит, (M^e)^d = M^(7·3) = M²¹. Но мы возвели 5³=125→26, потом 26³. 26 = 5³, значит 26³ = (5³)³ = 5⁹. А должно быть 5²¹. Противоречие возникает потому, что 26 ≠ 5³ в смысле возведения в куб, а 26 ≡ 5³ (mod 33). Тогда 26³ ≡ (5³)³ = 5⁹ (mod 33). Но 5²¹ ≡ 5 (mod 33). Значит, 5⁹ ≡ 5²¹? Проверим: 5⁹=20, 5²¹=5. Не равны. Значит, теорема Эйлера даёт M²⁰ ≡ 1, поэтому M²¹ ≡ M. Но 5⁹ ≠ 5²¹. В чём дело? Потому что 5⁹ = 5^(21−12) = 5²¹ · 5^(−12). Нельзя просто так.

Ключевой момент: (M^e)^d = M^(e·d) — это тождество, но e·d = 21, а мы получили 5⁹. Потому что 26 ≡ 5³, и 26³ ≡ (5³)³ = 5⁹. Но 5⁹ ≠ 5²¹. Однако 5²¹ ≡ 5 (mod 33). Значит, 5⁹ должно быть ≡ 5, если бы d было правильным. Но 5⁹=20≠5. Вывод: d=3 не является правильным обратным к e=7 по модулю φ=20? 7·3=21 ≡ 1 (mod 20) — да, является. Тогда почему не работает?

Потому что φ(n) = 20, но порядок группы обратимых элементов по модулю 33 равен lcm(2,10)=10, а не 20. Функция Эйлера даёт 20, но фактический порядок может быть меньше. Для 5 порядок равен 10 (5¹⁰≡1). Тогда 5²¹ = 5^(20+1) ≡ 5¹ = 5. А 5⁹ ≠ 5. Но (5³)³ = 5⁹, и это не равно 5. Значит, возведение в куб не является обратным к возведению в 7-ю степень на этом элементе? Проверим: 5⁷ mod 33 = 5⁷ = 5⁴·5²·5 = 31·25·5 = 31·125 = 31·26 = 806 mod 33 = 806−792=14. Тогда (5⁷)³ = 14³ = 2744 mod 33: 33·83=2739, ост. 5. ✔ Работает! Значит, шифрование 5⁷=14, а не 26. Я ошибся: в задаче e=7, а я зашифровал как e=3 (5³=26). Правильно: C = M⁷ mod 33.

Пересчитаем:

· K (11): 11⁷ mod 33. 11²=121 mod 33=22; 11⁴=22²=484 mod 33=484−462=22; 11⁷=11⁴·11²·11=22·22·11=484·11=5324 mod 33: 33·161=5313, ост. 11. (11 взаимно просто с 33, порядок 2? 11²=121≡22, 11³=22·11=242≡11, да порядок 2.)
· E (5): 5⁷ mod 33 = 14 (см. выше).
· Y (25): 25⁷ mod 33. 25²=625 mod 33=31; 25⁴=31²=961 mod 33=4; 25⁷=25⁴·25²·25=4·31·25=4·775=3100 mod 33: 33·93=3069, ост. 31.

Шифротексты: K→11, E→14, Y→31.

Расшифрование (d=3):

· 11³ mod 33 = 11 ✔
· 14³ = 2744 mod 33 = 5 ✔
· 31³ = 29791 mod 33: 33·902=29766, ост. 25 ✔

Ответ: d=3; C(K)=11, C(E)=14, C(Y)=31; после расшифрования получаем 11, 5, 25 → «KEY».

---

Задача 5: слово «CODE»

Дано: p = 7, q = 5, e = 5. C=3, O=15, D=4, E=5.

1. Ключи:

· n = 35
· φ = 6·4 = 24
· (d·5) mod 24 = 1: d=5 → 25 mod 24 = 1. d = 5.

2. Шифрование (C = M⁵ mod 35):

· C (3): 3⁵ = 243; 243 mod 35 = 243−210 = 33
· O (15): 15²=225 mod 35=15; 15⁴=225 mod 35=15; 15⁵=15·15=225 mod 35=15
· D (4): 4²=16; 4⁴=256 mod 35=256−245=11; 4⁵=11·4=44 mod 35 = 9
· E (5): 5²=25; 5⁴=625 mod 35=625−595=30; 5⁵=30·5=150 mod 35=10

Шифротексты: 33, 15, 9, 10.

3. Расшифрование (M = C⁵ mod 35):

· 33⁵ mod 35: 33≡−2; (−2)⁵=−32≡3 ✔
· 15⁵ mod 35 = 15 ✔
· 9⁵ mod 35: 9²=81 mod 35=11; 9⁴=11²=121 mod 35=16; 9⁵=16·9=144 mod 35=4 ✔
· 10⁵ mod 35: 10²=100 mod 35=30; 10⁴=30²=900 mod 35=25; 10⁵=25·10=250 mod 35=5 ✔

Ответ: d=5; шифротекст «CODE» → 33, 15, 9, 10; расшифрование даёт 3, 15, 4, 5 → «CODE».

---

Задача 6: слово «RSA»

Дано: e = 3, n = 55. R=18, S=19, A=1.

n = 55 = 5·11, φ = 40. (d·3) mod 40 = 1 → d=27 (3·27=81≡1).

Шифрование (C = M³ mod 55):

· R (18): 18³ = 5832; 5832 mod 55: 55·106 = 5830, ост. 2
· S (19): 19³ = 6859; 55·124 = 6820, ост. 39
· A (1): 1³ = 1

Шифротексты: 2, 39, 1.

Расшифрование (M = C²⁷ mod 55):

· 2²⁷ mod 55: 2⁵=32; 2¹⁰=32²=1024 mod 55=34; 2²⁰=34²=1156 mod 55=1; 2²⁷=2²⁰·2⁷=1·128=128 mod 55=18 ✔
· 39²⁷ mod 55: 39²=1521 mod 55=36; 39⁴=36²=1296 mod 55=31; 39⁸=31²=961 mod 55=26; 39¹⁶=26²=676 mod 55=16; 27=16+8+2+1 → 16·26·36·39.
  · 16·26=416 mod 55=31
  · 31·36=1116 mod 55=16
  · 16·39=624 mod 55=19 ✔
· 1²⁷ = 1 ✔

Ответ: d=27; «RSA» → 2, 39, 1; расшифрование даёт 18, 19, 1 → «RSA».

---

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

1. Почему используются простые p и q? Потому что для простых чисел легко вычислить φ(n)=(p−1)(q−1), а факторизация произведения двух больших простых чисел — вычислительно сложная задача, что и обеспечивает стойкость RSA.
2. Что если M ≥ n? Тогда M mod n теряет однозначность: разные сообщения, сравнимые по модулю n, дадут одинаковый шифротекст, и расшифрование вернёт не исходное M, а M mod n. Поэтому сообщение разбивают на блоки меньше n.
3. Почему e взаимно просто с φ(n)? Чтобы существовало обратное число d по модулю φ(n) (решение сравнения e·d ≡ 1 mod φ(n)). Если НОД(e, φ) ≠ 1, обратного элемента не существует, и расшифрование невозможно.
4. В чём вычислительная сложность для криптоаналитика? Задача факторизации большого числа n на простые множители. При достаточной длине ключа (2048+ бит) она практически неразрешима за разумное время.
5. Главная практическая проблема RSA для длинных сообщений? Низкая скорость и ограничение на размер блока (M < n). Поэтому RSA обычно используют для шифрования ключей симметричных алгоритмов (гибридная схема), а не самих данных.