12. Розділ 5. Криптолінґвістика (2012 р.)

Розділ 5. Криптолінґвістика

План викладення матеріалу

1. Основні визначення криптолінґвістики
2. Лінґвістичні схеми у криптографії
   1. Кодування інформації
   2. Моноалфавітні шифри
   3. Застосування перестановок
   4. Поліалфавітні шифри
   5. Книжкові шифри
   6. Дволітерні шифри
3. Основи криптоаналізу. Лінґвістичне дешифрування
   1. Розкриття шифру Цезара
   2. Розкриття шифру заміни
   3. Розкриття книжкового шифру
   4. Розкриття шифру Віженера
4. Контрольні питання
5. Задачі для самостійної роботи

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

Вивчення методів криптолінґвістики ґрунтується на моделях та методах комбінаторики, теорії ймовірностей, математичної статистики і теорії інформації. У загальній схемі квантитативної лінґвістики зв’язки між методами розділів математики та розділами квантитативної лінґвістики відображені на рис. 5.1.

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

1. 5.1.Основні визначення криптолінґвістики

Якщо ви хочете передати своє текстове повідомлення (послідовність символів деякого алфавіту) адресата так, щоб воно залишилося таємним для сторонніх осіб, то у вас є, принаймні, дві можливості. Ви можете спробувати приховати сам факт передачі тексту, тобто вдатися до методів стеганографії, в арсеналі якої – симпатичне (невидиме) чорнило, мікрокрапки і тому подібні засоби. Інша можливість полягає в спробі приховати зміст повідомлення від сторонніх осіб, випадково або навмисно познайомилися з переданим текстом. В цьому випадку ви можете вдатися до методів криптографії. Термін «криптографія» походить від двох грецьких слів: «криптос» – таємниця і «графейн» – писати, і означає тайнопис. «Тайнопис» якраз і має на увазі, що ви приховуєте зміст свого повідомлення. Повідомлення, яке ви хочете передати адресатові, називатимемо відкритим повідомленням. Для збереження повідомлення в таємниці воно перетвориться криптографічними методами і лише після цього передається адресатові. Перетворене повідомлення називатимемо шифрованим повідомленням. Інша назва шифрованого повідомлення – криптограма (або шифротекст). Уведемо такі означення (табл. 5.1) [6, 108, 1304, с.4].

Таблиця 5.1

Основні означення криптолінґвістики

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

Для зручності подальшого викладу позначимо буквою A – відкрите повідомлення, B – шифроване повідомлення, f – правило шифрування, g – правило розшифрування. В цьому випадку шифрування відкритого повідомлення A в шифроване повідомлення B можна записати у вигляді f(A)= B. Зворотне перетворення (тобто здобуття відкритого повідомлення A шляхом розшифрування B) запишеться у вигляді співвідношення g(B)= A [140].Правило шифрування f не може бути довільним. Воно має бути таким, аби за шифротекстом B за допомогою правила розшифрування g можна було однозначно відновити відкрите повідомлення A. Однотипні правила шифрування можна об’єднати в класи. Усередині класу правила розрізняються між собою за значеннями деякого ключа, який може бути числом, таблицею і так далі.Є принаймні дві обставини, які дозволяють зрозуміти необхідність запровадження поняття ключа. По-перше, звичайне шифрування проводиться з використанням спеціальних пристроїв. У вас має бути можливість змінювати значення параметрів пристрою, аби шифроване повідомлення не змогли розшифрувати навіть особи, що мають такий самий пристрій та не знають вибраного вами значення параметра. По-друге, багаторазове використання одного і того ж правила шифрування fдля шифрування відкритих текстів створює передумови для отримання відкритих повідомлень по шифрованих без знання правил розшифрування g. Тому необхідно своєчасно замінювати правило шифрування.

Використовуючи поняття ключа, процес шифрування можна описати у вигляді співвідношення f_a(A)= B, у якому a – обраний ключ, відомий відправникові та адресатові. Для кожного ключа a шифроперетворення f_a має бути зворотним, тобто повинне існувати зворотне перетворення , яке при обраному ключі a однозначно визначає відкрите повідомлення A за шифрованим повідомленням B, тобто g_a(B)= A. Сукупність перетворень f_a і набір ключів, яким вони відповідають, і називають шифром [140].

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

Часом змішують два поняття: шифрування і кодування. Ми вже домовилися, що для шифрування треба знати шифр і секретний ключ. При кодуванні немає нічого секретного, є лише певна заміна літер або слів на заздалегідь визначені символи. Методи кодування направлені не на те, аби приховати відкрите повідомлення, а на те, аби подати його в зручнішому вигляді для передачі по технічних засобах зв'язку, для зменшення довжини повідомлення тощо. В принципі, кодування, звичайно ж, можна розглядати як шифр заміни, для якого «набір» можливих ключів складається лише з одного ключа (наприклад, буква «а» в абетці Морзе завжди кодується знаками ●▬ і це не є секретом).

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

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

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

1. 5.2.Лінґвістичні схеми у криптографії

Криптографія (від грецького kryptós – прихований і gráphein – писати) – наука про методи забезпечення конфіденційності (неможливості прочитання інформації стороннім) і автентичності (цілісності і справжності авторства) інформації. Розвинулася через практичну потребу передавати важливі відомості найнадійнішим чином [114]. Донедавна криптографія займалася виключно забезпеченням конфіденційності повідомлень (тобто шифруванням) – перетворенням повідомлень зі зрозумілої форми в незрозумілу і зворотнім відновленням на стороні одержувача, забезпечуючи неможливість прочитання для того, хто перехопив або підслухав без секретного знання (а саме ключа, необхідного для розшифрування повідомлення). Упродовж останніх десятиліть сфера застосування криптографії розширилася і включає не лише таємне передавання повідомлень, але й методи перевірки цілісності повідомлень, ідентифікування відправника/одержувача (автентифікація), цифрові підписи, інтерактивні підтвердження та технології безпечного спілкування тощо.

1. 5.1.1.Кодування інформації

Характеристики кодів. Під час шифрування літери або фрази за допомогою коду кожного разу виходить однаковий шифрований текст, тоді як шифрування літери або фрази за допомогою системи шифрування в різні моменти часу виходять, як правило, різні шифровані тексти. Це відбувається тому, що більшість систем шифрування мають один або декілька параметрів, таких, як ключове слово або кутові установки коліс (у шифрмашинах). Через певні проміжки часу, регулярні або нерегулярні, значення параметрів змінюють, щоб для одного і того самого відкритого тексту на виході отримати різні шифровані тексти. Основний механізм отримання шифрованого тексту залишається незмінним, змінюються тільки параметри. Як правило, коди не містять таких параметрів, хоча код може змінитися цілком – але в цьому випадку це буде вже інший код. На практиці для цього час від часу випускають нову кодову книгу.

Вочевидь, найбільш відомим є код, винайдений в 1832 р. Самюелем Морзе (1791-1872) для передавання повідомлень телеграфом. У цьому коді літери алфавіту представлені у вигляді комбінацій «крапок» і «тире» (від одного до чотирьох знаків), цифри від 0 до 9 – п'ятьма знаками, а деякі розділові знаки – шістьма знаками. Для передачі «крапки» телеграфний ключ натискають протягом 1/24 частки секунди, а для передачі «тире» – протягом 1/8 частки секунди. Інтервал між посиланнями літер дорівнює часу передачі «крапки», а інтервал між літерами дорівнює часу передачі «тире». Код Морзе був розроблений таким чином, що час передачі найбільш частотних літер англійської мови виявлявся коротшим, ніж для менш частих літер. Тому літері Е відповідає єдина «крапка», а літері Т – єдине «тире», тоді як для літери J потрібно чотири символи: «крапка-тире-тире-тире». Це зроблено з метою мінімізувати час, необхідний для передавання повідомлення. Міжнародна версія коду Морзе для бездротового телеграфу приведена в табл. 5.2 [89, c.84].

Таблиця 5.2

Код Морзе для латинської абетки та цифр

Кваліфікований спеціаліст, використовуючи код Морзе, міг передавати в середньому близько 30 слів на хвилину.

Комп’ютерний практикум. Організуємо процедуру мовою Pascal для кодування голосних літер англійського алфавіту кодом Морзе.

Одночастинні та двочастинні коди. Більшість кодів передбачає використання кодової книги, яка може містити тисячі кодових груп. У кодах, якими користуються військові, літери, числа і фрази, зазвичай представляють кодовими групами з чотирьох або п'яти літер (цифр). Кодові групи зовсім не обов'язково повинні складатися з однакового числа символів. Головна перевага кодів полягає у великій кількості можливих кодових груп: їх може бути 10 тис. у разі чотиризначного цифрового коду, і майже 12 млн. для п'ятизначного літерного коду. Недоліки кодів полягають в тому, що користувачі кодів змушені носити з собою кодові книги, а також якщо противник отримає копію цієї книги, то він зможе безпосередньо читати всі наступні повідомлення.

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

Таблиця 5.3

Приклад розділу чотиризначної одночастинної кодової книги

Зазвичай, використовують не всі з 10 тис. можливих кодових груп. У них можуть бути залишені проміжки, щоб надалі була можливість за бажанням вставити в код інші слова та фрази. З криптографічної точки зору одночастинний код дає дуже велику перевагу криптоаналітику, оскільки він може здогадатися про значення ще не встановлених кодових груп, пошукавши в словнику відповідні слова, близькі до вже встановлених. Цю проблему можна усунути, якщо зробити числовий порядок кодових груп незалежним від алфавітного або числового порядку кодованих слів. У такому разі ми отримуємо двочастинний код, оскільки користувачам тепер знадобляться дві кодові книги – одна для шифрування, інша для розшифрування. Тоді наведені вище кодові слова в книзі для шифрування можуть виглядати, наприклад, як в табл. 5.4, а книга для розшифрування могла б починатися так, як показано в табл. 5.5, і так далі.

Таблиця 5.4

Кодова книга для шифрування

Таблиця 5.5

Кодова книга для розшифрування

У будь-якому випадку широко поширеним словам будуть, скоріш за все, зіставлені декілька кодових груп, а користувачі проінструктовані про використання всіх альтернативних варіантів у «випадковому» порядку.

1. 5.1.2.Моноалфавітні шифри

Шифр Юлія Цезара. Кожну літеру повідомлення Цезар замінював на іншу, яка в латинському алфавіті містилася від початкової на три позиції далі. Отже, літера А латинського алфавіту замінювалася на D, В на Е і т.д. до літери W, яка замінювалася на Z, потім Х на А, Y на В і, нарешті, Z на С. Якщо би він проробив це зі своїм відомим висловом

VENI. VIDI. VICI. (Прийшов. Побачив. Переміг.).

за допомогою 26-літерного алфавіту, яким користуються в англомовних країнах, то це повідомлення виглядало б наступним чином

YHQL. YLGL. YLFL.

Це не дуже складний метод, відразу стає очевидним, що повідомлення складається із трьох слів, і в кожному із них чотири літери, причому деякі літери повторюються. У такій нескладній системі складно ліквідувати ці недоліки. Але розширення алфавіту з 26 до 29 знаків і більше за рахунок включення знаків пунктуації та пропусків трохи замасковує довжину кожного слова. Проте, Цезар увійшов в історію криптографії, а шифр Юлія Цезара, як його досі називають, слугує прикладом однієї з перших систем шифрування та є частковим випадком шифру простої заміни.

Шифри простої заміни. У шифрі простої заміни звичайний алфавіт заміняють переставленим («перетасованим»). Це означає, що кожна літера звичайного алфавіту заміняють на літеру, що має той самий порядковий номер у переставленому алфавіті [110, с.77]. Формально в цьому випадку шифр заміни можна описати таким чином. Для кожної літери a вихідного алфавіту будують деяку множину символів M_a так, що множини M_a і M_b попарно не перетиналися при a¹b, тобто будь-які дві різні множини не містять однакових елементів. Множину M_a називають множиною шифропозначень для літери a (табл. 5.6).

Таблиця 5.6

Ключ шифру заміни

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

Задача 5.1. Нехай дано таке переставлення алфавіту (перший рядок – звичайний латинський алфавіт, другий – переставлений). Зашифрувати повідомлення COME AT ONCE  (задачу взято з [130, с.18]).

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

Y M I H B A W C X V D N O J K U Q P R T F E L G Z S

Розв’язок. Якщо використовувати шифр простої заміни з цим алфавітом шифрування для шифрування відкритого повідомлення COME AT ONCE, то отримаємо шифрований текст IKOB YT KJIB. Спроба дешифрувати його як шифр Юлія Цезара до успіху не приведе.

Припустимо, криптоаналітик вирішив, що перед ним шифр простої заміни. Чи зможе він дешифрувати його? Він точно зауважить, що повідомлення складається із трьох слів із 4, 2 та 4 літер відповідно, що літери 1 і 9, 2 і 7, 4 і 10 співпадають. Отже, хоч усіх тут десять літер, різних серед них лише сім. Звідси випливає, що будь-яка множина із трьох слів англійською, або будь-якою іншою мовою, яка задовольняє ці умови, є можливим розв’язком. Тому, поряд з іншими можливостями, розв’язками рівною мірою можуть бути такі повідомлення:

GIVE TO INGE

HAVE TO ACHE

SECT IN EAST.

Жоден із цих текстів не виглядає достатньо правдоподібним, але кожний з них є розв’язком. Це показує, що коротке повідомлення, шифроване простою заміною, може бути дешифроване неоднозначно, тому щоб розв'язок був єдиним у випадку шифру простої заміни треба мати не менше 50 знаків. Вважають [130, с.19], щоб розв’язок був не тільки єдиним, але його було б нескладно отримати, необхідно біля двохсот знаків тексту.

Зауваження. Є ще два зауваження до останнього прикладу та наведеного вище алфавіту простої заміни.

1. Задача дешифрування повідомлення у поданому випадку є значно легшою, ніж могла б бути, оскільки шифрований текст був записаний зі збереженням пропусків між словами. Тим самим стають відомі довжини слів початкового повідомлення. Є два стандартних способи ліквідації цієї проблеми.
2. Іґноруючи пропуски та знаки пунктуації, записати у вигляді рядка знаків латинського алфавіту. Тоді відкритий і шифрований тексти останнього прикладу будуть виглядати так: COMEATONCE i IKOBYTKJIB. Тоді криптоаналітик не знатиме, чи складається повідомлення з одного слова з 10 літер або з кількох слів меншої довжини, і, відповідно, кількість можливих варіантів розв’язку значно зростає. Недолік такого підходу є в тому, що отримувачу повідомлення необхідно вставляти в нього пропуски та знаки пунктуації в ті місця, які він вважає для цього кращими, а це іноді може привести до двозначності. Для ілюстрації такої ситуації придатна відома фраза СТРАТИТИНЕМОЖНАПОМИЛУВАТИ, де від розміщення коми зміст вироку змінюється на протилежний. Отже, отримання відкритого тексту ускладнюється і для криптоаналітика, і для адресата.
3. Замість пропуску використовувати якусь рідковживану літеру, наприклад, Х. У тих окремих випадках, коли зустрічається справжня літера Х, її замінюють на іншу комбінацію літер, наприклад, KS. Якщо зробити це із задачею 5.1, то саме повідомлення і відповідний шифрований текст запишуться так: COMEXATXONCE i IKOBGYTGKJIB, оскільки літера Х перетворюється на G в алфавіті шифрування, а в початковому повідомленні Х не зустрічається. Криптоаналітик може здогадатися, що G означає пропуск і після цього знайти довжини слів. Чим більша довжина тексту, тим наочнішим є розташування символів, що замінюють пропуски.

Також можна додати в алфавіт декілька знаків, щоб можна було врахувати і пропуски, і символи пунктуації, такі як крапка і кома. У цьому випадку в алфавіт шифрованного тексту доведеться давати нові символи. Як такі придатні будь-які неалфавітні знаки. Для латинського алфавіту типова трійка знаків може виглядати, наприклад, $, % i &. І може бути, що в 29-літерному алфавіті шифрованного тексту літера D буде відображена знаком &, літера J – знаком $, літера S – знаком %, а пропуск, крапка та кома – знаками S, C i W. Числа при цьому можна записати словами, а можна, навпаки, розширити алфавіт і далі, включивши в нього також і цифри. Такі додаткові знаки, можливо, надають шифрованому тексту «неприпустимого вигляду», але практично стійкість шифру зростає досить незначно.

1. Зауважимо, що в наведеному прикладі шифру простої заміни дві літери (Q i T) не змінюються. Часто студенти, що вивчають криптографію, вважають, що цього треба уникати. Насправді боятися цього не треба, якщо таких літер 1-2. Можна математично точно довести, що у випадково обраному алфавіті заміни з ймовірністю біля 63% зустрінеться хоча би одна літера, що не змінюється [130].

Шифри простої заміни перетворюють текст таким чином, що кожен символ замінюють на якийсь інший. При цьому символам у відкритому тексті відповідають однакові символи у криптотексті, а різним – різні. Ключем є табличка, що вказує, в який саме символ перетворюють кожен символ відкритого тексту. Символи в табличці можуть бути розміщені довільним чином. Отже, питання полягає в тому, скількома способами можна перемістити всі літери абетки у ключі. Для першої позиції для українського тексту літеру можна обрати 33-ма способами. Коли вона обрана, для другої позиції літеру можна обрати вже 32-ма способами, для третьої – 31-м способом тощо. Для передостанньої позиції вибір здійснюють двома способами, остання ж літера визначена однозначно. Тоді загальна кількість можливостей розмістити літери (ключів) є 33!. У загальному випадку, коли алфавіт налічує n символів, ми отримуємо n! ключів. Шифр зсуву є звуженням загального шифру заміни на сукупність лише n ключів, в яких нижній рядок є циклічним зсувом верхнього. Ключ повністю визначається довжиною зсуву s. Хоча кількість ключів при використанні шифрів простої заміни є велика, розшифрувати текст успішно дозволяє частотний метод.

Частота символу у тексті дорівнює кількості його входжень у цей текст, поділеній на загальну кількість літер у тексті. Наприклад, частота літери А у тексті «КУПИЛА МАМА КОНИКА» дорівнює 4/18, а частота пропуску між словами у цьому самому тексті дорівнює 2/18. Для кожної мови справджується такий емпіричний факт: у досить довгих текстах кожна літера зустрічається із приблизно однаковою частотою, залежною від самої літери і не залежною від конкретного тексту. Частотним методом можна здійснити дешифрування, навіть не знаючи ключа. Для цього обчислюють частоти кожного символу у криптотексті і порівнюють отримані результати з таблицею частот для мови, якою написане повідомлення. Це дозволить радикально скоротити перевірку.

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

ПЦПСПОФНПМПЛПИБГПЕФРПТМБВМЕОП,

який був отриманий шифром зсуву без врахування пропусків та розділових знаків. Підраховуємо частоти і зауважуємо, що найбільша (9/29) припадає на літеру П, припустимо, що у відкритому тексті їй відповідає найпоширеніша в українській мові літера О. Це означає, що довжина зсуву дорівнює 1. Виконуємо зсув вліво і отримуємо змістовне повідомлення

ОХОРОНУМОЛОКОЗАВОДУПОСЛАБЛЕНО.

Гомофонний шифр заміни був винайдений Гаусом. Цей шифр ґрунтується на ідеї, яка робить підрахунок частот безперспективним. Кожну літеру відкритого тексту замінюють будь-яким символом із кількох можливих. Наприклад, замість а може бути підставлено будь-яке з чисел 10, 17, 23, 45, 55, а замість б – будь-яке із 12, 71. Основною вимогою є те, щоб замість різних літер завжди підставлялися різні символи, вибір яких здійснюють щоразу випадково. Якщо кількість варіантів для кожної літери пропорційна її частоті в мові, то всі символи у криптотексті зустрічатимуться з приблизно відповідною частотою. Такий текст піддається різновиду частотного аналізу, який, крім частот окремих символів, враховує також частоти пар символів.

Задача 5.2. Зашифрувати повідомлення «Я ЗНАЙОМИЙ ІЗ ШИФРАМИ ЗАМІНИ» з ключем, заданим таблицею.

Розв’язок.Повідомлення «я знайомий із шифрами заміни» може бути зашифровано, наприклад, будь-яким з наступних трьох способів:

Задача 5.3.Одним з відкритих повідомлень є фраза:

СЬОГОДНІ ЗАНЯТТЯ НЕ БУДЕ,

або наступна фраза:

ЗАНЯТТЯ ПРОВЕСТИ ЗАВТРА.

Зашифрувати ці повідомлення за допомогою послідовності літер, тобто послідовності шифрування

ШИФРУВАТИ ПОВІДОМЛЕННЯ.

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

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

Таблиця 5.7

Послідовність літер українського алфавіту

Довжина послідовності шифрування (табл. 5.8)

ШИФРУВАТИПОВІДОМЛЕННЯ

Таблиця 5.8

Ключ шифру заміни

рівна довжині першого повідомлення (табл. 5.9)

СЬОГОДНІЗАНЯТТЯНЕБУДЕ

Таблиця 5.9

Повідомлення 1

та довжині другого повідомлення (табл. 5.10)

ЗАНЯТТЯПРОВЕСТИЗАВТРА

Таблиця 5.10

Повідомлення 2

Зашифруємо перше повідомлення (табл. 5.11).

Таблиця 5.11

Процес шифрування повідомлення 1

Отримаємо наступний шифр

НЖИФЗЖОБРРГВБШОБТЖЖУЕ

Зашифруємо друге повідомлення (табл. 5.12).

Таблиця 5.12

Процес шифрування повідомлення 2

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

ДІЗРЙХАЗЮДСЗАШШЦМЗЄДА

1. 5.1.3.Застосування перестановок

Шифр, перетворення з якого змінюють лише порядок розташування символів початкового тексту, але не змінюють їх самих, називається шифром перестановки (ШП) [140]. Шифри із застосуванням перестановок зберігають усі літери відкритого тесту, але розміщують їх у криптотексті в іншому порядку. Ці шифри інакше називають шифрами обходу [110 с. 87; 130].

Розглянемо перетворення з ШП, призначене для шифрування повідомлення довжиною n символів. Його можна подати за допомогою таблиці

де i₁ – номер місця шифротексту, на яке потрапляє перша літера вихідного повідомлення при вибраному перетворенні, i₂ – номер місця для другої літери тощо. У верхньому рядку таблиці виписані по порядку числа від 1 до n, а в нижньому – ті ж числа, але в довільному порядку. Така таблиця називається підстановкою міри n. Знаючи підстановку, що задає перетворення, можна здійснити як шифрування, так і розшифрування тексту. Наприклад, якщо для перетворення використовують підстановку

і відповідно до її шифрують слово ХЕРСОН, то вийде ОЕРХСН. Спробуйте розшифрувати повідомлення ТЛУАША, отримане внаслідок перетворення за допомогою вказаної вище підстановки.

Існує 1×2×3×…×n= n! варіантів заповнення нижнього рядка таблиці [140]. Таким чином, кількість різних перетворень шифру перестановки, призначеного для шифрування повідомлень довжини n, менше або рівне n! (зауважимо, що в цю кількість входить і варіант перетворення, що залишає всі символи на своїх місцях!). Із збільшенням числа n значення n! зростає дуже швидко.

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

Задача 5.4.Потрібно зашифрувати повідомлення «Сказано на глум, а ти бери на ум» (Галицько-руські народні приповідки: У 3-т т. / Зібрав, упорядкував і пояснив Др. Іван Франко: 2-е вид. – Львів: Видавничий центр ЛНУ імені Івана Франка, 2006. – Т.3. – 699с.) з ключем ФРАНКО.

Розв’язок. Записуємо текст у прямокутну матрицю.

Для ключа ФРАНКО порядок зчитування стовпчиків буде 6-5-1-3-2-4. В результаті отримуємо шифрований текст СОМРКНАИААТНЗГИААЛБУНУЕМ.

1. 5.1.4.Поліалфавітні шифри

Шифри Віженера. Слабкість шифру Юлія Цезара полягає в тому, що він має всього 25 можливих варіантів розшифрування, і тому криптоаналітик зможе всі їх перебрати. Щоб збільшити число таких варіантів, треба  зсувати літери не на фіксоване число позицій в алфавіті, а на змінну величину, залежну від розташування літери в тексті. Очевидно, повинно існувати правило обчислення величини зсуву у кожному конкретному випадку, інакше розшифрувати повідомлення буде неможливо навіть адресатові. Просте правило полягає у використанні послідовності з кількох фіксованих зсувів [110, с. 82].

Задача 5.5. Зашифруйте повідомлення COME AT ONCE зі зсувами 19-5 (задачу взято з [130, с.35]).

Розв’язок. У задачі 5.1 фраза COME AT ONCE була було шифрована з фіксованим зсувом 19, і в шифрованому вигляді було таким:

VHFX ТМ HGVX.

Будемо тепер по черзі використовувати два зсуви 19 і 5 так, щоб перша, третя, п'ята і так далі літери зсовувались на 19 позицій, а друга, четверта і так далі літери зсовувались на 5 позицій, у цьому випадку шифроване повідомлення матиме вигляд

VTFJ TY HSVJ.

Задача 5.6.Замінити в повідомленні COME AT ONCE знак пропуску на Z та зашифруйте його зі зсувами 19-5-11 (задачу взято з [130, с.36]).

Розв'язок. Якщо в повідомленні замінити знак пропуску на Z, то відкритий текст виглядає так:

COMEZATZONCE

Застосування трьох послідовних зсувів 19, 5 і 11 переводить повідомлення у таке:|

VTXXELMEZGHP

а ключем шифрування є трійка чисел 19-5-11. Щоб прочитати це повідомлення, одержувач повинен скористатися ключем розшифрування, який випливає з ключа шифрування заміною кожного числа з трійки на його доповнення по модулю 26, а саме: 7-21-15.

Навіть якщо криптоаналітик здогадається, що використаний шифр Юлія Цезара з трьома послідовними зсувами, йому доведеться перебрати 75 або більше комбінацій (тому що один зі зсувів може дорівнювати нулеві). Якщо повідомлення занадто коротке і неможливо знайти кожен з трьох зсувів окремо, то, ймовірно, доведеться застосувати метод «повного перебору». Однак, оскільки це вимагатиме перевірки 25´25´25=15625 варіантів, до нього варто вдаватися лише як до крайнього заходу. У особливому випадку, коли число зсувів у послідовності дорівнює числу літер в тексті, повідомлення стає таким, що не «дешифрується», якщо у послідовності зсувів не відмічено якої-небудь невипадкової характеристики.

Описаним тут способом посилення шифру Юлія Цезара за допомогою декількох зсувів користуються вже багато сотень років. Такі системи називають шифрами Віженера. Оскільки більшості людей легко запам'ятовувати слова, а не випадкові послідовності літер або чисел, то ключі шифрів Віженера нерідко набувають вигляду ключового слова. Літери ключового слова перетворяться в числа стандартним способом (А=0, В=1, С=2..., Z=25). Наприклад, ключове слово CHAOS еквівалентне використанню послідовності з п'яти зсувів 2-7-0-14-18. Ключове слово або числовий ключ виписують над відкритим текстом періодично. Додаючи до кожної літери відкритого тексту відповідний зсув, визначений літерою ключа, отримуємо шифрований текст.

Задача 5.7. Зашифруйте текст HOMOZHOMINIZLUPUSZEST за допомогою шифру Віженера з ключовим словом PASCAL.

Розв’язок. Шифрування відбувається так:

В результаті отримуємо шифрований текст

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

Кількаразове шифрування. У 20-х роках ХХ століття були винайдені роторні шифрувальні пристрої (додаток И), які вдосконалювалися упродовж наступних десятиліть і інтенсивно використовувалися під час Другої світової війни. Прикладом може служити відома німецька шифрмашина «Енігма». Роторні системи реалізовували багатократну композицію шифрів Віженера, що давало шифр з дуже великим періодом. Частковим випадком композиції двох шифрів є послідовне застосування двічі одного й того самого шифру але перспективнішим є подвійне шифрування з незалежним вибором ключа кожного разу. Тобто, за допомогою алгоритму шифрування Е повідомлення М перетворюється у криптотекст , де два ключі K₁ та K₂ вибирають незалежно один від одного. Алгоритм, який полягає у шифруванні повідомлення за допомогою одного шифру, а потім застосуванні до отриманого криптотексту ще одного шифру називають композицією або добутком цих двох шифрів. Дешифрування не викликає труднощів:  (треба звернути увагу на зміну порядку, в якому застосовують ключі) [6].

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

З цього погляду вигіднішим є подання інформації у цифровій формі, коли кожен символ тексту замінюємо його номером у алфавіті, нумерацію починаємо з 0. Для прикладу, слово БАНАН буде подане як 01 00 17 00 17. Кожна літера відображена своїм номером, записаним двома цифрами, перша з яких може бути нулем. При потребі в алфавіт можна включити, окрім літер, також знаки пунктуації, пропуск, цифри тощо.Номери літер ми можемо записувати не в десятковій системі числення, а у двійковій. Для того самого слова БАНАН матимемо запис 000001000000010001000000010001, де кожен блок із шести цифр є номером відповідної літери у двійковому записі (ми потребуємо не менше шести цифр, бо п'ятьма можна записати щонайбільше 32 числа, тоді як українська абетка налічує 33 літери). Будь-яку послідовність бітів називають двійковим словом.

Шифр одноразового блокноту був винайдений 1917 року Гілбертом Вернамом. Він використовує операцію додавання бітів за модулем 2, яку ми розглянемо перед тим, як описати сам шифр. Операцію позначають символом Å і задають так: 0Å0=0, 0Å1=1, 1Å0=1, 1Å1=0.

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

Для двійкових слів Х і Y однакової довжини результат їх побітового додавання позначатимемо як XÅ Y. Легко перевірити рівності XÅ Y = Y Å X та (X Å Y) Å Z = X Å (Y Å Z), що справджуються для будь-яких двійкових слів X, Y і Z однакової довжини. Для фіксованого k позначимо через 0 двійкове слово 000...00, що складається із k нулів. Очевидно, що для будь-якого двійкового слова Х довжини k виконують рівності XÅ0= X і XÅ X =0. Перейдемо тепер до опису шифру. Перед шифруванням повідомлення М записують у двійковій формі. Ключем K служить довільне двійкове слово однакової з М довжини. Шифрований текст С отримують побітовим додаванням повідомлення і ключа, тобто C= M Å K.

Задача 5.8. Зашифруємо слово  БАНАН з допомогою ключа K.

Розв’язок.  Вище подано двійкову форм слова БАНАН:

М = 000001000000010001000000010001.

Як ключ виберемо K = 001101110101100010011000111010.

Сумування цих двох двійкових послідовностей вже виконане нами вище. Отож маємо криптотекст

С = 001100110101110011011000101011.

Дешифрування у шифрі одноразового блокноту збігається із шифруванням – щоб отримати вихідне повідомлення М, треба додати до криптотексту С той самий ключ K. Це легко обґрунтувати: оскільки C= M Å K, то

CÅ K = (M Å K) Å K = M Å (K Å K)  = M Å 0 = M.

Шифр одноразового блокноту є абсолютно надійним або, як ще кажуть, надійним у теоретико-інформаційному сенсі. Якщо суперник не знає ключа K, то з підслуханого криптотексту С він зовсім нічого не може довідатися про повідомлення М. Справді, двійкове слово С могло б бути криптотекстом для будь-якого повідомлення М', якби шифрування здійснювалося з деяким іншим ключем K', а саме K' = M Å C , тоді як для суперника всі ключі однаково вірогідні. Наприклад, за допомогою деякого ключа K ми щойно перетворили повідомлення БАНАН у шифрований текст С = 001100110101110011011000101011. Але такий самий криптотекст ми отримали б, якби шифрували повідомлення ГРУША з ключем K' = 001111100001100100000100101011.

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

Іншими типовими значеннями модулів, що використовують в криптології, є 10 та 26. Як і в операціях за модулем 2, усі числа заміняють на остачу від ділення цих чисел на модуль. Якщо в остачі від’ємна величина, то до нею додають значення модуля, щоб остача стала додатною. Наприклад, використовуючи модуль 26 (допустимими є числа від 0 до 25), додамо 17 до 19. У результаті одержимо 10, оскільки 17+19=36, а 36 ділиться на 26 з остачею 10. Аби вказати, що використовують модуль 26, використаємо таку форму запису:

17+19=10(mod 26).

Якщо відняти 19 від 17, то результат (-2) буде від’ємним, тому до нього додають 26, і у результаті отримаємо 24.

Задача 5.9. Додати за модулем 26 послідовності 15 0 18 2 0 11 15 0 18 2 0 11 15 0 18 2 0 11 15 0 18 та 7 14 12 14 25 7 14 12 8 13 8 25 11 20 15 20 15 20 18 25 4 18 19.

Розв’язок.

і в результаті отримаємо 22 14 4 16 25 18 3 12 0 15 8 10 0 20 7 22 18 10 19 18 11.

1. 5.1.5.Книжкові шифри

Для роботи з книжковим шифром потрібна книга на будь-яку тему, текст якої набраний лише одним алфавітом. Щоб користуватися книжковим шифром, необхідно уміти попарно «додавати та віднімати» літери алфавіту. Цю процедуру починають з того, що кожній літері алфавіту присвоюють номер (для латинського алфавіту – А=0, В=1, С=2 ..., Z=25), далі проводиться додавання або віднімання (для 26 літер латинського алфавіту – за модулем 26) і зворотне перетворення результату в літери. Для полегшення процедури складено таблиці [15, с.29].

Задача 5.10. Перетворимо латинський алфавіт в числа, починаючи з А=0, В=1, і так далі. Потім додамо два приведених нижче тексти за модулем 26 і перетворимо отриманий чисельний результат знову в літери.

Розв'язок.

Пронумеруємо літери англійського алфавіту (табл. 5.13).

Таблиця 5.13

Нумерація літер латинського алфавіту

Спочатку за допомогою даної таблиці перетворимо тексти в числа:

Тепер додамо їх і приведемо за модулем 26:

Перетворимо результати знову в літери, використовуючи Таблицю 5.5:     

Такий шифрований текст буде надіслано. Одержувачеві потрібно буде відняти з нього Текст 2 за модулем 26, щоб відновити Текст 1, а саме:

Тепер віднімемо за модулем 26 (тобто якщо результат негативний, додамо 26). Одержуємо:

Перетворимо результат назад в літери:

і отримаємо Текст 1, тобто вихідне повідомлення.

Кожного разу при шифруванні повідомлення доводиться перетворювати текст в числа, додавати їх, віднімаючи там, де потрібно, число 26, і знов перетворювати числа в літери. Очевидно, що цей процес вельми трудомісткий, може легко призвести до помилки. Тому є сенс побудувати дві таблиці (одну – для шифрування, іншу – для розшифрування), з яких одразу можна взяти результат цих операцій (табл. К.1-К.2). Відмітимо, що під час користування таблицею шифрування (табл. К.1) не має значення, чи є текст повідомлення «Текстом 1», а текст ключа – «Текстом 2», або навпаки, оскільки додавання цих двох текстів у будь-якому випадку дає один і той же результат. Але під час використанні таблиці розшифрування (табл. К.2) шифрований текст і ключ необхідно розрізняти, оскільки для отримання відкритого тексту необхідно відняти ключ з шифрованого тексту, а не навпаки.

1. 5.1.6.Дволітерні шифри

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

Заміна «монограф-диграф». Алфавіт вписують в квадрат (прямокутник) такої розмірності, щоб вмістились усі символи, що підлягають кодуванню. Далі розглядатимемо випадок англійської мови з алфавітом у 26 літер. Тобто йдеться про квадрат 5x5, причому одна літера відсутня. Зазвичай опускають літеру J; у разі потреби її замінюють на I. П'ять рядків і п'ять стовпців квадрата позначено літерами А, В, С, D, Е (табл. 5.14).

Таблиця 5.14

Квадрат для заміни «монограф-диграф»

Кожну літеру відкритого тексту замінюють на пару літер, що позначають стовпець і рядок, на перетині яких вона стоїть. Так, на приклад, літера О переходить в СD. Тому шифрований текст отримують удвічі довшим за початковий відкритий текст і складається він тільки з літер від А до Е.

Задача 5.11. Зашифруйте фразу АLMA MATER, використовуючи табл. 5.16.

Розв’язок. Шифрована фраза відкритого тексту виглядає так:

AACA CBAA CBAA DDAE DB.

У такому вигляді цей шифр є слабким, але його стійкість можна підсилити, якщо внести дві зміни:

• використовувати переставлений алфавіт усередині квадрату 5x5;
• застосувати до шифрованого тексту шифр перестановки.

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

Задача 5.12. Зашифруйте фразу HAPPY BIRTHDAY, використовуючи таблицю з ключовим словом THURSDAY та застосуйте до шифрованого тексту перестановку 5-1-4-2-3. Квадрат для шифрування подано у табл. 5.15 (задачу взято з [130, с.68]).

Таблиця 5.15

Квадрат для заміни з ключовим словом

Розв'язок. Шифрована фраза відкритого тексту HAPPY BIRTHDAY виглядає так:

ABBBD EDEBC BDCDA DAAAB ВАВВВ С.

Оскільки в перестановці беруть участь п'ять чисел, впишемо шифрований текст в таблицю з п'яти стовпців. Відмітимо, що один із стовпців повинен містити шість літер, оскільки довжина шифрованого тексту 26 знаків. Отримувач повідомлення повинен знати, які стовпці (якщо такі є) є «довгими». Про це необхідно домовитися заздалегідь. Не обмежуючи загальності, припустимо, що «довгі» стовпці мають в перестановці менші номери. Тому в даному прикладі єдиним «довгим» стовпцем виявляється стовпець, позначений цифрою «1» (тобто другий ліворуч). Вписуючи шифрований текст в таблицю перестановок, отримуємо табл. 5.16.

Таблиця 5.16

Таблиця перестановок

Остаточний варіант надаваного тексту виглядає так:

BDDAA CBBDA BDCAB BBECA BAEBD В.

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

BLUAL BEАСЕ DVM.

Зауважимо, що перед повторним використанням квадрата застосування перестановки обов'язкове, оскільки інакше ми просто розшифруємо повідомлення!

МДПМ-шифри. Розглянутий метод можна було, строго кажучи, назвати системою «монограф-диграф-перестановка-монограф», скорочено МДПМ. У нім зв'язки між окремими літерами відкритого і шифрованого текстів дуже складні, оскільки кожну вихідну літеру замінюють парою літер, кожна з яких утворює диграф із літерою з деякої іншої пари, а він, у свою чергу, знову перетвориться в монограф.

Задача 5.13. Використовуючи метод МДПМ, зашифрувати 25-літерний алфавіт (літера J опущена) за допомогою квадрата 5x5 зі звичайним порядком розташування літер, а також перестановки 3-1-6-4-5-7-2-9-10-8 (задачу взято з [130, с.70]).

Розв'язок. «Відкритий текст» має вигляд: ABCDEFGHIKLMNOPQRSTUVWXYZ.

Після його перетворення по квадрату 5x5 (табл. 5.1), отримаємо:

АААВА CADAE BABBB CBDBE CACBC CCDCE DADBD CDDDE EAEBE CEDEE.

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

ААААА ABCDE ABCDE BBBBB ABCDE ABCDE ССССС ЕЕЕЕЕ DDDDD ABCDE

Таблиця 5.17

Таблиця перестановок

з якого, провівши зворотне перетворення, отримаємо шифрований текст із монографів

AAAHU BOWGG BOVHU NNPZZ TTQHU.

Складно здогадатись, що тут шифрований 25-літерний алфавіт, записаний у звичному порядку.

Історичний факт. На початку 1918 р. німецьке верховне командування почало використовувати шифр, основою якого був квадрат 5x5. У ньому 25 літер алфавіту перетворювалися в диграфи, в яких використовувались лише літери A, D, F, G, X. У його модифікації використовувався квадрат 6x6, де було 11 додаткових знаків. Це давало можливість використовувати всі 26 літер алфавіту і 10 цифр. Цей шифр був відомий під назвою «шифр ADFGVX». Таким чином, кожна літера вихідного повідомлення, перетворювалася на пару літер, які потім розділялися і переставлялися згідно ключа, ключ мінявся щодня. Розкрити цей шифр було нелегко, однак французький криптоаналітик Жорж Пенвен (Georges Painvin) знайшов метод прочитання цього шифру за наявності декількох повідомлень з однаковим відкритим текстом на початку або в кінці. І хоча вдалося прочитати повідомлення тільки декількох днів, їх кількість в ті дні була великою, а зміст — особливо важливим. Писали, що «одне з повідомлень було прочитано так швидко, що крупна операція німецьких військ, про яку в ньому йшлося, була повністю зірвана» [130, сс.71-72].

Система «диграф-диграф». У шифрі простої заміни кожну окрему літеру алфавіту заміняють іншою окремою літерою. Подібно до цього, можна запропонувати систему, в якій кожен диграф замінюють двома літерами. Найбільш простий спосіб в даному випадку – скласти список всіх можливих дволітерних комбінацій та їх шифрованих еквівалентів. Для латинського алфавіту це буде 676(=26x26) комбінацій, наприклад:

АА=ТК, AB= LD, AC = ER..., ZX = DW, ZY = HB, ZZ=MS.

Але це означає необхідність мати два списки по 676 елементів кожен: один для шифрування, інший – для розшифрування. І хоча стійкість такої системи буде вища в порівнянні з простою заміною, користуватися нею незручно. Альтернативою цьому може бути використання квадрату диграфів, що містить тільки 25 літер алфавіту (для англійського, наприклад, – окрім J). При цьому диграфи шифрованого тексту виходять з диграфів відкритого тексту згідно певного правила

1. 5.2.Основи криптоаналізу. Лінґвістичне дешифрування

Криптоаналіз – розділ криптології, що займається методами порушення конфіденційності і цілісності інформації без знання ключа [108, 114]. Застосування для криптоаналізу методів мовознавства називають лінґвістичним дешифруванням [89, с.82].

1. 5.2.1.Розкриття шифру Цезара

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

Задача 5.14. Текст повідомлення, шифрованого за системою Юлія Цезара, має вигляд XOPXC KJOVOZ. Необхідно дешифрувати повідомлення.

Розв’язок. Запишемо шифроване повідомлення та, в разі потреби, усі 25 його зсувів у стовпець, проставивши значення зсувів зліва від кожного рядка.

Ми бачимо, що у шифрі використаний зсув на 19 позицій, оскільки шифрований текст, будучи зсунутий на 7 позицій вперед, дає відкритий текст. Це означає, що для отримання шифрованого тексту відкритий текст треба зсунути на (26-7)=19 позицій. Ймовірно (якщо припускати, що при кожному іншому зсуві не отримують змістовне повідомлення), що ми правильно дешифрували це повідомлення, і тому немає необхідності виписувати інші варіанти. Таке припущення про поодинчість розв’язку достатньо обумовлене, коли шифроване повідомлення містить понад 5-6 знаків; але якщо повідомлення досить коротке, можливих розв’язків може бути декілька. Приведемо приклад неоднозначного розв’язку [130, с. 18]. Нехай шифрований текст виглядає так: MSG (це схоже на абревіатуру англійського слова «message» – «повідомлення»). Далі подано два можливих розв’язки, але звідси зовсім не випливає, що такий шифр є простим способом перекладу французького тексту на англійську мову.

1. 5.2.2.Розкриття шифру заміни

Спочатку ми розглянемо спосіб, яким не треба розкривати шифр простої заміни – спосіб повного перебирання всіх варіантів. Літері А відкритого тексту можна поставити у відповідність будь-яку із 26 латинських літер, літері В – будь-яку із 25, що залишилися, літері С – будь-яку із 24, що залишилися, і т. ін. Тому кількість можливих алфавітів простої заміни дорівнює 26´25´…´ 2 ´ 1, тобто 26! Це число більше за , тому  навіть комп’ютер, здатний кожну секунду перевіряти тисячу мільйонів (тобто ) алфавітів, затратить на цю задачу декілька сотень мільйонів років. Метод повного перебору, що дає задовільні результати з шифром Юлія Цезара (в ньому всього 25 варіантів), тут зовсім не придатний. Практичний метод розкриття шифру такого типу називають частотним аналізом та полягає в подальшому (табл. 5.18) [108; 110, с. 75; 114; 130].

Таблиця 5.18

Етапи розкриття шифру

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

UGPAKWBNHVTZUGDVZTD3MG5V2HUKVUHVCTWTZV4G2TJUK4JBVT6HVA3WTV41FG57

UK2V5KZDFQJJ82V8V7VSG57ZQV55G7G5V4HAHV4G2TZT4JGJUBT0VW0ZQUT0VUKDTW

QVUHVU3ZQ548VUKDTWQVUHVU3ZB935G5VUGV4G2TJKV6HV5KZF8Z7HUU8VAHSVDKU

6H5T9TVJHF2KU3VUHVW8DGWTVPNT5VUGVUBT9TV45KZT2TVG7V1TDQV5WG4UQPV9T

WT4V1TMG5V5QZG5GJQ48VM37Q2

Розв’язок.

1.  Спочатку складемо таблицю частот появи знаків (табл. 5.19) та відсортуємо її за спаданням кількості появ знаків.

Таблиця 5.19.

Частоти появи знаків у шифрованому тексті

1. Оскільки літера V зустрічається 43 рази у тексті з 256 знаків, тобто частіше за інші знаки, то можна зробити висновок, що знак V шифрованого тексту відповідає знаку пропуску.
2.  По всьому шифрованому тексті замінимо V на пропуски, і отримаємо текст із відомими довжинами слів. Усього слів у повідомленні 45, пронумеруємо їх, щоб далі було зручніше на них посилатися.

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

1.  Наступна за частотою появи у шифрованому тексті є знак Т – він з’являється 26 разів, тому припустимо, що це літера О відкритого тексту. Тоді шифрований текст виглядатиме так.

Наступним за частотою у шифрованому тексті є знаки U (23 появи) та G (20 появ). Згідно [115], третє та четверте місце за частотою появи літер української мови посідають літери Н та А. Припустимо, що знаки U і G відповідають Н і А (або А і Н). Спробуємо символами * та + замінити у шифрованому тексті знаки G та U, відповідно. Тоді частково встановлене повідомлення виглядає так.

Серед отриманого тексту звертають на себе увагу подвоєння символів ** (у слові 28) та чотириразова поява біграфів *+ (у словах 1, 2, а також слова 25, 35). Тобто знайдено або подвоєння літер НН та чотири рази з’являється біграф НА (з них два – окремі слова) у шифрованому тексті (якщо позначення літер символами * та + було вірне), або знайдено подвоєння літер АА та чотири рази з’являється біграф АН (з них два – окремі слова) у шифрованому тексті (якщо позначення літер символами * та + було не вірне). Очевидно, що ймовірність зустріти подвоєння літер НН в українському тексті набагато більша, ніж імовірність зустріти АА. Також більшою є імовірність появи біграфа НА, ніж АН. Тому наше припущення про те, що літера U шифрованого тексту є літерою Н в оригіналі, а літера G – літерою А справджується. Внесемо відповідні заміни у відкритий текст.

1.  Розглянемо короткі слова, де бракує 1-2 літер. Наприклад, для другого слова відкритого тексту (О.НА.) варто проаналізувати словники, які ж саме існують слова з п’яти літер, де першою О, а третьою та четвертою – НА. Знайдемо, що слів, які б відповідали заданій схемі, є три: ОдНАк, ОзНАк, ОсНАч. Проаналізуємо отримані результати. На другому місці слова у шифрованому тексті є літера є літера Z, абсолютна частота якої є досить високою і складає 13. В українській мові ймовірність літери Д складає 0,028, літери З – 0,018, літери С – 0,033, тобто найбільш частотною є літера С, далі – Д і З. Також біграф ОС є більш імовірною, ніж ОД чи ОЗ. Тому, попри те, що ймовірність появи біграфа АК більша за ймовірність появи біграфа АЧ, можна припустити, що слово, яке ми підбираємо, не ОЗНАК. Серед двох слів, які продовжуємо розглядати, слово ОДНАК має значно більшу ймовірність появи, ніж маловживане слово ОСНАЧ. Також на користь слова ОДНАК свідчить те, що ймовірність появи літери К є більшою за ймовірність появи літери Ч. Тому наступним нашим припущенням буде те, що шуканим словом є ОДНАК, що дає нам можливі літери Д замість Z та К замість D.

Розглянемо тепер слово з двох літер, що починається на Н (таких є чотири – 5, 20, 23, 32). Найбільш частотними словами, що відповідають схемі, є НЕ/НИ, НА (його відкидаємо, бо літера А вже відкрита), НУ та НЕ/НЄ [22-25]. Для нашого конкретного шифрованого тексту другим знаком слова є Н, абсолютна частота якого досить висока (14 появ у шифрованому тексті), тому припустимо, що знак Н шифрованого тексту відповідає літері Е шуканого відкритого тексту. Внесемо відповідні літери.

Розглянемо тепер двічі повторюваний блок у шифрованому тексті – слова 19 та 22, частина слова вже розшифрована (Н.КО..). Згідно словників, цим словом може бути НаКОли, НеКОли, НиКОни, НіКОли, НіКОль. Звернемо увагу на останню літеру слова: це або И, або Ь. Імовірність появи для літери И є значно вищою, ніж для літери Ь, літера И є однією із п’яти-шести найбільш частотних літер української мови. У шифрованому тексті літера Q також належить до п’ятірки найбільш частотних, тому ствердимо, що цій літері в шуканому тексті відповідає И.

Передостанньою літерою шуканого слова може бути Л або Н, проте слово НИКОНИ (третій день свят) є рідковживаним, тому припустимо, що передостанньою літерою шуканого слова буде Л. Другою літерою шуканого слова, таким чином, може бути А, Е або І. Пам’ятаємо, що А та Е уже відкриті, тому шукана літера – І.

Внесемо знайдені літери: замість Q – И, замість W – Л, замість K – І.

Із першої п’ятірки найбільш частотних літер шифрованого тексту нерозкритою залишився знак – цифра 5, якому, згідно з частотами появи літер української мови, може відповідати літера В або Т. Спробуємо знайти підтвердження цього. Так, слово .ІДК.И…. (11), вочевидь, не може починатись з літери Т, але цілком логічним є літера В на початку слова. Більше того, наприкінці слова знаходимо подвоєння літеру шифрованому тексті, і аналізованим словом ВІДК.И…. цілком може виявитись слово ВІДКРИТТЯМ. Тому спробуємо замінити цифру 5 у шифрованому тексті на В, F – літерою Р, J – Т, 8 - Я, 2 – М. Тоді сьоме слово .АМОТНІ.Т. є, очевидно, словом САМОТНІСТЬ, п’ятнадцяте слово ВВА.АВ – ВВАЖАВ, вісімнадцяте слово Л.ДИНО. – ЛЮДИНОЮ. 

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

Алфавіт шифрування, яким користується відправник, для отримання шифрованого тексту із відкритого, є, звичайно, його інверсією:

Початкове повідомлення виглядало наступним чином:

НАЙБIЛЬШЕ, ОДНАК, ДОКУЧАВ МЕНI НЕ ХОЛОД. САМОТНIСТЬ. ОЦЕ БУЛО СПРАВЖНIМ ВIДКРИТТЯМ. Я Ж ЗАВЖДИ ВВАЖАВ СЕБЕ САМОДОСТАТНЬОЮ ЛЮДИНОЮ, НIКОЛИ НЕ НУДИВСЯ, НIКОЛИ НЕ НУДЬГУВАВ НА САМОТI. ЦЕ ВIДРЯДЖЕННЯ БЕЗ КIНЦЕВОГО ТЕРМIНУ НЕ ЛЯКАЛО, ЙШОВ НА НЬОГО СВIДОМО. АЖ ПОКИ ВЛАСНИЙ ГОЛОС ПОЧАВ ВИДАВАТИСЯ ЧУЖИМ.

(Вдовиченко Г. Тамдевін. – К. : Нора-Друк, 2009, – 240 с.)

Задача 5.16. Отримано шифроване повідомлення із 53 п’ятизначних груп. Відомо, що система шифрування являє собою шифр простої заміни, пропуски у відкритому тексті замінюють на літеру Z, а всі інші знаки пунктуації іґнорують. Необхідно відновити відкритий текст повідомлення (задачу взято з [130, с.23]).

Шифрований текст має вигляд:

Розв’язок.

1.  Спочатку складемо таблицю частот появи знаків (табл. 5.20).

Таблиця 5.20

Частоти появи знаків у шифрованому тексті

1. Оскільки літера Y зустрічається 49 разів у тексті з 265 знаків, тобто частіше за інші знаки (18% тексту), то можна зробити висновок, що знак Y шифрованого тексту відповідає знаку пропуску. Далі за Y за частотою вживання ідуть літери Z і М, тому позначимо їх як кандидатури на місце літер Е та Т, або Т і Е.
2.  По всьому шифрованому тексті замінимо Y на пропуски, опускаючи при цьому пропуски між п’ятизначними групами (вони не містять жодної інформації), і отримаємо текст із відомими довжинами слів. Загальна кількість слів у повідомленні дорівнює 50. Пронумеруємо їх, щоб далі було зручніше на них посилатися.