Наприклад, англійська абетка

ДОБУЛ АВИТР ЕБАГО ЛОВИЬ

Літери кожної групи переставимо відповідно до зазначеного дворядкового запису за таким правилом: перша літера ставиться на третє місце, друга – на друге, третя – на п'яте, четверта – на перше і п'ята – на четверте. Здобутий текст виписуємо без пропусків:

УОДЛБТВАРИГБЕОАИОЛЬВ

При розшифровуванні текст розбивається на групи по п'ять літер, які переставляються у зворотному порядку: перша – на четверте місце, друга – на друге, третя – на перше, четверта – на п'яте і п'ята – на третє. Ключем шифру є обране число 5 і порядок розташування

 

1.1.1 Прилад Сцитала

 

Одним з перших фізичних приладів, які зреалізовують шифр перестановки, є так званий прилад Сцитала. Його було винайдено у давній "варварській" Спарті за часів Лікурга (V ст. до н. е.). Рим швидко скористався цим приладом. Для зашифровування тексту використовувався циліндр заздалегідь обумовленого діаметра. На циліндр намотувався тонкий ремінець з пергамента, і текст виписувався порядково вздовж осі циліндра. Потім ремінець змотувався й доправлявся одержувачеві повідомлення. Останній намотував його на циліндр того самого ж діаметра і зчитував текст по осі циліндра. У цьому прикладі ключем шифру є діаметр циліндра та його довжина, котрі, власне кажучи, породжують дворядковий запис, аналогічний до того, що його наведено вище.

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

Відкритий текст виписується в прямокутну таблицю з n рядків та m стовпців. Припускається, що довжина тексту t £ nm (у противному разі ділянка тексту, що залишилася, шифрується окремо за тим самим шифром). Якщо t є строго менше за nm, то порожні клітинки, що залишилися, заповнюються довільним набором літер абетки. Шифртекст виписується за цією таблицєю заздалегідь обумовленим "маршрутом" – шляхом, що він проходить одноразово через усі клітинки таблиці. Ключем шифру є числа n та m і окреслений маршрут.

У такому трактуванні шифр Сцитала набуває описаного нижче вигляду. Нехай m – кількість обвитків ремінця на циліндрі; n – кількість літер, розташованих на одному обвитку. Тоді відкритий текст, виписаний порядково в зазначену таблицю, шифрується шляхом послідовного зчитування літер за стовпцями. Оскільки маршрут є відомий і незмінний, то ключем шифру є числа m та mn, зумовлені діаметром циліндра й довжиною ремінця. При перехопленні повідомлення (ремінця) єдиним секретним ключем є діаметр.

Винахід дешифрувального пристрою – Антисцитала – приписують великому Аристотелю. Він запропонував використовувати конусоподібний "спис", на який намотувався перехоплюваний ремінець; цей ремінець пересувався віссю доти, аж допоки не з'являвся осмислений текст.

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

 

 

1.1.2 "Магічні квадрати"

 

"Магічними квадратами" називають квадратні таблиці з вписаними в їхні клітинки послідовними натуральними числами, розпочинаючи від 1, що вони дають у сумі по кожному стовпцю, кожному рядку і кожній діагоналі одне й те саме число.

Кількість "магічних квадратів" швидко зростає зі збільшенням розміру квадрата. Кількість "магічних квадратів" 4´4 становить 880, а кількість "магічних квадратів" 5´5 – близько 250000.

Уперше ці квадрати виникли в Китаї, де їм було надавано певної "магічної" сили. Наведемо приклад: у квадрат розміром 4´4 вписуються цифри від 1 до 16.

Зашифровування за "магічним квадратом" здійснюється у такий спосіб.

Наприклад, треба зашифрувати фразу: «ПРИЛІТАЮ СЬОГОДНІ». Літери цієї фрази вписуються послідовно до квадрата відповідно до записаних в них чисел, а в порожні клітинки (якщо такі є) проставляють довільні літери.

16І 3И 2Р 13О 5І 10Ь 11О 8Ю 9С 6Т 7А 12Г 4Л 15Н 14Д 1П

 

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

 

ІИРОІЬОЮСТАГЛНДП

 

При розшифровуванні текст вписується до квадрата – й відкритий текст читається в послідовності чисел "магічного квадрата".

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

 

1.1.3 Практичне застосовування шифрів перестановки в системах зв'язку

 

Практичну реалізацію шифру перестановкив системах зв'язку може бути подано на такому прикладі.

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

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

Перестановка частот. За допомогою системи фільтрів уся ширина смуги стандартного телефонного каналу може бути поділена на певну кількість частотних смуг, котрі потім може бути переставлено поміж собою (рис. 1.1 та 1.2).

 

Рисунок 1.1 Рисунок 1.2

 

Найпростіший скремблер обмежує захист уведенням подібних найпростіших частотних перетворень. Серійний скремблер переставляє діапазони 250...675 Гц, 675...1100 Гц, 1100...1525 Гц та 1950...2375 Гц.

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

Інвертування спектра. Більш складні скремблери додатково здійснюють інвертування спектра (рис. 1.3).

 

Рисунок 1.3

 

Частотно-часові перестановки. Ще більш складні системи розбивають сигнал на часовому інтервалі 60...500 мс і на кожнім інтервалі використовують у комбінації власні аналогові перетворення. Зміною перетворень у різні часові інтервали керує послідовність, яка надходить на вузол накладання шифру з блока ускладнювання. Той, хто просто послухає дешифроване аналоговим сигналом мовлення, почує якийсь булькіт, шум. Про складність завдання зашифрововування й розшифровування аналогових повідомлень писав Солженіцин у своєму «В круге первом»: «…Клиппирование, демпфирование, амплитудное сжатие, электронное дифференцирование и интегрирование привольной человеческой речи были таким же инженерным издевательством над ней, как если бы кто-нибудь взялся расчленить Новый Афон или Гурзуф на кубики вещества, втиснуть в миллиард спичечных коробков, перевезти самолетом в Нерчинск, на новом месте распутать, неотличимо собрать и воссоздать субтропики, шум прибоя, южный воздух и лунный свет. То же, в некоторых импульсах, надо было сделать и с речью, даже воссоздать ее так, чтобы не только было понятно, но Хозяин мог бы по голосу узнать, с кем говорит…». Так само барвисто й дещо зневажливо Солженіцин відгукувався про власне роботу з розробляння вітчизняних засобів захисту телефонної інформації. Однак тут він був неправий. На думку висококваліфікованих фахівців, того часу робота йшла вельми цілеспрямовано й апаратуру насправді випускали в призначений термін. Це – апаратура часової стійкості. За наявності спецтехніки типу видимого мовлення зміст перемов удається відновити. Якщо забути про інверсії, то ми маємо шифр перестановки.

Для гарантованого засекречування телефонного мовлення його спочатку оцифровують – переводять у двійкову послідовність, а потім опрацьовують так само, як і будь-яке текстове повідомлення.

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

 

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

 

Шифри простої заміни (одноабеткові підстановки) – це простий метод перетворень, який містить правило заміни символів вихідного тексту на другі символи тої самої абетки.

Шифр заміни є найпростішим та найбільш популярним шифром. Як випливає з самої назви, шифр заміни здійснює перетворення (заміну) літер чи інших "частин" відкритого тексту на аналогічні "частини" шифрованого тексту. Легко навести математичний опис шифру заміни. Нехай Х и Y – дві абетки (відкритого й шифрованного тексту відповідно), котрі складаються з однакової кількості символів. Нехай також g: Х Y – взаємно однозначне відбиття Х в Y. Тоді шифр заміни впливає у такій спосіб: відкритий текст x ₁ x ₂… x_n перетворюється на шифрований текст g (x ₁) g (x ₂)… g (x_n).

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

= { a ₀ + a ₁ + a ₂ + … + a_{m –1}}.

Поєднуючи за певним правилом літери з абетки , можна створити нові абетки:

· абетку , яка має m ² біграм a ₀ a ₀, a ₀ a ₁, …, a_{m -1} a_{m -1};

· абетку , яка має m ³ триграм a ₀ a ₀ a ₀, a ₀ a ₀ a ₁,…, a_{m -1} a_{m -1} a_{m -1}.

