Page 17 - 4395

Обчислюємо: Φ(n) = (p - 1)(q - 1) = (7 - 1)(17 – 1) = 96.
Вибираємо е так, щоб е було взаємно простим с Φ(n) = 96 і менше,
ніж Φ(n): е = 5.
Визначаємо d так, щоб d·e = 1 mod 96 і d < 96: d = 77, оскільки

77·5 = 385 = 4·96 + 1.
У результаті, ключі: відкритий KU = {5, 119} и закритий
KR = {77, 119}.

Тепер, якщо потрібно, наприклад, зашифрувати
повідомлення М = 19, то знаходимо:
е
5
С = М (mod n) = 19 (mod 119) = 66.
77
Для дешифрування обчислюємо: 66 (mod 119) = 19.
Зрозуміло, ключі можна застосувати і в зворотній
послідовності: шифрувати за допомогою ключа d і дешифрувати
ключем e. Зокрема, само так і відбувається в алгоритмі

підтвердження цифрового підпису.

2.2.2 Обчислювальні аспекти

Розглянемо труднощі обчислень в алгоритмі RSA при створенні
ключів і при шифруванні/дешифруванні.
Як шифрування, так і дешифрування включають піднесення

цілого числа до цілого степеню за модулем n. При цьому проміжні
значення будуть величезними. Для того, щоб частково цього
уникнути, використовується наступна властивість модульної

арифметики:

[(a mod n) · (b mod n)] mod n = (a · b) mod n,

тобто модульну операцію застосовують тільки один раз у самому
кінці обчислення.
Інша оптимізація полягає в ефективному використанні

показника степеня, оскільки у разі RSA показники степеня дуже
16
великі. Припустимо, що необхідно обчислити х . Прямий підхід
вимагає 15 множень. Проте можна добитися того ж кінцевого

результату за допомогою тільки чотирьох множень, якщо
8
2
4
використовувати квадрат кожного проміжного результату: х , х , х ,
16
х .
У курсовій роботі для зменшення обчислювального
навантаження не застосовують великі прості числа р і q, які зазвичай
повинні мати розмір 100-200 десяткових знаків. Принципові

17