Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження асиметричної криптосистеми RSA
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Кафедра автоматики та телемеханіки
Інформація про роботу
Рік:
2006
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Методи та засоби криптографічних перетворень
Група:
ІБ - 43
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Інститут комп”ютерних технологій, автоматики та метрології
кафедра автоматики та телемеханіки
ЗВІТ
ПРО ВИКОНАННЯ ЛАБОРАТОРНОЇ РОБОТИ №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. Переконались в тому, що алгоритм легкий для розуміння і реалізації і важкий для взлому.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора