Аналіз стійкості криптографічних систем з використанням штучного інтелекту

Размещено на http://www.allbest.ru/

Аналіз стійкості криптографічних систем з використанням штучного інтелекту

Annotation

The work is about the cryptographically methods, realized with soft. The different cryptographic objects are presented in it - from simple ciphers to cryptography protocols. Everyone has been completed with necessary explanations and some historical facts. Besides all, such wide used cryptographically systems as DES and RSA are presented and analyzed here. There are also their simple examples, realized with soft languages Dev-C++ and VBA. The work can be used for the first acquainting with the general ideas and characteristics in the Cryptography course.

Реферат

Робота містить теоретичний та практичний матеріал, що дозволяє ознайомитись з предметом вивчення та основними проблемами криптографії, історією її формування як науки та практичними сферами застосування. В роботі розглянуті різні криптографічні обєкти, починаючи від примітивних шифрів і закінчиючи криптографічними протоколами. Надані приклади їх реалізації та аналізу з допомогою сучасного програмного забезпечення.

Вступ містить інформацію щодо предмету та термінології, а також деякі історичні відомості. Основний матеріал роботи розбито на три тематичні частини, кожна з яких містить теорію та практичні завдання для самоперевірки. Відповіді і приклади розвязання до них містятться в 4-му розділі..

Зважаючи на технічні характеристики наявного програмного забезпечення, в даній роботі не ставилась задача створення нового шифру чи вдалої атаки на один із відомих шифрів. Натомість викладені в ній загальні відомості з криптографії, опис найвідоміших систем шифрування та приклади їх спрощеної реалізації, дають змогу використовувати її в якості методичного посібника для студентів при вивченні курсу криптографії та для першого ознайомлення з методами і засобами застосування комп'ютерних технології в цьому курсі.

Вступ

Предмет вивчення криптографії.

Як передати певну інформацію певному адресату таємно від інших? Існують три основні шляхи вирішення цієї проблеми.

1) По-перше - створити абсолютно надійний, недоступний для інших канал зв'язку між абонентами. Зауважимо, що при сучасному рівні розвитку науки і техніки, за умов значної віддаленості абонентів та необхідності неодноразової передачі великих об'ємів інформації, це практично неможливо.

2) Використовувати відкритий канал зв'язку, при цьому приховуючи сам факт передачі інформації. Засобами та методами таємної передачі займається стеганографія.

3) Використовувати відкритий канал зв'язку, але передавати інформацію в зміненому вигляді, так, щоб відновити її міг тільки адресат. Розробкою методів перетворення (шифрування) інформації з метою її захисту від сторонніх користувачів займається криптографія.

Такі методи і способи перетворення інформації називаються шифрами. Процесс застосування шифру до секретної інформації, тобто перетворення відкритого тексту в шифртекст, або криптграму, називається шифруванням, дешифрування, відповідно - процесс відтворення секретної інформації з криптограми.

Відмітимо, що задача таємної передачі виникає для секретної (таємної, конфіденційної і т.п.) інформації. Тобто такої, що має наступні характеристичні особливості: - існує певне коло законних користувачів, що мають право володіти даною інформацією; - існують незаконні користувачі (противники), які прагнуть оволодіти даною інформацією, щоб використати її на благо собі та на збитки законним користувачам.

Таким чином, криптографія займається такими методами захисту інформації, які не дозволили б противнику відновити її з перехвачених повідомлень. При цьому по каналу звязку передається не сама інформація, а шифртекст, так що перед противником виникає задача розкриття, або зламу шифра, тобто отримання секретної інформації із криптограми без знання застосованого шифру. Спроба зламу шифра називаеться атакою на шифр. Відповідно, важливою характеристикою шифра є його здатність витримувати атаки - стійкість шифра.

Слід зазначити, що до цього часу не існує точних математичних методів оцінки стійкості шифрів, тому для кожного конкретного шифру стійкість його визначається проведенням різноманітних атак на нього. Наука, що займається розробкою методів і способів розкриття шифрів, називається криптоаналізом, і разом з криптографією складає криптологію.

Ще одна криптографічна проблема полягає в тому, що шифрування та дешифрування мають бути - по можливості - простими, аби знизити часові витрати та ймовірность виникнення помилок при обробці інформації. Задля цього іноді навіть свідомо поступаються високою стійкістю шифру.

Отже, ясно, що отримання надійного та зручного у корисуванні шифру - непроста задача, тому, щоб подовжити термін «життя» шифру та підвищити його стійкість, в шифр вводиться ключ. Це змінна частина шифру, що застосовується для шифрування конкретного повідомлення, зміна ключа забезпечує зміну усієї криптограми, хоча принцип шифрування залишається тим самим. Тоді, навіть знаючи застосований шифр, противник не зможе прочитати повідомлення без ключа. Тобто задачею противника є підбір ключа, а надійність шифру певною мірою визначається кількістю всіх можливих ключів.

Проблема обміну ключами, що постає перед законними користувачами, може бути вирішена способами, які згадувались вище - створенням закритого каналу або таємної передачі інформації.

Отже, для шифрування/деширування певним шифром необхідні наступні обєкти:

Р - скінчена множина можливих відкритих текстів;

С - скінчена множина можливих шифрованих текстів;

К - ключовий простір, скінчена система можливих ключів;

F - множина функцій шифрування f_k: РК-С, що перетворюють відкритий текст хР на шифроване повідомлення у= f_k (х), уС з використанням деякого ключа kК;

D - множина функцій дешифрування d_k: С-Р, що здійснюють зворотне перетворення. Сукупність означених об'єктів {Р, С, К, F, D}, така, що kК f_kF, d_kD: (d_k f_k)(х)= (f_k d_k)(х)=х, називають криптосистемою, або системою шифрування.

Скінченність множин Р, С, К зумовленя скінченістю застосованого алфавіту - множини символів, що використовуються для їх запису. Проте не треба думати, що цей факт спрощує задачу противника - так, наприклад, система шифрування, що працює з 64-символьними послідовностями, записаними двійковою системою, має 2 ⁶⁴ можливих слів, а кількість можливих ключів становить (2 ⁶⁴)!, що практично унеможливлює атаку методом простого підбору ключів.

В залежності від того, чи дешифруваня відбувається за тим самим ключем, що і шифрування, виділяють системи симетричні та асиметричні. До останніх належать так звані системи з відкритим ключем, в яких ключ для шифрування є загальновідомим. Завдяки спеціальному вибору функцій шифрування/дешифрування зашифрувати повідомлення може будь-хто, прочитати - тільки той, хто має секретний, закритий ключ. Вимагається, щоб при цьому ключ для дешифрування неможливо або майже неможливо було відновити з відкритого ключа. Тоді знімається питання щодо обміну ключами. Принцип криптосистеми з відкритим ключем покладено в основу електронного підпису, електронних грошей та ін.

Розділ 1. Криптоаналіз класичних шифрів

Шифри як засіб таємної передачі інформації з'явились і застосовувались досить давно. Один із найдавніших відомих шифрів - «Сцитала», відноситься до часів війни спартанців з Афінами в Vст. до н.є. В листах Цезаря знайдено шифр, відомий тепер як «шифр Цезаря» - заміна кожної літери третьою за нею по алфавіту. Відомі шифри Генріха VI і Ришельє, «цифірна абетка» Петра І, „решітка” Кардано - видатного математика ХІVст., та ін. Криптографією займалися політики і дипломати, вчені та злодії; був час, коли мистецтво створення і розкриття шифрів вважалось чимось на зразок чорної магії.

Прогрес в науці і техніці не оминув і криптографію. З'являються перші шифрувальні машини; ще наприкінці ХІХ ст. голландець Керкгоффс (1835-1903) формулює криптоаналітичний принцип, за яким противнику вважається відомим весь метод шифрування, окрім ключа - ним користуються і до сьогодні.

Перша та Друга Світові Війни виводять криптологію на новий рівень. Їх масштаби вимагають передачі значних об'ємів секретної інформації - і, відповідно, якнайефективніших методів шифрування та аналізу зашифрованої інформації. В 1945р. американець Клод Шеннон виступає з доповіддю «Математична теорія криптографії», зміст якої було засекречено спецслужбами. Рік її опублікування - 1948р. вважається роком народження криптографії - „теорії інформації” - як математичної науки. В своїй праці Шеннон узагальнив накопичений до нього досвід створення та використання шифрів, та описав мовою математики деякі з найвідоміших шифрів, показавши, що навіть складні шифри можуть містити як елементи прості шифри заміни і перестановки, та їх різноманітні комбінації. Далі розглянемо та проаналізуємо деякі з них.

1.1 Шифр простої заміни

1.1.1 Опис та криптоаналіз

Взагалі шифром заміни називають метод шифрування, при якому кожна літера, або група літер, або слово заміняються певним символом або групою символів. Звичайно, складність шифру не залежить від природи застосованих для шифрування символів - це можуть бути літери, цифри, малюнки тощо.

Взагалі, нехай Х= {x₁, x₂, … x_n} - алфавіт, тобто набір символів відкритого повідомлення, У= {y₁, y₂, … y_m} - набір символів шифрованого повідомлення. Тоді шифр заміни описується функцією

f: X ->Y, f(x_i)=y_j, i=1,n; j =1,m.

Розрізняють шифри заміни:

а) симетричні та асиметричні;

б) моноалфавітні (простої заміни) та багатоалфавітні;

в) поточні та блочні, тощо.

Шифр простої заміни - такий, що f бієктивна, тобто Х і У мають однакову кількість символів, і кожному x_i однозначно відповідає єдине y_i. Тоді, замінивши кожен символ відкритого повідомлення х₁х₂...х_р, отримаємо шифроване повідомлення f(x₁) f(x₂)... f(x_р). Дешифрування проводиться у зворотному порядку.

Найпростішим варіантом шифру заміни є шифр зсуву, коли кожна літера „зсувається” по алфавіту на кілька позицій. Величина зсуву, власне, і є ключем. Наприклад: ключ - 13 (№„й”), тоді літери замінюються наступним чином:

Математично шифр зсуву описується як

y_i = x_i + k (mоd n),

де n - кількість літер алфавіту (для українського - 32, разом з «пробілом» - 33); k - ключ, величина зсуву, при k=3 отримаємо так званий «шифр Цезаря».

Цей шифр є простим та зрозумілим у використанні, проте розкривається просто перебором можливих варіантів, надто якщо під рукою є комп'ютер.

Наприклад, маємо криптограму, зашифровану шифром заміни:

Уо,дкедзеис,дзеис,дзеисдкїрїтїтбпнс,дЧесдухереділжянтутбпеджурнпусдяухтїтбпнс.

Візьмемо перших 10-15 символів, та розглянемо усі варіанти зсуву по алфавіту. Зауважимо, що при шифруванні в вихідному тексті замість ї, й, є можуть використовуватись і, и, е - це майже не впливає на зміст тексту, проте спрощує шифрування. Бачимо, що тут немає є, й, проте присутня ї - отже, спробуємо спочатку повний алфавіт з 32 символів та пробілу. Результат роботи програми:

Ключ	Оброблене повідомлення	Ключ	Оброблене повідомлення
1	Фпелєеієйт,еієйт	17	Єбтюутцущд,тцущд
2	Хрємжєїжку,єїжку	18	Жвуяфучфье,учфье
3	Цсжнзжизлф,жизлф	19	Згф хфшхює,фшхює
4	Чтзоізйімх,зйімх	20	Ідхацхщцяж,хщцяж
5	Шуіпїікїнц,ікїнц	21	Їецбчцьч з,цьч з
6	Щфїриїлиоч,їлиоч	22	Иєчвшчюшаі,чюшаі
7	Ьхисйимйпш,имйпш	23	Йжшгщшящбї,шящбї
8	Юцйткйнкрщ,йнкрщ	24	Кзщдьщ ьви,щ ьви
9	Ячкулколсь,колсь	25	Ліьеюьаюгй,ьаюгй
10	шлфмлпмтю,лпмтю	26	Мїюєяюбядк,юбядк
11	Ащмхнмрнуя,мрнуя	27	Нияж яв ел,яв ел
12	Бьнцонсоф ,нсоф	28	Ой за гаєм, гаєм
13	Вюочпотпха,отпха	29	Пкаібадбжн,адбжн
14	Гяпшрпурцб,пурцб	30	Рлбївбевзо,бевзо
15	Д рщсрфсчв,рфсчв	31	Смвигвєгіп,вєгіп
16	Еасьтсхтшг,схтшг	32	Тнгйдгждїр,гждїр
17	Єбтюутцущд,тцущд	33	Уодкедзеис,дзеис

Осмислений текст отримали тільки у одному випадку - 28. За допомогою знайденого ключа завершуємо розшифрування:

Отримане повідомлення	Уо,дкедзеис,дзеис,дзеисдкїрїтїтбпнс, дЧесдухереділжянтутбпеджурнпусдяухтїтбпнс.
Ключ	28
Оброблене повідомлення	Ой, за гаєм, гаєм, гаєм зелененьким, Там орала дівчинонька воликом чорненьким.

Взагалі кажучи, для розкриття шифру зсуву досить двох правильно розшифрованих літер - по одній обчислюємо величину зсуву, по іншій перевіряємо. Узагальненням шифру зсуву є афінний шифр:

y_i =аx_i + b (mоd n)

де ключ - пара чисел (а,b). Але він розкривається за… трьома відомими літерами. Наприклад, нам відомі: «р»(№19) - а(№1), «о»(№17) - в(№3), «п»(№20) - н(№16). Тоді розкриття шифру зводиться до розвязання системи:

а+ b=19 (mоd 32),

3а + b=17 (mоd 32);

звідки а=15, b=4. Третя літера слугує для перевірки. Власне кажучи, за трьома літерами можна розкрити шифр, не знаючи довжини алфавіту. Кількість можливих варіантів ключа для афінного шифру - n², для українського алфавіту 32²=1024. Тобто і в цьому разі можна обійтись простим перебором.

Дещо цікавіший шифр отримаємо, якщо натомість алфавіту візьмемо ключову фразу, в якій використані усі літери (так звану панграму).

Приклади панграм українською: - Гей, хлопці, не вспію - на ґанку ваша файна їжа знищується бурундучком. - Чуєш їх, доцю, га? Кумедна ж ти, прощайся без гольфів! - Жебракують філософи при ґанку церкви в Гадячі, ще й шатро їхнє п'яне знаємо. - Єхидна, ґава, їжак ще й шиплячі плазуни бігцем форсують Янцзи. - З'їв аґрусу -- та ягода цілюща б'є жах інфекцій шипучим „ь”. - Хвацький юшковар Філіп щодня на ґанку готує сім'ї вечерю з жаб. і т.д.

Тоді ключем є також і сама фраза. Так, викинувши «зайві» літери з панграми «Гей, хлопці, не вспію - на ґанку ваша файна їжа знищується бурундучком!» - отримаємо деяку послідовність літер «гейхлопцінвсюаґкуш фїжзищєтьсябрдчм», відмінну від алфавітної. Змінюючи величину зсуву, кожного разу отримаємо новий шифр, в якому символи замінюються неочевидним чином (звісно, доти, поки противнику невідома ключова фраза). Перебір усіх можливих варіантів ( 32³²) - проблема навіть для комп'ютера, перш за все - проблема часу. Тому варто скористатися більш ефективними методами аналізу.

За наявності досить великого уривку шифртексту непогані результати дає частотний аналіз, тобто визначення частоти застосування символів і порівняння з частотами літер того чи іншого алфавіту. Ці таблиці складаються на основі аналізу досить великих уривків випадкових текстів, краще - такої ж специфіки, що і шифроване повідомлення (якщо, звичайно, ми володіємо такою інформацією). Цей метод тим дієвіший, чим більше шифрованого тексту є в нашому розпорядженні. Наприклад, маємо криптограму:

Іпнабябтжи,нвкойуж,нкзйакнфжвднтйнубхж,

няж,нхжюнонфщгцщнвдуєнажхжабо,нінфжвднофяйойуйнябхж.

Лжнвжубяє?н-нрщтщнзбяйуб,нйущнінтщнзгб тйойуйфє.

нІнвкуйнрйужинчжгайн-нлжвнтщнзуйпйяє,нінфрдіуйфє.

Можемо пересвідчитись, що жоден зсув по алфавіту не дасть бажаного результату:

Ключ	Оброблене повідомлення	Ключ	Оброблене повідомлення
1	Їробвавузй,оглпкфз,	17	Чгбопнпєхщ,брювьжх,
2	Испвгбгфік,пдмрлхі,	18	Шдвпроржць,всягюзц,
3	Йтргдвдхїл,ренсмцї,	19	Щегрспсзчю,гтадяіч,
4	Кусдегецим,сєотнчи,	20	Ьєдстртішя,дубеаїш,
5	Лфтеєдєчйн,тжпуошй,	21	Южетусуїща,ефвєбищ,
6	Мхуєжежшко,узрфпщк,	22	зєуфтфиьб,єхгжвйь,
7	Нцфжзєзщлп,фісхрьл,	23	Аіжфхухйюв,жцдзгкю,
8	Очхзіжіьмр,хїтцсюм,	24	Бїзхцфцкяг,зчеідля,
9	Пшціїзїюнс,циучтян,	25	Виіцчхчлад,ішєїема,
10	Рщчїиіияот,чйфшуао,	26	Гйїчшцшмбе,їщжиєнб,
11	Сьшийїйапу,шкхщфбп,	27	Дкишщчщнвє,иьзйжов,
12	Тющйкикбрф,щлцьхвр,	28	Елйщьшьогж,йюікзпг,
13	Уяьклйлвсх,ьмчюцгс,	29	Ємкьющюпдз,кяїлірд,
14	Фаюлмкмгтц,юншячдт,	30	Жнлюяьяреі,лаимїсе,
15	Хбямнлндуч,яощашеу,	31	Зомяаюасєї,мбйнитє,
16	Цваномоефш,апьбщєф,	32	Іпнабябтжи,нвкойуж,

Тому вдамося до більш складних атак. Підрахуємо кількість та частоту літер у повідомленні (стовпчики 1 і 2, 5 і 6) та порівняємо з частотами літер у відкритому тексті (стовпчики 3 і 4, 7 і 8):

0,181	н		0,134	_		0,021	х		0,017	я
0,09	й		0,064	о		0,016	г		0,016	ь
0,08	ж		0,06	і		0,016	р		0,014	з
0,064	у		0,053	а		0,011	и		0,013	х
0,048	б		0,051	в		0,011	л		0,013	ч
0,037	в		0,05	н		0,011	п		0,008	г
0,037	ф		0,046	и		0,005	ц		0,008	ц
0,037	щ	0,044	т		0,005	ч		0,007	б
0,037	я		0,038	с		0,005	ю	0,007	ю
0,032	і		0,035	р		0,005	_		0,005	ї
0,032	о		0,03	к		0	е		0,005	й
0,032	т		0,029	л		0	ї		0,004	щ
0,027	а		0,028	е		0	м	0,003	ш
0,027	є		0,024	у		0	с		0,002	ж
0,021	д		0,02	м	0	ш	0,002	є
0,021	з		0,018	п		0	ь		0,002	ф
0,021	к		0,017	д

Повідомлення занадто коротке, щоб частоти співпадали точно, проте бачимо, що літера „н” в криптограмі зустрічається значно частіше, ніж будь-яка інша. Окрім того, вона стоїть після кожного розділового знаку. Це дає можливість припустити, що:

- „н” - це пробіл, „ ”;

- пунктуація в повідомленні збережена.

Заміняємо „н”:

іп абябтжи, вкойуж, кзйак фжвд тй убхж,

яж, хжю о фщгцщ вдує ажхжабо, і фжвд офяйойуй ябхж.

лж вжубяє? - рщтщ збяйуб, йущ і тщ згб_тйойуйфє.

і вкуй рйужи чжгай - лжв тщ зуйпйяє, і фрдіуйфє. (при цьому я залишила „_” на місці „ ” в криптограмі, аби зберегти різні символи. Далі будемо „відкриті” літери писати великими, щоб відрізняти їх від знаків криптограми.)

Бачимо кілька разів вживану окремо „і” - найімовірніші варіанти - слова а, і, в, я, з. Причому три останні - ймовірніші, тому що взагалі „і” зустрічається рідко, в складі інших слів - тільки два рази. Слово „іп” на початку означає, відповідно як, яр або ж зі, ви але тоді і або и =„п” і має частоту 0,011, що малоймовірно. Отже, припускаємо „і” =я:

Яп абябтжи, вкойуж, кзйак фжвд тй убхж,

яж, хжю о фщгцщ вдує ажхжабо, Я фжвд офяйойуй ябхж.

лж вжубяє? - рщтщ збяйуб, йущ Я тщ згб_тйойуйфє.

Я вкуй рйужи чжгай - лжв тщ зуйпйяє, Я фрдЯуйфє.

Бачимо слова „лж” в 3-му рядку та „лжв” - в четвертому. В криптограмі „ж” вживається часто, можливі варіанти „ж”= „а”, „о”, „і”. Тоді маємо пари слів: на - нам, та - там, так; що -щоб; ні - ніс і так далі. Зважаючи, що „ж” не зустрічається окремо, спробуємо „ж” = о; тоді „лж” - це що, „лжв”- щоб. Це не суперечить частоті знаків „л”, „в” в криптограмі.

Яп абябтОи, БкойуО, кзйак фОБд тй убхО,

яО, хОю о фщгцщ Бдує аОхОабо, Я фОБд офяйойуй ябхО.

ЩО БОубяє? - рщтщ збяйуб, йущ Я тщ згб_тйойуйфє.

Я Бкуй рйуОи чОгай - ЩОБ тщ зуйпйяє, Я фрдЯуйфє.

Бачимо двічі слово „фОБд” - варіанти: роби, собі. Останній ймовірніший, інакше отримаємо сумнівне „я роби” в другому рядку. Замінюємо „д”=і, „ф”=с:

Яп абябтОи, БкойуО, кзйак СОБІ тй убхО,

яО, хОю о Сщгцщ БІує аОхОабо, Я СОБІ оСяйойуй ябхО.

ЩО БОубяє? - рщтщ збяйуб, йущ Я тщ згб_тйойуйСє.

Я Бкуй рйуОи чОгай - ЩОБ тщ зуйпйяє, Я СрІЯуйСє.

Залишилась ще найчастіша літера в криптограмі - „й”. Малоймовірно, щоб вона була приголосною. Спробуємо „й”=а:

Яп абябтОи, БкоАуО, кзАак СОБІ тА убхО,

яО, хОю о Сщгцщ БІує аОхОабо, Я СОБІ оСяАоАуА ябхО.

ЩО БОубяє? - рщтщ збяАуб, Аущ Я тщ згб_тАоАуАСє.

Я БкуА рАуОи чОгаА - ЩОБ тщ зуАпАяє, Я СрІЯуАСє.

Далі, бачимо слово „тА” (отже, „т” - приголосна) та слова „тщ”, „рщтщ” в третьому рядку. „Щ” - досить часто вживана голосна, варіанти „е”, „и”, „у”. Тоді „Аущ” в третьому рядку, відповідно - але, аби, ану, агу. „Б” вже використана, якщо „у” =н, то в четвертому рядку маємо незрозуміле Б*НА, Б*ГА. Отже, перший варіант.

Яп абябтОи, БУоАЛО, УзАаУ СОБІ тА ЛбхО,

яО, хОю о СЕгцЕ БІЛє аОхОабо, Я СОБІ оСяАоАЛА ябхО.

ЩО БОЛбяє? - рЕтЕ збяАЛб, АЛЕ Я тЕ згб_тАоАЛАСє.

Я БУЛА рАЛОи чОгаА - ЩОБ тЕ зЛАпАяє, Я СрІЯЛАСє.

З отриманих уривків легко відновлюються: „о” - в, „т” - н, „р” - м, „є” - ь:

Яп абябНОи, БУВАЛО, УзАаУ СОБІ НА ЛбхО,

яО, хОю В СЕгцЕ БІЛЬ аОхОабВ, Я СОБІ ВСяАВАЛА ябхО.

ЩО БОЛбяЬ? - МЕНЕ збяАЛб, АЛЕ Я НЕ згб_НАВАЛАСЬ.

Я БУЛА МАЛОи чОгаА - ЩОБ НЕ зЛАпАяЬ, Я СМІЯЛАСЬ.

Завершуємо розшифрування криптограми:

ЯК ДИТИНОЮ, БУВАЛО, УПАДУ СОБІ НА ЛИХО,

ТО, ХОЧ В СЕРЦЕ БІЛЬ ДОХОДИВ, Я СОБІ ВСТАВАЛА ТИХО.

ЩО БОЛИТЬ? - МЕНЕ ПИТАЛИ, АЛЕ Я НЕ ПРИЗНАВАЛАСЬ.

Я БУЛА МАЛОЮ ГОРДА - ЩОБ НЕ ПЛАКАТЬ, Я СМІЯЛАСЬ.

Бачимо, що частота літер в тексті (надто - короткому уривку) може не співпадати з табличною. Дуже допомагає пунктуація , якщо розставлені проміжки між словами, то найкраще починати з коротких слів:

- на одну літеру - а, в, є, з, і, й, у, я;

- на дві - бо, ви, га, де, до, зі, їх, їм, її, ми, на, не, ні, ну, ой, по, те, ти, ті, це, ця, що, як, яр;

- на три (часто вживані) - або, але, вам, нам, ого, під, при, про, там, так, щоб; і так далі.

Розкриття хоч двох-трьох слів значно спрощує задачу - можна далі опиратися на відомі літери та контекст. Добре, якщо відома (хоч приблизно) тематика тексту - розшифрувавши, наприклад, «інтеграл», можемо шукати «експонента», «функція». тощо.

1.1.2 Програми до параграфа (редактор VВА)

Програма шифрування простою заміною-зсувом:

Private Sub Pr_zam()

Worksheets(4).Activate

Worksheets(4).Name = "Pr.Zam"

R = Worksheets(4).UsedRange.Rows.Count + 1//визначає номер 1-го

// незайнятого рядка на листі №4

Dim Mesg As Variant

Dim key As Variant

Dim Cryptg As Variant

Dim U_alf As Variant

Dim Len_mes As Integer

Dim Len_alf As Integer

U_alf = "абвгдеєжзіїийклмнопрстуфхцчшщьюя_ абвгдеєжзіїийклмнопрстуфхцчшщьюя_"

Mesg = InputBox("Введіть повідомлення") //приймає повідомлення

key = CInt(InputBox("Введіть ключ")) //та ключ

Len_mes = Len(Mesg)

Len_alf = Len(U_alf) / 2

Cryptg = Mesg

Dim k As Integer

For i = 1 To Len_alf

k = i + key

If k > Len_alf Then

k = k - Len_alf

End If

For j = 1 To Len_mes

If Mid(Mesg, j, 1) = Mid(U_alf, i, 1) Then

Mid(Cryptg, j, 1) = Mid(U_alf, k, 1) // замінює малу

Else

If Mid(Mesg, j, 1) = Mid(U_alf, i + Len_alf, 1) Then

Mid(Cryptg, j, 1) = Mid(U_alf, k + Len_alf, 1) // чи велику

End If // літеру повідомлення №і за

End If //алфавітом на №і+k за алфаітом

Next j

Next i

Cells(R, 1).Value = "Отримане повідомлення"

Cells(R + 1, 1).Value = "Ключ"

Cells(R + 2, 1).Value = "Шифроване повідомлення"

Cells(R, 2).Value = Mesg //записує повідомлення

Cells(R + 1, 2).Value = key //ключ

Cells(R + 2, 2).Value = Cryptg //та криптограму в діапазон

// В(R)-В(R+2)

Rahge(Cells(R, 1), Cells(R + 1, 2)).Hide //приховує повідомлення та //ключ

MsgBox ( "Обробленене повідомлення: " & Cryptg) //виводить зашифровне

//повідомлення

End Sub

Зауваженя 1. Ця ж програма може бути використана і для дешифрування повідомлення, якщо подати -k (mоd n) в якості ключа.

Зауваження 2. Якщо замість алфавіту ввести ключову фразу або набір деяких символів, отримаємо програму для шифрування неалфавітною заміною.

Програма, що зсуває шифртекст по алфавіту:

Private Sub Zam_vzl()

Worksheets(4).Activate

R = Worksheets(4).UsedRange.Rows.Count + 1

Dim Mesg As Variant

Dim Cryptg As Variant

Dim U_alf As Variant

Dim key As Integer

Dim k As Integer

Dim Len_mes As Integer

Dim Len_alf As Integer

U_alf = "абвгдеєжзіїийклмнопрстуфхцчшщьюя АБВГДЕЄЖЗІЇИЙКЛМНОПРСТУФХЦЧШЩЬЮЯ"

Mesg = InputBox("Введіть повідомлення") //приймає шифртекст

Len_mes = Len(Mesg)

Len_alf = Len(U_alf) / 2

Cells(R, 1).Value = "Отримане повідомлення"

Cells(R, 2).Value = Mesg

Cells(R + 1, 1).Value = "Ключ"

Cells(R + 1, 2).Value = "Оброблене повідомлення"

Cells(R + 1, 4).Value = "Ключ"

Cells(R + 1, 5).Value = "Оброблене повідомлення"

For key = 1 To Len_alf //перебирає ключі по алфавіту

Cryptg = Mesg

For i = 1 To Len_alf

k = i + key

If k > Len_alf Then

k = k - Len_alf

End If

For j = 1 To Len_mes

If Mid(Mesg, j, 1) = Mid(U_alf, i, 1) Then

Mid(Cryptg, j, 1) = Mid(U_alf, k, 1)

Else

If Mid(Mesg, j, 1) = Mid(U_alf, i + Len_alf, 1) Then

Mid(Cryptg, j, 1) = Mid(U_alf, k + Len_alf, 1)

End If

End If

Next j

Next i

If key < Len_alf / 2 + 1 Then //виводить таблицю

Cells(R + 1 + key, 1).Value = key //ключ

Cells(R + 1 + key, 2).Value = Cryptg //відповідне значення

Else //криптограми

Cells(R + 1 + key - Len_alf / 2, 4).Value = key //в два стовпці

Cells(R + 1 + key - Len_alf / 2, 5).Value = Cryptg

End If

Next key

End Sub

Програма для обчисленя частот літер (редактор VBA):

Private Sub TABLE()

Worksheets(2).Activate

Worksheets(2).Name = "TABLE"

Dim Mesg As Variant

Dim U_alf As Variant

Dim Len_mes As Integer

Dim Len_alf As Integer

U_alf = "абвгдеєжзіїийклмнопрстуфхцчшщьюя АБВГДЕЄЖЗІЇИЙКЛМНОПРСТУФХЦЧШЩЬЮЯ "

Mesg = Cells(37, 1).Value

Len_mes = Len(Mesg)

Len_alf = Len(U_alf) / 2

Dim k As Integer

Dim m As Integer

For i = 1 To Len_alf //для кожної літери алфавіту

k = 0 //підраховує кількість

For j = 1 To Len_mes

If Mid(Mesg, j, 1) = Mid(U_alf, i, 1) Then

k = k + 1

Else

If Mid(Mesg, j, 1) = Mid(U_alf, i + Len_alf, 1) Then

k = k + 1

End If

End If

Next j

Cells(i + 2, 1).Value = k / Len_mes //та обчислює частоту

Next i

For i = 1 To Len_alf //для кожної літери алфавіту

k = Cells(i + 2, 1).Value * Len_mes

For l = 1 To Len_alf

m = 0 //підраховує біграми

For j = 1 To Len_mes //з кожною літерою алфавіту

If Mid(Mesg, j, 2) = Mid(U_alf, i, 1) & Mid(U_alf, l, 1) Then

m = m + 1

End If

Next j

If k > 0 Then

Cells(i + 2, l + 3).Value = m / k //та обчислює частоту (або

Else //існування) біграм

Cells(i + 2, l + 3).Value = "X"

End If

Next l

Next i //виводить дані в таблицю

End Sub

1.1.3 Приклади і завдання до параграфа

1. Написати програму, що шифрує шифром заміни - зсуву або афінним. Передбачити можливість зміни ключа для кожного повідомлення, з її допомогою зашифрувати (розшифрувати) наступні фрази:

а)Життя_любить_того_хто_за_нього_бореться_а_нищить_того_хто_йому_піддається. Ключ: г

б)Била_жінка_чоловіка_пішла_позивати_присудили_чоловікові_ще_жінку_прохати. Ключ: т

в)Хщеемнцоюбгбеюунтямнйодемнонцотбрсунтямнеугвчаамн Ключ: н

г)Лгю_свшюрждщюпимрілмщючмювмбмоіючгрілмщ Ключ: ю

д)Яскїхс_їшиїяицщїсїхюуду_жїчицщ Ключ: ї

2. Написати програму що шифрує шифром заміни, замінюючи кожну літеру іншою (або деяким символом), обираючи її в неалфавітному порядку. З її допомогою зашифрувати (розшифрувати) наступні фрази. Порядок літер: гейхлопцінвсюакуш_фїжзищєтьсябрдчм.

а) Цілував_би_заєць_кобилу_та_високо Ключ: 3

б) Унадився_журавель_до_бабиних_конопель Ключ: 12

в) Трбаєіюлирєівслолігьіежуц Ключ: 25

г) Удкєйфрщьщябфпдопгфвнзфзщьщфикхійгф Ключ: 1

д) Яїабдєусуопцідоїабдиджиєущпдщуцуопцід Ключ: 14

3. Написати програму, що аналізує уривок шифрованого тексту, зсуваючи його по алфавіту. З її допомогою розшифрувати наступні повідомлення:

а) Єб, и жєгю щаїє - іацаїп ьтбмав. Іацаїп ієую, нч б дєзхтш, оч б еющвтда мчуазсш - ує фюе ьтбмав. (збережена пунктуація і проміжки між словами);

б)Їецічцьїйвцлчцецаяіпвцаімлуцчциїивюцьїйїфцхйїзцюїждіїфцєїбчєдцеюмлу. (пунктуація опущена, проміжки замінені символом).

4. Написати програму, що аналізує уривок шифрованого тексту, обчислюючи кількість повторень кожного символу, та повертає таблицю частот. З її допомогою розшифрувати наступні повідомлення:

а) Щ коаїя єїяпїз лбп - пмгбя вмцмєх гпбф кмугхцпо юо вілюо х єїьо внбеїпо. Х щ, вцїьбяопїз нопжбг уонхупїг, любф, о єонх - юїлщах юоьїи логїи, щь щ. Х ьбшпбгі абнб нхюо х шонр вбцїнї, х я ьбшпбдб я баои дбцїюр нфкбях шоц. Х внмах, щь бєїп, єбєбні ялх лиїнїнї, гбя єояїюр ялхи бєїп щьїзлр люцо'пїз ющдоц. (збережена пунктуація і проміжки між словами);

б) Ой 'гуг' єгмс: '-'г улйп - цал йусмл, фгмк ьгойп; дцфг 'кюкфг, мдуфг цусрг. Мп юляфж тдфік, мп 'гаїщрг, адфп тядояз тдєл алйп. Фг мдуфлш йусмл мдуфпш цсє, ой цдєупш адвф-аляудющє, актз чдтьгрюлюпш, дєрдулюпш, тядвяз фг йусмл чдякьфлюпш. Йдьс є тйг'гяп атк? Йдьс є? Мдьс х яг йусмг фгаптг? Мдьс юпи мкєку яг удтг юкхгяз фг тнпюл дцпфдйд, л тядаєсу, тчгюкфпш аптдйд, ой ькм, аалрфгато а фкєктг? . (збережена пунктуація і проміжки між словами);

в) Вйзфбнтшуфб-нтштзф,бїтмкф,бюцзф,бікчю_уупюбекфзф,бшціфзфбян_ияц.бнчуфбзти_зфбрйияч,бючнбшичбякцзф,бєфбут'бншз_мб-бші_нйл_хбіифдяц.бнштбчгцзч,бйштбєфечючу_зч,бєтзтуцобдйю,бнтштзфпбзйуф.бші_нфзчбншт,бшю_пзчшщб_бвкцу_зч,бфбпбзтгфзфбрнчкфбобшфючиуф. (пунктуація збережена, проміжки замінені символом);

г) Йд щрхво 'и йд ьзпдрх йд щрхво цфи чс ід рм еклмотх йжиш впдрх летх йжиш впдрх иім йжиє ипрм їмьюос йсїс рс їепс щхжйфх рх чмя щсльм мром гипдйдлейю ьзпд мром тигхйдлейю ьзпд пиїфм ьхктхжм я щьм кюинипрм екс пьш йсїс ищсфх нхє кйсцд м адйд кцмодйд йфсїх тигхйд кцмодйд йфсїх ньшпд а рс цфикцд їи йд рх щсльм ьзпдрх м гиісо йини ід рм еклмотх йжиш впдрх летх йжиш впдрх иім йжиє ипрм (пунктуація опущена, проміжки збережені);

д)Ьщїкїщйгзехйчхйіем_хйа'уллуйїайцйїщнщ_мйчщ'лмйшасаїмйфхйїайїмбйзйцмстйчйьаса'уллуйн_аехлзїкйеасагупйсуїмйлуйвйіафзйб_ушкй'скашхй'еувїх'кй'щ_щгйсхімй'нучмїхйну'луйощшйлмгупйїмбхй'нагучмїх'кйцхїхйіафзйьщїкйгзехй'зелуйвйлмйчоаьуей'зелуейнщ_щсашуйозгзй'увїкйом_чх'їуйбчуїбхйозгзй'увїкйбчуїбхйлмйеа_ашуйозгзйсхїкйлмйлхій'скашхйьу_буйуйчугй'сушйїхійьм_вфхій_ашїмлщйїмйба_мйскагачмвйеурлмйеацщйбчуїхйшуєгзїкй_йуйлм'їмлщйящйєйгсвйещлщйчщ'щсмйчщ'лм (пунктуація опущена, проміжки замінені символом).

1.2 Шифр перестановки

1.2.1 Опис та криптоаналіз

Шифр перестановки, або транспозиції, полягає в зміні порядку елементів відкритого тексту. Прикладами шифру перестановки є вже згадана вище „Сцитала” - тест писався на смужці пергаменту, намотаній на жезл-сциталу. Знятий, такий „лист” являв собою незрозумілу послідовність літер. Або, наприклад, „поворотна решітка” - вирізана з цупкого паперу так, щоб чотирма поворотами її відкриті комірки покривали всю площину листа. Текст записувався (і зчитувався) кожного разу тільки у відкриті комірки.

Математично шифр перестановки описується наступним чином. Нехай Х=х₁х₂х₃ …. х_nх_n+1х_n+2… - відкритий текст, S_n - шифр -перестановка. Тоді шифртекст має вигляд: f(Х)= х₍₁₎х₍₂₎ …. х_(n)х_n+(1) х_n+(2)….

На практиці це зручно робити з допомогою таблиці. Наприклад:

відкритий текст: НІЧ_ЯКА_МІСЯЧНА_ЗОРЯНА_ЯСНАЯ_Х

Н	І	Ч	_	Я
К	А	_	М	І
С	Я	Ч	Н	А
_	З	О	Р	Я
Н	А	_	Я	С
Н	А	Я	_	Х

після перестановки стовпців 34215: Ч_ІНЯ_МАКІЧНЯСАОРЗ_Я_ЯАНСЯ_АНХ

Це стовпцева перестановка. Тут символ Х в кінці додано для доведення кількості літер до числа, кратного кількості стовпців. У такому випадку можна застосовувати найпоширеніші або, навпаки, неймовірні сполучення, щоб ускладнити процесс розшифрування. Взагалі кажучи, для перестановки по 5 елементів існує усього лише 5!=120 варіантів ключа, тому можна обійтися і простим перебором- якщо ми певні, що використовувалась саме 5-перестановка. Інакше потрібно перебрати усі 2-, 3-, 4-. 5- і так далі перестановки. Більш ефективною є атака з використанням таблиці 1.2 частот біграм. (Нас буде цікавити не стільки частота, скільки можливість існування буквосполучення).

Наприклад: маємо шифртекст: НОІПВВОІЧ_ _ _АГЮЮЧКЕАА_ОСВ

Три проміжки підряд вказуть на те, що, швидше за все, була застосована перестановка. Взагалі можуть мати місце різні варіанти, для криптограми з 25 символів спробуємо спочатку найпростіший - перестановку з 5 елементів.

Для розшифровки записуємо знову в таблицю:

Н	О	І	П	В
В	О	І	Ч	_
_	_	А	Г	Ю
Ю	Ч	К	Е	А
А	_	О	С	В

та аналізуємо, користуючись таблицею частоти біграм. Причому легше спиратися не на найпоширеніші буквосполучення, а, навпаки, спочатку виключити неможливі поєднання. Почнемо з 4 та 3 рядків, оскільки вони містять більше «не популярних» літер. Таблиці ймовірного передування для них мають вигляд:

1	2
	Ю	Ч	К	Е	А
Ю	Х	Х	Х	Х	Х
Ч		Х
К	Х	Х	Х
Е				Х
А					Х

1	2
	_	_	А	Г	Ю
_	Х	Х
_	Х	Х
А			Х
Г				Х	Х
Ю			Х	Х	Х

Тут першою йде літера, що стоїть на початку рядка. Знак Х позначає неможливі сполучення. Разом - таблиця можливих передувань стовпців:

1	2
	1	2	3	4	5
1	Х	Х	Х	Х	Х
2	Х	Х
3	Х	Х	Х
4				Х	Х
5			Х	Х	Х

2	3	4	5	1
О	І	П	В	Н
О	І	Ч	_	В
_	А	Г	Ю	_
Ч	К	Е	А	Ю
_	О	С	В	А

Бачимо, що стовпець №1 не може передувати жодному стовпцю, отже, він - пятий.

Стовпцю №1 може передувати №4 або №5, але в першому випадку утворяться неможливі біграми ЧВ, ПН. Отже, на четвертому місці - №5. Стовпцю №5 може передувати №2 або №3, але якщо це №2, то в третьому рядку отримаємо слово _Ю_. Отже, на третьому місці - №3.

2	4	3	5	1
О	П	І	В	Н
О	Ч	І	_	В
_	Г	А	Ю	_
Ч	Е	К	А	Ю
_	С	О	В	А

Отримали осмислений текст: ОПІВНОЧІ_В_ГАЮ_ЧЕКАЮ_СОВА.

Підстановка, що використовувалась для шифрування - 51324.

Аналогічно розшифровується шифр стовпцевої та рядкової перестановки. За сумісністю літер відновлюємо порядок стовпців, за змістом - порядок рядків.

Слід зауважити, що застосувавши до тексту шифр простої заміни (після або перед перестановкою), ми одразу зробимо цей метод аналізу значно менш ефективним. Хіба що для відновлення можливого розташування пропусків, і то у припущенні, що вони були збережені при шифруванні. З іншого боку, переставлені символи не дадуть змоги відновити слова за контекстом та вже відкритими літерами. Тобто поєднанання двох навіть найпростіших методів шифрування значно підвищує стійкість шифру. Тому як ми побачимо далі, це широко застосовується в криптографічній практиці.

1.2.2 Програми до параграфа (редактор VBA)

Програма шифрування перестановкою:

Private Sub Perest()

Worksheets(1).Activate

Worksheets(1).Name = "Perest"

R = Worksheets(1).UsedRange.Rows.Count + 2

Dim Mesg As Variant

Dim TableM(5, 5) As Variant

Dim Cryptg As Variant

Dim Per_st(5) As Integer

Dim Per_rd(5) As Integer

Mesg = InputBox("Введіть повідомлення")

Cells(R + 1, 7).Value = Mesg

For i = 1 To 5 //вводить 5-перестановку

Per_st(i) = CInt(InputBox("Введіть елемент перестановки №" & i))

For j = 1 To 5

TableM(i, j) = Mid(Mesg, (i - 1) * 5 + j, 1)

Cells(R + i, j).Value = TableM(i, j) //записує текст в таблицю

Next j

Next i

For i = 1 To 5

Cells(R, 7 + i).Value = Per_st(i)

For j = 1 To 5

Cells(R + j, 7 + i).Value = TableM(j, Per_st(i)) //переставляє стовпці

Next j

Next i

For i = 1 To 5

Cells(R + i, 14).Value = Per_st(i)

For j = 1 To 5 //переставляє рядки

Cells(R + i, 14 + j).Value = Cells(R + Per_st(i), 7 + j).Value/

Next j

Next i

Cryptg = Mesg

For i = 1 To 5

For j = 1 To 5 //записує текст в рядок

Mid(Cryptg, (i - 1) * 5 + j, 1) = Cells(R + i, 14 + j).Value

Next j

Next i

Cells(R + 2, 7).Value = Cryptg //повертає криптограму

End Sub

Програма, що повертає таблицю сумісності літер в рядку:

Private Sub Tabl_bigr()

Worksheets(1).Activate

R = Worksheets(1).UsedRange.Rows.Count + 2

Dim Mesg As Variant

Dim TableM(5, 5) As Variant

Dim U_alf As Variant

Dim Stovp As Variant

Dim Num_lit(5) As Integer

Dim Len_alf As Integer

Mesg = InputBox("Введіть повідомлення:")

Cells(R + 1, 7).Value = Mesg

U_alf = "АБВГДЕЄЖЗІЇИЙКЛМНОПРСТУФХЦЧШЩЬЮЯ_"

Len_alf = Len(U_alf)

For i = 1 To 5

For j = 1 To 5

TableM(i, j) = "-" //попередньо заповнює таблицю ”-”

Cells(R + i, j).Value = Mid(Mesg, 5 * (i - 1) + j, 1)

Next j

Next i

Dim k As Integer

For k = 1 To 5 //обирає рядок в таблиці

Row = Mid(Mesg, 5 * (k - 1) + 1, 1) & Mid(Mesg, 5 * (k - 1) + 2, 1) & Mid(Mesg, 5 * (k - 1) + 3, 1) & Mid(Mesg, 5 * (k - 1) + 4, 1) & Mid(Mesg, 5 * k, 1)

For i = 1 To 5

For j = 1 To Len_alf

If Mid(Row, i, 1) = Mid(U_alf, j, 1) Then

Num_lit(i) = j //визначає місце літери в алфавіті

End If

Next j

Next i

Worksheets(2).Activate

For i = 1 To 5 //перевіряє, чи зустрічається таке

For j = 1 To 5 //поєднання літер

If Cells(Num_lit(i) + 2, Num_lit(j) + 3).Value = 0 Then

TableM(i, j) = "X" //якщо ні, то вставляє „Х”

End If

Next j

Next i

Next k

Worksheets(1).Activate

For i = 1 To 5

For j = 1 To 5 //виводить таблицю

Cells(R + 1 + j, 7 + i).Value = TableM(i, j)

Next j

Next i

End Sub

1.2.3 Завдання до параграфа

1. Написати програму шифрування перестановкою. Передбачити можливість зміни ключа (перестановки) для кожного повідомлення. З її допомогою зашифрувати:

а) БАЧИЛИ_ОЧІ_ЩО_КУПУВАЛИ_ЇЖТЕ перестановка 21453 - тільки стовпці;

б) ІЛКУКОВ_СЄЛО_БОХ_ТОВТИАЛЬ перестановка для розшифруваня 34215 - тільки стовпці;

в) НЕ_ВСЕ_Ж_КІШЦІ_МАСЛЕНИЦЯ_ перестановка 14253 - стовпці і рядки;

г) _ОТІ_А_МД__ЕНІБГМА_ЕМН_АС перестановка для розшифрування: 54132 - стовпці і рядки;

д) МТРІОЗЯК__О_САЬВОДХИВИММ_ перестановка 42351 - стовпці і рядки.

2. Написати програму, яка за таблицею біграм повертає таблицю сумісності літер. З її допомогою розшифрувати текст, зашифрований шифром перестановки: кодування криптоаналіз шифр ключ

а) ЕРТЩ_ТП_ЕІВ_ІІНЕПСН_ВИЛІА;

б) ЬКИТНОЕ_НКІЮ_ВКУШ_ККЗУРИУ;

в)Т_ХНОЛВА_ИОИВ_Д_ОВРГЛУІ_К;

г) ЛБХІ_ІЬСЛ_ЖАЇ__РВПАД_ІУРЖ;

д) ЇОА_НЕР_ЧГ_МСМІНВВИОІКІВШ

е) ЛМ_ААГБАІЛАВОПЛИ__МШЦЯ_ЙЕ

є) _АЛИЄДЗУБ_ЯС_ЯТНСЯ_ЕПААД_

1.3 Багатоалфавітні шифри

1.3.1 Шифр Віженера

В п. 1.1. ми познайомились з шифром простої (одноалфавітної) заміни і побачили, що він досить просто розкривається через порівняння частот літер шифр- та відкритого текстів. Аби ускладнити цю задачу, застосовуються шифри багатоалфавітної заміни, коли одна й та сама літера може замінятися різними - в залежності від свого положення в тексті. Класичним прикладом є шифр Віженера. Математично він може бути описаний так:

y_i= x_i + k_j (mod n), i=1,p;

j=i (mod m).

Тут, як і в п. 1.1., x_i - символ відкритого, y_i - шифрованого тексту, n - кількість літер в алфавіті, p - довжина повідомлення; k_j - символ ключа, m - довжина ключа.

Шифрування відбувається наступним чином: під відкритим текстом підписують ключове слово або фразу, і замінюють кожну літеру, зсуваючи її по алфавіту на кількість позицій, визначену номером ключової букви. Наприклад, зашифруємо текст „В_сутінках всі_кішки_сірі” з ключем „шмат”:

Записуємо в таблицю алфавітні заміни-підстановки, визначені літерами ключа, на зразок „й”-підстановки, наведеної в п.1.1. Літеру відкритого тексту знаходимо в 1-му рядку замінюємо на літеру з підстановки 1-шої букви ключа, наступну - 2-гої, потім 3-тьої, 4-тої і знову 1-шої, і так далі. Тобто тут маємо справу не з одним шифром заміни, а 4 одночасно. Отримана криптограма: „Юмтинцовщжахмцавдїлашгїзд”

1.3.2 Криптоаналіз шифру Віженера

Хоча шифр Віженера складніший за просту заміну, за наявності досить великого уривку тексту він також піддається криптоаналізу. Якщо є припущення, що використано саме шифр Віженера (це визначається шляхом статистичного аналізу текста), то для розкриття шифру перш за все потрібно визначити довжину ключового слова. Для цього скористаємося тестом Казіски - його ідея полягає в тому, що однакові уривки тексту, потрапивши на ту саму частину ключа, дадуть однакові елементи в криптограмі. Ймовірність появи схожих елементів випадково досить мала, тому можемо припустити, що довжина ключа m є найбільший спільний дільник відстаней між ними. Для уточнення значення m скористаємось індексом співпадіння - ймовірністю того, що в рядку осмисленого тексту 2 навманя вибрані літери співпадають. Ця величина була введена Фрідманом в 1920р.

Теорема 1.3.1. Для алфавіта Х={х₁, х₂,… х_n} індекс співпадіння обчислюється за формулою

(1.3.1)

де р_і - ймовірність появи літери х_і в осмисленому тексті.

Маючи певне припущення щодо довжини ключа, розписуємо текст на відповідну кількість стовпців, та визначаємо частоту літер у кожному з них. Якщо m підібране правильно, то частоти літер, а, отже, і І_С, співпадатимуть з частотами літер і індексом відкритого тексту. Для текстів українською

І_С ?0,052.

Інакше - І_С наближатиметься до індексу співпадіння для випадкового набору букв, для української мови ?0,03.

Далі, визначивши точну довжину ключа, спробуємо його підібрати. Для цього для пар стовпців (1,2), (1,3), (1,4) і т.д. обчислюємо індекс взаємної сумісності МІ (У¹,У²) - ймовірність співпадіння пари навманя вибраних літер в рядках тексту У¹,У². Якщо У¹,У² написані одним алфавітом Х, то величина МІ (У¹,У²) ? І_С для звязних текстів, інакше - прямує до випадкового значення І_С?0,03.

Теорема 1.3.2. Для рядків У¹,У² алфавіта Х={х₁, х₂,… х_n} взаємний індекс співпадіння обчислюється за формулою

(1.3.2)

де р_і¹, р_і² - ймовірність появи літери х_і в осмисленому тексті у відповідному рядку.

Тобто, орієнтуючись на найбільші (або, навпаки, найменші) частоти застосованих літер, намагаємося «зсунуи» підстановку одного рядка відносно іншого так, щоб взаємний індекс співпадіння ? 0,052. Після цього залишається тільки визначити зсув 1-го стовпця відносно алфавіту.

Зауваження. Цей же спосіб придатний і для одноалфавітної підстановки - з допомогою І_С впевнюємося, що застосована одноалфавітна підстановка, з допомогою МІ обчислюємо величину зсуву.

Для ефективності вказаного методу аналізу бажано мати досить довгий уривок шифртексту, аби частоти літер в ньому наближались до статистичних.

