1. Главная
  2. Технологии
  3. Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання

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 ключа розв’яжемо порівняння

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru ;

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.

Це означає, що Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru =6.

Тоді значення Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru можна знайти з виразу

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

Підрахуємо коефіцієнти, а0, а1, а2, а3, а4 та а5.

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

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

y = Dk = (-1)6*13 = 13;

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Задача 2.

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

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

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru ;

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

Таким чином

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru складає RSA ключову пару.

Перевірка:

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

Задача 10.

Нехай Р=11 і Q=7. Виберемо Ek=9 як випадковий ключ і побудуємо пару (Ek, Dk) для RSA ключів.

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

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

Ключ Dk знайдемо із порівняння

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru ,

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

Знайдемо розклад ланцюгового дробу:

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru ;

60/9=6+6/9; 9/6=1+3/6; 6/3=2+0.

Оскільки НСД Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru , то розв’язку для пари ключів (Ek, Dk) немає.

1.8.2 Задачі для самостійного розв’язку

Задача 1.Побудувати пару (Ek,Dk) для RSA криптоалгоритму, якщо Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru (значення Р і Q дивись у табл. 1.3).

Таблиця 1.3 – Значення Р і Q для задачі 1

n
Pп
Qп

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ruде Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru – номер за списком.

Якщо Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru , то Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru.

Задача 2.Розв’язати порівняння Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru , якщоN = Nп (значення Р і Q дивись у табл. 1.4).

Таблиця 1.4 – Значення Р і Q для задачі 2

n
Nп

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ruде Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru - номер за списком.

Якщо Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru , то Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

Задача 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 ключа розв’яжемо порівняння

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru ;

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.

Це означає, що Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru =6.

Тоді значення Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru можна знайти з виразу

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

Підрахуємо коефіцієнти, а0, а1, а2, а3, а4 та а5.

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

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

y = Dk = (-1)6*13 = 13;

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Задача 2.

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

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

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru ;

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

Таким чином

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru складає RSA ключову пару.

Перевірка:

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

Задача 10.

Нехай Р=11 і Q=7. Виберемо Ek=9 як випадковий ключ і побудуємо пару (Ek, Dk) для RSA ключів.

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

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

Ключ Dk знайдемо із порівняння

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru ,

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

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru

Знайдемо розклад ланцюгового дробу:

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru ;

60/9=6+6/9; 9/6=1+3/6; 6/3=2+0.

Оскільки НСД Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru , то розв’язку для пари ключів (Ek, Dk) немає.

1.8.2 Задачі для самостійного розв’язку

Задача 1.Побудувати пару (Ek,Dk) для RSA криптоалгоритму, якщо Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru (значення Р і Q дивись у табл. 1.3).

Таблиця 1.3 – Значення Р і Q для задачі 1

n
Pп
Qп

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ruде Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru – номер за списком.

Якщо Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru , то Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru.

Задача 2.Розв’язати порівняння Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru , якщоN = Nп (значення Р і Q дивись у табл. 1.4).

Таблиця 1.4 – Значення Р і Q для задачі 2

n
Nп

Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ruде Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru - номер за списком.

Якщо Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru , то Додаток А Асиметричні криптоалгоритми. Приклади розв’язку задач та задачі для самостійного розв’язання - student2.ru .

Наши рекомендации

Задачі для самостійного розв'язання

Задачі для самостійного розв'язання.

Приклади для самостійного розв’язання

Задачі для самостійного розв’язання

Задачі для самостійного розв’язку .

Задачі для самостійного розв’язку

Задачі для самостійного розв’язку

Задачі для самостійного розв’язання

Приклади розв’язання типових задач. Для розв’язання типових задач пропонується використовувати тарифну сітку, що містиь умовні цифри (таблиця 5.1)

Задачі для самостійного розв’язку