Мета, Хід роботи, Афінний шифр, Коротка теорія, Приклад шифрування за допомогою Афінного шифру,

Аффінний шифр

Коротка теорія

Афінний шифр - це окремий випадок більш загального моноалфавітного шифру підстановки.

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

Де - номер літери, що отримується в результаті шифрування,

- Номер шифрованої літери;

б, в – ключі шифрування;

m – розмір алфавіту.

При цьому на ключ накладається деяке обмеження: значення ключа a і розмірності алфавіту m повинні бути взаємно простими.

Де - обернене до б число по модулю m, тобто .

Число б оборотне тільки в тому випадку, якщо воно взаємно просте до m. Всі оборотні б для латинського алфавіту, розмір якого дорівнює 26, можна подати у вигляді списку з 13 чисел: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.

Приклад шифрування за допомогою Афінного шифру

Для шифрування використали латинський алфавіт, що з 26 букв. Спробуємо зашифрувати та розшифрувати слово «master», використовуючи при цьому Аффінний шифр. Наприклад будемо використовувати такі ключі: б=5, в=7.

Літера m має номер 12, тоді зашифрований номер дорівнюватиме (5*12+7) mod 26 = 15, що відповідає букві p
Літера a має номер 0, тоді зашифрований номер дорівнюватиме (5*0+7) mod 26 = 7, що відповідає букві h
Літера s має номер 18, тоді зашифрований номер дорівнюватиме (5*18+7) mod 26 = 19, що відповідає букві t
Літера t має номер 19, тоді зашифрований номер дорівнюватиме (5*19+7) mod 26 = 24, що відповідає букві y
Літера e маєномер 4, тоді зашифрований номер дорівнюватиме (5*4+7) mod 26 = 1, що відповідає букві b
Літера r має номер 17, тоді зашифрований номер дорівнюватиме (5*17+7) mod 26 = 14, що відповідає букві o

В результаті шифрування вийшов рядок phtybo

Розшифровувати буде рядок, отриманий у прикладі (phtybo)

Для початку потрібно знайти . а* за модулем 26 має давати одиницю. Отже, нам підходять результати 27, 53, 79, 105 тощо. Т.к. а = 5, нам потрібно число, що закінчується на 5. 105 підходить. 105/5=21, звідси випливає, що =21

Літера p має номер 15, тоді розшифрований номер дорівнюватиме 21*(15-7) mod 26 = 12, що відповідає букві m
Літера h має номер 7, тоді розшифрований номер дорівнюватиме 21*(7-7) mod 26 = 0, що відповідає букві a
Літера t має номер 19, тоді розшифрований номер дорівнюватиме 21*(19-7) mod 26 = 18, що відповідає букві s
Літера y має номер 24, тоді розшифрований номер дорівнюватиме 21*(24-7) mod 26 = 19, що відповідає букві t
Літера b має номер 1, тоді розшифрований номер дорівнюватиме 21*(1-7) mod 26 = 4, що відповідає букві e
Літера o має номер 14, тоді розшифрований номер дорівнюватиме 21*(14-7) mod 26 = 17, що відповідає букві r

Вийшло «master» - Наш початковий рядок.

Реалізація шифру

Було реалізовано алгоритм шифрування мовою програмування C#. Програма являє собою форму з кнопками та полями для заповнення:

Малюнок 1 - Головна форма програми

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

Малюнок 2. - Приклад роботи програми

Опис алгоритму роботи програми

На вхід програми подаються 2 ключі (a та b відповідно), а також вхідний рядок у вигляді масиву символів. Далі йде перевірка на коректність ключів. Якщо ключі коректні, перевірка, чи є введені символи літерами латинського алфавіту. Якщо символ є таким, шифрується, якщо ні - символ пропускається. Після закінчення символів виводиться результат. При розшифруванні, програма знаходить зворотний для ключа і далі аналогічно зашифрування.

Криптоаналіз

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

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

Малюнок 3 - шифртекст

Проведемо аналіз тексту за допомогою сервісу http://www.abakbot.ru/

Малюнок 4 - Частотний аналіз

Також візьмемо реальну таблицю частотивикористання букв латинського алфавіту.

Малюнок 5. - Частота використання англійських букв

Ми, що у нашому шифртексті найчастіше зустрічається буква h. На реальному алфавіті найчастіше зустрічається буква e. Виходячи з цього можна припустити, що буква e зашифрувалася як h. Літера e має номер 4, а літера h номер 7. Отже a*4+b=7,33,59 тощо. Перебравши кілька варіантів, дістанемося до a = 11, b = 15. 11 * 4 +15 = 59. Підставивши в програму a = 11 і b = 15, отримаємо англійський текст, що читається, зображений на малюнку 6.