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

О. Я. Матов, В. С. Василенко

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

66

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

завадостійкий код умовний лишки

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

О. Я. Матов

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

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

Вступ

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

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

Задачі захисту цілісності інформаційних об'єктів телекомунікаційних мереж

Наслідком природних впливів у каналах телекомунікаційних мереж (ТКМ) є зменшення співвідношення енергетик сигнал/шум (сигнал/завада). Це відношення визначає вірність інформації, визначену, наприклад, через імовірність помилок двійкових символів (біт) Рпом, а також інтенсивність цих помилок. Слід підкреслити, що інтенсивність природних дій у каналах деяких ТКМ, яка визначається, в основному, цим співвідношенням, є настільки значною, що лише за їх рахунок, без урахування можливостей зловмисників по створенню загроз, наприклад, різного роду завад, середня вірогідність помилки двійкового символу (біта) Рпом для телефонних кабельних каналів ТКМ складає від 1,29•10-4 до 2•10-3; для радіорелейних телефонних -- від 2,66•10-4 до 7,3•10-4 відповідно. Відомо також, що із часом такі помилки групуються в пакети двох видів: «короткі» -- тривалістю 2...10 мс і «довгі» -- тривалістю 100…200 мс. «Короткі» пакети з'являються частіше, але більшість зафіксованих помилок зосереджено в «довгих» групах (7590 %).

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

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

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

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

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

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

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

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

-- завади, викликані зовнішніми джерелами й атмосферними явищами.

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

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

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

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

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

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

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

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

Останній зі способів (механізмів) забезпечення цілісності інформаційних об'єктів -- із застосуванням завадостійких корегуючих кодів наразі знайшов широке застосування в стандартах радіозв'язку, у тому числі мобільного, стільникового зв'язку. Він не потребує зворотного каналу й забезпечує, як правило, прийнятне значення часу затримки передавання інформаційних об'єктів. Тому, чи не єдиною проблемою в цих та інших ТКМ із використанням телефонних кабельних та радіоканалів є проблема забезпечення цілісності інформаційних об'єктів в умовах впливу навіть природних (не говорячи вже про штучні, навмисні завади) пакетних викривлень, як «коротких» (тривалістю 2...10 мс) так і особливо «довгих» (тривалістю 100…200 мс). Це є особливо актуальним і для вже згаданих систем стільникового зв'язку. Наприклад, у стандартах CDMA базовий цифровий потік розбивається на пакети тривалістю по 20 мс і подається на згорточний кодер с половинною швидкістю [2]. При цьому тривалість пакета викривлень може бути порівняною чи, навіть, значно перевищувати тривалість інформаційного пакета, що може суттєво вплинути на результативність процедур інформаційного обміну.

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

Узагальнений завадостійкий код умовних лишків

Під узагальненими розумітимемо коди, призначені для виявлення (виявлення й виправлення) пакетних викривлень, у яких використовуються алгоритми кодування й декодування, аналогічні відповідним алгоритмам двійкових кодів, але по відношенню до b-розрядних, узагальнених символів (УС).

У цих кодах початкова двійкова кодова послідовність -- базове кодове слово І1, І2, …, Іn розбивається на n = k/b узагальнених b-розрядних символів -- груп двійкових розрядів з розрядністю b, в яких передбачається виявлення та виправлення викривлень:

І1………Іb, Іb+1…………І2b,…, Іm-b+1 ……Іn.

1-й УС 2-й УС n-й УС

Двійкові символи, що входять до однієї b-розрядної групи, розглядаються як b-значний УС, який може приймати будь-яке із s значень від 0 до s - 1, де s = 2b.

Код умовних лишків (лишків умовних код -- ЛУ-код) є одним із прикладів узагальнених кодів [3]. Теоретичною основою ЛУ-коду є теорія лишкових класів. Із цієї теорії [4] відомо, що будь-яке число можна представити у вигляді набору лишків від розподілу цього числа на набір взаємно простих чисел, які мають назву основ системи числення, -- pi, де і = 1, 2, …, n, n -- кількість таких основ. Вибір величини n здійснюється з умови, яка викладена нижче. Тоді:

А = б1, б2, …, бn, (1)

де б = А - [А/pi]·pi, а позначка [А/pi] означає операцію розрахунку цілої частини від дробового числа А/pi. При цьому між числом А та його уявленням (1) існує взаємна однозначна відповідність якщо:

.

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

Чудовою властивістю системи лишкових класів (СЛК) є те, що до неї легко вводяться властивості виявлення та виправлення викривлень. Відомо, що якщо ввести ще одну, контрольну, основу рk, то уявлення А в розширеному діапазоні R = P·рk, у вигляді

А = б1, б2, …, бn, бk, (2)

де бk -- лишок по основі рk, має чудову для побудови корегуючих кодів властивість: при pk > pn будь-яке викривлення в одному з лишків бі може бути знайденим, а при pk > 2·pn·pn-1, де pn, pn-1 -- найбільші з основ, може бути й виправленим. Це означає, що при представленні чисел у вигляді (2) створюється завадостійкий код із можливостями або виявлення викривлень, або їхньої корекції.

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

Нехай існує код деякого числа А, представленого в будь-якій системі числення, зокрема, позиційній, наприклад, двійковій. Для визначеності, нехай це число А представлено послідовністю з нулів і одиниць. Розіб'ємо цю послідовність певним (у загальному випадку довільним) чином на n груп, як і для решти узагальнених кодів.

Як показано вище, код кожного i-го УС слід розглядати як s-значний УС бi, який може приймати будь-яке з s значень від 0 до s 1, де s = 2b. Будемо умовно вважати цей код лишком деякого умовного числа А по основі pi. Оскільки величина бi, як елемент початкового числа

0 ? бi ? s 1,

а як лишок від ділення А на pi

0 ? бi ? pi,

то для представлення коду будь-якої групи у вигляді лишку по основі pi необхідно, щоб виконувалася умова:

pi > s - 1,

інакше в групу з b розрядів може бути записаним код бі ? pi, що в лишкових класах не припустимо.

При такому підході будь-які комбінації початкового коду числа А «вписуються» в систему числення з основами pi (і = 1, 2,...). Якщо розширити систему основ на контрольну pk і для одержаного набору умовних лишків бi (і = 1, 2,...) розрахувати умовний лишок бk, то на одержане умовне число

А = б1, б2, …, бn, бk (3)

розповсюджуються всі можливості СЛК по виявленню й виправленню викривлень, тобто одержаний код (3) має всі властивості коду (2), але останній код може бути отриманим для будь-якої двійкової послідовності, а не тільки по відношенню до чисел у лишкових класах. Відзначимо, що таким чином усунений перший недолік коду (2).

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

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

Такий код дозволяє знаходити й виправляти b-розрядні пакети викривлень, згруповані в межах будь-якого з n УС, і потребує при цьому надмірності біля

r ? 2b + 1 двійкових розрядів (оскільки , . У конкретних випадках ця надмірність може відхилятися в ту або іншу сторону, що залежить також від алгоритмів кодування-декодування.

Виявлення порушення цілісності із застосуванням коду умовних лишків

Нагадаємо, що ЛУ-код відноситься до узагальнених кодів, у яких усі операції з кодування-декодування здійснюються не над окремими двійковими розрядами, а над їхніми групами -- узагальненими символами. В основі ЛУ-коду лежать властивості системи лишкових класів, тому в ньому принципово можуть бути використані відомі [4] алгоритми кодування-декодування. В основі цих алгоритмів лежить той факт, що будь-яке викривлення в одній із груп розрядів бі переводить початкове число з робочого діапазону [0, P = ) до діапазону [P, R = q·Р), тобто приводить до збільшення початкового числа А < Р на деяку величину li·Ri. Тут q -- контрольна, надлишкова основа така, що її значення перевищує значення будь-якої з основ, що утворюють робочий діапазон Р, тобто q > pi, і = 1, 2, …, n [3]; li і Ri -- цілі числа (Ri = R/pi); Ri -- основні константи такої системи числення. Дійсно, якщо вихідне число

А = б1, б2, …, бi,…,бn, бk

є викривленим по основі pi і має вигляд:

А? = б1, б2, …, i,…,бn, бk,

де

= {бi + Дбi } (mod pi),

то це в системі числення в лишкових класах є еквівалентним наступному перетворенню:

А? = (б1, б2, …, {бi + Дбi } (mod pi),…,бn1, бk) =

= (б1, б2, …, бi,…,бn, бk) + (0, 0, …, Дбi, …, 0, 0).

При цьому величина ДА викривлення перевищує величину робочого діапазону Р:

ДА = (0, 0, …, Дбi, …, 0, 0) > Р.

Це пов'язано з тим, що тільки число виду ДА = li·Ri = li·R/pi має всі лишки, окрім лишка по основі pi такими, що дорівнюють нулю. Але величина

R/pi > R/q із тієї причини, що q > pi, і тоді, навіть при li = 1, величина викривлення ДА = li·Ri > P = R/q.

Відтак, сума А? = А + ДА > Р, тобто викривлене число (рис. 1) виходить за межі робочого діапазону Р і попадає до діапазону [P, R), що може бути певним чином виявленим.

Рис. 1. До виходу викривленого числа за межі робочого діапазону

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

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

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

На першому етапі алгоритму (при формуванні ознаки цілісності, контрольної ознаки чи кодуванні) виконується послідовність операцій (процедура нулевізації), яка зводиться до того, що по першим n лишкам бi (i = 1, 2, …, n) числа

А? = (б1, б2, …, {бi + Дбi } (mod pi),…, бn, бk)

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

t1 = (б1, , ,…, ,),

t2 = (0, (б2 - ) (mod p2), ,…, , ),

t3 = (0, 0, (б3 - - ) (mod p3), ,…, ,),

…………………………………………………………..

tn = (0, 0, 0, …,(бn - ) (mod pn), ).

Звернемо увагу на те, що кожне з таких мінімальних чисел може бути представленим у вигляді:

ti = vі•.

З урахуванням того, що в системі лишкових класів

ti (mod pі) = = {бі } (mod pі) = vі•(mod pі)

величину vі можна визначити як

vі = {/}(mod pі) = {(бі )/} (mod pі),

для всіх лишків бі з номерами і > 1, а для першого з лишків б1 значення v1 = 1.

Сума цих чисел Т = має наступні дві властивості [4]. По-перше, лишки цієї суми по всім основам, окрім рk, завжди дорівнюють лишкам вихідного числа А. По-друге, величина цієї суми завжди є меншою ніж величина робочого діапазону: Т < Р, тобто величина Т лежить у межах робочого діапазону й для не викривлених чисел Т = А.

Таким чином, процес отримання величини Т = А є процесом кодування вихідного числа ЛУ-кодом, при чому значення А залежить лише від цього вихідного числа, і не залежить від невідомої при кодуванні величини лишку по контрольній основі рk. Цей лишок бk (контрольна ознака, ознака цілісності, що розшукується) дорівнює при цьому сумі за модулем рk проміжних величин (і = 1, 2, ..., n) тобто:

бk = Т (mod рk) = () (mod рk).

На другому етапі алгоритму (контроль цілісності чи декодування) виконується віднімання із числа А? величини T, що призводить до того, що отримана різниця

Г = А? T = k·Р

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

г = (бk - (Т mod рk )) (mod рk) = (k·Р) (mod рk).

Величина Г при запису в лишкових класах має вигляд:

г = ( А? T) (mod рk)) = (0, 0, …, 0, …0, k·Р (mod рk)),

де k = 0, 1, 2, …, рk - 1.

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

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

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

Приклад 1. Нехай необхідно сформувати ознаку цілісності (контрольну ознаку) -- закодувати з використанням алгоритму нулевізації вихідний код 110110, вважаючи, що можлива довжина пакета викривлень b = 2. Тоді можливе розбиття вихідного коду на три (n = 3) дворозрядні групи б1 = 11, б2 = 01, б3 = 10, s = 4, а в якості умовних основ можна вибрати р1 = 4, р2 = 5, р3 = 7. При цьому значення контрольної основи (рk > 2·рn·рn-1 = 2·5·7 = 70) можна вибрати величиною рk = 71, що потребує для свого відображення семи розрядів. Визначимо також основні константи цієї системи числення для обраної сукупності основ: R1 = 2485; R2 =

= 2088; R3 = 1420; R4 = Р = 140; m1 = 1; m2 = 2; m3 = 6; m4 = 35.

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

А = 11.01.10.0000000.

При цьому, перше мінімальне число t1 повинно мати лишок по першій основі, що дорівнює 11(2) = 3(10). Таким числом є t1 = 3, або при представленні в СЛК із вибраними основами: t1 = 11.11.11.0000011.

Друге мінімальне число t2 повинно мати лишок по першій основі, який дорівнює нулю, а по другій:

