Ю Костів, В Максимович, М Мандрона - Використання статистичних тестів ніст сша для дослідження генераторів м -послідовностей - страница 1

Страницы:
1 

помещениях: методика расчета: РД5.0173-87. - М.: РТП НПО "Ритм", 1988. - 160 с. 4. Халяпин Д.Б. Защита информации. Вас подслушивают? Защищайтесь! / Д.Б.Халяпин. - М.: НОУ ШО "Баярд", 2004. - 432 с. 5. Кузавков В.В. Модель розповсюдження мовного сигналу і його ізоляція вікном /В.В. Кузавков, М.В. Логінов // Зб. наук. праць ВІТІНТУУ „КПІ" - 2010. - № 2. - С. 53-58. 6. Методика контролю захищеності мовної інформації від витоку акустичним та віброакустичним каналами: НД ТЗІ 2.3-017-08. - К. : ДССЗЗІ України, 2008. - 18 с. 7. Блінцов В.С. Головні завдання забезпечення інформаційної безпеки на водному транспорті та об'єктах морської інфраструк­тури / В. С. Блінцов // Сучасні проблеми інформаційної безпеки на транспорті: матеріали всеукраїнської науково-технічної конференції з міжнародною участю. - Миколаїв: НУК, 2011. -С. 24 - 27. 8. Клюкин И.И. Судовая акустика: учебное пособие / И.И. Клюкин, А.А. Клещёв. - Л.: Судостроение, 1981. - 144 с.

 

 

 

УДК 621.317.083

Ю. Костів, В. Максимович, М. Мандрона, Ю. Рибак

Національний університет "Львівська політехніка", кафедра безпеки інформаційних технологій

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

© Костів Ю., Максимович В., МандронаМ., РибакЮ., 2012

Сформульовано вимоги до генераторів псевдовипадкових імпульсних послідов­ностей при їх використанні в криптографії та для імітації вихідних сигналів дози­метричних детекторів. Наведено результати тестування п'яти генераторів М-по-слідовності і на їх основі зроблено висновки щодо випадковості їх вихідних сигналів.

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

The paper presents the requirements for pseudorandom pulse sequence generators for their use in simulation of the dosimeter detectors output signals, as well as for their use in cryptography. The paper presents the results of testing of five M - sequences generators and conclusions about their randomness.

Key words: pseudorandom generator, protection of information, pseudorandom numbers, statistic characteristics.

 

Вступ

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

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

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

Метою роботи є використання статистичних тестів Національного інституту стандартів і технологій (НІСТ) США для тестування генераторів М-послідовностей.

 

82

Вимоги до генераторів псевдовипадкових чисел і генераторів псевдовипадкових імпульсних послідовностей

У разі використання ГПІП для імітації вихідних сигналів дозиметричних детекторів ставляться такі вимоги [1]:

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

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

-          швидкодія ГПІП має забезпечувати формування вихідних імпульсів у заданому час­тотному діапазоні;

-          ГПІП повинні забезпечувати можливість оперативної зміни середньої частоти вихідних імпульсів, що дає змогу досліджувати динамічні властивості вимірювальних пристроїв.

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

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

-          проходити «тест на наступний біт». Суть тесту така: не повинно існувати поліноміального алгоритму, який, знаючи перші k біт випадкової послідовності, зможе передбачити k +1 біт з імовірністю понад 50 %;

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

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

-          мати великий період формованої послідовності;

-          мати ефективну апаратну і програмну реалізацію.

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

 

Генератори М-послідовностей

М-послідовність, або послідовність максимальної довжини, - псевдовипадкова двійкова послідовність, породжена регістром зсуву з лінійними зворотними зв'язками і максимальним періодом.

Варіанти побудови ГПЧ на основі генератора М-послідовностей необхідно розглядати, враховуючи рівняння його функціонування

Q(t +1) = TrQ(t), (1)

де Q(t) i Q(t+1) - стани регістра генератора двійкової послідовності в моменти часу t i t+1 (до і після синхроімпульсу), Т - квадратна матриця порядку N вигляду

T1 =

0  ...  0  0 aN
1    0           0     0                 1   ...  0  0 aN-1

0    1           0     0  або T2 =

0 ... 1 0 a2
0  0 ...   1    0                        0 ... 0 1 a1

N - степінь многочлена

Ф(х ) = £ aiXi,   aN = a0 = 1,   а^{0,1},   j = 1,(N -1), (2)

i=0

r - натуральне число.

Якщо k=1 і Т=Т1, генератор має вигляд, поданий на рис. 1, а при k=1 і Т=Т2 - на рис. 2.

 

 

83


тО______________________________ I____________________________ I

 

 

 

 

 

 

 

 

 

 

Пакет статистичних тестів Національного інституту стандартів і технологій

Національний інститут стандартів і технологій (США) (The National Institute of Standards and Technology) - підрозділ управління з питань технологій США, одного з агентств міністерства торгівлі США. Місія Інституту - "просувати" інноваційну та індустріальну конкуренто­спроможність США шляхом розвитку наук про виміри, стандартизації та технології з метою підвищення економічної безпеки та покращення якості життя.

Статистичні тести НІСТ [3] - пакет статистичних тестів, розроблений головною організацією НІСТ, яка є лабораторією інформаційних технологій (Information Technology Laboratory). До складу пакета входять 15 статистичних тестів, метою яких є визначення міри випадковості двійкових послідовностей, згенерованих апаратними чи програмними засобами. Ці тести основані на різних статистичних властивостях, притаманних тільки випадковим послідовностям.

Ці статистичні тести застосовуються для порівняння псевдовипадкових послідовностей з істинно випадковою послідовністю.

 

84

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

Статистичні тести НІСТ призначені для перевірки певної нульової гіпотези Н0 про те, що послідовність, яка перевіряється, є випадковою. З цією нульовою гіпотезою пов'язана альтер­нативна гіпотеза На про невипадковість послідовності. Для кожного тесту отримують висновок, що дає змогу відхилити нульову гіпотезу, ґрунтуючись на сформованій досліджуваним генератором послідовності.

Кожен тест оснований на обчисленні значення тестової статистики, яка є функцією даних.

Тестова статистика використовує обчислення значення Р-value, за допомогою якого і ви­значається, чи певна послідовність є випадковою. Якщо значення Р-value дорівнює 1, то послідовність абсолютно випадкова; Р-value, яке дорівнює 0, вказує, що послідовність абсолютно невипадкова. Для тесту необхідно вибрати рівень значущості а. Якщо значення Р-value більше або дорівнює а, то приймається нульова гіпотеза, тобто послідовність є випадковою. Якщо значення Р-value менше за а, то нульова гіпотеза відхиляється, тобто послідовність не є випадковою. Як правило, значення а вибирається в інтервалі [0.001, 0.01].

Якщо значення а дорівнює 0.001, це говорить про те, що з 1000 випадкових послідовностей тест не пройде лише одна. Якщо Р-value>0.001, послідовність розглядається як випадкова із імовірністю 99.9 %. При Р-value<0.001 послідовність розглядається як невипадкова з імовірністю 99.9 %. Якщо значення а дорівнює 0.01, це свідчить про те, що з 100 випадкових послідовностей тест не пройде лише одна. При Р-value>0.01 послідовність розглядається як випадкова із імовірністю 99 %. Якщо Р-value<0.01, послідовність розглядається як невипадкова з імовірністю

99 % [1].

 

Методика тестування генераторів псевдовипадкових чисел на випадковість

Процес дослідження генераторів псевдовипадкових чисел на випадковість складається з таких кроків:

1.        Генерація псевдовипадкової послідовності для тестування.

2.        Виконання набору статистичних тестів.

3.        Аналіз проходження статистичних тестів.

4.        Прийняття рішення щодо випадковості досліджуваної послідовності.

У цій роботі для генерації псевдовипадкових послідовностей використовуються п'ять генераторів М-послідовностей, побудованих на основі многочленів Ф(х)=1+х19+х24, Ф(х)=1+х9+х14+х29, Ф(х)=1+х11+х19+х25+ х31, Ф(х)=1+х18+ х31, Ф(х)=1+х10+ х12+ х19+ х24+ х30.

Для тестування генераторів використовуються сім тестів з пакета НІСТ:

1.         Частотний побітовий тест.

2.         Частотний блоковий тест.

3.         Тест на послідовність однакових бітів.

4.         Тест на найдовшу послідовність одиниць в блоці.

5.         Спектральний тест.

6.         Тест перевірки серій.

7.         Тест приблизної ентропії.

На основі цих тестів написано програми мовою C#.

Тестами № 1, 2, 3, 4, 6, 7 досліджуються послідовності довжиною 1048576 біт, а тестом № 5 -послідовність довжиною 262144 біти.

Результати проходження статистичних тестів оцінюють в процесі аналізу тестової статистики. Існує три варіанти оцінки тестової статистики:

1.    Аналіз на основі порогового значення. Якщо тестова статистика менша або більша від порогового значення, тоді послідовність не є випадковою.

2.    Аналіз на основі фіксованих інтервалів. Якщо тестова статистика виходить за межі встановленого інтервалу, послідовність не є випадковою.

 

85

3. Аналіз на основі імовірнісних значень. Для тестової статистики обчислюється значення P-value.

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

Для того, щоб генератор пройшов тест, значення змінної P-value повинно бути більшим за рівень значущості а, тобто за 0,01, в іншому випадку тест не пройдений. Коли тест пройдений, послідовність вважається випадковою з імовірністю 99 %. Якщо значення Р-value дорівнює 1, то послідовність абсолютно випадкова; те, що Р-value дорівнює 0, вказує, що послідовність абсолютно невипадкова, отже, чим більше значення змінної P-value, отриманої під час тестування, тим ближчі властивості досліджуваної послідовності до властивостей абсолютно випадкової послідовності.

 

Параметри досліджуваних генераторів

У цій роботі тестуються п'ять генераторів М-послідовностей, які побудовані на основі таких многочленів:

Ф(х)=1+х19+х24 - генератор М-послідовності варіант А; Ф(х)=1+х9+х14+х29 - генератор М-послідовності варіант Б; Ф(х)=1+х11+х19+х25+ х31 - генератор М-послідовності варіант В; Ф(х)=1+х18+ х31 - генератор М-послідовності варіант Г; Ф(х)=1+х10+ х12+ х19+ х24+ х30 - генератор М-послідовності варіант Д. У генераторах використовується матриця вигляду Т1, степінь матриці г = 1.

 

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

86



У таблиці наведено результати тестування п' яти генераторів М-послідовностей статис­тичними тестами НІСТ.

Висновки

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

 

1. Методи і засоби опрацювання вихідних сигналів дозиметричних детекторів / Ю.Я. Бобало, В.Б. Дудикевич, В.М. Максимович, В.О. Хорошко та ін. - Львів : Видавництво Нац. ун-ту "Львівська політехніка", 2009. - 200 с. 2. Горбенко І.Д. Прикладна криптологія /І.Д. Горбенко, Ю.І. Горбенко. - Харків: Форт, 2012. - 870 с. 3. NIST SP 800-22. A Statistic Test Suite for Random and Pseudorandom Number Generators for Cryptographic Application: [Електронний ресурс]. April 2000. -Режим доступу: http://csrc.nist.gov./publications/niatpubs//SP800-22rev1a.pdf.

 

 

 

УДК 681.322.067

О.А. Нємкова1, В.М. Чаплига1, З.А. Шандра2

Львівський інститут банківської справи, 2Національний університет "Львівська політехніка"

СТІЙКИЙ МОБІЛЬНИЙ ЗВ'ЯЗОК В УМОВАХ ШТУЧНИХ ЗАВАД

© Нємкова О.А., Чаплига В.М., Шандра З.А., 2012

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

Ключові слова: мобільний зв'язок, глушники мобільних телефонів, завадо­стійкість, швидке перетворення Фур'є.

This work deals with the possibility of the steady signal transmission at the expense of its special modulation. It is shown, that there is a criterion, at implementation of which, the reproduction of the signal is satisfactory. By means of computer modeling by MathCAD recommendations about definition of parameters of modulation, proceeding from character of noise are given.

Key words: mobile communications, cell phone silencers, noise immunity, Fast Fourier transform.

 

Вступ

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

 

87

Страницы:
1 


Похожие статьи

Ю Костів, В Максимович, М Мандрона - Використання статистичних тестів ніст сша для дослідження генераторів м -послідовностей