Тоді, по’єднуючи по n літер, дістаємо абетку , яка має mⁿ n -грам.

Наприклад, англійська абетка

= {ABCDEFGH … WXYZ},

яка містить m = 26 літер, дозволяє згенерувати за допомогою операції конкатенації абетку з 26² = 676 біграм

AA, AB, …, YZ, ZZ,

абетку з 26³ = 17576 триграм

AAA, AAB, …, ZZY, ZZZ

тощо.

При виконанні криптографічних перетворень корисно замінювати літери абетки на цілі числа – 0, 1, 2, 3,... Це дозволяє спростити виконання необхідних алгебраичних маніпуляцій. Наприклад, можна установити взаємно однозначну відповідність поміж українською абеткою

∑ _укр = {АБВГГ′Д … ЮЯ}

та множиною цілих

₃₃ = {0, 1, 2, 3, …, 32};

 

поміж російською абеткою

∑ _рос = {АБВГДЕ … ЮЯ}

та множиною цілих

₃₂ = {0, 1, 2, 3, …, 31};

поміж англійською абеткою

∑ _англ = {ABCDEF … YZ}

та множиною цілих

₂₆ = {0, 1, 2, 3, …, 25}

(див. табл. 1.1, 1.2 та 1.3).

Надалі буде зазвичай використовуватися абетка

_m = {0, 1, 2, 3, …, m – 1},

яка містить m «літер» (у вигляді чисел).

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

Таблиця 1.1 – Відповідність поміж українською абеткою та множиною цілих = {0, 1, 2, 3, …, 32}

Літера	Число	Літера	Число	Літера	Число	Літера	Число
А		З		О		Ч
Б		Й		П		Ш
В		І		Р		Щ
Г		Ї		С		Ь
Г′		Й		Т		Ю
Д		К		У		Я
Е		Л		Ф
Є		М		Х
Ж		Н		Ц

 

Таблиця 1. 2 – Відповідність поміж російською абеткою та множиною цілих = {0, 1, 2, 3, …, 31}

Літера	Число	Літера	Число	Літера	Число	Літера	Число
А		И		Р		Ш
Б		Й		С		Щ
В		К		Т		Ь
Г		Л		У		Ы
Д		М		Ф		Ъ
Е		Н		Х		Э
Ж		О		Ц		Ю
З		П		Ч		Я

 

Таблиця 1.3 – Відповідність поміж англійською абеткою та множиною цілих = {0, 1, 2, 3, …, 25}

Літера	Число	Літера	Число	Літера	Число
A		J		S
B		K		T
C		L		U
D		M		V
E		N		W
F		O		X
G		P		Y
H		Q		Z
I		R

Текст з n літерами абетки можна розглядати як n -граму

= (x ₀, x ₁, x ₂, …, x_{n –1}),

де x_i , 0 i < n, для певного цілого n = 1, 2, 3, …

Через позначатимемо множину n -грам, утворених з літер множини .

 

Криптографічне перетворення Е являє собою сукупність перетворень

E = { E ⁽ⁿ⁾: 1 n < };

E ⁽ⁿ⁾: _{m, n m, n}.

Перетворення E ^{( n )} визначає, як кожна n -грама відкритого тексту _{m, n} замінюється на n -граму шифртексту , тобто

= E ^{( n )} (), , _{m , n};

при цьому неодмінною є вимога взаємної однозначності перетворення E ^{( n )} на множину _{m , n}.

Криптографічна система може трактуватися як сімейство криптографічних перетворень

= { E_K: K },

позначених параметром К, називаним ключем.

Множина значень ключа утворює ключовий простір .

 

 

1.2.1 Шифр Цезаря

Історичним прикладом шифру заміни є шифр Цезаря (І ст. до н. е.), описаний істориком давнього Риму Светонієм. Гай Юлій Цезар використовував у своєму листуванні шифр власного винайдення. Стосовно сучасної української мови він полягав у такому. Виписувалась абетка: А, Б, В, Г, …; потім під нею виписувалась та ж сама абетка, але з циклічним зсуненням на три літери ліворуч: