Файл: Методы кодирования данных (Методы кодирования текстовой и числовой информации).pdf

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

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

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

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

ГЛАВА 1. Цели кодирования

Рассмотрим ряд определений, которые мы будем использовать далее:

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

Под кодированием понимают процесс преобразования информации из одной формы представления (алфавита) в другую.

Декодирование – это процесс обратный кодированию, т.е. восстановление

информации в первичном алфавите по полученной последовательности кодов.

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

Языки представления информации делятся на два типа:

• Естественные, например:

1. Английский

2. Французский

3. Русский

• Формальные, например:

1. Математический

2. Языки программирования

3. Ноты

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

• Засекречивание информации. Для получения шифротекстов используют

специально разработанные алгоритмы криптографии

• Ускорение записи или сжатие информации. Используют специально

созданные алгоритмы, преобразующие информацию определенного

размера в более короткое ее представление, которое не изменяет меру

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

однозначно декодировано

• Для передачи по техническим каналам связи. Например, код Морзе для

передачи телеграфных сообщений, протокол Ethernet (для передачи

информации по сети интернет)

• Для выполнения математических вычислений. Например, человек привык проводить вычисления в десятичной системе, а компьютеры- в двоичной Начиная с конца 60-х годов, компьютеры все больше стали использоваться для обработки текстовой информации, и в настоящее время основная доля персональных компьютеров в мире (и большая часть времени) занята обработкой именно текстовой информации. Все эти виды информации в компьютере представлены в двоичном коде, т. е. используется алфавит мощностью два (всего два символа 0 и 1). Связано это с тем, что удобно представлять информацию в виде последовательности электрических импульсов: импульс отсутствует (0), импульс есть (1). Наиболее значимым для развития техники оказался способ представления информации с помощью кода, состоящего всего из двух символов: 0 и 1. Для удобства использования такого алфавита договорились называть любой из его знаков «бит» (от английского «binary digit» -двоичный знак). Одним битом могут быть выражены два понятия: 0 или 1 (да или нет, черное или белое, истина или ложь и т.п.). Двоичные числа очень удобно хранить и передавать с помощью электронных устройств. Например, 1 и 0 могут соответствовать намагниченным и ненамагниченным участкам диска; нулевому и ненулевому напряжению; наличию и отсутствию тока в цепи и т.п. Поэтому данные в компьютере на физическом уровне хранятся, обрабатываются и передаются именно в двоичном коде.

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

• Текстовая

• Графическая

• Аудио

• Видео

1.1 Шифрование

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

Рассмотрим следующие определения, которые используются в криптографии:

Открытый (исходный) текст — данные, которые передаются без использования криптографии.
Шифротекст, шифрованный (закрытый) текст — данные, полученные после применения шифра с некоторым ключом.
Шифр, криптосистема — семейство обратимых преобразований открытого текста в шифротекст.
Ключ — параметр шифра, который определяет конкретное преобразование открытого текста. По принципу Керкгоффса, в шифрах криптографическая стойкость шифра целиком определяется секретностью ключа.
Шифрование — процесс нормального применения криптографического преобразования открытого текста на основе алгоритма и ключа, в результате которого возникает шифрованный текст.
Расшифровывание — процесс нормального применения криптографического преобразования шифрованного текста в открытый.
Открытый ключ — тот из двух ключей асимметричной системы, который свободно распространяется. Шифрующий для секретной переписки и расшифровывающий — для электронной подписи.
Секретный ключ, закрытый ключ — тот из двух ключей асимметричной системы, который хранится в секрете.
Криптоанализ — наука, которая изучает математические методы нарушения конфиденциальности и целостности информации и уязвимости шифров
Криптоаналитик — человек, создающий и применяющий методы криптоанализа.
Криптографическая атака — попытка криптоаналитика вызвать отклонения в атакуемой защищённой системе обмена информацией. Успешную криптографическую атаку называют взлом или вскрытие.
Дешифрование — процесс извлечения открытого текста без знания криптографического ключа на основе известного шифрованного. Термин дешифрование обычно применяют по отношению к процессу криптоанализа шифротекста (криптоанализ сам по себе, вообще говоря, может заключаться и в анализе криптосистемы, а не только зашифрованного ею открытого сообщения).
Криптографическая стойкость — способность криптографического алгоритма противостоять криптоанализу.
Имитозащита — защита от навязывания ложной информации. Другими словами, текст остаётся открытым, но появляется возможность проверить, что его не изменяли ни случайно, ни намеренно. Имитозащита достигается обычно за счет включения в пакет передаваемых данных имитовставки.
Имитовставка — блок информации, применяемый для имитозащиты, зависящий от ключа и данных.
Электронная цифровая подпись, или электронная подпись — асимметричная имитовставка (ключ защиты отличается от ключа проверки). Другими словами, такая имитовставка, которую проверяющий не может подделать.
Хеш-функция — функция, которая преобразует сообщение произвольной длины в целое число фиксированной длины, зависящей от алгоритма.

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

Симметричные:

1. DES

2. AES

3. ГОСТ 28147-89

4. BlowFish

5. RC4

Асимметричные:

1. RSA

2. Эль-Гамаль

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

Протокол Диффи-Хелмана
MtProto – протокол обмена сообщениями в Telegram
Протокол конфиденциального вычисления

1.2 Архивация

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

Степень сжатия информации зависит от содержимого файла и формата файла, а также от выбранного метода архивации. Степень (качество) сжатия файлов характеризуется коэффициентом сжатия K, определяемым как отношение объема исходного файла K V = к объему V V сжатого файла V: Чем больше величина K, тем выше степень сжатия информации. Заметим, что в некоторых литературных источниках встречается определение коэффициента сжатия, обратное приведенному отношению.

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

В настоящее время разработано много алгоритмов архивации без потерь. Однако все они используют две простые идеи. Первая идея, основанная на учете частот появления символов в тексте, была разработана Хаффманом (D.A. Huffman) в 1952 г. Она базируется на том факте, что в обычном тексте частоты появления различных символов неодинаковые. При кодировании символов в ЭВМ используют кодовые таблицы. При этом каждый символ кодируется либо одним байтом (CP-1251, КОИ-8), либо двумя байтами (Unicode). Кодовые таблицы стандартизируют процедуру кодирования. Однако для передачи информации по каналу связи (или для долговременного хранения) можно использовать более сложную процедуру кодирования, которая обеспечит уменьшение размера файла при полном сохранении исходной информации. При архивации не используются стандартные кодовые таблицы, а создаются собственные. При этом вид кодовой таблицы каждый раз изменяется и зависит от содержания архивируемого документа. При упаковке по методу Хаффмана часто встречающиеся символы кодируются (заменяются) короткими последовательностями битов, а более редкие символы — длинными последовательностями. К каждому сжатому архиву прикладывается таблица соответствия имеющихся символов и кодов (чисел), заменяющих эти символы. Архивы как бы отменяют стандартные кодовые таблицы.

Все способы сжатия можно разделить на две категории: обратимое и необратимое сжатие. Необратимое сжатие - такое преобразование входного потока информации, при котором выходной поток, основанный на определенном формате информации, представляет собой объект, достаточно похожий по внешним характеристикам на входной поток, однако отличается от него объемом. Степень сходства входного и выходного потоков определяется степенью соответствия некоторых свойств объекта (до сжатия и после), представляемого данным потоком информации. Такие подходы и алгоритмы используются для сжатия информации растровых графических файлов, видео и звука. При таком подходе используется свойство структуры данного формата файла и возможность представить информацию приблизительно схожую по качеству для восприятия человеком. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходная информация в процессе сжатия изменяется. Под качеством можно понимать степень соответствия исходной и результирующей информации, оцениваемое субъективно, исходя из формата информации. Для графических файлов такое соответствие определяется визуально, хотя имеются и соответствующие интеллектуальные алгоритмы и программы. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Данный подход реализован в популярных форматах представления фотоинформации - JPEG, TIFF, GIF, PNG и др., аудио информации - MP3, видео информации - MPEG-4.

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