---

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

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

1. Модуль n = p * q = 3 * 11 = 33.
2. Функция Эйлера φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20.
3. Проверка взаимной простоты e и φ(n): НОД(7, 20) = 1, значит e подходит.
4. Секретная экспонента d находится из условия d * 7 ≡ 1 mod 20. Подбором: 71=7, 72=14, 7*3=21 ≡ 1 mod 20. Значит d = 3.
5. Шифрование: C = M^e mod n = 5^7 mod 33.
   5^2 = 25
   5^4 = 25^2 = 625 mod 33. 3318 = 594, остаток 625 - 594 = 31.
5^7 = 5^4 * 5^2 * 5^1 = 31 * 25 * 5.
31 * 25 = 775. 775 mod 33: 3323 = 759, остаток 16.
   16 * 5 = 80. 80 mod 33: 33*2 = 66, остаток 14.
   C = 14.
6. Расшифрование: M = C^d mod n = 14^3 mod 33.
   14^2 = 196. 196 mod 33: 335 = 165, остаток 31.
14^3 = 31 * 14 = 434. 434 mod 33: 3313 = 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 = 13 * 7 = 91.
2. Функция Эйлера φ(n) = (13 - 1) * (7 - 1) = 12 * 6 = 72.
3. Проверка: НОД(5, 72) = 1, значит e подходит.
4. Нахождение d из условия d * 5 ≡ 1 mod 72.
   Алгоритм Евклида:
   72 = 5 * 14 + 2
   5 = 2 * 2 + 1
   2 = 1 * 2 + 0
   НОД(72, 5) = 1.
   Разматываем:
   1 = 5 - 2 * 2
   2 = 72 - 5 * 14
   1 = 5 - (72 - 5 * 14) * 2 = 5 - 72 * 2 + 5 * 28 = 5 * 29 - 72 * 2
   Значит 5 * 29 ≡ 1 mod 72, d = 29.
5. Создание подписи: S = M^d mod n = 15^29 mod 91.
   15^2 = 225. 225 mod 91: 912 = 182, остаток 43.
15^4 = 43^2 = 1849. 1849 mod 91: 9120 = 1820, остаток 29.
   15^8 = 29^2 = 841. 841 mod 91: 919 = 819, остаток 22.
15^16 = 22^2 = 484. 484 mod 91: 915 = 455, остаток 29.
   29 = 16 + 8 + 4 + 1.
   15^29 = 15^16 * 15^8 * 15^4 * 15^1 = 29 * 22 * 29 * 15.
   29 * 22 = 638. 638 mod 91: 917 = 637, остаток 1.
1 * 29 = 29.
29 * 15 = 435. 435 mod 91: 914 = 364, остаток 71.
   S = 71.
6. Проверка подписи: M' = S^e mod n = 71^5 mod 91.
   71 ≡ -20 mod 91.
   (-20)^2 = 400. 400 mod 91: 914 = 364, остаток 36.
(-20)^4 = 36^2 = 1296. 1296 mod 91: 9114 = 1274, остаток 22.
   (-20)^5 = 22 * (-20) = -440. -440 mod 91: 91*5 = 455, -440 + 455 = 15.
   M' = 15. Совпадает с исходным M = 15.

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

Ответ: n = 91, φ(n) = 72, d = 29, S = 71, M' = 15, подпись верна.

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

Дано: p = 11, g = 2, x = 8, k = 9, M = 5.

1. Открытый ключ y = g^x mod p = 2^8 mod 11.
   2^4 = 16 mod 11 = 5.
   2^8 = 5^2 = 25 mod 11 = 3.
   y = 3.
2. Обратный элемент k^(-1) по модулю (p - 1) = 10.
   НОД(9, 10) = 1.
   9 * 9 = 81 ≡ 1 mod 10, значит k^(-1) = 9.
3. Компоненты подписи.
   a = g^k mod p = 2^9 mod 11.
   2^9 = 2^8 * 2 = 3 * 2 = 6.
   a = 6.
   b = k^(-1) * (M - x * a) mod (p - 1) = 9 * (5 - 8 * 6) mod 10.
   8 * 6 = 48 mod 10 = 8.
   5 - 8 = -3 ≡ 7 mod 10.
   b = 9 * 7 = 63 mod 10 = 3.
   b = 3.
   Подпись: (a, b) = (6, 3).
4. Проверка подписи.
   Левая часть: (y^a * a^b) mod p = (3^6 * 6^3) mod 11.
   3^2 = 9, 3^4 = 81 mod 11 = 4, 3^6 = 4 * 9 = 36 mod 11 = 3.
   6^2 = 36 mod 11 = 3, 6^3 = 3 * 6 = 18 mod 11 = 7.
   3 * 7 = 21 mod 11 = 10.
   Правая часть: g^M mod p = 2^5 mod 11 = 32 mod 11 = 10.
   10 = 10, подпись верна.

Ответ: y = 3, k^(-1) = 9, a = 6, b = 3, проверка даёт 10 = 10, подпись корректна.

Мини-тест

1. б) (e, n)
2. в) Взаимно простым с р-1
3. б) Закрытого ключа отправителя
4. в) Разложения большого числа на простые множители
5. в) g^M mod p

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

1. Основная идея асимметричного шифрования в том, что для шифрования и расшифрования используются разные ключи: открытый ключ известен всем и служит для зашифрования, а закрытый ключ хранится в секрете у владельца и служит для расшифрования. Это снимает проблему передачи секретного ключа по незащищённому каналу.
2. В RSA это возможно потому, что пара чисел e и d подбирается так, что они являются взаимно обратными по модулю φ(n). Тогда для любого M, взаимно простого с n, выполняется (M^e)^d = M^(e*d) ≡ M mod n. Поэтому зашифрованное открытым ключом сообщение можно восстановить только с помощью парного закрытого ключа.
3. Хеш-образ сообщения это результат применения однонаправленной хеш-функции к сообщению, то есть число фиксированной длины. В цифровой подписи он используется потому, что подписывать само длинное сообщение медленно и неудобно, а хеш-образ короткий. Кроме того, хеш-функция обеспечивает целостность: любое изменение сообщения меняет хеш-образ, и подпись перестаёт быть верной.
4. Основные этапы генерации подписи по Эль-Гамалю:
   Выбираются большое простое p и генератор g.
   Выбирается закрытый ключ x и вычисляется открытый ключ y = g^x mod p.
   Для подписи сообщения M выбирается случайное k, взаимно простое с p-1.
   Вычисляется a = g^k mod p.
   Вычисляется b = k^(-1) * (M - x*a) mod (p-1).
   Подпись это пара (a, b).
5. Преимущества асимметричных криптосистем: не нужно передавать секретный ключ по защищённому каналу, можно обеспечить цифровую подпись и аутентификацию, число ключей растёт линейно с числом участников. Недостатки: значительно ниже скорость шифрования и расшифрования, большая длина ключей, более высокая вычислительная сложность по сравнению с симметричными алгоритмами.
6. Числа p и q должны быть большими, чтобы модуль n был достаточно велик и его нельзя было разложить на множители за разумное время. Они должны быть различными, потому что если p = q, то n = p^2 и факторизация сводится к извлечению квадратного корня, что резко снижает стойкость. Кроме того, при p = q функция Эйлера считается иначе.
7. Если в алгоритме Эль-Гамаля использовать одно и то же k для подписи двух разных сообщений, то у обеих подписей совпадёт компонента a. Из двух уравнений для b можно исключить x и найти k, а затем вычислить закрытый ключ x. Это полностью компрометирует систему.
8. Однонаправленная хеш-функция перед подписыванием используется для сжатия сообщения до фиксированной длины и для обеспечения целостности. Подписывается не само сообщение, а его хеш-образ, что ускоряет работу и делает невозможным подбор другого сообщения с тем же хеш-образом.