Алгоритм RSA. Звіт до лабораторної роботи з Інші. Робота № 516467

Алгоритм RSA

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2010

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Інші

Група:

ІБ – 44

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет Львівська політехніка Звіт до лабораторної роботи № 4 на тему: “ Алгоритм RSA ” Мета роботи: ознайомитись з алгоритмом RSA. Написати програми для закодування та розкодування слова з 3-х букв алгоритмом RSA. Завдання Зашифрувати слово ШУМ відкритого тексту за алгоритмом RSA. Дані параметри згідно з варіантом: p = 5, q = 17; n = p * q = 85; phi(n) = (p - 1) * (q - 1) = 64; е = 27, було обране навмання з діапазону 1 < e < phi(n), таке що НСД(е, phi(n)) = 1. Представлення слова ШУМ у цифровій формі Ш=28 У=24 М=17, тобто {28,24,17}. Алгоритм RSA Безпека алгоритму RSA побудована на принципі складності факторизації. Алгоритм використовує два ключі — відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пари ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключем, то розшифрувати його можна тільки відповідним секретним ключем. Генерація ключів Для того, щоб згенерувати пари ключів виконуються наступні дії: вибираються два великих простих числа и обчислюється їх добуток обчислюється Функція Ейлера вибирається ціле таке, що та взаємно просте з за допомогою розширеного алгоритма Евкліда знаходиться число таке, що Число називається модулем, а числа і — відкритою й секретною експонентами, відповідно. Пари чисел є відкритою частиною ключа, а — секретною. Числа і після генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті. Шифрування й розшифрування Для того, щоб зашифрувати повідомлення обчислюється . Число використовується в якості шифртексту. Для розшифрування потрібно обчислити . Неважко переконатися, що при розшифруванні ми відновимо вихідне повідомлення: З умови виходить, що для деякого цілого , отже Згідно теореми Ейлера: , тому Цифровий підпис RSA може використовуватися не тільки для шифрування, але й для цифрового підпису. Підпис повідомлення обчислюється з використанням секретного ключа за формулою: Для перевірки правильності підпису потрібно переконатися, що виконується рівність Генерація простих чисел Для знаходження двох великих простих чисел і , при генерації ключа, звичайно використовуються ймовірносні тести чисел на простоту, які дозволяють швидко виявити й відкинути складні числа. Для генерації і необхідно використовувати криптографічно надійний генератор випадкових чисел. У порушника не має бути можливості одержати будь-яку інформацію про значення цих чисел. і не повинні бути занадто близькими одне до одного, інакше можна буде знайти їх використовуючи метод факторизації Ферма. Крім того, необхідно вибирати «сильні» прості числа, щоб не можна було скористатися алгоритмом Поларда. Доповнення повідомлень При практичному використанні необхідно деяким чином доповнювати повідомлення. Відсутність доповнень може призвести до деяких проблем: значення і дадуть при зашифруванні шифртексти 0 і 1 при будь-яких значеннях і . при малому значенні відкритого показника (, наприклад) можлива ситуація, коли виявиться, що . Тоді , і зловмисник легко зможе відновити вихідне повідомлення обчисливши корінь ступеня з . оскільки RSA є детермінованим алгоритмом, тобто не використовує випадкових значень у процесі роботи, то зловмисник може використати атаку з обраним відкритим текстом. Для розв'язання цих проблем повідомлення доповнюються перед кожним зашифруванням деяким випадковим значенням. Доповнення виконується таким чином, щоб гарантувати, що , і . Крім того, оскільки повідомлення доповнюється випадковими даними, то зашифровуючи той самий відкритий текст ми щораз будемо одержувати інше значення шифртексту, що робить атаку з обраним відкритим текстом неможливою. Вибір значення відкритого показника RSA працює значно повільніше симетричних алгоритмів. Для підвищення швидкості шифрування відкритий показник вибирається невеликим, звичайно 3, 17 або 65537. Ці числа у двійковому вигляді містять тільки по двох одиниці, що зменшує число необхідних операцій множення при піднесенні до степеня. Наприклад, для піднесення числа до степеня 17 потрібно виконати тільки 5 операцій множення: Вибір малого значення відкритого показника може призвести до розкриття повідомлення, якщо воно відправляється відразу декільком одержувачам, але ця проблема вирішується за рахунок доповнення повідомлень. Вибір значення секретного показника Значення секретного показника повинне бути досить великим. У 1990 році Міхаель Вінер (Michael J. Wiener) показав, що якщо і , то є ефективний спосіб обчислити по і . Однак, якщо значення вибирається невеликим, те виявляється досить великим і проблеми не виникає. Довжина ключа Число n повинне мати розмір не менше 512 біт. У даний момент (2007 рік) система шифрування на основі RSA вважається надійною, починаючи з величини N в 1024 біта. Список функцій, змінних та констант використаних в програмі X – константа, що визначає довжину слова яке може бути опрацьоване програмою; phi – змінна, яка відповідає змінній Phi(n) у алгоритмі RSA; M[] – масив в який заносеться повідомлення; n – змінна, яка відповідає змінній n в алгоритмі RSA; e – змінна, яка відповідає змінній e в алгоритмі RSA; d – змінна, яка відповідає змінній d в алгоритмі RSA; C[] – масив, в якому зберігається зашифрований текст; FLAG – змінна, що використовується в обрахунках; i, j – змінні, що використовуються в лічильниках циклів; q – змінна, яка відповідає змінній q в алгоритмі RSA; p – змінна, яка відповідає змінній p в алгоритмі RSA; s – змінна, що використовується в обрахунках; crypt – функція зашифрування алгоритмом RSA; decrypt – функція розшифрування алгоритмом RSA; check – функція для перевірки НСД(e, phi)=1. Блок-схема програми зашифрування/розшифрування алгоритмом RSA Текст програми #include<stdio.h> #define X 3 /* Вказуємо довжину слова */ int phi, M[X], n, e, d, C[X], FLAG; int check() /* Функція що перевіряє */ /* чи НСД(е,phi(n))=1 */ { int i; for(i=3; e%i==0 && phi%i==0; i+2) { FLAG = 1; return; } FLAG = 0; } void encrypt() /* Функція, що проводить зашифування */ /* слова побуквенно, після чого */ /* виводить результат */ { int i, j; for(j=0; j<X; j++) C[j] = 1; for(j=0; j<X; j++) { for(i=0; i<e; i++) C[j] = (C[j] * M[j]) % n; } printf("\n\tEncrypted keyword:\t"); for(j=0; j<X; j++) { C[j] = C[j] % n; printf(" %d", C[j]); } } void decrypt() /* Функція, що проводить розшифрування */ /* слова побуквенно, після чого */ /* виводить результат */ { int i, j; for(j=0; j<X; j++) M[j] = 1; for(j=0; j<X; j++) { for(i=0; i<d; i++) M[j] = (M[j] * C[j]) % n; } printf("\n\tDecrypted keyword:\t"); for(j=0; j<X; j++) { M[j] = M[j] % n; printf(" %d", M[j]); } } Продовження стр. 1Продовження стр. 1 void main(void) { int p, q, s; printf("\n\tEnter Two Relatively Prime Numbers:\t"); scanf("%d %d", &p, &q); n = p * q; phi = (p - 1) * (q - 1); printf("\n\t phi(n):\t%d", phi); do { printf("\n\n\tEnter E:\t"); scanf("%d", &e); check(); } while(FLAG == 1); d = 1; do /* Знаходження оберненого */ /* елементу d до е */ { s = (d * e) % phi; d++; } while(s!=1); d--; printf("\n\tPublic Key:\t{%d,%d}", e, n); printf("\n\tPrivate Key:\t{%d,%d}", d, n); printf("\n\n\n\tEnter plain text:\t "); scanf("%d %d %d", &M[0], &M[1], &M[2]); encrypt(); printf("\n\n\n\tEnter encrypted text:\t "); scanf("%d %d %d", &C[0], &C[1], &C[2]); decrypt(); printf("\n\n\tPress any key to continue..."); getch(); } Результат виконання програми Висновок: в даній лабораторній роботі я ознайомився з принципами роботи алгоритму RSA. Реалізував програми для зашифрування та розшифрування слів даним методом. RSA є надзвичайно популярним через його простоту в реалізації, та високу стійкість. Стійкість RSA залежить від використання великих степенів, що спричиняє надзвичайно велику кількість обчислень для розшифрування повідомлення порушником. Довжина ключів RSA росте паралельно із зростанням обчислювальних потужностей обчислювальної техніки, що роботь не практичним процес зламу даного шифру.

Звіт до лабораторної роботи Інші

18.02.2012 11:02-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись