Оптимізація параметрів структурних елементів генератора Джіффі
Результати дослідження генератора Джіффі за різної кількості базових генераторів на основі регістрів зсуву з лінійним зворотним зв'язком і різного степеня їх поліномів, що проведено з використанням тестів NIST. Шляхи оптимізації параметрів генератора.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | украинский |
| Дата добавления | 31.05.2017 |
| Размер файла | 94,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Оптимізація параметрів структурних елементів генератора Джіффі
Постановка проблеми. В умовах стрімкого розвитку інформаційних технологій значно розширюється сфера застосування генераторів випадкових і псевдовипадкових послідовностей (ГПВП). На сьогодні існує чимало різноманітних методів і принципів генерування псевдовипадкових послідовностей, кожен з яких має свої переваги та недоліки [1-5]. Важливе значення серед генераторів псевдовипадкових послідовностей займає генератор Джіффі, проте його якісні характеристики є малодослідженими. Тому виникає задача, що полягає у покращенні характеристик генератора Джіффі з метою отримання на його виході послідовностей, що прямо чи опосередковано можна було б застосовувати у вирішенні задач захисту інформації.
Для того, щоб робити висновок про можливість застосування того чи іншого генератора псевдовипадкової послідовності для вирішення конкретних задач, потрібно виконати оцінювання його якості та надійності. Проведення тестування генераторів, особливо тих, що використовуються в системах захисту інформації (зокрема криптографічних додатках), є актуальною теоретичною та практичною задачею. На сьогодні, для тестування псевдовипадкових послідовностей використовують велику кількість різноманітних графічних та оціночних тестів. Також розроблено кілька програмних продуктів, що містять комплекси тестів для перевірки різних статистичних властивостей псевдовипадкових послідовностей, найвідомішим серед таких продуктів є набір статистичний тестів NIST STS [6, 7].
Мета роботи - використовуючи набір статистичних тестів NIST STS визначити оптимальні параметри структурних елементів генератора Джіффі шляхом зміни принципів побудови його базових генераторів.
Виклад основного матеріалу. Генератор Джіффі забезпечує перемішування двох послідовностей х1 та х2 з виходів двох генераторів М-послідовнос - тей, які ще називають генераторами на основі регістрів зсуву з лінійними зворотніми зв'язками (ЬЕЗЯ) шляхом керування послідовністю з виходу ЬББК 3. Це перемішування здійснюється згідно з функцією
N (Х1, Х2, Х3) = Х1Х3 + Х2Х3 = Х3 © Х1Х2 © Х2Х3, (1)
яка може бути реалізована за допомогою мультиплексора 2^1 (рис. 1) [1].
Генератори М-послідовностей, що є базовими для генератора Джіффі, можуть реалізовуватися різними способами, згідно з рівнянням
генератор джіффі поліном
0 (ї+1)=тда, (2)
де: 0 (ї) і 0 (ї +1) - стани регістра генератора в моменти часу ї і ґ+1 відповідно (до і після приходу синхроімпульсу); Т - квадратна матриця порядку N де N - степінь примітивного полінома. Тому прийнято рішення за допомогою статистичних тестів та шляхом зміни степеня г (а отже, зміни структури самого генератора) визначити, як це впливатиме на якість вихідної псевдовипадкової послідовності з генератора Джіффі.
Рис. 1. Генератор Джіффі
Для дослідження якості обирали базові генератори М-послідовностей не тільки з різними степенями твірного поліному, але також змінювали степінь r, до якого підноситься матриця T.
Оцінювання вихідних послідовностей з генератора виконували за допомогою пакету статистичних тестів NIST STS. Результати аналогічних оцінювань генератора Джіффі, на цей час, в літературі відсутні. Для отримання послідовностей з такого генератора розроблено його імітаційні моделі на мові Delphi, що дають змогу одержувати вихідні послідовності залежно від зміни параметрів. Набір тестів NIST STS містить 15 статистичних тестів, розроблених для перевірки гіпотези про випадковість двійкових послідовностей довільної довжини, що генеруються ГПВП [6].
Тест вважається пройденим, коли ймовірність проходження тесту Р потрапить у межі від 0,98 до 1,00. Якщо ж імовірність Р буде знаходитись нижче 0,98, вважається, що тест не пройдено. За отриманими результатами будуємо статистичний портрет генераторів, який складається з матриці розміром mxq, де m - кількість двійкових послідовностей, які перевіряють, а q - кількість статистичних тестів, які використовуються для тестування кожної послідовності. Кінцеве рішення про випадковість послідовності приймається за результатами сукупності усіх тестів [7].
Тестування проводили за рівня значущості а = 0,01, який рекомендований розробниками NIST STS. Статистичні портрети генераторів (рис. 2 та рис. 3) мають вигляд матриці розміром 1000x188, елементами якої є 188000 значень відповідних ймовірностей. На усіх рисунках довірчий інтервал позначено червоними лініями.
Рис. 2. Статистичний портрет генератора Джіффі №1: а) r=1, б) r=5
Рис. 3. Статистичний портрет генератора Джіффі №4: а) г=1, б) г=5
генератор джіффі поліном
Детальний звіт оцінювання генераторів Джіффі за кожним тестом наведено в таблиці.
Результати здійсненого дослідження свідчать, що із збільшенням степеня г базових генераторів М-послідовностей якість генератора Джіффі покращується, оскільки кількість не пройдених тестів зменшується.
Результати тестування генераторів Джіффі
|
№ |
Статистичний тест |
Номер досліджуваних генераторів |
||||||||
|
1 |
2 |
3 |
4 |
|||||||
|
r=1 |
r=5 |
r=1 |
r=5 |
r= 1 |
r=5 |
r= 1 |
r=5 |
|||
|
1 |
Frequency (Monobit) Test |
- |
- |
- |
+ |
- |
+ |
+ |
+ |
|
|
2 |
Frequency Test within a Block |
- |
- |
- |
+ |
- |
+ |
- |
+ |
|
|
3 |
Cumulative Sums (Cusum) Test |
- |
- |
- |
- |
- |
+ |
+ |
+ |
|
|
4 |
Runs Test |
- |
- |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
5 |
Test for the Longest Run of Ones in a Block |
- |
- |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
6 |
Binary Matrix Rank Test |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
7 |
Discrete Fourier Transform (Specral) Test |
+ |
+ |
|||||||
|
8 |
Non-Overlapping Template Matching Test |
- |
- |
+ |
+ |
+ |
+ |
- |
+ |
|
|
9 |
Overlapping Template Matching Test |
- |
- |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
10 |
Maurer's «Universal Statistical» Test |
+ |
- |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
11 |
Approximate Entropy Test |
- |
- |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
12 |
Serial Test |
- |
- |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
13 |
Linear Complexity Test |
+ |
- |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
14 |
Random Excursions Test |
- |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
|
|
15 |
Random Excursions Variant Test |
- |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
Висновки. За допомогою імітаційного моделювання та статистичного тестування доведено, що змінюючи структуру базових генераторів М-послідовностей, а саме збільшуючи значення степеня r та вибираючи твірний поліном більшого степеня, можна значно покращити якість імпульсної послідовності з виходу генератора Джіффі. Дослідження показали, що оптимальним значенням є r = 5. Подальше збільшення r для великих ступенів твірного поліному не призводить до значного покращення якості вихідної послідовності, але при цьому зростають апаратні затрати на реалізацію такого генератора.
Література
1. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях / М.А. Иванов. - М.: Изд-во КУДИЦ - ОБРАЗ, 2001. - 368 с.
2. Иванов М.А. Теория, применение и оценка качества генераторов псевдослучайных последовательностей / М.А. Иванов, ИВ. Чугунков. - М.: Изд-во КУДИЦ - ОБРАЗ, 2003. - 240 с.
3. Гарасимчук О.І. Генератори псевдовипадкових чисел, їх застосування, класифікація, основні методи побудови і оцінка якості / О.І. Гарасимчук, В.М. Максимович // Захист інформації: зб. наук. праць. - К., 2002. - 7 с.
4. Гарасимчук О.І. Генератори пуассонівського імпульсного потоку на основі генераторів М-послідовностей / О.І. Гарасимчук, В.М. Максимович // Вісник Національного університету «Львівська політехніка». - Сер.: Комп'ютерні науки та інформаційні технології. - Львів: Вид-во НУ «Львівська політехніка». - 2004. - №521. - С. 17-23.
5. Rock A. Pseudorandom Number Generators for Criptographic Applications / A. Rock. - Salzbuburg, 2005. - Pp. 57-65.
6. Статистические тесты NIST. [Электронный ресурс]. - Доступный с http://ru.wikipe - dia.org/wiki/Статестичиские_тесты_NIST.
7. NIST SP 800-22. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. [Electronic resource]. - Mode of access http://csrc.nist.gov/publicati - ons/ni stpub s // SP800-22rev 1 a.pdf.
Размещено на Allbest.ru
...Подобные документы
Теоретические основы нейминга. Методология создания имени. Алгоритм работы генератора названий и разбиения слова на слоги. Разработка функции деления слова на слоги. Осуществление группировки слогов в слова. Рождение имен. Анализ полученного генератора.
курсовая работа [35,5 K], добавлен 26.05.2009Розробка іспитового стенда для лабораторії, визначення тривалості робіт, ресурсів на її виконання. Характеристика параметрів моделі до оптимізації. Очікувана тривалість робіт за проектом. Причини та критерії оптимізації моделі. Розрахунок бюджету проекту.
контрольная работа [1,1 M], добавлен 09.11.2015Розробка інтелектуального програмного продукту для рішення завдання оптимізації у заданій предметній області. Алгоритм розрахунку пласкої конічної передачі. Оптимізація параметрів та вибір мови програмування. Приклад розрахунку конічної передачі.
курсовая работа [1,5 M], добавлен 24.06.2013Процес послідовної передачі даних, режим її здійснення. Типова схема інтерфейсу. Структурна схема модуля шифрування. Розробка генератора псевдовипадкових чисел на основі регістра зсуву з оберненими зв’язками. Симуляція роботи розробленої моделі пристрою.
курсовая работа [594,1 K], добавлен 09.04.2013Розробка програми, яка розраховує параметри магнітних ланцюгів генератора постійного струму і асинхронного двигуна, з можливістю імпорту результатів розрахунків в документ Word, а також передбачена можливість збереження результатів в текстовому файлі.
курсовая работа [1,2 M], добавлен 17.04.2009Структура и функции генератора случайных чисел. Методы предельного уменьшения ошибки второго рода. Усиление шумового сигнала. Его дискретизация по времени и аналого-цифровое преобразование. Формирование случайной последовательности и ее корреляция.
курсовая работа [299,4 K], добавлен 11.12.2014Разработка программно управляющего задающего генератора пачек прямоугольных импульсов на микропроцессоре. Составление алгоритма и написание программы генерирования импульсов определённой длительности. Расчет временных соотношений и анализ погрешностей.
дипломная работа [3,2 M], добавлен 26.12.2011Анализ способов построения генераторов случайных чисел для криптографических задач. Анализ генератора случайных чисел на основе магнитометров. Анализ статистических свойств двоичных последовательностей, полученных путем квантования данных магнитометра.
дипломная работа [2,5 M], добавлен 06.05.2018Дослідження складної системи "Велосипед" з елементами, з'єднаними детермінованим зв'язком. Побудова цільової функції для оптимізації системи, визначення її надійності та вартості приросту надійності її елементів. Блок-схема процесу функціонування системи.
курсовая работа [99,0 K], добавлен 01.03.2014Визначення двовимірних масивів. Розміщення елементів на головній та бічній діагоналі. Алгоритми обробки двовимірних масивів. Двовимірні масиви в задачах лінійної алгебри. Ініціалізація елементів матриці за допомогою генератора псевдовипадкових чисел.
контрольная работа [162,8 K], добавлен 02.12.2014Системы стабилизации частоты синхронного генератора. Передаточные функции для разомкнутой и замкнутой системы. Переходная характеристика системы стабилизации частоты синхронного генератора. Качество непрерывных линейных систем автоматического управления.
контрольная работа [1,0 M], добавлен 03.02.2022Сутність алгоритму розв’язку задачі на оптимізацію конічної передачі. Оптимізація параметрів, підстави до розробки, призначення та вимоги до програмного продукту, вибір моделі його створення. Особливості діаграми прецедентів та умови виконання програми.
курсовая работа [1,6 M], добавлен 12.06.2013Розрахунок оптимального діаметру теплової мережі енергосистеми теплопостачання від джерела до споживача, при змінній швидкості теплоносія та діаметра теплообмінника. Розробка програми за допомогою алгоритмічної мови програмування QBasic і Microsoft Excel.
курсовая работа [1,0 M], добавлен 02.01.2014Визначення параметрів цифрового сигналу на виході АЦП. Розробка структури цифрового лінійного тракту, розрахунок його завадостійкості. Аналіз роботи демодулятора. Ймовірність помилкового прийому комбінації коду Хемінга та безнадлишкового коду МТК-2.
курсовая работа [1,1 M], добавлен 06.08.2013Створення системи експериментального дослідження математичних моделей оптимізації обслуговування складних систем. Визначення критеріїв оптимізації обслуговуваних систем та надання рекомендацій щодо часу проведення попереджувальної профілактики.
дипломная работа [3,0 M], добавлен 22.10.2012Розрахунок оптимального діаметру теплової мережі системи теплопостачання від джерела до споживача при змінній швидкості теплоносія та витратах на електроенергію у середовищі Microsoft Excel та за допомогою алгоритмічної мови програмування Quick Basic.
курсовая работа [38,0 K], добавлен 09.11.2010Оптимізація як цілеспрямована діяльність, що полягає в здобутті найкращих результатів за відповідних умов: критерії, постановка задачі, основні завдання. Розгляд методів дослідження функцій класичного аналізу. Особливості застосування принципу максимуму.
контрольная работа [377,6 K], добавлен 19.12.2012Аналіз основних операцій спецпроцесора обробки криптографічної інформації, його синтез у модулярній системі числення та дослідження математичної моделі надійності. Виведення аналітичних співвідношень для оцінки ефективності принципу кільцевого зсуву.
дипломная работа [1,8 M], добавлен 15.10.2013Методика розробки мережі із заданими параметрами. Розрахунок швидкості надходження елементів даних в систему, утилізації одного сервера, функції Ерланга та коефіцієнту Пуасона. Середній час обслуговування для елементів даних в черзі. Лістинг програми.
контрольная работа [493,5 K], добавлен 21.10.2013Поняття черги в програмуванні, основні операції з чергою і їх реалізація. Опис алгоритму й специфікація програми. Розробка додатку з використанням задачі Ларсона по опису зв'язного неорієнтованого графа. Алгоритм розв’язку і результати виконання програми.
курсовая работа [1,1 M], добавлен 14.09.2012
