Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання
1.8.1 Приклади розв’язку задач
Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання
1.8.1 Приклади розв’язку задач
Задача 1.
Нехай Р=11, Q=7, Еk=37. Побудуйте ключову пару (Ek, Dk) для RSA-перетворення.
Розв’язок задачі:
Модуль перетворення має значення
N = P*Q = 11*7 = 77.
Розраховуємо значення функцій Ойлера
j(N) = (P-1)(Q-1) = 10*6 =60 = 22 3 5.
Для знаходження Dk ключа розв’яжемо порівняння
.
Подамо це порівняння у вигляді (1.58)
.
Підставимо значення j (Nj) та Ek маємо
.
Подамо а/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.
Тоді значення 
можна знайти з виразу
.
Підрахуємо коефіцієнти, а0, а1, а2, а3, а4 та а5.
Визначимо ключ розшифрування
y = Dk = (-1)6*13 = 13;
.
Перевірку здійснюємо підстановкою значень Ek та Dk в основне порівняння
.
Таким чином (Ek =37 та Dk= 13) є ключовою парою RSA-перетворення.
Задача 2.
Нехай Р=11 і Q=7. Побудувати пару (Ek, Dk) для RSA-перетворення, обґрунтувавши та вибравши один із випадкових ключів.
Розв’язок задачі:
Знаходимо модуль перетворення та значення функції Ойлера j (N)
Порівняння виду
.
запишемо у вигляді Діафантового рівняння
.
Вибравши випадково Ek =17 ключ, взаємопростий з функцією Ойлера, тобто (Ek, 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=Dk, використовуючи співвідношення (1.59)
.
Знаходимо рекурентно значення а2:
Підставивши значення а2. в (1.10.12), маємо
.
Таким чином пара
складає RSA ключову пару.
Перевірка:
Підставивши значення ключів Ek =17та Dk = 53, маємо
.
Задача 10.
Нехай Р=11 і Q=7. Виберемо Ek=9 як випадковий ключ і побудуємо пару (Ek, Dk) для RSA ключів.
Розв’язок задачі:
Знаходимо модуль RSA перетворення та значення функції Ойлера:
Ключ Dk знайдемо із порівняння
,
далі зведемо вищенаведене порівняння до Діафантового рівняння
Знайдемо розклад ланцюгового дробу:
;
60/9=6+6/9; 9/6=1+3/6; 6/3=2+0.
Оскільки НСД 
, то розв’язку для пари ключів (Ek, Dk) немає.
1.8.2 Задачі для самостійного розв’язку
Задача 1.Побудувати пару (Ek,Dk) для RSA криптоалгоритму, якщо 
(значення Р і Q дивись у табл. 1.3).
Таблиця 1.3 – Значення Р і Q для задачі 1
| n | ||||||||||
| Pп | ||||||||||
| Qп |
де 
– номер за списком.
Якщо 
, то 
.
Задача 2.Розв’язати порівняння 
, якщоN = Nп (значення Р і Q дивись у табл. 1.4).
Таблиця 1.4 – Значення Р і Q для задачі 2
| n | ||||||||||
| Nп |
де - номер за списком.
Якщо 
, то 
.
Задача 1.
Нехай Р=11, Q=7, Еk=37. Побудуйте ключову пару (Ek, Dk) для RSA-перетворення.
Розв’язок задачі:
Модуль перетворення має значення
N = P*Q = 11*7 = 77.
Розраховуємо значення функцій Ойлера
j(N) = (P-1)(Q-1) = 10*6 =60 = 22 3 5.
Для знаходження Dk ключа розв’яжемо порівняння
.
Подамо це порівняння у вигляді (1.58)
.
Підставимо значення j (Nj) та Ek маємо
.
Подамо а/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.
Тоді значення можна знайти з виразу
.
Підрахуємо коефіцієнти, а0, а1, а2, а3, а4 та а5.
Визначимо ключ розшифрування
y = Dk = (-1)6*13 = 13;
.
Перевірку здійснюємо підстановкою значень Ek та Dk в основне порівняння
.
Таким чином (Ek =37 та Dk= 13) є ключовою парою RSA-перетворення.
Задача 2.
Нехай Р=11 і Q=7. Побудувати пару (Ek, Dk) для RSA-перетворення, обґрунтувавши та вибравши один із випадкових ключів.
Розв’язок задачі:
Знаходимо модуль перетворення та значення функції Ойлера j (N)
Порівняння виду
.
запишемо у вигляді Діафантового рівняння
.
Вибравши випадково Ek =17 ключ, взаємопростий з функцією Ойлера, тобто (Ek, 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=Dk, використовуючи співвідношення (1.59)
.
Знаходимо рекурентно значення а2:
Підставивши значення а2. в (1.10.12), маємо
.
Таким чином пара
складає RSA ключову пару.
Перевірка:
Підставивши значення ключів Ek =17та Dk = 53, маємо
.
Задача 10.
Нехай Р=11 і Q=7. Виберемо Ek=9 як випадковий ключ і побудуємо пару (Ek, Dk) для RSA ключів.
Розв’язок задачі:
Знаходимо модуль RSA перетворення та значення функції Ойлера:
Ключ Dk знайдемо із порівняння
,
далі зведемо вищенаведене порівняння до Діафантового рівняння
Знайдемо розклад ланцюгового дробу:
;
60/9=6+6/9; 9/6=1+3/6; 6/3=2+0.
Оскільки НСД , то розв’язку для пари ключів (Ek, Dk) немає.
1.8.2 Задачі для самостійного розв’язку
Задача 1.Побудувати пару (Ek,Dk) для RSA криптоалгоритму, якщо (значення Р і Q дивись у табл. 1.3).
Таблиця 1.3 – Значення Р і Q для задачі 1
| n | ||||||||||
| Pп | ||||||||||
| Qп |
де – номер за списком.
Якщо , то .
Задача 2.Розв’язати порівняння , якщоN = Nп (значення Р і Q дивись у табл. 1.4).
Таблиця 1.4 – Значення Р і Q для задачі 2
| n | ||||||||||
| Nп |
де - номер за списком.
Якщо , то .