3.3. Методы шифрования

Методы замены. Шифрование методом замены (подстановки) основано на алгебраической операции, называемой подстановкой.

Подстановкой называется взаимно однозначное отображение некоторого конечного множества М на себя. Число N элементов этого множества называется степенью подстановки. Природа множества M роли не играет, поэтому можно считать, что M={1,2,...,N}.

В криптографии рассматриваются четыре типа подстановки (замены): моноалфавитная, гомофоническая, полиалфавитная и полиграммная.

Далее в примерах, где необходимо, будет использовано кодирование букв русского алфавита, приведенное в табл. 3.1. Знак "_" означает пробел.

Таблица 3.1

Кодирование букв русского алфавита

Буквы	А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я _
Коды	010203040506070809101112131415161718192021222324252627282930313233

При моноалфавитной замене каждой букве алфавита открытого текста ставится в соответствие одна буква шифротекста из этого же алфавита.

Пример 1. Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ".

Подстановка задана табл. 3.2.

Таблица 3.2

Алфавиты исходного и шифротекста

Алфавит исходного текста	А Б В Г Д ...
Алфавит шифротекста	_ Я Ю Э Ь

Шифротекст: "ИШМРТЮ_УШЫАЩ_ФЫУТЧ".

Основным недостатком рассмотренного метода является то, что статистические свойства открытого текста (частоты повторения букв) сохраняются в шифротексте.

Общая формула моноалфавитной замены имеет следующий вид:

Yi=k1*Xi+k2(mod N)

где уi - i-й символ алфавита;

k1 и k2 - константы;

Xi - i-й символ открытого текста (номер буквы в алфавите);

N - длина используемого алфавита.

Шифр, задаваемый формулой:

yi=xi+ki(mod N),

где ki - i-ая буква ключа, в качестве которого используются слово или фраза, называется шифром Вижинера.

Пример 2. Открытый текст: "ЗАМЕНА".

Ключ: "КЛЮЧ" (табл. 3.3).

Таблица 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мулы:

уi=ki-xi(mod n) и

yi=xi-ki(mod n).

Гомофоническая замена одному символу открытого текста ставит в соответствие несколько символов шифротекста. Этот метод применяется для искажения статистических свойств шифротекста.

Пример 3. Открытый текст: "ЗАМЕНА". Подстановка задана в табл. 3.4.

Таблица 3.4

Алфавиты открытого и шифротекста

при гомофонической замене

Алфавит открытого текста	А Б ... Е Ж З ... М Н
Алфавит шифротекста	17 23 97 47 76 32 55 31 44 51 67 19 28 84 48 63 15 33 59 61 34

Шифротекст: "76 17 32 97 55 31".

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

Полиалфавитная подстановка использует несколько алфавитов шифротекста. Пусть используется k алфавитов. Тогда открытый текст:

Х=X₁X₂...X_k X_k+1...X_2k X_2k+1...

заменяется шифртекстом:

Y=F1(X1)F2(X2)...Fk(Xk) F1(Xk+1)...Fk(X2k) F1(X2k+1)...

где Fi(Xj) означает символ шифртекста алфавита i для символа открытого текста Xj.

Пример 4. Открытый текст: "ЗАМЕНА", k=3.

Подстановка задана таблицей из примера 3.

Шифртекст: "76 31 61 97 84 48".

Полиграммная замена формируется из одного алфавита с помощью специальных правил. В качестве примера рассмотрим шифр Плэйфера.

В этом шифре алфавит располагается в матрице. Открытый текст разбивается на пары символов X_iX_i+1. Каждая пара символов открытого текста заменяется на пару символов из матрицы следующим образом:

1) если символы находятся в одной строке, то каждый из символов пары заменяется на стоящий правее его (за последним символом в строке следует первый);

2) если символы находятся в одном столбце, то каждый символ пары заменяется на символ, расположенный ниже его в столбце (за последним нижним символом следует верхний);

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

4) если в открытом тексте встречаются два одинаковых символа подряд, то перед шифрованием между шали вставляется специальный символ (например, тире).

Пример 5. Открытый текст: "ШИФР_ПЛЭЙФЕРА". Матрица алфавита представлена в табл. 3.5.

Таблица 3.5

А	Ч	Б	М	Ц	В
Ч	Г	Н	Ш	Д	О
Е	Щ	,	Х	У	П
.	З	Ъ	Р	И	Й
С	Ь	К	Э	Т	Л
Ю	Я	_	Ы	Ф	-

Шифртекст: "РДЫИ,-СТ-И.ХЧС"

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

Шифр, в котором сам открытый текст или получающаяся криптограмма используются в качестве "ключа", называется шифром с автоключом. Шифрование в этом случае начинается с ключа, называемого первичным, и продолжается с помощью открытого текста или криптограммы, смещенной на длину первичного ключа.

Пример 6. Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ".

Первичный ключ: "КЛЮЧ"

Схема шифрования с автоключом при использовании открытого текста представлена в табл. 3.6.

Таблица 3.6