Файл: 1.docx

При досить довгій роботі скремблера неминуче виникає його зациклення. Після виконання певного числа тактів в осередках скремблера створиться комбінація біт, яка в нім вже одного дня виявлялася, і з цієї миті кодуюча послідовність почне циклічно повторюватися з фіксованим періодом. Ця проблема неусувна за своєю природою, оскільки в N розрядах скремблера не може перебувати більше 2N комбінацій біт, і, отже, максимум, через, 2N-1 циклів повтор комбінації обов'язково станеться. Комбінація "усі нулі" відразу ж виключається з ланцюжка графа станів скремблера - вона приводить скремблер до такого ж положення "усі нулі". Це вказує ще і на те, що ключ "усі нулі" непридатний для скремблера. Кожен генерований при зрушенні біт залежить тільки від декількох біт що зберігається в даний момент скремблером комбінації. Тому після повторення деякої ситуації, що одного дня вже зустрічалася в скремблері, що усі йдуть за нею в точності повторюватимуть ланцюжок, що вже пройшов раніше в скремблері.

Можливі різні типи графів стану скремблера. На малюнку 2 приведені зразкові варіанти для 3-розрядного скремблера. У разі "А" окрім завжди присутнього циклу "000">>"000" ми бачимо ще два цикли - з 3-мя станами і 4-мя. У разі "Б" ми бачимо ланцюжок, який сходиться до циклу з 3-х станів і вже ніколи звідти не виходить. І нарешті, у разі "В" усі можливі стани окрім нульового, об'єднані в один замкнутий цикл. Очевидно, що саме в цьому випадку, коли усе 2N-1 станів системи утворюють цикл, період повторення вихідних комбінацій максимальний, а кореляція між довжиною циклу і початковим станом скремблера (ключем), яка привела б до появи слабкіших ключів, відсутній.

Мал. 2.

І ось тут математика піднесла прикладній науці, якій являється криптографія, черговий подарунок. Наслідком однієї з теорем доводиться (у термінах стосовно скремблювання), що для скремблера будь-якої розрядності N завжди існує такий вибір охоплюваних зворотним зв'язком розрядів, що генерована ними послідовність біт матиме період, рівний 2N-1 бітам. Так, наприклад, в 8-бітовому скремблері, при охопленні 0-го, 1-го, 6-го і 7-го розрядів дійсно за час генерації 255 біт послідовно проходять усі числа від 1 до 255, не повторюючись жодного разу.

Схеми з вибраними за цим законом зворотними зв'язками називаються генераторами послідовностей найбільшої довжини (ПНД), і саме вони використовуються в скремблюючій апаратурі. З безлічі генераторів ПНД заданої розрядності в часи, коли вони реалізовувалися на електричній або мінімальній електронній базі вибиралися ті, у яких число розрядів, що беруть участь в створенні чергового біта, було мінімальним. Зазвичай генератора ПНД вдавалося досягти за 3 або 4 зв'язки. Сама ж розрядність скремблерів перевищувала 30 біт, що давало можливість передавати до 240 біт = 100 Мбайт інформації без побоювання початку повторення кодуючої послідовності.

ПНД нерозривно пов'язані з математичною теорією поліномів, що не приводяться. Виявляється, досить щоб поліном міри N не був представимо по модулю 2 у вигляді твору ніяких інших поліномів, для того, щоб скремблер, побудований на його основі, створював ПНД. Наприклад, єдиним поліномом міри, що не приводиться, 3 являється x3+x+1, в двійковому виді він записується як 10112 (одиниці відповідають присутнім розрядам). Скремблери на основі поліномів, що не приводяться, утворюються відкиданням самого старшого розряду (він завжди присутній, а отже, несе інформацію тільки про міру полінома), так на основі вказаного полінома, ми можемо створити скремблер 0112 з періодом зациклення 7(=23-1). Природно, що на практиці застосовуються поліноми значно вищих порядків. А таблиці поліномів будь-яких порядків, що не приводяться, можна завжди знайти в спеціалізованих математичних довідниках.

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

1.3.2 Блокові шифри

1.3.2.1. Загальні відомості про блокові шифри ( 19 кб )На сьогодні розроблено досить багато стійких блокових шифрів. Практично усі алгоритми використовують для перетворень певний набір биективных (оборотних) математичних перетворень

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

1.3.2.3. Блоковий шифр TEAБлоковий алгоритм TEA приведений як приклад одного з найпростіших в реалізації стійких криптоалгоритмов.

1.3.2.4. AES: cтандарт блокових шифрів США c 2000 рокуВ 1998 році був оголошений відкритий конкурс на криптостандарт США на декілька перших десятиліть XXI століття. Переможцем конкурсу був визнаний бельгійський блоковий шифр Rijndael. Швидше за все він стане стандартом де-факто блокового шифрування у всьому світі.

Загальні відомості про блокові шифри

Характерною особливістю блокових криптоалгоритмов є той факт, що в ході своєї роботи вони виробляють перетворення блоку вхідної інформації фіксованої довжини і отримують результуючий блок того ж об'єму, але недоступний для прочитання стороннім особам, ключем, що не володіє. Таким чином, схему роботи блокового шифру можна описати функціями Z=EnCrypt(X, Key) і X=DeCrypt(Z, Key)

Ключ Key є параметром блокового криптоалгоритма і є деякий блок двійкової інформації фіксованого розміру. Початковий (X) і зашифрований (Z) блоки даних також мають фіксовану розрядність, рівну між собою, але необов'язково рівну довжині ключа.

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

Наступні розробки всесвітньо визнані стійкими алгоритмами і публікацій про універсальні методи їх злому в засобах масової інформації на момент створення матеріалу не зустрічалося.

Криптоалгоритм іменується ідеально стійким, якщо прочитати зашифрований блок даних можна тільки перебравши усі можливі ключі, до тих пір, поки повідомлення не виявиться осмисленим. Оскільки по теорії вірогідності шуканий ключ буде знайдений з вірогідністю 1/2 після перебору половини усіх ключів, то на злом ідеально стійкого криптоалгоритма з ключем довжини N буде потрібно в середньому 2N-1 перевірок. Таким чином, в загальному випадку стійкість блокового шифру залежить тільки від довжини ключа і зростає експоненціально з її зростанням. Навіть припустивши, що перебір ключів виробляється на спеціально створеній багатопроцесорній системі, в якій завдяки діагональному паралелізму на перевірку 1 ключа йде тільки 1 такт, то на злом 128 бітового ключа сучасній техніці буде потрібно не менше 1021 року. Природно, усе сказане відноситься тільки до ідеально стійких шифрів, якими, наприклад, з великою часткою упевненості являються приведені в таблиці вище алгоритми.

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

Таким чином, на функцію стійкого блокового шифру Z=EnCrypt(X, Key) накладаються наступні умови:

1. Функція EnCrypt має бути оборотною.

2. Не повинно існувати інших методів прочитання повідомлення X по відомому блоку Z, окрім як повним перебором ключів Key.

3. Не повинно існувати інших методів визначення яким ключем Key було вироблено перетворення відомого повідомлення X в повідомлення Z, окрім як повним перебором ключів.

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

Усі дії, вироблювані над даними блоковим криптоалгоритмом, засновані на тому факті, що перетворюваний блок може бути представлений у вигляді цілого ненегативного числа з діапазону, відповідного його розрядності. Так, наприклад, 32-бітовий блок даних можна інтерпретувати як число з діапазону 0.4'294'967'295. Крім того, блок, розрядність якого зазвичай є "мірою двійки", можна трактувати як декілька незалежних ненегативних чисел з меншого діапазону (розглянутий вище 32-бітовий блок можна також представити у вигляді 2 незалежних чисел з діапазону 0.65535 або у вигляді 4 незалежних чисел з діапазону 0.255).

Над цими числами блоковим криптоалгоритмом і виконуються за певною схемою наступні дії (ліворуч дані умовні позначення цих операцій на графічних схемах алгоритмів) :

Як параметр V для будь-якого з цих перетворень може використовуватися:

1. фіксоване число (наприклад, X'=X+125)

2. число, що отримується з ключа (наприклад, X'=X+F(Key))

3. число, що отримується з незалежної частини блоку (наприклад, X2'=X2+F(X1))

Останній варіант використовується в схемі, названій на ім'я її творця мережею Фейштеля (йому. Feistel).

Послідовність виконуваних над блоком операцій, комбінації перерахованих вище варіантів V і самі функції F і складають "ноу-хау" кожного конкретного блокового криптоалгоритма. Розмір блоків і довжина ключа сучасних (1999 рік) алгоритмів були нами розглянуті раніше. Один-два разу в рік дослідницькі центри світу публікують черговий блоковий шифр, який під лютою атакою криптоаналітиків або придбаває за декілька років статус стійкого криптоалгоритма, або (що відбувається незмірно частіше) безславно йде в історію криптографії.

Характерною ознакою блокових алгоритмів є багатократне і непряме використання матеріалу ключа. Це диктується в першу чергу вимогою неможливості зворотного декодування відносно ключа при відомих початковому і зашифрованому текстах. Для вирішення цього завдання в приведених вище перетвореннях найчастіше використовується не само значення ключа або його частини, а деяка, іноді безповоротна (небиективная) функція від матеріалу ключа. Більше того, в подібних перетвореннях один і той же блок або елемент ключа використовується багаторазово. Це дозволяє при виконанні умови оборотності функції відносно величини X зробити функцію безповоротної відносно ключа Key.

Оскільки операція зашифровування або розшифровки окремого блоку в процесі кодування пакету інформації виконується багаторазово (іноді до сотень тисяч разів), а значення ключа і, отже, функцій Vi(Key) залишається незмінним, то іноді стає доцільно заздалегідь одноразово вичислити ці значення і зберігати їх в оперативній пам'яті спільно з ключем. Оскільки ці значення залежать тільки від ключа, то оин в криптографії називаються матеріалом ключа. Необхідно відмітити, що ця операція жодним чином не змінює ні довжину ключа, ні криптостойкость алгоритму в цілому. Тут відбувається лише оптимізація швидкості обчислень шляхом кеширования (англ. caching) проміжних результатів. Описані дії зустрічаються практично в багатьох блокових криптоалгоритмах і носять назву розширення ключа (англ. key scheduling)

Мережа Фейштеля

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

Класична мережа Фейштеля має наступну структуру:

Мал. 1.

Незалежні потоки інформації, породжені з початкового блоку, називаються гілками мережі. У класичній схемі їх дві. Величини Vi іменуються параметрами мережі, звичайно це функції від матеріалу ключа. Функція F називається твірною. Дія, що складається з одноразового обчислення функції, що утворює, і наступного накладення її результату на іншу гілку з обміном їх місцями, називається циклом або раундом (англ. round) мережі Фейштеля. Оптимальне число раундів K - від 8 до 32. Важливе те, що збільшення кількості раундів значно збільшує криптоскойстость будь-якого блокового шифру до криптоаналізу. Можливо, ця особливість і вплинула на таке активне поширення мережі Фейштеля - адже при виявленні, скажімо, якого-небудь слабкого місця в алгоритмі, майже завжди досить збільшити кількість раундів на 4-8, не переписуючи сам алгоритм. Часто кількість раундів не фіксується розробниками алгоритму, а лише вказуються розумні межі (обов'язково нижній, і не завжди - верхній) цього параметра.

Відразу ж виникає питання, - чи є ця схема оборотною ? Очевидно, так. Мережа Фейштеля має ту властивість, що навіть якщо як функція, що утворює, F буде використане безповоротне перетворення, то і в цьому випадку увесь ланцюжок буде відновлений. Це відбувається внаслідок того, що для зворотного перетворення мережі Фейштеля не треба обчислювати функцію F - 1.

Більше того, як неважко помітити, мережа Фейштеля симетрична. Використання операції XOR, оборотної своїм же повтором, і інверсія останнього обміну гілок роблять можливим раскодирование блоку тією ж мережею Фейштеля, але з інверсним порядком параметрів Vi. Помітимо, що для оборотності мережі Фейштеля не має значення чи являється число раундів парним або непарним числом. У більшості реалізацій схеми, в яких обидві вищеперелічені умови (операція XOR і знищення останнього обміну) збережено, пряме і зворотне перетворення виробляються однією і тією ж процедурою, якою як параметр передається вектор величин Vi або в початковому, або в інверсному порядку.