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

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

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

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

Чому шифруючу послідовність достатньо обмежити лише одним бітом на біт вихідного тексту? Справа в тому, що в арифметиці за модулем 2, до якої відносяться будь-які перетворення над бітами, існують тільки дві оборотні операції що виключає АБО (англ. exclusive OR - XOR,воно ж - додавання по модулю 2) і заперечення . Оборотною називається функція, у якої, знаючи результат і всі операнди, крім одного, можна відновити цей невідомий операнд.

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

Отже, як би багато ми не створювали шифруючих біт на один бітвихідного тексту, всі їх доведеться накладати на цей біт шляхом комбінації з операцій XOR і заперечень. Але заперечення можна вносити всередину операції XOR-для будь-яких a і b:

NOT (a XOR b) = a XOR (NOT b) = (NOT a) XOR b

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

р XOR F(g1, g2, g3,…), де p - вихідний біт (від англ. plain-відкритий), gi - шифруючі біти, F - деяка функція, що містить в якості операцій виключає АБО і заперечення. Очевидно, що логічніше відразу зробити це перетворення над проміжними бітами gi і отримати в результаті лише один біт шифруючий g. У результаті вся формула шифрування набуде універсального вигляду: с = р XOR g, де с - зашифрований біт (від англ. ciphered - Зашифрований).

Усі сучасні потокові шифри діють за цією схемою. Біт шифрування, що виходить на кожному новому кроці автомата, як і цілий набір таких біт, прийнято позначати символом γ (гама), а самі потокові шифри отримали через це другу назву - шифри гамування. Класичним шифром гамірування є, наприклад, шифр Вермана. Загальна схема шифрування потоковим шифром наведено малюнку 6.2.2.1.

Малюнок 6.2.2.1- Шифрування потоковим шифром у загальному вигляді

Зашифруємо слово "кіт". Використовуємо ASCII-коди символів та їх бінарне уявлення:

до - 170 - 10101010;

про - 174 - 10101110;

т - 226 - 11100010.

Тобто. послідовність для шифрування має вигляд: 101010101010111011100010.

Для шифрування візьмемо ключ: абв - 160,161,162 - 101000001010000110100010. Для кожного конкретного алгоритму ключ формується по-своєму.

Зробимо шифрування операцією XOR:

Отримана послідовність розбивається 8 біт. Далі знаходимо ASCII-коди отриманих чисел. Отримуємо "UV?".

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

Вихідна послідовність розбивається по 8 біт. Отримуємо 170, 174, 226 - "кіт".

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

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

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

Ключ є необхідною частиною шифру, що гамує. Якщо ключ і схема породження гами не є секретним, то потоковий шифр перетворюється на звичайний перетворювач-кодер - скремблер (від англ. Scramble - перемішувати, збивати). Скремблери широко використовуються в системах зв'язку для поліпшення статистичних характеристик сигналу, що передається. Частота появи одиниць і нулів в обробленому скремблер потоці близька до (0,5), що дає виграш в якості передачі сигналу. Крім того, часта зміна нулів і одиниць необхідна в багатьох системах синхронізації - по моменту зміни значення (фронту) сигналу з "0" на "1" або з "1" на "0" приймальна сторона коригує свої генератори синхроімпульсів. Часто щодо потокових шифрів за аналогією зподібними кодерами вживається термін "скремблер".

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

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

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

Таблиця 6.2.2.1 – Властивості різновидів потокових шифрів

Гамма залежить від біт вихідного чи зашифрованого тексту	Гамма НЕ залежить від біт вихідного чи зашифрованого тексту
Гамма залежить від номера поточного такту шифрування	(-) дешифратор втрачає синхронізацію при помилці "вставка/пропуск біта" в каналі зв'язку (-) дешифратор розмножує помилки "спотворення біта" в каналі зв'язку (+) схема стійка до атаки за відомимвихідному тексту	(-) дешифратор втрачає синхронізацію при помилці "вставка/пропустка біта" в каналі зв'язку (+) дешифратор не розмножує помилки "спотворення біта" в каналі зв'язку (+) схема стійка до атаки за відомим вихідним текстом
Гамма НЕ залежить від номера поточного такту шифрування	(+) дешифратор не втрачає синхронізації при помилці класу "вставка/пропуск біта" в каналі зв'язку (-) дешифратор розмножує помилки класу "спотворення біта" в каналі зв'язку (-) схема не стійка до атаки за відомим вихідним текстом

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

Найпростішими схемами, що використовуються як базові при побудові інших, стійкіших, потокових шифрів, є лінійні регістри зсуву - ЛРС (англ. linear feedback shift registers - LFSR). Їх будова дуже проста: пристрій являє собою кілька (від 20 до 100) осередків пам'яті, в кожній з яких може зберігатися один біт інформації. Сукупність біт, що у цей час у ЛРС, називається його станом. Для вироблення чергового біта послідовності, що шифрує, тобто гами, ЛРС виробляє один цикл перетворень, званий тактом, за наступним алгоритмом.

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

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

Схематично лінійний регістр зсуву виглядає, як показано малюнку 6.2.2.2.

Рисунок 6.2.2.2 - Загальний вигляд лінійного регістру зсуву

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

При досить довгій роботі скремблера неминуче виникає його зациклювання — кількість усіляких варіантів станів ЛРС звичайно, а отже, після виконання певної кількості тактів у його осередках створиться комбінація біт, яка в ньому одного разу вже опинялася. З цього моменту послідовність, що кодує, почне циклічно повторюватися з фіксованим періодом. Якщо уявити безліч станів ЛРП і переходів між ними у вигляді графа, то в залежності від номерів осередків, що породжують зворотний зв'язок, можуть вийти різні топології. Деякі їх наведені малюнку 6.2.2.3.

Рисунок 6.2.2.3 - Приклад роботи лінійного регістру зсуву

Цикл "000" характерний для всіх графів через будову ЛЗК. На малюнку 6.2.2.4 (а) крім "нульового" циклу видно ще два цикли - з 3-х станів і з 4-х. На малюнку 6.2.2.4 (б) ланцюжок сходить до циклу з 3-х станів і вже ніколи звідти не виходить. І, нарешті, малюнку 6.2.2.4 (в) всі можливі стану, крім нульового, об'єднані в один замкнутий цикл. Вочевидь, що у тому випадку, коли все 2 N -1 станів системи (де N — розрядність ЛРС), крім нульового, утворюють єдиний цикл, період повторення гами максимальний, а кореляціяміж довжиною циклу та початковим станом регістру (тобто ключем), яка призвела б до появи слабших ключів, відсутня.

Малюнок 6.2.2.4 - Графи лінійного регістру зсуву

З множини генераторів ПНД заданої розрядності в часи, коли вони реалізовувалися на електричній або мінімальній електронній базі, вибиралися схеми з мінімальною кількістю відводів на зворотний зв'язок. Зазвичай генератора ПНД будь-якої бажаної розрядності можна досягти за 2, 3 або 4 відводи. Однак дуже великі відстані між відводами зворотного зв'язку, які неминуче з'являються при поєднанні малого числа відводів і великої розрядності ЛРС, також можуть негативно позначитися на стійкості послідовності шифруючої до криптоаналізу.