((б2 - ) (mod p2) = (1 - 3) (mod 5) = 11(2).

Мінімальним числом, яке має такі лишки по першій і другій основам, є

t2 = 8, тобто: t2 = 00.11.01.0001000.

Трете мінімальне число t3 повинно мати нульові лишки по першим двом основам, а по третій:

((б3 - - ) (mod p3) = (2 - 3 ? 1) (mod 7) = 5 = 101(2).

Мінімальним числом, що має такі лишки, є t3 = 40, тобто: t3 =

= 00.00.101.0101000.

Тоді сума цих чисел Т = дорівнює 51, тобто:

Т = 11.01.10.0110011.

Код Т і є результатом кодування. У цьому коді лишок по контрольній основі г = 0110011 і є шуканим значенням ознаки цілісності (контрольної ознаки).

Приклад 2. Нехай треба здійснити контроль цілісності (декодувати) з використанням алгоритму нулевізації для умов наведеного вище прикладу 1 код А? = 11.01.01.0110011, у якому викривлена третя пара розрядів. Як і раніше

t1 = 011.011.011.0000011, t2 = 000.011.001.0001000.

Для третього мінімального числа t3:

((б3 - - ) (mod p3) = (1 - 3 - 1) (mod 7) = 4 = 100(2).

Мінімальним числом, що має такі лишки, є t3 = 60, тобто: t3 =

= 000.000.100.0111100.

При цьому:

Т = =71,

тобто оскільки Т (mod 71) = 0, тоді Т = 11.01.01.0000000, і

г = Г (mod рk) = (бk - (Т mod рk )) (mod рk) = (0110011 0000000) (mod 71) = 51.

Оскільки ознака цілісності (контрольна ознака) є відмінною від нуля -- г ? 0, то робимо висновок про виявлення порушення цілісності, чи про наявність викривлення в об'єкті, що декодується.

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

Відомо, що [4] при рk > 2·рn·pn-1 є взаємно однозначна відповідність між величиною викривлення Дбi і величиною г, що дає змогу, отримавши г, визначити місце та величину викривлення, тобто здійснити її виправлення.

Для виявлення можливостей побудови алгоритму контролю та поновлення цілісності з використанням процедури нулевізації нагадаємо, що на числовій осі величина викривлення liRi відображається точкою в деякому піддіапазоні «контрольного» діапазону [(Р + 1), R).

Відповідно, процес викривлення початкового числа А відобразиться переміщенням точки А з робочого діапазону [0, P) до деякого іншого піддіапазону. Звернемо увагу на те, що в залежності від величини початкового числа (рис. 2), викривлене число (А1 чи А2) може попасти до одного із суміжних діапазонів із номерами k або (k 1).

Рис. 2. Ілюстрація процесу нулевізації

Зокрема, при

А = А1 ? kР liRi,

це буде (в уже прийнятих позначеннях) діапазон [(k 1)Р, kР), тобто діапазон із номером (k 1), а при

А = А2 > kР liRi

це буде діапазон із номером k.

Унаслідок операції нулевізації із числа А?, яке контролюється, віднімаються відповідно числа Т = А? (k 1)Р < P, чи Т = А? kР < P. При цьому по контрольній основі q отримується результат г такий, що відповідає лівій межі (див. рис. 2) піддіапазону [(k 1)Р, kР), тобто величині (k 1)Р, або ж такий, що відповідає лівій межі піддіапазону [kР, (k + 1)Р), а саме величині kР.

Тобто маємо:

г = {kР}q, або г = {(k 1)Р}q,

звідки, за правилами СЛК, отримаємо:

k = {г/{Р}q}q, (4а)

чи

(k 1) = {г/{Р}q}q. (4б)

Таким чином, використовуючи вирази (4а), (4б) завжди можна визначити номер того діапазону -- число k, у який потрапили викривлене число та результат нулевізації.

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

Оскільки подальші міркування певним чином залежать від співвідношення величин kР та liRi, розглянемо два наступних випадки.

У першому випадку, коли kР > liRi, значення Ri, яке характеризує величину й місце викривлення, можна визначити з очевидної нерівності:

kР [kР/Ri]Ri < Р. (5)

Підставимо в (5) замість Ri його значення у вигляді:

Ri = Рq/pі.

Тоді:

kР [kР/ Ri]Ri = kР [kРpі / Рq] Рq/ pі = kР [kpі /q]qР / pі < Р.

Розділивши обидві частини правої частини останньої нерівності на величину Р, отримаємо:

k [kpі /q]q/pі < 1.

Після множення обох частин останньої нерівності на величину pі, одержимо:

kpі [kpі /q] q < pі,(6)

або

{kpі}q < pі. (7)

Звернемо увагу на те, що в (5), (6) вирази у квадратних дужках є не що інше як величина li, оскільки:

[kР/ Ri] = [kpі /q] = li. (8)

Вирази (5) та еквівалентні їм вирази (6), (7) утворюють системи нерівностей по n нерівностей у кожній (величина і може приймати значення і = 1, 2, …, n), у яких справедливим є лише одна нерівність для того номера і та того значення основи pі, по яким має місце викривлення.

Таким чином, унаслідок розв'язання систем нерівностей (6), (7) щодо змінної pі, місце викривлення стає виявленим. Для визначення ж його величини проаналізуємо величини Т = А? kР, чи Т = А? (k 1)Р, які формуються по всім лишкам окрім лишку по контрольній основі в ході операції нулевізації числа, яке контролюється.

Як видно з рис. 2, величина сформованого в ході нулевізації числа Т є меншою вихідного числа А2 на величину (kР liRi), тобто:

Т = А? kР = А2 (kР liRi) < А2, (9)

та

Д = (kР liRi),

а величина скорегованого числа повинна визначатися як:

А2 = Т + (kР liRi).

Тобто величина скорегованого значення лишку:

= {+ Д) = { Т + (kР liRi)}mod pi = { {liRi}mod pi}mod pi,

або з урахуванням (8):

= { {[kpі /q]Ri}mod pi}mod pi. (10)

Приклад 3. Нехай у СЛК із основами 2, 3, 5, 17 вихідне число 1810 = 0, 0, 3, 1 внаслідок викривлення перетворилося на 0, 0, 0, 1 = 12010.

Результат нулевізації має значення:

Г = 0, 0, 0, 1, г = 1,

звідки

k = {г/{Р}q}q = {1/13}17 = (1 + 317)/13 = 52/13 = 4.

Пошук місця викривлення дає:

{kpі}q < pі,

для k = 4:

{45}17 < 5,

тобто виявлене викривлення по основі p3.

Розрахунок скорегованого лишку по основі p3:

= {0 {[20 /17]42}5}5 = 5 2 = 3.

Видно, що корекція викривлення здійснена правильно.

У другому випадку, коли результат нулевізації -- число (k 1)Р (див. рис. 2) є меншим за величину викривлення liRi, величина різниці за виразом (6)

kpі [kpі /q]q < pі

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

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

{kpі}q < pі

слід скористатися системою нерівностей:

{q {kpі}q}q < pі. (11)

У разі вірності однієї із цих нерівностей, правомочним є висновок про те, що

г = {(k 1)Р}q,

а отже

k = {г/{Р}q}q +1. (12)

Як видно з рис. 2, у цьому разі величина викривлення liRi > (k 1)Р. Тоді величина сформованого в ході нулевізації числа Т є більшою вихідного числа А2 на величину [liRi (k 1)Р], тобто:

Т = А? (k 1)Р = А1 + [liRi (k 1)Р] < А1. (13)

Останній вираз може бути представленим у вигляді:

Т = А? kР = А1 [(k 1)Р liRi].

Неважко помітити, що вирази (9) та (13) є тотожними, якщо вважати, що номер діапазону в обох випадках має значення k. І, хоча значення викривлення при цьому

ДА? = (kР liRi),

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

А1 = Т + ((k 1)Р liRi).

Тобто скореговане значення символу обчислюється як:

= {+ Д) = {Т + ((k 1)Р liRi)}mod pi = { {liRi}mod pi}mod pi,

або з урахуванням (8) та згідно з виразом (10) отримаємо:

= { {[kpі /q]Ri}mod pi}mod pi.

Приклад 4. Нехай у СЛК із основами 2, 3, 5, 17 вихідне число 010 = 0, 0, 0, 0 внаслідок викривлення перетворилося на 0, 0, 2, 0 = 10210.

Результат нулевізації дає:

Г = 0, 0, 0, 5, г = 5,

звідки

k = {г/{Р}q}q = {5/13}17 = (5 + 217)/13 = 39/13 = 3.

Пошук місця викривлення дає:

{kpі}q < pі,

для k = 3:

{35}17 = 15 > 5,

а величина {q {kpі}q}q при (k 1) = 3 має значення, яке є меншим величини основи p3: 17 5 = 2 < 5, тобто, як і в попередньому прикладі, виявленим є викривлення по основі p3, але з урахуванням (12) при (k 1) = 3, чи при k = 4.

Розрахунок скорегованого лишку по основі p3:

= {2 {[20 /17]42}mod 5}mod 5 = 2 2 = 0.

Видно, що корекція викривлення здійснена правильно.

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

1) здійснення нулевізації прийнятого (зчитаного із запам'ятовуючого пристрою) інформаційного об'єкта з визначенням величин г та k;

2) перевірки для кожної з основ pі справедливості хоча б однієї з нерівностей:

{kpі}q < pі,

Чи

{q {kpі}q}q < pі,

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

3) здійснення корекції визначеного викривлення:

= { {[kpі /q]Ri}mod pi}mod pi.

Приклад 5. Нехай для умов прикладів 1, 2 потрібно декодувати з використанням останнього алгоритму код числа А = 51 = 11.01.10.0110011, у якому викривлена третя пара розрядів так, що = 11.01.01.0110011. Врахуємо, що перша операція вже виконана (приклад 2), і отримані наступні результати: г = 51 та k = 10, а також те, що R1 = 2485; R2 = 2088; R3 = 1420; R4 = Р = 140, m1 = 1; m2 = 2; m3 = 6; m4 = 35 (рис. 3).



Рис. 3. Ілюстрація процесів нулевізації для прикладів 5, 6

Тоді друга операція щодо перевірки для кожної з основ pі справедливості хоча б однієї з нерівностей:

{kpі}q < pі,

чи

{q {kpі}q}q < pі,

зведеться до наступного.

Для першої з основ p1 = 4:

{kpі}q = {104}71 = 40 < pі = 4 -- нерівність не є справедливою;

{q {kpі}q}q = {71 40}71 = 31< 4 -- нерівність не є справедливою.

Для другої з основ p2 = 5:

{kpі}q = {105}71 = 50 < 5 -- нерівність не є справедливою;

{q {kpі}q}q = {71 50}71 = 21< 5, -- нерівність не є справедливою.

Для третьої з основ p3 = 7:

{kpі}q = {107}71 = {70}71 < 7 -- нерівність не є справедливою;

{q {kpі}q}q = {71 70}71 = 1 < 7 -- нерівність є справедливою.

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

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

= { {[kpі /q]Ri}mod pi}mod pi = {1 {[117 /71]1420}7}7 =

= {1 {[1,084]1420}7}7 = {1 6}7 = 210 = 102.

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

Приклад 6. Нехай для умов прикладу 5 потрібно декодувати з використанням останнього алгоритму код числа А = 130 = 10.00.100.0111011, у якому викривлена третя пара розрядів так, що = 10.00.11.0110001. Неважко впевнитися в тому, що результатом першої операції є наступні результати: г = 14 та k = 11.

Тоді друга операція щодо перевірки для кожної з основ pі справедливості хоча б однієї з нерівностей:

{kpі}q < pі,

чи

{q {kpі}q}q < pі,

зведеться до наступного.

Для першої з основ p1 = 4:

{kpі}q = {114}71 = 44 < pі = 4 -- нерівність не є справедливою;

{q {kpі}q}q = {71 44}71 = 27 < 4 -- нерівність не є справедливою.

Для другої з основ p2 = 5:

{kpі}q = {115}71 = 55 < 5 -- нерівність не є справедливою;

{q {kpі}q}q = {71 55}71 = 16 < 5 -- нерівність не є справедливою.

Для третьої з основ p3 = 7:

{kpі}q = {117}71 = 6 < 7і -- нерівність є справедливою.

Оскільки справедливим є перша з нерівностей, попередньо обраховане значення k = 11 є правильним.

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

= { {[kpі /q]Ri}mod pi}mod pi = {3 {[117 /71]1420}7}7 =

= {3 {[1,084]1420}7}7 = {3 6}7 = 410 = 1002.

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

Перевагами алгоритму нулевізації є:

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

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

Недоліками цього алгоритму є:

1) обчислення величини T здійснюється послідовно, оскільки значення наступної величини tі може бути визначеним лише при відомих попередніх tі (і = 1, 2, …, і - 1), що виключає можливість розпаралелювання процесу. За рахунок цього слід очікувати меншої швидкодії цього алгоритму порівняно з попереднім;

2) достатньо велика розрядність мінімальних чисел tі. Якщо вважати, що кодуваннюдекодуванню підлягають числа (блоки), які складаються з n лишків по b розрядів кожен, то перше мінімальне число потребує N = nb розрядів, друге --

(N ? b) = b(n 1),…, i-е -- (N ? (і ? 1)b) = b(n і + 1), … розрядів, що потребує наявності запам'ятовуючих пристроїв з відповідною ємністю.

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

Література

1. НД ТЗІ 2.5-005-99 «Класифікація автоматизованих систем і стандартні функціональні профілі захищеності оброблюваної інформації від несанкціонованого доступу».

2. Дубровский В.В. CDMA -- взгляд глазами профессионала. -- mailto:v_dubrovskii@mail.ru.

3. Василенко В.С., Будько М.М., Короленко М.П. Механізми контролю цілісності інформації та її поновлення // Правове, нормативне та метрологічне забезпечення Системи захисту інформації в Україні. -- К.: НТУУ «КПІ». -- 2000. -- С. 130-139.

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

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