ABCDEFGHIJKLMNOPQRSTUVWXYZ 4 страница

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

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

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

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

Наприкінці слід зауважити, що більше як на 95 відсотків стійкість шифру, побудованого на основі схеми Фейстеля, визначається складністю функції нелінійного перетворення F_i(R_i , К_і ) і правилом обчислення ключа К_і.

2.6 Поточні шифри

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

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

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

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

2.7 Шифри гаммування

2.7.1 Накладення гамми шифру на відкритий текст.

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

Під гаммуванням розуміють процес накладення за певним законом гамми шифру на відкриті дані. Гамма шифру – це псевдовипадкова послідовність, створена за заданим алгоритмом для зашифровування відкритих даних і розшифровування зашифрованих даних.

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

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

Рівняння зашифровування можна записати у вигляді

, i = 1 ... М,

де – i-й блок шифртексту; – i-й блок гамми шифру; – i-й блок відкритого тексту; М – кількість блоків відкритого тексту.

Процес розшифровування зводиться до повторного генерування гамми шифру і накладення цієї гамми на зашифровані дані. Рівняння розшифровування має вигляд

= .

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

2.7.2 Методи генерування псевдовипадкових послідовностей чисел.

При шифруванні методом гаммування як ключ використовується випадковий рядок бітів, котрий поєднується з відкритим текстом, також поданим у двійковому вигляді (наприклад А = 00000, У = 00001, З = 00010 і т. д.), за допомогою побітового додавання за модулем 2 – і в результаті виходить шифрований текст.

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

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

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

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

· період гамми повинен бути доволі великим для шифрування повідомлень різної довжини;

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

· генерування гамми не повинно спричинятись до великих технічних складностей.

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

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

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

Один з перших способів генерування псевдовипадкових чисел на ЕОМ запропонував 1946 року Джон фон Нейман. Суть цього способу полягає в тому, що кожне наступне випадкове число утворюється піднесенням до квадрата попереднього числа з відкиданням цифр молодших і старших розрядів. Однак цей спосіб виявився ненадійним – і від нього невдовзі відмовились.

З відомих процедур генерування послідовності псевдовипадкових цілих чисел найчастіше застосовується так званий лінійний конгруентний генератор. Цей генератор продукує послідовність псевдовипадкових чисел Y₁, Y₂,..., Y_і_-1, Y_і, ..., використовуючи співвідношення

Y_i = (a · Y_i_-1+ b) mod m,

де Y_i – i-тe (поточне) число послідовності; Y_i_-1– попереднє число послі-довності; а, b та m – константи; m – модуль; а – множник (коефіцієнт); b – приріст. Поточне псевдовипадкове число Y_i дістають з попереднього числа Y_i_-1множенням його на коефіцієнт а, додаванням з прирістом b та обчисленням остачі від ділення на модуль m. Дане рівняння генерує псевдовипадкові числа з періодом повторювання, котрий залежить від обираних значень параметрів а, b та m і може сягати значення m. Значення модуля m обирається дорівнюваним 2ⁿабо простому числу, наприклад

m = 2³¹ – 1. Приріст b має бути взаємно простим з m, коефіцієнт а має бути непарним числом.

Конгруентні генератори, що працюють за алгоритмом, запропонованим Національним бюро стандартів США, використовуються, зокрема, в системах програмування. Ці генератори мають довжину періоду 2²⁴ і добрі статистичні властивості. Однак така довжина періоду є замала для криптографічних застосовувань. Окрім того, доведено, що послідовності, генеровані конгруентними генераторами, не є криптографічно стійкі.

Існує спосіб генерування послідовностей псевдовипадкових чисел на підставі лінійних рекурентних співвідношень.

Розглянемо рекурентні співвідношення та їхні різницеві рівняння:

;

(2.7.1)

де h₀ 0, h_k = 1 і кожне h_i належить до поля GF(q).

Розв’язком цих рівнянь є послідовність елементів а₀, а₁, а₂, ... поля GF(q). Співвідношення (2.7.1) визначає правило обчислення a_k за відомими значеннями величин а₀, а₁, а₂, ..., а_k–₁. Потім за відомими значеннями а₀, а₁, а₂, ..., а_k визначають a_k₊₁ і т. д. Як наслідок за початковими значеннями а₀, а₁, а₂, ..., а_k–₁можна побудувати нескінченну послідовність, причому кожен її наступний член визначається з k попередніх. Послідовності такого виду легко зреалізовуються на комп'ютері; при цьому реалізація виходить особливо простою, якщо всі h_i та a_i набувають значень 0 та 1 з поля GF(2).

На рис.2.13 подано лінійну послідовну перемикальну схему, яку може бути використано для обчислення суми (2.7.1) і, отже, для обчислення значення a_k за значеннями k попередніх членів послідовності. Вихідні величини а₀, а₁, а₂, ..., а_k–₁ вміщують в розряди регістру зсування, послідовні зсунення вмісту якого відповідають обчисленню послідовних символів; при цьому вихід i-го зсунення дорівнює a_i. Даний пристрій називають генератором послідовності чисел, побудованим на базі зсувового регістру з лінійним зворотним зв'язком.

Позначення:

– суматор за модулем 2

– ланцюг (відвід) з коефіцієнтом передавання h, h = 0 або 1

– запам'ятовувальна комірка, котра зберігає а, тобто на виході

комірки а = 0 або а = 1

Рисунок 2.13 – Генератор з регістром зсування

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

h (X) = h_jХ^j,

де Х – формальна змінна; h^j – коефіцієнт при Х^j, який набуває значення 0 чи 1; h₀ 0, h_k = 1, і нехай n – найменше ціле додатне число, для якого багаточлен Xⁿ – 1 ділиться на h(X). Окрім того, багаточлен

g(X) = (Xⁿ – 1) / h (X).

Тоді розв’язки рекурентних співвідношень

h_j a_i+J= 0

у вигляді послідовності елементів a₀, a₁, a_i, …, a_n–₁ є періодичні з періодом п і сукупність, складена з перших періодів усіх можливих розв’язків, розглядуваних як багаточлени за модулем (Xⁿ – 1), тобто

a (X) = a₀ Xⁿ^–1 + a₁ X^n–² + … + a_n–₂ X + a_n–₁,

збігається з ідеалом, породженим багаточленом g(X) в алгебрі багаточленів за модулем (Xⁿ – 1).

Зауважимо, що якщо за такого визначення багаточлена a(X) елементи а₀, а₁, а₂, … обчислюються в порядку зростання номерів, то коефіцієнти багаточлена a(X) обчислюються, розпочинаючи з коефіцієнтів при ступенях вищих порядків. Слід також зазначити, що вигляд багаточлена

визначає конфігурацію зворотних зв'язків (відводів) h_j в генераторі з регістром зсування. Інакше кажучи, якщо в багаточлена h(X) коефіцієнт h_j = 1, це означає, що відвід h_j у схемі генератора наявний, якщо ж у багаточлена h(X) коефіцієнт h_j= 0, то відвід h_j в схемі генератора є відсутній. У якості h(X) необхідно обирати незвідний примітивний багаточлен. За такого обрання багаточлена h(X) зі старшим степенем m генератор забезпечує видавання псевдовипадкової послідовності двійкових чисел з максимально можливим періодом 2^m – 1.

Розглянемо за приклад трирозрядний регістр зсування з лінійним зворотним зв'язком (рис.2.14), побудований відповідно до незвідного примітивного багаточлена

h(X) = X³ + X² + 1,

де коефіцієнти h₃ = 1, h₂ = 1, h₁ = 0, h₀ = 1.

Рисунок 2.14 – Трирозрядний регістр зсування зі зворотними зв'язками

Нехай ключем є 101. Регістр розпочинає працювати з цього стану; послідовність станів регістру наведено на Рис.2.14. Регістр проходить через усі сім ненульових станів – і знову повертається до свого вихідного стану 101. Це є найдовший період даного регістру з лінійним зворотним зв'язком. Така послідовність називається послідовністю максимальної довжини для зсувового регістра (Maxіmal Length Shіft Regіster Sequence – MLSRS). За будь-якого цілого m існує m-бітова послідовність MLSRS з періодом 2^m – 1. Зокрема за m = 100 послідовність матиме період 2¹⁰⁰– 1 і не повторюватиметься 10¹⁶ років при передаванні лініями зв'язку зі швидкістю 1 Мбіт/с.

У нашому прикладі вихідною послідовністю (гаммою шифру) Г_ш зсувового регістру зі зворотним зв'язком є послідовність 1010011, котра циклічно повторюється. У цій послідовності є чотири одиниці й три нулі і їхній розподіл є настільки близький до рівномірного, наскільки це є можливе в послідовності, котра має довжину 7. Якщо розглянути пари послідовних бітів, то пари 10 та 01 з'являються двічі, а пари 00 та 11 – одноразово, що знову стає настільки близьким до рівномірного розподілу, наскільки це є можливо. У разі послідовності максимальної довжини для m-розрядного регістру ця властивість рівнорозподілюваності поширюється на трійки, четвірки й т. д. бітів, аж до m-бітових груп. Внаслідок такої близькості до рівномірного розподілу послідовності максимальної довжини часто використовуються в якості псевдовипадкових послідовностей у криптографічних системах, котрі імітують роботу криптостійкої системи одноразового шифрування.

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

Якщо відводи регістру зі зворотним зв'язком зафіксовано, то для віднайдення початкового стану регістру доволі знати m бітів відкритого тексту. Щоб віднайти m бітів ключового потоку, m бітів відомого відкритого тексту складають за модулем 2 з відповідними m бітами шифртексту. Здобуті m бітів дають стан регістру зсування зі зворотним зв'язком у зворотному напрямку на певний момент часу. Потім, моделюючи роботу регістру у зворотному напрямку, можна визначити його вихідний стан.

Якщо відводи регістру зі зворотним зв'язком не є фіксовані, а є частиною ключа, то досить 2m бітів відомого відкритого тексту, аби порівняно швидко визначити розташування відводів регістру та його початковий стан.

Нехай S(і) – вектор-стовпець, який складається з m символів 0 та 1 й визначає стан регістру в і-й момент часу. Тоді

S(i + 1) = A · S(i) mod 2,

де А – матриця розміром m´m, котра визначає положення відводів регістру зі зворотним зв'язком.

Для трирозрядного регістру (рис.2.14)

А = .

Матриця А завжди має таку структуру: у її першому рядку відбито послідовність відводів у регістрі, безпосередньо під головною діагоналлю розташовуються одиниці, а в решті позицій – нулі.

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

S (1) – перша група m відомих бітів ключового потоку;

S (2) – наступна група (розпочинаючи з номера 2) з m відомих бітів

ключового потоку;

S (m + 1) – остання група з m відомих бітів ключового потоку.

Далі можна утворити дві матриці розміром m´m:

X(1) = [S(1), S(2), …, S(m)];

X(2) = [S(2), S(3), …, S(m + 1)],

пов'язані співвідношенням

X(2) = A · X(1) mod 2.

Можна довести, що для будь-якої послідовності максимальної довжини матриця X(1) завжди є несингулярна, тому матрицю А можна обчислити як

A = X(2) [X(1)]^–1 mod 2.

Обертання матриці Х(1) потребує (щонайбільш) біля m³ операцій, тому легко виконується за будь-якого розумного значення m.

Для криптографії послідовності максимальної довжини MLSRS можна зробити більш криптостійкими, використовуючи нелінійну логіку. Зокрема, як ключовий потік використовується нелінійно "фільтрований" вміст регістру зсування, а для здобуття послідовності максимальної довжини – лінійний зворотний зв'язок, як це подано на рис.2.15.

Рисунок 2.15 – Лінійний регістр зсування

з нелінійними логічними ланцюгами на виході

Функція f має обиратися у такий спосіб, аби забезпечити оптимальний баланс поміж нулями й одиницями, а „фільтрована” послідовність має розподіл, близький до рівномірного. Необхідно також, аби „фільтрована” послідовність мала великий період. Якщо (2^m – 1) є простим числом (як у прикладі: за m = 3 маємо 2³ – 1 = 7), то „фільтрована” послідовність може мати період (2^m – 1) (при обранні структури зсувового регістру відповідно до незвідного примітивного багаточлена h(X) степеня m). До згаданих значень m належать, зокрема, такі: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, а здобуті в такий спосіб прості числа називаються простими числами Мерсена.

Незважаючи на те, що „фільтровану” вихідну послідовність зазвичай не можна здобути за допомогою m-розрядного зсувового регістру з лінійним зворотним зв'язком, її завжди можна здобути за допомогою зсувового регістру більшої довжини з лінійним зворотним зв'язком. Регістр довжиною (2^m – 1) завжди дозволить це зробити, а іноді для цього придатен і більш короткий регістр.

3 симетричні криптографічні системи

3.1 класичні симетричні криптосистеми

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

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

Різноманітні симетричнікриптосистеми базуються на слідуючих основних класах перетворень.

· Перестановки

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

· Одно- та багатоабеткові підстановки

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

Через деякий час симетричні алгоритми були розділені на два великих класи - блочні і поточні.

· Блочні шифри

Фактично блочний шифр – це система підстановки в абетці блоков (вона може бути як одно- , так і як багатоабетковою залежно від режиму блочного шифру). Застосування блочних алгоритмів криптозахисту допускає поділ переданої в канал зв'язку послідовності символів відкритого тексту на блоки фіксованої довжини з наступним шифруванням кожного блоку окремо. При цьому однаковим шифруючим блокам будуть відповідати однакові шифртексти. В теперешній час блочні шифри є більш розповсюдженими. Так, вітчизняний та амеріканський стандарти шифрування відносяться до блочних шифрів.

· Поточні шифри

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

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

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

· Гаммування

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

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

3.2 Криптосистема Хілла

Лестером Хіллом було сформульовано алгебричний метод, котрий узагальнює афінне підставляння Цезаря

Е_а,b: ;

Е_а,b: t Е_а,б(t);

Е_а,b(t) = at + b (mod m),

де a, b – цілі числа, 0 £ a, b < m; НСД (найбільший спільний дільник) (a, m) = 1, для визначення n-грам

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

Нехай є лінійним перетворенням, описуваним квадратною матрицею, причому

: .

Криптосистема, розроблена Хіллом, базується на лінійній алгебрі.

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

Таблиця 3.1 - Відповідність поміж англійською абеткою та множиною цілих