Наприклад, маємо криптограму:

лцоусж_нтвяєснїьїхєтізце_мігюфіусбіібгоисрмтбсоетвшбсрмтбсоетвгищгічїюїтісії_шмтгсьшсфхяьвщгпеїї_вйтдзстхурксхзьблутдзідеїчусйім_піьчвгагвйасд_ччхмтбгьуілідеііігцяечвпук_фєфгчшсжтїрвгасїіх_єїчтіііїжіяспїцюфязтхттзхьумррнївфужціеюїіїтнмтщляїрвйасєьугсяеювйасичушхмтвгяадціютвфзенічевюдчуяястмзчжіхюьчагвюеепієцршцевщзью_тївцєпвлаілчисрмтбллуахмтзошхтпттрніфтєчєгвщз_хтквлігпжттьррї_отірвюхюжфасфхпеитетвиг_фхусцісбссіовяяінттфйлїтніищзіечвюїтехшдлутдйфагвщз_мчсфвщз_фзцївдаулхазхісблцтцгьиахмтрвчшьетмбгіжжсцєфозї_вбєіййтзнїютхттжйгтюямтігфиспїзїфжтьрїрсямтюиіечпшхвбяасйіцжлвссичупвешсціієсйаін_теріїтпіі_жтїовяусдрчдгімїуї_йгім_вчусф_чювиивгіхерїтбсхастьєьвскдйутцерзсхшчювзтзгцшскбуфвфєвліцжлвпбгіетввх_ряужвщєфзпг_вгасуйувгідтхттігфтдгііедртбсюасбфтьглюфсчавліжевуєхсічїюртігіхюріьчвсбсбфтжйле_міі_ріясжшіюв_тдлбтювйажйютігцтдгінєсьамйіхерїтщвюхеаіч_хтеївкєццйувгіїтвйьчвутзцюяцфєвївиуфлхусь_ьївиєуумеллбусїії_пімтфшдсешрфгхусиїтбцьвївпусхмг_щжтьгідчї_тффмтднфєвліїевйтдлбтювщєфзхєзб:тз_шцежчясфтї_міфев_меуїтяеіїевяшсжтїрвутдгіееєттьйщ'рошірвртжспигцічюмдгев_тлцьуяеівеоттщв_тхутлрвйаулхєз_іете_ізбіясь_зткйетвюїтоїтдгіжеуртісіжеожф_оїіовбгетвшфйідту_ірвцєхоттувхамзізтжрї_вцуізьясешеевчусхмтавпуйславсюпсфщєлгявївкз_щєвевщямсйтілцтлгюєгв_тєсбяцвщєєйлзефяувліхчуиасйічюегуінїтєушткзіхсф_чювцєщотхевитювчшсфхяцвїгчвотггьизбіїтнібеєштлзфувгіїтнртвйяусслетвщшжзиивгіеюншдївчясу_в_вчшсюхруцйувгіудйіетвфєхсібссфєгвчшсемгтвкз_щєвевотфйчтгйьсфвчшсхрщпвцяжншрсеіь_хяясю_втеічеушцївчшстьсгціхюріетушч_еюсстрчсхївеаіююуфєпвеєсяшіовйтццдясжйєяошірвуєгціхюжіїеєштбллуффєтузьшхгічевяєхсігпдтхсжшіігяєбвртваиафвщязррткзісбвювтїрдевйяжцйуіліхсдшцтвртєушчтеїї_влимціітхїею

Аналізуючи з допомогою програми, бачимо:

уривок	мтб	тбс	етв	мтб	тбс	етв	ї_в	вйа
кількість	4	4	8	4	4	8	4	5
уривок	іїт	їтн	іхю	вщз	іхю	вщз	влі	ірв
кількість	5	4	4	4	4	4	5	4
довж повід	1661	уривок	етв	3
місця	48	60	400	700	1112	1144	1356	1400

найчастіше (8 разів) зустрічається уривок „етв” - на 48, 60, 400, 700, 1112, 1144, 1356 і 1400 позиціях. Найбільший спільний дільник - 4, швидше за все, ключове слово містить 4 літери. Розписуємо шифртекст на 4 стовпці:

л	ц	о	у
с	ж	_	н
т	в	я	є
с	н	ї	ь
ї	х	є	т
і	з	ц	е

і т.д. Отримаємо 4 уривки, кожен з яких зашифровано відповідною підстановкою:

1)лстсїі_юсбсбтсбтщїі_гсьп_дхсбдес_чгсчбіегчкфсрс_тїсютзмїжютщрсгюсшвдтеечсчюгецеьїпісбазтртг_впь_рюсет_сбоіфтщчтддг_ф_їузбцарьбжф_ізтжюісїьсючвсжспсєіет_осдїй_сювебсьдцсюзсфвжбт_жф_свтідебсьфвехїіючсж__сюдюжідємеще_їцвтчзцїфсїулс_тсфсбїс_ьчфдведюфззес_ееяесрдеьрржгюеляещхрузтзстттдеіе_оефтрхумт_ісесайвслї_емілгєцєевчсюієксющеюсцчгзтелвтвстжвюїс_сувдтхсгст_ефгфспжс_стеїсгют_ссеюпсоцсяргюебфухехпсібвфзкбтежістєт_мт; 2)цжвнхзмфбгрсврсвгюсшсфвевзухлзїйпввдхгліцв_гжвїєіжпфххрвцїнлвєсвихгцвнвутжьвпрвюввлрлхопнєвхлжровжфивфцсвнйнзвелйвмвфвлхлгхвегсовйнхйягпфряипбйливцснрпжвдгугвфвгрствйехвгквллгврвзвугхггдсбгслвсюгрвбймржвлвйггсйрвахвцгввцфвльвулїпфегицвхщгїфнлвлвзб_жфмвуевжвгєйовсцмвцеовувл_ебьквогусоовтйувовзжвзевхвссфгвщвслгвсвйфлуйенузфвоввфввгбнєзгнйсвзгнвувюцгйвссвевщвййвхвнехюеувтцруетхаувявцжовцжєлфзгвсджгваврзвївцлдвуевцх;

3)о_яїєціііомошмогіїімьхщїйсрзуічіігй_мьііяпфчтгіїііїятьрфіімяйьяйчмяіфіюямічюішщ_цлчмлмштічщтітртюфхтихісятлііюхуфщчщздхіцьмчтіцзбйїтгмфїжїмішяівчеій_іітяріїіч_иіїхьсуршзцбфівівящпгйітфірюфлчіуіріісфлііш_бйюціьіїюіткйійуюєих_имбіішшхїьпмжі_мфійбщх:шчті_їіятуітщшрпід_ьіт_тйхі_і_йюїіріжїбві_цтхірцьшчмплющякєщйцю_бщляіиігїші_цтичхїоьіішфірялщиішч_чхйііфіфчмкєочьчрцшія_ішчьіішюрїіфешйдйшуіішлєьіяітшярищріюрййішршїлії;

4)унєьтегуіитебтеичтїтшягїтткьтдумьаачтудіеуєшїахчіяцзтунуеїтїауеаутаюзчдязхаеєцзтєаитутхтфєзкгтїіхапегусіятїиеїштазсзцааститшмжєїєтютттизтртехацсушіатїіїучм_мучихтаєктзчтшуєцпехуєгаудттітатюажєчтхьбтеіяіттаттнахтхчеєуїьтявууьєеуїмдрутвугтдттєїттєєтцяїфмтїшїтет'ітичгтувттлаєеіязеїтжтжфігшдієтазїуяеутуапєвзвяттєтяєзухачуттхчєхтшягтиїбтуїтуешиедявшрууеєбєшгзвттсшщярьявчцшсхечсчвюєєітяєієхїтутшчєгхієтаятсвдяухцтчїиіе.

Для кожного окремо проведемо частотний аналіз:

