Модель захисту від зловмисника 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Модель захисту від зловмисника



Модель захисту від зловмисника

Будемо розглядати ситуацію, коли користувачі A та B спілкуються, обмінюючись повідомленнями, що передаються за допомогою деякого каналу зв’язку. На жаль, канал спілкування прослуховується зловмисником, і кожне повідомлення, що відправляється від A до B або від B до A, потрапляє і до зловмисника.

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

Згідно з наведеною схемою перед відправленням повідомлення перетворюється у шифротекст c за допомогою функції шифрування E(K, m). Крім вихідного повідомлення, або відкритого тексту, параметром цієї функції є деяке число K, що називається ключем. При одному і тому повідомленні різним значенням ключа відповідають різні шифротексти. Для того, щоб від шифротексту перейти до відкритого тексту на приймальному боці застосовується функція дешифрування D(K,c). Таким чином, для того, щоб отримати відкритий текст треба знати ключ. Про застосування спільного секретного (закритого) ключа користувачі A та B повинні домовитися завчасно або скористатися надійним каналом зв’язку для передавання цього ключа від одного користувача до іншого.

Подана схема шифрування може застосовуватися не тільки для обміну повідомленнями, але і для зберігання даних. Зберігання інформації можна розглядати як передавання повідомлення не у просторі, а у часі, коли А і В одна і та ж особа.

 

Принцип Керкгоффса

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

Для перетворення повідомлення до такого вигляду, щоб його зміст став недоступним зловмиснику, можна застосовувати окремий алгоритм. Але зберігання алгоритму у секреті впродовж тривалого часу малоймовірне. Застосування ж нового алгоритму завжди пов’язане з великими витратами. Тому доцільно використовувати деякий параметр алгоритму, який суттєво впливає на результат шифрування. Знання цього параметру дозволяє відносно легко повернутися від зашифрованого тексту до відкритого, а відсутність цього параметру у зацікавленої особи робить таке повернення практично неможливим. Цей параметр називають ключем. На рис.2 він показаний як аргумент К функцій шифрування Е та дешифрування D.

Відомий принцип Керкгоффса говорить: надійність схеми шифрування повинна залежати лише від секретності ключа і не залежати від секретності алгоритмів шифрування та дешифрування. Обґрунтування цього принципу полягає у наступному. Змінювати алгоритми складно. Вони вбудовуються в апаратне або програмне забезпечення, яке важко підлягає оновленню. На практиці один і той же алгоритм використовується впродовж досить тривалого часу. Крім того, навіть простий ключ важко зберігати у секреті. Забезпечити ж секретність цілого алгоритму набагато складніше і дорожче. Кожний учасник системи використовує один і той же алгоритм. Зловмиснику досить лише отримати алгоритм від одного з них, а знайти одного незахищеного користувача серед мільйонів не так вже і важко.

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

Розглянута схема шифрування має один недолік. Зловмисник C може не просто прочитати повідомлення, але і змінити його зміст. В цьому разі користувач В отримає викривлене повідомлення.

Для запобігання такій можливості застосовують додаткове шифрування, яке називають автентифікацією. У автентифікації використовується секретний ключ, який позначають Ka на відміну від ключа шифрування Ke. Процес автентифікації повідомлення m схематично представлений на рис. 3. Коли користувач А відправляє повідомлення m, він визначає так званий код а автентичності повідомлення (Message Authentication Code – MAC)

a = h(Ka, m),

де h – функція обчислення MAC. Користувач В отримує m і a, обчислює значення a за відомим йому ключем і порівнює обчислене значення з отриманим у повідомленні.

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

 

Цифрові підписи

Цифрові підписи – це еквівалент відкритого ключа для кодів автентичності повідомлень (МАС). Схема цифрового підпису полягає в наступному. Користувач А генерує пару ключів (SA, PA). Ключ SA, застосовується користувачем А для перетворення повідомлення m: s = g(SA,m), g – функція, значенням якої є цифровий підпис. Ключ PA – відкритий (публікується), і тому кожний, хто володіє цим ключем може застосувати його до отриманого повідомлення і переконатися в тому, що повідомлення надіслано користувачем А.

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

 

Типи атак

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

У цьому випадку користувачі А і В зашифровують свої дані, а зловмисник може отримати тільки шифрований текст. Це найбільш важкий тип атаки, оскільки зловмисник володіє найменшим об’ємом інформації. Атака з відомим відкритим текстом Зловмисник знає і відкритий і шифрований текст. Мета такої атаки – знайти ключ. На практиці існує багато ситуацій, коли зловмисник може узнати відкритий текст повідомлення. Атака з обраним відкритим текстом У цьому типі атак зловмисник може відправляти довільну кількість спеціально підготовлених простих (відкритих) текстів і отримувати відповідні шифровані тексти. Можливість такого типу атак виникає, наприклад, коли користувач А передає усі свої вхідні повідомлення користувачу В. Зловмисник направляючи повідомлення користувачу А і перехоплюючи повідомлення користувачу В отримує умови для здійснення атаки поданого типу.Існує два види атак з обраним відкритим текстом: автономна (offline) і оперативна (online). У першому випадку набір відкритих текстів готується завчасно, до відправлення першого повідомлення користувачеві А. У другому – вибір кожного наступного відкритого тексту здійснюється на основі вже отриманих шифрованих. Як правило, оперативна атака значно ефективніша за автономну. Атака з обраним шифрованим текстом При проведенні цього типу атаки у зловмисника є можливість підбирати як відкритий, так і шифрований текст. Для кожного підібраного відкритого тексту зловмисник отримує відповідний шифрований текст, а для кожного шифрованого – відповідний відкритий. Цей вид атак ще потужніший ніж попередній. Атаки, що основуються на парадоксі задачі про дні народження

Парадокс задачі про дні народження: якщо в кімнаті знаходяться 23 особи, ймовірність того, що у двох з них співпав день народження приблизно 1/2. Це на подив дуже велика величина.

Р = 1 – А36523 /36523 =1 – (365!/(23!))/36523 ≈ 1/2.

Цей тип атаки оснований на тому факті, що однакові значення, їх називають колізіями (collisions), з’являються набагато частіше, ніж можна було б очікувати. Двостороння атака Цей тип атаки також ґрунтується на використанні колізій. На відміну від попереднього типу зловмисник не чекає пасивно збігу двох МАС, а завчасно генерує випадкові різні ключі, обчислює відповідні значення МАС для відомого постійного повідомлення кожної транзакції і запам’ятовує обчислені значення у таблиці. Після цього, перехоплюючи повідомлення від користувача А до користувача В, зловмисник перевіряє, чи міститься МАС фіксованої частини у таблиці. Якщо так, з високою ймовірністю відповідний ключ з таблиці є ключем транзакції, що застосував користувач А. Якщо застосувати цей тип атаки до прикладу системи з 64-бітовим ключем, треба побудувати таблицю для 232 різних 64-бітових ключів. В цій таблиці для кожного значення ключа запам’ятовується значення МАС для фрази: «Готові ви прийняти транзакцію?».

Виникає питання: скільки транзакцій треба прослухати зловмиснику, доки обчислене значення МАС не знайдеться у таблиці. Зрозуміло, що це випадкова величина. Оскільки кількість ключів у таблиці становить 1/232 частину від кількості усіх можливих 64-бітних ключів, то ймовірність знайти обчислений МАС у таблиці 1/232 ч. Тому математичне сподівання кількості перевірок становить 232.

 

Поле, кільце, група

Поле – це кільце, у якому кожний елемент, крім 0, має протилежний (обернений) відносно операції. Таким чином, множина елементів поля є групою відносно операції +, а множина елементів поля після вилучення елемента 0 утворює групу відносно операції.

Кільцем називається множина M елементів, на якій визначені дві операції, що задовольняють наступним умовам. Відносно першої операції (яка часто називається «додаванням») множина M є абелевою групою. Найчастіше цю операцію позначають як +, а відповідний нейтральний елемент - 0 (нулем).

Групою називається множина M елементів, на якій визначена операція, що задовольняє наступним умовам:

1) " a, b Î M, a b Î M (замкненість);

2) " a, b, c Î M, (a b) c = a (b c) (асоціативність);

3) $! e Î M | " a Î M, a e = e a = a (існування нейтрального елементу);

4) " a Î M, $ b Î M | a b = e (існування протилежного елементу).

Якщо операція групи комутативна (" a, b Î M, a b = b a), групу називають комутативною або абелевою.

 

Симетричні шифри

Застосування симетричних шифрів передбачає два перетворення: c = E(m, k) m = D (c, k), де m – відкритий текст, E – функція шифрування, D – функція дешифрування, c – шифротекст. Згідно з принципом Керкгоффса функції E і D загальновідомі, і секретність c забезпечується секретністю ключа k. Іноді симетричні системи застосовують два ключі: один - для шифрування, другий – для дешифрування. Але між цими ключами існує відомий зв’язок, і за будь-яким відомим одним з них можна легко обчислити інший.

Більшість симетричних алгоритмів можна поділити на дві групи. Перша група – поточні шифри, де на кожному кроці обробляється один елемент даних (буква або біт), друга – блочні шифри, в яких за один крок обробляється група елементів даних (наприклад, 64 біти). Блочні шифри

Блочний шифр на кожному етапі обробляє групу бітів відкритого тексту. Ця група називається блоком.

З метою підвищення стійкості довжина блоку обирається достатньо великою (64, 128 або більше бітів).

 

Шифр Фейстеля

Історично першим з сучасних блочних шифрів є DES (Data Encryption Standard), який ґрунтується на шифрі Г. Файстеля, який працював у фірмі IBM і виконав деякі з перших невійськових досліджень у галузі алгоритмів шифрування. Шифрування за алгоритмом Г. Файстеля являє собою ітераційну процедуру, тобто передбачає багаторазове повторення подібних дій. Традиційно ітерації в алгоритмах шифрування називають раундами. Блок-схема одного раунду показана на рис. 2.1.Особливість поданого алгоритму полягає в тому, що функція раунду має зворотну незалежно від того, яка функція застосовується в середині раунду. Кожний i-й раунд шифрування здійснюється згідно з правилами li = ri-1, ri = li-1 Å F(ki, ri-1). Отже, розшифровування відбувається згідно з перетвореннями ri-1 = li, li-1 = ri Å F(ki, li). Наведені формули показують, що для розшифровування треба застосовувати ті ж підключі, що і при шифруванні, але у зворотному порядку. При цьому алгоритм розшифрування збігається з алгоритмом шифрування (рис. 2.2), якщо на вхід подати шифр, у якому переставлені ліва і права половини (rs, ls).

 

Алгоритм DES

Алгоритм DES складається з 16 раундів, довжина блоку – 64 біти, довжина ключа 56 бітів, а довжина кожного підключа (ключа раунду) – 48 бітів. Оскільки при сучасних обчислювальних методах довжина ключа 56 бітів може виявитися недостатньою, замість DES використовують 3DES, що являє собою послідовне виконання трьох алгоритмів DES з різними ключами.Алгоритм DES шифрування 64-бітового блоку складається з трьох кроків: 1) початкова перестановка бітів блоку згідно з фіксованою таблицею перестановок; 2) виконання 16 раундів алгоритму Файстеля до отриманого блоку; 3) перестановка зворотна до початкової.Початкова та кінцева перестановки представлені відповідно таблицями 2.1 та 2.2. Кожний елемент таблиці дорівнює номеру біту у вхідному блоці (до перестановки). Місце елементу в таблиці визначає розташування відповідного біту після перестановки. При цьому елементи першого рядка відповідають розташуванню бітів на місцях з першого по восьмий, другого – з 9-го по 16-ий і т.д. Наприклад, табл. 2.1 вказує, що на перше місце в результаті перестановки ставиться 58-й біт, а на друге – 50-й. Тому табл. 2.2 вказує, що на 58-е місце переставляється 1-й біт, а на 50-е – на другий.Тепер розглянемо функцію F, яка отримує два аргументи: ri-1 - молодші 32 біти поточного стану блоку і ключ раунду ki. Функція F послідовно виконує п’ять перетворень: 1) перестановка з розширенням; 2) обчислення суми за модулем 2 результату попереднього перетворення і ключа раунду; 3) розщеплення результату попереднього перетворення – отримання восьми груп бітів по 6 біт у кожній; 4) стиск кожної групи до 4-бітового коду; 5) утворення 32-бітового коду на виході F. У першому перетворенні 32-бітовий код розтягується до 48 бітів і перемішується згідно з таблицею 2.3, яка читається так само, як попередні. Це допомагає розсіювати зв’язки між вхідними бітами і вихідними, тобто створює лавинний ефект, коли мала відміна між двома вхідними наборами даних призводить до великих відмін на виході. Після порозрядного додавання за модулем 2 ключа раунду до отриманого 48-бітового коду у сумі послідовно виділяються групи по 6 біт: біти з першого по шостий утворюють першу групу, з сьомого по дванадцятий – другу і т.д. Остання, восьма група утворюється бітами з 43-го по 48-й. Кожна 6-бітова група перетворюється у 4-бітову за допомогою окремої таблиці, що називається S-блоком. Всього використовується вісім S-блоків (рис. 2.3). Перший і шостий біти групи визначають номер рядка S-блоку, а біти з другого по п’ятий – номер стовпця. Елемент S-блоку, що розташований на перетинанні визначених рядка та стовпця, у двійковому коді дорівнює вихідному 4-бітовому значенню.

 

Визначення поля GF(28).

S-блоки почергово обробляють елементи рядків матриці станів. Елементи цієї матриці – байти, і над ними виконуються операції додавання та множення, визначені у полі GF(28). Елементами цього поля є байти, що представляються упорядкованою послідовністю восьми бітів (a7 a6 a5 a4 a3 a2 a1 a0). Кожному байту ставиться у відповідність поліном a7x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + a1x1 + a0x0. У полі GF(28) операція додавання визначається як додавання за модулем 2 відповідних коефіцієнтів (тобто порозрядна операція Å). Операція множення визначається як множення відповідних поліномів за модулем простого поліному х8 + х4 + х3 + х + 1.

Виконання перетворення SubBytes

Функція раунду використовує чотири операції: SubBytes, ShiftRows, MixColumns, AddRoundKey.

SubBytes. Ця операція здійснює заміну байтів у повідомленні згідно з таблицею підстановки, що називається S-блоком. При дешифруванні застосовується обернений S-блок.

S-блоки в алгоритмі DES ретельно підбиралися авторами з метою запобігти зламуванню за допомогою диференційного криптоаналізу. В алгоритмі Rijndael S-блоки мають прозору математичну структуру, що дозволяє формально аналізувати стійкість шифру до диференційного та лінійного аналізів, а також доводити коректність алгоритму.

 

Режим ECB

ECB – Electronic Code Book – електронна кодова книга, являє собою найпростіший стандартний спосіб використання блочного шифру, але він слабо захищений від атак з вилученнями та вставками. Крім того, помилка, зроблена в одному біті шифротексту, впливає на увесь блок у розшифрованому тексті. Дані m, що треба зашифрувати, поділяються на блоки довжиною n бітів:m1, m2, …., mq.

Останній блок доповнюється до довжини n. До блоків застосовується функція кодування, значенням якої є зашифрований блок.Ci = Ek(mi).Дешифрування є оберненням функції шифрування mi = Dk(Ci), де Dk = Ek-1.

З режимом ECB пов’язана низка проблем. Перша виникає внаслідок того, що однакові блоки мають однакові шифри. (mi = mj Þ Ci = Cj). Це дійсно проблема, оскільки часто шаблонні початок та кінець повідомлення збігаються.

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

Режим CBC

CBC (Cipher Block Chaining - зчеплення шифрованих блоків) - найбільш поширений спосіб експлуатації блочного шифру, оскільки призначений для запобігання втратам в результаті атаки з вилученнями та вставками. Помилковий біт шифротексту не тільки перетворює помилковий блок, у якому міститься, але і псує біт у наступному блоці відкритого тексту, що можна легко визначити і сприймати як сигнал про атаку.У режимі CBC формування коду поточного блоку здійснюється з урахуванням шифру попереднього блоку. При цьому виникає зчеплення блоків, що знайшло свій відбиток у назві режиму. Кодування блоків відбувається згідно з виразами C1 = Ek (m1 Å IV), Ci = Ek (mi Å Ci-1), i > 1.

