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

Реферат: UA 67988 U UA 67988 U 5 10 15 20 25 30 35 40 Запропонована корисна модель може бути використана в сучасних інформаційнокомунікаційних системах та мережах з метою забезпечення цілісності та достовірності інформаційного потоку даних. Відомий спосіб забезпечення цілісності інформації на базі завадостійкого коду Хеммінга [1]. В цьому коді для формування контрольних ознак використовується процедура, яка є залежною лише від обраної довжини базового кодового слова і не залежить від інших умов. Недоліком такого способу є простота модифікації інформації, яка циркулює в інформаційно-комунікаційних системах та мережах, з наступним формуванням відповідної контрольної ознаки. В наслідок цього будь-які модифікації таким кодом не виявляються. Відомі також способи забезпечення цілісності інформації на базі циклічних кодів [1-2]. В таких кодах є досить обмежена можливість забезпечення прихованості констант для обрахування контрольних ознак. Така можливість полягає у незначній кількості варіацій утворюючими поліномами для формування контрольних ознак. В наслідок цього модифікації інформаційних об'єктів можуть бути виявленими із вкрай низькою імовірністю. Метою даного способу є використання механізму формування контрольних ознак, які є стійкими щодо несанкціонованої модифікації інформаційних об'єктів. Для досягнення мети поставлена задача розроблення такого завадостійкого коду, в якому для формування контрольних ознак використовується певна множина змінних констант і який може забезпечити необхідну цілісність інформації в умовах її навмисної чи ненавмисної модифікації. Поставлена задача вирішується тим, що в запропонованому коді застосовані можливості теорії литкових класів по відношенню до інформації, наданої у вигляді кодів незалежно від систем числення, а також за рахунок застосування при формуванні контрольних ознак на базі теорії лишкових класів множини основ, які можуть бути використані як секретні елементи і забезпечувати за рахунок цього формування контрольних ознак, які є стійкими до розкриття. Технічний результат, який може бути отриманий при створенні даної корисної моделі полягає в тому, що підвищується достовірність отриманої інформації за умов виявлення та виправлення помилок, зменшення ймовірності виникнення помилок в результаті природних та штучних завад, а також стійкості цієї інформації до несанкціонованої модифікації. Спотворення інформації, тобто порушення її цілісності, можливі на будь-якому етапі її циркуляції у обчислювальних мережах: при зберіганні, передачі або обробці. Забезпечення цілісності інформаційних об'єктів в сучасних інформаційних системах можливе із застосуванням завадостійких корегуючих кодів, що знайшло широке застосування в протоколах передачі даних. Розглядається можливість збільшення тривалості інформаційних пакетів із одночасним застосуванням перемежування потрібної глибини та завадостійких корегуючих кодів, які були б спроможними забезпечити виявлення та виправлення пакетів спотворень значної тривалості. Як один із таких кодів пропонуються узагальнений завадостійкий корегуючий код на базі теорії лишкових класів - код умовних лишків [3-5]. В системі лишкових класів будь-яке число представляють у вигляді набору лишків від розподілу цього числа на набір взаємно простих чисел, які мають назву основ системи числення - pi де i=1, 2,…, n, n - кількість таких основ. Вибір величини n здійснюють з умови, яка викладена нижче. Тоді А = 1, 2,…, n, 45 (1) де  = А-[А/рi] pi, a позначка [А/рi] означає операцію розрахунку цілої частини від дробового числа А/рi. При цьому між числом А і його уявленням (1) існує взаємна однозначна відповідність, якщо n A  P  П pi , i 1 50 55 де Р - діапазон представлення або робочий діапазон чисел. Величину i представляють групою двійкових розрядів, кількість яких не перевищує розрядності відповідної основи pi. Основною властивістю системи лишкових класів (СЛК) є те, що вона дозволяє ефективно виявляти і виправляти спотворення в групах двійкових розрядів - в узагальнених символах. Відомо, що якщо ввести ще одну, надлишкову, основу рk то уявлення А в розширеному діапазоні R = Р·рk у вигляді А = 1, 2,…,n, k, (2) 1 UA 67988 U 5 10 15 20 25 30 де k - лишок по основі pк, утворює завадостійкий код. При побудові таких завадостійких кодів слід забезпечити наступні умови: при pk > рn будь-яке спотворення в одному з лишків (узагальненому символі) i може бути виявленим, а при pк > 2·рn·рn1, де рn, рn1 - найбільші із основ, може бути і виправленим. Такий код має два недоліки. Перший недолік пов'язаний з тим, що можливі спотворення знаходяться і виправляються (спотворений символ поновлюється) тільки в тому випадку, якщо спотворений лише один з символів i, тобто спотворення повинні бути фіксованими в межах однієї із груп розрядів. Такий недолік є притаманним і будь-якому іншому коду і тому усувається відомими способами - застосуванням перемежування (декореляції) з глибиною не меншою ніж два. Другий недолік пов'язаний з необхідністю роботи з числами в системі числення в залишкових класах. Цей недолік достатньо просто усувається в коді умовних лишків (ЛУ-коді), який вводиться таким чином. Код деякого числа А - базове кодове слово (БКС), представляють в будь-якій системі числення, зокрема позиційній, наприклад двійковій. Розбивають цю послідовності певним (у загальному випадку довільним) чином на n узагальнених символів, як і для решти узагальнених кодів. Код кожного i-го узагальненого символу розглядатимуть як s - значний розряд αi, який може b приймати будь-яке з s значень від 0 до (s-1), де s=2 . Код цього символу вважається лишком деякого умовного числа А по основі pi. Оскільки величина i, як елемент початкового числа 0 ≤ i ≤ s-1, а як лишок від ділення А на рi 0 ≤ i ≤ pi, то для представлення коду будь-якої групи у вигляді лишку по основі pi необхідно, щоб виконувалася умова pi > s-l, інакше в групу із b розрядів може бути записаним код i ≥ рi, що в литкових класах не допустимо. При такому підході будь-які комбінації початкового коду числа А "вписуються" в систему числення з основами рі (і = 1, 2,…). Якщо розширити систему основ на надлишкову основу рk і для одержаного набору умовних лишків i (і = 1, 2,…) розрахувати надлишковий умовний лишок k, то на одержане умовне число А' = 1, 2,…, n, k 35 40 45 (3) розповсюджується усі можливості СЛК по виявленню і виправленню спотворень, тобто одержаний код (3) має всі властивості коду (2), але останній код може бути застосованим для будь-якої двійкової послідовності, а не тільки по відношенню до чисел в литкових класах. Таким чином усунено другий недолік коду (2). ЛУ-код дозволяє знаходити і виправляти b - розрядні пакети спотворень, згруповані в межах будь-якого з n узагальнених символів і потребує при цьому надмірність біля r≈2b+1 двійкових розрядів (оскільки pk≈2рnpn+1, r=[log2pk]+1). В конкретних випадках ця надмірність може відхилятися в ту або іншу сторону, що залежить також від алгоритмів кодування-декодування. Оскільки в основі ЛУ-коду лежать властивості СЛК, то в цьому коді принципово можуть бути використані і відомі алгоритми кодування-декодування. Це є можливим завдяки тому, що спотворення в одній з груп розрядів α i переводить k початкове число з робочого діапазону [0, P  П pi ) в діапазон [Р, R=pk·P), тобто призводить до i 1 50 55 збільшенню початкового числа А' Р, 2 UA 67988 U 5 10 15 20 25 оскільки тільки число виду А = li·Ri=li·R/pi має всі лишки, окрім лишка по основі pi, такими, що дорівнюють нулю. Але А = А = li·Ri > Р = R/pk тобто, навіть при li=1 величина R/pi > R/pk по тій причині, що pk > pi. ~ Відтак, якщо сума A  A'A  P , тобто прийняте число вийшло за межі робочого діапазону Р, попало в діапазон [Р, R) і є спотвореним. В разі ж відсутності спотворень (А = 0) прийняте ~ число A  P , тобто не є спотвореним. Цей факт як раз і надає змогу здійснювати як кодування, тобто формування надлишкових символів так і декодування, тобто виявлення наявності викривлень та можливого їх корегування. При цьому можливість вибору довільної та секретної сукупності основ рі (і = 1, 2,…, n) та рk надає можливості щодо унеможливлення несанкціонованої модифікації інформаційних об'єктів, що циркулюють в телекомунікаційних мережах. Джерела інформації: 1. Жураковський Ю. П. Теорія інформації та кодування/ Ю. П. Жураковський, В. П. Полторак / Навчальний посібник - К.: "Вища школа", 2001-255 с. 2. Сорока Л. С. Основи теорії інформації / Л. С. Сорока / Навчальний посібник -X.: ХНУ ім. В. Н. Каразіна, 2007.-264 с. 3. Василенко B. C. Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об'єктів. Код умовних лишків / B. C. Василенко, О. А. Матов // Реєстрація, зберігання і обробка даних - 2006. - Т. 8, № 3. - С. 48-66. 4. Василенко B. C. Узагальнені завадостійкі коди в задачах забезпечення цілісності інформаційних об'єктів в умовах природних впливів / B. C. Василенко // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні.-2006. - Вип. 2(13)- С. 144-159. 5. Василенко B. C. Узагальнений завадостійкий код умовних лишків в задачах забезпечення цілісності впливів / B. C. Василенко, O. K. Юдін // Радіотехніка. Всеукраїнська міжвідомча науково-технічна збірка. Темат. вип… "Проблеми телекомунікацій". - Харків: ХНУРЕ.,-2007. Вип. 148 - С. 228-233. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 Спосіб забезпечення цілісності інформації на базі завадостійкого коду умовних лишків, що полягає у використанні механізму формування контрольних ознак, що є стійкими щодо несанкціонованої модифікації інформаційних об'єктів, який відрізняється тим, що застосовують множини основ для формування контрольних ознак на базі теорії лишкових класів, які можуть бути використані як таємні елементи і забезпечувати за рахунок цього формування контрольних ознак, які є стійкими до розкриття. Комп’ютерна верстка А. Крижанівський Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3