56. Шифрование методом замены. Простая, полиалфавитная и многозначная замены.

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

Подстановкой называется взаимнооднозначное отображение некоторого конечного множества М на себя. Число 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текста _ Я Ю Э Ь

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

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

Yi=k1*Xi+k2(mod N)

где уi- i-й символ aлфавитa; k1 и k2- константы;

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

Шифр, задаваемый фоpмулой: yi=xi+ki(mod n),

где ki- i-ая буква ключа, в качестве которого используются слово или фраза, называется шиф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 -> _М. Шифртекст: "ТМКЭШМ".

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

Суть полиалфавитного шифра заключается в циклическом применении нескольких моноалфавитных шифров к определённому числу букв шифруемого текста. Предположим, что имеется некоторое сообщение x1 , x2 , x3 , …, xn , …, x2n, …, которое необходимо зашифровать, а также для использования полиалфавитного шифра взяли n моноалфавитных шифров. В данном случае к первой букве применяется первый моноалфавитный шифр, ко второй букве — второй, к третьей — третий, …, к n-ой

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

Омофоническая замена — шифр подстановки, при котором каждый символ открытого текста заменяется на один из нескольких символов шифралфавита, причём количество заменяющих символов для одной буквы пропорционально частоте этой буквы. Это позволяет скрыть настоящую частоту появления данной буквы в зашифрованном тексте.

Особенность данного метода состоит в том, что шифрозамены не повторяются. Это значит, что если у буквы «Ф» 3 шифрозамены, например, , и , то шифрозамены , и обозначают только букву «Ф».

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

Пусть — символ алфавита, который используется в открытом тексте. Для каждого составим множество символов , таким образом, чтобы для различных символов и множества и не пересекались. Обычно элементами множества являются числа. При омофоническом шифровании, число замен для каждого символа берется пропорционально вероятности появления этого символа в открытом тексте. При шифровании замена для символа открытого текста выбирается либо случайным образом (генератор случайных чисел), либо определенным образом (например, по порядку). Чтобы запомнить буквы, которые чаще всего встречаются в текстах, используют комбинации букв «сеновалитр» и «tetrishonda» для русского и английского языков соответственно. Эти комбинации похожи на слова, а потому легко запоминаются.

		Вероятность появления букв русского алфавита
	Букв а	Вероятнос ть			Букв а	Вероятнос ть				Букв а	Вероятнос ть				Букв а		Вероятнос ть
	А	0,069			И	0,064				Р	0,042				Ш		0,006
	Б	0,013			Й	0,010				С	0,046				Щ		0,004
	В	0,038			К	0,029				Т	0,054				Ъ		0,001
	Г	0,014			Л	0,039				У	0,023				Ы		0,015
	Д	0,024			М	0,027				Ф	0,003				Ь		0,013
	Е,Ё	0,071			Н	0,057				Х	0,008				Э		0,002
	Ж	0,007			О	0,094				Ц	0,005				Ю		0,005
	З	0,016			П	0,026				Ч	0,012				Я		0,017

(*) (В таблице представлены результаты частотного анализа художественных и научнотехнических текстов общим объёмом более 1 млн символов. При этих же условиях вероятность «пробела» составляет 0,146.)

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

№	А	Б	В	…	Е	…	О	П	Р	…	Э	Ю	Я
1	012	128	325	…	037	…	064	058	265	…	501	064	106
2	659	556	026	…	700	…	149	073	333	…	248	749	098
…	…	…	…	…	…	…	…	…	…	…		…	…
17	111		061	…	144	…	903	656	476	…			453
…	…		…	…	…	…	…	…	…	…
38	366		804	…	…	…	123		865	…
…	…			…	…	…	…		…	…
69	095				…		010
…					…		…
71					541		268
…							…
94							479

Некоторые поля в таблице пусты, так как для каждого символа исходного алфавита количество замен различно. Например, по этому фрагменту можно зашифровать слово «ВЕРА». Каждую букву исходного сообщения, в данном случае слова, следует заменить на одну из шифрозамен в столбце этой буквы. Если буквы заменить такими шифрозаменами: «В»-, «Е»-, «Р»-, «А»-, тогда зашифрованное слово имеет вид числовой последовательности « »^[.