У обчисленні шифру першого блоку використовується початкове значення IV (вектор ініціації), яке можна розглядати як елемент функції шифрування. Режим забезпечує нерівність шифрованих блоків при однакових відкритих текстах цих блоків. На практиці цю величину передають у відкритому вигляді як частину повідомлення.

Розшифровування здійснюється у відповідності з наступними виразами m1 = Dk (C1) Å IV, mi = Dk (Ci) Å Ci-1, i > 1.

 

Режим OFB

OFB (Output FeedBack – зворотний зв’язок за виходом). При цьому методі блочний шифр фактично перетворюється у потоковий. Помилковий біт у шифротексті дає тільки один помилковий біт у розшифрованому тексті. В поданому режимі довжина блоку s вибирається з фіксованого діапазону: 1 £ s £ n, де n – кількість бітів вектору ініціації IV. За допомогою блочного шифру створюється потік ключів довжиною s бітів. Рекомендується брати s = n, оскільки при цьому очікувана довжина періоду потоку ключів досягає максимального значення. Процес шифрування можна описати наступними співвідношеннями

O0 IV,

Oi Ek(Oi-1),

Ci Pi Å MSBs(Oi),

де MSBs(Oi) – старші (ліві) s бітів числа Oi.

Відповідна схема шифрування, показана на рис. 2.7.

Спочатку змінній O0 присвоюється початкове значення IV. Потім, при i = 1, 2, …, q виконуються перетворення: Oi = Ek (Oi-1), ei = s розташованих ліворуч бітів блоку Oi,

Ci = mi Å ei.

 

Режим CFB

CFB (Cipher FeedBack – зворотний зв’язок за шифром). Подібно до попереднього способу цей метод перетворює блочний шифр у потоковий. Помилка у зашифрованому тексті впливає як на власний блок, так і на наступний у відкритому тексті.

Режим CFB відрізняється від попереднього тим, що кожний наступний аргумент функції шифрування утворюється шифротекстом (рис. 2.9). Послідовність операцій при цьому має наступний вигляд.

O0 IV, C0 e

O1 Ek(IV)

Oi Ek(LSBn-s(Oi-1) || Ci-1), i ³ 2

Ci mi Å MSBs(Oi),

де LSBn-s(Oi) – молодші (праві) n-s бітів числа Oi, символом «||» позначено операцію конкатенації, e - пустий рядок.

Схема шифрування CFB показана на рис. 2.9, а дешифрування – на 2.10.

 

Режим CTR

CTR (Counter – лічильник). Цей метод передбачає шифрування поточного стану лічильника і застосування порозрядного XOR до отриманого шифру і поточного сегменту відкритого тексту.

Ctr0 IV,

Ctri Ctri-1 + 1,

Ci mi Å Ek(Ctri).

Дешифрування відбувається згідно з виразом

mi Ci Å Ek(Ctri).

Оскільки у поданому методі зворотний зв’язок не використовується, алгоритми шифрування і дешифрування можуть виконуватися паралельно.

Контроль дійсності повідомлень за допомогою блочного шифру

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

Вони можуть скористатися спільним секретним ключем і алгоритмом з ключем (наприклад, блочним шифром) для генерації контрольного значення, що відсилається разом з даними. Такі значення називають кодами автентичності повідомлень (Message Authentication Codes – MAC):

MAC = F (k, m),

де F – контрольна функція, k – секретний ключ, m – повідомлення. Існує декілька типів MAC, але найбільш розповсюджена – це CBC-MAC. Цей код узагальнює режим CBC блочного шифрування. Процедура отримання MAC виглядає наступним чином.Спочатку дані доповнюються так, щоб їх можна було розбити на серію n-бітових блоків. Отримані блоки шифруються блочним шифром в режимі CBC. Останній блок після необов’язкової процедури, що відкидає молодші n – m біти, утворює m-бітовий код автентичності MAC. Таким чином, якщо m1, …, mq - n-бітові блоки відкритого тексту, то обчислення MAC можна описати наступним чином:l1 = Ek(m1), l2 = E(l1 Å m2), …, li = E(li-1 Å mi), …, lq = E(lq-1 Å mq).Якщо використовується m-бітовий MAC, і m < n, то MAC = F(lq), де F – функція, що відкидає молодші біти свого аргументу. У випадку m = n, MAC = lq.

Міжнародні стандарти пропонують три способи доповнення відкритого тексту до отримання довжини кратної довжині блоку.Всі додаткові символи – нулі. Цей метод має недолік, що полягає у неможливості виявлення додавання, переміщення або вилучення нулів, якщо невідома довжина оригінального повідомлення.В кінці доданої послідовності нулів вставляється одна одиниця, що є міткою кінця повідомлення.Крім доданих нулів, в кінці повідомлення додається спеціальний блок, що містить інформацію про довжину відкритого тексту.Стандарти пропонують два можливих необов’язкових заключних кроки, розроблених для ускладнення здійснення зловмисником атак методом повного перебору:вибрати ключ k1 і обчислити lq = E(k, D(k1, lq));вибрати ключ k2 і обчислити lq = E(k2, lq).

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

 

Потокові шифри

При шифруванні великого об’єму даних (аудіо, відео) у реальному часі потрібні більш швидкі алгоритми, ніж блочні. В цих випадках застосовують потокові шифри, що схожі на одноразовий шифр-блокнот. Суть потокового шифрування полягає у додаванні за модулем 2 бітів потоку ключів до бітів повідомлення. Однак, замість фіксованого потоку ключів, який застосовувався у ранніх потокових шифрах і був секретним ключем, у сучасних системах потік ключів генерується з основного ключа за допомогою однозначно визначених детермінованих алгоритмів.

Під впливом секретного ключа на виході генератора ключового потоку утворюється послідовність бітів, зовні схожа на випадкову. Ця послідовність однозначно визначається ключем. Тому на передавальному та приймальному боці ідентичні послідовності.Кожний біт створеної послідовності додається за модулем 2 до поточного біту повідомлення ci = ki + mi, mi = ci + ki.

Припустимо зловмисник отримав два шифротексти Сk, Сl. Якщо ці шифротексти утворені за допомогою одного ключа K, то зловмисник може отримати суму за модулем 2 відповідних відкритих текстів Сk Å Сl = Mk Å K Å Ml Å K = Mk Å Ml. Таким чином, у зловмисника виникає можливість отримати деяку інформацію, використовуючи шифровані тексти. Це небажано, і тому ключ змінюють або після його застосування для деякого повідомлення, або після застосування впродовж сеансу зв’язку (декілька повідомлень в обох напрямках).Щоб надати шифру необхідну стійкість, генератор ключового потоку виробляє послідовність бітів з певними властивостями.Ключовий потік повинен мати великий період. Оскільки ключовий потік утворюється в результаті детермінованого процесу з основного (секретного) ключа, знайдеться таке число n, що ki = ki+n для усіх значень i. Число n називається періодом послідовності.

Ключовий потік повинен мати псевдовипадкові властивості. Інакше кажучи, генератор послідовності повинен пройти певну кількість статистичних тестів на випадковість.

Алгоритм генерації ключового потоку повинен мати лінійну складність (бути нескладним).І, нарешті, головна властивість – поновлення послідовності при відомій початковій частині повинно бути нездійснимим в обчислювальному відношенні. В ідеалі, навіть якщо відомий перший мільярд бітів ключової послідовності, ймовірність угадати наступний біт неповинна перебільшувати 1 / 2.

 

Роботу РЗЛЗЗ

Роботу РЗЛЗЗ можна описати наступним чином. Кожній комірці sr-i поставимо у відповідність булеву змінну ci, яка дорівнює 1, якщо комірка sr-i є відводом, і - 0 у іншому разі. Припустимо, у початковому стані кожна комірка sr-i містить значення ar-i. В кожному такті значення комірок можуть змінюватися. Позначимо значення комірки sr-i у t-у такті ar-it. Будемо вважати ar-i = ar-i0. Тоді у перших r тактах на виході регістру отримуємо послідовність a00, a10, …, ar-10. У кожному наступному такті j ³ r значення на виході регістру дорівнює

c1 ar-1j-r Å c2 ar-2j-r Å … Å cr a0j-r.

Зауважимо, що коли у початковому стані всі комірки мають нульове значення, то на виході утворюються тільки нулі. Якщо ж стартова послідовність нетривіальна (хоча б один елемент дорівнює одиниці), то на виході утворюється нетривіальна періодична послідовність.

Чому періодична? Дійсно, кількість можливих послідовностей довжини r скінчена, і змінюючи ці послідовності довільним чином, обов’язково отримаємо послідовність, що виникала раніше. Внаслідок детермінованості процесу отримаємо періодичну послідовність. Нагадаємо, що періодом послідовності називається найменше натуральне число N таке, що для будь-якого i більше деякого фіксованого числа виконується

aN+i = ai.

Існує 2r – 1 різних ненульових початкових станів регістру. Тому значення періоду, що генерується регістром з лінійним зворотним зв’язком не більше 2r – 1.

Властивості послідовності, що видається РЗЛЗЗ тісно пов’язані з властивостями двійкового характеристичного поліному

c(x) = 1 + c1 x + c2 x2 + … + cr xr,

асоційованого з цим регістром. Його ненульові коефіцієнти називають відводами за аналогією з відповідними комірками регістру, що доставляють значення аргументів функції зворотного зв’язку. В полі GF(2r) множення виконується за модулем c(x). На рис. 3.3 зображений РЗЛЗЗ, асоційований з поліномом x3 + x + 1.

Означення 3.1. Елемент a групи G називається утворюючим, якщо кожний елемент G дорівнює цілому степеню a.

Означення 3.2. Двійковий поліном c(x) степеню r називається примітивним, якщо він простий (ділиться тільки на 1 та на самого себе), і найменше значення числа n такого, що c(x) ділить xn + 1, дорівнює 2r – 1.

Означення 3.3. Елемент e мультиплікативної групи G називається примітивним (утворюючим), якщо кожний ненульовий елемент групи G дорівнює цілому степеню e..

Властивості послідовності бітів на виході РЗЛЗЗ залежать від характеристичного поліному наступним чином.

1. Якщо старший коефіцієнт характеристичного поліному cr = 0, періодичність може виявитися не з першого такту.

2. Якщо cr = 1, відповідна послідовність називається неособливою (несингулярною). Вона періодична з самого початку, тобто рівняння aN+i = ai виконується для усіх i, а не тільки для достатньо великих. Особливо цікаві неособливі послідовності, що відповідають поліномам з наступними додатковими властивостями.

А. Коли c(x) простий, при будь-якому ненульовому початковому стані регістру період послідовності дорівнює найменшому числу N, при якому поліном c(x) ділить 1 + xN. Як наслідок, період послідовності ділить число 2r -1.

B. Якщо c(x) примітивний, будь-який ненульовий початковий стан регістру дає послідовність з максимально можливим періодом 2r -1.

 

Щифр Рона

RC – Ron’s Cipher (шифр Рона) розроблений дослідником Масачусетського технологічного інституту Роном Рівестом. Це один з найбільш швидкісних потокових алгоритмів. На вхід алгоритму надходить масив S[0 … 255], заповнений числами від 0 до 255, що переставлені в залежності від ключа. В результаті роботи алгоритму утворюється потік ключів, що додається за модулем 2 до відкритого тексту. Додавання виконується у режимі обробки байту у кожному такті.

Алгоритм утворення потоку ключів представляється наступним чином. Спочатку змінним i та j присвоюються нульові значення. Потім повторюється наступна процедура

i = (i + 1) % 256;

j = (j + S[i]) % 256;

swap(S[i], S[j]);

t = (S[i] + S[j]) % 256;

k = S[t];

Стійкість шифру основана на наступному спостереженні; навіть коли зловмисник дізнався ключа k та номеру кроку i, він може обчислити лише значення S[t], а не увесь внутрішній стан масиву. Це прямує з того, що зловмисник не в змозі визначити значення змінної t, не знаючи j, S[i] або S[j]. Це дуже сильний алгоритм, оскільки кожний його крок збільшує криптостійкість. А, саме:i = (i + 1) % 256 забезпечує однократне використання кожного елементу масиву; j = (j + S[i]) % 256 забезпечує нелінійну залежність вихідних даних від масиву; swap(S[i], S[j]) змінює масив в процесі ітерацій; t = (S[i] + S[j]) % 256 завдяки цій операції генерована послідовність мало говорить про внутрішній стан масиву.

Початкова перестановка масиву S визначається ключем за наступним правилом. На старті S[i] = i. В інший масив K довжини 256 байтів заноситься необхідна кількість копій ключа. Після цього параметру j присвоюється нульове значення і збільшуючи i на 1 на кожному кроці (i = 0, 255), виконуються оператори

j = (j + S[i] + K[i])% 256;

swap(S[i], S[j]);

 

Атака «людина посередині»

Незважаючи на привабливість на перший погляд, протокол Діфі-Хелмана не забезпечує автентичності узгодженого ключа. Активний зловмисник може перехоплювати повідомлення між Алісою і Бобом і замінювати їх своїми. Протокол атаки виглядає наступним чином.

1. Єва перехоплює перше повідомлення від Аліси до Боба, замінює ga на ge і відправляє Бобу від імені Аліси.

2. Боб відправляє gb, яке перехоплює Єва. В результаті встановлюється ключ geb між Бобом і Євою.

3. Аналогічно Єва може відправити Алісі від імені Боба ge і таким чином встановити ключ gae між Алісою і Євою.

Надалі Єва має змогу читати і змінювати секретні повідомлення між Євою та Бобом.

Для запобігання атаці «людина посередині» застосовуються протоколи на основі використання центрів сертифікації.

 

Криптосистема RSA

Один з найбільш популярних алгоритмів шифрування цієї групи є алгоритм Рівеста-Шаміра-Адлемана (Rivest-Shamir-Adleman – RSA). Алгоритм RSA ґрунтується на застосуванні однобічної функції піднесення до степеня за відомим модулем. При відкритих значеннях n та e для поданого повідомлення m легко обчислити me (mod n) – шифр повідомлення. При цьому за відомим шифром відновити повідомлення без додаткової інформації практично неможливо. В той же час, якщо відомо розкладання n на множники, остання задача стає розв’язною.

Криптосистема RSA передбачає наступну послідовність дій.

Обрати два великих випадкових простих числа p і q, таких, що |p| ≈ |q|, де |p | - кількість бітів необхідна для представлення числа p (|p| = élog2(p+1)ù). Обчислити n = pq. Обчислити F(n) = НСК(p-1, q-1). Обрати випадкове ціле число e < F(n), таке, що НСД(e, F(n)) = 1 mod F(n), і знайти ціле число d, таке, що ed = 1 mod F(n). Таке d існує, і його можна знайти за допомогою розширеного алгоритму Евкліда. Скористатися парою (n, e) як відкритим ключем, знищивши числа p, q і F(n), і запам’ятати d як закритий ключ.

Шифрування. Для того, щоб надіслати Алісі секретне повідомлення m, що, як число, менше n, Боб створює зашифрований текст c = me mod n. (З точки зору Боба, простір вихідних повідомлень представляє собою множину всіх додатних чисел, що менше n, хоча насправді цим простором є група Zn*.)

Розшифрування. m = cd mod n.

Слід відзначити, що нерівність m < n практично завжди означає, що m Î Zn* (тобто майже всі числа, що менше n належать мультиплікативній групі цілих чисел, взаємно простих з n). Умова m Î Zn* порушується, якщо m = up або m = vq, де u < q і v < p. В цих умовах Боб може розкласти число n на прості множники, обчисливши значення НСД (m, n Приклад. Припустимо, Аліса обрала числа p = 11, q = 13. Тоді n = 143, F(n) = НСК(p-1, q-1)= НСК(10, 12) = 60. Нехай, e = 7. За допомогою розширеного алгоритму Евкліда визначаємо, що d = 43. Кроки визначення показані у табл. 6.1. Припустимо, Боб бажає передати Алісі повідомлення, відкритий текст якого є число 3. Він шифрує це повідомлення за допомогою відкритого ключа Аліси e = 7 і відправляє 37 mod 143 = 42.



Поделиться:


Последнее изменение этой страницы: 2017-02-21; просмотров: 2703; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.81.221.121 (0.13 с.)