Файл: Опорный конспект.pdf

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

2 Система шифрування Віженера

Шифр Гронсфельда являє собою, власне кажучи, окремий випадок системи шифрування Віженера.

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

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

Таблиця Віженера використовується для зашифрування та розшифрування. Таблиця має два

входи:

верхній рядок символів, який використовується для зчитування літери вихідного відкритого тексту;

крайній лівий стовпець ключа, який використовується для зчитування літери ключа.

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

Нехай ключова послідовність має довжину r, тоді ключ r-алфавітної підстановки є r-рядок

( 0 , 1 , , r 1 ) .

Система шифрування Віженера перетворить відкритий текст x (x0 , x1 , , xn 1 ) у шифротекст

y ( y0 , y1 , , yn 1 ) за допомогою ключа ( 0 , 1 , , r 1 ) відповідно до правила

Tn : xn (x0 , x1 , , xn 1 ) yn ( y0 , y1 , , yn 1 ) ,

Наприклад, з використанням шифру Віженера виконати шифрування відкритого тексту М= “БЕЗ КАЛИНИ НЕМА УКРАЇНИ” ключем Key =“БАРВІНОК”.

Випишемо вихідне повідомлення в рядок і запишемо під ним ключове слово з циклічним повторенням. У третій рядок будемо виписувати літери шифротексту, обумовлені таблицею Віженера (таблиця 2 дадатка Б).

У результаті отримаємо шифротекст, що записано блоками по п'ять букв ВЕЩМІ ЯШЮІН ЦОІЄЯ ББЇҐЇ.

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

Наприклад, виконаємо шифрування без використання таблиць Віженера.

Будемо розглядати український алфавіт (m=33). Поставимо у відповідність кожному символу алфавіту ціле натуральне число, інакше кажучи, пронумеруємо символи алфавіту, починаючи з нуля.

21

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

У результаті одержимо той самий шифротекст, що й у випадку використання таблиць Віженера: ВЕЩМІ ЯШЮІН ЦОІЄЯ ББЇҐЇ .

3 Шифр “Подвійний квадрат Уітстона”

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

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

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

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

Наприклад, використовуючи подвійний квадрат Уітстона, зашифрувати повідомлення «НЕ ЦУРАЙТЕСЬ ТОГО СЛОВА, ЩО МАТИ СПІВАЛА».

Будемо розглядати український алфавіт, який доповнимо символами “.” (крапка), “,” (кома) та “_” (пропуск). Разом алфавіт буде містити 36 символів. Отож візьмемо таблиці розміром 6 6 (рис. 1).

Отже, маємо шифротекст, записаний блоками по 5 символів: ФГХЦЙ ,ЬЦЄК РЧНЦЦ ЇГТЩД ЕРВ.Н ИГТМЯ ПЕЇПС .ЧРУЯ .

22

Розшифрування виконується так само, як і шифрування. Єдина відмінність полягає в тому, що при розшифруванні таблиці міняються місцями (рис. 2).

Шифрування методом подвійного квадрата досить стійкий до розкриття та простий у застосуванні шифр.

Рисунок 2 – Таблиці для розшифрування в шифрі “Подвійний квадрат Уітстона”

4 Одноразова система шифрування

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

одноразова система шифрування. Характерною рисою одноразової системи шифрування є одноразове використання ключової послідовності.

де Ki – i-й елемент випадкової ключової послідовності.

Ключовий простір K одноразової системи являє собою набір дискретних випадкових величин з Zm і містить mn значень.

Процедура розшифрування описується співвідношенням (3.7)

де

Ki – i-й елемент тієї самої випадкової ключової послідовності.

Одноразову систему було винайдено в 1917 р. американцями Дж. Моборном і Г. Вернамом. Для реалізації цієї системи підстановки іноді використовують одноразовий блокнот. Цей блокнот складається з відривних сторінок, на кожній з яких надрукована таблиця з випадковими числами (ключами) Ki . Блокнот виконується у двох екземплярах: один використовується відправником, а інший

- одержувачем. Для кожного символа X i повідомлення використовується свій ключ Ki з таблиці тільки

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

Цей шифр абсолютно надійний, якщо набір ключів Ki дійсно випадковий і непередбачений.

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

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

23

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

5 Шифрування методом Вернама

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

Відкритий текст представляється в коді Бодо (у вигляді п'ятизначних імпульсних комбінацій). У цьому коді, наприклад, буква «А» мала вигляд (+ + – – –). На паперовій стрічці ця буква одержувала такий вигляд (рис. 3) .

Знак «+» означав отвір, а знак «-» – його відсутність. При зчитуванні зі стрічки п'ятірка металевих щупів «пізнавала» отвір (при наявності отвору щуп замикав електричний ланцюг) і на лінії зв'язку посилався імпульс струму (рис. 4).

Рисунок 3 – Паперова стрічка системи Вернама

Рисунок 4 – Імпульс струму в системі Вернама Вернам запропонував електромеханічно покоорди-натно додавати імпульси знаків секретного

тексту з імпульсами гами.

Гама – це секретний ключ, що представляє хаотичний набір літер того самого алфавіту.

Додавання здійснювалося за модулем 2.

0 0 = 0,

0 1 = 1,

1 0 = 1,

1 1 = 0 ,

де

– операція додавання за модулем 2,

0– знак «-» коду Бодо,

1– знак «+» коду Бодо.

Нехай, наприклад, знак гами має вигляд

+ – + – – (10100).

Тоді буква «А» при шифруванні переходить у двійкову комбінацію 01100 (– + + – –). При розшифруванні необхідно повторити покоординатно ту саму операцію

(01100) (10100) = (11000) = А.

Схема шифрування методом Вернама подана на рисунку 5

24