Методы замены
Шифрование методом замены (подстановки) основано на алгебраической
операции,
называемой подстановкой. Подстановкой называется взаимнооднозначное
отображение
некоторого конечного множества М на себя. Число N элементов этого
множества называ-
ется степенью подстановки. Природа множества M роли не играет, поэтому
можно счи-
тать, что M = {1, 2, ..., N}.
Если при данной подстановке S число j переходит в Ij, то подстановка
обозначается
символом S:
В этой записи числа 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 ∈ {M\{j1, j2}}. Любая
подстановка разлагается в
произведение транспозиций.
В криптографии рассматриваются четыре типа подстановки (замены):
моноалфавит-
ная, гомофоническая, полиалфавитная и полиграммная.
Далее всюду в примерах, где необходимо, будем использовать кодирование
букв
русского алфавита, приведенное в табл. 6.1. Знак «_» в
табл. 6.1. и далее означает пробел.
При моноалфавитной
замене каждой букве алфавита открытого текста ставится в
соответствие одна буква шифртекста из этого же алфавита.
Пpимеp. Открытый текст: «ШИФРОВАНИЕ_ЗАМЕНОЙ». Подстановка
задана
табл. 6.2.
Шифртекст:
«ИШМРТЮ_УШЫАЩ_ФЫУТЧ».
Основным недостатком рассмотренного метода является сохранение
статистических
свойств открытого текста (частота повторения букв) в шифртексте.
Общая формула моноалфавитной замены выглядит в виде
Yi = k1Xi + k2(mod N),
где Yi – i-й символ aлфавитa; k1 и k2 – константы; Xi
– i-й символ открытого текста (номер
буквы в алфавите); N – длина используемого алфавита.
Шифр, задаваемый фоpмулой
Yi = Xi + ki(mod N),
где ki – i-ая буква ключа, в качестве которого используются слово
или фраза, называется
шифpом Вижинера.
Пример. Открытый текст: «ЗАМЕНА». Ключ: «КЛЮЧ».
