МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Інститут комп”ютерних технологій, автоматики та метрології кафедра автоматики та телемеханіки ЗВІТ ПРО ВИКОНАННЯ ЛАБОРАТОРНОЇ РОБОТИ №3 з курсу: “ Методи та засоби криптографічних перетворень ” на тему: “ Дослідження асиметричної криптосистеми RSA ” Львів – 2006 Мета: Вивчити алгоритм RSA та навчитися зашифровувати та розшифровувати масиви даних з допомогою цього алгоритму. Завдання 1. 1.Вивчити теоретичні відомості стосовно криптосистеми RSA та загальні поняття з теорії великих чисел. 2. Скористайтесь демонстраційною програмою RSA (RSA.exe) для дослідження процесу зашифровування та розшифровування з допомогою криптосистеми RSA. 3.Зашифрувати інформацію подану у вигляді слова за алгоритмом RSA. Із таблиці 1 вибирають слово для шифрування, таблиці 3 – потрібні для реалізації цього алгоритму числа ( p q). Таблиця 2. Варіанти 1 2 3 4 5 6 7 8 9 10 11  Слово О М Д Т Ш Х Ф С Н Л Е   Д Е В Р У І О І И І Р   А Д А И М Д Н М З С А   Таблиця 3. Варіанти 1 2 3 4 5 6 7 8 9 10 11  p 3 5 7 3 5 7 3 5 7 11 11  q 17 13 11 13 11 13 11 17 17 17 13   Букви тексту замінити натуральними числами, що відповідають порядковому номеру букви в українському алфавіті, наприклад А=1, Б=2, В=3 і т.д. 4.Скласти звіт, додавши до нього результати виконання роботи по пунктах 1,2,3 та висновки по роботі. Завдання 2. 1. Написати програму, зручною для вас мовою програмування, для обчислення функції fi(xi)=xiemod p над блоками вхідної послідовності довжиною по 128 біт. У якості вхідної послідовності взяти довільний текстовий файл. При виникненні блоку з кількістю біт меншою за 128, доповнити його нулями. e – довільне велике число довжиною 128 біт; p - довільне велике просте число довжиною 128 біт. Процедуру піднесення до степеня необхідно виконати з використанням бінарного алгоритму. Операцію модульного множення чисел виконати з допомогою класичного алгоритму та алгоритму Монтгомері. Порівняти швидкодії обчислення лишків для цих двох алгоритмів. Оцінити загальну швидкодію обчислень. 2. Результати виконання програми записати у файл даних. 3.Скласти звіт, додавши до нього результати виконання роботи та висновки по роботі. Теоретичні відомості Генерування ключів. Вибирають два досить великі прості числа
. Для їх добутку
значення функції Ойлера дорівнює
. Далі випадковим чином вибирають елемент
, що не перевищує значення
і взаємно простий з ним. Іншими словами,
є випадковим елементом із множини
. Для
за алгоритмом Евкліда знаходять елемент
, обернений до
в
, тобто такий, що
і
. Як результат покладають: Відкритий ключ:
Таємний ключ:
. Шифрування відбувається блоками. Для цього повідомлення записують у цифровій формі і розбивають на блоки так, що кожен блок позначає число, яке не перевищує
. Якщо блок записаний у вигляді двійкового слова довжини
, то повинна виконуватись нерівність
. Блок
розглядається як елемент кільця
і як такий, може підноситись до степеня за модулем
. Алгоритм шифрування
у системі
полягає у піднесені
до степеня
. Записується це так:
Результат роботи тестової програми This program implements the simulation of R S A system ----------------------------- Input text = theformatofthesefilesissequenceofenriesEntriesarepredonantlylineorientedthosparenthesescanbeusedtocontinuealistofitemsthatacrosslineboundary Input text length = 140 random P = 151 random Q = 67 N = 10117 Phi(N)= 9900 generated E = 7 public key (E,N) = (7,10117) generated D = 4243 private(secret) key (D,N) = (4243,10117) E N C R Y P T I O N cipher text = (plain text)** E (mod N) plain cipher t 116 - 3054 h 104 - 8144 e 101 - 815 f 102 - 4560 o 111 - 2328 r 114 - 8602 m 109 - 2671 a 97 - 5926 t 116 - 3054 o 111 - 2328 f 102 - 4560 t 116 - 3054 h 104 - 8144 e 101 - 815 s 115 - 3602 e 101 - 815 f 102 - 4560 i 105 - 2048 l 108 - 10062 e 101 - 815 s 115 - 3602 i 105 - 2048 s 115 - 3602 s 115 - 3602 e 101 - 815 q 113 - 300 u 117 - 616 e 101 - 815 n 110 - 1784 c 99 - 1805 e 101 - 815 o 111 - 2328 f 102 - 4560 e 101 - 815 n 110 - 1784 r 114 - 8602 i 105 - 2048 e 101 - 815 s 115 - 3602 E 69 - 2607 n 110 - 1784 t 116 - 3054 r 114 - 8602 i 105 - 2048 e 101 - 815 s 115 - 3602 a 97 - 5926 r 114 - 8602 e 101 - 815 p 112 - 790 r 114 - 8602 e 101 - 815 d 100 - 927 o 111 - 2328 n 110 - 1784 a 97 - 5926 n 110 - 1784 t 116 - 3054 l 108 - 10062 y 121 - 6631 l 108 - 10062 i 105 - 2048 n 110 - 1784 e 101 - 815 o 111 - 2328 r 114 - 8602 i 105 - 2048 e 101 - 815 n 110 - 1784 t 116 - 3054 e 101 - 815 d 100 - 927 t 116 - 3054 h 104 - 8144 o 111 - 2328 s 115 - 3602 p 112 - 790 a 97 - 5926 r 114 - 8602 e 101 - 815 n 110 - 1784 t 116 - 3054 h 104 - 8144 e 101 - 815 s 115 - 3602 e 101 - 815 s 115 - 3602 c 99 - 1805 a 97 - 5926 n 110 - 1784 b 98 - 9146 e 101 - 815 u 117 - 616 s 115 - 3602 e 101 - 815 d 100 - 927 t 116 - 3054 o 111 - 2328 c 99 - 1805 o 111 - 2328 n 110 - 1784 t 116 - 3054 i 105 - 2048 n 110 - 1784 u 117 - 616 e 101 - 815 a 97 - 5926 l 108 - 10062 i 105 - 2048 s 115 - 3602 t 116 - 3054 o 111 - 2328 f 102 - 4560 i 105 - 2048 t 116 - 3054 e 101 - 815 m 109 - 2671 s 115 - 3602 t 116 - 3054 h 104 - 8144 a 97 - 5926 t 116 - 3054 a 97 - 5926 c 99 - 1805 r 114 - 8602 o 111 - 2328 s 115 - 3602 s 115 - 3602 l 108 - 10062 i 105 - 2048 n 110 - 1784 e 101 - 815 b 98 - 9146 o 111 - 2328 u 117 - 616 n 110 - 1784 d 100 - 927 a 97 - 5926 r 114 - 8602 y 121 - 6631 D E C R Y P T I O N plain text = (cipher text)** D (mod N) cipher plain symbol 3054 - 116 t 8144 - 104 h 815 - 101 e 4560 - 102 f 2328 - 111 o 8602 - 114 r 2671 - 109 m 5926 - 97 a 3054 - 116 t 2328 - 111 o 4560 - 102 f 3054 - 116 t 8144 - 104 h 815 - 101 e 3602 - 115 s 815 - 101 e 4560 - 102 f 2048 - 105 i 10062 - 108 l 815 - 101 e 3602 - 115 s 2048 - 105 i 3602 - 115 s 3602 - 115 s 815 - 101 e 300 - 113 q 616 - 117 u 815 - 101 e 1784 - 110 n 1805 - 99 c 815 - 101 e 2328 - 111 o 4560 - 102 f 815 - 101 e 1784 - 110 n 8602 - 114 r 2048 - 105 i 815 - 101 e 3602 - 115 s 2607 - 69 E 1784 - 110 n 3054 - 116 t 8602 - 114 r 2048 - 105 i 815 - 101 e 3602 - 115 s 5926 - 97 a 8602 - 114 r 815 - 101 e 790 - 112 p 8602 - 114 r 815 - 101 e 927 - 100 d 2328 - 111 o 1784 - 110 n 5926 - 97 a 1784 - 110 n 3054 - 116 t 10062 - 108 l 6631 - 121 y 10062 - 108 l 2048 - 105 i 1784 - 110 n 815 - 101 e 2328 - 111 o 8602 - 114 r 2048 - 105 i 815 - 101 e 1784 - 110 n 3054 - 116 t 815 - 101 e 927 - 100 d 3054 - 116 t 8144 - 104 h 2328 - 111 o 3602 - 115 s 790 - 112 p 5926 - 97 a 8602 - 114 r 815 - 101 e 1784 - 110 n 3054 - 116 t 8144 - 104 h 815 - 101 e 3602 - 115 s 815 - 101 e 3602 - 115 s 1805 - 99 c 5926 - 97 a 1784 - 110 n 9146 - 98 b 815 - 101 e 616 - 117 u 3602 - 115 s 815 - 101 e 927 - 100 d 3054 - 116 t 2328 - 111 o 1805 - 99 c 2328 - 111 o 1784 - 110 n 3054 - 116 t 2048 - 105 i 1784 - 110 n 616 - 117 u 815 - 101 e 5926 - 97 a 10062 - 108 l 2048 - 105 i 3602 - 115 s 3054 - 116 t 2328 - 111 o 4560 - 102 f 2048 - 105 i 3054 - 116 t 815 - 101 e 2671 - 109 m 3602 - 115 s 3054 - 116 t 8144 - 104 h 5926 - 97 a 3054 - 116 t 5926 - 97 a 1805 - 99 c 8602 - 114 r 2328 - 111 o 3602 - 115 s 3602 - 115 s 10062 - 108 l 2048 - 105 i 1784 - 110 n 815 - 101 e 9146 - 98 b 2328 - 111 o 616 - 117 u 1784 - 110 n 927 - 100 d 5926 - 97 a 8602 - 114 r 6631 - 121 y Кодування слова за допомогою алгоритму RSA н и З  17 10 9  



