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

 

ЗМІСТ


ПЕРЕЛІК СКОРОЧЕНЬ

ВСТУП

. ДОСЛІДЖЕННЯ ОСНОВНИХ ВІДМІННОСТЕЙ ФУНКЦІОНУВАННЯ СПЕЦПРОЦЕСОРІВ ОБРОБКИ КРИПТОГРАФІЧНОЇ ІНФОРМАЦІЇ

.1 Дослідження сучасних та перспективних задач криптоперетворень

.2 Сутність процедур шифрування і розшифрування СОКІ

.3 Аналіз основних операцій СОКІ

.4 Обґрунтування вимог до алгоритмів шифрування, що реалізуються СОКІ

. ФОРМУЛЮВАННЯ ПРИНЦИПІВ ОБРОБКИ ІНФОРМАЦІЇ У МСЧ

.1 Синтез структур СОКІ у МСЧ

.2 Дослідження методів реалізації арифметичних операцій у МСЧ

.3 Аналіз впливу основних властивостей МСЧ та принципи функціонування СОКІ

. СИНТЕЗ СПЕЦПРОЦЕСОРА ОБРОБКИ КРИПТОГРАФІЧНОЇ ІНФОРМАЦІЇ У МОДУЛЯРНІЙ СИСТЕМІ ЧИСЛЕННЯ

.1 Принципи технічної реалізації арифметичних операцій у МСЧ

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

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

. ДОСЛІДЖЕННЯ МАТЕМАТИЧНОЇ МОДЕЛІ НАДІЙНОСТІ СПЕЦПРОЦЕСОРА ОБРОБКИ КРИПТОГРАФІЧНОЇ ІНФОРМАЦІЇ У МОДУЛЯРНІЙ СИСТЕМІ ЧИСЛЕННЯ

.1 Вихідні дані, що необхідно для синтезу СОКІ у МСЧ

.2 Математична модель надійності СОКІ у МСЧ

.3 Аналіз продуктивності та надійності СОКІ у МСЧ

. МЕТОДИЧНИЙ РОЗДІЛ

ВИСНОВКИ

ПЕРЕЛІК ПОСИЛАНЬ


ПЕРЕЛІК СКОРОЧЕНЬ


ЕОМ - електронно-обчислювальна машина

КА - криптографічний аналіз

КЗІ - криптографічний захист інформації

КПІ - криптографічне перетворення інформації

КС - криптографічна система

КТМ - код табличного множення

НСД - найменший спільний дільник

ОКЗ - оператор кільцевого зсуву

ОП - обчислювальний пристрій

ОпП - операційний пристрій

ПЗП - постійний запамятовуючий пристрій

ПЗСЧ - позиційно-залишкова система числення

ПКЗ - принцип кільцевого зсуву

ПОКЗ - показник оператора кільцевого зсуву

ПСЧ - позиційна система числення

СЕОМ - спеціалізована електронно-обчислювальна машина

СЗК - система залишкових класів

СОП - спеціалізований обчислювальний пристрій

ССН - структурна схема надійності

СЧ - система числення

УОКЗ - узагальнений оператор кільцевого зсуву


ВСТУП


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

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

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


1. ДОСЛІДЖЕННЯ ОСНОВНИХ ВІДМІННОСТЕЙ ФУНКЦІОНУВАННЯ СПЕЦПРОЦЕСОРІВ ОБРОБКИ КРИПТОГРАФІЧНОЇ ІНФОРМАЦІЇ


1.1 Дослідження сучасних та перспективних задач криптоперетворень


Радикальне вирішення проблем захисту інформації, циркулюючої у високопродуктивних автоматизованих системах, може бути отримане на базі використання криптографічних методів. При цьому важливим є вживання швидкісних алгоритмів шифрування, які не призводять до зниження продуктивності комп'ютерних і телекомунікаційних систем. Криптографічні перетворення даних є гнучким і ефективним засобом забезпечення їх конфіденційності, цілісності і достовірності. Використання методів криптографії в сукупності з необхідними технічними і організаційними заходами може забезпечити захист від широкого спектру потенційних погроз. Потреби сучасної практичної інформатики привели до виникнення нетрадиційних завдань захисту електронних даних, однією з яких є аутентифікація електронної інформації в умовах, коли ті, що обмінюються цією інформацією сторони не довіряють один одному. Ця проблема пов'язана із створенням систем електронного цифрового підпису. Теоретичною базою для вирішення цієї проблеми стало відкриття в середині 1970-х років американськими дослідниками У. Діффі и М. Е. Хеллманом двохключовій криптографії [1-5], яке з'явилося блискучим досягненням багатовікового еволюційного розвитку криптографії. Революційні ідеї двохключової криптографії привели до різкого зростання числа відкритих досліджень в цій області, показали нові дороги вдосконалення криптографії, її далеко не вичерпані можливості і унікальне значення в сучасних умовах бурхливого розвитку електронних інформаційних технологій.

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

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

Перевірки ЕЦП за допомогою відкритого ключа дозволяє з високою мірою гарантії упевнитися в тому, що отримане повідомлення було складене власником секретного ключа. Загальнодоступний відкритий ключ формується на основі секретного ключа або обоє виробляються одночасно по спеціальних процедурах, причому визначення секретного ключа по відкритому ключу є обчислювально складним математичним завданням. Під обчислювально складними (важко вирішуваними) завданнями розуміються завдання, що свідомо мають рішення, але виконання надзвичайно великого числа операцій обчислювача, що вимагають для його знаходження (ЕОМ або іншого обчислювального пристрою). Це число має бути таким великим, що використання всіх обчислювальних пристроїв, які можуть бути залучені в єдиний обчислювальний процес, не дозволить знайти рішення з істотною вірогідністю (наприклад, вірогідністю 0,001) за осяйний час (десятиліття, століття, тисячоліття і т. д.). Середнє число операцій, які необхідно виконати для того, щоб знайти рішення за допомогою кращого алгоритму, береться за кількісну міру складності важко вирішуваного завдання. Проблема оцінки складності полягає в її залежності від алгоритму пошуку рішення. Для різних алгоритмів в загальному випадку виходять різні значення складності. Для конкретного важко вирішуваного завдання нелегко довести, що знайдений алгоритм з мінімальною трудомісткістю (тобто кращий алгоритм). Вживання двохключових шифрів засноване на припущенні про існування важко вирішуваних завдань, тобто таких завдань, для яких відсутнє рішення з порівняно низькою трудомісткістю. На базі двохключових криптографічних алгоритмів запропоновані системи таємного електронного голосування, які використовують механізм сліпого підпису, тобто можливості підписати повідомлення без ознайомлення з його вмістом. Різні способи таємного електронного голосування мають великі перспективи для вдосконалення політичної системи управління сучасним суспільством з розвиненою інформаційною інфраструктурою. Протокол сліпого підпису дозволяє побудувати різного роду системи електронних грошей. Відмінність електронних грошей від перерахувань грошових коштів з використанням ЕЦП полягає в тому, що вони забезпечують таємницю покупки, здійсненої між покупцем і продавцем. Суспільний інтерес представляють також системи електронного жеребкування, варіантом якого є гра в покер по телефону. У ширшому плані можуть бути створені електронні гральні будинки, які гарантуватимуть гравцям захист від обману на набагато вищому рівні, ніж це робиться в звичайних гральних будинках.


1.2 Сутність процедур шифрування і розшифрування СОКІ


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

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

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

Перша проблема відома, останні ж дві є відносно новими, і з їх рішенням пов'язаний ряд перспективних напрямів теоретичній і практичній криптографії. Проте, традиційне криптографічне завдання забезпечення секретності інформації не втратило своєї гостроти і в даний час. Це зв'язано, головним чином, з тим; що в епоху масового вживання комп'ютерних технологій завдання захисту електронної інформації набуло характеру широкомасштабної проблеми. При цьому до алгоритмів шифрування пред'являються жорсткі технологічні вимоги, які продиктовані їх використанням в різних електронних пристроях (телекомунікаційних системах, ЕОМ, комп'ютерних мережах, інтелектуальних електронних картках і ін.). Характерним для технологічних вживань криптографічних засобів є зростання вимог до шифрів одночасно по стійкості, швидкості і по простоті реалізації. Посилювання вимог по стійкості обумовлене тим, що різностороннє використання криптографії пов'язане з ширшими можливостями для того, що атакує слідувати особливостям конкретних умов, в яких функціонує криптосистема (наприклад, є можливості: перша - здійснити зовнішню дію на пристрій шифрування з метою викликати випадкові апаратні збої, друга - виконати вимір споживаної потужності, третя - визначити час обчислень і т. п.). Збільшені вимоги за швидкістю пов'язані з необхідністю збереження високої продуктивності автоматизованих систем після вбудовування в них механізмів захисту. Простота апаратної реалізації необхідна для зниження вартості засобів шифрування, що сприятиме їх масовому вживанню і ширшим можливостям вбудовування в портативну апаратуру. Через специфіку представлення інформації в цифрових пристроях найбільший інтерес представляють блокові шифри, які можуть, наприклад, забезпечити довільний доступ до даних на зашифрованих магнітних носіях.

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

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

Проведення конкурсів на розробку нових алгоритмів шифрування в США (конкурс AES), Європі (конкурс NESSIE) і Японії є проявом визнання технологічної ролі шифрування. Технологічні вживання настільки багатообразні, що розробка нових спеціалізованих алгоритмів шифрування, мабуть, залишатиметься актуальною ще довгий час. Значний інтерес сучасної прикладної криптографії лежить в області пошуку нових криптографічних примітивів для побудови блокових шифрів, перспективних для технологічних вживань і забезпечуючих: високу швидкість; високу стійкість; низьку складність реалізації.

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

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

У програмних і програмно-апаратних шифрах підстановки реалізуються у вигляді таблиць підстановок, що зберігаються в пам'яті ЕОМ. У цьому варіанті легко реалізуються підстановки над двійковими векторами завдовжки до 13 біт (необхідний об'єм пам'яті складає близько 10 Кбайт). Не дивлячись на великий об'єм оперативної пам'яті сучасних ЕОМ, реалізація операцій підстановок над двійковими векторами завдовжки більше 16 біт представляється проблематичною. У апаратних шифрах підстановки реалізуються у вигляді комбінаційних електронних схем. Підстановки загального вигляду над двійковими векторами довжиною більше 13 біт мають високу складність реалізації.

Принципово можуть бути знайдені найкращі по тих або інших криптографічних критеріях підстановки. В разі підстановок малого розміру (наприклад 6x4) встановлена безліч ефективних підстановок. Проте для підстановок розміру 8x8 і більш вибір оптимальних підстановок є проблематичним. У зв'язку з цим вибір підстановок великого розміру у ряді шифрів здійснюється через деякі відомі операції, що володіють певними властивостями. Характерним прикладом є шифр SAFER, в якому підстановки визначені через операцію піднесення до дискретного ступеня і операцію дискретного логарифмування в полі вирахувань по модулю 257. Зважаючи на наявні проблеми при розробці швидкісних блокових шифрів на базі підстановок були запропоновані альтернативні рішення. Одне з таких рішень представлене шифром RC5, в якому єдиною нелінійною операцією є операція обертання (циклічного зрушення), залежна від перетворюваних даних, яка легко реалізується на сучасних масових процесорах. Не дивлячись на крайню простоту побудови, шифр RC5 виявився вельми стійким до лінійного і диференціального криптоаналізу. Теоретичні дослідження показали, що залежність вибору модифікацій операції обертання від перетворюваних даних є ефективним засобом протидії цим двом найважливішим типам атак. Завдяки своїй ефективності циклічне зрушення, залежне від перетворюваних даних, знайшло вживання в нових шифрах - RC6 і MARS.

Фіксована операція циклічного зрушення як окремий випадок операції перестановки є лінійною операцією, то завдання її залежності від перетворюваних даних наводить до побудови нової нелінійної операції з хорошими криптографічними властивостями. Мабуть, окрім операції циклічного зрушення, залежної від перетворюваних даних, існують і інші види керованих операцій. Важливими характеристиками останніх є їх тип і кількість різних варіантів, з яких здійснюється вибір поточної модифікації, використовуваної для перетворення деякого підблоку даних. Другий параметр визначає, скільки додаткових бітів даних можуть бути задіяні при виконанні керованої операції над поточним перетворюваним бітовим підблоком даних. В разі керованої операції циклічного зрушення є n модифікацій. Не дивлячись на настільки мале число модифікацій, дана керована операція виявилася ефективним криптографічним примітивом. Можна чекати, що вельми ефективними виявляться операції з істотно великим числом модифікацій, наприклад рівним від 2» до 23» і більш. Такою керованою операцією є операція перестановки бітів, залежна від перетворюваних даних, яка є узагальненням операції керованого циклічного зрушення [6-10].

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

Традиційні табличні підстановки, а також арифметичні та інші операції, які спочатку використовуються для вирішення інших завдань, не є орієнтованими на криптографічне вживання. З криптографічної точки зору останні містять в собі як позитивні (наприклад, операція порозрядного підсумовування по модулю два проста для реалізації і володіє високою швидкодією), так і негативні (наприклад, лінійність) властивості. Для криптографічного вживання доцільно розробити операції, що оптимізовані в криптографічному відношенні і володіють спеціальними властивостями, які необхідні для здобуття високої стійкості алгоритмів шифрування. До прообразу таких операцій можна віднести операцію циклічного зрушення, залежну від перетворюваних даних, яка була використана як базовий криптографічний примітив в шифрах RC5 [11-12], RC6 і MARS [13-16]. Завдання вибору поточній модифікації такої операції залежно від перетворюваних даних визначає її нелінійні властивості. Не дивлячись на те, що реалізується вибір всього з n (n - довжина двійкового вектора, над яким виконується операція циклічного зрушення) різних модифікацій, даний криптографічний примітив виявився вельми ефективним. Його достоїнства полягають в легкості програмної реалізації, нелінійності і збільшенні ефективного розміру входу до log2 n біт (це кількість бітів даних, задаючих вибір поточної модифікації, тобто бітів, що управляють).

1.3 Аналіз основних операцій СОКІ


Структура і механізм дії операцій керованих перестановок і керованих суматорів є досить наочними, тому дані варіанти керованих операцій сприймаються як самостійний клас криптографічних примітивів. Ще ширшим класом керованих операцій представляються керовані підстановлювальні операції. Проте даний тип операцій не настільки очевидним чином сприймається як самостійний клас операцій. У зв'язку з цим доречно підкреслити, чим керовані підстановлювальні операції відрізняються від операцій підстановок розміру тхп, де т> п. Останні називатимемо керованими підстановками. За своїм змістом і суті керовані підстановлювальні операції є спеціально проектованими операціями криптографічної орієнтації, що виконуються над двома і більш двійковими векторами. Будуються такі операції за певним правилом, що дозволяє розробляти операції для перетворення двійкових векторів довільного розміру. При цьому вони володіють такою структурою, що складність їх апаратної реалізації зростає приблизно по лінійному закону із збільшенням розміру перетворюваних двійкових векторів. Керовані підстановлювальні операції (УПО) характеризуються наступними ознаками: використанням типових булевих функцій, задаючих зв'язок між вхідними і вихідними бітами; можливістю проектування УПО для перетворення двійкових векторів розміру від 32 до 256 біт; невисокою складністю реалізації схемотехніки; високою швидкодією; V можливістю теоретичного обґрунтування вибору УПО певного вигляду для довільного розміру входу. Керовані операції володіють наступними позитивними особливостями: забезпечують можливість участі всіх бітів перетворюваного блоку даних при виконанні єдиної нелінійної операції; вирішують зміну прямої операції на зворотну шляхом інвертування спеціального біта, задаючого режим зашифрування або розшифрування; дозволяють побудувати нових типів криптосхем, що забезпечують зміну режиму перетворення шляхом зміни черговості використання підключів; забезпечують можливість побудови ефективних механізмів внутрішнього розгортання ключа, що дає високу швидкість шифрування в застосуваннях з частою зміною секретних ключів. Не дивлячись на початкову орієнтацію на апаратну реалізацію, проектування ефективних керованих операцій потенційно може привести до істотного стрибка в зростанні швидкості програмних шифрів. Це пов'язано з тим, що деякі типи керованих операцій, наприклад, керовані перестановки, надзвичайно ефективні як криптографічний примітив і володіють дуже низькою вартістю реалізації схемотехніки. Таке співвідношення ефективності і вартості реалізації роблять привабливим для виробників масових процесорів включення нової команди - керованої перестановки - до складу стандартних команд процесора. Можливість забезпечення швидкості програмного шифрування до 800 - 2000 Мбіт/с істотно підвищує конкурентоспроможність таких процесорів при мінімальних витратах схемотехнік. Наприклад, реалізація операційного блоку керованих перестановок (БУП) з 64-бітовим входом для перетворюваних даних і 192-бітовим входом, що управляє, вимагає не більше 1200 транзисторів, а реалізація БУП з 32-бітовим входом для даних і 80-бітовим входом, що управляє, вимагає не більше 1000 транзисторів [17-20].

Стійкість криптосистеми RSA заснована на складності розкладання модуля на два великі прості множники. Якщо завдання такого розкладання удалося б вирішити, то тоді можна було б легко обчислити функцію Ейлера від модуля і потім, використовуючи розширений алгоритм Евкліда, визначити секретний ключ по відкритому. До теперішнього часу не знайдені загальні способи рішення цієї задачі, що практично реалізовуються, при довжині модуля 512 біт і більш. Проте для приватних видів простих чисел р і q складність цього завдання різко знижується, тому в криптосистемі RSA необхідно виконати ряд спеціальних тестів при генерації секретного ключа. Іншою особливістю системи RSA є її мультиплікативність: Е(М\, М2)= E(M[) E(M2)(mod n), що дозволяє порушникові на основі двох підписаних повідомлень сформувати підпис третього повідомлення, яке рівне М' = М\Мг (mod n). Оскільки Мз в переважній більшості випадків не буде яким-небудь осмисленим текстом, та наявність цієї особливості не є недоліком. У системі RSA необхідно враховувати також наступну можливість. Вибравши довільне значення S, можна обчислити значення М'= S, тобто довільне значення можна представити як підпис деякого повідомлення. Такі фіктивні повідомлення, природно, є випадковими. Проте у ряді вживань мають місце випадки, коли потрібно підписувати випадкові повідомлення. У таких випадках використовують наступну схему.

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

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

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

Сучасна система комп'ютерної безпеки, орієнтована на масове вживання, має бути стійкою, технологічно ефективною і ергономічною. Перерахуємо ряд основних властивостей, які роблять систему привабливою для широкого кола користувачів. Комплексність - можливість установки найрізноманітніших режимів захищеної обробки інформації з врахуванням специфічних вимог різних користувачів. Сумісність - система має бути сумісна зі всіма програмами, написаними для даної ОС, і повинна забезпечувати захищений режим роботи комп'ютера в мережі. Переносимість - можливість установки системи на різних типів комп'ютерних систем, включаючи портативні. Зручність в роботі - система має бути проста в експлуатації і не повинна міняти звичну технологію роботи користувачів. Робота в реального часу - процеси перетворення інформації, в т.ч. шифрування, повинні виконуватися з великою швидкістю. Високий рівень захисту інформації. Мінімальна вартість системи [21-25].

Як ідеологічна основа для розробки СЗІ масового призначення пропонується широке використання методів швидкісного шифрування програмними засобами з використанням нових типів блокових шифрів. Для побудови ефективних СЗІ масштабу реального часу можна запропонувати такі принципи: глобальне шифрування - вся інформація на вбудованому магнітному носієві, включаючи завантажувальний сектор, системне і прикладне програмне забезпечення і т. д., має бути перетворена швидкісним програмним шифром; базова ОС має бути збережена в незмінному вигляді, аби забезпечити високу переносимість і сумісність; використання спеціального криптографічного модуля для ініціалізації процесу первинного завантаження і забезпечення повного контролю за процедурою завантаження [26-30].


1.4 Обґрунтування вимог до алгоритмів шифрування, що реалізуються СОКІ


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

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

Алгоритм повинен володіти необхідними характеристиками, що забезпечують невисоку вартість апаратної реалізації (і зручність програмної реалізації).

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

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

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

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

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

Протоколи несиметричної криптографії засновані на тому, що кожен користувач криптосистеми формує для себе пару функціонально зв'язаних ключів, один з яких є його секретом, а другою доступний всім іншим користувачам і називається відкритим ключем даного користувача. У цій парі один з ключів може використовуватися для шифрування, інший для розшифрування даних. За допомогою секретного ключа користувач захищає свою коштовну інформацію. Інші користувачі для зв'язку з ним використовують його відкритий ключ. Тут можливі дві схеми. Якщо користувач А шифрує повідомлення своїм секретним ключем, а користувач В розшифровує це повідомлення за допомогою відкритого ключа користувача А, те цю схему називають цифровим підписом (ЦП) (сформувати підпис може лише один, прочитати можуть всі). У протилежній схемі користувач А шифрує повідомлення відкритим ключем користувача В і направляє його В. Останній розшифровує його своїм секретним ключем. Ніхто окрім нього це зробити не може. Ця схема називається направленим шифруванням. Стійкість приведених схем заснована на тому, що за допомогою відомого відкритого ключа практично неможливо розрахувати секретний ключ. Реалізація ідеї несиметричного шифрування заснована на понятті однобічною взаємно однозначній функції Y = f(X), такий, що при відомому X порівняно просто обчислити Y, проте зворотну функцію X = f (Y) обчислити практично (за прийнятний час) неможливо. Цю властивість називають практичною безповоротністю. Приведене визначення вельми умовно, оскільки складність обчислення зворотної функції може знижуватися за рахунок залучення усе більш досконалих алгоритмів, а час обчислення знижується у міру зростання продуктивності ЕОМ [26-30].

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

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

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

Перш ніж перейти до криптографічних завдань, звернемося до історичних витоків еліптичних кривих, які вивчають більше півтора століть. Досліджуючи завдання про правильний багатокутник, К. Гаус в 1801 році довів, що якщо число n сторін багатокутника представляється у вигляді твору простих чисел Ферма, то такий багатокутник може бути побудований за допомогою циркуля і лінійки. Це еквівалентно вирішенню рівняння х» 1 = 0 в квадратних радикалах. Теорема Гауса надалі послужила основою для теорії алгебри Абеля і Галуа. Удосконалюючи метод Гауса, Абель через 25 років створив теорію еліптичних функцій, а Галуа через 30 років теорію кінцевих полів. Еліптичні криві (ЄС Elliptic curve) часто називають геометричною інтерпретацією еліптичних функцій. Крім того, вони є приватними випадком кривих алгебри [13]. У даній главі ми розглянемо лише деякі приватні питання теорії еліптичних кривих, цікаві з точки зору подальших застосувань. Найбільш важливим аспектом теорії є введення операції складання крапок як основи для побудови Абелевої групи. Крім того, принциповим питанням є знаходження числа вирішень рівняння кривої і числа точок кінцевого порядку (точок кручення). Побачити графік кривої і дати наочну інтерпретацію закону складання крапок удається лише над полем дійсних чисел (з деякими обмовками і над полем раціональних чисел). З цього ми і почнемо коротке введення в теорію ЄС. У збиток математичної строгості ми опускаємо докази практично всіх теорем, і основну увагу приділяємо прикладам. Такий підхід виправдовується прикладною спрямованістю книги.

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


2. ФОРМУЛЮВАННЯ ПРИНЦИПІВ ОБРОБКИ ІНФОРМАЦІЇ У МСЧ


.1 Синтез структур СОКІ у МСЧ


Вивчення всіх особливостей СЗК доцільно після короткого ознайомлення з деякими властивостями порівняння [31].

Розглянемо множину всіх натуральних чисел. Задамо число (модуль) mі=5. При діленні будь-якого натурального числа А на mі = 5 може отриматися наступна сукупність залишків: 0, 1, 2, 3, 4. Всю множину натуральних чисел, враховуючи нуль, можна розбити на пять класів, включаючи в кожен клас числа, які при діленні на mі = 5 дають один і той же залишок {аі}. Класом {аі} по даному модулю mі будемо називати множину всіх натуральних чисел, які можна порівняти тільки з деяким даним числом аі. Вважається, що ці числа можна порівняти між собою по модулю mі = 5.

Приклад 2.1.1

Визначити класи по модулю mі = 5 серед натуральних чисел включаючи нуль.

Очевидно, що таких класів буде пять: 0, 1, 2, 3, 4.


{0, 5, 10, 15, 20,…};

{1, 6, 11, 16, 21,…};

{2, 7, 12, 17, 22,…};

{3, 8, 13, 18, 23,…};

{4, 9, 14, 19, 24,…}.


Приклад 2.1.2

Визначити найменший додатний залишок числа А = 17 по модулю mі=5.

Так як 17 = 5*3 + 2, то аі = 2. Це записується у вигляді порівняння 17 º 2 (mod 5). Тоді загальний алгоритм визначення залишків числа А за модулем mі матиме вигляд:


аі = А - [A/mі]·mі, (2.1)


де [A/mі] - ціла частина числа A/mі, що не перевищує його.

Наприклад, [0,3] = 0, [3,9] = 3, [5,1] = 5, [-3,4] = - 4, тощо.

Приклад 2.1.3

Визначити залишки від ділення числа А = 26 на числа m1 = 2, m2 = 3, m3= 5.


а1 = 26 - [26/2]·2 = 26 - 13·2 = 0; 26 = 0 (mod 2);

а2 = 26 - [26/3]·2 = 26 - 8·3 = 2; 26 = 2 (mod 3);

а3 = 26 - [26/5]·2 = 26 - 5·5 = 1; 26 = 1 (mod 5).


Відмітимо, що числа, які входять в класи 0, 1, 2, 3, 4 (див приклад 2.1.1) називаються залишками по модулю mі = 5. Якщо з кожного класу {aі} взяти по одному залишку, то їх сукупність буде називатися повною системою залишків по модулю пять.

Приклад 2. 1. 4

Визначити всі варіанти повних систем залишків по модулю mі=5.

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


{.., -10, -5, 0, 5, 10,…};

1 {…, -9, -4, 1, 6, 11,…};

2 {…, -8, -3, 2, 7, 12,…};

3 {…, -7, -2, 3, 8, 13,…};

4 {…, -6, -1, 4, 9, 14,…}.

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

, 1, 2, 3, 4 - повна система найменших невідємних залишків;

, 1, 2, 3, 4 - повна система найменших додатних залишків;

, 1, 2, -2, -1 - повна система найменших по абсолютній величині залишків.

Як правило, повну систему залишків визначають з додатних чисел кожного класу {аі} залишків в загальному вигляді повна система залишків по модулю mі завжди містить такі числа: 0, 1, 2, 3,…, mі - 1.

Коротко розглянемо дії над залишками. Арифметично додати два залишки аі (А = аі (mod mi)) і bі (В = bі (mod mi)) із повної системи, значить додати їх по правилам додавання залишків (аі + bі) mod mi, тобто необхідно додати залишки аі та bі по загальним правилам додавання, а від суми (аі + bі) визначити залишок (аі + bі) = сі (mod mi). Таблиця модульного додавання по модулю пять (таблиця 2.1) дає наочне уявлення про алгоритм виконання ції операції. Аналогічно виконуються останні арифметичні операції - віднімання (таблиця 2.2) та множення (таблиця 2.3).


Таблиця 2.1 Модульне додавання по модулю пять.

bіаі01234001234112340223401334012440123

Таблиця 2.2 Модульне віднімання по модулю пять

bіаі01234001234140123234012323401412340

Таблиця 2.3 Модульне множення по модулю пять.

bіаі01234000000101234202413303142404321

Приклад 2.1.5

Визначити суму наступних залишків по модулю пять: 0 + 1, 3 + 3, 3 + + 4, 2 + 3, 4 + 1

У відповідності з даними таблиці 2.1 визначимо:


(0 + 1) = 1 (mod m5);

(3 + 3) = 1 (mod m5);

(3 + 4) = 2 (mod m5);

(2 + 3) = 0 (mod m5);

(4 + 1) = 0 (mod m5).


Приклад 2.1.6

Визначити різницю наступних залишків по модулю пять: 0 - 1, 3 - 3, 4 - 3, 2 - 3, 4 - 1.

У відповідності з таблицею 2.2 визначимо:


(0 - 1) = 4 (mod m5);

(3 - 3) = 0 (mod m5);

(4 - 3) = 1 (mod m5);

(2 - 3) = 4 (mod m5);

(4 - 1) = 3 (mod m5).


Приклад 2.1.7

Визначити добуток залишків по модулю пять: 0·1, 3·3, 4·3, 2·3, 4·1.

У відповідності з таблицею 2.3 визначимо:


(0·1) = 0 (mod m5);

(3·3) = 4 (mod m5);

(4·3) = 2 (mod m5);

(2·3) = 1 (mod m5);

(4·1) = 4 (mod m5).


Введемо поняття непозиційної системи числення в залишкових класах. Для цього задамо набір взаємно попарно простих чисел m1 m2, …, mn. Для представлення числа А в СЗК необхідно визначити набір таких залишків {ai}, і = 1, 2,..., n, щоб виконувалася система наступних порівнянь:


А1 = а1 (mod m1); (2.2)

А2 = а2 (mod m2);

Аn = аn (mod mn).


В діапазоні [0, М), де М = П mі, вибір залишків аі однозначно визначить і = 1 число А. Для числа А / М це визначення неоднозначне. Таким чином, числа А в СЗК являють собою набір залишків:


АСЗК = (а12,…аn). (2.3)


Приклад 2.1.8

СЗК задана основами m1 = 2, m2 = 3, m3 = 5. Необхідно представити число А = 26 в заданій СЗК.

У відповідності з результатами приклада 2.1.3:


АСЗК = (а1, а2, а3) = (0, 2, 1).


Так як в ЕОМ кожна цифра (кожен залишок аі) кодується двохкодовим кодом, то результат приклада 2.1.8 буде мати такий вигляд:


АСЗК = (а1, а2, а3) = (00, 10, 01).


Набір кодових слів для даної СЗК наведено в таблиці 2.4. Зазначимо, що при іншому наборі основ СЗК операнд А буде представлятися іншою сукупність залишків.

Для вирішення задачі переводу операндів із СЗК в ПСЧ існує кілька методів. Розглянемо один з них. Нехай:


АСЗК = (а1, а2, а3, …, аn), (2.4)

тоді: АПСЧ = (S aі·bі) mod M = (a1·b1 + а2·b2 +... + аn·bn) mod M, (2.5)

де Ві = mі·(mі/М),


а значення mі визначається як результат порівняння


mі·(mі/М) = 1 (mod mi).


Таблиця 2.4. Набір кодових слів для СЗК заданої основами 2, 3 і 5.

Число АЧисло А в СЗКmi = 2mi = 3mi = 500000001101001201001031000114001100511000060000017101010801001191001001000100011110001120000101310101114010100151000001600100117110010180000111910110020010000211000012200101023110011240001002510100026010001271000102800101129110100

Приклад 2.1.9

Нехай задана також СЗК, як і в прикладі 2.1.8. Необхідно перевести число А = (0, 2, 1) в ПСЧ.

У відповідності з правилом:


АПСЧ = (S aі·bі) mod M = (0·15 + 2·10 + 1·6) mod 30 = 26,

де b1 = (1, 0, 0) = 15; b2 = (0, 1, 0) = 10; b3 = (0, 0, 1) = 6;

М = 2·3·5 = 30.


Для даної розрядної сітки (заданої СЗК) константи Ві (і = 1, 2, 3,..., n) визначаються раніше і зберігаються в ПЗП ЕОМ.

2.2 Дослідження методів реалізації арифметичних операцій у МСЧ


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

Додавання, віднімання і множення в СЗК здійснюється по дуже простому алгоритму: ці операції модульні і здійснюються незалежно по кожному модулю СЗК в межах розрядної сітки [0, М).

Приклад 2.2.1

Додати два числа А = (0, 01, 000), В = (1, 10, 001) (дивись таблицю 2.4).


m1 = 2m2 = 3m3 = 5А =001000++++В =110001С =100001

де с = (с1, с2, с3) = (1, 00, 001);

с1= (0 + 1) = 1 (mod 2);

с2 = (01 + 10) = 00 (mod 3);

с3 = (000 + 001) = 001 (mod 5).


Рисунок 2.1 Суматор в системі залишкових класів.


Приклад 2.2.2

Для тих же операндів визначити в СЗК різницю чисел А і В.


m1 = 2m2 = 3m3 = 5А =001000----В =110001С =110100

Де с = (с1, с2, с3) = (1, 10, 100);

с1 = (0 - 1) = 1 (mod 2);

с2 = (01 - 10) = 10 (mod 3);

с3 = (000 - 001) = 100 (mod 5).


Приклад 2.2.3

Визначити добуток чисел А і В в СЗК для операндів А = (1, 01, 010), В= = (1, 00,011).


m1 = 2m2 = 3m3 = 5А =001000····В =110001С =110100

Де с = (с1, с2, с3) = (1, 00, 001);

с1 = (1·1) = 1 (mod 2);

с2 = (01·00) = 00 (mod 3);

с3 = (010·011) = 001 (mod 5).


Позначивши узагальнену арифметику операцію через символ ?, не важко реалізувати алгоритм виконання арифметичних операцій в СЗК в загальному вигляді: Нехай А =(а1, …, аn), В = (b1, …, bn), тоді:


С = А?В = [(а1?b1) mod m1, 2?b2) mod m2, …, (аn?bn) mod mn]. (2.6)


2.3 Аналіз впливу основних властивостей МСЧ та принципи функціонування СОКІ


Із вищерозглянутих прикладів випливають основні властивості системи залишкових класів:

) незалежність залишків;

) рівноправність залишків;

) малорозрядність залишків.

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

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

Основна ідея визначення помилкового залишку аі = аі+?аі полягає в тому, що для одержаної в результаті операції послідовності неправильних операндів Аі (і = 1, 2, 3,..., r) у динаміці обчислювального процесу, не перериваючи розвязання задачі, послідовно визначаються умовні альтернативні сукупності W(А) = Wі-1(А) L Wі(А). За визначений час умовна альтернативна сукупність стягається до помилкового залишку (або двох залишків mi і mn). Після цього відомими методами проводиться корекція спотвореного залишку аі. Відмінною рисою даного методу корекції помилок є можливість виправляти помилки без зупинки обчислень, що можливо для ЕОМ, які функціонують в реальному часі.

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

) Рівноправність залишків. Будь-який залишок аі числа Ак у СЗК несе інформацію про все вихідне число, що дає можливість чисто програмними методами замінити спотворений тракт по модулю mi на справний (контрольний) тракт по модулю mi (mi < mi), не перериваючи розвязання задачі. Окрім того, ЕОМ в СЗК з двома контрольними основами зберігає свою працездатність при відмові будь-яких двох обчислювальних трактів. При виникненні третьої чи навіть четвертої відмови, ЕОМ все ще може виконувати програму при деякому зменшенні точності чи швидкості обчислень, тобто ЕОМ в СЗК є винятково живучою, наближаючись в цьому плані до живих організмів. Відзначимо, що дана особливість обумовлює одну із самих чудових властивостей СЗК: та сама ЕОМ може мати різну надійність при розвязанні задач в залежності від вимог, які висуваються до точності, обсягу памяті і швидкодії машини при їх розвязанні, тобто в процесі розвязання різних задач на ЕОМ у СЗК можливе здійснення обмінних операцій між точністю, швидкодією і надійністю.

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

Отже, розглянуті властивості СЗК, при використанні її в СОП, дозволяють значно підвищити ефективність функціонування ЕОМ.


3. СИНТЕЗ СПЕЦПРОЦЕСОРА ОБРОБКИ КРИПТОГРАФІЧНОЇ ІНФОРМАЦІЇ У МОДУЛЯРНІЙ СИСТЕМІ ЧИСЛЕННЯ


.1 Принципи технічної реалізації арифметичних операцій у МСЧ


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

Відомо, що існує чотири принципи реалізації арифметичних операцій в МА: суматорний принцип на базі малорозрядних двійкових суматорів; табличний принцип (ТП) (на основі постійних запамятовуючих пристроїв ПЗП); прямий логічний принцип реалізації арифметичних операцій, заснований на описанні модульних операцій на рівні систем функцій перемикачів, за допомогою яких формуються значення подвійних розрядів результуючих залишків (як елементну базу для технічної реалізації даного принципу доцільно використовувати систолічні і програмовані логічні матриці, а також ПЛІС); принцип кільцевого зсуву (ПКЗ), заснований на використані кільцевих регістрів зсуву.

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

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

Система залишкових класів має цінну властивість незалежності один від одного залишків за прийнятою системою основ. Це відкриває широкі можливості в побудові не тільки нової машинної арифметики, але й принципово нової схемної реалізації ЕОМ, котра, в свою чергу помітно розширює застосування машинної арифметики [3 - 11].

Операційний пристрій ЕОМ в СЗК може бути виконаний або в суматорному варіанті (на базі малорозрядних двійкових суматорів), або в табличному (матричному) варіанті [9]. При побудові ОпП на базі малорозрядних суматорів кожен із розрядів числа обробляється незалежно, але час виконання всієї операції визначається часом необхідним для отримання результату по найбільшій основі СЗК.

Відмітимо основні недоліки суматорного варіанта:

а) складність синтезу двійкових суматорів;

б) значний час перетворення інформації, який визначається максимальною основою СЗК;

в) складність реалізації операції множення;

г) неефективне використання двійкових елементів розрядної сітки компютера, внаслідок надмірності представлення максимальних чисел.

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

Із проведених досліджень [6, 9, 11] очевидно, що питання повязані із використанням табличних методів для реалізації арифметичних операцій (з допомогою ПЗП), доцільно розглядати лише стосовно ЕОМ в СЗК.


3.2 Розробка та дослідження методів реалізації модульних операцій, заснованих на принципі застосування кільцевих регістрів зсуву


Малорозрядність залишків дає нам можливість реалізації арифметичних операцій в СЗК, або на базі малорозрядних двійкових суматорів, або в табличному варіанті. При першому методі реалізації арифметичних операцій проявляється (хоча і в значно меншому ступені) той же недолік, що і в ПСЧ: наявність міжрозрядних звязків у межах даної основи СЗК. У табличному варіанті реалізації арифметичних операцій відсутні міжрозрядні звязки між обробляючими операндами взагалі, однак, для достатньо великої розрядної сітки ЕОМ (для великих за величиною модулів СЗК) різко збільшується кількість обладнання операційних пристроїв. Важливо та актуально розглянути проміжний варіант реалізації арифметичних операцій в СЗК, заснований на застосуванні принципу кільцевого зсуву шляхом використання кільцевих зсуваючих регістрів (КЗР) (або ще називають кільцевих регістрів зсуву (КРЗ)) В [11] сформований принцип реалізації арифметичних операцій в СЗК- принцип кільцевого зсуву (ПКЗ), особливість котрого в тім, що результат арифметичної операції по довільному модулю СЗК, заданої сукупністю , основ, визначається тільки за рахунок послідовно циклічних зсувів заданої цифрової структури.

Дійсно, відома теорема Келі встановлює ізоморфізм між елементами кінцевої абелевої групи і елементами групи перестановок. В цьому випадку матриця складання для довільного модуля СЗК буде задана табл.3.1(для - табл.3.2)


Таблиця 3.1

012…0012…1123…02234…1………………01…

Таблиця 3.2

01234001234112340223401334012440123

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

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

Нехай довільна система алгебри представлена у вигляді


,


де G- непорожня множина;

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

Операція + складання в безлічі класів залишків R, породжених ідеалом J, утворює нове кільце, яке називається кільцем класів залишків R/J. Його можна відрекомендувати у вигляді z/(), де z - безліч цілих чисел 0 ±1 +2...; - основа СЗК. (Якщо основа СЗК - просте число, то z/(), - поле). Дана обставина, як зазначалось, і обумовлює можливість реалізації арифметичної операції складання в СЗК без міжрозрядних перенесень шляхом кільцевого зсуву за допомогою вживання групи КЗР.

На основі сформульованого в [32-35] ПКЗ розроблений метод реалізації арифметичних операцій в класі залишків (системі залишкових класів) - метод двійкового кодування. Суть методу полягає в тому, що вихідна цифрова структура для кожного з модулів (основ) СЗК представляється у вигляді вмісту першого рядка (стовпця) таблиці модульного складання (віднімання) виду

, (3.1)


де- операція конкатенації;

- розрядний двійковий код, відповідний значенню -го залишку числа по модулю

Для заданого модуля цифрова структура буде мати такий вигляд

.

Таким чином, за допомогою кільцевих регістрів зсуву, що широко використовуються в ПСЧ, легко реалізувати арифметичні операції в СЗК, причому, виходячи з виразу (3.1), ступені циклічних перестановок визначаються наступними виразами:


(3.2)

(3.3)


Позначимо, що , тобто при z = усі елементи впорядкованої множини залишаються на вихідному місці. При технічній реалізації даного методу перший операнд вказує на номер розряду КРЗ, визначаючого результат модульної операції по модулю , а другий операнд визначає кількість розрядів КРЗ (- двійкових розрядів), на які необхідно провести зсув вихідного (2.4) вмісту КРЗ відповідно до алгоритмів (3.2) (3.3). Хай . Тоді таблиця значень модульної суми для кільця класу залишків z/(5) представиться у вигляді матриці (табл.3.2). Вміст розрядів КЗР представиться у вигляді числових даних, наприклад, першого рядка (стовпця) табл.3.2 (рис.3.1,а). На рисунку знаком позначений позитивний (проти годинникової стрілки) напрям зсуву вмісту розрядів КЗР. При цьому перший операнд вказує номер розряду КЗР, вміст якого визначає результат даної операції, а другий операнд вказує число зсувів вмісту розрядів КЗР (рис.3.1, а, б, в).

Введемо поняття оператора кільцевого зсуву (ОКЗ). ОКЗ - це оператор, що визначає величину (виражену в кількості зсуваємих розрядів КЗР) і напрям зсуву розрядів КЗР, і позначається

Так, для операції модульного складання ОКЗ представиться у вигляді , при цьому час зсуву (утворює в основному час виконання операції) вмісту розрядів КЗР визначається виразом


(3.4)


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

На підставі ПКЗ, використовуючи наступну тотожність


(, (3.5)


можна реалізувати операцію модульного віднімання . У цьому випадку ОКЗ має вигляд .

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


Рисунок 3.1 Варіанти структури кільцевого регістру зсуву для

а) 1-й варіант; б) 2-й варіант; в) 3-й варіант


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

Пристрій містить перший інформаційний вхід 1, перший вхідний регістр 2, дешифратор 3, групу ключових елементів 4, групу елементів І 5, перший елемент АБО 6, вихідний регістр 7, вихід 8 пристрою, другий інформаційний вхід 9, другий вхідний регістр 10, суматор 11 по модулю Р, вхід 12 передачі модуля Р, перший 13 і другий 14 елементи І, другий елемент АБО 15, приймаючий регістр 16, схему 17 порівняння, лічильник 18, шину 19 управління складанням, шину 20 управління відніманням, шину 21 запуску пристрою, генератор 22 імпульсів, третій і четвертий елементи І 23 і 24, помножувач 25 частоти і кільцевий регістр 26 зсуву.

Суматор 11 по модулю Р інвертує другий вхідний операнд В по модулю Р, тобто на виході суматора 11 формується Р-В. Помножувач 25 частоти в раз збільшує кількість вихідних імпульсів генератора 22, де Р - модуль основи СЗК, Р- кількість двійкових розрядів одного розряду регістра 26.

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

Розглянемо роботу пристрою. Для операції модульного складання позначається закономірність розподілу в полі матриці (таблиця, Р = 5) зокрема по рядках, результатів операції. Ця закономірність дозволяє замінити матричний пристрій (ПЗП) кільцевим регістром 26 зрушення, в якому записаний один з рядків таблиці.

Хай необхідно визначити (А + В) mod Р (присутній сигнал на шині 19). Вихідне становище пристрою: нульовий стан всіх регістрів 2, 10, 16 і лічильника 18, в регістр 26 записаний перший рядок таблиці модульного складання.

По входу 1 в двійковому коді поступає перший операнд А в регістр 2, а по входу 9 в двійковому коді - другий операнд В на вхід регістра 10 і на перший вхід суматора 11, на виході якого отримаємо значення Р - В. Сигнал по шині 19 відкриває елемент І 13, через який з виходу регістра 10 через елемент АБО 15 операнд В поступає в приймаючий регістр 16. Дешифратор 3 перетворює операнд А з двійкового коду в десятковий, і на один з ключових елементів 4 поступає сигнал, відповідний значенню А. По сигналу по шині 21 з виходу генератора 22 на входи відкритих елементів И 23 і 24 поступають імпульси. З виходу елементу І 23 через помножувач 25 на вхід регістра 26 поступає послідовність імпульсів, збільшена в n раз. У момент порозрядного збігу стана лічильника 18 і регістра 16 (в обох буде записано значення операнда B) схема 17 порівняння видає сигнал, котрий закриває елементи І 23 і 24 і відкриває відповідний ключовий елемент 4 і елемент І 5, через який значення відповідного розряду регістра 26 поступає на елемент АБО 6 і далі в регістр 7.

Нехай необхідно визначити результат операції (А - В) mod Р (присутній сигнал на шині 20). В цьому випадку з виходу суматора 11 значення (Р - В) через відкритий елемент І 14, елемент АБО 15 поступає в регістр 16. Подальша робота пристрою аналогічна визначенню результату операції модульного складання при вхідних операндах А і Р - В.

Розглянемо приклади конкретного виконання операції модульного складання і віднімання для Р = 5 (n = 3).

Вихідне положення вмісту регістра 26 відповідає значенню першого рядка таблиці, тобто перший розряд - 000, другий - 001, третій - 010, четвертий 011 і п'ятий 100. Схематично вихідний вміст регістра 26 можна представити у вигляді (рис.3.1,б).

Приклад 1. А = 0, В = 2. Необхідно визначити (А + В) mod Р (табл.3.2; рис.3.1,а) Перший операнд А = 000 поступає у вхідний регістр 2, з виходу якого через дешифратор 3 сигнал поступає на вхід першого ключового елементу 4. Другий операнд В = 010 поступає на вхід регістра 10 і на перший вхід суматора 11, на другий вхід якого поступає значення Р = 101. Значення операнда В = 010 через відкритий елемент І 13 (присутній сигнал на шині 19), елемент АБО 15 поступає в регістр 16. Управляючий сигнал по шині 21 запускає генератор 22, імпульси через відкриті елементи І 23,24 поступають відповідно на вхід помножувача 25 і лічильника 18. У момент порозрядного збігу стана лічильника 18 (в лічильники міститься значення 010) і регістра 16 схемою 17 виробляється сигнал,котрий закриває елементи І 23 і 24 і відкриває перший елемент 4, відповідно відкривається перший елемент І 5. Одночасно з виходу помножувача 25 на вхід регістра 26 поступають Вn = =23 = 6 імпульсів , котрі зсувають вліво на шість двійкових розрядів (на два розряди регістра 26) первинний вміст регістра, тобто перший вихідний імпульс генератора 22 зсуває вліво вміст регістра 26 на три двійкові розряди. В цьому випадку вміст регістра 26 представляється у вигляді (рис.3.1,в)



другий вихідний імпульс генератора 22 зсуває ще вліво вміст регістра 26 на три двійкові розряди. В цьому випадку вміст регістра 26 представляється у вигляді (рис.3.1,в)

Як було показано, після цього вихідний сигнал схеми 17 закриває елементи І 23 і 24, і з виходу генератора 22 імпульси на помножувач 25 не проходять. Після цього вміст першого розряду регістра 26 - 010 (А = 0) через відкритий перший елемент І 5, елемент АБО 6 поступає на вхід регістра 7. Вміст регістра 7 і представлятиме результат операції.


Рисунок 3.2. Пристрій для складання і віднімання по модулю СЗК


Алгоритм підвищення швидкодії виконання операції модульного складання (віднімання) полягає у використанні тотожності (3.2), а також наступних співвідношень:

,

.


У цьому випадку для операції модульного складання ПОКЗ представляється у вигляді


тобто при операнд визначає кількість z зсувів вмісту КЗР, а операнд - номер розряду КЗР, що визначає результат операції; при операнд визначає кількість z зсувів вмісту КЗР, а операнд - номер розряду КЗР, що визначає результат операції.

Для операції модульного віднімання ПОКЗ представляється у вигляді



тобто при операнд визначає кількість z зсувів вмісту розряду КЗР, а операнд - номер розряду КЗР, що визначає результат операції; при операнд визначає кількість зсувів вмісту розряду КСР, а операнд - номер розряду КЗР, що визначає результат операції.

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

Один з алгоритмів підвищення швидкодії виконання операції модульного складання (віднімання) є алгоритм, заснований на властивості наступної тотожності:


(3.5)


тобто зсув вмісту КЗР можна здійснити як в позитивному, так і в негативному напрямах (для , рис.3.1, б), де для операції модульного складання ПОКЗ представляється у вигляді



Надалі для зручності розрахунків, вважатимемо, що - непарне число Для операції модульного віднімання ПОКЗ представиться у вигляді табл. 3.3. Вживання даного алгоритму дозволяє (залежно від величини модуля ) до 90% скоротити значення величини z, що значно зменшує час t виконання модульних операцій (рис.3.3, а, б).


Таблиця 3.3

01234001234140123234012323401412340

Рисунок 3.3. Варіанти структури кільцевого регістру зсуву для модуля в СЗК: а) 1-й варіант; б) 2-й варіант; в) 3-й варіант


Розглянемо методи і алгоритми реалізації ПКЗ, що дозволяють удвічі скоротити максимальне значення ПОКЗ (максимальне число зсувів вмісту розрядів КЗР). Очевидно, що . Розглянемо наступний вираз:

. (3.6)


У цьому випадку вміст розрядів КЗР відповідає -й рядку (стовпцю) матриці табл. 3.1 (див. рис. 3.1в), а зсув вмісту розрядів КЗР буде проводитися щодо величини , тобто величина максимальної кількості зсувів вмісту розрядів КСР буде рівна . Таким чином, максимальне значення ПОКЗ рівне

(3.7)


Розглянутий алгоритм (рис.3.3в) виконання операції модульного складання (віднімання) дозволяє істотно підвищити швидкодію виконання модульних операцій в СЗК.

Сучасні ЕОМ при рішенні задач значну частину свого корисного часу витрачають на реалізацію операції множення. ЕОМ приблизно половину часу своєї роботи «присвячує» реалізації операції множення і ділення. Існує достатньо багато методів обійти операцію ділення (наприклад, множення першого операнда на зворотну мультиплікативну величину дільника), проте заміна операції множення сукупністю однотипних операцій складання за допомогою ПКЗ значно знижує призначену для користувача продуктивність ЕОМ. Тому при створенні ЕОМ в СЗК важливо синтезувати пристрій для множення, безпосередньо використовуючи принцип кільцевого зсуву.

Один з варіантів реалізації операції модульного множення ) методом кільцевого зсуву полягає у використанні набору з двох КЗР із застосуванням відомого співвідношення:


(3.8)

ОКЗ для першого КЗР представиться у вигляді , а для другого . Час t виконання операції модульного множення буде не набагато більше часу, визначаємого виразом (3.4). Недолік даного варіанту реалізації операції модульного множення - порівняно великий об'єм устаткування операційного пристрою ЕОМ.

Розглянемо варіант реалізації операції модульного множення - варіант множини контурів (ВМК). В цьому випадку використовується один КЗР, за допомогою якого визначається і результат модульного складання віднімання, а ОКЗ для операції модульного множення представляється у вигляді , де i - номер контура, в якому проводиться зсув вмісту розрядів КЗР (i =); n - кількість контурів, по яких працює пристрій ; j - номер встановлюваного рядка матриці значень (індекс i для операндів а, опускається);- ПОКЗ, позначаючий кількість зсувів вмісту розрядів КЗР в даному i-м контурі ().

Суть ВМК полягає в тому, що по значенню другого операнда встановлюється ий рядок таблиці значень шляхом зсуву вмісту розрядів КЗР по окремих контурах (по окремих модулях , причому , оскільки мінімальний (перший) модуль рівний двом, тобто , оскільки нульовий рядок таблиці значень не встановлюється (), то Разом з тим перший розряд КЗР встановлюється одночасно з другим і, таким чином, . Нульовий розряд КЗР участі в реалізації ВМК не приймає, оскільки операція множення на нуль простіше організовується по окремому алгоритму, наприклад, шляхом виведення вхідних нульових шин операндів безпосередньо на нульовий вихід пристрою. Встановлення значення вмісту розрядів КЗР проводиться послідовно, починаючи з (-1)-го (старшого) розряду і до другого включно, тобто справа наліво (рис.3.4, 3.5, табл. 3.4).


Таблиця 3.4

01234000000101234202413303142404321

Рисунок 3.4 Схема реалізації узагальненої арифметичної операції для довільного модуля СЗК


Рисунок 3.5. Схема реалізації операції модульного множення для


3.3 Виведення аналітичних співвідношень для оцінки ефективності принципу кільцевого зсуву


Введемо поняття узагальненого операнда кільцевого зсуву (УОКЗ) у вигляді матриці , де показник узагальненого операнда кільцевого зсуву (ПУОКЗ) означає кількість зсувів вмісту розрядів КЗР в i-м контурі при встановленні j-го рядка матриці модульного виразу . Таким чином, УОКЗ складатиметься з набору -х ОКЗ і може бути розкладений або по рядках , або по контурах у вигляді


(3.9)

(3.10)


Виходячи із запису УОКЗ (3.10), можна визначити тимчасову матрицю :


(3.11)


Час встановлення j-го рядка матриці (час реалізації операції) значень рівен сумі ПУОКЗ для j-го рядка матриці (3.11), помноженої на величину (3.4)


. (3.12)


Очевидно, що . Час реалізації модульної операції множення можна також визначити, виходячи з виразу (3.10). Дійсно, в цьому випадку тимчасова матриця по контурах співпадатиме з транспонованою матрицею , тобто


, (3.13)


а час встановлення j-го рядка матриці рівне сумі ПУОКЗ для j-го стовпця матриці (3.13), помноженої на величину . Очевидно, що в загальному випадку час t реалізації модульної операції , як і для операції модульного складання і віднімання, залежить від величини операнда (від номера j встановлюваного рядка), тобто


. (3.14)


Виходячи з виразу (3.14), доцільно оперувати середнім і максимальним часом реалізації модульних операцій


, (3.15)

. (3.16)


Відповідно до виразу (3.12) запишемо формули (3.15), (3.16) у вигляді


, (3.17)

, (3.18)


а для операції складання (віднімання) формула (3.4) представиться у вигляді

, (3.19)

. (3.20)


Відзначимо, що в кожному з контурів можна застосувати розроблені вище алгоритми скорочення часу встановлення потрібного рядка таблиці даної модульної операції. В цьому випадку результат операції модульного множення визначатиметься за час менший, ніж те, що визначається виразами (3.17) - (3.18). Відомо, що час реалізації операцій складання і множення у ПСЧ визначається наступними виразами:


, (3.21)

. (3.22)


де ? - кількість двійкових розрядів в поданні операндів (розрядна сітка ЕОМ); () - час проходження сигналу через елемент І (АБО) (час «спрацювання» відповідного логічного елементу). Беручи до уваги, що , запишемо вирази (3.22) і (3.23) у вигляді


, (3.22)

. (3.23)


Проведемо порівняльний аналіз часу реалізації арифметичних операцій в ПСЧ і в СЗК для однобайтового (l = 1) і чотирьохбайтового (l = 4) машинного слова. Для l = 1 (?=8) СЗК може представлятися набором наступних основ: для l= 4(?=32) -

Відзначимо, що час реалізації арифметичних операцій в СЗК за принципом кільцевого зсуву визначається часом реалізації даної модульної операції для максимального по величині модуля СЗК, тобто для l = 1 - це модуль = а для l= 4 - це модуль =Відповідно до формул (3.17) - (3.22) розрахуємо максимальний і середній час для реалізації арифметичних операцій (табл. 3.5) без вживання алгоритмів їх прискорення в СЗК і для двійкових ПСЧ. З таблиці 3.5 видно, що вживання принципу кільцевого зсуву, навіть без вживання алгоритмів підвищення швидкодії виконання модульних операцій, дозволяє зменшити, в порівнянні з ПСЧ, час реалізації модульної операції арифметичного множення при прийнятному часі виконання модульної операції складання (віднімання) в СЗК. Відзначимо, що із збільшенням величини l ефективність вживання ПКЗ для виконання арифметичної операції множення в класі залишків зростає


Таблиця 3.5 Дані продуктивності СОКІ

Розрядність чиселt[?]ПСЧМСЧскладання (віднімання)множенняСкладання (віднімання)множеннямаксимальнесереднємаксимальнесереднє

171281811,56322,5

65204814059,52030297,5

Розглянемо приклад конкретної реалізації операції модульного множення при

УОКЗ для представимо у вигляді


, (3.24)


У загальному вигляді УОКЗ розкладемо по рядках і контурах.

По рядках:


,

,

.


По контурах:


,

,

,


На підставі співвідношення (3.24) УОКЗ для відповідно другої третьої (j=3) і четвертої (j=4) рядків табл. 3.4 матиме наступний вигляд:


,

,

.


Загальний алгоритм утворення ПОКЗ для представлений в табл.3.6 (див. рис. 3.5). Визначимо час встановлення j-го рядка табл.3.6 відповідно до виразу (3.4): ?, ?, ? . Визначемо, що відповідно до виразу (3.22) максимальний час встановлення j-й строки Дана обставина підтверджує, що реальна ефективність використання ПКЗ вище, ніж та, що визначається виразами (3.17) та (3.20).


Таблиця 3.6 Алгоритм реалізації операції множення

Номер встановлюваємої строки матриці Номер

контура

ПОКЗ

Вихідний зміст

КЗРОКЗ (

УОКЗ

0 2 3 4 1

3 4 1 2

0 4 1 2 30 1 2 4 3

0 2 4 1 30 2 4 1 30 2 3 4 1

0 3 4 1 20 4 1 3 2

0 1 3 4 20 3 1 4 20 2 3 4 10 3 4 2 10 4 3 2 1

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

, (3.25)


Де - час зсуву одного біта інформації (одного двійкового розряду), де для .

З метою усунення вказаного недоліку і підвищення ефективності реалізації арифметичних операцій в класі залишків пропонується новий метод реалізації арифметичних операцій, також заснований на використанні ПКЗ - метод унітарного кодування, суть якого полягає в тому, що інформаційна структура довільного модуля СЗК представляється у вигляді унітарного (m-1) - розрядного коду


(3.26)


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



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


. (3.27)


Раніше наголошувалося, що час реалізації арифметичної операції А ± В у класі залишків визначатиметься часом виконання операції для максимального значення залишку з сукупності для даного операнда , тобто


. (3.28)


Аналіз виразів (3.25) і (3.28) показує, що розроблений метод унітарного представлення зменшує час виконання арифметичних операцій в порівнянні з методом двійкового кодування в раз. Для з'ясування алгоритму реалізації арифметичних операцій в класі залишків на підставі розробленого методу розглянемо приклад конкретної реалізації операції складання А + В для СЗК, заданими основами . Нехай А = (0, 10, 100) і В=(1,01,010) (табл. 3.7). Оскільки , то відповідно до виразу (3.28) час реалізації операції складання в СЗК для даних операндів рівно ; і в цьому випадку алгоритм реалізації операції складання повністю визначається алгоритмом реалізації операції модульного складання по найбільшому модулю СЗК. Вихідний вміст КРЗ визначається у вигляді





Таблиця 3.7

AА в СЗКAA в СЗК0 1 2 3 4 5 6 7 8 9 10 11 12 13 140 1 0 1 0 1 0 1 0 1 0 1 0 1 000 01 10 00 01 10 00 01 10 00 01 10 00 01 10000 001 010 011 100 001 001 010 011 100 000 001 010 011 10015 16 17 18 19 20 21 22 23 24 25 26 27 28 291 0 1 0 1 0 1 0 1 0 1 0 1 0 100 01 10 00 01 10 00 01 10 00 01 10 00 01 10000 001 010 011 100 000 001 010 011 100 000 001 010 011 100

Перший операнд дешифрується і значення в унітарному коді заноситься в четвертий розряд КРЗ, вміст якого приймає вигляд





Другий операнд також дешифрується і отримане значення визначає кількість z зсувів в позитивному (проти годинникової стрілки) напрямку вмісту КРЗ. У результаті вміст КРЗ представляється так:





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


Таблиця 3.8 Алгоритм шифрування

Вхід шифратораВихід шифратора

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

Проведемо загальну порівняльну оцінку часу реалізації арифметичних операцій в ПСЧ і в класі залишків при використанні ПКЗ. Відомо, що час реалізації арифметичних операцій складання і множення в ПСЧ для l - байтових машинних слів визначається виразами (3.22) і (3.23), де , а можливий максимальний час реалізації відповідних арифметичних операцій для ПКЗ при вживанні методу двійкового подання буде рівний


(3.29)

. (3.30)


Виходячи з виразів (3.6) і (3.7), видно, що максимально можливий час реалізації арифметичних операцій в класі залишків при використанні методу унітарного кодування для операції складання рівно


(3.31)


а для множення


, (3.32)


оскільки , тобто операнд в унітарному коді заноситься в КЗР, а потім послідовно проводиться складання по схемі.

Розрахунки (табл.3.9), проведені відповідно до виразів (3.22), (3.23), (3.29) - (3.32), показали високу ефективність методу унітарного кодування з погляду мінімізації часу реалізації арифметичних операцій в класі залишків в порівнянні з методом двійкового кодування в СЗК і часом реалізації таких же операцій в ПСЧ. Вживання запропонованих алгоритмів дозволить (залежно від величини модуля і значення операнда ) до 90% скоротити максимальний час реалізації арифметичних операцій в СЗК. Модульність структури обчислювального процесу в класі залишків дає можливість ефективно застосувати ПКЗ для реалізації основних арифметичних операцій. Використання ПКЗ дозволить, як і при табличному принципі, усунути вплив міжрозрядних зв'язків між двійковими розрядами операндів А і В на результат обчислень при прийнятній кількості устаткування операційного пристрою ЕОМ.


Таблиця 3.9 Дані продуктивності СОКІ у МСЧ

Розрядність чиселОснови МСЧПСЧМСЧ (ПКЗ)складаннямноженнядвійкове представленняУнітарне представленняскладаннямноженняскладаннямноження1712818636303351248312121324911529085518306652048140203028756

Таким чином, на основі сформульованого ПКЗ запропоновані нові методи реалізації арифметичних операцій в класі залишків - методи двійкового і унітарного кодування. Розроблені алгоритми реалізації даних методів, а також алгоритми, що дозволяють скоротити час реалізації арифметичних операцій в класі залишків. Проведений розрахунок часу реалізації арифметичних операцій в СЗК, навіть без урахування впливів алгоритмів підвищення швидкодії, показана висока ефективність використання запропонованих методів. Розглянуті методи і алгоритми можуть бути рекомендовані до практичного використання для ЕОМ, що функціонують в реальному часі з підвищеними вимогами по відмовостійкості (рис. 3.6).


Рисунок 3.6. Схема функціонування операційного пристрою СОКІ у МСЧ для ПКЗ а) 1-й алгоритм; б) 2-й алгоритм


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

Очевидно, що максимальної швидкодії виконання арифметичних операцій при вживанні принципу кільцевого зсуву можна досягти, використовуючи програмний метод реалізації модульних операцій. В цьому випадку, використовуючи керуючі матриці, в більшості варіантів результат операції можна досягти за менше, ніж , число зсувів двійкових розрядів. Це обумовлено тим, що зсув вмісту КЗР проводиться відповідно до даних керуючих матриць на число двійкових розрядів, кратне величині, тобто на мінімально необхідне число двійкових розрядів. Здійсненність даної процедури обумовлена надмірністю вмісту розрядів КЗР. Вміст керуючих матриць визначається для кожної операції (складання, віднімання і т.п.) і для кожної підстави СІК індивідуально. Вузлу керуючої матриці привласнюється значення (з урахуванням напряму зсуву), рівне кількості необхідних зсувів вмісту двійкових розрядів КЗР. Для вміст керуючих матриць операцій складання, віднімання і множення розрахований і представлений відповідно в табл. 3.10-3.11


Таблиця 3.10

0123400000001313-211024614-4193-64-4-1-6214-3-3-3-3-315

Таблиця 3.11

0123400000001-3-1-3-3-3132-64-4-1-62134614-4194313-2110

Таблиця 3.12

01234000000010000002011-1-3630-6-33-6184043-3-414

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

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

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

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

Через властивість ПКЗ вага вектора вмісту КЗР завжди постійний, тобто


(3.33)


Співвідношення (3.33) можна представити у вигляді


. (3.34)


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

Розглянемо приклад конкретного виконання операції модульного складання в полі для (таб.3.2) з урахуванням корегуючих здібностей коду СЗК при використанні ПКЗ.

На рис.3.7 представлений вихідний вміст КЗР для .

Для даного прикладу ваги відповідних розрядів КЗР такі:


Таким чином,



Рисунок 3.7.а. Узагальнена схема кільцевого регістру зсуву для довільного модуля СЗК


Рисунок 3.7.б. Схема кільцевого регістру зсуву для модуля =5


Введемо позначення значення вмісту j -го лічильника, підключеного до виходу j -го розряду КЗР після -го зсуву розрядів КЗР як . Тоді справедливе наступне співвідношення:


. (3.35)


На підставі виразу (3.35) може бути реалізований алгоритм виявлення помилок (табл. 3.13). Таким чином, вживання ПКЗ дозволяє істотно підвищити достовірність, обчислень. Це досягається за рахунок використання специфічних особливостей реалізації арифметичних операцій модульного складання і віднімання в полі . Окрім цього, з'являються додаткові корегуючі можливості за рахунок використання властивостей принципу кільцевого зсуву - постійність структури поля , зокрема, постійна вага вектора вмісту КЗР.

Таблиця 3.13 Таблиця шифрування даних у МСЧ

000 001 010 011 100000 000 001 010 100000 001 010 100 101000 001 011 100 100000 010 011 011 100000 001 001 010 01100000 00101 01010 01111 101004. ДОСЛІДЖЕННЯ МАТЕМАТИЧНОЇ МОДЕЛІ НАДІЙНОСТІ СПЕЦПРОЦЕСОРА ОБРОБКИ КРИПТОГРАФІЧНОЇ ІНФОРМАЦІЇ У МОДУЛЯРНІЙ СИСТЕМІ ЧИСЛЕННЯ

  • 4.1 Вихідні дані, що необхідно для синтезу СОКІ у МСЧ
  • спецпроцесор криптографічний модулярний кільцевий
  • Метою розрахунку обчислювальної системи є визначення кількісних значень її показників в залежності від надійності елементів, типу системи, режимів роботи та умов її експлуатації, а також відповідності цим вимогам.
  • Завдання розрахунку надійності вирішується у двох основних випадках:
  • а) при оцінці надійності з проектованої системи;
  • б) при визначенні шляхів підвищення надійності системи, яка експлуатується.
  • Методика (алгоритм) розрахунку надійності:
  • 1) Загальний аналіз системи. Проводиться аналіз принципової схеми системи, внаслідок чого визначаються типи елементів, їх кількість, типи дефектів і вплив на працездатність системи. Формулюється поняття відмова системи згідно з її цільовим призначенням і набором параметрів, які визначають її нормальне функціонування.
  • 2) Отримання структурної схеми надійності. Будується структурна схема надійності системи. Структурна схема надійності системи це зображення системи у вигляді сукупності елементів, які визначають її працездатність, і зв'язки між ними. Елементи на ССН зображаються прямокутниками, аналогічними позначенню резисторів на електричних схемах.
  • Елементи в ССН вмикаються послідовно, якщо відмова хоча б одного з елементів призводить до відмови всієї системи в цілому, і паралельно, якщо при відмова одного чи декількох елементів не призводить до втрати працездатності системи. Відповідно до цього розрізняють структурні схеми надійності трьох типів: з послідовним, паралельним та змішаним з'єднанням елементів. Приклади таких ССН показано на рисункові 4.1 а), б) та в) відповідно. Існує ще один тип ССН із так званим містковим з'єднанням елементів (рисунок 4.1 г)), коли один елемент (наприклад, елемент 2) вмикається з іншими елементами одночасно послідовно і паралельно в залежності від ланцюжка.
  • Слід зауважити, що порядок вмикання елементів у ССН визначається лише їх впливом не працездатність системи, так як елемент, увімкнений у принциповій схемі паралельно, може бути увімкненим у ССН послідовно і навпаки.
  • 3) Попередній розрахунок надійності. Проводиться попередній розрахунок показників надійності системи з врахуванням ССН і з використанням табличних значень інтенсивностей відмов її елементів без врахування режимів роботи (коефіцієнтів навантаження) та умов експлуатації. Мета попереднього розрахунку - визначення можливості забезпечення необхідної надійності на обраній елементній базі.
  • 4) Остаточний розрахунок надійності. Здійснюється остаточний розрахунок надійності системи, для чого:
  • - проводиться вибір параметрів W1, …, Wn, які характеризують працездатність елементів, електричний розрахунок схеми і визначення реальних значень параметрів W1p, …, Wnp;
  • - за довідниками визначають номінальні значення вибраних параметрів W1н, …, Wnн і обчислюються коефіцієнти навантаження елементів:

k н1 = W1p / W, …, k нn = Wnp / Wnн; (4.1)


  • - здійснюється пошук поправочних коефіцієнтів a1,..., an за номограмами з врахуванням знайдених коефіцієнтів навантаження і умов експлуатації (температури та інше);
  • - розраховуються дійсні значення інтенсивностей відмов елементів l1*,..., ln* з врахуванням поправочних коефіцієнтів a1,..., an:

lі* = аі × lі, (4.2)


  • де і = 1, 2,..., n;
  • - визначаються показники надійності для знайдених інтенсивностей відмов lі*.
  • У тому випадку, коли відсутня інформація про інтенсивності відмов деяких елементів системи, може бути використаний так званий коефіцієнтний метод. Суть його полягає в урахуванні того, що відношення інтенсивності відмов елементів різних типів із збільшенням температури, електричного навантаження та інших факторів змінюється неоднозначно. Тоді, вибравши за основний елемент той, для якого є найповніша інформація про інтенсивність його відмов lосн (l*осн) і її залежність від різних факторів (тобто відомі номограми поправочних коефіцієнтів даного елемента), інтенсивність відмов будь-якого іншого елемента lі (lі*), можна отримати помноживши її на відповідний коефіцієнт Xі:

lі = lОСН Xі; (4.3)

lі* =l*ОСН Xі =l ОСН aіXі. (4.4)


  • Коефіцієнти X визначені для елементів різного типу та наведені у довідникових таблицях. У якості основного елемента найчастіше використовують резистори, з Xі=1.
  • Аналіз даних таблиці показує, що розкид максимальних і мінімальних значень коефіцієнтів Xі МІН. та Xі МАКС. невеликий і дозволяє використовувати їх середню величину Xі СЕР. в інженерних розрахунках.
  • Для оцінки інтенсивності відмов інтегральних мікросхем l*іС може бути використана інформація про інтенсивність відмов елементів їх структури і конструкції: діодів lД, транзисторів lТ і з'єднань lЗ, а також про кількість зовнішніх виводів (вхідних та вихідних кіл). Тоді для корпусних інтегральних схем:

l*іkС = [NТaТlТ + NДaДlД + (3NТ + 2NД + NД)lЗ] Квб, (4.5)


  • де aТ, aД - поправочні коефіцієнти для транзисторів і діодів;

NТ, NД, NВ - кількість транзисторів, діодів та зовнішніх виводів;

Квб - коефіцієнт вібрації.

Для без корпусних інтегральних мікросхем формула (4.9) спрощується тому, що NВ = 0.

Поправочні коефіцієнти aТ, aД визначаються за довідниковими даними [22].

  • 5) Аналіз результатів. Перевіряється відповідність отриманих значень показників надійності системи необхідним значенням і робиться висновок:
  • а) про можливості використання системи за призначенням;
  • б) про найменш надійні елементи системи;
  • в) про можливі шляхи підвищення надійності системи.
  • Розглянутий алгоритм розрахунку надійності має загальний характер і може бути використаний для аналізу надійності чотирьох типів схем: нерезервованих і не відновлюваних; нерезервованих і відновлюваних; резервованих і не відновлюваних; резервованих і відновлюваних.

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

  • Основними методами резервування обчислювальних систем являються: загальне постійне, роздільне постійне, та змішане постійне резервування. Недоліком цих методів резервування є те, що сфера їх застосування обмежується, як правило, аналоговими системами невеликої складності. У чистому вигляді такі методи недопустимі для більшої частини апаратури цифрових систем обчислювальних пристроїв. Особливостями цієї апаратури є те, що в ній інформація подана у вигляді двійкових кодів числового, адресного, логічного, командного та іншого характеру. Окрім того, така апаратура виконана, як правило, на інтегральних мікросхемах. Дія на них різноманітних перешкод призводить до спотворення інформації, яке не може бути скомпенсоване вище згаданими методами резервування.
  • Отже, для цифрових систем слід використовувати інші методи резервування, серед яких найпоширенішим є метод мажоритарного резервування. Суть цього метода полягає в тому, що інформація з виходів резервованих систем вибирається за більшістю (шляхом голосування одним із трьох способів).
  • Розрізняють: арифметичне мажоритування; медіанне (числове) мажоритування; кодове мажоритування.
  • 1) При арифметичному мажоритуванні на вихід системи надходить код, який відповідає середньому арифметичному кодів на виході каналів, які резервуються.
  • Наприклад, система має три канали, які видають чотирирозрядну інформацію 0001 (перший канал), 0100 (другий канал) і 1101 (третій канал). Тоді на вихід системи повинен надійти код:
  • К ={[0001]2 + [0100]2 + [1101]2}/3 = {[1]10 + [4]10 + [13]10}/3 = [0110]2 = [6]10,
  • де [Х]2, [Х]10 - числа, записані в двійковій та десятковій системах числення відповідно.
  • Арифметичне мажоритування може бути реалізоване шляхом послідовного з'єднання двох чотирирозрядних комбінаційних суматорів і схеми ділення на три (рисунок 4.4 а)). Арифметичне мажоритування часто використовується в системах попередньої обробки вимірювальної інформації, яка надходить від декількох одно типових датчиків АСК з метою зменшення похибки.
  • 2) При медіанному мажоритуванні результат формується як число більше меншого і менше більшого. У наведеному прикладі результатом медіанного мажоритування буде код [0100]2, оскільки йому відповідає число, яке більше 1 і менше 13.

  • Рисунок 4.1 Реалізація мажоритування:
  • а) - арифметичного; б) - медіанного; кодового в) - для однорозрядних кодів; г) - чотирирозрядних кодів.
  • Схему реалізації медіанного мажоритування зображено на рисунку 4.4 б), вона складається з двох паралельно увімкнених блоків порівняння, перетворювача кодів X/Y, який за сигналами від цих блоків формує код управління комутатором, що видає на вихід інформацію з відповідного каналу. Вона використовується в схемах обчислювальних пристроїв при логічній обробці інформації від різних джерел.
  • На практиці найбільшого поширення набули системи з m = 3, k = 2 і m= = 5, k = 3. Їх називають мажоритарно - резервованими системами 2 із 3 і 3 із 5.
  • Приклад реалізації мажоритарного елемента 2 із 3 показано на рисунку 4.4 в). Його вихідний сигнал описується таблицею відповідності 4.2, з якої випливає, що
  • Z = X3X2 V X2X1 V X1X3.
  • Таблиця 4.1 Відповідність вхідних і вихідних сигналів елемента 2 із 3
Вхідні сигналиВихідний сигналX3X2X1Z00000010010001111000101111011111

  • Таким чином, мажоритарний елемент формує сигнал за більшістю 0 (1) на його виході. На рисунку 4.1 наведено схему мажоритування для розглянутого вище прикладу, яку складено з чотирьох однорозрядних мажоритарних елементів. При появі на входах цієї схеми кодів 0001, 0100 і 1101 з трьох каналів на її виході буде з формовано код 0101.
  • Кодове мажоритування на практиці знайшло найбільшого поширення в задачах резервування цифрових систем обчислювальних пристроїв. Використання найпростіших схем кодового мажоритування забезпечує працездатність системи при наявності в ній k - 1 каналів, які відмовили.

4.2 Математична модель надійності СОКІ у МСЧ

  • Синтезуючи структуру СОКІ у класі залишків ймовірність безвідмовної роботи СОКІ у ПСЧ можна визначити як ймовірність безвідмовної роботи ЕОМ у ПСЧ для випадку ковзного резервування з навантаженим резервом. В цьому випадку формула для визначення імовірності безвідмовної роботи СОКІ у МСЧ прийме вигляд наступного виразу:

(4.6)


Тут p1(t) = e -l1t - ймовірність безвідмовної роботи тракту ЕОМ по найбільшій (найменш надійній) основі mn+k СЗК, де l1 - інтенсивність відмов обладнання тракту ЕОМ у СЗК найбільшій основі mn+k.

Співвідношення (4.11) може бути використане для розрахунку імовірності безвідмовної роботи ЕОМ в СЗК при наступних припущеннях:

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

комутуючі пристрої ідеальні (тобто ймовірність безвідмовної роботи комутатора дорівнює одиниці);

інформаційні і контрольні тракти ЕОМ рівнонадійні, тобто ймовірність безвідмовної роботи всіх трактів ЕОМ приймається рівною імовірності безвідмовної роботи p1(t) тракту ЕОМ по найбільшій основі СЗК mn+k, що має найменшу ймовірність безвідмовної роботи;

не враховується можливість відновлення трактів ЕОМ у СЗК, які відмовили.

Відмітимо, що реальна надійність ЕОМ у СЗК буде вищою, ніж та, що визначається співвідношенням (4.11), тому що дана формула не враховує можливість заміни одним контрольним трактом по основі mj одного або одночасно декількох непрацездатних інформаційних трактів за умови:


, (4.7)


  • де r - максимальне число трактів, які заміняються одним контрольним працездатним трактом по основі mj.
  • 4.3 Аналіз продуктивності та надійності СОКІ у МСЧ
  • Проведемо порівняльний аналіз надійності потроєної позиційної ЕОМ з ідеальним мажоритарним елементом ЕОМ у СЗК з ідеальним комутатором по безвідмовності, застосовуючи розглянуту надійну модель. Позначимо через lэ інтенсивність відмов обладнання, віднесену до одного двійкового розряду (до одиниці розрядної сітки СЕОМ). В цьому випадку ймовірність безвідмовної роботи обладнання, віднесена до одного двійкового розряду ЕОМ дорівнює:

. (4.8)


  • Для позиційної l-байтової ЕОМ ймовірність безвідмовної роботи дорівнює:

, (4.9)

де l0 = 8 l lЕ.

  • З врахуванням l0 вираз (4.9) набуває наступного вигляду:

. (4.10)


  • Відомо, що ймовірність безвідмовної роботи для потроєної мажоритарної структури, яка містить три ЕОМ і ідеальний мажоритарний елемент, дорівнює:

. (4.11)


Для ЕОМ в СЗК ймовірність безвідмовної роботи тракту по довільній основі :


p1(t)=e-l1t; (4.12)

або , (4.13)

де an+k = [log 2(mn+k -1)] + 1.

  • Ймовірність безвідмовної роботи ЕОМ у СЗК визначається відповідно до виразу (4.11).
  • Нехай l = 1 (однобайтова ЕОМ) і k = 1. Тоді з урахуванням критерію мінімальності апаратурної надлишковості ЕОМ систему залишкових класів можна представити у виді набору наступних основ m1 = 3, m2 = 4, m3 = 5, m4 = = 7, m5 = 11. При цьому:

,


і НСД (mi, mj) = 1 для i ¹ j. В цьому випадку співвідношення (4.11) заприйме вигляд:


. (4.14)


  • Позначимо l* = 8lе. При цьому вирази (4.13) і (4.14) можна записати наступним чином:

; (4.15)

. (4.16)

Відповідно до виразів (4.15) і (4.16) розраховуються значення імовірності безвідмовної роботи для потроєної позиційної ЕОМ і для ЕОМ у СЗК. На рисунку представлено графіки залежностей P(l*t) для однобайтових ЕОМ: нерезервованої (I), триканальної резервованої ЕОМ у ПСЧ (II) і ЕОМ у СЗК з параметрами l = 1, n = 4, k = 1 (III). Видно, що ЕОМ у СЗК з однією контрольною основою (III) більш надійніша потроєної позиційної обчислювальної системи (II). При цьому критичне значення імовірності безвідмовної роботи ЕОМ в класі залишків дорівнює 0,425, а критичне значення потроєної обчислювальної системи дорівнює 0,5, тобто розширюється область значень l*t, при яких збільшується (в порівнянні з нерезервованою позиційною ЕОМ (I)) безвідмовність роботи непозиційної ЕОМ.

  • Нехай k = 2. У цьому випадку СЗК можна представити у виді набору наступних основ: m1 = 3, m2 = 4, m3 = 5, m4 = 7, m5 = 11, m6 = 13.
  • Для даного набору основ вираження (4.11) запишемо наступним чином:

; (4.17)

або . (4.18)


  • 5. МЕТОДИЧНИЙ РОЗДІЛ

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

  • У методичному розділі дипломного проекту розробляється доповідь для конференції інженерного складу на «Криворізькому залізорудному комбінаті» для співробітників підприємства та інженерів горно добувної галузі, які займають посади інженерів-технологів, інженерів-електриків, інженерів по обслуговуванню технічних засобів. У конференції беруть участь інженери, що мають освіту бакалавра, спеціаліста та магістра.
  • Враховуючи зміни, що тривають у технічному комплексі країни, виникла необхідність розгляду окремих питань, які є необхідними для якісної роботи механізмів роторного екскаватору з нейрорегуляторами NN Predictive Controller і Model Reference Controller.
  • Конференція проводиться з питань особливостей автоматизованих систем управління типовим промисловим устаткуванням.
  • Цілі, що будуть реалізовані:
  • Вміти розраховувати потужність електроприводу механізмів підйому, переміщення та повороту, вибрати тип та основні елементи систем управління механізмами;
  • Робити вибір архітектури нейронної мережі системи управління, розрахувати та виконати вибір основної елементної бази;
  • Робити вибір методу навчання нейтронної мережі системи управління електроприводом;
  • Моделювати систему в пакеті прикладних програм MATLAB, розраховувати та будувати графіки перехідних процесів;
  • Виконувати синтез системи з нейрорегулятором.

Наступним етапом роботи є розробка програми конференції. Програма проведення конференції включає: визначення цілей конференції, визначення членів президії, встановлення кількості та характеру засідань їх тривалості, визначення місця доповіді на тему «Нейромережеві системи управління багатомасовими електромеханічними системами основних механізмів роторного екскаватора з нейрорегуляторами NN Predictive Controller і Model Reference Controller» в роботі конференції.

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

Відповідно до програми конференції доповідь на тему «Нейромережеві системи управління багатомасовими електромеханічними системами основних механізмів роторного екскаватора з нейрорегуляторами NN Predictive Controller і Model Reference Controller» буде викладена третьою за списком доповідачів.

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

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

1. Терехов В.А., Ефимов Д.В., Тюкин И.Ю. Нейросетевые системы управления. - М.: ИПРЖР, 2002. - 480 с.

. Клепиков В.Б., Махотило К.В., Сергеев С.А., Вороновский Г.К. Искусственные нейронные сети: новая парадигма в управлении // Труды межд. конф. «Проблемы автоматизированного электропривода. Теория и практика».- Харьков: Основа.- 1995. - С. 111-115.

3. Головко В.А. Нейронные сети: обучение, организация и применение. Кн. 4. - М.: ИПРЖР, 2001. - 256 с.

. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. Пер. с польск. И.Д. РудШНМкого. - М.: Горячая линия - Телеком, 2006. - 452 с.

Представимо тезисні положення доповіді.

Тема дослідження «Нейромережеві системи управління багатомасовими електромеханічними системами основних механізмів роторного екскаватора з нейрорегуляторами NN Predictive Controller і Model Reference Controller».

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

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

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

Об'єкт дослідження - двомасова система управління електроприводом основних механізмів роторного екскаватора.

Предмет дослідження - характерники двомасової системи з нейромережевою системою управління.

Мета дослідження - здійснити дослідження характерник двомасової системи з нейрорегуляторами NN Predictive Controller і Model Reference Controller та провести їх аналіз.

Завдання дослідження:

  1. Провести аналіз наукових джерел з проблеми дослідження.
  2. Теоретично обґрунтувати математичну модель двомасової системи.
  3. Провести розрахунок перехідних процесів двох масової систем на ЕОМ.
  4. Провести синтез нейрорегуляторів NN Predictive Controller і Model Reference Controller системи автоматичного управління.

Наукова новизна дослідження та теоретичне значення:

  • вперше встановлені характеристики двомасової системи управління електроприводом основних механізмів роторного екскаватора з нейрорегуляторами NN Predictive Controller і Model Reference Controller;
  • вдосконалено систему дослідження характеристик двомасової системи управління електроприводом основних механізмів роторного екскаватора
  • подальшого розвитку знайшли підходи до проведення досліджень характеристик двомасової системи.
  • Практична значущість дослідження полягає в тому, що розроблена математична модель двомасової системи управління електроприводом основних механізмів роторного екскаватора та встановлені її характеристики, отримані результати впроваджені у практику.
  • При проведенні дослідження розроблена математична модель системи з урахуванням податливості зв'язків між двигуном і механізмом, складені рівняння стану двомасової системи і проведено моделювання системи на ЕОМ. Як видно з графіків, перехідні процеси робочого механізму мають задовільний характер.
  • Для отримання задовільних динамічних характеристик був виконаний синтез оптимальної системи по інтегральному квадратичному критерію якості.
  • Виконано синтез на ЕОМ системи з нейроконтролером. Для синтезу використаний нейроконтролер з прогнозом NN Predictive Controller, реалізований в пакеті прикладних програм МАТLАВ.
  • У дослідженні розглянуті принципи побудови і функціонування нейроконтролера, приведений порядок синтезу нейроконтролера, побудовані процеси в двохмасовій системі з нейроконтролером. Аналіз графіків показав, що реакція системи на ступінчасту дію з випадковою амплітудою цілком задовільна, має коливальний характер з достатньо швидким загасанням.
  • Під час роботи конференції нами встановлені такі соціодемографічні характеристики слухачів, що прийняли участь у конференції: базова освіта - вища, стать - переважно чоловіча, вік - від 21- до 27 років, місце проживання - громадянин України, фінансово-економічні умови - нормальні, слід зазначити, що слухачі з цікавістю вислуховували доповіді, задавали питання.
  • Для того щоб зацікавити слухачів було використаний наступний мотиваційний вступ:
  • «Шановні, слухачі! У час стрімкого росту інформації, розвитку техніки та технології нейронних мереж нам, інженерам, фахівцям, що трансформують технічні знання з метою вирішення технологічних та виробничих задач, є необхідним займатися наукового діяльністю.
  • Таблиця 5.1 Вибір базових понять, визначення способів перевірки та формування базових знань

Питання доповідіЧасПерелік базових понятьСпособи (методи, форми, засоби) корегування базових знаньСпособи активізації учасників конференції під час доповіді123451. Характеристики двомасової системи як проблема у сучасній науці та практиці. 2. Математична модель двомасової системи. 3. Структура штучної Нейтронної мережі 4. Синтез нейрорегуляторів NN Predictive Controller і Model Reference Controller системи автоматичного управління 5. Результати розрахунку перехідних процесів двомасової систем на ЕОМ15 хв.1.Схема механічної частини електроприводу. 2. Поняття двомасової системи та її розрахункова схема. 3. Поняття нейтронної мережі 4. Поняття перехідних процесів та методи їх розрахунку на ЕОМ.При відсутності у слухачів базових знань, з теми доповіді, вони будуть викладені підчас доповідіДля актуалізації студентів використовуються питання 1. Які складові елементи має електромеханічна система. 2. Що таке двомасова система, та чим вона відрізняється від одно масової системи. 3. Структура нейтронної мережі 4. Поняття перехідної функції, процесу. Як перехідний процес відображається на графіку.


  • В нашу галузь все більш входять технології нейромережевих систем управління електромеханічним устаткуванням. І тому наша наукова діяльність повинна здійснюватися з точки зору цих нововведень. Тільки тоді, інженер зможе встигати за новими технологіями, займатися дослідницькою діяльністю яка у майбутньому, можливо, займе визначне місце у науці України».
  • Наступним етапом є вибір базових понять, визначення способів перевірки та формування базових знань (таблиця 5.1).

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

  • повнота (повністю розкрите питання);
  • логічність побудови;
  • доступність викладу;
  • наочність.

Далі представлена презентація з питань доповіді, що розроблена у програмі Power Point.


Презентація з питань доповіді, розроблена у програмі Power Point.


Слайд 1.


Слайд 2


Слайд 3


Слайд 4


Слайд 5


Слайд 6


Слайд 7


Слайд 8


Слайд 9


Слайд 10


Слайд 11


Слайд 12

ВИСНОВКИ


Підведемо підсумок впливу властивостей СЗК на основні характеристики спеціалізованих ЕОМ, а також на їх структуру і принципи функціонування.

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

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

Рівноправність залишків. Будь який залишок аі числа А = а1, а2,..., аn в СЗК несе інформацію про все початкове число А, що дає можливість програмними методами замінити обчислюваний тракт по модулю mi, який, зіпсувався, на працездатний тракт по модулю mj (mi < mj), не перериваючи вирішення задачі. Окрім того, ЕОМ в СЗК з двома контрольними основами зберігає свою працездатність при відмові будь-яких двох обчислюваних трактів. При відмові третього чи навіть четвертого тракту ЕОМ в СЗК ще може виконувати програму при деякому зниженні точності обчислень, тобто така ЕОМ: має властивість деградації і являється виключно живучою. Дана властивість обумовлює наступну характерну особливість функціонування ЕОМ: один і той же обчислювач в СЗК може мати різну надійність при вирішенні різних задач в залежності від вимог, які предявляються до точності, обєму памяті і швидкодії ЕОМ, тобто в процесі вирішення задач можливе здійснення обмінної операції між точністю обчислень, швидкодією розвязання алгоритмів і надійністю (вірогідністю) вирішення задачі.

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

Малорозрядність залишків. Створені алгоритми реалізації арифметичних операцій, дозволяють різко підвищити надійність і продуктивність ЕОМ. Окрім того, є можливість підвищити ймовірність обчислень за рахунок організації процесу самокорекції результату обчислень шляхом множення проміжного результату операції по модулю mi на нуль, так як ймовірність появи нулів в залишкові по модулю mi достатньо висока і рівна 1/mi. Тому зявляється можливість побудови аналогової обчислюваної системи, яка функціонує з будь-якою заздалегідь заданою точністю при невисокій точності обчислень в кожному тракті ЕОМ в СЗК, рівній 1/mi.

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

На сьогодні ведуться пошуки шляхів покращення надійністних характеристик спеціалізованих ЕОМ за рахунок використання так званого позиційно-залишкового представлення операндів. Нехай задано операнд А в позиційному представленні:


А' = (аn-1·qn-1 + аn-2·qn-2 +... + а1·q + а0),

де аі = 0,..., q - 1; q £ М.


Дане представлення операнда А без надлишкове, але якщо кодування кожної q-тої цифри аq здійснити кодом СЗК з двома контрольними основами, то в межах кожної q-тої цифри код в позиційно-залишковому представленні буде надлишковим, тобто буде мати деякі коректуючи властивості, а операнд А прийме вигляд:


А = S1, а2,..., аn, аn+1, аn+2)qі-1


де mn+1, mn+2 - контрольні основи СЗК.

Існує інше можливе представлення операнда А при позиційно-залишковому кодуванні. Всі q-і цифри операнда А кодуються безнадлишково по n основам СЗК, але при цьому додається n-й контрольний розряд, закодований в СЗК по основам mn + 1, mn + 2 в результаті число А прийме вигляд;


А'' = S1, а2,..., аn)qі // (аn+1, аn+2) // N


де // - знак операції конкатенації (склеювання);- номер q-njї цифри (N = 0, n - 1) числа А, яка в даний момент закодована по контрольним основам mn + 1, mn + 2 (an+1, an+2).

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

Одним з важливих шляхів подальшого застосування СЗК являється використання залишкового кодування при обробці інформації в гіперкомплексній числовій області. У відповідності з результатами першої теореми Гауса, яка стверджує, що по даному комплексному модулю m = q1 + q2 і норма якого відповідно рівна , кожне комплексне число зрівняне з одним і тільки одним залишком із ряду натуральних чисел 0, 1, 2,..., mi - 1. В цьому випадку встановлюється ізоморфізм між комплексними числами і їх натуральними залишками. Дана обставина дозволяє повністю замінити комплексну числову область натуральною, тобто залишками по нормі /m/ даного модуля m = q1 + q2і. Це дає можливість обробляти інформацію в комплексній області, працюючи тільки з натуральною областю, що дозволяє суттєво спростити алгоритм вирішення задач, підвищити ймовірність і продуктивність їх реалізації. При реалізації обчислюваних алгоритмів в комплексній області відсутня складна операція виділення реальної і уявної частин і операція визначення їх взаємного звязку, зявляється можливість паралельної обробки. Застосування СЗК для обробки інформації в гіперкомплексній області відкриває широкі перспективи створення ефективних алгоритмів керування складними технічними обєктами на основі використання багатовимірних векторів функціональних просторів різних класів [17 ÷ 21].


ПЕРЕЛІК ПОСИЛАНЬ


1.Изотов Б. В., Молдовян А. А., Молдовян Н. А. Скоростные методы защиты информации в АСУ на базе управляемых операций // Автоматика и телемеханика. - 2001. - №6. - С. 168-184.

2.Карякин Ю. Д. Технология «AXIS-2000» защиты материальных объектов от подделки // Управление защитой информации. - Минск. - 1997. - Т. 1. - №2. - С. 90-98.

.Кострикин А. И. Введение в алгебру. Основы алгебры: Учебник для вузов. - М.: Физматлит, 1994. - 320 с.

.Крамер Г. Математические методы статистики. - М.: Мир, 1975. - 648 с.

.Молдовян А. А., Молдовян Н. А. Вероятностные механизмы в недетерминированных блочных шифрах // Безопасность информационных технологий. - 1997. - №3. - С. 58-61.

.Молдовян А. А., Молдовян Н. А. Метод скоростного преобразования для защиты информации в АСУ // Автоматика и телемеханика. - 2000. - №4. -С. 151-165.

.Молдовян А. А., Молдовян Н. А., Молдовян П. А. Новый метод криптографических преобразований для современных систем защиты ПЭВМ // Управляющие системы и машины. - Киев. - 1992. - №9/10. - С. 44-50.

.Молдовян А. А., Молдовян Н. А. Псевдовероятностные скоростные блочные шифры для программной реализации. Кибернетика и системный анализ.- Киев.-1997. -№4. -С. 133-141.

.Молдовян А. А., Молдовян Н. А. Скоростные шифры на базе нового криптографического примитива// Безопасность информационных технологий. - 1999. -№1. -С. 82-88.

10.Молдовян А. А., Молдовян Н. А., Советов Б. Я. Криптография. - СПб.: Лань, 2000. -224-с, ил.

11.Молдовян А. А., Молдовян Н. А. Способ блочного шифрования данных. Патент РФ №2106752. МПК 6 Н 04 L 9/00. - Бюл. №7 от 10.03.98.

.Молдовян А. А. Некоторые вопросы защиты программной среды ПЭВМ// Безопасность информационных технологий. - 1995. - №2. - С. 22-28.

.Молдовян Н. А. Скоростные блочные шифры.- СПб.: Издательство СПбГУ, 1998. -230 с.

.Смид М. Э., Бранстед Д. К. Стандарт шифрования данных: Прошлое и Будущее. The Data Encryption Standard: Past and Future // ТИИЭР. - 1988. - T. 76. - №5.- С 43-53.

15.Сэвидж Д. Э. Сложность вычислений. - М.: Факториал, 1998. - 368 с, ил.

.Шеннон К. Э. Символический анализ релейных и переключательных схем // В кн.: Шеннон К. Э. Работы по теории информации и кибернетике. - М.: Иностранная литература, 1963. - С. 9-45.

.Шеннон К. Э. Синтез двухполюсных переключательных схем // В кн.: Шеннон К. Э. Работы по теории информации и кибернетике. - М.: Иностранная литература, 1963. - С. 59-105.

.Шеннон К. Э. Теория связи в секретных системах// В кн.: Шеннон К. Э. Работы по теории информации и кибернетике. - М.: Иностранная литература, 1963. -С. 333-402.

19.Benes V. Е. Algebraic and Topological Properties of Connecting Networks // Bell Systems Technical Journal. - 1962. - V. 41. - P. 1249-1274.

20.Benes V. E. Mathematical Theory of Connecting Networks and Telephone Traf-fic. - New York.: Academic Press, 1965. - 319 p.

21.Benes V. E. On Rearrangeable Three-stage Connecting Networks // Bell Systems Technical Journal. - 1962. - V. 41.-P. 1481-1492.

22.Bennett С. Н., Brassard G. Quantum Cryptography: Public Key Distribution and Coin Tossing // Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing // Banjalore, India. - 1984. - P. 175-179.

23.Biham E., Biryukov A., Shamir A. Cryptanalysis Skipjack Reduced to 31 Round Using Impossible Differentials // Advances in Cryptology- EUROCRYPT99 // Lecture Notes in Computer Science. Springer-Verlag.- 1999.- V. 1592.- P. 12-23.

24.Biham E. On Matsuis Linear Cryptanalysis// Advances in Cryptology -EUROCRYPT94// Lecture Notes in Computer Science. Springer-Verlag. - 1995. - V. 950. - P. 341-355.

25.Biham E. and Shamir A., Differential Cryptanalysis of the Full 16-round DES// Advances in Cryptology- CRYPTO92// Lecture Notes in Computer Science. Springer-Verlag. - 1993. - V. 740. - P. 487-496.

26.Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems (ex-tended abstract)// Advances in Cryptology- CRYPTO90// Lecture Notes in Computer Science. Springer-Verlag. - 1991. - V. 537. - P. 2-21.

27.Biham E., Shamir A. Differential Fault Analysis of Secret Key Cryptosystems // Advances in Cryptology - CRYPTO97 // Lecture Notes in Computer Science. Springer-Verlag. - 1997. - V. 1294. - P. 513-525.

28.Biryukov A., Wagner D. Advanced Slide Attacks // Advances in Cryptology - EUROCRYPT2000 // Lecture Notes in Computer Science. Springer-Verlag. - 2000. - V. 1807. - P. 589-606.

29.Biryukov A., Wagner D. Slide Attacks // Fast Software Encryption, 6th International Workshop // Lecture Notes in Computer Science. Springer-Verlag. - 1999. - V. 1636. - P. 245-259.

30.Burwick C, Coppersmith D., DAvingnon E., Gennaro R., Halevi Sh., Jutla Ch., Matyas Jr.S.M., OConnor L., Peyravian M., Safford D., Zunic N. MARS -a Candidate Cipher for AES // Proc. of 1st Advanced Encryption Standard Candidate Conference, Venture, California, Aug. 20-22, 1998 (#"justify">).

31.Camion P., Carlet C, Charpin P., Sendrier. On Correlation-immune Functions // Advances in Cryptology- CRYPTO91 // Lecture Notes in Computer Science. Springer-Verlag. - 1992. - V. 576. - P. 87-100.

32.Балашов Е.П., Негода В.Н., Пузанков Д.В. и др. Информационные системы: Табличная обработка информации/Под ред. Балашова Н.П. и Смолова В.Б. - Л.: Энергоатомиздат. Ленингр. отд-ние, 1985. - 184 с.

33.Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Электронные цифровые вычислительные машины. - Киев: Вища шк., 1976. - 440 с.

.Виноградов И.М. Основы теории чисел. - Наука, 1981. - 176 с.

35.Краснобаев В.А. Надежностная модель ЭВМ в системе остаточных классов./Электронное моделирование, 1985, №4, с. 44 - 46.

36.Краснобаев В.А. Вариант математической модели надежности ЭВМ в системе остаточных классов/Кибернетика, 1987, №1, с. 25 - 26, 38.

.Пухов Г.Е., Евдокимов В.Ф., Синьков Н.В. Розрядоаналоговые вычислительные системы. - М.: Сов. Радио, 1987. - 254 с.

.Краснобаев В.А., Ирхин В.П. Пример решения обратной задачи оптимального резервирования в системе остаточных классов/Кибернетика, 1990, №13, с. 43 - 44.

.Краснобаев В.А. Надежностный синтез в системе остаточных классов./Кибернетика, 1990, №5, с. 139 - 142.

.Акушский И.Я.. Юдицкий Д.И. Машинная арифметика в остаточных классах. - М.: Сов. Радио, 1968. - 444 с.

.Торгашев В.А. Система остаточных классов и надежность ЭВМ. - М.: Сов. Радио, 1973. - 118 с.

.Долгов А.И. Диагностика устройств, функционирующих в системе остаточных классов. - М.: Радио и связь. 1982. - 64 с.

.А. с. 922731 СССР. Устройство для умножения в системе остаточных классов/В.А. Краснобаев. - Бюл. Изобретений, 1982, №15.

.А. с. 1168934 СССР. Устройство для сложения и вычитания чисел по модулю Р/В.А. Краснобаев и др. - Бюл. Изобретений, 1985, №27.

.А. с. 1247868 СССР. Устройство для сложения и вычитания чисел по модулю Р/В.А. Краснобаев и др. - Бюл. Изобретений, 1986, №28.

.А. с. 999050 СССР. Арифметическое устройство в системе остаточных классов/В.А. Краснобаев А.В. Королев и др. - Бюл. Изобретений, 1983, №7.

.А. с. 1107122 СССР. Арифметическое устройство в системе остаточных классов/В.А. Краснобаев и др. - Бюл. Изобретений, 1984, №29.

.Краснобаев В.А. Искусственный интеллект и система исчисления в остаточных классах/Проблемы бионики. 1987, №39, с. 40 - 46.

.Евстигнеев В.Г. Сведо - Швед В.Н., Краснобаев В.А. Арифметические алгоритмы для q - й системы исчисления/Тем. Сб. Науч. Трудов ХАИ. 1982, №4, с. 165 - 168.

.Евстигнеев В.Г. Сведо-Швед В.Н., Краснобаев В.А. Реализация арифметических операций и помехоустойчивое кодирование в позиционно - остаточной системе исчисления/Радиотехника, 1983, №66, с. 40 - 46.

.Акушский И.Я., Амербаев И.Я., Пак И.Т. Основы машинной арифметики комплексных чисел. - Алма-Ата: Наука, 1970. - 248 с.

.Коляда А.А., Пак И.Т. Модулярные структуры конвейерной обработки информации. - Минск: изд - во Минского университета, 1992. - 256 с.

53.Харченко В.С., Тимонькін Г.М., Сичов В.О., Лисенко І.В. Теорія надійності та живучості елементів і систем літальних комплексів. - Харків: друкарня Харківського військового університету, 1997. - 403 с.

54.Козирь И.Я. Качество и надежность интегральных микросхем. - М.: Высшая школа, 1987.

55.KHERE ALI ABDYLLAH, Яськова К.В., Краснобаєв В.А. Принципи реалізації модульних операцій в модулярній арифметиці // Вісник Харківск. держ. техн. ун-ту с/г-ва. Харків.-2007.-Вип.57.-С.100-104

56.Яськова К.В. Повышение отказоустойчивости информационно-управляющей системы АСУТП сельскохозяйственного производства на основе использование модулярной арифметике // Материалы международного форума молодежи «Молодежь и сельскохозяйственная техника в 21 веке». Харьков.-2007.-С.143

.Краснобаєв В.А., Барсов В.І., Яськова К.В. Відмовостійкі обчислювальні системи на основі модулярної арифметики: концепції, методи та засоби // Радіоелектронні і компютерні системи. - 2007.- №8(27). -С.82-90


ЗМІСТ ПЕРЕЛІК СКОРОЧЕНЬ ВСТУП . ДОСЛІДЖЕННЯ ОСНОВНИХ ВІДМІННОСТЕЙ ФУНКЦІОНУВАННЯ СПЕЦПРОЦЕСОРІВ ОБРОБКИ КРИПТОГРАФІЧНОЇ ІНФОРМАЦІЇ .1 Дослідженн

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