Задание 1. Математика (криптография): в криптосистеме RSA используются простые числа p = 17 и q = 19. 1) Вычислите модуль n = p × q и функцию Эйлера φ(n) = (p − 1)(q − 1). 2) Выберите открытую экспоненту e = 5. Убедитесь, что НОД(e, φ(n)) = 1. 3) Найдите секретную экспоненту d как обратное число к e по модулю φ(n), решив сравнение e × d ≡ 1 (mod φ(n)). 4) Зашифруйте сообщение m = 42: вычислите c = m^e mod n. 5) Расшифруйте полученный шифротекст: вычислите m' = c^d mod n. Проверьте, что m' = m.

1. Модуль и функция Эйлера: \[n=pq=17\cdot19=323,\qquad \varphi(n)=(17-1)(19-1)=16\cdot18=288.\]
2. Проверка взаимной простоты: \[\gcd(5,288)=1,\] поэтому экспонента \(e=5\) подходит.
3. Ищем \(d\): \[5d\equiv1\pmod{288}.\] Так как \(288=5\cdot57+3\), \(5=3+2\), \(3=2+1\), получаем \(1=3-2=3-(5-3)=2\cdot3-5=2(288-5\cdot57)-5=2\cdot288-115\cdot5.\] Следовательно, \(-115\cdot5\equiv1\pmod{288}\), поэтому \(d\equiv-115\equiv173\pmod{288}\). Берём \(d=173\).
4. Шифрование: \[c=42^5\bmod323.\] \(42^2=1764\equiv148\pmod{323}\), \(42^4\equiv148^2=21904\equiv283\pmod{323}\), поэтому \(42^5\equiv283\cdot42=11886\equiv42\pmod{323}\). Значит, \(c=42\).
5. Расшифрование: \[m'=42^{173}\bmod323=42.\] Полученное сообщение совпадает с исходным.

Ответ: n = 323; φ(n) = 288; d = 173; c = 42; m' = 42 = m.