Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Елементарна криптографія
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Лабораторна робота №2
з дисципліни
«Теорія алгоритмів і математичні основи представлення знань»
на тему:
“ Елементарна криптографія”
Львів - 2008
Мета: ознайомитись з методами криптографії
Теоретичні відомості
Криптологія є . наукою, яка поділяється на криптографію та криптоаналіз. Однак досить часто термін криптографія вживається у загальнішому розумін ні як синонім до криптології. Захист інформації є ширшою галуззю, що охоплює крім теоретичних основ також технічні засоби, юридичні аспекти тощо.
Тайнопис також е ширшим поняттям. Крім криптографічних, він допускає й такі способи збереження таємниці, при яких повідомлення ніяк не перетворюється, а приховується сам факт його існування чи пересилання. Прикладом може служити використання невидимого чорнила.
Вживання термінів код та кодування як синонімів до шифру та шифрування є не лише архаїчним, а часто й помилковим. Код — це усталене правило для заміни одиниць інформації (букв, слів, цілих фраз) певними символами. Наприклад, S0S є кодом прохання про допомогу, а згідно із ASCII кодом літера а кодується двійковою послідовністю 1100001. Коди, які вивчає математична теорія кодування, застосовуються з метою дещо протилежною до криптографічної. Повідомлення шифрується для того, щоб воно стало незрозумілим, а кодується для того, щоб бути зрозумілим навіть після часткового спотворення із-за природних перешкод у каналі зв'язку. Ці два терміни слід чітко розме жовувати тому, що на практиці одна й та ж інформація може підлягати обом діям — у типовій ситуації текст закодовують у двійкову послідовність, її шифрують, а отриманий криптотекст перед відправленням кодують за допомогою коду, який дозволить виправити помилки після передачі.
Як рівноправні терміни ми будемо вживати дієслова шифрувати і криптувати та віддієслівні іменники шифрування і криптування. Виключно справою смаку є вибір між словосполученнями розкрити криптосистему та зламати криптосистему. Нарешті, Термін криптотекст має синонім криптограма, який щоправда зустрічається частіше у популярній, ніж у фаховій літературі.
Класичні методи шифрування:
2.1. Шифри простої заміни перетворюють відкритий текст таким чином, що кожен символ замінюється на якийсь інший. При цьому однаковим символам у відкритому тексті відповідають однакові символи у криптотексті, а різним — різні. Ключем є табличка, що вказує в який саме символ переходить кожен символ відкритого тексту. Для прикладу, шифр Цезаря в українському алфавіті задається таким ключем:
абвгґдеєжзиіїйклмнопрстуфхцчшщьюя
гґдеєжзиіїйклмнопрстуфхцчшщьюяабв
При шифруванні кожна буква, яка зустрічається у повідомленні, шукається у верхньому рядку і замінюється відповідною буквою із нижнього рядка (пропуски між словами та розділові знаки ігноруються). Наприклад, криптографія перетворюється у нуйтхсеугчкв.
Шифр зсуву є звуженням загального шифру заміни на сукупність лише п ключів, у яких нижній рядок є циклічним зсувом верхнього рядка. Ключ такого гатунку повністю визначається довжиною зсуву s. Можна вважати, що 0 ≤ s < п, оскільки зсуви на s і на s + п позицій дають однаковий результат.
Інші підкласи шифру простої заміни розглядаються у § 11.3.
2.2. Частотний аналіз. Як нам відомо з попереднього пункту, шифр заміни над n-символьним алфавітом має n! ключів. Для значень п = 26,33 (латинський та український алфавіти) це число є дуже великим. Для його оцінки можна скористатись варіантом формули Стірлінга B.I, звідки для п = 26 отримуємо п > 10 26. Число справді велике — нагада ємо, що наша планета існує лише 109 років, а наступний льодовиковий період очікується через 14000 років, тобто 4,41504 • 1011 секунд [137]. Це співставлення переконливо засвідчує безперспективність брутальної атаки на шифр заміни, однак цього недостатньо аби стверджувати, що він є надійним. Виявляється, успішний криптоаналіз можливий за допомогою частотного методу.
Частота символу у тексті дорівнює кількості його входжень у цей текст, поділеній на загальну кількість букв у тексті. Наприклад, частота букви а у тексті купилаиніамаиконика дорівнює 4/18 = 2/9, а частота пропуску між словами у цьому ж тексті дорівнює 2/18 = 1/9. Для кожної мови справджується такий емпіричний факт:
У досить довгих текстах кожна буква зустрічається із приблизно однаковою частотою, Залежною від самої букви і незалежною від конкретного тексту.
На підставі цього факту із кожним символом пов'язують деяке число, частоту цього символу в мові, з якою приблизно він зустрічається в кожному великому тексті цією мовою. Підрахунок частот символів у мові здійснюють на основі вибраного навмання середньостатистичного тексту. У додатку А наведено таблички частот для української, російської та англійської мов.
Припустимо, що перехоплено довгий криптотекст (або послідовність багатьох коротких), отриманий за допомогою шифру заміни. Частотним методом можна здійснити дешифрування, навіть не знаючи ключа. Для цього обчислюють частоти кожного символу в криптотексті і порівнюють отримані результати з табличкою частот для мови, якою написане повідомлення. Не слід сподіватися, що таким чином можна буде однозначно встановити ключ, але перебір це дозволить скоротити радикально. Наприклад, якщо при шифруванні не ігноруються пропуски між словами, то найпоширеніший символ у криптотексті поза сумнівом відповідає саме пропуску. А відтак стає відомою сукупність символів, що відповідають словам з одної букви (в українській мові це а,б,в,б,ж,з,і,й,о,у,я) та словам з двох букв (де,не,на,до та інші), що дозволяє ці символи розпізнати ціною справді невеликого перебору. Свою роль при частотному аналізі відіграє та обставина, що кожна мова володіє властивістю надлишковості, тобто текст можна поновити навіть коли частина його букв невідома.
Гомофонний шифр заміни був винайдений великим німецьким математиком Карлом Фрідріхом Гаусом [141]. Цей шифр грунтується на ідеї, яка робить підрахунок частот символів безперспективним. Кожна буква відкритого тексту замінюється не єдиним символом як у шифрі простої заміни, а будь-яким символом із декількох можливих. На приклад, замість а може здійснюватись підстановка будь-якого із чисел 10,17,23,46,55, а замість б — будь-якого із 12,71. Головне, щоб замість різних букв завжди підставлялись різні символи — ця вимога забезпечує можливість дешифрування. Вибір одного з можливих варіантів щоразу робиться випадково. Якщо кількість варіантів для кожної букви пропорційна її частоті в мові, то всі символи у досить довгому криптотексті зустрічатимуться з приблизно однаковою частотою, що не дозволить пов'язати їх з якимись буквами відкритого тексту. Однак гомофонний шифр піддається ретельнішому і трудомісткішому різновиду частотного аналізу, який окрім частот окремих символів враховує також частоти пар символів. Подібний аналіз дозволяє ламати ще один клас шифрів заміни, про що йдеться у наступному пункті.
Частотний аналіз може бути корисним і в інших ситуаціях. Напри клад, він дозволяє комп'ютерові без участі людини відрізнити осмислений текст від хаотичного набору символів. Завдяки цьому на машину можна перекласти здійснення брутальної атаки, тобто повного перебору ключів.
2.3. Поліграмні шифри. Послідовність кількох букв тексту називається поліграмою. Послідовність із двох букв називається біграмою (іноді диграфом), а із l букв — l-грамою. З- і 4-грами називають відповідно три- і тетраграмами. Полгграмний шифр заміни полягає у розбитті відкритого тексту на l-грами для деякого фіксованого числа l і заміні кожної з них на якийсь символ чи групу символів. Ключем є правило, за яким відбувається заміна. Якщо загальна кількість символів у тексті не ділиться націло на l, то остання група символів доповнюється до l -грами довільним наперед обумовленим способом.
Як приклад розглянемо біграмний (часом кажуть диграфний) шифр, який назвемо шифром чотирьох квадратів, хоча насправді він є відміною відомого шифру Play fair (початок XVI століття). Цей шифр застосовується до текстів латинкою.
2.4. Поліалфавітні шифри можна потрактувати як такі шифри заміни, в яких, позиція букви у відкритому тексті впливає на те, за яким саме правилом ця буква буде змінена. Ми розглянемо два класичні приклади.
шифр віженера. Відкритий текст і криптотекст записуються в одному й тому ж алфавіті. Для букв x та у цього алфавіту означимо їх суму х + у як результат циклічного зсуву букви x вправо у алфавіті на кількість позицій, що дорівнює номеру букви у в алфавіті. При цьому дотримуємося такої домовленості:
нумерація букв алфавіту починається з нуля.
Наприклад, для української абетки маємо а+а=а,б+а=б,в+б=г, я+в = б. Ця операція природним чином задається так званою таблицею Віженера
Шифр Віженера застосовують до повідомлення, записаного в рядок без пропусків між словами та розділових знаків. Ключем є слово у тому ж алфавіті. Якщо ключ коротший за повідомлення, то його записують багато разів підряд доки не вийде рядок такої ж довжини. Рядок з розмноженим ключем розміщують під рядком з повідомленням, і букви, що опинилися одна над другою, додають.
2.5. Шифрування блоками. Часто алгоритм шифрування буває призначений для перетворення послідовностей символів лише фіксованої довжини l. Коли ж потрібно застосувати його до більшого тексту, цей текст розбивають на блоки — групи по l символів, і кожен блок перетворюють окремо. Такі шифри називаються блоковими з періодом 1. Якщо загальна кількість символів у тексті не ділиться націло на l, то остання група символів доповнюється до повного блоку довільним наперед обумовленим способом.
Прикладом блокового шифру з періодом l може слугувати будь-який поліграмний шифр, що здійснює заміну l -грам. Стосовно термінології зазначимо, що під поліграмою розуміють послідовність літер деякої природної мови, в той час як блок може складатися із довільних символів, скажімо, цифр.
Шифр Віженера з фіксованою довжиною ключа l теж можна роз глядати як блоковий шифр з періодом l.
2.6. Шифри перестановки зберігають всі букви відкритого тексту, але розміщують їх у криптотексті в іншому порядку. Прикладами шифрів перестановки, які нам вже зустрічалися, є шифр частоколу і Скитала. Це представники широкого підкласу шифрів перестановки, які називаються шифрами обходу. У якості ще одного типового прикладу розглянемо матричний шифр обходу. Повідомлення записується рядками у вигляді прямокутної матриці. Криптотекст формується зчитуванням букв із матриці у зміненому порядку, а саме, стовпчиками. При цьому послідовність, у якій зчитуються стовпчики, визначається ключем. Було поширеним задання ключа'у вигляді ключового слова ,що легко запам'ятовувалось. Порядок зчитування стовпчиків збігався з алфавітним порядком букв ключового слова.
Текст програми
#include <graphics.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <dos.h>
#define M 255
#define N 8
#define asc 48
#define max 123
#define min 32
//#define lam 0.08
void Generate(int (*p)[N]);
char * Cod_Decod(int (*z_1)[N],int (*z_2)[N],int (*z_3)[N],int (*z_4)[N],char *symv);
int main(void){
int sumvolu_1[N][N];
int sumvolu_2[N][N];
int sumvolu_3[N][N];
int sumvolu_4[N][N];
int (*p_1)[N],(*p_2)[N],(*p_3)[N],(*p_4)[N];
char word[M],*shifr,*deshifr;
int ost,b;
printf("\t\t\tVvedit vashe rechennia\n\n");
gets(word);
fflush(stdin);
b=strlen(word);
if( (ost=b%2) ){
word[b]=' ';
word[b+1]='\0';
}
p_1=sumvolu_1;p_2=sumvolu_2;
p_3=sumvolu_3;p_4=sumvolu_4;
randomize();
Generate(p_1);Generate(p_2);
Generate(p_3);Generate(p_4);
getch();
clrscr();
printf("\n\nEntered word : %s",&word);
shifr=Cod_Decod(p_1,p_2,p_3,p_4,word);
delay(1000);
printf("\n\nCoded word : %s",shifr);
delay(1000);
deshifr=Cod_Decod(p_2,p_1,p_4,p_3,shifr);
printf("\n\nDecoded word : %s",deshifr);
getch();
clrscr();
return 0;
}
void Generate(int (*p)[N]){
int i,j,ext,k,all=0,probih=0,can=1,done;
int mean_while[N*N];
for(j=0,all=0;j<N;j++)
for(i=0;i<N;i++){
done=all;
do{
can=1;
ext=random(max);
if(ext<32)ext+=min;
if( (ext>=32 && ext<=33) || (ext>=44 && ext<=46) || (ext>=48 && ext<=57) || (ext>=65 && ext<=90) || (ext>=97 && ext<=122)){
if(probih)
for(k=0;k<all;k++)
if(ext==mean_while[k]){
can=0;
break;
}
if(can){
//sumvolu_1[j][i]=ext;
*(*(p+j)+i)=ext;
mean_while[all]=ext;
all++;probih=1;
}
}
}while(done==all);
}
for(j=0;j<N;j++){
printf("\n");
for(i=0;i<N;i++)
printf(" %d",*(*(p+j)+i));
}
printf("\n\n");
}
char * Cod_Decod(int (*z_1)[N],int (*z_2)[N],int (*z_3)[N],int (*z_4)[N],char *symv){
int i,j;
int i_1,i_2,j_1,j_2,k;
char string[M];
int s_1,s_2;
for(k=0;k<strlen(symv);){
s_1=*(symv+k);
s_2=*(symv+k+1);
for(j=0;j<N;j++)
for(i=0;i<N;i++){
if(*(*(z_1+j)+i)==s_1){
j_1=j;i_1=i;
}
if(*(*(z_4+j)+i)==s_2){
j_2=j;i_2=i;
}
}
string[k]=*(*(z_2+j_1)+i_2);
string[k+1]=*(*(z_3+j_2)+i_1);
k=k+2;
}
string[k]='\0';
return string;
}
Результати роботи програми :
Висновок: У даній лаборторній роботі я розробив алгоритм і написав програму, яка реалізовує кодування повідомлення та його розкодовування.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора