Харківський національний університет радіоелектроніки

Булах Євгеній Вячеславович

УДК 681.3+681.5:007

КІНЦЕВІ АВТОМАТИ З ПСЕВДОВИПАДКОВИМИ

ПЕРЕХОДАМИ І МЕТОДИ ЗАХИСТУ ІНФОРМАЦІЇ

НА ЇХ ОСНОВІ

05.13.13 – Обчислювальні машини, системи та мережі

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Харків 2004

Дисертацією є рукопис.

Робота виконана в Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник

доктор технічних наук, професор

Аліпов Микола Васильович, професор кафедри електронних обчислювальних машин Харківського національного університету радіоелектроніки

Офіційні опоненти: –

доктор технічних наук, професор Хажмурадов Манап Ахмадович, нач. відділу Національного наукового центру "Харківський фізико-технічний інститут"; –

кандидат технічних наук, доцент Лужецький Володимир Андрійович, зав. кафедрою захисту інформації Вінницького національного технічного університету.

Провідна установа:

Національний технічний університет "ХПІ",

кафедра систем інформації, м. Харків

Захист відбудеться 03.03.2004р. о 13-30 годині на засіданні спеціалізованої вченої ради Д64.052.01 у Харківському національному університеті радіоелектроніки за адресою: пр. Леніна, 14, м. Харків, 61166, факс: (0572) 40-91-13.

З дисертацією можна ознайомитися в бібліотеці університету за адресою: пр. Леніна, 14, м. Харків, 61166.

Автореферат розісланий 02.02. 2004р.

Вчений секретар

спеціалізованої вченої ради Саєнко В.І.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках основного напрямку наукових досліджень кафедри "Конструювання ЕОМ" Харківського державного технічного університету радіоелектроніки: "Розробка методів захисту інформації при її збереженні і передачі." Результати дисертації використані в процесі виконання держбюджетних НДР зі створення нових методів захисту інформації при її збереженні і передачі і пов'язані з пріоритетними напрямками розвитку науки і техніки (д/б 190232 "Розробка теорії і методів захисту інформації при її передачі і збереженні"; д\б 190 (520-7) "Система захисту інформації при її передачі в інтелектуальних середовищах") у рамках координаційних планів НДР Міністерства освіти і науки України, де автор брав участь як виконавець, а також використовуються у навчальному процесі при виконанні лабораторних робіт і дипломному проектуванні (акт від 28.01.2004).

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

Для досягнення поставленої мети вирішено такі задачі:–

розробка датчиків віртуальних послідовностей;–

синтез алгоритмів функціонування КА пошуку точки екстремуму унімодальної функції в умовах впливу на процес пошуку регулярної несиметричної і симетричної віртуальної послідовності; –

синтез алгоритмів функціонування КА пошуку точки екстремуму унімодальної функції в умовах впливу на процес пошуку нерегулярної несиметричної і симетричної віртуальної послідовності; –

розробка структур КА, кодуючих і декодуючих пристроїв дискретного каналу;–

створення на основі синтезованих КА підстановних методів захисту інформації.

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

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

Методи дослідження. Досягнуті цілі базуються на комплексному використанні методів теорії графів і математичного програмування. Для дослідження розроблених методів захисту інформації використовується теорія імовірності і комбінаторні методи рішення задач синтезу КА з псевдовипадковими переходами. При синтезі кодуючих і декодуючих структур використана теорія КА.

Наукова новизна отриманих результатів

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

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

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

Практичне значення отриманих результатів полягає в тім, що:–

розроблені структурні схеми нових датчиків віртуальних послідовностей, для організації псевдовипадкових переходів КА з одного стану в інший;–

створено структурні схеми КА, кодуючих і декодуючих пристроїв для дискретного каналу передачі інформації на основі завадостійких до віртуальних послідовностей алгоритмів пошуку;–

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

розраховано невизначеність, що створює КА з псевдовипадковими переходами, яка при передачі 64 цифр восьмеричної системи складає _; –

основні положення, висновки і рекомендації, які викладені у дисертаційній роботі були застосовані при викладанні лекційного курсу "Кінцеві автомати" для студентів спеціальності КСМ (комп’ютерні системи та мережі) у розділі „Кінцеві автомати з псевдовипадковими переходами” та у процесі дипломування (м. Харків, Україна, акт від 10.01.2004), на кафедрі ЕОМ Харківського національного університету радіоєлектроніки ;–

на основі завадостійких алгоритмів, що отримані у дисертаційній роботі, розроблено пристрій керування вихідними потужними електронними ключами за рахунок псевдовипадкових імпульсів з заданими параметрами. Використання таких пристроїв у автономних джерелах електрозабезпечення газорозподільних станцій, які розроблено у НПФ „Газінжінірінг-сервіс” (м. Харків, Україна, акт від 20.09.2003), дозволяє уникнути великих імпульсних низькочастотних навантажень на електрогенератор у разі, якщо потужність споживачів електроенергії сумірна з потужністю турбогенераторної установки.

Особистий внесок здобувача. У роботі [1] розроблено структури віртуальних датчиків завад для несиметричних віртуальних послідовностей невипадкових та випадкових її параметрів; у роботі [2] запропоновано структуру кінцевого автомату з псевдовипадковими переходами з одного стану в другий для дискретного каналу передачі інформації; у роботі [3] розроблена стратегія пошуку та сформульовані правила виділення нового інтервалу невизначеності для завадостійких до нерегулярних вибурювань алгоритмів пошуку точки екстремуму унімодальної функції; у роботі [6] розроблено співвідношення для розміщення точок експерименту на ізнов виділених інтервалах невизначеності; у роботі [7] розроблена логічна схема побудови завадостійкого алгоритму пошуку точки екстремуму унімодальної функції при впливі на неї регулярних несиметричних віртуальних послідовностей.

Апробація результатів дисертації. Результати дисертаційної роботи доповідалися й обговорювалися на 3-му міжнародному молодіжному форумі "Радіоелектроніка i молодь у XXI ст." (Харків, 1999); на 6-й міжнародної конференції "Теорія і техніка передачі, прийому й обробки інформації" – 2 публікації (Харків - Туапсе, 2000) .

Публікації. Матеріали дисертаційної роботи викладено в 7 наукових працях. З них 4 статті в наукових журналах по профілю ВАК і 3 публікації тез доповідей на науково-технічних конференціях.

Структура й обсяг дисертації. Дисертація складається з вступу, чотирьох розділів і висновку, викладених на 148 сторінках, містить 2 додатки, 16 рисунків, 13 таблиць і бібліографію з 98 назв.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

У другому розділі визначено основні вимоги і розроблена структура кінцевого автомата з псевдовипадковими переходами, та дано розв'язання задач синтезу датчиків, симетричних і несиметричних віртуальних послідовностей. Структура кінцевого автомата наведена на рис. 1, де символ _- позначає суматор, що на кожнім такті роботи автомата підсумовує значення двійкового коду символів вхідного алфавіту і значення віртуальної послідовності, яке представлене двійковім кодом; ДВП – датчик віртуальної послідовності, що формує в залежності від параметрів _ (відповідно – амплітуда імпульсу, тривалість імпульсу, часовий інтервал між двома сусідніми імпульсами); ТГ – тактовий генератор; КС – керуючий сигнал.; КА – кінцевий автомат, що здійснює пошук точки екстремуму унімодальної функції у вихідному інтервалі невизначеності.

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

Датчики віртуальної послідовності характеризуються такими параметрами: максимальною амплітудою імпульсу (_), максимальною тривалістю імпульсу (_), часовим інтервалом між двома сусідніми імпульсами (_), що можуть бути випадковими і детермінованими, самі послідовності можуть бути однополярними і двополярними. Приклади цих послідовностей дано на рис. 2. Такі датчики будуються на основі генераторів псевдовипадкових чисел, які рівномірно розподілені в інтервалі [0,1] [1]. У роботі розглянуто схемотехнічна і програмна реалізація таких датчиків.

Рис. 2. Приклади віртуальних

послідовностей для різних значень a, l, H

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

_,

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

Під розв’язуючою функцією розуміють функцію, за якою на _-му кроці алгоритму виділяється новий інтервал невизначеності.

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

Критерієм оптимальності алгоритму пошуку служить мінімаксний критерій виду:

_, (1)

де _ – множина унімодальних функцій; _– довжина інтервалу невизначеності, який отримано на останньому кроці _-го алгоритму; _– множина можливих алгоритмів;_– мінімально можлива відстань між двома сусідніми точками експериментів.

Зворотну величину від _ позначимо _. Вона показує, на скільки рівних частин буде розбитий вихідний інтервал невизначеності за _ кроків _ алгоритмом.

Критерій (1) з урахуванням функції _ можна записати й у такій формі: _. (2)

У рамках введених понять сформулюємо задачу синтезу алгоритмів пошуку точки екстремуму унімодальної функції в умовах дії завад віртуальних послідовностей: для функцій класу _ однієї змінної точка екстремуму _ зміщується в процесі пошуку під дією віртуальної послідовності в напрямку _ або _; пошук _ здійснюється алгоритмом, що складається з _ кроків і формує одночасно _ точок експерименту. Множиною значень експерименту, що вільні від помилок, є множина _, де _ – номер точки експерименту, для якої _. Під дією завад замість _ будемо спостерігати величини _ , для яких _ .

Завдання полягає в тім, щоб у цих умовах для будь-яких _, _, _ – заданих параметрів віртуальної послідовності – синтезувати алгоритм пошуку точки екстремуму унімодальної функції _ (визначити стратегію пошуку і розв’язуючу функцію), для якого має місце мінімаксна стратегія (1), (2).

Для синтезу алгоритмів функціонування КА з псевдовипадковими переходами необхідно розробити правила виділення нового інтервалу невизначеності відносно точки екстремуму унімодальної функції та правила розподілу точок в ізнов виділеному інтервалі невизначеності.

Для того щоб сформулювати правила виділення нового інтервалу невизначеності (співвідношення для розв'язуючої функції), проаналізовані всі можливі наслідки (наслідок, російський еквівалент – исход), що виникають після здійснення експерименту на першому, другому і т.д. кроках. При аналізі наслідків з'ясовується: був або не був прояв віртуальної послідовності. Так для наслідку _ є характерним те, що регулярне збурювання хоча і було, але воно не внесло змін у значення експерименту (регулярне збурювання зміщує _ в напрямку _ ). З цієї причини відносно _ виділяється новий інтервал невизначеності_. Для наслідку _, _ однозначно не можна затверджувати, що на першому кроці було або не було регулярного зміщення. Тому застосовуємо принцип “перетинань” і формуємо інтервал невизначеності відносно_ :

_, де _

Величину, яка є зворотною довжині інтервалу невизначеності, що отриманий на _-м кроці, позначимо через _ . Тоді, якщо припустити, що оптимальний алгоритм існує, то на відрізку _ діє оптимальний _ кроковий алгоритм. Цей алгоритм розіб'є відрізок _ на _ рівних частин. Для наслідку _ необхідно виконати другий крок. Нехай у напіввідчиненому інтервалі _ обрано деяким чином точки експерименту_ . Тоді може виникнути один з наслідків: _ ;_. Для наслідку _ новим напіввідчиненим інтервалом невизначеності відносно _ буде _ . Для наслідку _ застосовується принцип “перетинання”, на підставі якого встановлюємо: _, де _.

Подібним чином формуються нові інтервали невизначеності на наступних кроках алгоритму.

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

Показано, що на розміщення точок експерименту істотний вплив має амплітуда регулярного збурювання. Так, якщо _ і

_, (3)

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

У тих випадках, коли співвідношення (3) не виконується, принцип “повторних порівнянь” застосовується не з першого кроку алгоритму. Крок, на якому застосовується принцип “повторних порівнянь”, визначається наступними твердженнями.

Якщо_: S1. _ – непарне число,_– парне число, _і виконуються співвідношення:

_; _, (4)

то на _-му кроці алгоритму застосовується оптимістична стратегія пошуку.

S2. _ – непарне число,_– парне число, _, _ і виконуються співвідношення:

_; _, (5)

то на _-му кроці алгоритму застосовується змішана стратегія:_.

S3. _ – непарні числа, _ і виконуються умова:

_;_, (6)

то для _ застосовується оптимістична стратегію, якщо ж _ , то застосовується змішана стратегію:

_; _.

S4. _ – парне число,_– непарне число,_ і при цьому виконуються співвідношення (4), то на _-му кроці застосовується оптимістична стратегія.

S5. _– парне число,_– непарне число, _і при цьому мають місце співвідношення (5), то на _-му кроці алгоритму застосовується змішана стратегія: _.

S6. _– парні числа, _, і при цьому виконуються співвідношення (6), то для _ – застосовується оптимістична стратегія, для _ – змішана стратегія: _.

Співвідношення (4) – (6) дозволяють синтезувати завадостійкий алгоритм пошуку для будь-яких значень параметрів віртуальної послідовності за такою схемою.

1. Якщо співвідношення (3) виконується, то алгоритм будується за схемою _- алгоритму, у противному разі перейти на п. 2.

2. Побудувати _-кроковий алгоритм пошуку в умовах дії несиметричної регулярної послідовності, _присвоїти значення, рівне одиниці.

3. Сформувати можливий наслідок. Якщо всі наслідки сформовані, то перейти до п. 8, у противному випадку перейти до п. 4.

4. Використовуючи співвідношення (4–6), розподілити точки експерименту, потім на підставі правил прийняти рішення щодо виділення нового інтервалу невизначеності відносно _.

5. Визначити _ і якщо _, перейти до п.6. У противному разі перейти до п.7.

6. Сформувати можливий наслідок на _-му кроці. Якщо всі наслідки сформовані – перейти до п.7, у противному разі – перейти до п.4.

7. Покласти _ і якщо _ , перейти до п.3. У противному разі перейти до п.6.

8. Алгоритм побудовано.

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

В цьому ж розділі побудовані розв’язуючі функції та стратегії пошуку для інших співвідношень між параметрами віртуальної послідовності l і H (l<H; l>H). Наведено приклади рішення задач синтезу завадостійких до регулярних симетричних віртуальних послідовностей алгоритмів пошуку точки екстремуму унімодальної функції. Отримано значення цільових функцій для описаних прикладів. Це дало змогу створити алгоритмічні основи синтезу КА з псевдовипадковими переходами на базі завадостійких до регулярних симетричних та несиметричних віртуальних послідовностей алгоритму пошуку.

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

При виконанні першого кроку алгоритму можуть виникнути наслідки:

_, _.

Для наслідка а) характерно те, що _. Для наслідка _ застосовують змішану стратегію, для якої характерно таке розміщення точок експерименту: _ розміщують в інтервалі _ , а дві інші – таким чином:_,_ . При цьому: можуть виникнути наслідки: _;_; _;_ .

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

_; _. (8)

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

Шляхом аналізу можливих наслідків, що виникають у процесі пошуку, показано, що напіввідчинений інтервал невизначеності _ буде розбитий на _, а первинний інтервал на _ рівні частини, де _ визначається з таких рівностей:

_;

_

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

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

У четвертому розділі для конкретних параметрів віртуальної послідовності розроблені алгоритми функціонування КА з псевдовипадковими переходами, задані орієнтованим графом; структурні схеми кодуючого пристрою; методи захисту інформації на основі розроблених КА. Наведена оцінка невизначеності, породжувана КА із псевдовипадковими переходами і результати впровадження.

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

_

Рис. 3. Фрагмент графу логічної схеми кінцевого автомату для випадку

_

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

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

_

Рис. 4. Структурна схема кодуючого пристрою

Кодуючий пристрій містить регістр даних, суматор, постійний запам'ятовуючий пристрій – ПЗП, пристрій порівняння, КА, передавач.

Значення унімодальної функції записуються в ПЗП. При цьому записується тільки стандартна функція (функція, що має екстремум у нульовій точці); значення точок екстремуму ототожнюються з адресами ПЗП. Кількість символів вхідного алфавіту дорівнює 64, амплітуда віртуальної послідовності – не більш ніж 64, у цьому випадку використано ПЗП з параметрами 512*8. Тоді вихідному інтервалові невизначеності _ будуть відповідати адреси ЗУ, починаючи з 257 і кінчаючи 384. У двох сусідніх ячейках ЗУ, починаючи з 257, 258 і т.д. буде записане те ж саме значення унімодальної функції. Цей прийом дозволяє виключити додаткові стани КА.

Нехай координата точки екстремуму дорівнює _ . Тоді для одержання унімодальної функції, координата точки екстремуму якої дорівнює _ , необхідно інформацію з ПЗУ перезаписати в ОЗУ за таким правилом: інформацію з ячейки ПЗУ _ записати в ячейку ОЗУ за адресою _. Оскільки аргумент унімодальної функції є адитивна суміш координати точки екстремуму й амплітуди імпульсу віртуальної завади, то запис із ПЗУ в ОЗУ здійснюється декілька в іншій формі: інформація з ячейки ПЗУ А1 записується в ячейку ОЗУ за адресою _, де _– амплітуда імпульсу віртуальної перешкоди.

Після того, як функція сформована, виконують послідовне зчитування інформації з ячейок:

_

Потім, як уже відомо, пристроєм порівняння формується один із сигналів "0", "1", "2", що надходять на входи КА і передавач. Кінцевий автомат переходить в інший стан. У подальшому кодуючий пристрій функціонує аналогічним образом. Декодувальний пристрій містить приймач і кінцевий автомат, які з'єднані послідовно.

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

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

Таблиця 2

Ряди цілих позитивних чисел

_ |

12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1

_ | 76 | 47 | 29 | 18 | 11 | 7 | 4 | 3 | 2 | 1 | 1

_ | 41 | 28 | 19 | 13 | 9 | 6 | 4 | 3 | 2 | 1 | 1 | 1

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

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

У цьому ж розділі дана оцінка ступеня захищеності інформації при її передачі. Показано, що якщо по дискретному каналі передається 64 цифри восьмеричної системи, то невизначеність (кількість варіантів перебору) складе _.

Результати роботи з розробки структури датчиків віртуальних послідовностей; алгоритмічні основи синтезу завадостійких до нерегулярних і регулярних, симетричних і несиметричних послідовностей; алгоритми пошуку точки екстремуму унімодальної функції, структура КА з псевдовипадковими переходами використовуються у навчальному процесі і розглядаються як окремі розділи лекційного курсу "КА с псевдослучайными переходами" для студентів спеціальності "Комп’ютерні системи та мережі", що читається студентам ХНУРЄ.

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

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

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

ВИСНОВКИ

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

Основні наукові і практичні результати дисертаційної роботи такі.

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

2. Створено алгоритмічні основи синтезу КА з псевдовипадковими переходами на базі завадостійких до регулярних несиметричних і симетричних віртуальних послідовностей алгоритмів одномірного пошуку точки екстремуму унімодальної функції. Одержано співвідношення для розв'язуючої функції (правила виділення нового інтервалу невизначеності) і стратегії пошуку (розподіл точок експерименту в ізнов виділеному інтервалі невизначеності) завадостійких алгоритмів пошуку точки екстремуму унімодальної функції та схеми їх побудови. Це дало змогу організувати псевдовипадковий вибір підстановок символів вхідного алфавіту, які являють собою нерівнозначні префіксні коди [7].

3. Створено алгоритмічні основи синтезу КА з псевдовипадковими переходами на базі завадостійких до нерегулярних (тривалість збурювання є випадкова величина) несиметричних і симетричних віртуальних послідовностей алгоритмів одномірного пошуку точки екстремуму унімодальної функції. Одержано співвідношення для розв'язуючої функції і стратегії пошуку завадостійких до несиметричних і симетричних нерегулярних віртуальних послідовностей алгоритмів пошуку точки екстремуму унімодальної функції, що описують функціонування кінцевих автоматів із псевдовипадковими переходами, і які є генераторами псевдовипадкових підстановок символів вхідного алфавіту [3, 6].

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

5. Розроблено структурні схеми нових датчиків віртуальних послідовностей для організації псевдовипадкових переходів КА. Створено структурні схеми КА, кодуючих і декодуючих пристроїв для каналу передачі інформації на основі завадостійких до віртуальних послідовностей алгоритмів пошуку [1], [2].

6. Проведено оцінку ступеня захищеності інформації при її передачі. При цьому ураховувалися алгоритм функціонування КА, конкретна унімодальна функція однієї змінної, тип віртуальної послідовності та її параметри. Показано, що якщо по дискретному каналі передається 64 цифри восьмеричної системи, то невизначеність (кількість варіантів перебору) складе _ [5].

7. Розроблено пристрій керування вихідними потужними електронними ключами за рахунок псевдовипадкових імпульсів з заданими параметрами на основі завадостійких алгоритмів, що отримані у дисертаційній роботі. Використання таких пристроїв у автономних джерелах електрозабезпечення газорозподільних станцій, які розроблено у НПФ „Газінжінірінг-сервіс”, дозволяє уникнути імпульсних низькочастотних навантажень на електрогенератор.

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ РОБІТ

ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Алипов Н.В., Алипов И.Н., Булах Е.В., Охапкин А.А., Ребезюк Л.Н. Датчики виртуальных помех, используемые для организации функционирования дискретных автоматов в системах защиты информации / Сб. "Радиотехника". Вып. 107, 1999 . С. 33-99.

2. Алипов И.Н., Булах Е.В., Ребезюк Л.Н. Структура дискретных автоматов с псевдослучайными переходами и методы защиты информации на их основе // Радиоэлектроника и информатика. 1999. № 4, С. 59-60.

3. Алипов Н.В., Булах Е.В. Синтез помехоустойчивых к нерегулярным возмущениям алгоритмов поиска точки экстремума унимодальной функции // Радиоэлектроника и информатика. 1999. № 3, С. 66-68.

4. Булах Е.В. Примеры построения алгоритмов функционирования дискретных автоматов с псевдослучайными переходами // Автоматизированные системы управления и приборы автоматики. 2001. № 115, С. 82-87.

5. Булах Е.В. Методы защиты информации на основе деревообразных автоматов / Зб. наукових праць за матеріалами 3-го міжнародного молодіжного форуму "Радіоелектроніка i молодь у XXI ст.", ч. 2 – Харків: ХТУРЕ, 1999. С. 453-456.

6. Алипов Н.В., Булах Е.В. Алгоритм поиска точки экстремума унимодальной функции при воздействии на нее несимметричных нерегулярных виртуальных последовательностей // Сб. научных трудов по материалам 6-й международной конференции "Теория и техника передачи, приема и обработки информации", – Харьков: ХТУРЭ, 2000. С. 591-592.

7. Алипов Н.В., Булах Е.В. Помехоустойчивые к несимметричным регулярным последовательностям алгоритмы поиска точки экстремума унимодальной функции // Сб. научных трудов по материалам 6-й международной конференции "Теория и техника передачи, приема и обработки информации", – Харьков: ХТУРЭ, 2000. С. 593-595.

АНОТАЦІЯ

Булах Е.В. Кінцеві автомати з псевдовипадковими переходами і методи захисту інформації на їх основі – Рукопис.

Дисертація на здобуття вченого ступеня кандидата технічних наук за фахом 05.13.13 – обчислювальні машини, системи і мережі. – Харківський національний університет радіоелектроніки, Харків, 2004.

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

Результати роботи використано при виконанні держбюджетних НДР по створенню нових методів захисту інформації при її збереженні і передачі (д/б 190232 "Розробка теорії і методів захисту інформації при її передачі і збереженні", д\б 190 (520-7) "Система захисту інформації при її передачі в інтелектуальних середовищах"), а також використовуються в навчальному процесі при виконанні лабораторних робіт і дипломному проектуванні у Харківському національному університеті радіоелектроніки.

Ключові слова: кінцевий автомат, завадостійкий алгоритм пошуку, віртуальна послідовність, довжина пошуку, кількість точок експерименту, розв'язуюча функція, стратегія пошуку, алгоритми придушення віртуальної послідовності, принцип "перетинання", принцип "повторних порівнянь", унімодальна функція, логічний синтез кінцевого автомата.

АННОТАЦИЯ

Булах Е.В. Конечные автоматы с псевдослучайными переходами и методы защиты информации на их основе. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 – вычислительные машины, системы и сети. – Харьковский национальный университет радиоэлектроники, Харьков, 2004.

Диссертация посвящена разработке алгоритмов функционирования конечных автоматов с псевдослучайными переходами из одного состояния в другое, помехоустойчивых к виртуальным последовательностям и осуществляющих одномерный поиск точки экстремума унимодальной функции. Такие конечные автоматы являются генераторами шифра замены (подстановки) для символов входного алфавита. Показано, что для реализации идеи Вернама необходимо разработать основы алгоритмического (логического) синтеза конечных автоматов помехоустойчивых к виртуальным последовательностям, выполнить структурный синтез таких автоматов.

Структура подобного автомата включает следующие совокупности: сумматор, датчик виртуальной последовательности и конечный автомат реализующий помехоустойчивый алгоритм поиска, такие автоматы характеризуются тем, что имеют одно начальное и N конечных состояний (N – количество символов входного алфавита). Переход автомата из начального в одно и тоже конечное состояние осуществляется различными маршрутами. Каждому маршруту соответствует определенная совокупность выходных сигналов конечного автомата, которая является шифром замены. Выбор определенного маршрута зависит в конкретной момент времени от параметров виртуальной последовательности. В конкретный момент времени эти параметры могут быть случайными и неслучайными величинами, поэтому шифры замены формируются псевдослучайным образом и представляют собой префиксные (неравнозначные) коды. Для раскрытия такого шифротекста необходимо знать вид унимодальной функции, помехоустойчивый алгоритм поиска, параметры виртуальной последовательности (максимальная амплитуда импульса, максимальная длительность импульса, минимальный временной интервалом между двумя соседними импульсами). Многообразие алгоритмов функционирования конечных автоматов с псевдослучайными переходами, алгоритмов поиска, виртуальных последовательностей и использование предложенных кодов значительно усложняет процесс вскрытия шифротекста.

В диссертационной работе получены соотношения для решающей функции и стратегии поиска помехоустойчивых к несимметричным и симметричным регулярным виртуальным последовательностям алгоритмов поиска точки экстремума унимодальной функции, на основе которых синтезированы оригинальные алгоритмы поиска.

Получены соотношения для решающей функции и стратегии поиска помехоустойчивых к несимметричным и симметричным нерегулярным виртуальным последовательностям алгоритмов поиска точки экстремума унимодальной функции, которые описывают функционирование конечных автоматов с псевдослучайными переходами из одного состояния в другое, являющихся генераторами псевдослучайных подстановок символов входного алфавита.

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

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

Созданы избыточные представления десятичных чисел, на основе которых синтезированы методы защиты информации от несанкционированного доступа и сбоев в канале передачи информации.

Построены методы защиты информации