Предположим, что нужно передать сообщение X из алфавита А, в котором буквы алфавита отождествлены с числами 1,2,..L, где L - число элементов алфавита А. Каждой букве алфавита соответствует код ki, 1=1..L. При появлении в сообщении X очередной буквы хj ее код представляется кодом номера позиции j, занимаемой в данный момент буквой хj в списке. Это дает возможность на приемном конце по коду номера позиции j определить букву хj. После кодирования буквы хj одновременно на приемном и передающих концах перемещают букву хj в начало списка, увеличивая тем самым на единицу номера букв, стоявших на позициях от 1 до j-1. Номера букв, стоявших на позициях от j+1 до L, остаются без изменений. В результате кодирования открытого текста в начале списка будут находиться буквы, которые наиболее часто встречались в открытом тексте.
Пример 6.19. Открытый текст: "АБРАКАДАБРА". Алфавит: {А,Б,Д,К,Р}.
Начальный список соответствует последовательности букв в алфавите и ему соответствует список кодов {К1,К2,КЗ,К4,К5}. Схема кодирования показана на рис.6.9.
К1 А А Б P А К А Д А Б Р А К2 Б Б А Б Р А К А Д А Б Р К3 Д Д Д A Б Р Р К К Д А Б К4 К К К Д Д Б Б Р Р К Д Д К5 Р Р Р К К Д Д Б Б Р К К - - - <начальный список список кодов
Рис.6.9. Динамика изменения списка при кодировании.
Интересный метод кодирования в 1992 году предложил С.П. Савчук. В отличие от метода стопки книг перемещению подвергается список кодов. Пусть алфавит А={а1,а2,...,аn}. Данному порядку расположения букв соответствует начальный список кодов K0={k1,k2,..,kn}. При появлении в кодируемом сообщении буквы ai в качестве кода выбирается соответствумций ее местоположению код ki. После этого осуществляется сдвиг списка кодов:
{k1,k2,...,ki,...,kn}->{k2,k3,...,kn,k1}
Таким образом, список кодов образует замкнутое кольцо.
Пример 6.20. Открытый текст: "АБРАКАДАБРА". Алфавит: {А,Б,Д,К,Р}. Список кодов: К0={К1,К2,КЗ,К4,К5}.
Динамика изменения списка кодов представлена на рис.6.10 (коды, которыми кодируется открытый текст, выделены квадратами).
Особенность данного метода состоит в том, что кодированный текст обеспечивает равномерную частоту появления кодов. Обычно криптоаналитики при наличии доступа к системе шифрования (кодирования) используют шифрование своих сообщений из одинаковых символов для анализа получаемых криптограмм и раскрытия ключа. Рассмотрим пример с кодированием по методу С.П.Савчука .
Пример 6.21. Открытый текст: "АААААААААА" Алфавит: {А,Б,Д,К,Р}. Список кодов: К@={К1,К2,Ка,К4,К5}. Закодированное сообщение "К1 К2 К3 К4 К5 К1 К2 К3 К4 К5" содержит одинаковое число всех кодов.
Таким образом, если число символов открытого текста кратно длине алфавита, то этот метод дает одинаковое число появления различных кодов при использовании в качестве открытого текста одинаковых символов.
Смысловое кодирование - это кодирование, в котором в качестве исходного алфавита используются не только отдельные символы (буквы), но и слова и даже наиболее часто встречающиеся фразы.
Рассмотрим пример одноалфавитного и многоалфавитного смыслового кодирования.
Пример 6.22. Открытый текст: "19.9.1992 ГОДА". Таблица кодирования представлена в таблице 6.13.
Таблица 6.13 Элементы откpытого Коды текста 1 089 146 214 417 2 187 226 045 361
Закодированное сообщение при одноалфавитном кодировании:
"089 289 786 289 786 089 289 289 187 031".
Закодированное сообщение при многоалфавитном кодировании:
"089 289 786 023 432 146 194 635 187 031"
(при многоалфавитном кодировании одинаковые символы заменяются кодами из следующего столбца).
Среди различных кодов, применяемых для кодирования естественных языков, особый интерес вызывает код Хаффмена [6], который позволяет сжимать открытый текст. Суть его состоит в присваивании наиболее часто встречающимся буквам наиболее коротких кодов.
Строка двоичных символов кодов Хаффмена единственным образом разлагается на коды символов (такие коды называются префиксными).
Пример 6.23. Закодированное кодом Хаффмена сообщение имеет вид: "O11O1OOO1OOOOOO1O1O1111OOO1OOOOO".
Пользуясь деpевом для английского языка, получаем 0110=S. Далее снова начинаем движение из вершины: 100=E; 01000=C; 00010=U; 1011=R; 1010=I; 001=T; 00000=Y. Открытый текст: "SECURITY".
6.5. Другие методы шифрования
Широкое применение персональнта ЭВМ (ПЭВМ) сделало актуальной задачу защиты хранящихся данных (файлов). Для защиты файлов могут быть применены рассмотренные методы шифрования и кодирования.
Специфика применения ПЭВМ позволяет реализовать дополнительные методы кодирования для надежного закрытия содержимого файлов. Примером такого кодирования является метод рассечения-разнесения, в соответствии с которым содержимое одного файла разбивается на блоки, которые разносятся по нескольким файлам. Каждый такой файл не несет никакой информации, а сбор данных в единое целое осуществляется простой программой.
Пример 6.24. Блок (файл открытого текста) начинается словами: "МЕТОД_РАССЕЧЕНИЯ-РАЗНЕСЕНИЯ".
Для рассечения блока открытого текста на 8 частей запишем открытый текст в следующем виде (таблица 6.14).
Таблица 6.14
1 2 3 4
1 М Е Т О 2 Д _ Р А
1 С С Е Ч 2 Е Н И Я
1 - Р А З 2 Н Е С Е
1 Н И Я ...
Для рассечения текста на 8 частей выбраны 2 строки и 4 столбца. Пусть столбцы sj выбираются в последовательности {4,1,3,2}, а строки ri- в последовательности (2,1}. Тогда номер k блока Фk, куда записывается очередной символ открытого текста, определяется по формуле:
k= (ri-1)n+sj,
где n - число столбцов.
Первый символ М запишется в блок с номером (ri=2, sj=4):
k=(2-1)*4+4=8;
второй символ E - в блок с номером (ri=2, sj=1);
k=(2-1)*4+1=5, и т.д.
Тогда блоки Фk, записанные в порядке номеров, будут содержать следующие символы: Ф1=(_НЕ...), Ф2=(АЯЕ...), Ф3=(РИС..,), Ф4={ДЕН...), Ф5={ЕСРИ...}, Ф6={ОЧЗ...), Ф7={ТЕАЯ...), Ф8={МС-Н...}. Таким образом, один блок открытого текста заменяется восемью блоками, которые в сумме дают длину исходного блока. Другой важной проблемой при использовании ПЭВМ является проблема хранения больших массивов данных. Для этой цели применяются различные методы сжатия данных (сжатие можно рассматривать как метод кодирования).
Методы сжатия данных осуществляют такое преобразование повторящихся символов и строк символов, которое позволяет использовать для хранения данных меньший объем памяти.
Методы сжатия можно разделить на два класса: статические и динамические (адаптивные).
Методы статического сжатия данных эффективны, когда частоты появления символов изменяются незначительно. Методы динамического сжатия адаптивно отслеживают неравномерности частот появления символов с сохранением последовательности изменений вероятностей появления символов.
К статическим методам можно отнести рассмотренные код Хаффмена и метод стопки книг Б. Я. Рябко. Адаптивные методы сжатия могут динамично реагировать на изменения в открытом тексте, происходящие по мере кодирования. Первые такие методы являлись модификацией кодов Хаффмена и использовали счетчики для хранения текущих частот появления каждого символа. При таких методах наиболее часто встречающиеся символы сдвигаются ближе к корню дерева и, следовательно, получают более короткие кодовые слова.
Кодирование Лемпеля-Зива [4] использует синтаксический метод для динамического источника. Этот метод осуществляет синтаксический анализ символьных потоков, которые не превышают званной длины, и строит таблицу отображения этих потоков в кодированные слова фиксированной длины. Длина кодового слова зависит от размера таблицы, используемой для хранения кодового отображения поток-слово. Например, размер таблицы в 4096 слов требует 12-битового кодового слова. Кодовое слово является просто табличным адресом соответствующих слов в таблице .
При кодировании по методу Лемпеля-Зива-Уэлча [4] таблица инициализируется символьным множеством и содержит вместо потоков заданной длины пары (кодовое слово, символ) фиксированной длины. Таблица строится на основе синтаксического анализа самого длинного опознанного в таблице потока и использовании последующего символа для формирования нового входа в таблицу. Это позволяет уменьшить размеры таблицы.
В последнее время широкое распространение получили методы сжатия на основе расширяющихся деревьев [4]. Префиксный код переменной длины в этих методах строится на основе положения символов в дереве. Для получения оптимальных кодов дерево балансируется.
Каждый из методов кодирования, подробное рассмотрение которых выходит за рамки учебного пособия, может использоваться для защиты данных, особенно если используется свой (нестандартный) вариант метода сжатия данных. Стойкость кодирования повышается при использовании нескольких методов сжатия для одного блока открытых данных.
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ]