17 10 9  33 75 25   Текст програми /* Author: Pate Williams (c) 1997 Extended binary Euclid algorithm. See "Handbook of Applied Cryptography" by Alfred J. Menezes et al Section 14.4.3 pages 608 - 610. */ #include <stdio.h> #include "lip.h" #define DEBUG void zbinary_ext_gcd(verylong zx, verylong zy, verylong *za, verylong *zb, verylong *zv) /* returns a * x + b * y = v, v = gcd(x, y) */ { verylong zA = 0, zB = 0, zC = 0, zD = 0; verylong zX = 0, zY = 0, zc = 0, zg = 0; verylong zu = 0; zone(&zg); zcopy(zx, &zX); zcopy(zy, &zY); while (!zodd(zX) && !zodd(zY)) { zrshift(zX, 1l, &zc); zcopy(zc, &zX); zrshift(zY, 1l, &zc); zcopy(zc, &zY); zlshift(zg, 1l, &zc); zcopy(zc, &zg); } zcopy(zX, &zu); zcopy(zY, zv); zone(&zA); zzero(&zB); zzero(&zC); zone(&zD); do { while (!zodd(zu)) { zrshift(zu, 1l, &zc); zcopy(zc, &zu); if (!zodd(zA) && !zodd(zB)) { zrshift(zA, 1l, &zc); zcopy(zc, &zA); zrshift(zB, 1l, &zc); zcopy(zc, &zB); } else { zadd(zA, zY, &zc); zrshift(zc, 1l, &zA); zsub(zB, zX, &zc); zrshift(zc, 1l, &zB); } } while (!zodd(*zv)) { zrshift(*zv, 1l, &zc); zcopy(zc, zv); if (!zodd(zC) && !zodd(zD)) { zrshift(zC, 1l, &zc); zcopy(zc, &zC); zrshift(zD, 1l, &zc); zcopy(zc, &zD); } else { zadd(zC, zY, &zc); zrshift(zc, 1l, &zC); zsub(zD, zX, &zc); zrshift(zc, 1l, &zD); } } if (zcompare(zu, *zv) >= 0) { zsub(zu, *zv, &zc); zcopy(zc, &zu); zsub(zA, zC, &zc); zcopy(zc, &zA); zsub(zB, zD, &zc); zcopy(zc, &zB); } else { zsub(*zv, zu, &zc); zcopy(zc, zv); zsub(zC, zA, &zc); zcopy(zc, &zC); zsub(zD, zB, &zc); zcopy(zc, &zD); } #ifdef DEBUG zwrite(zu); printf(" "); zwrite(*zv); printf(" "); zwrite(zA); printf(" "); zwrite(zB); printf(" "); zwrite(zC); printf(" "); zwriteln(zD); #endif } while (zscompare(zu, 0l) != 0); zcopy(zC, za); zcopy(zD, zb); zmul(zg, *zv, &zc); zcopy(zc, zv); zfree(&zA); zfree(&zB); zfree(&zC); zfree(&zD); zfree(&zX); zfree(&zY); zfree(&zc); zfree(&zg); zfree(&zu); } int main(void) { verylong za = 0, zb = 0, zv = 0, zx = 0, zy = 0; zintoz(693l, &zx); zintoz(609l, &zy); zbinary_ext_gcd(zx, zy, &za, &zb, &zv); printf("a = "); zwriteln(za); printf("b = "); zwriteln(zb); printf("v = "); zwriteln(zv); zfree(&za); zfree(&zb); zfree(&zv); zfree(&zx); zfree(&zy); return 0; } Висновок: під час виконання даної лабораторної роботи ми ознайомились з методом шифрування інформації RSA. Переконались в тому, що алгоритм легкий для розуміння і реалізації і важкий для взлому.