Файл: Методы кодирования данных, основные понятия.pdf

Алгоритм Хаффмана остается всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами, в отличие от алгоритма Шеннона-Фано.

Данный метод кодирования состоит из двух наиболее важных этапов:

• построение оптимального кодового дерева;
• построение отображения код-символ на основе построенного дерева.

___________________

¹¹ Шавенько Н.К. Основы теории информации и кодирования / Н.К. Шавенько. – М.: МИИГАиК, 2012. – 34-37 с.

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

Не участвовавшие в объединении вероятности символов и вероятность вспомогательного символа снова ранжируют, т.е. размещают в порядке убывания вероятностей в дополнительном столбце, а два последних символа группируются. Такого рода процесс продлевают до тех пор, пока не получат единичный вспомогательный сим­вол с вероятностью, которая будет равна 1. Пример того, как кодируют по алгоритму Хаффмена приведен в Таблице 5.

Таблица 5

Кодирование по алгоритму Хаффмена

Граф кодирования (кодовое дерево) представлен на рис. 3, он иллюстрирует выстраивание символов на группы и отдельные символы, причем из точки, которой соответствует вероятность 1, направлены две ветви: одной из них (с большей вероятностью) присваиваем символ 1, а второй – символ 0.

Рис. 3. Граф кодирования по алгоритму Хаффмена

Данное ветвление шаг за шагом будем делать до тех пор, пока не дойдем до вероятности каждого символа. Спускаясь по кодовому дереву сверху вниз, легко записать для каждого символа источника сообщений соразмеримую ему комбинацию (кодовый символ): m₁ = 01, m₂ = 00, m₃ = 111, m₄ = 110, m₅ = 100, m₆ = 1011, m₇ = 10101, m₈ = 10100

Этот алгоритм можно использовать и при ином числовом основании кода, а также использовать блоки, как это рассмотрено в алгоритме Шеннона-Фано.¹¹

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

___________________

¹¹ Шавенько Н.К. Основы теории информации и кодирования / Н.К. Шавенько. – М.: МИИГАиК, 2012. – 37-40 с.

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

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

Глава 3. Кодирование как средство защиты информации от несанкционированного доступа

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

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

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

___________________

¹¹ Шавенько Н.К. Основы теории информации и кодирования / Н.К. Шавенько. – М.: МИИГАиК, 2012. – 27-53 с.

⁴ Кретова Л.М. Методы и средства защиты информации: 2-е издание. Учебное пособие для студентов вузов / Л.М. Кретова. – М.: АГРАФ, 2012. – 34 с.

Реализация для методов криптографического закрытия может быть программная и аппаратная:

• программная реализовывается на основе вычислительных процессов, причем и на этапе шифрования, и на этапе дешифрирования;
• аппаратная реализация создана на использовании специализированной аппаратуры.

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

Далее рассмотрим подробнее метода криптографического закрытия на примере шифрования текстов.

3.1. Шифр простой подстановки

Данный метод шифрования заключается в том, что при нем все символы алфавита однозначно заменяют другими символами того же самого или другого алфавита. Например, если объем алфавита исходного сообщения берем за n, а замена происходит из того же алфавита, то в таком случае существует n! способов замены символов отправного сообщения, т.е. имеется n! многообразных ключей.⁴

Рассмотрим несколько примеров шифра подстановки:

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

________________________

¹¹ Шавенько Н.К. Основы теории информации и кодирования / Н.К. Шавенько. – М.: МИИГАиК, 2012. – 54 с.

⁴ Кретова Л.М. Методы и средства защиты информации: 2-е издание. Учебное пособие для студентов вузов / Л.М. Кретова. – М.: АГРАФ, 2012. – 36 с.

а б в г д ………. ъ э ю я

г д е ё ж ………. я а б в

Таким образом видно, что при шифровании буква А заменяется буквой

Г, буква Б заменяется буквой Д и т.д. Ключом в шифре Цезаря служит мера

сдвига алфавита в нижней строке, на деле являющаяся любой.

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

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

3. Квадрат Полибия, шифрование в данном случае заключается в том, что ­в квадратную матрицу с числом элементов, которое равно или больше объема алфавита на место каждого элемента в хаотическом порядке вписываются все буквы алфавита, та буква, которая зашифрована, заменяется ее координатами в матрице. При расшифровке такого сообщения каждая пара чисел определяла соответствующую букву сообщения. Ключом в таком шифровании служит расположение букв в исходной матрице, но стоит отметить, что при свободном от порядка расположении букв в исходной матрице возникает определенное затруднение, т.к. отправителю и получателю данного сообщения необходимо помнить заданное расположение букв (ключ шифра), что весьма трудно делать, а если либо иметь при себе записанный ключ, то это опасно, т.к. что посторонние лица могут с ним ознакомиться. Чтобы устранить данные неудобства иногда ключ представляют дальнейшим образом ­– берут за основу любое «ключевое слово», преимущественно легкозапоминающееся, выдергивают из него повторы букв, а потом записывают его в начальных элементах матрицы, на место же других элементов записывают остальные буквы алфавита в естественном порядке. Широко применяемым примером данного шифра служит в народе называемый «тюремный шифр», в котором матрица заполняется буквами в порядке их расстановки в алфавите.¹¹

3.2. Шифры перестановки

Данный метод шифрования заключается в том, что берется определенное число n и записывается в строку ряд чисел 1, 2, …, n затем под ними записываются те же цифры, но уже в произвольном порядке, к примеру, для n = 5:

1 2 3 4 5

4 3 2 5 1

Далее записывается шифруемое сообщение без пропусков и дробится на группы по n букв, н стоит отметить, что если число букв до n не кратно n, то последняя группа дополняется до n любыми буквами. Впоследствии буквы каждой группы передвигаются в соответствии с выбранной двухстрочной таблицей: 1-ая буква становится 4-ой, 2-ая – 3-ей и т.д. После того, как выполнили перестановку в каждой группе, полученный текст записывается без пропусков. Для данного шифра ключом служит таблица перестановок. При дешифрировании криптограмма разбивается на группы по n букв и буквы перестанавливаются в противоположном порядке.¹¹

____________________

¹¹ Шавенько Н.К. Основы теории информации и кодирования / Н.К. Шавенько. – М.: МИИГАиК, 2012. – 54-55 с.