2.2.1. скремблери
Скремблерами називаються програмні або апаратні реалізації алгоритму, що дозволяє шифрувати побитно безперервні потоки інформації. Сам скремблер вдає із себе набір біт, що змінюються на кожному кроці за певним алгоритмом. Після виконання кожного чергового кроку на його виході з'являється шифрує біт - або 0, або 1, який накладається на поточний біт інформаційного потоку операцією XOR.
2.2.2. блокові шифри
Блокові шифри шифрують цілі блоки інформації (від 4 до 32 байт) як єдине ціле - це значно збільшує стійкість перетворень до атаки повним перебором і дозволяє використовувати різні математичні та алгоритмічні перетворення.
Останнім часом сфера застосування скремблируется алгоритмів значно скоротилася. Це пояснюється в першу чергу зниженням обсягів побитной послідовної передачі інформації, для захисту якої були розроблені дані алгоритми. Практично повсюдно в сучасних системах застосовуються мережі з комутацією пакетів, для підтримки конфіденційності якої використовуються блокові шифри. А їх криптостойкость перевершує, і часом досить значно, криптостойкость скремблеров.
Суть скремблювання полягає в побітному зміні проходить через систему потоку даних. Практично єдиною операцією, використовуваної в скремблерами є XOR - "побітно виключає АБО". Паралельно проходженню інформаційного потоку в скремблер за певним правилом генерується потік біт - кодує потік. Як пряме, так і зворотне шифрування здійснюється накладенням по XOR кодує на вихідну.
Генерація кодує біт проводиться циклічно з невеликого початкового об'єму інформації - ключа за наступним алгоритмом. З поточного набору біт вибираються значення певних розрядів і складаються по XOR між собою. Всі розряди зсуваються на 1 біт, а тільки що отримане значення ( "0" або "1") поміщається в звільнився наймолодший розряд. Значення, що знаходилося в самому старшому розряді до зсуву, додається в послідовність, що кодує, стаючи черговим її бітом (див. Рис.1).
З теорії передачі даних криптографія запозичила для запису подібних схем двійкову систему запису. По ній зображений на малюнку скремблер записується комбінацією "100112" - одиниці відповідають розрядам, з яких знімаються біти для формування зворотного зв'язку.
Розглянемо приклад кодування інформаційної послідовності 0101112 скремблер 1012 з початковим ключем 1102.
скремблер код.біт інф.біт рез-т
Як бачимо, пристрій скремблера гранично просто. Його реалізація можлива як на електронній, так і на електричній базі, що й забезпечило його широке застосування в польових умовах. Більш того, той факт, що кожен біт вихідної послідовності залежить тільки від одного вхідного біта, ще більше зміцнило становище скремблеров в захисті потокової передачі даних. Це пов'язано з неминуче виникають в каналі передачі перешкодами, які можуть спотворити в цьому випадку тільки ті біти, на які вони припадають, а не пов'язану з ними групу байт, як це має місце в блокових шифри.
Декодування заскремблірованних послідовностей відбувається за тією ж самою схемою, що і кодування. Саме для цього в алгоритмах застосовується результуюче кодування по "виключає АБО" - схема, однозначно відновити події при розкодування без будь-яких додаткових обчислювальних витрат. Зробимо декодування отриманого фрагмента.
Як Ви можете здогадатися, головна проблема шифрів на основі скремблеров - синхронізація передавального (кодує) і приймає (декодирующего) пристроїв. При пропуску або помилковому вставлянні хоча б одного біта вся передана інформація необоротно втрачається. Тому, в системах шифрування на основі скремблеров дуже велика увага приділяється методам синхронізації. На практиці для цих цілей зазвичай застосовується комбінація двох методів: а) додавання в потік інформації синхронізуючих бітів, заздалегідь відомих приймальній стороні, що дозволяє їй при незнаходження такого біта активно почати пошук синхронізації з відправником, і б) використання високоточних генераторів тимчасових імпульсів, що дозволяє в моменти втрати синхронізації виробляти декодування прийнятих бітів інформації "по пам'яті" без синхронізації.
Число біт, охоплених зворотним зв'язком, тобто розрядність пристрою пам'яті для породжують послідовність, що кодує біт називається розрядністю скремблера. Зображений вище скремблер має розрядність 5. Щодо параметрів криптостойкости дана величина повністю ідентична довжині ключа блокових шифрів, який буде проаналізовано далі. На даному ж етапі важливо відзначити, що чим більше розрядність скремблера, тим вище криптостойкость системи, заснованої на його використанні.
При досить довгій роботі скремблера неминуче виникає його зациклення. За виконання певного числа тактів в осередках скремблера створиться комбінація біт, яка в ньому вже одного разу виявлялася, і з цього моменту кодує послідовність почне циклічно повторюватись з фіксованим періодом. Дана проблема непереборна за своєю природою, так як в N розрядах скремблера не може перебувати більше 2 N комбінацій біт, і, отже, максимум, через, 2 N -1 циклів повтор комбінації обов'язково станеться. Комбінація "всі нулі" відразу ж виключається з ланцюжка графа станів скремблера - вона призводить скремблер до такого ж стану "всі нулі". Це вказує ще й на те, що ключ "всі нулі" непридатний для скремблера. Кожен генерується при зсуві біт залежить тільки від декількох біт інформації, що зберігається в даний момент скремблер комбінації. Тому після повторення деякої ситуації, одного разу вже зустрічалася в скремблер, всі наступні за нею будуть в точності повторювати ланцюжок, вже минулий раніше в скремблер.
Можуть бути різні типи графів стану скремблера. На малюнку 2 приведені приблизні варіанти для 3-розрядного скремблера. У разі "А" крім завжди присутнього циклу "000" >> "000" ми бачимо ще два цикли - з 3-ма станами і 4-ма. У разі "Б" ми бачимо ланцюжок, яка сходиться до циклу з 3-х станів і вже ніколи звідти не виходить. І нарешті, в разі "В" всі можливі стани крім нульового, об'єднані в один замкнутий цикл. Очевидно, що саме в цьому випадку, коли всі 2 N -1 станів системи утворюють цикл, період повторення вихідних комбінацій максимальний, а кореляція між довжиною циклу і початковим станом скремблера (ключем), яка привела б до появи більш слабких ключів, відсутня.
І ось тут математика піднесла прикладній науці, якою є криптографія, черговий подарунок. Наслідком однієї з теорем доводиться (в термінах стосовно Скремблювання), що для скремблера будь розрядності N завжди існує такий вибір охоплених зворотним зв'язком розрядів, що генерується ними послідовність біт буде мати період, рівний 2 N -1 бітам. Так, наприклад, в 8-бітному скремблер, при охопленні 0-го, 1-го, 6-го і 7-го розрядів дійсно за час генерації 255 біт послідовно проходять всі числа від 1 до 255, не повторюючись ні разу.
Схеми з вибраними за цим законом зворотними зв'язками називаються генераторами послідовностей максимальної довжини (ПНД), і саме вони використовуються в скремблируется апаратурі. З безлічі генераторів ПНД заданої розрядності за часів, коли вони реалізовувалися на електричної або мінімальної електронній базі вибиралися ті, у яких число розрядів, що беруть участь у створенні чергового біта, було мінімальним. Зазвичай генератора ПНД вдавалося досягти за 3 або 4 зв'язку. Сама ж розрядність скремблеров перевищувала 30 біт, що давало можливість передавати до 2 40 біт = 100 Мбайт інформації без побоювання початку повторення послідовності, що кодує.
ПНД нерозривно пов'язані з математичною теорією непріводімих полиномов. Виявляється, достатньо щоб поліном ступеня N ні представимо по модулю 2 в вигляді твору ніяких інших поліномів, для того, щоб скремблер, побудований на його основі, створював ПНД. Наприклад, єдиним непріводімим полиномом ступеня 3 є x 3 + x + 1, в двійковому вигляді він записується як 10112 (одиниці відповідають присутнім розрядам). Скремблери на основі непріводімих полиномов утворюються відкиданням найстаршого розряду (він завжди присутній, а отже, несе інформацію тільки про ступінь полінома), так на основі зазначеного полінома, ми можемо створити скремблер 0112 з періодом зациклення 7 (= 2 3 -1). Природно, що на практиці застосовуються поліноми значно більш високих порядків. А таблиці непріводімих полиномов будь-яких порядків можна завжди знайти в спеціалізованих математичних довідниках.
Істотним недоліком скремблируется алгоритмів є їх нестійкість до фальсифікації. Детальніше дана проблема розглянута на наступній лекції, стосовно створення цілих криптосистем.
2.2.2.1. Загальні відомості про блокові шифри (19 кб)
На сьогоднішній день розроблено досить багато стійких блокових шифрів. Практично всі алгоритми використовують для перетворень певний набір биективное (оборотних) математичних перетворень
2.2.2.2. мережа Фейштеля
Мережею Фейштеля називається метод оборотних перетворень тексту, при якому значення, обчислене від однієї з частин тексту, накладається на інші частини. Часто структура мережі виконується таким чином, що для шифрування і дешифрування використовується один і той же алгоритм - відмінність полягає тільки в порядку використання матеріалу ключа.
2.2.2.3. Блоковий шифр TEA
Блоковий алгоритм TEA наведено як приклад одного з найпростіших в реалізації стійких криптоалгоритмів.