Как уже отмечалось выше, под кодированием понимается замена элементов открытого текста (букв, слов, фраз и т.п.) кодами. Различают символьное и смысловое кодирование.
При символьном кодировании каждый знак алфавита открытого текста заменяется соответствующим символом. Примером символьного кодирования служит азбука Морзе, а также методы шифрования заменой и перестановкой. Рассмотрим метод символьного кодирования, который использует предыдущие символы открытого текста. Этот метод, называемый метод стопки книг, был предложен Б.Я. Рябко.
Предположим, что нужно передать сообщение X из алфавита А, в котором буквы алфавита отождествлены с числами 1,2,..L, где L - число элементов алфавита А. Каждой букве алфавита соответствует код ki, i=1..L. При появлении в сообщении X очередной буквы хj ее код представляется кодом номера позиции j, занимаемой в данный момент буквой хj в списке. Это дает возможность на приемном конце по коду номера позиции j определить букву хj. После кодирования буквы хj одновременно на приемном и передающих концах перемещают букву хj в начало списка, увеличивая тем самым на единицу номера букв, стоявших на позициях от 1 до j-1. Номера букв, стоявших на позициях от j+1 до L, остаются без изменений. В результате кодирования открытого текста в начале списка будут находиться буквы, которые наиболее часто встречались в открытом тексте.
Пример 1. Открытый текст: "АБРАКАДАБРА". Алфавит:{А,Б,Д,К,Р}.
Начальный список соответствует последовательности букв в
алфавите и ему соответствует список кодов {К1,К2,КЗ,К4,К5}. Схема
кодирования показана на рис. 9 (коды, которыми кодируется открытый текст, выделены).
К1 А А Б P А К А Д А Б Р А
К2 Б Б А Б Р А К А Д А Б Р
К3 Д Д Д A Б Р Р К К Д А Б
К4 К К К Д Д Б Б Р Р К Д Д
К5 Р Р Р К К Д Д Б Б Р К К
¦ ¦
¦ L начальный список
список кодов
Рис.9. Динамика изменения списка при кодировании.
Закодированное сообщение: "К1 К2 К5 К3 К5 К2 К5 К2 К5 К5 К3".
Интересный метод кодирования в 1992 году предложил С.П.
Савчук. В отличие от метода стопки книг перемещению подвергается
список кодов. Пусть алфавит А={а1,а2,...,аn}. Данному порядку
расположения букв соответствует начальный список кодов
K0={k1,k2,..,kn}. При появлении в кодируемом сообщении буквы ai в
качестве кода выбирается соответствующий ее местоположению код
ki. После этого осуществляется сдвиг списка кодов:
{k1,k2,...,ki,...,kn}->{k2,k3,...,kn,k1}
Таким образом, список кодов образует замкнутое кольцо.
Пример 2. Открытый текст: "АБРАКАДАБРА".
Алфавит: {А,Б,Д,К,Р}.
Список кодов: К0={К1,К2,КЗ,К4,К5}.
Динамика изменения списка кодов представлена на рис.10
(коды, которыми кодируется открытый текст, выделены квадратами).
А [K1] К2 К3 [K4] К5 [K1] К2 [K3] К4 К5 [K1]
Б К2 [К3] К4 К5 К1 К2 К3 К4 [К5] K1 K2
Д К3 К4 К5 К1 К2 K3 [K4] К5 К1 К2 K3
К К4 К5 К1 К2 [K3] К4 К5 К1 К2 К3 К4
Р К5 К1 [К2] К3 К4 К5 К2 К2 К3 [K4] K5
¦ ¦
¦ L начальный список
L алфавит
Рис.10. Динамика изменения списка кодов.
Закодированное сообщение:
"К1 К3 К2 К4 К3 К1 К4 К3 К5 К4 К1".
Особенность данного метода состоит в том, что кодированный текст обеспечивает равномерную частоту появления кодов. Обычно криптоаналитики при наличии доступа к системе шифрования (кодирования) используют шифрование своих сообщений из одинаковых символов для анализа получаемых криптограмм и раскрытия ключа. Рассмотрим пример с кодированием по методу С.П. Савчука .
Пример 3. Открытый текст: "АААААААААА"
Алфавит: {А,Б,Д,К,Р}.
Список кодов: К0={К1,К2,К3,К4,К5}.
Закодированное сообщение
"К1 К2 К3 К4 К5 К1 К2 К3 К4 К5"
содержит одинаковое число всех кодов.
Таким образом, если число символов открытого текста кратно
длине алфавита, то этот метод дает одинаковое число появления
различных кодов при использовании в качестве открытого текста
одинаковых символов.
Смысловое кодирование - это кодирование, в котором в качестве исходного алфавита используются не только отдельные символы (буквы), но и слова и даже наиболее часто встречающиеся фразы.
Рассмотрим пример одноалфавитного и многоалфавитного смыслового кодирования.
Пример 4. Открытый текст: "19.9.1992 ГОДА".
Таблица кодирования представлена в таблице 13.
| элементы открытого текста | коды | ||||||
| 1 | 089 146 214 417 | ||||||
| 2 | 187 226 145 361 | ||||||
| _ | _ | ||||||
| 9 | 289 023 194 635 | ||||||
| ГОД | 031 155 217 473 | ||||||
| _ | 786 432 319 157 | ||||||
| Таблица 13 | |||||||
Закодированное сообщение при одноалфавитном кодировании:
"089 289 786 289 786 089 289 289 187 031".
Закодированное сообщение при многоалфавитном кодировании:
"089 289 786 023 432 146 194 635 187 031"
(при многоалфавитном кодировании одинаковые символы заменяются
кодами из следующего столбца).
Среди различных кодов, применяемых для кодирования естественных языков, особый интерес вызывает КОД ХАФФМЕНА, который позволяет сжимать открытый текст. Суть его состоит в присваивании наиболее часто встречающимся буквам наиболее коротких кодов.
Строка двоичных символов кодов Хаффмена единственным образом разлагается на коды символов (такие коды называются префиксными).
Пример 5. Закодированное кодом Хаффмена сообщение имеет
вид: "O11O1OOO1OOOOOO1O1O1111OOO1OOOOO".
Пользуясь деpевом для английского языка, получаем 0110=S.
Далее снова начинаем движение из вершины: 100=E; 01000=C;
00010=U; 1011=R; 1010=I; 001=T; 00000=Y.
Открытый текст: "SECURITY".
УПРАЖНЕНИЯ.