 |
Методи шифрування з симетричним ключем
|
|
|
|
Методи заміни. Сутність методів заміни (підстановки) полягає в заміні символів вихідної інформації, записаних в одному алфавіті, символами з іншого алфавіту за певним правилом [56]. Найпростішим є метод прямої заміни. Символам Так, вихідного алфавіту Ао, за допомогою яких записується початкова інформація, однозначно ставляться у відповідність символи Су шифрувального алфавіту Аb У найпростішому випадку обидва алфавіту можуть складатися з одного і того ж набору символів. Наприклад, обидва алфавіту можуть містити літери російського алфавіту. Завдання відповідності між символами обох алфавітів здійснюється за допомогою перетворення числових еквівалентів символів вихідного тексту То, довжиною К символів за певним алгоритмом. Алгоритм моноалфавитной заміни може бути представлений у вигляді послідовності кроків. Крок 1. Формування числового кортежу лота, шляхом заміни кожного символу s^ е То (i=l,K),, представленого в вихідному алфавіті Ао розміру [lxR], на число hoi(soi), відповідне порядковому номеру символу сой в алфавіті Ао. Крок 2. Формування числового кортежу лих шляхом заміни кожного числа кортежу Loh на відповідне число кп кортежу лих, що обчислюється за формулою: hu = (k,xhoi(soi)+k2)(mod R), де ki - десятковий коефіцієнт; k2 - коефіцієнт зсуву. Вибрані коефіцієнти, ki, k2 повинні забезпечувати однозначну відповідність чисел ho, та hi, а при отриманні hi, = 0 виконати заміну hi, = R. Крок 3. Отримання шифртекста Ti шляхом заміни кожного числа h], (si,) кортежу L]h відповідним символом Si, e Ti (i=l,k) алфавіту шифрування А] розміру [1XR]. Крок 4. Отриманий шифртекст розбивається на блоки фіксованої довжини Ь. Якщо останній блок виявляється неповним, то в кінець блоку поміщаються спеціальні символи-заповнювачі (наприклад, символ *).
|
|
|
Рис 13. Класифікація методів криптографічного перетворення інформації
Приклад.
Вихідними даними для шифрування є:
Т0 = <МЕТОД_ШИФРОВАНИЯ>;
Ао = <АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩ
ЪЫЬЭЮЯ >;
Покрокове виконання алгоритму приводить до отримання таких результатів.
Крок 1. Loh = <12,6,18,14,5,32,24,9,20,16,14,3,1,13,9,31>.
Крок 2. L1h = <19,1,5,25,30,15,23,10,11,31,25,24,18,22,10,12>.
Крок 3. T1 = <С О Я Г Б Д И Ь Ч У Г Ц К П М Х>.
Крок 4. T2 = < С О Я Г Б Д И Ь Ч У Г Ц К П М Х>.
При розшифруванні спочатку усувається розбиття на блоки, тобто отримується неперервний шифротекст Т1 довжиною К символів. Розшифровування здійснюється шляхом розв’язання цілочислового рівняння.
При відомих цілих величинах kbk2, hh та R величина ho обчислюється методом перебору п. Послідовне застосування цієї процедури до всіх символів шифртексту призводить до його розшифрування. За умовами наведеного прикладу може бути побудована таблиця заміни, в якій взаємозамінні символи розташовуються в одному стовпці (табл. 1).
Таблиця 1
Таблиця заміни
Використання таблиці заміни значно спрощує процес шифрування. При шифруванні символ вихідного тексту порівнюється з символами рядка Отже, таблиці. Якщо сталася збіг в і-му стовпці, то символ вихідного тексту замінюється символом з рядка Cі, що знаходиться в тому ж стовпці таблиці. Розшифрування здійснюється аналогічним чином, але вхід в таблицю проводиться у рядку Sn. Основним недоліком методу прямої заміни є наявність одних і тих же статистичних характеристик вихідного і закритого тексту. Знаючи, якою мовою написаний вихідний текст і частотну характеристику вживання символів алфавіту цієї мови, криптоаналітика шляхом статистичної обробки перехоплених повідомлень може встановити відповідність між символами обох алфавітів. Істотно більш стійкими є методи поліалфавітной заміни. Такі методи засновані на використанні несколких алфавітів для заміни символів вихідного тексту. Формально поліалфавітну заміну можна представити таким чином. При N-алфавітної заміни символ сой з вихідного алфавіту Ао замінюється символом вц з алфавіту Аь S02 замінюється символом S22 з алфавіту Аг і так далі. Після заміни SON символом S ММ з AN символ SO (N + D заміщається символом Si (N + i) З алфавіту Аi і так далі.
|
|
|
Найбільшого поширення набув алгоритм поліалфавітної заміни з використанням таблиці (матриці) Віжінера Тв, яка являє собою квадратну матрицю [R x R], де R - кількість символів у використовуваному алфавіті. У першому рядку розташовуються символи в алфавітному порядку. Починаючи з другого рядка, символи записуються зі зрушенням ліворуч на одну позицію. Виштовхувані символи заповнюють позиції праворуч (циклічний зсув), які звільняються. Якщо використовується російський алфавіт, то матриця Віжінера має розмірність [32x32]
(Рис. 16).
АБВГД ЪЭЮЯ_
ВВГДЕ ЭЮЯ_А
Тв= ВГДЕЖ ЮЯ_АБ
_АБВГ ЫЪЭЮЯ
Рис. 16. Матриця Віжінера
Шифрування здійснюється за допомогою ключа, що складається з М неповторюваних символів. З повної матриці Віжінера виділяється матриця шифрування Тш, розмірністю [(M+1),R]. Вона включає перший рядок і рядки, перші елементи яких співпадають з символами ключа. Якщо як ключа вибрано слово <ЗОНД>, то матриця шифрування містить п'ять рядків
(Рис. 17).
АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_
ЗИКЛМН0ПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБВГДЕЖ
ОПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБВГДЕЖЗИКЛМН
Я0ПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБВГДЕЖЗИКЛМ
ДЕЖЗИКЛМН0ПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБВГ
Рис. 17. Матриця шифрування для ключа <ЗОНД>
Алгоритм шифрування з допомогою таблиці Віжінера являє собою наступну послідовність кроків.
Крок 1. Вибір ключа К довжиною М символів.
Крок 2. Побудова матриці шифрування Тш = (Ьу) розмірністю [(M +1), R] для вибраного ключа К.
Крок 3. Під кожним символом S ^ вихідного тексту довжиною І
символів розміщується символ ключа км (рис. 20). Ключ повторюється необхідну кількість разів.
Крок 4. Символи вихідного тексту послідовно заміщуються символами, вибираними з Тш за наступним правилом:
1) визначається символ km ключа К, відповідний заміщає символу sог,
|
|
|
2) знаходиться рядок я в Тш, для якої виконується умова кт = Ьп_______,
3) визначається стовпець j, для якого виконується умова:
4) символ sог заміщається символом Ь ^.
Крок 5. Отримана зашифрована послідовність розбивається на блоки певної довжини, наприклад, по чотири символи. Останній блок доповнюється, при необхідності, службовими символами до повного об’єму. Розшифрування здійснюється в такій послідовності:
Крок 1. Під шифртекста записується послідовність символів ключа за аналогією з кроком 3 алгоритму шифрування.
Крок 2. Послідовно вибираються символи Sjr з шифртекста і відповідні символи ключа km. У матриці Тш визначається рядок я, для якої виконується умова km = Ь: 1. У рядку я визначається елемент by = Sir. У розшифрований текст на позицію г поміщається символ bij.
Крок 3. Розшифрований текст записується без поділу на блоки. Прибираються службові символи.
Приклад.
Потрібно за допомогою ключа К = <ЗОНД> зашифрувати вихідний текст Т = <БЕЗОБЛАЧНОЕ_ НЕБО>.
Механізми шифрування та розшифрування представлені на рис. 18.
Вихідний текст БЕЗОБЛАЧНОЕ_ НЕБО
Ключ ЗОНД ЗОНД ЗОНД ЗОНД
Текст після заміни
ИУФТИШНЫФГФУОТ
Розшифрований текст БЕЗО БЛАЧ НОЕ_ НЕБО.
Вихідний текст БЕЗОБЛАЧНОЕ_НЕБО j
Шуканий текс Б Е З О Б Л А Ч Н О Е_Н Е Б О
Ключ З О Н Д З О Н Д З О Н Д З О Н Д
Текст після заміни И У Ф Т И Ш Н Ы Ф Ы Т Г Ф У О Т
Шифротекст И У Ф Т И Ш Н Ы Ф Ы Т Г Ф У О Т
Ключ З О Н Д З О Н Д З О Н Д З О Н Д
Розшифрований текс Б Е З О Б Л А Ч Н О Е Н Е Б О
Шуканий текст Б Е З О Б Л А Ч Н О Е _Н Е Б О
Рис. 18. Приклад щифрування з використанням матриці Віжінера
Крипостійкість методів поліалфавітной заміни значно вище методів простої заміни, оскільки одні й ті ж символи вихідної послідовності можуть замінюватися різними символами. Проте стійкість шифру до статистичних методів криптоаналізу залежить від довжини ключа. Для підвищення криптостійкості може використовуватися модифікована матриця шифрування. Вона представляє собою матрицю розмірності [11,R], де R число символів алфавіту. У першому рядку розташовуються символи в алфавітному порядку. Інші 10 рядків нумеруються від 0 до 9. У цих рядках символи розташовуються випадковим чином. Як ключі використовуються, наприклад, неперіодичні нескінченні числа n, е та інші. Черговий n-й символ вихідного тексту замінюється відповідним символом з рядка матриці шифрування, номер якої збігається з n-ю цифрою нескінченного числа.
|
|
|
Методи перестановки. Суть методів перестановки полягає в поділі вихідного тексту на блоки фіксованої довжини і подальшої перестановці символів всередині кожного блоку за певним алгоритмом [56]. Перестановки виходять за рахунок різниці шляхів записи вихідної інформації та шляхів зчитування зашифрованої інформації в межах геометричної фігури. Прикладом найпростішої перестановки є запис блоку вихідної інформації в матрицю по рядках, а зчитування - по стовпцях. Послідовність заповнення рядків матриці і зчитування зашифрованої інформації по стовпцях може задаватися ключем. Крипостійкість методу залежить від довжини блоку (розмірності матриці). Так для блоку довжиною 64 символу (розмірність матриці 8х8) можливі 1.6*109 символів комбінацій ключа. Для блоку довжиною 256 символів (матриця розмірністю 16x16) число можливих ключів досягає 1,4 х1026. Рішення завдання перебору ключів в останньому випадку навіть для сучасних ЕОМ представляє істотну складність. Перестановки використовуються також у методі, заснованому на застосуванні маршрутів Гамільтона. Цей метод реалізується шляхом виконання наступних кроків.
Крок 1. Вихідна інформація розбивається на блоки. Якщо довжина шіфруемий інформації не кратна довжині блоку, то на вільні місця останнього блоку поміщаються спеціальні службові символи-заповнювачі (наприклад, *).
Крок 2. Символами блоку заповнюється таблиця, в якій для кожного порядкового номера символу в блоці відводиться цілком певне місце (рис. 18).
Крок 3. Зчитування символів з таблиці здійснюється по одному з маршрутів. Збільшення числа маршрутів підвищує крипостійкість шифру.
Маршрути вибираються або послідовно, або їх черговість задається ключем К.
Крок 4. Зашифрована послідовність символів розбивається на блоки фіксованої довжини L. Величина L може відрізнятися від довжини блоків, на які розбивається вихідна інформація на кроці 1.
Розшифрування проводиться в зворотному порядку. Відповідно до ключа вибирається маршрут і заповнюється таблиця згідно з цим маршрутом.
Таблиця
Маршрут № 1
Маршрут № 2
Рис. 18. Варіант восьмиелементної таблиці та маршрутів Гамільтона
З таблиці символи зчитуються в порядку проходження номерів елементів. Нижче наводиться приклад шифрування інформації з використанням маршрутів Гамільтона. Нехай потрібно зашифрувати вихідний текст То = <МЕТОДЫ_ПЕРЕСТАНОВКИ> K=<2, 1. 1>, L=4. Для шифрування використовуються таблиця і два маршрути, представлені на рис. 18. Для заданих умов маршрути із заповненими матрицями мають вигляд, показаний на рис. 19
|
|
|
Маршрут № 2
Маршрут №
.Маршрут № 1
Рис. 19. Приклад шифрування з використанням маршрутів Гамільтона
Крок 1. Оригінальний текст розбивається на три блоки:
Б1 =<МЕТОДЫ_П>;
Б2 = <ЕРЕСТАНО>;
БЗ = <ВКИ*****>.
Крок 2. Заповнюються три матриці з маршрутами 2,1,1 (рис.19).
Крок 3. Отримання шифртекста шляхом розстановки символів у відповідності з маршрутами.
Tj = <ОП_ТМЕЫДЕСРЕТАОНИ*КВ****>.
Крок 4. Розбиття на блоки шифртекста
Т, = <ОП_Т МЕЫД ЕСРЕ ТАОН И*КВ ****>.
У практиці велике значення має використання спеціаль-них апаратних схем, що реалізують метод перестановок (рис. 29). Зашифрування Розшифрування
Зашифрування Розшифрування
Рис. 20. Схема перестановок
Паралельний двійковий код блоку вихідної інформації (наприклад, два байти) подаються на схему. За рахунок внутрішньої комутації в схемі здійснюється перестановка біт в межах блоку. Для розшифрування блоку інформації входи і виходи схеми міняються місцями [49]. Методи перестановок просто реалізуються, але мають два істотні недоліки. По-перше, вони допускають розкриття шифртекста за допомогою статистичної обробки. По-друге, якщо вихідний текст розбивається на блоки довжиною До символів, то кріптоайалітіку для розкриття шифру достатньо направити в систему шифрування К-1 блок тестової інформації, в яких всі символи за винятком одного однакові.
Аналітичні методи шифрування. Для шифрування інформації можуть використовуватися аналітичні перетворення [8]. Найбільшого поширення набули методи шифрування, засновані на використанні матричної алгебри. Зашифрування k-го блоку вихідної інформації, представленого у вигляді вектора В = 
, здійснюється шляхом множенія матриці-ключа А = || щ \ вектора Вк. В результаті множення виходить блок шифртекстe у вигляді вектора Ck= Iks ||, де елементи вектора Ск визначаються за формулою:
Розшифрування інформації здійснюється шляхом послідовного множення векторів С^ і матриці А"1, зворотної до матриці А. Приклад шифрування інформації з використанням алгебри матриць. Нехай необхідно зашифрувати і розшифрувати слово
То = < ЗАБАВА > з використанням матриці-ключа А:
Для зашифрування вихідного слова необхідно виконати наступні кроки.
Крок 1. Визначається числовий еквівалент вихідного слова як послідовність відповідних порядкових номерів букв слова Те:
Те = <8, 1, 2, 1, 3, 1>.
Крок 2. Множення матриці А на вектори Ві = {8, 1, 2} та В* = {1, 3, 1}:
Крок 3. Зашифроване слово записується у вигляді послідовності чисел Ті = <28, 35, 67, 21, 26, 38>. Розшифрування слова здійснюється наступним чином.
Крок 1. Обчислюється визначник |А| = -115.
Крок 2. Визначається приєднана матриця А*, кожний елемент якої є алгебраїчним доповненням елемента щ матриці А
Крок 3. Отримується транспонована матриця АТ
Крок 4. Визначається обернена матриця А"1 за формулою:
А"1 = АТ/ |А|.
В результаті обчислень обернена матриця матиме вигляд:
Крок 4. Визначаються вектори В1 та В2:
В1 = А-1С1; В2 = А-1С2.
Крок 5. Числовий еквівалент розшифрованого слова Тэ=<8, 1,2, 1, 3, 1 > замінюється символами, в результаті чого отримується слово То = <ЗАБАВА>.
Адитивні методи шифрування. Сутність адитивних методів шифрування полягає в послідовному підсумовуванні цифрових кодів, відповідних символам вихідної інформації, з послідовністю кодів, яка відповідає деякому кортежу символів [56]. Цей кортеж називається гаммою. Тому адитивні методи шифрування називають також гаммуванням. Для даних методів шифрування ключем є гамма. Крипостійкість адитивних методів залежить від довжини ключа і рівномірності його статистичних характеристик. Якщо ключ коротший, ніж шифрована послідовність символів, то шифротекст може бути розшифрований криптоаналітичними методами. Чим більша різниця довжин ключа та вихідної інформації, тим вища ймовірність успішної атаки на шифртекст. Якщо ключ являє собою неперіодичну послідовність випадкових чисел, довжина якої перевищує довжину шифрованої інформації, то без знання ключа розшифрувати шифртекст практично неможливо. Як і для методів заміни як ключ можуть використовуватися неповторювані послідовності цифр, наприклад, в числах к, е та інших. На практиці найбільш ефективними і поширеними є адитивні методи, в основу яких покладено використання генераторів (датчиків) псевдовипадкових чисел. Генератор використовує вихідну інформацію щодо малої довжини для отримання практично нескінченної послідовності псевдовипадкових чисел.
Для отримання послідовності псевдовипадкових чисел (ПВЧ) можуть використовуватися конгруентні генератори. Генератори цього класу виробляють псевдовипадкові послідовнності чисел, для яких можуть бути строго математично визначені такі основні характеристики генераторів як періодичність і випадковість вихідних послідовностей. Серед конгруентних генераторів ПСЧ виділяється своєю простотою і ефективністю лінійний генератор, що виробляє псевдослучайную послідовність чисел T (i) відповідно до співвідношенням
T(i+1) = (a-T(i) + с) mod m,
де а, с - константи, Т(0) - вихідна величина, вибрана як породжуюче число.
Період повторення такого датчика ПСЧ залежить від величин а і с. Значення т зазвичай приймається рівним 2s, де s - довжина слова ЕОМ у бітах. Період повторення послідовності генерованих чисел буде максимальним тоді і тільки тоді, коли с - непарне число і a (mod 4) = 1, [39]. Такий генератор може бути порівняно легко створений як апаратними засобами, так і програмно.
|
|
|
