Информатика_Ч1

функции) не существует эффективных алгоритмов. Заметим, что обратная функция может не существовать.

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

В качестве примеров задач, приводящих к односторонним функциям, можно привести следующие.

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

2.Дискретное логарифмирование в конечном простом поле (проблема Диффи-Хелмана). Допустим, задано большое простое число p и пусть g – примитивный элемент поля Галуа GF(p). Тогда для любого a вычислить ga (mod p) просто, а вычислить a по заданным k = ga (mod p) и p оказывается затруднительным.

Криптосистемы с открытым ключом основываются на одностронних функциях-ловушках. При этом открытый ключ определяет конкретную реализацию функции, а секретный ключ дает информацию

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

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

Пример

Пусть абоненты А и В решили наладить секретную переписку с открытым ключом. Тогда каждый из них независимо от другого выбирает два больших простых числа, находит их произведение, находит функцию Эйлера от этого произведения и выбирает случайное число, меньшее этого вычисленного значения. Функция Эйлера φ(p) равна количеству чисел, меньших p и взаимнопростых с p, т. е. не имеющих с числом p общих делителей кроме единицы; при этом если p – простое число, то φ(p) = p – 1.

131

Итак:

A: p1, p2 , rA = p1· p2 , φ(rA), (a, φ(rA)) = 1, 0 < a < φ(rA) B: q1, q2 , rB = q1· q2 , φ(rB), (b, φ(rB)) = 1, 0 < b < φ(rB)

Затем печатается телефонная книга, доступная всем желающим, которая имеет вид:

Абонент	А	В
Открытые ключи	rA, a	rB, b

Здесь rA – произведение двух простых чисел p1, p2, известных только абоненту А; а – открытый ключ, доступный каждому, кто хочет передать сообщение А; rB – произведение двух простых чисел q1, q2, известных только абоненту B; b – открытый ключ, доступный каждому, кто хочет передать сообщение B.

Каждый из абонентов находит свой секретный ключ из сравнений:

A: α: αa ≡ 1(mod φ(rA)),		0 < α < φ(rA)
B: β: βb ≡ 1(mod φ(rB)),		0 < β < φ(rB)
Получаем следующую таблицу ключей:
Абонент	Открытые ключи		Секретные ключи
А		rA, a	α
В		rB, b	β

Пусть абонент А решает послать сообщение m абоненту В:

А: m → B и пусть 0 < m < rB, иначе текст делят на куски длиной rB. Далее абонент А шифрует свое сообщение m открытым ключом

абонента В и находит

m1 = mb (mod rB), 0 < m1 < rB.

Абонент В расшифровывает это сообщение своим секретным ключом:

m2 = m1β (mod rB), 0 < m2 < rB.

и получает m2 = m.

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

Пусть

p1 = 7, p2 = 23 – простые числа А.

rA = p1· p2 =161 φ(rA) = 132.

q1 = 11, q2 = 17 – простые числа В.

rB = q1· q2 = 187 φ(rB) = 160.

a = 7, b = 9 – случайные числа, выбранные А и В соответственно.

132

Телефонная книга: А: 161, 7 В: 187, 9

Каждый из абонентов находит свой секретный ключ: А: 7·α ≡ 1 (mod 132) → α = 19

B: 9·β ≡ 1 (mod 160) → β = 89

Пусть абонент А решает послать абоненту В сообщение m =3. Тогда он шифрует свое сообщение открытым ключом абонента В: m1 ≡ 39≡ 48 (mod 187)

Абонент расшифровывает это сообщение своим секретным ключом:

m2 ≡ 4889≡ 3 (mod 187) Следовательно, m2 = m =3.

7.4. Компьютерная стеганография

Способы и методы сокрытия секретных сообщений известны с давних времен, причем данная сфера получила название «стеганография». Слово происходит от греческих слов steganos – секрет, тайна и graphy – запись, т.е. означает буквально «тайнопись».

Стеганография в отличие от криптографии имеет другую задачу; ее цель – скрыть сам факт существования секретного сообщения. При этом оба способа могут быть объединены и использованы для повышения эффективности защиты информации.

Методы стеганографии известны с древности. Хорошо известны различные способы скрытого письма между строк обычного, незащищенного письма – для этого используются специальные «невидимые» чернила. Другие способы включают в себя использование микрофотоснимков, незначительные различия в написании рукописных символов, маленькие проколы определенных символов в сообщении, множество других приемов сокрытия сообщения.

Компьютерные технологии придали новый импульс развитию и совершенствованию стеганографии, появилось новое направление в области защиты информации – компьютерная стеганография (КС). Методы КС, используя естественные неточности устройств оцифровки и избыточность аналогового видео- и аудиосигналов, позволяют скрывать сообщения в компьютерных файлах.

В современной КС существует два типа файлов: сообщение – файл, который необходимо скрыть, и контейнер – файл, который ис-

133

пользуется для скрытия в нем сообщения. Контейнеры бывают двух типов: контейнер-оригинал («пустой» контейнер) – это контейнер, который не содержит скрытой информации, и контейнер-результат – это контейнер, содержащий скрытую информацию. Под ключом в КС понимается секретный элемент, который определяет порядок занесения сообщения в контейнер.

Основные положения КС:

1.Методы скрытия должны обеспечивать аутентичность и целостность файла.

2.Предполагается, что противнику полностью известны возможные стеганографические методы.

3.Безопасность методов основывается на сохранении стеганографическим преобразованием основных свойств открыто передаваемого файла при внесении в него секретного сообщения и некоторой неизвестной противнику информации – ключа.

4.Даже если факт скрытия сообщения стал известен противнику, извлечение секретного сообщения представляет собой сложную вычислительную задачу.

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

– защита конфиденциальной информации от НСД;

– камуфлирование программного обеспечения;

– защита авторского права на некоторые виды интеллектуальной собственности;

– преодоление систем мониторинга и управления сетевыми ресурсами.

Рассмотрим, какими способами можно скрыть сообщение в файлах.

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

Для сокрытия информации в текстовых файлах используется специальное форматирование файлов, вставка дополнительных пробелов между словами, предложениями и абзацами, выбор определенных позиций букв в тексте (акростих – один из этих методов).

Информацию можно скрыть в неиспользуемых местах накопителей информации на магнитных дисках (например, на нулевой дорожке или в блоках, помеченных как поврежденные).

134

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

7.5. Сжатие (архивация информации)

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

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

Более удобно использовать для создания копий специально разработанные программы архивации файлов. Эти программы позволяют не только сэкономить место на носителях, но и объединять группы совместно используемых файлов в один архивный файл, что заметно облегчает ведение архивов.

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

Существует два основных метода архивации без потерь:

–алгоритм Хоффмана;

–алгоритм Лемпеля – Зива.

135

Практически все популярные программы архивации без потерь используют объединение этих двух методов – алгоритм LZH.

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

Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего повтора, а другие, соответственно, реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, а для записи редко встречающихся символов – длинные последовательности, то суммарный объем файла уменьшится. Например, английский алфавит имеет частоты, показанные в табл. 4. Соответствующие ему коды представлены здесь же.

					Таблица 4
	Частота встречаемости букв английского алфавита
	и соответствующий код Хоффмана
Буква	Частота, %	Код Хоффмана	Буква	Частота, %	Код Хоффмана
E	13	100	M	2,5	00011
T	10,5	001	U	2,4	0010
A	8,1	1111	G	2	00001
O	7,9	1110	Y	1,9	00000
N	7,1	1100	P	1,9	110101
R	6,8	1011	W	1,5	011101
I	6,3	1010	B	1,4	011100
S	6,1	0110	V	0,9	1101001
H	5,2	0101	K	0,4	110100011
D	3,8	11011	X	0,15	110100001
L	3,4	01111	J	0,13	110100000
F	2,9	01001	Q	0,11	1101000101
C	2,7	01000	Z	0,07	101000100

Строка двоичных кодов Хоффмана единственным образом разлагается на составные части, так как она действительно является просто строкой, представленной двоичным деревом знаков, обозначающих соответствующие буквы (рис. 37).

На рис. 37 правые ветки дерева соответствуют коду 1, а левые – коду 0.

Тогда строка из 29 знаков исходного текста

136

0

1

T E

H S I R N O A

L D

Y G U M C F

B W P

V

J X K

Z Q

Рис. 37. Двоичное дерево кодов Хоффмана

WENEEDMORESNOWFORBETTERSKIING преобразуется при использовании кода Хоффмана в строку

01110110 01100100 10011011 00011111 01011100 01101100

11100111

01010011 11010110 11100100 00100110 01011011 01101000

11101010 10110000 001, которая единственным образом расчленяется на буквы алфавита при простом сканировании текста слева направо для восстановления исходного сообщения. Заметим, что в случае сжатия методом Хоффмана исходная строка из 29 байтов (один символ кодируется одним байтом) заменилась строкой из 16 байтов.

Алгоритм Лемпеля–Зива

Классический алгоритм Лемпеля–Зива – LZ77, названный так по году опубликования, предельно прост. Он формулируется следующим образом: «если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче, чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность».

137

Примеры

Фраза КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ закодируется как КОЛО(-4, 3)_(-5, 4)О_(-14, 7)ЬНИ.

Строка из одинаковых символов АААААА закодируется как А(-1, 6).

Алгоритмы сжатия изображений

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

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

В целом алгоритм основан на дискретном косинусоидальном преобразовании (ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

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

Фрактальный алгоритм. Фрактальная архивация основывается на том, что мы представляем изображение в более компактной форме – с помощью коэффициентов системы итерируемых функций (IFS). Строго говоря, IFS представляет собой набор трехмерных аффинных

138

преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, y координата, яркость). Фактически, фрактальная компрессия – это поиск самоподобных областей в изображении и определение для них аффинных преобразований. При этом каждое преобразование кодируется считанными байтами, в то время как изображение, построенное с их помощью, может занимать несколько мегабайт.

Рекурсивный (волновой) алгоритм. Этот вид архивации исходит из идеи использования когерентности областей. Идея алгоритма заключается в том, что мы сохраняем в файл разницу – число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к нулю.

Так два числа a2i a2i+1 всегда можно представить в виде bli = (a2i +

+ a2i+1)/2 b2i = (a2i – a2i+1)/2.

Рассмотрим конкретный пример: пусть мы сжимаем строку из 8 значений яркости пикселов (ai): (220, 211, 212, 218, 217, 214, 210, 202). Мы получим следующие последовательности b1i и b2i: (215.5, 215, 215.5, 206) и (4.5, -3, 1.5, 4). Повторим операцию, рассматривая b1i как ai. Мы получим из (215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хоффмана, мы можем поместить в файл. Дополнительное сжатие можно получить, повторяя преобразование 4-6 раз.

7.6. Защита от программ шпионов

Защита от программных закладок

Программные закладки (ПЗ) – это программы, которые могут выполнять хотя бы одно из следующих действий:

–вносить произвольные искажения в коды программы, находящейся в оперативной памяти (ПЗ первого типа);

–переносить фрагменты информации из одних областей оперативной или внешней памяти компьютера в другие (ПЗ второго типа);

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

Задача защиты от ПЗ может рассматриваться в трех вариантах:

139

–не допустить внедрения ПЗ в компьютерную систему;

–выявить внедренную ПЗ;

–удалить внедренную ПЗ.

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

Универсальным средством защиты от внедрения ПЗ является создание изолированного компьютера. Компьютер называется изолированным, если:

–в нем установлена BIOS (базовая система ввода-вывода), не содержащая ПЗ;

–ОС проверена на наличие в ней ПЗ;

–достоверно установлена неизменность BIOS и ОС для данного сеанса;

–на компьютере не запускалось и не запускается никаких иных программ, кроме уже прошедших проверку на присутствие в них закладок;

–исключен запуск проверенных программ вне изолированного компьютера.

Выявление внедренного кода ПЗ заключается в обнаружении признаков его присутствия в компьютерной системе. Эти признаки можно разделить на два класса:

–качественные и визуальные;

–обнаруживаемые средствами тестирования и диагностики.

К качественным и визуальным признакам отнесем ощущения и наблюдения пользователя, отмечающие отклонения в работе компьютерной системы (изменение длины и состава файлов, исчезновение файлов, изменение скорости работы прикладных программ и т. д.).

Признаки, выявляемые с помощью средств тестирования и диагностики, характерны как для ПЗ, так и для вирусов.

Конкретный способ удаления ПЗ зависит от метода ее внедрения в компьютерную систему. Если это программно-аппаратная закладка, то следует перепрограммировать ПЗУ компьютера. Если это загрузочная, драйверная, прикладная, замаскированная закладка или закладка-имитатор, то можно заменить их на соответствующую загрузочную запись, драйвер, прикладную или служебную программу, полученную из заслуживающего доверие источника.

140