Lab_5_AOK_1

Генератори псевдовипадкових послідовностей на основі регістрів зсуву з лінійним зворотним зв’язком: Методичні вказівки до лабораторної роботи №5 з дисципліни “Алгоритмічні основи криптології” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, Ю.М.Костів - Львів: НУЛП 2012. - 15 с.

Укладачі: А.Е.Лагун, к.т.н., доцент Ю.М.Костів, асистент

Відповідальний за випуск:

Л.В. Мороз, к.т.н., доцент

Рецензент: В.М.Максимович, д.т.н., професор

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

1.ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ

1.1.Регістри зсуву

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

-послідовності, які генерують РЗЛЗЗ, мають хороші статистичні властивості;

-їх поведінка легко аналізується з використанням алгебри;

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

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

Найпростішим типом регістрів зсуву є регістр зсуву з лінійним зворотним зв'язком або РЗЛЗЗ (рис.1). Двійкові псевдовипадкові періодичні послідовності, що генеруються з використанням регістрів зсуву з лінійним зворотним зв'язком, називаються РЗЛЗЗ-послідовностями або лінійними рекурентними послідовностями.

Від певних комірок регістра робляться відведення, або точки знімання, вміст цих комірок додається за модулем 2, а сума повертається в першу комірку регістра зсуву. (На рис.1 qi {0,1} позначають наявність або відсутність точки відведення у даної комірки. Символ позначає операцію сума за mod 2.)

Рис.1. Регістр зсуву з лінійним зворотнім зв’язком

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

Розглянемо основні властивості алгебри регістрів зсуву з лінійним

послідовності можуть бути виражені в термінах теорії Галуа стосовно заданого многочлена.

єелементом кільця степеневих рядів з цілочисельними коефіцієнтами за mod 2.

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

розмахом а (і позначається span(a)); цей параметр є мірою криптографічної стійкості послідовності. Такий регістр зсуву (мінімального розміру) може бути знайдений ефективним способом за допомогою алгоритму Берлекампа-Мессі.

4.Функція побітової суми двох двійкових псевдовипадкових

ж буде і побітова сума C X , а її еквівалентний лінійний розмах не перевищує суми лінійних розмахів а і b.

5.За визначенням, m-послідовність - це послідовність РЗЛЗЗ

максимально можливого періоду T 2r 1 (де r - кількість комірок регістра). Крім того, відомо, що m-послідовності - це послідовності, які генеруються регістрами з примітивними поліномами зворотного зв'язку. Такі послідовності збалансовані (мають однакову кількість нулів і одиниць) і мають властивість

де Брюїна: у кожному окремому періоді m- послідовності довільна ненульова підпослідовність довжини r з'являється лише один раз.

Багато сучасних потокових шифрів сконструйовані на основі комбінування виходів від декількох РЗЛЗЗ різними нелінійними способами.

1.2 Регістри Фібоначчі і Галуа, їх програмна реалізація.

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

Регістри Фібоначчі (рис.1). Функція зворотного зв'язку – це додавання операцією XOR певних біт регістра.

Для прикладу візьмемо многочлен x32 x7 x5 x3 x2 x 1. Це означає, що якщо взяти 32-бітовий регістр зсуву і генерувати нові біти XORдодаванням тридцять другого, сьомого, п'ятого, третього, другого і першого бітів, то результуюча послідовність матиме максимальний період - вона пройде

через 232 1 значення до того, як почне повторюватися.

РЗЛЗЗ в програмній реалізації працюють досить повільно, і швидкість можна збільшити застосуванням для програмування мови Асемблер замість Сі. Ще одне можливе рішення - запускати 16 РЗЛЗЗ (або 32, залежно від розміру слова в комп'ютері) у паралельному режимі. Така схема використовує масив слів таким чином, що кожна бітова комірка регістру представлена окремим РЗЛЗЗ. За умови, що всі вони мають один і той же поліном зворотного зв'язку, така схема працює досить швидко. У загальному випадку найкращий спосіб оновлювати стани регістрів зсуву - це множити поточний стан на відповідні двійкові матриці.

Регістри Галуа. У РЗЛЗЗ можна модифікувати схему зворотного зв'язку перетворивши регістр в так звану "конфігурацію Галуа". Не можна сказати, що результуючий генератор стає кращим з криптографічної точки зору, але він теж може мати максимальний період і простий в програмній реалізації. У цій схемі замість використання біт з точок знімання для генерації нового найлівішого біта, до кожного біта з точки знімання і виходу генератора застосовується операція XOR і результат замінюється сумою, що вийшла; потім вихід генератора стає новим самим лівим бітом. Таким чином, на відміну від регістру Фібоначчі, де зворотний зв'язок є функцією від всіх комірок в регістрі, а результат поміщається в найлівішу комірку, зворотний зв'язок в регістрі Галуа потенційно застосовний до кожної комірки регістра, хоча є функцією тільки від значення найправішої комірки.

Вихідний b 9 b 8 b7 b 6 b 5 b4 b 3 b 2 b 1 b0 біт

Рис.2. Схема регістру Галуа з лінійним зворотним зв’язком

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

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

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

1.3. Статистичні тести

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

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

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

послідовностей довжини N - це функція T: B N {"прийняти", "відкинути"},

і решту послідовностей – "хороші" або "випадкові".

Ймовірність того, що вироблена генератором послідовність буде відкинута

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

довжини N в дійсні числа. Тобто, якщо позначити R N послідовність з N статистично незалежних і симетрично розподілених двійкових випадкових

до одного з відомих ймовірнісних розподілів. Найчастіше це нормальний розподіл або розподіл -квадрат з d ступенями свободи (де d - деяке додатне ціле число). Оскільки для цих розподілів доступні числові таблиці, то подібний вибір істотно спрощує визначення порогів t1 і t2 при заданих і N. Нормальний закон розподілу використовують в тих випадках, коли підсумовується велика кількість незалежних і ідентично розподілених випадкових величин. Розподіл - квадрат з d ступенями свободи - коли підсумовуються квадрати d незалежних і нормально розподілених випадкових величин з нульовим середнім і дисперсією рівною 1.

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

розподілене у відповідності з біноміальним законом розподілу, добре

нормальним законом розподілу з нульовим середнім і одиничною дисперсією,

послідовних блоків довжиною L (наприклад L=8), і визначається число ns (s N )

апроксимується розподілом 2 з 2-ма ступенями свободи, оскільки члени суми

Значення матсподівання E( f ) і дисперсії D( f ) функції f , зведені Маурером в таблицю і обчислені з припущенням, що s(i) незалежні. Для дисперсії також введено множник

Остаточна статистика:

c(L, K ) D( f )

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

для цього тесту, складає l (10 2l 1000 2l ) біт.

Таблиця 1. Значення математичного сподівання і дисперсії для універсального тесту

1.3.6. Тест повторень

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

У класичному завданні про розміщення розглядається експеримент, що полягає у киданні R куль випадковим чином в N урн, так що ймовірність попадання кожної кулі в будь-яку конкретну урну складає 1/N. Кількість