Принципиально шифрование не отличается от кодирования. В криптографии под шифрованием понимается процесс, в котором криптографическому преобразованию подвергается каждый символ открытого текста, а под кодированием - замену элементов открытого текста (символов, комбинаций символов, слов и т.п.) кодами.
Шифрование методом замены (подстановки) основано на алгебраической операции, называемой подстановкой.
Подстановкой называется взаимнооднозначное отображение
некоторого конечного множества М на себя. Число N элементов этого
множества называется степенью подстановки. Природа множества M
роли не играет, поэтому можно считать, что M={1,2,...,N}.
Если при данной подстановке S число j переходит в Ij, то
подстановка обозначается символом S:
- -
¦ 1 2 ... n ¦
¦ I1 I2 ... In ¦
- -
В этой записи числа 1,2,...,n можно произвольным образом
переставлять, соответственно переставляя числа I1,I2,...In.
Результат последовательного выполнения двух подстановок S1 и
S2 одной и той же степени также является подстановкой, которая
называется произведением подстановок S1 и S2 и обозначается S1S2.
Произведение подстановок обладает свойством ассоциативности.
Пусть S - произвольная подстановка степени n. Если для некоторого j число Ij отлично от j, то говорят, что подстановка S действительно перемещает число j; в противном случае говорят, что подстановка S оставляет число j на месте.
Две подстановки называются независимыми, если они не имеют общих действительно перемещаемых чисел.
Количество m чисел, действительно перемещаемых подстановкой S, называется длиной цикла подстановки.
Подстановка S называется транспозицией, если существует пара (j1,j2) различных элементов из M, удовлетворяющих условиям: Ij1=j2, Ij2=j2, Ij=j для каждого j пp. {M\{j1,j2}}. Любая подстановка разлагается в произведение транспозиций.
Разложение подстановки в произведение независимых подстановок однозначно (с точностью до порядка множителей).
В криптографии рассматриваются четыре типа подстановки
(замены): моноалфавитная, гомофоническая, полиалфавитная и
полиграммная.
Далее всюду в примерах, где необходимо, будем использовать
кодирование букв русского алфавита, приведенное в таблице 1.
Знак "_" в таблице 1 и далее означает пробел.
Таблица 1
Буква А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я _
Код 010203040506070809101112131415161718192021222324252627282930313233
При моноалфавитной замене каждой букве алфавита открытого текста ставится в соответствие одна буква шифртекста из этого же алфавита.
Пpимеp 1. Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ".
Подстановка задана таблицей 2.
Таблица 2
Алфавит исходного текста А Б В Г Д ...
Алфавит шифpтекста _ Я Ю Э Ь
Шифртекст: "ИШМРТЮ_УШЫАЩ_ФЫУТЧ".
Основным недостатком рассмотренного метода является то, что
статистические свойства открытого текста (частоты повторения
букв) сохраняются в шифртексте.
Общая формула моноалфавитной замены выглядит следующим
образом:
Шифр, задаваемый фоpмулой:
Пример 2. Открытый текст: "ЗАМЕНА".
Ключ: "КЛЮЧ" (таблица 3).
Таблица 3
З А М Е Н А
К Л Ю Ч К Л
y1=8+11(mod 33)=19 -> Т
y2=1+12(mod 33)=13 -> М
у3=13+31(mod ЗЗ)=11-> К
y4=6+24(mod 33)=30 -> Э
у5=14+11(mod 33)=25 -> Ш
y6=1+12(mod 33)=13 -> М.
Шифртекст: "ТМКЭШМ".
Шифры Бофора используют фоpмулы:
Гомофоническая замена одному символу открытого текста ставит в соответствие несколько символов шифртекста. Этот метод применяется для искажения статистических свойств шифртекста.
Пример 3. Открытый текст: "ЗАМЕНА".
Подстановка задана таблицей 4.
Шифртекст: "76 17 32 97 55 31".
Таблица 4
Алфавит откpытого текста А Б ... Е Ж З ... М Н ...
17 23 97 47 76 32 55
Алфавит шифpтекста 31 44 51 67 19 28 84
48 63 15 33 59 61 34
Таким образом, при гомофонической замене каждая буква открытого текста заменяется по очереди цифрами соответствующего столбца.
Полиафавитная подстановка использует несколько алфавитов шифртекста. Пусть используется k алфавитов. Тогда открытый текст:
Пример 4. Открытый текст: "ЗАМЕНА", k=3.
Подстановка задана таблицей из примера 3.
Шифртекст: "76 31 61 97 84 48".
Полиграммная замена формируется из одного алфавита с помощью
специальных правил. В качестве примера рассмотрим шифр Плэйфера.
В этом шифре алфавит располагается в матрице. Открытый текст
разбивается на пары символов XiXi+1. Каждая пара символов
открытого текста заменяется на пару символов из матрицы следующим
образом:
1) если символы находятся в одной строке, то каждый из
символов пары заменяется на стоящий правее его (за последним
символом в строке следует первый);
2) если символы находятся в одном столбце, то каждый символ
пары заменяется на символ, расположенный ниже его в столбце (за
последним нижним символом следует верхний);
3) если символы пары находятся в разных строках и столбцах,
то они считаются противоположными углами прямоугольника. Символ,
находящийся в левом углу, заменяется на символ, стоящий в другом
левом углу; замена символа, находящегося в правом углу,
осуществляется аналогично;
4) если в открытом тексте встречаются два одинаковых символа
подряд, то перед шифрованием между шали вставляется специальный
символ (например, тире).
Пример 5. Открытый текст: "ШИФР_ПЛЭЙФЕРА". Матрица алфавита представлена в таблице 5.
Таблица 5
А Х Б М Ц В
Ч Г Н Ш Д О
Е Щ , Х У П
. З Ъ Р И Й
С Ь К Э Т Л
Ю Я _ Ы Ф -
Шифртекст: "РДЫИ,-СТ-И.ХЧС"
При рассмотрении этих видов шифров становится очевидным, что
чем больше длина ключа (например, в шифре Виженера), тем лучше
шифр. Существенного улучшения свойств шифртекста можно достигнуть
при использовании шифров с автоключом.
Шифр, в котором сам открытый текст или получающаяся
криптограмма используются в качестве "ключа", называется шифром с
автоключом. Шифрование в этом случае начинается с ключа,
называемого первичным, и продолжается с помощью открытого текста
или криптограммы, смещенной на длину первичного ключа.
Пример 6. Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ".
Первичный ключ: "КЛЮЧ"
Схема шифрования с автоключом при использовании открытого
текста представлена в таблице 6.
Таблица 6
Ш И Ф Р О В А Н И Е _ З А М Е Н О Й
К Л Ю Ч Ш И Ф Р О В А Н И Е _ З А М
362152414012223124093422101939221623
В Ф Т З Ж Л Х Ю Ч И А Х Й Т Е Х П Ц
Схема шифрования с автоключом при использовании криптограммы представлена в таблице 7.
Таблица 7
Ш И Ф Р О В А Н И Е _ З А М Е Н О Й
К Л Ю Ч В Ф Т З С Ч У Х Ъ Э У Э Ы Й
362152411824202227305330244326443920
В Ф Т З C Ч У Х Ъ Э У Э Ы Й Щ К Й У