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

Реферат

на тему

«Блокові шифри»

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

Під N-розрядним блоком будемо розуміти послідовність з нулів і одиниць довжини N:

x = (x0 , x1 , ..., x_ 1) О Z2,N;

x у Z2,N можна інтерпретувати як вектор і як двоичное представлення цілого числа

||x|| = .

Наприклад, якщо N = 4, те

(0,0,0,0)®0(0,0,0,1)®1(0,0,1,0)®2(0,0,1,1)®3

(0,1,0,0)®4(0,1,0,1)®5(0,1,1,0)®6(0,1,1,1)®7

(1,0,0,0)® 8(1,0,0,1)® 9(1,0,1,0)® 10(1,0,1,1)® 11

(1,1,0,0)® 12(1,1,0,1)® 13(1,1,1,0)® 14(1,1,1,1)® 15.

Блоковим шифром будемо називати елемент p О SYM(Z2,N):

p: x® y = p(x),

де x = (x0, x1, ..., xN-1), x = (y0, y1, ..., y_ 1). Хоча блокові шифри є окремими випадками підстановок (тільки на алфавітах дуже великої потужності), їхній варто розглядати особливо, оскільки, по-перше, більшість симетричних шифрів, використовуваних у системах передачі інформації, є блоковими і, по-друге, блокові шифри зручніше за все описувати в алгоритмічному виді, а не як звичайні підстановки.

Припустимо, що

p(xi) = yi , 0 Ј i < m,

для деякого p О SYM(Z2,N), вихідного тексту X = {xi: xi ОZ2,N} і шифрований тексти Y = {yi}. Що можна сказати про p(x), якщо xП {xi}? Оскільки p є перестановкою на Z2,N , те {yi} різні і p(x)П {yi} при xП {xi}. Що ж ще можна сказати про p?

(2N _ m)! з (2N)! перестановок у SYM(Z2,N) задовольняє рівнянню

p(xi) = yi , 0 Ј i < m,

Подальша специфікація p(x) при відсутності додаткової інформації не представляється можливої. Це визначається в основному тим обставиною, що p є елементом, що належить SYM(Z2,N). Якщо відомо, що p належить невеликій підмножині П з SYM(Z2,N), то можна зробити більш визначений висновок. Наприклад, якщо

П = {p j : 0Ј j <2}, p(i) = (i+j) (mod 2N ), 0 Ј i <2 ,

то значення p(x) при заданому значенні x однозначно визначає p. У цьому випадку X є підмножиною підстановок Цезаря на Z2,N.

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

xi « yi , 0 Ј i < m,

не в змозі на основі цієї інформації визначити вихідний текст, що відповідає yП {yi}.

Якщо для шифрування вихідного тексту використовується підсистема p з ПО SYM(Z2,N), то систему підстановок, що виходить у результаті, П будемо називати системою блокових шифрів або системою блокових підстановок. Блоковий шифр являє собою окремий випадок моноалфавитной підстановки з алфавітом Z2N = Z2,N . Якщо інформація вихідного тексту не може бути представлена N-розрядними блоками, як у випадку стандартного алфавітно-цифрового тексту, то перше, що потрібно зробити, це перекодувати вихідний текст саме в цей формат. Перекодування можна здійснити декількома способами і з практичної точки зору неважливо, який зі способів був обраний.

В установках обробки інформації блокові шифри будуть використовуватися багатьма користувачами. Ключовою системою блокових шифрів є підмножина П[K] симетричної групи SYM(Z2,N)

П[K] = {p {k}: kО K},

индексируемое по параметрі k О K; k є ключем, а K - простором ключів. При цьому не потрібно, щоб різні ключі відповідали різним підстановкам Z2,N.

Ключова система блокових шифрів П[K] використовується в такий спосіб. Користувач i і користувач j деяким чином укладають угоду щодо ключа k з K, вибираючи, таким чином, елемент із П[K] і передаючи текст, зашифрований з використанням обраної підстановки. Запис

y = p{k, x}

будемо використовувати для позначення N-розрядного блоку шифрованого тексту, що отриманий у результаті шифрування N-розрядного блоку вихідного тексту x з використанням підстановки p{k}, що відповідає ключеві k. Покладемо, що зловмисникові

відомий простір ключів K;

відомий алгоритм визначення підстановки p{k} за значенням ключа k;

невідомо, який саме ключ k вибрав користувач.

Якими можливостями розташовує зловмисник? Він може:

одержати ключ унаслідок недбалості користувача i або користувача j;

перехопити (шляхом перехоплення телефонних і комп'ютерних повідомлень) шифрований текст y, переданий користувачем i користувачеві j, і робити проби на всі можливі ключі з K до одержання повідомлення вихідного тексту, що читається;

одержати відповідні вихідний і шифрований тексти (x® y) і скористатися методом проби на ключ;

одержати відповідні вихідний і шифрований тексти і досліджувати співвідношення вихідного тексту x і шифрованого тексту y для визначення ключа k;

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

листинг мовою ассемблера характеризується сильно вираженим структурованим форматом, або

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

Припустимо, що N = 64 і кожен елемент SYM(Z2,N) може бути використаний як підстановка, так що K = SYM(Z2,N).

Тоді:

існує 264 64-розрядних блоків; зловмисник не може підтримувати каталог з 264 =1,8x1019 рядками;

проба на ключ при числі ключів, рівному (264)!, практично неможлива; відповідність вихідного і шифрованого текстів для деяких N-розрядних блоків

p{k,xi} = yi , 0 Ј i < m,

не дає зловмисникові інформації щодо значення

p{k, x} для xП {xi}.

Системи шифрування з блоковими шифрами, алфавітом Z2,64 і простором ключів K = SYM(Z2,64) є неподільними в тім змісті, що підтримка каталогу частот появи букв для 64-розрядних блоків або проба на ключ при числі ключів 264 виходить за межі можливостей зловмисника. Варто порівняти цю проблему з тією задачею, з яким зіштовхується зловмисник у процесі криптоанализа тексту, зашифрованого підстановкою Цезаря з алфавітом {A,..., Я,}; для визначення ключа підстановки Цезаря потрібно лише log232 = 5 біт, у той час як для простору ключів K = SYM(Z2,64) потрібно 264 битов.

На жаль, розроблювач і зловмисник знаходяться в однаковому положенні: розроблювач не може створити систему, у якій були б реалізовані всі 264! підстановок SYM(Z2,64), а зловмисник не може випробувати таке число ключів. Залишається погодитися з тим, що не кожен елемент із SYM(Z2,64) буде використаний як підстановку.

Таким чином, вимоги до гарного блокового шифру формулюються в такий спосіб. Необхідні:

досить велике N (64 або більш) для того, щоб утруднити складання і підтримка каталогу. У вимогах до нового стандарту шифрування ;

досить великий простір ключів для того, щоб виключити можливість підбора ключа;

складні співвідношення

p{k,x} : x ® y=p {k,x}

між вихідним і шифрованим текстами для того, щоб аналітичні і (або) статистичні методи визначення вихідного тексту і (або) ключа на основі відповідності вихідного і шифрованого текстів були б по можливості нереалізовані.

Генерування блокових шифрів

Одним з найбільш розповсюджених способів завдання блокових шифрів є використання так званих мереж Фейстела (по імені дослідника, що працював у свій час у IBM, і одного з авторів стандарту DES). Мережа Фейстела являє собою загальний метод перетворення довільної функції (звичайно називаною F-функцією) у перестановку на безлічі блоків. Ця конструкція була винайдена Хорстом Фейстелом і була використана у великій кількості шифрів, включаючи DES і ДСТ 28147-89. F-функція, що представляє собою основний будівельний блок мережі Фейстела, завжди вибирається нелінійної і практично у всіх випадках необоротної.

Формально F-функцію можна представити у виді відображення

F: Z2,N/2 ґ Z2, k ® Z2,N/2,

де N - довжина преутвореного блоку тексту (повинна бути парної), k - довжина використовуваного блоку ключової інформації.

Нехай тепер X - блок тексту, представимо його у виді двох подблоков однакової довжини X = {A, B}. Тоді одна ітерація (або раунд) мережі Фейстела визначається як

Xi+1 = Bi||(F(Bi, ki) Е Ai)

де Xi = {Ai, Bi}, || - операція конкатенації, а Е - побітове що виключає АБО. Структура ітерації мережі Фейстела представлена на мал. 2.1. Мережа Фейстела складається з деякого фіксованого числа ітерацій, обумовленого розуміннями стійкості розроблювального шифру, при цьому на останній ітерації перестановка місцями половин блоку тексту не виробляється, тому що це не впливає на стійкість шифру.

Дана структура шифрів володіє поруч достоїнств, а саме:

процедури шифрування і расшифрования збігаються, з тим виключенням, що ключова інформація при расшифровании використовується в зворотному порядку;

для побудови пристроїв шифрування можна використовувати ті ж блоки в ланцюгах шифрування і расшифрования.

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

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

Іншим підходом до побудови блокових шифрів є використання оборотних залежних від ключа перетворень. У цьому випадку на кожній ітерації змінюється весь блок і, відповідно, загальна кількість ітерацій може бути скорочено. Кожна ітерація являє собою послідовність перетворень (так званих "шарів"), кожне з яких виконує свою функцію. Звичайно використовуються шар нелінійної оборотної заміни, шар лінійного перемішування й один або два шари підмішування ключа. До недоліків даного підходу можна віднести те, що для процедур шифрування і расшифрования в загальному випадку не можна використовувати ті самі блоки, що збільшує апаратні і/або програмні витрати на реалізацію.

Алгоритми блокового шифрування

Алгоритм DES і його модифікації

Американський стандарт криптографічного закриття даних DES (Data Encryption Standard) є типовим представником сімейства блокових шифрів. Цей шифр допускає ефективну апаратну і програмну реалізацію, причому можливо досягнення швидкостей шифрування до декількох мегабайт у секунду. Шифр DES являє собою результат 33 відображень:

DES = IP-1ґ ґIP, (2.1)

де IP (Initial Permutation - вихідна перестановка) являє собою дротову комутацію з інверсією IP_ 1;

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

Підстановки , 1Ј i Ј 16, описуються в такий спосіб:

Крок 1. На i-м циклі вхідний блок xi довжиною 64 символу

xi = (xi,0, xi,1 ..., xi,63)

поділяється на два блоки по 32 символу X = (xi,0, xi,1 ..., xi,31) і X' = (x'i,0, x'i,1 ..., x'i,31).

Правий блок X' розбивається на вісьмох блоків по чотирьох символу:

Ці вісім блоків шляхом копіювання крайніх елементів перетворяться у вісьмох блоків із шести символів:

Крок 2. На i-циклічній ітерації 48 розрядів ключа

(ki,0, ki,1, ... , ki,47).

поразрядно суммируются (по модулі 2) з отриманими вище 48 розрядами даних.

Крок 3. j-й блок із шести символів (0Ј j <8) подається на вхід блоку підстановки (S-бокс) S[j] має шестиразрядный вхід і четырехразрядный вихід і являє собою чотири перетворення з Z2,4 у Z2,4; два крайніх розряди вхідного блоку служать для вибірки одного з цих перетворень. Кожна з восьми підстановок S[0], S[1],..., S[7] здійснюється з використанням чотирьох рядків і 16 стовпців матриці з елементами {0,1,...,15}. Кожний з масивів розмірністю 4ґ 16 визначає підстановку на безлічі Z2,4 у такий спосіб. Якщо входом є блок із шести символів

(z0, z1, z2, z3, z4, z5),

те дві крайні позиції (z0, z5) інтерпретуються як двоичное представлення цілих чисел з набору {0,1,2,3}.

Ці цілі визначають номер рядка (від 0 до 3). чотири символи, що залишилися (z1, z2, z3, z4) інтерпретуються як двоичное представлення цілих чисел з набору {0,1,...,15} і служать для визначення стовпця в масиві (від 0 до 15). Таким чином, вхідний блок (0,0,1,0,1,1) відповідає рядкові 1 і стовпцеві 5.

Крок 4.32 розряду, що складають вихід S-боксу, подаються на вхід блоку дротової комутації (P-бокс).

Крок 5. Компоненти правого вхідного 32-розрядного блоку X', перетвореного в T(X'), поразрядно суммируются по модулі 2 з компонентами лівого вхідного 32-розрядного блоку X.

На кожній ітерації використовується 48-розрядний ключ (ki,0, ki,1 ..., ki,47). Оскільки вхідним ключем DES є 56-розрядний блок k = = (ki,0, ki,1 ..., ki,55), те кожен його розряд використовується багаторазово.

Який саме з ключів використовується на i-циклічній ітерації, визначається списком ключів. Для опису списку ключів уведені додаткові елементи.

Ключ визначається по наступному алгоритмі:

виробляється початкова перестановка PC-1 ключа 56-розрядного ключа користувача k = (ki,0, ki,1 ..., ki,55). Одержуваний у результаті 56-розрядний блок розглядається як два 28-розрядних блоки: лівий - C0 і правий - D0;

виробляється ліве циклічне зрушення блоків C0 і D0 s[1] раз для одержання блоків C1 і D1;

зі зчеплення блоків (C1, D1) вибираються 48 розрядів за допомогою перестановки PC-2. Ці розряди використовуються на першій ітерації;

використовувані на i-й циклічної ітерації розряди ключа визначаються методом індукції. Для одержання блоків Ci і Di робимо ліве циклічне зрушення s[i] раз блоків Ci-1 і Di-1.

Інверсією DES (обеспечивающей расшифрование зашифрованих за допомогою DES даних) є

DES-1 = IP-1ґp T1ґp *ґ ...ґp*ґ pT16 ґIP, (2.2)

Расшифрование зашифрованого за допомогою DES тексту здійснюється з використанням тих же блоків завдяки оборотності перетворення.

Такий загальний алгоритм DES. Спробуємо проаналізувати його ефективність.

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

Однак, даний алгоритм, будучи першим досвідом стандарту шифрування має ряд недоліків. За час, що пройшов після створення DES, комп'ютерна техніка розвилася настільки швидко, що виявилося можливим здійснювати вичерпний перебір ключів і тим самим розкривати шифр. Вартість цієї атаки постійно знижується. У 1998 р. була побудована машина вартістю близько 100000 доларів, здатна по даній парі <вихідний текст, шифрований текст> відновити ключ за середній час у 3 доби. Таким чином, DES, при його використанні стандартним образом, уже став далеко не оптимальним вибором для задоволення вимогам скритності даних.

Була висунута велика кількість пропозицій по удосконаленню DES, що почасти компенсують зазначені недоліки. Ми розглянемо два з них.

Найбільше широко відомою пропозицією по посиленню DES є так називаний «потрійний DES», одна з версій якого визначається формулою

.

Тобто, ключ для EDE3 має довжину 56 ґ 3 = 168 біт, і шифрування 64-бітового блоку здійснюється шифруванням з одним подключом, расшифрованием з іншим і потім шифруванням із третім. (Причина, по якій другим кроком є , а не , є сумісність з DES: якщо вибрати K=k,k,k, те EDE3K = DESk. Причина використання DES три рази замість двох полягає в існуванні атаки «зустріч у середині» на подвійний DES.)

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

У 1984 р. Рон Ривест запропонував розширення DES, називане DESX (DES eXtended), вільне від недоліків потрійного DES.

DESX визначається як

= k2 Е DESk(k1 Е x)

Тобто, ключ DESX K = k,k1,k2 складається з 54+64+64=184 біт і включає три різних подключа: ключі «DES» k, попередній «зашумляющий» ключ k1 і завершальний «зашумляющий» ключ k2.

Для шифрування блоку повідомлення ми складаємо його поразрядно по модулі 2 з k1, шифруємо його алгоритмом DES із ключем k і знову поразрядно складаємо його по модулі 2 з k2. Таким чином, витрати DESX на шифрування блоку усього на двох операцій додавання по модулі 2 більше, ніж витрати вихідного алгоритму.

У відношенні DESX чудово те, що ці дві операції « щовиключає АБО» роблять шифр набагато менш уразливим стосовно перебору ключів. Укажемо, що DESX утрудняє одержання навіть однієї пари <xi, DESXK(xi)> у тому випадку, коли зловмисник організує атаку на шифр по обраному вихідному тексті, одержуючи безліч пар <Pj, DESK(Pj)>.

DESX призначався для збільшення захищеності DES проти перебору ключів і збереження його стійкості проти інших можливих атак. Але DESX у дійсності також збільшує стійкість проти диференціального і лінійного криптоанализа, збільшуючи необхідну кількість проб з обраним вихідним текстом до величини, що перевищує 260. Подальше збільшення стійкості проти цих атак може бути досягнуто заміною в DESX операції « щовиключає АБО» на додавання, як це було зроблено в

= k2 + DESk(k1 + x)

де додавання визначається в такий спосіб: L.R + L'.R' = (L а L').(R а R'), |L|=|R|=|L'|=|R'|= 32, а а позначає додавання по модулі 232.

Сказане не означає, що неможливо побудувати машину, що розкриває DESX за прийнятний час. Але воно має на увазі, що така машина повинна використовувати яку-небудь радикально нову ідею. Це не може бути машина, що реалізує перебір ключів у загальноприйнятому змісті.

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