Генератор псевдовипадкової бітової послідовності з підвищеною крипостійкістю

16/12/2014 11:10am

Автор: Мандрона М.М., Максимович В.М., Герасимчук О.І., Костів Ю.М.

Категории: информационные технологии


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

 

Мандрона Марія    Миколаївна





Мандрона Марія Миколаївна
аспірант, Україна, Львів,
Національний університет «Львівська політехніка»
Львівський державний університет безпеки життєдіяльності

Максимович Володимир Миколайович




Максимович Володимир Миколайович
д-р техн. наук, професор, Україна, Львів,
Національний університет «Львівська політехніка»

Гарасимчук




Гарасимчук Олег Ігоревич
канд. техн. наук, доцент, Україна, Львів,
Національний університет «Львівська політехніка»

 

 

 

 

 

 

 

 

Костів Юрій Михайлович
канд. техн. наук, Україна, Львів,
Національний університет «Львівська політехніка»

 

 

 

Генератор псевдовипадкової бітової послідовності з підвищеною крипостійкістю

В умовах широкого використання обчислювальної техніки і засобів обміну інформацією поширюються можливості її витоку та несанкціонованого доступу до неї зі злочинною метою. Для протидії злочинам або зменшення збитків від них необхідно коректно вибирати заходи і засоби забезпечення захисту інформації. Серед останніх широкого розповсюдження набули криптографічні засоби, невід’ємною складовою частиною яких, в багатьох випадках, є генератори псевдовипадкової бітової послідовності (ГПВБП). Вони використовуються, зокрема,  для генерації ключів, в потокових шифрах, при формуванні цифрового підпису. ГПВБП також широко застосовуються у сфері технічного захисту інформації для пригнічення електромагнітного випромінювання, зашумлення приміщення, при побудові генераторів шуму, скремблерів, та є складовими елементами захисту у мобільному зв’язку. Отже, розроблення якісного та надійного ГПВБП вважається одним із важливих завдань сучасної прикладної та теоретичної криптографії.
На сьогоднішній день є чимало способів формування псевдовипадкових послідовностей, розроблена велика кількість ГПВБП, що різнять своїми характеристиками, основними з яких є: криптостійкість, статистичні характеристики, швидкодія, і технологічність у випадку їх апаратної реалізації.
Метою роботи є розроблення генератора псевдовипадкової бітової послідовності, в якому при збережені високих показників технологічності, швидкодії і статистичних характеристик, притаманних модифікованим адитивним генераторам Фібаначчі (МАГФ) [1-4], досягається підвищення рівня криптостійкості.
У попередній роботі [5] детально розглядалися МАГФ і варіанти покращення їх статистичних характеристик. Генератори такого типу не є криптостійкими, оскільки окрім початкових установок регістрів немає інших засобів для її забезпечення, що очевидно не є достатнім. Тому ми спробували підвищити криптографічну стійкість МАГФ, ускладнивши схему його побудови, доповнивши її додатковими структурними елементами.
На рис. 1 представлена структурна схема ГПВБП на основі МАГФ з підвищеною крипостійкістю, а її спрощене зображення, з окремо виділеним блоком підвищення криптостійкості (БПК), – на рис. 2.
Структурна схема ГПВБП на основі МАГФ
Рис. 1. Структурна схема ГПВБП на основі МАГФ
Спрощена структурна схема ГПВБП на основі МАГФ
Рис. 2. Спрощена структурна схема ГПВБП на основі МАГФ
До складу генератора входять регістри Рг1 – Рг3, комбінаційний суматор КС, логічна схема ЛС, блоки суматорів за модулем 2 БСМ1 і БСМ2, лічильники Лч1 і Лч2 і схеми логічного множення І1 і І2. Робота генератора описується рівняннями:
,                                                       (1)
,  – значення чисел в регістрах Рг1 - Рг3 в поточному і наступному тактах роботи пристрою відповідно,  – число на виході БСМ2, сформоване в результаті додавання за модулем 2 розрядів   числа  на виході БСМ2 і розрядів  числа E(f) на виході Лч2:
.                                                       (2)
В свою чергу число D(t) утворюється додаванням за модулем 2 розрядів  числа B(t) на виході КС і розрядів  числа C(t) на виході Лч1:
.                                                     (3)
Число B(t) формується так:
,                                   (4)
де n – кількість двійкових розрядів структурних елементів схеми
Значення змінної а визначається логічним рівнянням:
,                                            (5)
де  – значення розрядів на виходах БСМ2 (виходах БПК).
Тактові імпульси проходять на вхід Лч1 при умові – , а на вхід Лч2 – якщо . Ці умови можуть змінюватись і входити, поряд із початковими установками Лч1 і Лч2, в ключ, довжина якого буде визначати рівень криптостійкості генератора.
Вихідна бітова послідовність формується на виході молодшого розряду регістра Рг1.
Швидкодія генератора, враховуючи те, що лічильники працюють повільніше від регістрів, може бути оцінена часом спрацювання елементів схеми, таким чином:
,                                      (6)
де  – час спрацювання Лч1 і Лч2,  – час спрацювання КС,   – час спрацювання ЛС ,  – час спрацювання блоків БСМ1 і БСМ2.
Криптостійкість генератора визначається кількістю комбінацій значень можливих варіантів початкових установок Лч1, Лч2 і кількістю можливих варіантів комутації тактових імпульсів елементами логічного множення. Загальна кількість таких варіантів може бути оцінена виразом
,                                          (7)
враховуючи те, що на керуючі входи логічних елементів І1 і І2 можуть подаватись будь-які двійкові розряди числа на виході КС.
На рис. 3 наведено результати аналізу статистичних характеристик вихідної послідовності досліджуваного генератора при різних, довільно вибраних, значеннях початкових станів Лч1 і Лч2.
Статистичні портрети ГПВБП з різними  початковими значеннями лічильникіСтатистичні портрети ГПВБП з різними  початковими значеннями лічильникі                                                               

Рис. 3. Статистичні портрети ГПВБП з різними початковими значеннями лічильників:
а – Лічильник 1=1, Лічильник 2=2; б – Лічильник 1=5, Лічильник 2=7

По вісі абсцис відкладено номер тесту NIST, по вісі ординат – імовірність проходження тесту. Тест вважається пройденим, у тому випадку, коли імовірність проходження тесту потрапить у межі від 0,98 до 1,00, в іншому випадку – тест не пройдено [6, 7]. Для наочності межі довірчого інтервалу позначені пунктирними лініями.
В табл. 1 представлено розширені результати тестування вихідної бітової послідовності генератора при різних початкових значеннях чисел в лічильниках. Отже, статистичні характеристики ГПВБП практично не залежать від початкових станів Лч1 і Лч2.
Таблиця 1.
Результати тестування ГПВБП при зміні початкових значень лічильників


Початкові значення
чисел в лічильниках

Результати тестування NIST

Лічильник 1

Лічильник 2

Кількість тестів

Не пройдених

Пройдених

1

2

1

187

5

7

0

188

23

33

1

187

171

393

1

187

393

171

0

188

1487

2111

0

188

14051

30211

0

188

171078

712731

0

188

23

30211

1

187

30211

23

0

188

Висновки
Проведені дослідження підтвердили високу якість розробленого ГПВБП. Подальше покращення його характеристик можливе при: зміні структури базового МАГФ за рахунок збільшення кількості регістрів запам’ятовуючих попередні значення псевдовипадкових чисел, збільшенні кількості розрядів структурних елементів, ускладнення роботи блоку підвищення криптостійкості БПК.
Література
1. Mascagni M. Parallel Pseudorandom Number Generation / M. Mascagni // Advanced architecture Computers. –1995.  P. 42-48.
2. Anderson P. A Fibonacci-based pseudo-random number generator. [Електронний ресурс]. – Доступний з : http://link.springer.com/chapter/10.1007/978-94-011-3586-3_1#page-1
3. Orue A. B. Trifork, a New Pseudorandom Number Generator Based on Fibonacci Maps / Orue A. B., F. Montoya, L. Hernández Encinas // Journal of computer science and engineering, volume1, issuex, xxx 2010. [Електронний ресурс]. – Доступний з : http://iliasistemas.com/descargas/TRIFORK.pdf
4. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях: учебное пособие / М.А. Иванов, И.В. Чугунков. – М.: Изд-во НИЯУ МИФИ, 2012. – 400 с.
5. Костів Ю.М.  Апаратна реалізація і дослідження модифікованих генераторів Фібоначчі / Ю.М. Костів, В.М. Максимович, М.М. Мандрона, О.І. Гарасимчук // Комп’ютерні технології друкарства. – Львів : Вид-во Української академії друкарства. – 2013. – Вип. 29. – С. 167-174.
6. Мандрона М.М. Дослідження впливу параметрів генератора Голлманна на статистичні характеристики вихідного сигналу / Мандрона М.М., Максимович В.М., Костів Ю.М., Гарасимчук О.І. // Вісник кременчуцького національного університету ім. М. Остроградського. – Кременчук: КрНУ, 2013. – Вип. 4 (81). – С. 98-103. 

  1. Горбенко І.Д. Прикладна криптологія: Теорія. Практика. Застосування: монографія / І.Д. Горбенко, Ю.І. Горбенко. – Харків: Вид-во «Форт», 2012. – 880 с.


Презентация

Контакты

 

 

Контакты

НАШІ КОНТАКТИ:

[email protected]

[email protected]

м. Дніпро

тел. +38 (056) 794-36-74, +38 (056) 794-36-75

моб. +38 (050) 320 69 72

ISSN 20760507

Керівник проекту - Гриньов Володимир Анатолійович

Партнеры