Современные информационные технологии/4.Информационная безопасность

Д.т.н Юдин А.К., Вадясов К.А.

Национальный Авиационный Университет, Украина

Возможности использования алгоритмов сжатия изображений как основ алгоритмов криптографической защиты

В течение последних 10 лет в рамках компьютерной графики бурно развивается совершенно новая область — алгоритмы сжатия изображений. Появление этой области обусловлено тем, что изображения — это своеобразный тип данных, характеризуемый тремя особенностями:

1. Изображения (как и видео) занимают намного больше места в памяти, чем текст. Так, скромная, не очень качественная иллюстрация на обложке книги размером 500x800 точек, занимает 1.2 Мб — столько же, сколько художественная книга из 400 страниц (60 знаков в строке, 42 строки на странице). В качестве примера можно рассмотреть также, сколько тысяч страниц текста мы сможем поместить на CD-ROM, и как мало там поместится качественных несжатых фотографий. Эта особенность изображений определяет актуальность алгоритмов архивации графики.

2. Второй особенностью изображений является то, что человеческое зрение при анализе изображения оперирует контурами, общим переходом цветов и сравнительно нечувствительно к малым изменениям в изображении. Таким образом, мы можем создать эффективные алгоритмы архивации изображений, в которых декомпрессированное изображение не будет совпадать с оригиналом, однако человек этого не заметит. Данная особенность человеческого зрения позволила создать специальные алгоритмы сжатия, ориентированные только на изображения. Эти алгоритмы обладают очень высокими характеристиками.

3. Мы можем легко заметить, что изображение, в отличие, например, от текста, обладает избыточностью в 2-х измерениях. Т.е. как правило, соседние точки, как по горизонтали, так и по вертикали, в изображении близки по цвету. Кроме того, мы можем использовать подобие между цветовыми плоскостями R, G и B в наших алгоритмах, что дает возможность создать еще более эффективные алгоритмы. Таким образом, при создании алгоритма компрессии графики мы используем особенности структуры изображения.

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

Такое широкое распространение изображений и алгоритмов их сжатия приводит к необходимости создания алгоритмов сжатия изображений, которые могли бы одновременно служить средствами защиты данных изображений и средством идентификации.

Рассмотрим наиболее распространенный алгоритм сжатия JPEG (Joint Photographic Experts Group — объединённая группа экспертов в области фотографии), его основу составляют два алгоритма:

1. Дискретное преобразование Фурье

2. Алгоритм Хаффмана

Для вычисления дискретного преобразования Фурье требуется совершить действий, где - количество пикселей изображения. Современные изображения имеют размер минимум 1024 на 768 пикселей. Следовательно, для восстановления изображения необходимо совершить действий.

Алгоритм Хаффмана обрабатывает каждый двоичный символ изображения. Следовательно, это действий, где - количество пикселей изображения. Тогда для восстановления изображения следует совершить действий.

Следовательно, в случае размера изображения 1024 на 768 пикселей для его полного восстановления необходимо совершить действий. Однако данный алгоритм сжатие никоим образом не способствует защите содержимого изображения, но при этом является криптоустойчивым.

Однако если применить генератор псевдослучайных бит и добавить его в дискретное преобразование Фурье:

Мы получим криптографический алгоритм с длиной ключа равной длине числа генерируемого генератором псевдослучайных бит

где - случайна последовательность бит. Это позволит внести элемент защиты содержимого изображения и метод идентификации, а также увеличит криптоустойчивость в раз. Тогда для восстановления исходного изображения размером 1024 на 768 пикселей необходимо будет совершить действий, при условии обладания ключом .

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

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

Литература:

1. Дж. Миано. Форматы и алгоритмы сжатия изображений в действии. Учеб. Пособ. – М.:Издательство Триумф, 2003 – 336 с.: ил.

2. Ватолин Д.С. Алгоритмы сжатия изображений. Методическое пособие. М.: Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им. М.В.Ломоносова, 1999 — 76 с.

3. Претт У. Цифровая обработка изображений. М.: Мир 1982 – 790 с.