Моделі і методи ортогональних дискретних перетворювань Уолша та їх використання в системах відкритого шифрування

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

Черкаський державний технологічний університет

Автореферат

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

Моделі і методи ортогональних дискретних перетворювань Уолша та їх використання в системах відкритого шифрування

Кожухівська О.А.

01.05.02 - математичне моделювання та обчислювальні методи

Черкаси - 2011

Вступ

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

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

У зв'язку з інтенсивним розвитком цифрової обчислювальної техніки увагу дослідників стали привертати повні системи прямокутних ортогональних функцій Уолша, Хаара, Віленкіна-Крестенсона, Віленкіна-Понтрягіна, для яких існують швидкі обчислювальні процедури. Необхідно відмітити, що спектральна обробка у базисах Уолша, Хаара, комплексних прямокутних і інших функцій в найбільшій степені задовольняють сучасній елементній базі і тенденціям її розвитку. Розв'язку вказаних задач присвячені роботи багатьох дослідників. Зокрема, Ахмеда Н., Рао К.Р., Опенгейма А.В., Рабінера Л.Р., Сидельникова В.М., Білецького А.Я. та інших.

Відмічені вище задачі при їх комплексному вирішенні дозволяють розробити високоефективні і швидкодіючі алгоритми розв'язку багатьох науково-технічних задач у режимі реального часу і у векторному режимі для комп'ютерів з архітектурою типу "одна команда, багато даних" (ОКБД).

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційне дослідження виконувалось в рамках науково-дослідної роботи Черкаського державного технологічного університету, в якій автор брала участь: "Моделі локальних підсистем керування лазерним випромінюванням для рішення траєкторних задач на базі таблично-алгоритмічних методів апаратурної реалізації в проблемно-орієнтованих системах", державна реєстрація № 0109U002739.

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

Для досягнення мети у дисертації необхідно розв'язати наступні задачі:

розробити моделі і методи оптимального математичного апарату на базі узагальнених кронекеровських добутків (УКД) матриць для розв'язку задачі відкритого шифрування;

запропонувати використання апарату УКД матриць для розпаралелювання і векторизації матриць Уолша і Фур'є з урахуванням відліків сигналів, характерних для розглянутих в дослідженні задач;

отримати моделі переходу від базису функцій Уолша до базису функцій Фур'є та методу, що його реалізує, для розглянутої задачі;

удосконалити організацію векторних обчислень моделей швидких перетворювань Фур'є і Уолша, що дозволяє проводити аналіз векторних алгоритмів указаних перетворювань за допомогою алгоритмів розщеплення та Джентлмена-Сенде;

модифікувати методи і моделі кодування і декодування інформації для систем відкритого шифрування на базі кодів Ріда-Маллєра в задачі імітозахисту;

дослідити ефективність використання розроблених методів та моделей в системах відкритого шифрування;

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

Об'єктом дослідження дисертаційної роботи є процеси удосконалення систем відкритого шифрування.

Предметом дослідження є моделі та методи ортогональних дискретних перетворювань Фур'є і Уолша та їх використання при шифруванні інформації на базі кодів Ріда-Маллєра для системи відкритого шифрування.

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

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

Автором отримані наукові результати, які полягають у наступному:

розроблені моделі і методи узагальнених кронекеровських добутків матриць і розглянуті їх основні властивості, що дозволило використовувати їх для розпаралелювання і векторизації матриць ОДП і покращити часовий показник обчислення на ЕОМ;

на основі узагальнених кронекеровських добутків матриць удосконалені методи розпаралелювання і векторизації матриць Фур'є і Уолша, що дозволяє використовувати їх для реалізації в реальному масштабі часу, а також у векторному режимі і скорочувати об'єм необхідної пам'яті ЕОМ;

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

удосконалена організація векторних обчислень алгоритмів швидких

перетворювань Фур'є і Уолша, що дозволяє проводити аналіз векторних алгоритмів

указаних перетворювань за допомогою алгоритмів розщеплення та Джентлмена-Сенде;

модифіковані ряд методів кодування і декодування кодів Ріда-Маллєра першого порядку з використанням швидких перетворювань Уолша-Адамара і Уолша-Пелі, що дозволило реалізувати їх в режимі реального часу і у векторному режимі для комп'ютерів з архітектурою команд типу ОКБД на базі моделей оптимізованих ОДП для задачі кодування за Рідом-Маллєром в системі відкритого шифрування.

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

Запропоновані в роботі методи і моделі досліджуваних об'єктів дозволяють:

розробляти алгоритми генерації імітовставки на базі моделей швидких перетворювань Уолша і Фур'є без переставлення початкових даних у вигляді закону двійкової інверсії і оберненого коду Грея;

використовувати методи генерування імітовставки на базі апарату надлишкових кодів, що базуються на ОДП, у реальному масштабі часу і у векторному режимі для комп'ютерів з архітектурою команд типу ОКБД;

застосовувати векторні алгоритми перетворювань Фур'є і Уолша з використанням алгоритмів розщеплення і Джентлмена-Сенде в задачі відкритого шифрування;

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

Результати дисертаційного дослідження використані і впроваджені в Головному управлінні державного казначейства України у Черкаській області, в навчальному процесі під час читання лекцій, проведення практичних занять і лабораторних робіт на кафедрі інформатики та інформаційної безпеки Черкаського державного технологічного університету, у державному підприємстві - НВК "Фотоприлад" (м. Черкаси).

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

У публікаціях, написаних у співавторстві, здобувачеві належать: в роботі [1] постановка задачі моделювання алгоритмів передачі інформації; в роботах [18,19,22,23] - розробка алгоритмів швидких перетворювань кодів Ріда-Маллєра; в роботах [2,3] - постановка задачі моделювання зображень; в роботах [4-6] - сформульована методика розв'язку нелінійних задач з використанням поліномів Чебишова; в роботах [7,15-17,20,21] - методика моделювання задач з використанням ОДП Уолша і Фур'є; в роботі [24] - методика оптимізації систем захисту інформації; в роботі [25] - постановка задачі моделювання одновимірного швидкого перетворювання Фур'є.

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

Апробація результатів роботи. Основні ідеї, принципи, положення і результати досліджень доповідались та обговорювались на наукових конференціях та семінарах: IV і V Всеукраїнських конференціях молодих науковців "Інформаційні технології в освіті, науці і техніці" (ІТОНТ - 2004) і (ІТОНТ - 2006) (Черкаси - 2004 і Черкаси - 2006); Міждержавних науково-методичних конференціях "Проблеми математичного моделювання" (Дніпродзержинськ, 2004) і (Дніпродзержинськ, 2005); Міжнародній науково-практичній конференції "Наука і освіта - 2004" (Дніпропетровськ, 2004); Міжнародній науково-практичній конференції "Науковий потенціал світу - 2004" (Дніпропетровськ, 2004); Міжнародній науково-практичній конференції "Динаміка наукових досліджень - 2004" (Дніпропетровськ, 2004); Международной научно-практической конференции "Системы и средства передачи и обработки информации" (Черкассы, 2005); Міжнародній науково-технічній конференції "Сучасні проблеми мікроелектроніки, радіоелектроніки та приладобудування (СПМРТП - 2006)" (Вінниця, 2006); Міжнародній конференції з автоматичного управління (Автоматика - 2006) (Вінниця, 2006); Першій і Другій Міжнародних науково-практичних конференціях "Методи та засоби кодування, захисту й ущільнення інформації" (Вінниця, 2007 і Вінниця, 2009); Всеукраїнській науковій конференції "Актуальні проблеми аналізу та моделювання складних систем" (Черкаси, 2007).

Публікації. За результатами дисертаційної роботи опубліковано 26 наукових праць, з яких 13 статей у виданнях ВАК України, в яких публікуються основні результати дисертаційних досліджень, 13 тез доповідей на міжнародних конференціях.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків і списку використаних джерел. Загальний обсяг дисертаційної роботи становить 192 сторінки, у тому числі: основний текст викладено на 147 сторінках; 13 таблиць та 28 рисунків; 14 додатків; список використаних джерел складає 162 найменування.

1. Основний зміст роботи

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

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

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

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

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

де індекс означає упорядкування за Уолшем-Качмажом. Дискретизація функцій Уолша-Качмажа приводить до матриць Уолша-Качмажа.

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

Розглянемо алгоритми ШПУА, ШПУП і ШПУК.

Алгоритм ШПУА є математичне представлення у матричному вигляді відомого алгоритму перетворювання Уолша-Адамара типу Кулі-Тьюкі.

Представлення ШПУА. Пряме перетворювання Уолша-Адамара вектор-стовпця можна представити у вигляді:

,

де розмірність матриці, - матриця Уолша-Адамара, яка факторизується так:

,

де

;

,

де кронекеровський добуток матриць.

Представлення ШПУП. Нехай , . Матрицю Уолша-Пелі можна представити:

.

Представлення ШПУК. Нехай , . Матрицю Уолша-Качмажа можна представити:

Розглянемо розпаралелювання швидких алгоритмів ОДП Фур'є і Уолша. Більш детально розпаралелювання алгоритмів ОДП розглянуто в дисертації. Як відомо, процедури перетворювання Фур'є і Уолша дозволяють початковий ряд даних розділити на два: за парними і непарними номерами. Продовжимо цей процес до отримання рядів, які складаються із одного члена. Послідовність обчислення покажемо на прикладі ряду із восьми членів перетворювань Уолша-Адамара. У цьому випадку число ітерацій ; число обчислювальних операцій

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

Таблиця 1

1-а ітерація	2-а ітерація	3-я ітерація

,

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

і можна також вважати, що , tобм. і - рівні приблизно величини. Тоді:

.

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

.

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

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

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

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

Матрицю Уолша-Адамара можна представити у вигляді:

,

де - одинична матриця порядку , символи кронекеровські добутки матриць за рядками і стовпцями відповідно.

Матрицю Уолша-Пелі можна факторизувати так:

.

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

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

;

;

;

,

де - одинична матриця порядку ,

- стандартна матриця Уолша-Адамара другого порядку.

Факторизація матриць Уолша-Пелі. Матриця факторизується так:

,

де

; .

Розглянемо наступний метод факторизації матриць Уолша-Пелі. Матрицю Уолша-Пелі представимо у вигляді:

,

де

; .

Використовуючи властивості УКД матриць, які описані в дисертації, матриці Уолша-Пелі представимо так :

;

.

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

Уведемо поняття косокронекеровського добутку матриць за рядками:

,

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

Представимо матрицю Уолша-Качмажа у наступному вигляді:

,

де

; .

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

,

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

Тепер матрицю Уолша-Качмажа представимо у вигляді:

,

де

; ;.

Факторизація матриць Фур'є. Більшість із відомих алгоритмів ШПУП і ШПФ вимагають переставлень початкових даних. Це переставлення отримало назву двійкової інверсії, оскільки дані записуються у двійковому інверсному порядку. Операція двійкової інверсії вимагає додаткової пам'яті для обчислення (робочий масив такої ж довжини, як і початковий ряд). Переставлення даних шляхом двійкової інверсії складає до 10 % часу обчислення ШПФ і до 12 % часу обчислення ШПУП на ЕОМ при довжині масиву .

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

, ,

де

,

. Степені величин розподіляються так: у першій ітерації матриці Уолша-Пелі степені величин змінюються від до ; у другій ітерації - степені величин приймають значення ; у наступній ітерації - степені величин приймають значення і т.д.; у останній ітерації степені величин дорівнюють нулю.

У першому алгоритмі факторизації матриці Уолша-Пелі величини повинні знаходитися у нижній половині матриць ітерацій. У другому алгоритмі факторизації матриці Уолша-Пелі величини повинні знаходитися у правій частині. Перший алгоритм ШПФ з використанням ШПУП можна представити так:

,

де

.

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

.

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

Другий алгоритм ШПФ із застосуванням другого алгоритму ШПУП має вигляд:

,

де

.

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

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

,

a перетворювання Адамара того ж вектора як

.

Звідси

,

де - матриця Фур'є, а і - матриці прямого і оберненого перетворювань Уолша-Адамара відповідно. Таким чином,

- є матриця переходу від базису функцій Уолша у базис функцій Фур'є. Відмітимо, що вхідна послідовність повинна бути упорядкована за Пелі, тому що у цьому випадку величини вихідної послідовності будуть розташовуватися у «натуральному» порядку.

В третьому розділі розглянуті моделі і методи оптимізації швидких перетворювань Фур'є та Уолша для задачі кодування і декодування інформації за Рідом-Маллєром в системі відкритого шифрування.

Для дослідження структури алгоритмів ОДП Уолша скористаємося кронекеровським і узагальненим кронекеровським добутками матриць, які приведені в розд. 2 дисертації. Нехай , де - натуральне число.

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

;

;

.

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

Алгоритм векторизації ШПУА. Приведемо запропонований у дисертації алгоритм векторизації ШПУА за допомогою перетворювання Джентлмена-Сенде.

Запишемо перетворювання Джентлмена-Сенде:

Застосуємо до послідовностей і ШПУА розмірністю N/2 . У результаті отримаємо масиви і :

Елементи масивів і розташуємо один за одним за формулою:

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

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

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

Розглянемо методи декодування кодів PM-1 з використанням запропонованих у дисертаційній роботі способів генерації усіх елементів послідовностей для матриць Уолша-Адамара і Уолша-Пелі.

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

і дозволяють виправляти велику кількість похибок. Наприклад, коди Адамара довжиною виправляють

похибок і

виявляють.

Розглянемо ряд способів для отримання матриць Уолша.

Сукупність -розрядних чисел можна представити у вигляді квадратної матриці порядку , елементи якої (0 і 1)

,

де - транспонована матриця до .

Для отримання матриць Уолша-Пелі порядку необхідно матрицю перемножити на матрицю , де - інвертована матриця, тобто її рядки розташовані у оберненому порядку по відношенню до матриці .

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

Розглянемо простий спосіб отримання вектор-послідовностей матриць Уолша-Адамара. Нехай ; , тоді , . Позначимо:;;; , де - операція порозрядного додавання за модулем 2 (виключне або). Аналогічно можна отримати вектор-послідовності матриць Уолша-Пелі: ; ; ; . Такого виду представлення матриць Уолша знаходить застосування при декодуванні кодів Ріда-Маллєра.

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

Запропоновані способи отримання вектор-послідовностей матриць Уолша дають виграш у швидкодії і скорочують об'єм необхідної пам'яті ЕОМ.

У четвертому розділі приведено комп'ютерне моделювання системи відкритого шифрування.

З метою проведення комп'ютерного моделювання на базі моделей та методів, які представлені в розділах 2 і 3 дисертаційної роботи, розроблено структуру програмних засобів для первинної обробки сигналів бінарної природи в середовищі MatLab. Структурна блок-схема методів обробки сигналів в системі відкритого шифрування наведена в дисертації.

Апробація розробленого комплексу програм. Застосуємо описані вище алгоритми модифікованого швидкого перетворювання Уолша (МШПУ) до алгоритму декодування кодів PM-1 на основі ШПУ. У цьому випадку алгоритм декодування вимагає

операцій додавання, операцій порівняння і операцій взяття модулю. Асимптотична складність МШПУ визначається виразом

.

Нехай довжина коду дорівнює N= 16. Тоді дані про алгоритми ШПУ, НА і ВШПУП (векторне швидке перетворювання Уолша-Пелі) зведемо в таблицю 2. На рис. 1 наведені отримані графічні залежності згідно таблиці 2.

Із наведеної таблиці 2 і рис. 1 виходить, що виграш у швидкодії алгоритму ВШПУП у порівнянні з алгоритмом ШПУ в 1,5 рази, а в порівнянні з алгоритмом НА в 1,35 рази без суттєвого збільшення витрат пам'яті ЕОМ.

Використовуючи описані в дисертації способи векторизації, можливо збільшити швидкодію декодування кодів PM-1.

Моделювання алгоритму перетворювання Уолша-Пелі для декодування кодів Ріда-Маллєра приведено в дисертаційній роботі.

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

Таблиця 2 Порівняння часу виконання алгоритмів відповідно ШПУ, НА і ВШПУП (мс)

Алгоритми Операції	ШПУ	НА	ВШПУП
Додавання Порівняння Взяття модуля	64 15 16	52 5 30	32 15 16

Рис.1. Графічні залежності часу виконання алгоритму від операції згідно таблиці 2

Основна задача захисту інформації шляхом відкритого шифрування (імітовставки) забезпечується шляхом генерації відрізка інформації фіксованої довжини (від 1 до 32 біт у відповідності з: ДСТУ ГОСТ 28147: 2009 - Приклади обчислення імітовставки; ISO - ДСТУ ISO/IES 11770-3:2002 - Протоколи, що ґрунтуються на асиметричних криптографічних перетворюваннях). Даний відрізок отримуємо з відкритих даних (повідомлення) та ключа шифру, який додається до зашифрованих даних для забезпечення механізму імітозахисту. Його довжину приймаємо рівною 2 бітам.

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

фур'є алгоритм імітовставка векторний

Висновки та основні результати роботи

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

В цій області отримані наступні результати:

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

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

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

4. Запропоновані рекурентні алгоритми представлень перетворювань Уолша трьох видів (згідно упорядкування) і показана можливість використання алгоритмів перетворювань Уолша у векторному режимі для комп'ютерів з архітектурою команд ОКБД («одна команда, багато даних»). Досліджена організація векторних обчислень перетворювань Уолша і Фур'є, що дозволяє проводити аналіз векторних алгоритмів указаних перетворювань за допомогою алгоритмів розщеплення і Джентлмена-Сенде.

5. Розроблені методи кодування і декодування кодів РМ-1 з використанням швидких перетворювань Уолша-Адамара і Уолша-Пелі для реалізації їх у режимі реального часу і у векторному режимі з архітектурою команд типу ОКБД. Проведений порівняльний аналіз декодування кодів РМ-1 за допомогою векторних алгоритмів указаних вище перетворювань і інших відомих алгоритмів. Запропоновані методи декодування кодів РМ-1 способом генерації усіх елементів послідовностей для матриць Уолша-Адамара і Уолша-Пелі, які зручні для використання в системах відкритого шифрування.

6. Проведено комп'ютерне моделювання оптимізованих швидких перетворювань Фур'є та Уолша з метою застосування указаних ортогональних дискретних перетворювань для задачі кодування за Рідом-Маллєром в системі відкритого шифрування.

7. Отримані графічні залежності, які відображають переваги запропонованих у дисертаційній роботі перетворювань Уолша-Адамара, Уолша-Пелі і Уолша-Качмажа з метою застосування указаних ортогональних дискретних перетворювань для задачі кодування за Рідом-Маллєром в системі відкритого шифрування. Із аналізу наведених графічних залежностей слідує, що виграш у швидкодії алгоритму векторного швидкого перетворювання Уолша-Пелі (ВШПУП) у порівнянні з алгоритмом ШПУ в 1,5 рази, а в порівнянні з алгоритмом НА в 1,35 рази без суттєвого збільшення витрат пам'яті ЕОМ. Розроблені методи представляють практичний інтерес для спеціалістів, які займаються цифровою обробкою інформації та криптографічними перетвореннями.

Список опублікованих наукових праць за темою дисертації

1.Кожухівська О.А. Моделювання алгоритмів передачі інформації / О.А. Кожухівська, А.Д. Кожухівський // Вісник ЧДТУ. №4.- Черкаси: 2003. С. 53-55.

2. Кожухівський А.Д. Математичне моделювання зображень / А.Д. Кожухівський, О.А. Кожухівська, П.В. Дяченко//Вісник ЧДТУ. №1. Черкаси, 2004. С. 16-20.

3. Кожухівський А.Д. Алгоритми класичних і зсунених ортогональних поліномів Чебишова / А.Д. Кожухівський, О.А. Кожухівська, П.В. Дяченко // Вісник ЧДТУ. №2. Черкаси, 2004. С.111-114.

4. Кожухівський А.Д. Моделювання алгоритмів розв'язку нелінійних задач з використанням поліномів Чебишова / А.Д. Кожухівський, О.А. Кожухівська // Вісник ЧДТУ. №3. Черкаси, 2004. С.27-31.

5.Кожухівський А.Д. Математичне моделювання кодування зображень / А.Д. Кожухівський,О.А. Кожухівська // Вісник ЧДТУ. №4. Черкаси, 2004. С.31-35.

6.Кожухівський А.Д. Моделювання систем функцій в узагальнених дискретних базисах /А.Д. Кожухівський, О.А. Кожухівська // Вісник ЧДТУ. №1. Черкаси, 2005 . С.33-37.

7.Кожухівський А.Д. Математичне моделювання сигналів у базисі Фур'є / А.Д. Кожухівський, О.А. Кожухівська // Вісник ЧДТУ. №2. Черкаси, 2005. С.85-89.

8.Кожухівський А.Д. Математичне моделювання дискретного перетворювання Фур'є /А.Д. Кожухівський, О.А. Кожухівська // Вісник ЧДТУ.-№4. Черкаси, 2005 . С.39-45.

9.Кожухівський А.Д. Моделювання зображень / А.Д.Кожухівський, О.А. Кожухівська, П.В. Дяченко // Вісник Черкаського національного університету: Серія "Прикладна математика". Вип. 83. Черкаси, 2006. С. 67-71.

10.Лега Ю.Г. Математичне моделювання одновимірного швидкого перетворювання Фур'є / Ю.Г.Лега, А.Д. Кожухівський, О.А. Кожухівська // Вісник ЧДТУ, №1. Черкаси, 2006. С. 51-55.

11.Кожухівський А.Д. Математичне моделювання функцій Уолша / А.Д. Кожухівський, О.А. Кожухівська // Вісник ЧДТУ. №2. Черкаси, 2006. С.11-14.

12.Кожухівська О.А. Розпаралелювання алгоритмів швидких перетворювань кодів Ріда-Маллєра / О.А. Кожухівська, А.Д. Кожухівський // Праці Луганського відділення МАІ, №1(14). Луганськ, 2007. С. 29-32.

13.Кожухівська О.А. Застосування матриць Уолша для декодування кодів Ріда-Маллєра / О.А.Кожухівська // Міжвузівський збірник "НАУКОВІ НОТАТКИ". Луцьк, 2010. Випуск № 27. С. 139-146.

14.Кожухівський А.Д. Моделювання зображень / А.Д. Кожухівський, О.А. Кожухівська, П.В. Дяченко // Матеріали доповідей IV Всеукраїнської конференції молодих науковців "Інформаційні технології в освіті, науці і техніці (ІТОНТ - 2004)". Ч.I. Черкаси, 2004. С. 143-145.

15.Кожухівський А.Д. Алгоритм розв'язку нелінійних задач з використанням

поліномів Чебишова / А.Д. Кожухівський, О.А. Кожухівська // Тези доповідей Міждержавної науково-методичної конференції "Проблеми математичного моделювання". Ч.I. Дніпродзержинськ, 2004. С.23-24.

16.Кожухівська О.А. Алгоритми передачі інформації / О.А.Кожухівська //Матеріали YII Міжнародної науково-практичної конференції "Наука і освіта. 2004"Т.73. Дніпропетровськ, 2004. С.35-37.

17.Кожухівська О.А. Цифрова обробка зображень / О.А. Кожухівська //Матеріали I Міжнародної науково-практичної конференції "Науковий потенціал світу 2004". Т.58. Дніпропетровськ, 2004. С.73-76.

18.Кожухівська О.А. Алгоритми стискання спектральної інформації / О.А. Кожухівська // Матеріали III Міжнародної науково-практичної конференції "Динаміка наукових досліджень 2004".Т.55. Дніпропетровськ, 2004. С. 58-61.

19.Кожухівська О.А. Моделювання алгоритмів функцій Віленкіна-Крестенсона і узагальнених функцій Хаара / О.А. Кожухівська // Тези доповідей Міждержавної науково-практичної конференції "Проблеми математичного моделювання".Дніпродзержинськ, 2005. С. 149-150.

20.Кожухівська О.А. Векторизація перетворювань Фур'є і Уолша / О.А. Кожухівська // Труды IX Международной научно-практической конференции "Системы и средства передачи и обработки информации" (тезисы докладов). Черкассы, 2005. С. 161-163.

21.Кожухівська О.А. Розпаралелювання алгоритмів / О.А.Кожухівська // Матеріали Y Всеукраїнської конференції молодих науковців "Інформаційні технології в освіті, науці і техніці" (ІТОНТ - 2006). Черкаси, 2006. С. 59.

22.Кожухівська О.А.Факторизація матриць Уолша / О.А. Кожухівська // Тези доповідей другої Міжнародної науково- практичної конференції "Методи та засоби кодування, захисту й ущільнення інформації". Вінниця, 2007. С. 37-38.

23.Кожухівська О.А. Моделювання алгоритмів швидких перетворювань Ріда-Маллєра / О.А. Кожухівська, А.Д. Кожухівський // Матеріали II Міжнародної науково-технічної конференції "Сучасні проблеми мікроелектроніки, радіоелектроніки та приладобудування ПМРТП)". Вінниця, 2006. С.21-22.

24.Кожухівська О.А. Алгоритми швидких перетворювань для кодів Ріда- Маллєра / О.А. Кожухівська, А.Д. Кожухівський // Тези доповідей XIII Міжнародної конференції з автоматичного управління (Автоматика-2006). Вінниця,2006. С.448.

25.Кожухівська О.А. Алгоритми швидких перетворювань кодів Ріда-Маллєра / О.А. Кожухівська, А.Д. Кожухівський // Матеріали Всеукраїнської наукової конференції "Актуальні проблеми аналізу та моделювання складних систем". Черкаси, 2007. С.17-18.

26.Кожухівський А.Д. Моделі та методи оптимізації систем засобів захисту інформації / А.Д. Кожухівський, А.В. Сагун, О.А. Кожухівська // Тези доповідей другої Міжнародної науково-практичної конференції "Методи та засоби кодування, захисту й ущільнення інформації". Вінниця, 2009. С. 72-73.

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