Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Афінний метод шифрування. Метод шифрування RSA.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Курсова робота
Предмет:
Методи та засоби криптологічних перетворень
Група:
ІБ-44
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет Львівська політехніка
Курсовий поект
з дисципліни: “Методи та засоби криптологічних перетворень”
Виконав студент групи ІБ — 44
Перевірив
Горпенюк А. Я.
Львів — 2010
Зміст
Завдання стр. 3
Опис Афінного методу шифрування стр. 3
Опис методу шифрування RSA стр. 5
Зашифрування Афінним шифром стр. 7
Зашифрування алгоритмом RSA стр. 10
Результати роботи програм зашифрування стр. 16
Висновки стр. 17
Список використаної літератури стр. 18
Номер залікової книжки: 0609015
Завдання №1 Симетричне шифрування
Вибрати ключі та розробити програму для зашифрування файлу даних лінійним афінним шифром 3-ого порядку (2 + 1 mod 4 = 3). Об’єм афлавіту NA повинен становити 64 (25+1 = 26 = 64).
Завдання №2 Асиметричне шифрування
Зашифрувати слово ХІД відкритого тексту за алгоритмом RSA. Дані параметри згідно з варіантом: p = 5, q = 13; n = p * q = 658; phi(n) = (p - 1) * (q - 1) = 48; е = 17, було обране навмання з діапазону 1 < e < phi(n), таке що НСД(е, phi(n)) = 1.
Представлення слова ХІД у цифровій формі Х=25 І=11 Д=5, тобто {25,11,5}.
1. Афінні шифри.
2. Алгоритм 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 біта.
Розроблення алгоритму за шифрування афінним
Список змінних та функцій використаних в програмі
alpfavit[] – масив з буквами латинського алфавіту;
zufrtext [] – масив, в який записується числова інтерпретація відкритого тексту;
dtxt – довжина повідомлення;
dalf – довжина алфавіту;
dt – кількість стовпців в матриці, в яку записаний текст повідомлення;
strlen() – визначення довжини рядка, який може бути заданий напряму або в масиві;
printf() – функція, що виводить текст і/або змінні на екран;
scanf() – функція, що зчитує введену користувачем інформацію з клавіатури;
fprintf() – функція, що записує текст і/або змінні в файл;
fscanf() – функція, що зчитує інформацію з файлу;
fclose() – функція, що закриває файл та зберігає його вміст;
fopen() – функція, що відкриває файл для читання і/або запису;
*ptext , *etext – покажчики на файл з відкритим та зашифрованим текстом, відповідно;
Блок схема програми зашифрування лінійним афінним шифром
Текст програми
#include<stdio.h>
#include<string.h>
#define C 255
#define N 64
#define K 3
void main(void) {
char alpfavit[N] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
char vidkrutiy[C],rezultat[C];
int zufrtext[C], A[K][K] ={{17,17,11},{10,11,17},{9,9,7}};
int S[K] = { 11, 23, 23 };
int i, j, dtxt, dalf, dt, temp = 0;
FILE *ptext;
FILE *etext;
ptext = fopen("pov.txt", "r");
fscanf(ptext, "%s", vidkrutiy);
printf("\n\n\tVidkrutiy text:\t "); scanf("%s", vidkrutiy);
dalf = strlen(alpfavit) - 1;
dtxt = strlen(vidkrutiy) - 1;
for (i=0; i<=dtxt; i++)
{ for (j=0; j<=dalf; j++)
{ if (vidkrutiy[i] == alpfavit[j]) zufrtext[i] = j;
if (( (dtxt/K) % K ) == 0) dt = round(dtxt/K);
else dt = round(dtxt/K) + 1;
int X[dt][K],
zufrrezultat[dt][K];
for (i=0; i<=(dt-1); i++)
{ for (j=0; j<=(K-1); j++)
{ X[i][j] = zufrtext[temp];
temp++; } }
temp = 0;
for (i=0; i<=(dt-1); i++)
{ for (j=0; j<=(K-1); j++)
{ zufrrezultat[i][j] = ( A[0][j] * X[i][0] ) + ( A[1][j] * X[i][1] ) + ( A[2][j] * X[i][2] ) + S[j];
if (zufrrezultat[i][j] >= N)
zufrrezultat[i][j] = zufrrezultat[i][j] % N;
} }
etext = fopen("text.txt", "w");
for (i=0; i<=(dt-1); i++)
{ for (j=0; j<=(K-1); j++)
{ if (temp < (dtxt+1))
{ fprintf(etext, "%c", alpfavit[zufrrezultat[i][j]]);
temp++;
} } }
temp = 0;
etext = fopen("text.txt", "r");
fscanf(etext, "%s", rezultat);
printf("\n\n\tZashifr tex:\t %s", rezultat);
printf("\n\n\n\n\tPress any key...");
fclose(ptext);
fclose(etext);
getch(); }
Зашифрування слова"ХІД" за алгоритмом RSA
Згідно номера залікової книжки числа p та q становлять відповідно 5 та 13.
Генерування ключів:
n=pq=5*13=65
(n)=n-p-q+1=48 //функція Ойлера
е вибираємо рівним 17
((n), е)=(48, 17)=1 //ці числа взаємно прості
Знаходимо обернений до е елемент d за допомогою розширеного алгоритму Евкліда:
48=17*2+14
17=14*1+3
14=3*4+2
3=2*1+1
2=1*2+0
V0=0, V1=1
V2=0-2*1=-2
V3=1-1*(-2)=3
V4=-2-12=-14;
V5=3+14=17
Отже, d==17
Відкритий ключ: n=65, e=17
Таємний ключ: d=17
Зашифрування:
Слово ХІД у числовому форматі матиме вигляд-{25,11,5}. Розбиваємо цей текс на блоки по 2 букви, і підносимо кожен блок до степеня 17 за модулем 65 за допомогою бінарного алгоритму.
17 =10001
2517mod 65-?
z0=1
z1=1*1*25mod 65=25
z2=25*25mod 65=40
z3=40*40mod 65=40
z4=40*40mod 65=40
z5=40*40*25mod 65=25
Отже, 2517 mod65=25
1117mod 65-?
z0=1
z1=1*1*11 mod 65=11
z2=11*11 mod 65=16
z3=16*16 mod 65=61
z4=61*61 mod 65=16
z5=16*16*11 mod 65=46
Отже, 1117mod 65=46
5 17mod 65-?
z0=1
z1=1*1*5 mod 65=5
z2=5*5 mod 65=25
z3=25*25 mod 65=40
z4=40*40 mod 65=40
z5=40*40*5 mod 65=5
Отже, 5 17mod 65=5
Отже, слово ХІД зашифроване за алгоритмом RSA матиме вигляд 25 46 5.
Розроблення алгоритму зашифрування
aлгоритмом RSA
В даному випадку, згідно із варіантом завдання, необхідно зашифрувати слово ШУМ алгоритмом RSA. Нам дано p = 5 і q = 17, е можна обрати на вибір. Всі інші елементи ми будемо дізнаватись за допомогою реалізації програмних засобів для їх знаходження.
Список змінних та констант
M[] – масив в який заносеться повідомлення;
n – змінна n в алгоритмі RSA;
e – змінна e в алгоритмі RSA;
d – змінна d в алгоритмі RSA;
C[] – масив, в якому зберігається зашифрований текст;
i, j – змінні, що використовуються в лічильниках циклів;
q – змінна, яка відповідає змінній q в алгоритмі RSA;
p – змінна, яка відповідає змінній p в алгоритмі RSA;
Блок-схема програми зашифрування алгоритмом RSA
Текст програми
#include<stdio.h>
#define X 3
char alpfavit[N] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't','u', 'v', 'w', 'x', 'y', 'z' };
int phi, M[X], n, e, d, C[X], PR;
char source[];
int check()
{ int i;
for(i=3; e%i==0 && phi%i==0; i+2)
{ PR = 1;
return;
}
PR = 0;
}
void Zashifruvannya ()
{ 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\tVidkrutui text:\t");
for(j=0; j<X; j++)
{ C[j] = C[j] % n;
printf(" %d", C[j]);
}
}
void rozhifruvannya()
{ 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\tZashifrovaniy text:\t");
for(j=0; j<X; j++)
{ M[j] = M[j] % n;
printf(" %d", M[j]);
}
}
void main(void)
{ int p, q, s;
printf("\n\tVvedit dva prostuh chisla:\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\tVvedit E:\t");
scanf("%d", &e);
check(); }
while(PR == 1);
d = 1;
do
{ s = (d * e) % phi;
d++;
}
while(s!=1);
d--;
printf("\n\tVidkritiy kluch:\t{%d,%d}", e, n);
printf("\n\tZakritiy kluch:\t{%d,%d}", d, n);
printf("\n\n\n\tVvedit text:\t ");
scanf("%s", source);
Zashifruvannya ();
printf("\n\n\n\ttext:\t ");
scanf("%s", eresult);
Zashifruvannya();
printf("\n\n\tPress any key...");
getch();
}
Результат виконання програми
зашифрування афінним шифром(3-го порядкку)
Результат виконання програми зашифрування алгоритмом RSA
Висновок
В даній роботі я вивчив і реалізував алгоритм кодування та розкодування афінним шифром 3-ого порядку. А також зашифрував слово за допомогоя алгоритму RSA.
Список використаної літератури
М.Вельшенбах. Криптография на С и С++ в действии. М., Триумф, 2004.
Б.Шнайер. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си. М., Триумф, 2002.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора