Задача 1. Нехай Р=11, Q=7, Еk=37. Побудуйте ключову пару (Ek, Dk) для RSA-перетворення

Нехай Р =11, Q =7, Е_k =37. Побудуйте ключову пару (E_k, D_k) для RSA-перетворення.

Розв’язок задачі:

Модуль перетворення має значення

N = P*Q = 11*7 = 77.

Розраховуємо значення функцій Ойлера

j (N) = (P -1)(Q -1) = 10*6 =60 = 2² 3 5.

Для знаходження D_k ключа розв’яжемо порівняння

.

Подамо це порівняння у вигляді (1.58)

.

Підставимо значення j (N_j) та E_k маємо

.

Подамо а / b у вигляді ланцюгового дробу

;

60/37=1+23/37; 37/23=1+14/23; 23/14=1+9/14; 14/9=1+5/9; 9/5=1+4/5; 5/4=1+1/4; 4/1=4+0.

Це означає, що =6.

Тоді значення можна знайти з виразу

.

Підрахуємо коефіцієнти, а ₀, а ₁, а ₂, а ₃, а ₄ та а ₅.

Визначимо ключ розшифрування

y = D_k = (-1)⁶*13 = 13;

.

Перевірку здійснюємо підстановкою значень E_k та D_k в основне порівняння

.

Таким чином (E_k =37 та D_k = 13) є ключовою парою RSA-перетворення.