Для создания подписи RSA нам необходимо выполнить следующие шаги: 1. Вычислить значение функции Эйлера от произведения двух простых чисел p и q, равное (p-1)(q-1). В нашем случае p=5, q=11, значит, phi = (5-1)(11-1) = 40. 2. Найти число d, обратное к числу c по модулю phi. Находим d так, чтобы c*d = 1 (mod phi). Для этого можно воспользоваться расширенным алгоритмом Евклида. В нашем случае c=27, поэтому: 27 * x + 40 * y = 1 Решаем эту систему уравнений и находим x = 23, y = -16. Значит, d = 23 (mod 40). 3. Вычисляем значение подписи s по формуле s = m^d (mod n), где n = p*q. В нашем случае n = 5*11 = 55, поэтому: s = 7^23 (mod 55) Вычисляем это значение по алгоритму быстрого возведения в степень. Для этого представим показатель степени d в двоичной системе и вычислим последовательно квадраты числа 7 в соответствующих степенях двойки. Получаем: d = 23 = 16 + 4 + 2 + 1 = 2^4 + 2^2 + 2^1 + 2^0 7^2 = 49 (mod 55) 7^4 = (7^2)^2 = 49^2 = 10 (mod 55) 7^8 = (7^4)^2 = 10^2 = 35 (mod 55) 7^16 = (7^8)^2 = 35^2 = 5 (mod 55) 7^23 = 7^(16+4+2+1) = 7^16 * 7^4 * 7^2 * 7^1 = 5*10*49*7 = 154,350 (mod 55) = 45 Значит, подпись s равна 45. 4. Итак, мы получили подпись s = 45 для сообщения m = 7. Чтобы проверить подпись, необходимо выполнить обратную операцию и вычислить значение m' по формуле m' = s^c (mod n). В нашем случае n = 55, c = 27, s = 45, поэтому: m' = 45^27 (mod 55) Также как и в предыдущем пункте, вычисляем это значение по алгоритму быстрого возведения в степень: 27 = 16 + 8 + 2 + 1 = 2^4 + 2^3 + 2^1 + 2^0 45^2 = 2025 (mod 55) = 20 45^4 = (45^2)^2 = 20^2 = 21 (mod 55) 45^8 = (45^4)^2 = 21^2 = 46 (mod 55) 45^16 = (45^8)^2 = 46^2 = 21 (mod 55) 45^27 = 45^(16+8+2+1) = 45^16 * 45^8 * 45^2 * 45^1 = 21 * 46 * 20 * 45 = 58,860,000 (mod 55) = 7 Таким образом, мы получили значение m' = 7, которое совпадает с исходным сообщением. Значит, подпись верна и сообщение не было изменено.