частина 1	частина 2	частина 3	частина 4
частота	літера	частота	літера	частота	літера	частота	літера
0,0072	а	0,0072	а	0,0000	а	0,0602	а
0,0386	б	0,0169	б	0,0169	б	0,0096	б
0,0386	в	0,2265	в	0,0096	в	0,0241	в
0,0337	г	0,0795	г	0,0145	г	0,0265	г
0,0361	д	0,0120	д	0,0072	д	0,0217	д
0,0843	е	0,0361	е	0,0048	е	0,0554	е
0,0145	є	0,0145	є	0,0120	є	0,0723	є
0,0289	ж	0,0337	ж	0,0072	ж	0,0096	ж
0,0289	з	0,0313	з	0,0096	з	0,0337	з
0,0410	і	0,0048	і	0,2048	і	0,0434	і
0,0386	ї	0,0145	ї	0,0482	ї	0,0554	ї
0,0000	и	0,0120	и	0,0193	и	0,0265	и
0,0048	й	0,0434	й	0,0458	й	0,0000	й
0,0072	к	0,0048	к	0,0072	к	0,0072	к
0,0145	л	0,0554	л	0,0241	л	0,0024	л
0,0120	м	0,0120	м	0,0410	м	0,0145	м
0,0000	н	0,0313	н	0,0000	н	0,0072	н
0,0096	о	0,0265	о	0,0145	о	0,0000	о
0,0169	п	0,0193	п	0,0120	п	0,0072	п
0,0265	р	0,0361	р	0,0410	р	0,0096	р
0,1470	с	0,0554	с	0,0096	с	0,0193	с
0,0843	т	0,0120	т	0,0506	т	0,1880	т
0,0145	у	0,0386	у	0,0169	у	0,0843	у
0,0386	ф	0,0410	ф	0,0361	ф	0,0072	ф
0,0169	х	0,0482	х	0,0313	х	0,0410	х
0,0193	ц	0,0410	ц	0,0265	ц	0,0193	ц
0,0289	ч	0,0000	ч	0,0482	ч	0,0410	ч
0,0024	ш	0,0024	ш	0,0554	ш	0,0361	ш
0,0145	щ	0,0072	щ	0,0313	щ	0,0024	щ
0,0193	ь	0,0072	ь	0,0337	ь	0,0169	ь
0,0530	ю	0,0120	ю	0,0313	ю	0,0096	ю
0,0072	я	0,0072	я	0,0434	я	0,0434	я
0,0000	_	0,0000	_	0,0000	_	0,0000	_

Обчислюємо І_С¹=0,055, І_С²=0,081, І_С³=0,068, І_С⁴=0,071 - довжина ключа підібрана вірно. Індекси взаємного співпадіння

МІ(1,2)=0,025, МІ(1,3)=0,029, МІ(1,4)=0,039

вказують на наявність зсуву алфавітних підстановок відносно одна одної. Бачимо, що в першій колонці значно більшу частоту, ніж інші, має „с”, в 2-гій - „в”, в 3-тій - „і”, в 4-тій - „т”. Сумістимо ці літери в таблиці:

частина 1	частина 2	частина 3	частина 4
частота	літера	частота	літера	частота	літера	частота	літера
0,0072	а	0,0120	м	0,0169	у	0,0096	б
0,0386	б	0,0313	н	0,0361	ф	0,0241	в
0,0386	в	0,0265	о	0,0313	х	0,0265	г
0,0337	г	0,0193	п	0,0265	ц	0,0217	д
0,0361	д	0,0361	р	0,0482	ч	0,0554	е
0,0843	е	0,0554	с	0,0554	ш	0,0723	є
0,0145	є	0,0120	т	0,0313	щ	0,0096	ж
0,0289	ж	0,0386	у	0,0337	ь	0,0337	з
0,0289	з	0,0410	ф	0,0313	ю	0,0434	і
0,0410	і	0,0482	х	0,0434	я	0,0554	ї
0,0386	ї	0,0410	ц	0,0000	_	0,0265	и
0,0000	и	0,0000	ч	0,0000	а	0,0000	й
0,0048	й	0,0024	ш	0,0169	б	0,0072	к
0,0072	к	0,0072	щ	0,0096	в	0,0024	л
0,0145	л	0,0072	ь	0,0145	г	0,0145	м
0,0120	м	0,0120	ю	0,0072	д	0,0072	н
0,0000	н	0,0072	я	0,0048	е	0,0000	о
0,0096	о	0,0000	_	0,0120	є	0,0072	п
0,0169	п	0,0072	а	0,0072	ж	0,0096	р
0,0265	р	0,0169	б	0,0096	з	0,0193	с
0,1470	с	0,2265	в	0,2048	і	0,1880	т
0,0843	т	0,0795	г	0,0482	ї	0,0843	у
0,0145	у	0,0120	д	0,0193	и	0,0072	ф
0,0386	ф	0,0361	е	0,0458	й	0,0410	х
0,0169	х	0,0145	є	0,0072	к	0,0193	ц
0,0193	ц	0,0337	ж	0,0241	л	0,0410	ч
0,0289	ч	0,0313	з	0,0410	м	0,0361	ш
0,0024	ш	0,0048	і	0,0000	н	0,0024	щ
0,0145	щ	0,0145	ї	0,0145	о	0,0169	ь
0,0193	ь	0,0120	и	0,0120	п	0,0096	ю
0,0530	ю	0,0434	й	0,0410	р	0,0434	я
0,0072	я	0,0048	к	0,0096	с	0,0000	_
0,0000	_	0,0554	л	0,0506	т	0,0602	а

За індексами взаємного співпадіння (індекси вгорі позначають величину зсуву):

МІ(1,2^-18)=0,062, МІ(1,3 ^-11)=0,056, МІ(1,4¹)=0,059

- бачимо, що зсув стовпців відносно 1-го підібрано вірно. Тоді набір літер в кожному рядку може бути ключовим; припускаючи, що ключем було осмислене слово, обираємо «світ» в 21-му рядку. Величина

МІ(алф,1^-21)=0,05

Діємо тепер навпаки: у відповідному рядку знаходимо літеру криптограми і записуємо ту, що стоїть напроти у першому рядку.

Отримали зв'язний текст - припущення вірне. Закінчуємо розшифрування:

чужа_душа_то_кажуть_темний_ліс_а_я_скажу_не_кожна_ой_не_кожна_чужа_душа_то_тихе_море_сліз_плювати_в_неї_гріх_тяжкий_не_можна_і_чим_же_чим_ви_будете_карати_моє_смутне_зацьковане_дитя_чи_ж_вигадає_суд_і_магістрати_страшнішу_кару_ніж_таке_життя_ви_грамотні_ви_знаєте_латину_за_крок_до_смерті_перед_вічним_сном_одного_прьшу_у_мою_дитину_не_кидайте_словами_як_багном_притихли_люди_знітилися_свідки_сльозина_блисла_у_якоїсь_тітки_відтак_уже_не_ставлений_ніким_прийняв_присягу_шибилист_яким_даруйте_я_незвичка_промовляти_хотів_сказати_річ_іще_таку_марусю_знаю_ще_із_немовляти_і_гриця_знаю_ще_у_сповитку_он_там_сидить_та_бідна_чураїха_чи_на_суді_була_вона_коли_проз_їхній_двір_тоді_я_саме_їхав_коли_грицька_на_цвинтар_повезли_чи_рвала_мати_так_на_собі_коси_як_задзвонили_по_його_душі_та_він_же_їй_як_рідний_син_і_досі_у_них_і_виріс_там_на_шпориші_вона_ж_свою_дитину_годувала_та_вже_й_сусідську_бавила_чужу_бобренчиха_ж_тим_часом_воювала_за_курку_за_телицю_за_межу_все_ннколи_то_в_них_і_повелося:_сьогодні_ситий_бо_учора_їв_то_те_дитя_й_на_ноги_зіп'ялося_і_розуму_дійшло_у_чураїв_коли_ж_у_гриця_вибилось_навусся_і_чураївна_стала_на_порі_то_полюбилась_хлопцеві_маруся_могли_б_лише_радіти_матері_воно_на_те_й_заходилось_спочатку_грицько_пішов_тим_часом_у_похід_попідростали_верби_і_дівчатка_про_це_в_суді_можливо_б_і_не_слід_але_ж_маруся_так_його_чекала_такі_літа_одна_перебула_нікому_ні_руки_не_шлюбувала_ані_на_кого_й_оком_не_вела_грицько_ж_він_міряв_не_тією_міркою_в_житті_шукав_дорогу_не_пряму_він_народився_під_такою_зіркою_що_щось_в_душі_двоїлося_йому_від_того_кидавсь_берега_до_того_любив_достаток_і_любив_пісні_це_як_скажімо_вірувати_в_бога_і_продавати_душу_сатані (Л.Костенко)

Стійкість шифру Віженера, як шифра простої заміни, можна підвищити, перемішавши літери перед шифруванням, тобто використовувати підстановки з неалфавітним порядоком літер. Тоді, навіть підібравши ключове слово, противник не прочитає криптограму, не знаючи застосованої підстановки; розкрити шифр можна тільки повністю завершивши частотний аналіз. Проте за наявності досить великого уривка тексту це можливо.

1.3.3 Шифр Вернама та інші

Криптоаналіз шифру Віженера грунтується на періодичності застосованого ключа. Аби ліквідувати цей недолік, Віженер запропонував використовувати ключове слово лише 1 раз, а далі в якості ключа брати сам текст повідомлення.

Проте можливість для статистичного аналізу залишається і тут. Так як частоти літер в відкритому тексті і ключовому рядку однакові, то літера, наприклад, «а», зашифрована за допомогою «б», буде зустрічатися в криптограмі з частотою, рівною добутку частот а і б.

Отже, потрібно обирати ключ, що за своїми статистичними показниками відрізняється від відкритого тексту. Таку схему шифрування запропонував в 1918р. Г.Вернам. Його система шифрування обробляла літери, а двійкові символи, отримуючи криптограму шляхом операції ХОR (побітового додавання за mоd 2) відкритого «тексту» і ключа. Розшифрування відбувалося так само. Проте використаний ключ був хоча і довгий, але все ж періодичний, тому полишав можливості для аналізу.