Область наук:

  • Комп'ютер та інформатика

  • Рік видавництва: 2009


    Журнал: Наукові відомості Бєлгородського державного університету. Серія: Економіка. Інформатика


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

    Текст наукової роботи на тему «Алгоритм стиснення алфавітній інформації з адаптацією для криптосистем»

    ?УДК 004.492

    АЛГОРИТМ стиснення алфавітному ІНФОРМАЦІЇ З адаптацією

    ДЛЯ криптосистем

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

    В.Г. Потьомкін Н.І. Корсунь

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

    e-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

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

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

    Аналізуючи досить довгий, зашифрований текст, можна по частотах появи символів зробити відновлення початкового тексту. При цьому зовсім не обов'язково аналізувати всі букви слів тексту. Решта можна підібрати за змістом, так як природні мови мають великий надмірністю. Для російської мови, наприклад, буква «о» з'являється в 45 разів частіше букви «ф» і в 30 разів частіше букви «е». Відносна частота появи пробілу або розділового знака в російській мові складає 0,174. Дану проблему легко зрозуміти на прикладі наступної алегорії. Маска, приховуючи лик, повністю повторює його анатомічні особливості, але за непрямими ознаками (рис, пропорції) можна без праці ідентифікувати власника.

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

    ,і 1

    Н ь ;; Е

    • В 1 7 л. . |в " . .

    Код симп-мулу про табліце- ^ N811

    Мал. 1. Частота народження символів в текстовому файлі, розміром 10 кбайт

    Як випливає з експерименту, в спектрі чітко простежуються сплески частоти появи певних символів. Самий часто зустрічається символ даного тексту - знак пробілу з кодом 32 в таблиці ДИБІ 1ВМ ср866 [2]. Отже в шифрі символ з такою ж смисловим навантаженням, але іншим значенням буде так само часто зустрічатися. Знаючи алгоритм шифрування, який, як правило, не є секретним, можна без зусиль скласти структуру тексту [1]. Середня частота народження інших символів мають сплеск частоти (рис. 1) - це букви «о», «е», «а», «і», «н», в більшості текстів лежить в одних і тих же діапазонах.

    З цього випливає, що для несанкціонованого доступу є такі переваги:

    1) уявлення про структуру тексту (по розташуванню знаків пробілу);

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

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

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

    Основними технічними характеристиками процесів стиснення є [3]:

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

    2. Швидкість стиснення - час, що витрачається на стиснення деякого обсягу інформації вхідного потоку.

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

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

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

    ходимость оснастити криптосистему складним штучним інтелектом, для проведення аналізу повідомлення і виділення з нього базового сенсу. Для даної задачі основою штучного інтелекту можуть служити алгоритми автореферірованія, наочним прикладом роботи яких може служити функція «Автореферат» текстового процесора Microsoft Word [4].

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

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

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

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

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

    Найкращим підходом до вирішення цієї проблеми має алгоритм RLE [3]. В основу алгоритму RLE (Run-Length Encoding) покладено принцип виявлення повторюваних послідовностей даних і заміни їх простою структурою, в якій вказується код даних та коефіцієнт повторення. Програмні реалізації алгоритму RLE відрізняються простотою, високою швидкістю роботи, внаслідок однопрохідного способу стиснення і декомпресії. Найкращими об'єктами для даного алгоритму є графічні файли, в яких великі одноколірні ділянки зображення кодуються довгими послідовностями однакових байтів [6]. Цей метод також може давати помітний виграш на деяких типах файлів баз даних, що мають таблиці з фіксованою довжиною полів.

    Класична реалізація алгоритму полягає в тому, що здійснюється пошук найменш часто зустрічається байта, називають його префіксом і роблять заміни ланцюжків однакових символів на трійки "префікс, лічильник, значення". Якщо ж цей байт зустрічається у вихідному файлі один або два рази поспіль, то його замінюють на пару "префікс, 1" або "префікс, 2". Залишається одна невикористана пара "префікс, 0", яку можна використовувати як ознака кінця упакованих даних. Наприклад, послідовність АААВВСРЕЕЕЕ кодується (# 3A) (# 2B) (# 1C) (# 1D) (# 4Е), # - знак префікса. Стисла послідовність символів, що повторюються представляється структурою, що складається з трьох елементів: байт-покажчик на префікс, лічильник повторів символів, байт, який зберігає зразок повторюваного символу.

    Одна з найбільш вдалих версій даного алгоритму заснована на тому, що байт, що відповідає за наявності префікса, об'єднується з байтом лічильника символів, що повторюються [3]. У цьому байті старший біт виконує функцію прапора наявності префікса. Якщо значення старшого біта дорівнює одиниці, то даний байт є носієм префікса, а значення решти сім біт - кількість повторень символу не більше 128. Якщо значення старшого біта дорівнює нулю, то префікса немає, і значення байта інтерпретується як число в графічних даних або цифра в текстових. Внаслідок цього для зберігання префікса не потрібно виділяти додатковий байт, що дозволяє підвищити коефіцієнт стиснення інформації, особливо при великій кількості коротких послідовностей повторюваних символів. Ефективність (за коефіцієнтом стиснення) даної версії алгоритму вище, в порівнянні з класичною версією. Пояснюється це тим, що в класичному алгоритмі стиснення стисла послідовність представлена ​​трьома байтами, в даній версії-двома (байт-покажчиком префікса, поєднаний з лічильником і зразок повторюваного символу).

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

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

    Модифікація алгоритму RLE заснована на усуненні протиріччя, що виражається в нераціональному використанні старшого біта кодіровочние байта, що призводить до невиправданого скорочення потужності використовуваного алфавіту. Для усунення цього протиріччя необхідно збільшити потужність алфавіту не зраджуючи розмір кодувальної таблиці. При кодуванні будь-якого текстового документа необхідно щоб кодировочная таблиця містила необхідний мінімум використовуваних символів. До них можна віднести наступні типи: літери великі та малі національного (в даному прикладі російський алфавіт) і латинського алфавітів, цифри, знаки пунктуації та деякі, в разі потреби, допоміжні символи. Якщо брати за основу кодіровочние таблицю ANSI I IBM cp866 [2], то буде потрібно 164 символу. Однак закодувати таку кількість кодів символів сім'ю битами (128 можливих значень) не представляється можливим.

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

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

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

    Байти стислої інформації необхідно інтерпретувати за такими правилами:

    1. Значення байта, старший біт якого дорівнює одиниці - інтерпретується як:

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

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

    2. Значення байта, старший біт якого дорівнює нулю - інтерпретується як код символу прийнятої кодувальної таблиці 1.

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

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

    Упакована кодировочная таблиця

    Таблиця 1

    Блок-схема алгоритму, побудована на основі наведених правил, наведена на рис. 2.

    Мал. 2. Блок-схема алгоритму стиснення, де S - текстовий файл довжини R, Si - i-й еліменти файлу S, з - лічильник повторюваних символів, flag - прапор наявності послідовності повторюваної

    символів, F-файл, стислої інформації

    У наведеному алгоритмі в файлі S довжини R зчитуються послідовно символи Si, порівнюються два поруч стоять і при їх збігу встановлюється flag в одиницю. Здійснюється підрахунок символів, що повторюються, по закінченню повтору проводиться запис в файл F префікса зі значенням лічильника повторень і повторюваного символу. Якщо flag приймає значення нуль, то це означає, що символ повторів не має і його слід записувати в файл F без префікса.

    При декомпресії символи обробляються в наступному порядку:

    1) якщо код символу належить діапазону від 196 до 255, то прописна буква зі значенням, зміщеним на 127;

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

    На рис. 3 відображено частотний спектр появи символів у текстовому файлі розміром 10 Кб, порівняння якого з даними, наведеними на рис. 1, показує що запропонований алгоритм дозволив знизити сплески частоти появи символів в середньому на 20%. Це дає можливість більш ефективного застосування більш потужних алгоритмів стиснення [3, 5].

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

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

    Квдсмднеле в таблиці АНБІ

    Мал. 3. Частота народження символів в текстовому файлі, розміром 10 кбайт, підданий стиску запропонованим алгоритмом

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

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

    література

    1. Основи криптографії [Текст]: Алфьоров А.П., Зубов А.Ю., Кузьмін А.С., Черемуш-кін А.В .; - Геліос АРВ. - 2002. - с. 480.

    2. Лідовскій В. В.Загадочное сімейство [Текст] / Лідовскій В. В .// Компьютерра. - №42. - 2003 г. - с. 2.

    3. Основи стиснення інформації [Текст]: Фомін А.А. Санкт-Петербурзький державний технічний університет, 1998. с. 82.

    4. Молявко А. / Офіційний навчальний курс Microsoft: Microsoft Office Word 2003. Базовий курс [Текст] - М .: Еком. 2005. - 408 с.

    5. Blelloch G. Introduction to Data Compression [Текст] / Blelloch G. // Computer Science Department Carnegie Mellon University, - 2001. - p. 156.

    6. Ватолин Д.С. / Алгоритми стиснення зображень [Текст]: - Видавничий відділ факультету Обчислювальної Математики і Кібернетики МГУ ім. М.В.Ломоносова. 1999 г. - 76 з.

    ALGORITHM OF COMPRESSION OF THE ALPHABETIC INFORMATION WITH ADAPTATION

    FOR CRYPTOSYSTEMS

    V. G. POTEMKIN N.I. KORSUNOV

    Belgorod State Technological University

    e-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    In this article we propose an efficient compression algorithm to protect against the interception of information transmitted. Analysis algorithms to compress the information, and identified their shortcomings, in that in the process of compression, they do not adequately perceive the sequence of repeated characters, have insufficient capacity to alphabets. To address the shortcomings, a new system of compression, for which the algorithm is given. A comparison of the proposed algorithm with a well-known.

    Key words: information, reliability, compression, unauthorized access, redundancy, coding.


    Ключові слова: інформація /криптостойкость /стиснення /несанкціонований доступ /надмірність /кодування

    Завантажити оригінал статті:

    Завантажити