Вивчення криптографічних методів підстановки заміни

а

б

в

г

д

е

е

ж

з

і

ї

до

л

м

н

про

п

р

з

т

у

Ф

х

ц

ч

ш

щ

'

и

ь

е.

ю

я

до

л

м

н

про

п

р

з

т

у

ф

х

ц

ч

ш

щ

'

и

ь

е.

ю

я

а

б

в

г

д

е

е

ж

з

і

ї

н

про

п

р

з

т

у

ф

х

ц

ч

ш

щ

'

и

ь

е.

ю

я

а

б

в

г

д

е

е

ж

з

і

ї

до

л

м

і

ї

до

л

м

н

про

п

р

з

т

у

ф

х

ц

ч

ш

щ

'

и

ь

е.

ю

я

а

б

в

г

д

е

е

ж

з

г

д

е

е

ж

з

і

ї

до

л

м

н

про

п

р

з

т

у

ф

х

ц

ч

ш

щ

'

и

ь

е.

ю

я

а

б

в

а

б

в

г

д

е

е

ж

з

і

ї

до

л

м

н

про

п

р

з

т

у

ф

х

ц

ч

ш

щ

'

и

ь

е.

ю

я

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

У

Про

З

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

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

Афінна система підстановок Цезаря

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

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

Визначимо в такій системі перетворення Е _{a, b:} Z _m → Z _m:

Е _{a, b} (x) = ax + b mod m,

де в якості ключа k = (A, b) використовується пара цілих чисел, які відповідають умовам 0   a, b <m, і НОД (а, m) = 1.

У даному перетворенні буква, відповідна числа x у відкритому тексті, замінюється на літеру шифртекста, відповідну числовому значенню y = (ax + b) mod m (наприклад m = 26 в латинському алфавіті).

Слід зауважити, що перетворення Е _{a, b} (x) є взаємно однозначним відображенням на безлічі Z _m тільки у тому випадку, якщо НОД (а, m) = 1, тобто а і m повинні бути взаємно простими числами.

Це умова взаємної простоти необхідно для забезпечення ін'єктивні відображення Е _{a, b} (x) = ax + b mod m. Якщо воно не виконується, можлива ситуація, коли дві різні букви відображаються в одну (виникає неоднозначність розшифрування), а деякі букви відсутні в шифртекст, оскільки ніякі букви в них не відображаються.

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

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

Криптосистема Хілла і її окремий випадок шифр Плейфеpа

Ці криптосистеми також належать до класу шифрів, заснованих на аналітичних перетвореннях шифрованих даних як і афінна система шифрування. Вони засновані на підстановці не окремих символів, а n - грам (шифр Хілла) або 2-грам (шифр Плейфеpа). При більш високій криптостійкості вони значно складніше для реалізації і вимагають досить великої кількості ключової інформації.

Алгебраїчний метод, узагальнюючий афінних підстановку Цезаря для шифрування n-грам, був сформульований Лестером С. Хіллом.

Шифрування ведеться шляхом виконання множення вектора на матрицю. Матриця є ключем шифрування. Відкритий текст розбивається на n-грами - блоки довжиною n, що дорівнює розмірності матриці і кожна n-грами х = (х _0, х _1, х _{2, ...,} х _n-1) розглядається як вектор.

Ключова матриця Т розміром п × п виду Т = {t _{i, j},} i, j = 0,1, ..., n - 1 задає відображення, що є лінійним перетворенням:

Т: Z _{m, n} → Z _{m, n,} Т: х → у; у = Тх,

де .

Для розшифрування шифртекста необхідно виконати зворотне перетворення:

х = Т ^-1 у.

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

Т Т ^-1 = Т ^-1 Т = I, де I - одинична матриця.

Доведено, що для цього необхідно, щоб визначник матриці det Т, не ділився на будь-яке просте р, яке ділить m.

Шифри гамування

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

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

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

Слід зазначити, що при блочному шифруванні відкриті дані розбивають на блоки Т ₀ ⁽ⁱ⁾ однакової довжини, зазвичай по 64 біта. Гамма шифру виробляється у вигляді послідовності блоків γ _i аналогічної довжини.

Рівняння зашифрування можна записати у вигляді

c _i = γ _i  m _i, i = 1, ..., M,

де c _i - i-ий блок шифртекста; γ _i - i-ий блок гами шифру; m _i - i-ий блок відкритого тексту; М - кількість блоків відкритого тексту.

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

m _i = γ _i   c _i, i = 1, ..., M.

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

Щоб отримати лінійні послідовності елементів гами, довжина яких перевищує розмір шифрованих даних, використовуються датчики псевдовипадкових чисел (ПСЧ). Одним із добрих конгруентних генераторів є лінійний конгруентний датчик ПСЧ. Він виробляє послідовності псевдовипадкових чисел γ _i, описувані співвідношенням

γ _{i +1} = (а γ _i + B) mod m,

де а і b - константи; γ ₀ - вихідна величина, вибрана в якості породжує числа. Очевидно, що ці три величини і утворюють ключ.

Такий датчик генерує псевдовипадкові числа з певним періодом повторення, що залежать від вибраних значень а і b. Необхідно вибирати числа a і b такі, щоб період був максимальним. Як показано Д. Кнутом, це можливо тоді і тільки тоді, коли b - непарне і взаємно просте з m, і величина а mod 4 = 1. За іншими рекомендаціями b - взаємно просте з m, і а непарне.

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

R _i = (S _i + G) mod (k -1),

де R _i, S _i, G - символи відповідно зашифрованого, вихідного тексту і гамми.

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

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

Таблиця 8 - Приклад шифрування гаммированием

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

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

Як гами може бути використана будь-яка послідовність випадкових символів, наприклад, послідовність цифр числа p і т.п. При шифруванні за допомогою, наприклад, апаратного шифратора послідовність гами може формуватися за допомогою датчика псевдовипадкових чисел (ПСЧ). В даний час розроблено декілька алгоритмів роботи таких датчиків, які забезпечують задовільні характеристики гами.

Метод гамування стає безсилим, якщо зловмисникові стає відомий фрагмент вихідного тексту і відповідна йому шифрограма. Простим вирахуванням за модулем виходить відрізок псевдовипадковою послідовності (ПСП) і по ньому відновлюється вся послідовність. Зловмисники може зробити це на основі припущень про зміст вихідного тексту. Так, якщо більшість посилаються повідомлень починається зі слів "СОВ.СЕКРЕТНО", то криптоаналіз всього тексту значно полегшується. Це слід враховувати при створенні реальних систем інформаційної безпеки.

Шифр Вернама

Цей метод є окремим випадком шифрування гаммированием для двійкового алфавіту (при значенні модуля m = 2).

Конкретна версія цього шифру, запропонована в 1926 році співробітником фірми AT & T Вернама, використовує двійкове представлення символів вихідного тексту. Кожна літера в повідомленні в алфавіті, розширеному деякими додатковими знаками, спочатку переводилася з використанням телеграфного коду Бодо в пятібітовий символ. Тобто алфавіт криптосистеми представляє собою безліч Z ₃₂ всіх пятібітових послідовностей.

Ключ k = (K _0, k ₁ ,..., k _{n -1),} де "k _i Î Z ₃₂ записувався на паперовій стрічці. При шифруванні ключ додавався до початкового тексту підсумовуванням за модулем 2.

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

y _i = x _i  k _i, i = 1, ..., n

Тут х ₁ х ₂ ... x _п - відкритий текст, k ₁ k ₂ ... k _п - ключ, y ₁ y ₂ ... y _п - шифрований текст.

Розшифрування полягає у додаванні за модулем 2 символів у шифртекста з тією ж послідовністю ключів k:

y  k = x.

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

Полібіанскій квадрат

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

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

Шифрувальні таблиці Трісемуса

У 1508 р. абат з Німеччини Йоганн Трісемус написав друковану роботу з криптології під назвою "Поліграфія". У цій книзі він вперше систематично описав застосування шифруючих таблиць, заповнених алфавітом у випадковому порядку. Для отримання такого шифру заміни зазвичай використовувалися таблиця для запису літер алфавіту і ключове слово. У таблицю спочатку вписувалося по рядках ключове слово, причому повторювані букви відкидалися. Потім ця таблиця доповнювалася не увійшли до неї літерами алфавіту по порядку.

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

Приклад. Для російського алфавіту шифруюча таблиця може мати розмір 4x8. Виберемо в якості ключа слово бандеролі. Шифруюча таблиця набуде вигляду:

Таблиця 9 - Приклад використання шифрів таблиці Трісемуса

Б	А	Н	Д	Е	Р	Про	Л
Ь	У	Г	Ж	3	І	І	До
М	П	З	Т	У	Ф	X	Ц
Ч	Ш	Щ	И	'	Е	Ю	Я

При шифруванні за допомогою цієї таблиці

повідомлення В И Л Е Т А Є М П Я Т О Г О

отримуємо шифртекст П Д К З У З Ч Ш Л И Й З Й

Шифр Вінстона

У 1854 р. англієць Чарльз Уїтстона розробив новий метод шифрування біграм, який називають "подвійним квадратом". Свою назву цей шифр отримав за аналогією з полібіанскім квадратом. На відміну від полібіанского шифр "подвійний квадрат" використовує відразу дві таблиці, що розміщені по одній горизонталі, а шифрування йде біграм (парами), як у шифрі Плейфера. Ці не настільки складні модифікації призвели до появи на світ якісно нової криптографічного системи ручного шифрування. Шифр "подвійний квадрат" виявився дуже надійним і зручним і застосовувався Німеччиною навіть в роки другої світової війни.

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

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

Таблиця 10 - Приклад використання шифру Вінстона

Припустимо, що шифрується біграм вихідного тексту ІЛ. Буква І знаходиться у колонці 1 і рядку 2 лівої таблиці. Буква Л знаходиться в стовпці 5 і рядку 4 правої таблиці. Це означає, що прямокутник утворений рядками 2 і 4, а також стовпцями 1 лівої таблиці та 5 правої таблиці. Отже, в біграм шифртекста входять буква О, розташована в стовпці 5 і рядку 2 правої таблиці, і буква В, розташована у стовпці 1 та рядку 4 лівої таблиці, тобто отримуємо біграм шифртекста ОВ.

Якщо обидві літери біграм повідомлення лежать в одному рядку, наприклад ТО, то біграм повідомлення ТО перетворюється на біграм шифртекста ЖБ. Аналогічним чином шифруються всі біграм повідомлення:

Повідомлення ПР ІЛ ЕТ АЮ _ш ЄС ТО ГО

Шифртекст ПЕ ОВ ЩН ФМ Еш РФ БЖ ДЦ

Шифрування методом "подвійного квадрата" дає дуже стійкий до розтину і простий у застосуванні шифр. Злом шифртекста "подвійного квадрата" вимагає великих зусиль, при цьому довжина повідомлення повинна бути не менше тридцяти рядків.