Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Симетричне шифрування. Асиметричне шифрування.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Курсова робота
Предмет:
Методи та засоби криптологічних перетворень
Група:
ІБ-44
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет Львівська політехніка
Курсовий поект
з дисципліни: “Методи та засоби
криптологічних перетворень”
Виконав
студент групи ІБ — 44
Перевірив
Горпенюк А. Я.
Львів — 2010
Зміст
Завдання стр. 3
Опис використаних методів шифрування стр. 3
Розроблення алгоритму зашифрування лінійним шифром 1–ого порядку стр. 6
Блок-схема програми №1 стр. 7
Програма №1 стр. 8
Розроблення алгоритму за шифрування aлгоритмом RSA стр. 10
Блок-схема програми №2 стр. 11
Програма №2 стр. 12
Висновки стр. 15
Список використаної літератури стр. 16
Номер останніх цифр залікової книжки: 47
Завдання №1
Симетричне шифрування
Вибрати ключі та розробити програму для зашифрування файлу даних лінійним афінним шифром 1-ого порядку. Об’єм афлавіту NA повинен становити 512 (25+4 = 29 = 512).
Завдання №2
Асиметричне шифрування
Зашифрувати слово СІМ відкритого тексту за алгоритмом RSA. Дані параметри згідно з варіантом: p = 5, q = 11; n = p * q = 55; phi(n) = (p - 1) * (q - 1) = 40; е = 13, було обране навмання з діапазону 1 < e < phi(n), таке що НСД(е, phi(n)) = 1.
Представлення слова СІМ у цифровій формі С=21 І=11 М=16, тобто {21,11,16}.
Опис використаних методів шифрування
1. Шифри простої заміни.
n-символьний алфавіт утотожнюємо з кільцем Zn. А саме, кожна буква замінюється своїм номером у алфавіті, прийому нумерація починається з нуля.
Наприклад, латинська абетка утотожнюється із Z26, а українська із Z33. Літера а української абетки трактується як 0, літера б як 1, в як 2 і т.д. Тепер до букв відкритого тексту ми можемо вільно застосовувати операції додавання та множення за відповідним модулем.
Шифр зсуву.
Ключ: s таке, що 0 < s < п.
Шифрування. У повідомленні кожна буква х заміщується буквою Е(х) = (х + s) mod n.
Дешифрування. У криптотексті кожна буква х' заміщується буквою D(x') = (х' + s') mod п, де
s' = п - s. Величину зворотнього зсуву s' будемо називати дешифруючим ключем.
Лінійний шифр.
Ключ: а таке, що 0 < а < п і НСД (а, п) = 1.
Шифрування. У повідомленні кожна буква х заміщується буквою Е{х) = (ах) mod n.
Дешифрування. У криптотексті кожна буква х' заміщується буквою D(x') = (a'x') mod п, де
а' = a-1 mod n — дешифруючий ключ.
Узагальненням і шифру зсуву, і лінійного шифру є Афінний шифр.
Ключ: a, s такі, що 0 < s < п, 0 < а <п і НСД (а, п) = 1.
Шифрування. У повідомленні кожна буква х заміщується буквою Е(х) = (ах + s) mod n.
Дешифрування. У криптотексті кожна буква х' заміщується буквою D(x') = (a'x'+ s’) mod n, де пара а’ = a-1 mod n, s’ = (-a’s) mod n є дешифруючим ключем.
Як і кожен шифр простої заміни, афінний шифр піддається частот ному аналізові.
2. Афінні шифри вищих порядків.
Подумаємо, як можна розши рити монограмні шифри попереднього пункту так, щоб вони оперували з k-грамами для довільного k > 1. Спочатку введемо операцію дода вання в Znk. Сумою векторів X = (x1,. . .,хk) і s = (s1,… ,sk) з Znk є вектор X + S = ((x1 + s1) mod n,…, (хk + sk) mod n). Zkn з операцією додавання є групою. Вектор -S = (n — s1,…, n — sk) є оберненим до вектора
S = (s1,…,sk).
Шифр зсуву k-го порядку.
Ключ: S є Zkn.
Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою Е(Х) = X + S.
Дешифрування. Кожна k-грама X' криптотексту заміщується k-грамою D(X') = X' + 5’, де
S' = -S є дешифруючим ключем.
Лінійний шифр k-го порядку.
Ключ: А Є GLk(Zn).
Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою Е(Х)= АХ.
Дешифрування. Кожна k-грама Х’ криптотексту заміщується k-грама D(X') = A'X', де
А’ = А-1 — дешифруючий ключ.
Афінний шифр k-го порядку.
Ключ: А Є GLk{Zn} і S Є Znk.
Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою Е(Х) = АХ + S.
Дешифрування. Кожна k-грама X' криптотексту заміщується k-грамою D{X’} = А’X’ + S’, де А’ = А-1 і S’ = -A’S — дешифруючий ключ.
3. Алгоритм 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 біта.
Розроблення алгоритму зашифрування
лінійним афінним шифром k-ого порядку
В даному випадку, згідно із завданням курсового проекту, необхідно розробити алгоритм зашифрування 1-ого порядку. Це означає, що нашим ключем буде матриця 1х1, тобто один елемент. Для зашифрування нашого повідомлення, нам доведеться розбити його на k-грами по одному символу, після чого помножити ці k-грами на матрицю-ключ.
Блок схема програми зашифрування лінійним афінним шифром
Текст програми
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
const size_t small_buffer = 20;
const size_t big_buffer = 102400;
void main() {
clrscr();
char text[small_buffer];
char big_text[big_buffer];
FILE *start_file = fopen( "f:\\start.txt", "rb" ); /відкриваєм файл/
size_t read_len = 0;
size_t file_len = 0;
while( read_len = fread(text, 1, small_buffer, start_file ) ) /довжина файлу/
{
memcpy( big_text + file_len, text, read_len );
file_len += read_len;
}
int j,a,i;int key[]={1,0,0,0,0,0,0,0,0}; /задаємо значення ключа/
int k2,k1[9]; k2=0;
for(i=0;i<9;i++) /очищення масиву/
{k1[i]=0;}
for(i=0;i<9;i++) /цикл знаходження значення ключа/
{{ if (1==key[i])
k1[i]=pow(2,i);
else k1[i]=0;}
a=a+k1[i];}
k2=pow(2,9);
for(j=0;j<file_len;j++) /цикл шифруфання тексту/
{
big_text[j]=big_text[j]*a;
big_text[j]=big_text[j]%k2;
}
FILE *end_file = fopen( "f:\\end.txt", "wb" ); /створення файлу з шифртекстом/
fwrite( big_text, 1, file_len, end_file ); /заносимо шифртекст у файл/
fclose( start_file );
fclose( end_file ); }
Відкритий текст: тест
Криптотекст: кєлк
Розроблення алгоритму зашифрування
aлгоритмом RSA
В даному випадку, згідно із варіантом завдання, необхідно зашифрувати слово СІМ алгоритмом RSA. Ми маємо p = 5 і q = 11, е можна обрати на вибір. Всі інші елементи ми будемо дізнаватись за допомогою реалізації програмних засобів для їх знаходження.
Проведено попереднє зашифрування алгоритмом RSA, та знаходження змінної d для закритого ключа, що використовується в розшифруванні криптотексту.
дано: p = 5, q = 11;
розрахуємо модуль n = p * q, який буде рівним n = 5 * 11 = 55;
розрахуємо phi(n) = (p – 1) * (q – 1), що буде рівним phi(n) = (5 – 1) * (11 – 1) = 40;
навмання вибираємо е з кільця цілих чисел 1 < e < phi(n), таке що НСД(e, phi(n)) = 1.
е = 13;
отримуємо відкритий ключ (e, n), який дорівнює (13, 55);
за допомогою розширеного алгоритму Евкліда знаходимо d, таке що ed = 1 mod phi(n):
d = e –1 mod phi(n);
d = 13 –1 mod 40;
Цілочисельно ділимо phi(n) = 40 на e –1 = 13:
40 = 13 * 3 + 1;
13 = 1 *13 +0;
V0 = 0;
V1 = 1;
V2 = V0 – q1V1 = 0 – 3 * 1 = –3;
Отже, наше d буде дорівнювати останній елемент V2 mod 40, тобто -3 mod 40 = 37.
отримуємо закритий ключ (d, n), який дорівнює (37, 55).
шифрування слова
с=21,і=11,м=16
21^13mod55=21
11^13mod55=11
16^13mod55=26
зашифрований текст: 21 11 26
Блок-схема програми зашифрування алгоритмом RSA
Текст програми
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
const size_t small_buffer = 20;
const size_t big_buffer = 1024000;
char binarn(char a, int n, int m);
void main() {
clrscr();
char text[small_buffer];
char btext[big_buffer];
FILE *start_file = fopen( "f:\\start.txt", "rb" ); /відкриваєм файл з криптотекстом/
FILE *end_file = fopen( "f:\\end.txt", "wb" ); /створюєм файл для запису шифртексту/
size_t read_len = 0;
size_t file_len = 0;
while( read_len = fread(text, 1, small_buffer, start_file ) ) / довжина файла/
{
memcpy( btext + file_len, text, read_len );
file_len += read_len;
}
int q,f,p,k,i,e,n1;q=11;p=5;
n1=q*p; / початкові умови шифрування/
char slovo,slovo_1,z;
f=n1-p-q+1;
printf(”vvedit proste n1 e v mezax= “); /знаходим відкритий ключ/
printf(“%d\n”,f);
printf("e=");
scanf(“%d”,&e);
for(i=0;i<=e;i++) /знаходим таємний ключ/
{ if (1==e*i%f)
{k=i;break;} else k=0; }
for(int j1=0;j1<file_len-2;j1=j1+2)
{
for(int j=1;j>=0;j--) /ділимо текст на блоки/
{for (int i=0;i<13;i++)
{
z=(z<<1) | btext[j+j1] & 1;
btext[j+j1]= (btext[j+j1]>>1);
}
}char slovo=0;
for (int i=0;i<13*2;i++)
{
slovo=(slovo<<1) | z & 1;
z= (z>>1);
}
slovo=binarn(slovo,e,n1); /функція піднесення до степеня по модулю/
for (int i=0;i<13*2;i++) /замінюєм блоки на слова/
{
z=(z<<1) | slovo& 1;
slovo= (slovo>>1);
}
for( j=1;j>=0;j--)
{ for (i=0;i<13;i++)
{
btext[j+j1]=(btext[j+j1]<<1) | z & 1;
z= (z>>1) ;
}
}
}
fwrite( btext, 1, file_len, end_file ); /записуєм шифртекст в файл/
fclose( start_file );
fclose( end_file ); getch(); }
char binarn(char a, int n, int m) { /бінарний метод піднесення до степеня/
if (n == 1)
return a % m;
char z;
z = binarn(a, n / 2, m);
z = (z * z) % m;
if (n % 2 == 1) z = (z * a) % m;
return z;
}
Результат виконання програми
зашифрування алгоритмом RSA
Відкритий текст :тест
Криптотекст:6&+d
Висновок
При роботі із цим курсовим проектом я ознайомився з симетричними та асиметричними алгоритмами закодування відкритих текстів. Для закодування симетричнимом алгоритмамом використовував афінний лінійний шифр який є не стійкий до атаки з вибором відкритого тексту. Для закодування асиметричнимом алгоритмамом використовував алгоритм RSA який є дуже зручний через високу стійкість та простоту в реалізації.
Список використаної літератури
О.В.Вербіцький. Вступ до криптології. Львів., "ВНТЛ", 1998.
И.М.Виноградов. Основы теории чисел. М., "Наука", 9-е издание 1981.
В.Жельников. Криптография от папируса до компьютера. М., "АВР", 1996.
К.Шеннон. Теория связи в секретных системах. В Работы по теории информации и кибернетике, стр. 333-402. М, Изд. Иностр. Лит., 1963.
М.Вельшенбах. Криптография на С и С++ в действии. М., Триумф, 2004.
Б.Шнайер. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си. М., Триумф, 2002.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора