Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методичні вказівки до циклу лабораторних робіт
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки
Предмет:
Захист інформації в комп’ютерних системах
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ І СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Методичні вказівки
до циклу лабораторних робіт
з курсу “Захист інформації в комп’ютерних системах ” для студентів базового напрямку 6.050102 “Комп’ютерна інженерія”
Затверджено на засіданні кафедри Електронних Обчислювальних Машин Протокол № 1 від 28 серпня 2012 року
Львів – 2012
Методичні вказівки до циклу лабораторних робіт з курсу „Захист інформації в комп’ютерних системах” для студентів базового напрямку 6.050102 / Укладачі: В.М. Сокіл, О.М. Колодчак, А.А. Андрух – Львів: Національний університет “Львівська політехніка”, 2012, 23 с.
Укладачі: В.М. Сокіл, к.т.н., доц. кафедри ЕОМ
О.М. Колодчак, асистент кафедри ЕОМ
А.А. Андрух, ст.викладач кафедри ЕОМ
Відповідальний за випуск: М.М. Кузьо, к.т.н., доц. кафедри ЕОМ
Рецензент: В.А. Голембо, к.т.н., доц. кафедри ЕОМ.
Лабораторна робота № 1
Шифр моноалфавітної заміни (шифр Цезаря)
Мета роботи: ознайомитись з основами класичної техніки шифрування – шифрами моноалфавітної заміни, та типовим прикладом шифрів даного виду – шифром Цезаря.
Теоретичні відомості
При використанні моноалфавітної заміни окремі букви відкритого тексту заміняються іншими буквами або числами або якимись іншими символами. Якщо відкритий текст розглядається як послідовність бітів, то підстановка зводиться до заміни заданих послідовностей бітів відкритого тексту заданими послідовностями бітів шифрованого тексту.
Найдавнішим і найпростішим з відомих підстановочних шифрів є шифр, що використовувався Юлієм Цезарем. У шифрі Цезаря кожна буква алфавіту замінюється буквою, що перебуває на три позиції далі в цьому ж алфавіті. Найпростіше побачити це на прикладі.
Відкритий текст: meet me after the toga party Шифрований текст: PHHW PH DIWHU WKH WRJD SDUMB
Зверніть увагу на те, що алфавіт вважається "циклічним", тому після Z іде А. Визначити перетворення можна, перелічивши всі варіанти, як показано нижче.
Відкритий текст: a b c d e f g h I j k l m n o p q r s t u v w y z
Шифрований текст: D E F G H I J K L M N O P Q R S T U W Y Z
Якщо кожній букві призначити числовий еквівалент (а = 1, b = 2 і т.д.), то алгоритм можна показати наступними формулами. Кожна буква відкритого тексту р заміняється буквою шифрованого тексту З:
C = E(p) = (p+3) mod (26)
У загальному випадку зміщення може бути будь-яким, тому узагальнений алгоритм Цезаря записується формулою
C = E(p) = (p+k) mod (26)
де к приймає значення в діапазоні від 1 до 25. Алгоритм дешифрування також простий:
p = D(C) = (C - k) mod (26)
Якщо відомо, що певний текст був шифрований за допомогою шифру Цезаря, то за допомогою простого перебору всіх варіантів розкрити шифр дуже просто - для цього досить перевірити 25 можливих варіантів ключів. На рис. 1 показані результати застосування цієї стратегії до зазначеного вище повідомлення. У цьому випадку відкритий текст розпізнається в третьому рядку.
Застосування методу послідовного перебору всіх можливих варіантів виправдано наступними трьома важливими характеристиками даного шифру.
Відомі алгоритми шифрування й дешифрування.
Необхідно перебрати всього 25 варіантів.
Мова відкритого тексту відома та легко розпізнається.
Вказівки щодо реалізації:
Шифр Цезаря реалізує шифрування повідомлення шляхом «зсуву» усіх символів повідомлення на певне число кк (в оригінальному шифрі дане число дорівнювало 3).
Якщо буква вихідного повідомлення мала позицію jj у вихідному алфавіті, то в зашифрованому повідомленні вона буде замінюватися буквою, що знаходиться на позиції кк+jj. Нехай маємо вихідне повідомлення: “I remember that September”. Будемо використовувати латинський алфавіт зі стандартною послідовністю слідування символів в алфавіті. Результати шифрування наведені в таблиці нижче:
Пояснення до таблиці:
1-й рядок - фраза для шифрування;
2-й рядок - номера букв фрази для шифрування в латинському алфавіті;
3-й рядок - номера букв фрази для шифрування, збільшені на 3;
4-й рядок - результат «ділення по модулю 26» чисел 3-го рядка;
5-й рядок - зашифрована фраза
Спроектуємо форму додатку, що дозволить нам вводити повідомлення для шифрування, крок та виводити зашифроване повідомлення:
Завдання:
1. Розробити програму, що реалізує шифрування вихідного повідомлення за допомогою шифру Цезаря. Повідомлення, що необхідно зашифрувати, має бути задано українською мовою. В якості ключа шифрування обирається номер студента у списку групи.
2. Оформити та захистити звіт.
Лабораторна робота № 2
Перестановочний шифр
Мета роботи: ознайомитись з основами класичної техніки шифрування – перестановочними шифрами.
Теоретичні відомості
Розглянутий вище метод ґрунтувався на заміщенні символів відкритого тексту різними символами шифрованого тексту. Принципово інший клас перетворень будується на використанні перестановок букв відкритого тексту. Шифри, створені за допомогою перестановок, називають перестановочными шифрами.
Найпростіший з таких шифрів використає перетворення "драбинки", та полягає в тому, що відкритий текст записується уздовж похилих рядків певної довжини ("сходів"), а потім зчитується порядково по горизонталі. Наприклад, щоб зашифрувати повідомлення "meet me after the toga party" за методом драбинки зі сходами довжиною 2, запишемо це повідомлення у вигляді
m
e
m
a
t
r
h
t
g
p
r
y
e
t
e
f
e
t
e
o
a
a
t
Шифроване повідомлення буде мати такий вигляд.
MEMATRHTGPRYETEFETEOAAT
Такий "шифр" особливої складності для криптоаналізу не представляє. Більш складна схема припускає запис тексту повідомлення в горизонтальні рядки однакової довжини та наступне зчитування тексту стовпець за стовпцем, але не один за одним, а відповідно до деякої перестановки стовпців. Порядок зчитування стовпців при цьому стає ключем алгоритму. Розглянемо наступний приклад.
Ключ: 4 3 1 2 5 6 7
4
3
1
2
5
6
7
a
t
t
a
c
k
p
o
s
t
p
o
n
e
d
u
n
t
i
l
t
w
o
a
m
x
y
z
Відкритий текст:
Шифрований текст: TTNAAPTMTSUOAODWCOIXKNLYPETZ
Простий перестановочный шрифт дуже легко розпізнати, тому що букви в ньому зустрічаються з тією же частотою, що й у відкритому тексті. Наприклад, для тільки що розглянутого способу шифрування з перестановкою стовпців аналіз шифру виконати досить просто - необхідно записати шифрований текст у вигляді матриці й перебрати можливі варіанти перестановок для стовпців. Можна використати також таблиці значень частоти біграм та триграм.
Перестановочный шифр можна зробити більше захищеним, виконавши шифрування з використанням перестановок кілька разів. Виявляється, що в цьому випадку застосовану для шифрування перестановку відтворити вже не так просто. Наприклад, якщо попереднє повідомлення шифрувати ще раз за допомогою того ж самого алгоритму, то результат буде наступним.
Ключ: 4 3 1 2 5 6 7
4
3
1
2
5
6
7
t
t
n
a
a
p
t
m
t
s
u
o
a
o
d
w
c
o
i
x
k
n
l
y
p
e
t
z
Відкритий текст:
Шифрований текст: NSCYAUOPTTWLTMDNAOIEPAXTTOKZ
Щоб наочніше уявити те, що ми одержимо в підсумку повторного застосування перестановки, зіставимо кожну букву вихідного відкритого тексту з номером відповідної їй позиції. Наше повідомлення складається з 28 букв, і вихідною послідовністю буде послідовність
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Після першої перестановки одержимо послідовність, що усе ще зберігає деяку регулярність структури.
03
10
17
24
04
11
18
25
02
09
16
23
01
08
15
22
05
12
19
26
06
13
20
27
07
14
21
28
Після другої перестановки виходить наступна послідовність.
17
09
05
27
24
16
12
07
10
02
22
20
03
25
15
13
04
23
19
14
11
01
26
21
18
08
06
28
Регулярність цієї послідовності вже зовсім не проглядається, тому її криптоанализ буде вимагати значно більших зусиль.
Завдання:
1. Створити програму, що реалізує довільний перестановочний шифр.
2. Підготувати і захистити звіт, в якому обов’язково навести алгоритм роботи даного перестановочного шифру.
Лабораторна робота №3
Криптоаналіз шифрів моноалфавітної заміни
Мета роботи: ознайомитись з основними методами, що використовуються для криптоаналізу шифрів моноалфавітної заміни та , зокрема, з основами частотного аналізу зашифрованого тексту.
Теоретичні відомості
При наявності всього 25 можливих варіантів ключів шифр Цезаря далекий від того, щоб вважатися надійно захищеним. Істотного розширення простору ключів можна домогтися, дозволивши використання довільних підстановок. Давайте ще раз згадаємо шифр Цезаря.
Рис. 1 Приклад зашифрованого тексту
Відкритий текст: a b c d e f g h I j k l m n o p q r s t u v w y z
Шифрований текст: D E F G H I J K L M N O P Q R S T U W Y Z
Якщо в рядку "Шифрований текст" допустити використання кожної з перестановок 26 символів алфавіту, то ми одержимо 26!, або більш ніж 4 х 1026 можливих ключів. Це на 10 порядків більше, ніж розмір простору ключів DES, і це здається достатнім для того, щоб унеможливити успішне застосування криптоаналізу на основі методу послідовного перебору.
Однак для криптоаналітика існує й інша лінія атаки. Якщо криптоаналітик має уявлення про природу відкритого тексту (наприклад, про те, що це зашифрований текст англійською мовою), можна використати відому інформацію про характерні ознаки, властиві текстам відповідною мовою. Щоб показати, як цей підхід застосовується на практиці, розглянемо невеликий приклад. Припустимо, нам потрібно розшифрувати наступний зашифрований текст.
На першому етапі можна визначити відносну частоту появи в тексті різних букв і порівняти їх із середньостатистичними даними для букв англійської мови, показаними на рис. 2.
Якщо повідомлення досить довге, цієї методики вже може бути досить для розпізнавання тексту, але в нашому випадку, коли повідомлення невелике, точного відповідності очікувати не доводиться. У нашому випадку відносна частота входження букв у шифрованому тексті (у відсотках) виявляється наступною.
Рис. 2. Відносна частота появи букв в англійському тексті
Порівнюючи ці результати з даними, показаними на рис. 2, можна припустити, що, швидше за все, букви Р и Z шифрованого тексту є еквівалентами букв е и t відкритого тексту, хоча важко сказати, якій саме букві - Р або Z - відповідає е, а який - t. Букви S, U, ПРО, М и Н, що володіють відносно високою частотою появи в тексті, швидше за все, відповідають буквам з множини {г, n, i, о, a, s}.. Букви з низькою частотою появи (а саме А, В, G, Y, I, J), очевидно, відповідають буквам множини {w,v,b,k,x,q,j,z}.
Далі можна піти декількома шляхами. Можна, наприклад, прийняти якісь припущення про відповідності й на їхній основі спробувати відновити відкритий текст, щоб побачити, чи виглядає такий текст схожим на що-небудь змістовне. Більш систематизований підхід полягає в продовженні пошуку в тексті нових характерних закономірностей. Наприклад, може бути відомо, що в розглянутому тексті обов'язково повинні бути присутнім деякі слова. Або ж можна шукати повторювані послідовності букв шифрованого тексту й намагатися визначити їхні еквіваленти у відкритому тексті.
Один з дуже ефективних методів полягає в підрахунку частоти використання комбінацій, що складаються із двох букв. Такі комбінації називають біграмами. Для значень відносної частоти появи в тексті біграмм теж можна побудувати гістограму, подібну показаної на рис. 2. Відомо, що в англійській мові найпоширенішою є біграма th. У нашому шифрованому тексті найчастіше (три рази) зустрічається комбінація ZW. Тому можна припустити, що Z відповідає t, a W - h. Тоді з раніше сформованої гіпотези випливає, що Р відповідає е. Зауважимо, що в шифрованому тексті буквосполучення ZWP є, і тепер ми можемо представити його як the. В англійській мові the є найпоширенішою триграмою (тобто комбінацією із трьох букв), тому можна сподіватися, що ми рухаємося в правильному напрямку.
Тепер зверніть увагу на комбінацію ZWSW у першому рядку. Звичайно, ми не можемо сказати з повною впевненістю, що ці букви належать тому самому слову, але, якщо припустити, що це так, вони відповідають слову th?t. Звідси робимо висновок, що букві S відповідає а.
Тепер ми маємо наступний результат.
З'ясувавши значення всього лише чотирьох букв, ми розшифрували вже значну частину повідомлення. Продовжуючи аналіз частоти появи букв, а також застосовуючи метод «проб і помилок», залишається проробити зовсім небагато роботи, щоб отримати остаточну відповідь. Розшифрований вихідний текст (з доданими в нього пробілами) має такий вигляд.
Моноалфавітні шифри легко розкриваються, тому що вони успадковують частоту вживання букв оригінального алфавіту. Контрзаходом у цьому випадку є застосування для однієї букви не одного, а декількох замінників (називаних омофонами). Наприклад, букві е вихідного тексту може відповідати кілька різних символів шифру, (скажемо, 16, 74, 35 й 21), причому кожен такий символ може використовуватися або по черзі, або за випадковим законом. Якщо число символів-замінників, призначених букві, вибрати пропорційним частоті появи цієї букви, то підрахунок частковості вживання букв у шифрованому тексті стає безглуздим. Великий математик Карл Фрідріх Гаусс (Carl Friedrich Gauss) був упевнений, що з використанням омофонів він винайшов шифр, що неможливо зламати. Але навіть при вживанні омофонів кожному елементу відкритого тексту відповідає тільки один елемент шифрованого тексту, тому в останньому як і раніше повинні спостерігатися характерні показники частоти повторення комбінацій декількох букв (наприклад, біграм), і в результаті завдання криптоаналізу як і раніше залишається досить елементарним.
Щоб у тексті, шифрованому за допомогою методів підстановок, структура вихідного тексту проявлялася менш помітно, можна використати два принципово різних підходи. Один з них полягає в заміщенні не окремих символів відкритого тексту, а комбінацій декількох символів, а інший підхід передбачає використання для шифрування декількох алфавітів.
Завдання:
1. Отримати у викладача згідно з варіантом приклад текстового файлу, зашифрованого шифром Цезаря.
2. Створити програму, що реалізує метод крипто аналізу на основі частотного аналізу шифрованого тексту.
3. Підготувати і захистити звіт.
Лабораторна робота №4
Організація стегоканалу в BMP-файлі
Мета роботи: ознайомитися з поняттям стеганографії та проаналізувати можливості організації стегоканалу в ВМР-файлі
Теоретичні відомості
Стеганографія - метод передачі інформації, що приховує саме факт самої передачі інформації. Головна відмінність стеганографії від криптографії, де криптограф точно може визначити чи є передане повідомлення зашифрованим текстом, полягає в можливості вбудовувати секретні повідомлення у відкриті повідомлення так, щоб неможливо було запідозрити існування вбудованого таємного послання. Слово "стеганография" у перекладі із грецького буквально означає "тайнопис" (steganos - секрет, таємниця; graphy - запис). Стеганографія містить у собі безліч секретних засобів зв'язку, таких як невидиме чорнило, мікрофотознімки, умовне розташування знаків, таємні канали й засоби зв'язку на плаваючих частотах і т.д.
Бурхливий розвиток обчислювальної техніки й нових каналів передачі інформації сприяє появі нових стеганографічних методів, в основі яких лежать особливості подання інформації в комп'ютерних файлах, обчислювальних мережах і т.п. Тому останнім часом з'явився новий напрямок стеганографії - комп'ютерна стеганографія.
Комп'ютерна стеганографія - це приховання повідомлення або файлу в іншому повідомленні або файлі. Наприклад, стеганографи можуть сховати аудіо-або відеофайл в іншому інформаційному або навіть у великому графічному файлі. Процес стеганографії можна розділити на кілька етапів.
1. Вибір інформаційного файлу. Першим етапом у процесі стеганографії є вибір файлу, якому необхідно сховати. Його ще називають інформаційним файлом.
2. Вибір файлу-контейнера. Другим етапом у процесі стеганографії є вибір файлу для приховання інформації. Його ще називають файлом-контейнером. У більшості відомих програм по стеганографії говориться, що для приховання інформації, обсяг пам'яті файлу-контейнера повинен десь у вісім разів перевищувати обсяг пам'яті інформаційного файлу. Отже, щоб сховати файл розміром 710КБ, знадобиться графіка обсягом 5600КБ.
3. Кодування файлу. Після того, як обраний файл-контейнер програмне забезпечення по стеганографії вбудовує у нього інформаційний файл.
4. Відправлення прихованого повідомлення по електронній пошті і його декодування. Останнім етапом у процесі стеганографії є відправлення файлу-контейнера з вбудованим інформаційним файлом (по електронній пошті, наприклад) та наступне його декодуваня.
Основні принципи побудови стегосистем:
- криптоаналітик має повний інформацію про стеганографічну систему та деталі її реалізації.
- єдиною інформацією, що залишається невідомою криптоаналітику, є ключ, за допомогою якого тільки його власник може встановити факт присутності й зміст схованого повідомлення; якщо криптоаналітик якимось чином довідається про факт існування схованого повідомлення, це не повинне дозволити йому розшифрувати подібні повідомлення в інших даних доти, поки ключ зберігається в таємниці;
- криптоаналітик повинен бути позбавлений яких-небудь технічних й інших переваг у розпізнаванні або розкритті змісту таємних повідомлень.
- у якості даних може використовуватися будь-яка інформація: текстове повідомлення, зображення, відео- або аудіо-файл, і т.п. Далі будемо використати слово "повідомлення", тому що повідомленням може бути як текст або зображення, так й, наприклад, аудіодані. Для позначення прихованої інформації, будемо використовувати саме термін повідомлення.
Основні терміни й визначення.
Стеганографічна система або стегосистема – сукупність засобів і методів, які використовуються для формування прихованого каналу передачі інформації.
Контейнер – будь-яка інформація, призначена для приховання таємних повідомлень; порожній контейнер – контейнер без убудованого повідомлення; заповнений контейнер – стего-контейнер, що містить вбудовану інформацію.
Вбудоване (приховане) повідомлення – повідомлення, що вбудоване в контейнер.
Стеганографічний канал або просто стегоканал – канал передачі.
Стегоключ (просто ключ) – секретний ключ, необхідний для приховування інформації. Залежно від кількості рівнів захисту (наприклад, вбудовування попередньо зашифрованого повідомлення) у стегосистемі може бути один або декілька стегоключів. Як і у криптографії, за типом стегоключа стегосистеми можна розділити на два типи: із секретним ключем; з відкритим ключем. У стегосистемі із секретним ключем використовується один ключ, що повинен бути визначений або до початку обміну секретними повідомленнями, або переданий по захищеному каналу.
У стегосистемі з відкритим ключем для вбудовування й розшифрування повідомлення використовуються різні ключі, які розрізняються таким чином, що за допомогою обчислень неможливо вивести один ключ із іншого. Тому один ключ (відкритий) може передаватися вільно по незахищеному каналі зв'язку. Крім того, дана схема добре працює й при взаємній недовірі відправника й одержувача.
Вимоги до побудови стегосистемы.
Стегосистема повинна відповідати наступним вимогам:
Властивості контейнера повинні бути модифіковані таким чином, щоб зміну неможливо була виявити при візуальному контролі. Ця вимога визначає якість приховання впроваджуваного повідомлення: для забезпечення безперешкодного проходження стегоповідомлення по каналу зв'язку воно жодним чином не повинно привернути увагу атакуючого.
Стегоповідомлення повинне бути стійким до спотворень, у тому числі й зловмисних. У процесі передачі зображення (звук або інший контейнер) може зазнавати різних трансформацій: зменшуватися або збільшуватися, перетворювати в інший формат і т.д. Крім того, контейнер може бути стиснуто, у тому числі й з використанням алгоритмів стиску із втратою даних. Для збереження цілісності вбудованого повідомлення, необхідне використання коду з виправленням помилок.
Можна виділити три тісно зв'язаних між собою напрямки стеганографії: приховування даних (повідомлень); цифрові водяні знаки; та цифрові заголовки.
Передача разом з контейнером прихованих даних висуває серйозні вимоги до контейнера: розмір контейнера в кілька разів повинен перевищувати розмір даних, що вбудовують.
Цифрові водяні знаки використаються для захисту авторських або майнових прав на цифрові зображення, фотографії або інші оцифровані твори мистецтва. Основними вимогами, які пред'являються до таких вбудованих даних, є надійність і стійкість до спотворень. Цифрові водяні знаки мають невеликий об’єм, однак, з врахуванням зазначених вище вимог, для їхнього вбудовування використовуються більш складні методи, ніж для вбудовування просто повідомлень або заголовків.
Заголовки використається в основному для маркування зображень у великих електронних сховищах (бібліотеках) цифрових зображень, аудіо- і відеофайлів. У цьому випадку стеганографічні методи використовуються не тільки для забезпечення ідентифікуючого заголовка, але й інших індивідуальних ознак файлу. Вбудовані заголовки мають невеликий об’єм. Вимоги до них також мінімальні: заголовки повинні вносити незначні спотворення та бути стійкіми до основних геометричних перетворень.
Обмеження
Залежно від призначення до стеганографії пред’являються різні вимоги щодо співвідношення між стійкістю вбудованого повідомлення до зовнішніх впливів (у тому числі й стегоаналізу) і розміром самого повідомлення, що вбудовується. Для більшості сучасних методів, що використовуються для приховування повідомлення в цифрових контейнерах, має місце зворотна залежність надійності системи від обсягу даних, що приховуються. Ця залежність говорить про те, що при збільшенні обсягу даних, що вбудовують, знижується надійність системи (при незмінності розміру контейнера).
Методи використання надмірності цифрові фотографії, цифрового звуку й цифрового відео
Молодші розряди цифрових відліків містять дуже мало корисної інформації. Їхнє заповнення додатковою інформацією практично не впливає на якість сприйняття, що й дає можливість приховання конфіденційної інформації
Недоліки: За рахунок введення додаткової інформації спотворюються статистичні характеристики цифрових потоків. Для зниження компрометуючих ознак потрібна корекція статистичних характеристик
Переваги: Можливість схованої передачі великого обсягу інформації. Можливість захисту авторського права, схованого зображення товарної марки, реєстраційних номерів і т.п.
Завдання :
1. Проаналізувавши формат ВМР, створити програму для організації стегоканалу для приховування даних, що в середньому є в 10 раз меншими за розмір файлу.
2. Підготувати та захистити звіт.
Лабораторна робота №5
Симетричні блокові шифри на основі мережі Фейстеля
Мета роботи : ознайомитися з методом побудови алгоритмів симетричного блокового шифрування на прикладі мережі Фейстеля.
Теоретичні відомості
Мережа Фе́йстеля (конструкція Фейстеля) — один з методів побудови блокових шифрів. Мережа представляє із себе певну ітеровану структуру, що називається коміркою Фейстеля. При переході від однієї комірки до іншої міняється ключ, причому вибір ключа залежить від конкретного алгоритму. Операції шифрування та дешифрування на кожному етапі дуже прості, і при певній доробці збігаються, вимагаючи тільки зворотного порядку використовуваних ключів. Шифрування за допомогою даної конструкції легко реалізуються як на програмному рівні, так і на апаратному, що забезпечує широкі можливості застосування. Більшість сучасних блокових шифрів використовують мережу Фейстеля як основу. Альтернативою мережі Фейстеля є підстановочно-перестановочна мережа
Конструкція блокового шифру на основі мереж Фейстеля
Розглянемо випадок, коли ми хочемо зашифрувати деяку інформацію, представлену у двійковому вигляді в комп'ютерній пам'яті (наприклад, файл) або електроніці, як послідовність нулів й одиниць.
Вся інформація розбивається на блоки фіксованої довжини. У випадку, якщо довжина вхідного блоку менше, ніж розмір, що шифрується заданим алгоритмом, то блок подовжується яким-небудь способом. Як правило довжина блоку є ступенем двійки, наприклад: 64 біта, 128 біт. Далі будемо розглядати операції, що відбуваються тільки з одним блоком, тому що з іншими в процесі шифрування виконуються ті ж самі операції.
Обраний блок ділиться на два рівних подблока — «лівий» (L0) і «правий» (R0).
«Лівий подблок» L0 видозмінюється функцією f(L0,K0) залежно від раундового ключа K0, після чого він додається по модулі 2 з «правим підблоком» R0.
Результат додавання присвоюється новому лівому підблоку L1, що буде половиною вхідних даних для наступного раунду, а «лівий подблок» L0 присвоюється без змін новому правому підблоку1 (див. схему), що буде іншою половиною.
Після чого операція повторюється N-1 раз, при цьому при переході від одного етапу до іншого міняються раундові ключі (K0 на K1 і т.д.) за яким-небудь математичним правилом, де N — кількість раундів у заданому алгоритмі. Розшифрування інформації відбувається так само, як і шифрування, з тією лише відмінністю, що ключі йдуть у зворотному порядку, тобто не від першого до N-ному, а від N-го до першого.
Шифрування
Розшифрування
Алгоритмічний опис
блок відкритого тексту ділиться на 2 рівні частини (L0, R0 )
у кожному раунді обчислюється ( i=1…n - номер раунду)
Li = Ri-1 + f (Li-1, Ki-1)
Ri = Li-1
де f — деяка функція, а Ki − 1 — ключ i-го раунду.
Результатом виконання n раундів є (Ln, Rn ). Але звичайно в n-ом раунді перестановка Ln й Rn не виконується, що дозволяє використати ту ж процедуру й для розшифрування, просто інвертувавши порядок використання раундової ключової інформації:
Li-1 = Ri + f (Li, Ki-1)
Ri-1 = Li .
Невеликою зміною можна домогтися й повної ідентичності процедур шифрування й дешифрування.
Одна з переваг такої моделі — оборотність алгоритму незалежно від використовуваної функції f, і вона може бути як завгодно складною
Математичний опис
Інволюція — взаємо-однозначне перетворення, застосування якого двічі приводить до вихідного значення.
Нехай X — вхідний блок, а A - деяке інволютиве перетворення, Y - вихід.
При однократному застосуванні перетворення: Y = AX, при повторному: AY = A2X = AAX = XɣX .
Нехай вхідний блок X=(L, R) складається із двох підблоков (L й R) рівної довжини. Визначимо два перетворення G (X,K) = (L + F(K,R), R) (шифрування ключем K) і T(L,R) = (R,L) (перестановка подблоков). Введемо позначення: X′ = (L′, R′) =GX , X″= (L″, R″) = G2X.
Доведемо їх інволютивність:
Нескладно помітити, що перетворення G міняє тільки лівий подблок L, залишаючи правий R незмінним. Тому далі будемо розглядати тільки подблок L. Після того як перетворення G буде двічі застосоване до L одержимо:
L″= L′+ F(K, R′) = L′+ F(K, R) = L + F(K, R)+F(K,R) = L .
У такий спосіб G2X = X, отже G - інволюція.
T2X = T2(L,R) = T(R,L) = (L,R) = X.
Розглянемо сам процес шифрування.
Визначимо X як вхідне значення. Нехай Gi — перетворення із ключем Ki, а Yi — вихідне значення після i-го раунду. Тоді перетворення на i+1-му раунді можна записати у вигляді Yi + 1 = TGiYi, крім першого, де Y1 = TG1X. Отже, вихідне значення після m раундів шифрування буде Ym = TGmYm-1 = TGmTGm-1 … TG1X. Можна помітити, що на останньому етапі не обов'язково виконувати перестановку T.
Розшифрування виконується із застосуванням всіх перетворень у зворотному порядку. У силу інволютивності кожного з перетворень зворотний порядок дає вихідний результат:
X = G1TG2T … Gm-1TGmT(Ym) = G1TG2T … Gm-1T(Ym-1) = … = G1T(Y1) = X.
Функції, що використовуються у мережі Фейстеля
P-блок (P-box)
Блок перестановок усього лише змінює положення цифр й є лінійним. Цей блок може мати дуже велику кількість входів-виходів, однак у силу лінійності систему не можна вважати криптостійкою. Криптоаналіз ключа для n-розрядного P-блоку проводиться шляхом подачі на вхід n-1 різних повідомлень, кожне з яких складається з n-1 нуля («0») і 1 одиниці («1»).
Схема 8-розрядного P-блоку
S-блок (S-box)
Блок підстановок (S-блок) складається з: дешифратора, що перетворює n-розрядний двійковий сигнал в однорозрядний сигнал за підстановкою 2n; системи комутаторів внутрішніх з'єднань (усього з'єднань 2n!); та шифраторів, що переводить сигнал з однорозрядного 2n-ого в n-розрядний двійковий. Аналіз n-розрядного S-блоку при великому n досить складний. Однак реалізувати такий блок на практиці дуже складно, тому що число можливих з'єднань украй велике (2n!). На практиці блок підстановок використається як частина більше складних систем.
У загальному випадку S-блок може мати нерівне число входів/виходів. У цьому випадку в системі комутації від кожного виходу дешифратора може йти не одне з'єднання, а 2 або більше або не йти зовсім. Те ж саме справедливо й для входів шифратора.
В електроніці можна безпосередньо застосовувати наведену нижче схему, у програмуванні ж генерують таблиці заміни. Обидва ці підходи є еквівалентними, тобто файл, зашифрований на комп'ютері, можна розшифрувати на електронному пристрої й навпаки.
Схема 3-розрядного S-блоку
Таблиця заміни для наведеного 3-розрядного S-блоку
№ комбінації
0
1
2
3
4
5
6
7
Вхід
000
001
010
011
100
101
110
111
Вихід
010
110
000
001
011
100
111
101
Циклічний зсув
Циклічний зсув вліво на 3 розряди 8-бітної шини
Можна показати, що циклічний зсув є частиною P-блоку.
У найпростішому випадку (зсув на 1 біт), крайній біт переміщається на інший кінець регістра або шини. Залежно від того, який біт береться – правий або лівий, зсув називається вправо або вліво. Зсув на більше число біт можна розглядати, як багаторазове застосування зсуву на 1.
Циклічний зсув на m біт для n-розрядного входу (m < n)
Напрямок зсуву
Порядок проходження бітів до зсуву
Порядок проходження битов після зсуву
вліво
b0,b1,b2,...,bn − 1
bm,bm + 1,...bn − 1,b0,b1,...,bm − 1
вправо
b0,b1,b2,...,bn − 1
bn − m,bn − m + 1,...bn − 1,b0,b1,...,bn − m − 1
Додавання по модулю n
Операція - (A + B) mod n - це залишок від ділення суми A + B на n, де A й B - числа, що додаються.
Можна показати, що додавання двох чисел по модулі n представляється у двійковій системі числення, як S-блок, у якого на вхід подається число A, а як система комутації S-блоку використається циклічний зсув вліво на B розрядів.
В комп'ютерній техніці й електроніці операція додавання, як правило, реалізована як додавання по модулі n = 2m, де m — ціле (звичайно m дорівнює розрядності машини). Для одержання у двійковій системі A + B mod 2m досить додати числа, після чого відкинути розряди починаючи з m-того й старше.
Множення по модулю n
Операція - (A * B) mod n — це залишок від ділення добутку A * B на n, де A й B - числа, що перемножуються.
У персональних комп'ютерах на платформі x86 при перемножуванні двох m-розрядних чисел виходить число розрядністю 2*m. Щоб одержати залишок від ділення на 2m потрібно відкинути m старших біт.
Переваги й недоліки
Переваги:
Простота апаратної реалізації на сучасній елементній базі
Простота програмної реалізації в силу того, що значна частина функцій підтримується на апаратному рівні в сучасних комп'ютерах (наприклад, додавання по модулю 2 додавання по модулю 2n, множення по модулю 2n, і т.д.)
Добра вивченість алгоритмів на основі мереж Фейстеля
Недоліки:
За один раунд шифрується тільки половина вхідного блоку
Модифікації мережі Фейстеля
При великому розмірі блоків шифрування (128 біт і більше) реалізація такої мережі Фейстеля на 32-розрядних
22.03.2018 19:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора