Лекция 5. Шифры замены и модульного гаммирования.

5.1.Шифры замены и коды. Рандомизация.

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

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

Таблица 1. Шифр двузначной замены

	0	1	2	3	4	T O B E O R N O T T O B E 133002243014113013 13300224
0	v	p	b	a	c
1	q	n	z	t	r
2	d	u	x	l	e
3	o	j	s	i	f
4	k	g	v	h	m
5	w

В общем случае, преобразование открытого текста в шифрах замены задается с помощью различных таблиц, которые носят название таблиц замены. Для указанных шифров криптографическая система фактически заключается в алгоритме типа «взять очередную букву открытого текста, найти ее в левой части таблицы, выбрать соответствующее значение из правой части и записать его на соответствующее место в шифртекст». Стоит подчеркнуть, что для данной процедуры не важно, в каком алфавите представлен открытый текст и какова «начинка» таблицы. В принципе, она может оказаться пустой. В последнем случае наиболее ясно видно, что собой представляет система шифрования как таковая. Для того, чтобы ее «оживить» необходимо каждый раз перед зашифрованием криптограммы решать конкретный вопрос: какими данными заполнить таблицу? Ответ состоит в том, что эти данные являются ключом для шифра замены и, следовательно, возникают из источника ключей.

В зависимости от структуры таблицы, данные можно представить различным образом. Очевидно, что чем компактнее представление данных, тем лучше. Для шифра простой замены, например, ключом служит любая перестановка букв алфавита, так как таблица замены по ней строится без труда. Для шифра Цезаря ключами могут служить числа, задающие величину циклического сдвига алфавита. В первом случае количество ключей равно !. Во втором - ключей всего . В обоих случаях не все ключи равноценны. Например, при выходном алфавите, отличающемся от входного перестановкой двух букв, шифрованный текст можно прочитать так же легко, как и открытый. С этой точки зрения принято говорить о качестве ключей шифрсистемы.

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

Ш и ф р а н т

Д е ш и ф р а н т

	1 2 3 4 5 6 7 8 9 0
1 2 3 4 5 6 7 8 9 0	С В Т И О Ы И Ч А О Е Ю А Л Ж П О И Я Р К Н О И Б У Е Т Д М Т А О Р Н И Ш А С Л О З Е Я Д Т О П В Ц А Б М И С Э М Е Н Т Н Л Е Щ О А Ы И Р К Ь В И Л Ф О Е Н А С К Х Д Р И Н В У О П С А Н Т Г О Е Р Е В

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

В течение одного такта шифрования шифрсистема может преобразовать один, либо несколько знаков, некоторый участок открытого текста, слог, фразу, слово и, в принципе, целое сообщение. Шифры замены преобразуют на каждом такте группу символов. Количество знаков в группе при этом фиксировано и называется значностью группы. Группы значности 2 незываются биграммами, значности 3 - триграммами, значности 4 - четырехграммами и так далее. В общем случае группы значности  называются -граммами.

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

Очевидно, что код, позволяющий зашифровать на уровне слов произвольный открытый текст, должен иметь объем, сравнимый с подробным словарем естественного языка, что для практического применения неудобно, тем более, если учесть, что коды традиционно относятся к ручным системам шифрования, т.е. не рассчитаны на использование средств автоматизации. В этой связи, при составлении кода основным этапом является изучение словарного состава будущей переписки, в результате чего определяется набор слов и фраз, подлежащих занесению в список словарных величин. Чем ярче выражена специфика переписки, тем компектнее и удобнее в использовании код. На практике это приводит к «специализации» кодов, то есть к тому, что не всякий открытый текст может быть качественно зашифрован с помощью конкретного кода. С другой стороны, преимуществом кодов является сжатие информации при зашифровании, поскольку кодовые группы, как правило короче величин, которые они заменяют. Как и любой другой шифр, код может быть тем или иным образом модифицирован. Он может быть усложнен, например, за счет использования различных кодовых групп для зашифрования одной и той же открытой величины. Выбор кодовой группы из соответствующего списка производится случайным образом.

Аналогичная процедура, называемая рандомизацией, может применяться для преобразования открытого текста перед зашифрованием независимо от системы шифра. Преобразование заключается в том, что знаки открытого текста заменяются на символы другого алфавита, большего по объему, чем исходный. В процессе замены конкретная буква переходит случайным образом в один из связанных с ней символов. Количество таких символов для каждой буквы различно и пропорционально частоте ее встречаемости в исходном открытом тексте. В результате получается последовательность, все знаки которой встречаются примернo с одинаковой частотой. Рандомизация модет быть введена в любую криптографическую систему, и ее использование, затрудняет раскрытие шифра на основе статистического анализа.

Шифры замены часто приводятся в специальной и популярной литературе в качестве примеров слабых шифров. Необходимо отметить, что, как и для любого другого шифра, это может быть верным лишь в конкретных случаях. Например, алгоритмы DES, ГОСТ 28147-89 базируются на шифре замены, а алгоритм шифрования RSA реализует этот шифр непосредственно.