Abstract

The article deals with the problems of the encryption and data compression. The encryption and data compression are tie together. In booth case frequency distribution of characters in output data is changed. Data compression before the encryption troubles cryptanalysis (decryption) of ciphertext. The analysis of algorithms data compression and encryption shows, that at the same time with data compression possible the data encryption. It is allows to decrease computational expenses and increase the security of the cryptosystem.

1. Вступ

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

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

Наукова криптологія (cryptos – таємний, logos – слово) бере початок з роботи К.Шеннона “Теорія зв’язку в секретних системах” (1949р.), в якій було показано, що для деякого випадкового шифру кількість знаків шифротексту, отримавши який криптоаналітик при необхідних обчислювальних ресурсах зможе відновити ключ (тобто розкрити шифр), становить:

, (1)

де H(Z) – ентропія ключа, r – надлишковість відкритого тексту, N-обсяг алфавіту.

З виразу (1) видно, що зниження надлишковості (стиснення даних) може значно збільшити криптостійкість навіть для коротких ключів [1].

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

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

2. Шифрування інформації

Розглянемо деякі традиційні методи криптографії.

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

- моноалфавітну підстановку

- багатоалфавітну підстановку.

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

, (2) 

де - десятковий коефіціент, - коефіціент зсуву, - розмір алфавіту, - символ початкового тексту [2].

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

Ці недоліки можна зменшити за рахунок використання багатоалфавітної підстановки. При n-алфавітній підстановці знак m1 з початкового повідомлення замінюється знаком з алфавіту B1, m2 – відповідно з алфавіту B2, …, mn – знаком з алфавіту Bn, mn+1 – знову з алфавіту B1 і т.д. Ефект використання багатоалфавітної підстановки полягає в тому, що забезпечується маскування природної частотної статистики початкової мови повідомлення, оскільки конкретний знак з алфавіту А може бути перетворений в декілька різних знаків шифрувального алфавіту В.

Знаки початкового тексту можливо також переставляти у відповідності з деяким правилом. Недолік перестановок той самий, що і моноалфавітної підстановки.

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

Значно більшу криптостійкість забезпечує шифрування з використанням генератора псевдовипадкових чисел (ПВЧ). Найбільш широке застосування знаходять лінійні конгруентні генератори ПВЧ. Цей генератор формує послідовність псевдовипадкових чисел Т1, Т2,…, Тm, використовуючи співвідношення: 

, (3) 

де і - константи, Т0 – початкова величина, вибрана в якості породжуючого числа.

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

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

Такі відомі схеми кодування як DES, RSA [3], алгоритм криптографічного перетворення згідно ГОСТ 28147-89 [7] повністю або частково являються комбінацією методів, розглянутих вище (не розглядаються в даній роботі).

3.Одночасне стиснення і шифрування даних

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

Розглянемо з цієї точки зору деякі методи стиснення інформації.

Достатньо простий і ефективний метод стиснення даних з невідомим розподілом частот, відомий як кодування за ступенем новизни, був відкритий у 1980 р. Рябко.

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

=ABCDDAAACAB

в алфавіті АL={A,B,C,D}. При появі в слові чергової букви “а” по лінії зв’язку передається монотонний код номера позиції, яку займає в даний момент символ “а” в списку, а символ “а” 

Таблиця 1. Кодування за ступенем новизни

Вхід | Вихід