Задача 2. Нехай Р=11 і Q=7. Побудувати пару (Ek, Dk) для RSA-перетворення, обґрунтувавши та вибравши один із випадкових ключів

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

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

Знаходимо модуль перетворення та значення функції Ойлера j (N)

Порівняння виду

.

запишемо у вигляді Діафантового рівняння

.

Вибравши випадково E_k =17 ключ, взаємопростий з функцією Ойлера, тобто (E_k, j (N)) = 1, маємо

.

Тепер подамо a / b у вигляді ланцюгового дробу:

;

60/17=3+9/17; 17/9=1+8/9; 9/8=1+1/8; 8/1=8+0.

Таким чином

.

Розраховуємо значення y=D_k, використовуючи співвідношення (1.59)

.

Знаходимо рекурентно значення а₂:

Підставивши значення а ₂. в (1.3.12), маємо

.

Таким чином пара

складає RSA ключову пару.

Перевірка:

Підставивши значення ключів E_k =17та D_k = 53, маємо

.