Міністерство освіти та науки України
Національний університет “Львівська політехніка”
кафедра
“Комп’ютеризовані
системи автоматики”
Звіт
до лабораторної роботи № 3
з дисципліни “Основи збору, передавання та обробки інформації”
на тему:
Алгоритм шифрування з відкритим ключем RSA
Варіант №12
Мета роботи: вивчити принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідити числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA.
1. Загальні відомості
2.2.1. Метод справа-наліво двійкового потенціювання.
Цей метод має декілька назв. Інколи його називають алгоритмом двійкових квадратів та добутків, оскільки він реалізується за допо могою цих операції, а інколи і алгоритмом індійського потенціювання. Має назву потенціювання справа-наліво, тому що він перебирає символи вказівника степеню, починаючи з молодшого розряду.
Нехай необхідно обчислити вираз (2.5) зі значенням
. (2.7)
Представимо число у вигляді суми степенів 2
(2.8)
Тепер розпишемо вираз (2.7) з врахуванням розкладу (2.8)
. (2.9)
Застосовуючи властивість (2.3), (2.6) до виразу (2.9), отримуємо
. (2.10)
Такий підхід і називається методом двійкових квадратів та добутків. Мовою С++ цей алгоритм виглядає так:
// обчислення
m = 1;
while (x)
{
if (x&1) m = (m*a) % n;
x = x >> 1;
a = (a*a) % n;
}
2.4.1. Алгоритм Евкліда.
В основі алгоритму лежить повторне ділення із залишком: обчислюємо залишок , потім і так далі, поки залишок на стане рівним нулю.
Загальний алгоритм Евкліда обчислення НСД (,) для
Мовою С++ цей алгоритм виглядає так:
// обчислення НСД (,)
while (a != 0)
{
temp = b %a;
b = a;
a = temp;
}
nsd = b;
Загальний розширений алгоритм Евкліда
обчислення оберненого значення
Мовою С++ цей алгоритм виглядає так:
// обчислення
// вхід: числа a та n, для яких треба знайти nsd= НСД (,)
long long n1, c, k, nsd, c1, c2, k1, k2, q, r;
n1 = n; //резервуємо значення n
c2 = 1; c1 = 0; k2 = 0; k1 = 1;
while(n != 0)
{
q = a/n; r = a - q*n; c = c2 - q*c1; k = k2 - q*k1;
a = n; n = r; c2 = c1; c1 = c; k2 = k1; k1 = k;
}
nsd = a; c = c2; k = k2;
// якщо аглоритм дав від’ємне значення с, тоді с = с (mod n)
if (c < 0) c += n1;
// вихід: числа nsd, c, k
// с – обернене значення за модулем n
Зауваження: у результаті роботи алгоритму можуть виникати від’ємні числа, і тому усі змінні мають бути знакового типу. Для беззнакових (unsigned) змінних алгоритм буде працювати некоректно! Якщо = НСД (,), то числа та не є взаємно простими.
Завдання
На основі інструментарію Visual C++ 2005 розробити Windows Forms програму CLR для реалізації вказаного проекту алгоритму криптографічної системи з відкритими ключами RSA.
Усі окремі алгоритми (наприклад, обчислення НСД бінарним алго ритмом Евкліда) реалізувати у вигляді підпрограм (функцій).
№ п/п
Проект програми
12
Підбір закритого ключа та злом системи RSA (рис. 5.1.б)
З метою компактності у завданні вказуються лише номери алгоритмів, на основі яких потрібно реалізувати загальний проект програ ми RSA. Розшифрування номерів подаються тут:
1. Алгоритм піднесення до степеню: 1.1. Метод справа-наліво двійкового потенціювання; 1.2. Метод зліва-направо двійкового потенціювання; 1.3. Рекурсивний метод двійкового потенцію вання; 1.4. Метод вікна; 1.5. Метод змінного вікна.
2. Обч. найбільшого спільного дільника: 2.1. Алгоритм Евклі да; 2.2. Бінарний алгоритм Евкліда.
3. Обч. оберненого значення за модулем: 3.1. Розширений ал горитм Евкліда; 3.2. Розширений бінарний алгоритм Евкліда.
4. Тести визначення простоти числа: 4.1....
