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

Размещено на http://www.allbest.ru/

УДК 004.421.5

ПРОЕКТУВАННЯ ГЕНЕРАТОРІВ ПСЕВДОВИПАДКОВИХ БІТОВИХ ПОСЛІДОВНОСТЕЙ ЗА СИСТЕМНО-ТЕОРЕТИЧНИМ ПІДХОДОМ

М. Мандрона1, В. Максимович2, Ю. Костів2, О. Гарасимчук3

1Кафедра управління інформаційною безпекою

Львівського державного університету безпеки життєдіяльності,

2Кафедра безпеки інформаційних технологій,

3Кафедра захисту інформації,

Національного університету “Львівська політехніка”

© Мандрона М., Максимович В., Костів Ю., Гарасимчук О., 2015

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

Ключові слова: криптографічні пристрої, потокові шифри, генератори псевдовипадкових послідовностей, статистичні характеристики.

бітовий послідовність фібоначчі лінійний

The approaches to designing the pseudorandom bit sequences generators are analyzed. By means of system-theoretical approach the modified additive Fibonacci's generator is projected and results of it research are given, among their: period of repetition, statistical characteristics, linear complication, volume of key information (key length) and swiftness.

Keywords: cryptographic devices, stream ciphers, generators of pseudorandom sequences, statistical characteristics.

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

Метою роботи було проаналізувати різні способи проектування генераторів псевдовипадкових послідовностей та використати системно-теоретичний підхід для побудови модифікованого адитивного генератора Фібоначчі (МАГФ).

Підходи до проектування генераторів псевдовипадкових бітів

В роботах [1, 2] зазначено, що існує чотири різних підходи до проектування потокових шифрів, які у повній мірі можна віднести і до проектування ГПВБП - невід'ємної складової цих шифрів:

системно-теоретичний підхід;

інформаційно-теоретичний підхід;

складнісно-теоретичний підхід;

рандомізований підхід.

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

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

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

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

Особливості системно-теоретичного підходу

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

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

При використанні системно-теоретичного підходу проектування ГПВБП необхідно їх перевіряти на відповідність таких критеріїв [1, 2]:

великий період повторення;

велика лінійна складність;

статистичні характеристики;

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

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

критерії нелінійності для логічних функцій, таких як відсутність кореляції m-го порядку, відстань до лінійних функцій і т.д..

При розробленні нових ГПВБП корисно пам'ятати, що криптографія це суміш математики і плутанини, і без плутанини математика може бути використана проти вас [2].

Головною проблемою генераторів, розроблених з допомогою системно-теоретичного підходу, є неможливість доведення їх безпеки. ГПВБП може відповідати усім правилам розробки, але бути небезпечним - не крипостійким. Інший може бути цілком безпечним. Отже, процес проектування ГПВБП є достатньо евристичним [2].

При використанні системно-теоретичного підходу до проектування ГПВБП, вони повинні оцінюватись за такими параметрами:

період повторення, при різних початкових станах структурних елементів;

статистичні характеристики;

лінійна складність;

об'єм ключової інформації (довжина ключа);

швидкодія.

Дослідження характеристик ГПВБП на основі МАГФ

Далі наведені поглиблені дослідження генератора, що запропонований нами в роботах [3-4], на відповідність сформульованим вище вимогам. Цей генератор є базовим і може розглядатись як окрема ланка для створення більш складних багатоланкових пристроїв. Правила побудови багатоланкових генераторів є окремою задачею, яка подібна до задачі побудови РЗЛЗЗ і генераторів з використанням R-блоків на основі примітивних поліномів [5].

Структурна схема ГПВБП на основі МАГФ наведена на рис. 1 [3-4].

Рис. 1. Структурна схема ГПВБП на основі МАГФ

До його складу входять регістри Рг1-Рг3, комбінаційний суматор КС і логічна схема ЛС. Робота генератора описується рівняннями:

,

, (1)

,

де - і - - числа в регістрах Рг1 - Рг3 в поточному і наступному тактах роботи, значення змінної “а” визначається рівнянням

а = а0 xor а1 xor а2 … xor аz, (2)

де (; ), в даному випадку, значення двійкових розрядів числа в регістрі Рг1, а n - кількість двійкових розрядів Рг1 - Рг3 і КС.

Дослідження періоду повторення. Період повторення ГПВБВ на основі МАГФ досліджувався з допомогою імітаційної моделі. Фіксація періоду відбувалась в моменти повторення значень чисел в регістрах Рг1 - Рг3. Складність дослідження полягає в тому, що період повторення потрібно визначати для усіх можливих комбінацій значень початкових чисел в регістрах. При достатньо великих кількостях двійкових розрядів структурних елементів пристрою, ця задача практично не вирішується через неприйнятно великий час моделювання. Так, наприклад, при для повного перебору необхідно кроків (тактів). Якщо частота кроків перебору дорівнює Гц, час повного дослідження займе одну секунду. Якщо n, для повного перебору потрібно кроків, що, при тій самій частоті перебору, займе с або приблизно 32 роки.

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

На рис. 2 представлені результати дослідження періодів повторення генератора - для кількох значень n. Тут

, (3)

де , і - початкові числа в Рг1, Рг2 і Рг3.

аб

в

Рис. 2. Залежності періодів повторення Тр від початкових станів Q0 регістрів Рг1 - Рг3: а) - , б) - , в) -

Наведені результати дають змогу зробити такі висновки стосовно ГПВБП на основі МАГФ:

період повторення Tp істотно залежить від початкових станів регістрів Q0 (аналогічна залежність спостерігається і в інших ГПББП, наприклад, на основі РЗЛЗЗ чи R-блоків [6]);

максимальні значення Tp з ростом числа розрядів n швидко збільшуються;

більше половини значень Tp є близькими до максимальних (50 з 63 перевищують 23 при n=2, 418 з 511 перевищують 417 при n=3, 2783 з 4095 перевищують 1266 при n=4).

Подальше дослідження періоду повторення генератора проводилось таким чином. При визначалось максимальне значення Tp при переборі усіх можливих значень Q1_0, Q2_0 i Q3_0. При фіксувалось значення Q1_0=0, Q2_0=0 і здійснювався повний перебір значень Q3_0. При були зафіксовані значення Q1_0=0, Q2_0=0, Q3_0=2. Значення Q1_0, Q2_0 i Q3_0, що фіксувались, вибирались виходячи із попередніх досліджень з метою досягнення максимально можливих значень Tp.

Результати дослідження максимальних значень Tp наведені в табл. 1.

Таблиця 1 - Результати дослідження ГПВБП на основі МАГФ

Дослідження статистичних характеристик включно з лінійною складністю. Статистичні характеристики досліджувались за допомогою тестів NIST [6], що включають в себе і визначення лінійної складності. Тестувалась бітова послідовність довжиною біт, що знімалась з молодшого розряду регістра Рг1. Результати тестування наведені в табл. 1. Тут прийняті такі позначення: “-” - більшість тестів не пройдені; “-2”, “-1” - не пройдено 2 чи1 тести; “+” - усі тести пройдено.

Отже, при сформована бітова послідовність відповідає вимогам статистичної безпеки.

Визначення об'єму ключової інформації (довжини ключа). Криптографічним ключем даного генератора є початковий стан регістрів Рг1 - Рг3. Повна множина значень цих станів дорівнює при довжині ключа 3n. Однак, статистично безпечною можна вважати тільки ту множину, яка відповідає вихідним бітовим послідовностям, що проходять усі тести NIST. Виходячи із попередніх досліджень ця множина включає в себе не менше значень, що відповідає довжині ключа . Для більш конкретного окреслення цієї множини необхідно виявити закономірності впливу її значень на період повторення і статистичні характеристики вихідного сигналу при відносно малих значеннях n з відповідними узагальненнями на будь-які значення n.

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

, (4)

де , і - час спрацювання Рг, ЛС і КС відповідно. Максимально можлива частота тактових імпульсів дорівнює:

. (5)

Отже, швидкодія генератора, перш за все, залежить від часу спрацювання КС і ЛС, оскільки регістри пам'яті Рг1 - Рг3 працюють синхронно і затримка їх спрацювання дорівнює затримці спрацювання одного тригера.

Швидкодія КС може бути збільшена при використанні відомих способів побудови комбінаційних суматорів з паралельним і послідовно-паралельним переносом і ніяк не впливає на період повторення генератора і його статистичні характеристики.

Час спрацювання логічної схеми ЛС залежить від схемотехніки її реалізації і від кількості членів рівняння (2), яка може бути різною. Зменшення цієї кількості дозволяє істотно підвищити швидкодію пристрою в цілому. Однак, оскільки таке зменшення може вплинути на період повторення пристрою і його статистичні характеристики, необхідно проводити відповідні дослідження (визначення періоду повторення і тестування на відповідність статистичним характеристикам), що для окремих випадків реалізації ГПВБП на основі МАГФ було нами виконано в роботах [3, 4].

Висновки

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

Література

1. Rueppel R.A.., “Stream Cipher”, Contemporary Cryptology: The Science of Information Integrity, G.J. Simmons, ed., IEEE Press, 1992, pp. 65-134.

2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ. - М.: Изд-во “Триумф”, 2002. - 797 с.

3. Мандрона М.Н. Исследование статистических характеристик модифицированных генераторов Фибоначчи / М.Н. Мандрона, В.Н. Максымовыч // Проблемы управления и информатики : межд. наук.-техн. журн. - 2014. - №6. - С. 28-36.

4. Максимович В.М. Апаратна реалізація і дослідження модифікованих генераторів Фібоначчі / Максимович В.М., Гарасимчук О.І., Костів Ю.М., Мандрона М.М. // Комп'ютерні технології друкарства : збірник наукових праць. - Львів : Вид-во Української академії друкарства. - 2013. - № Вип. 29. - С. 167-174.

5. Иванов М.А., Чугунков И.В. Криптографические методы защиты информации в компьютерных системах и сетях: учебное пособие / Под ред. М.А. Иванова. М.: НИЯУ МИФИ, 2012. - 400 с.

6. NIST SP 800-22. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. April, 2010.

Размещено на Allbest.ru