Информационная безопасность / Общий_лекция

111

При этом полагается, что

Функцию Эйлера можно также представить в виде так называемого произведения Эйлера:

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

Некоторые значения функции

			+0		+1		+2		+3		+4		+5		+6		+7		+8		+9
	0+			1		1		2		2		4		2		6		4		6
	10+	4		10		4		12		6		8		8		16		6		18
		8		12		10		22		8		20		12		18		12		28
	20+
	30+	8		30		16		20		16		24		12		36		18		24
	40+	16		40		12		42		20		24		22		46		16		42
		20		32		24		52		18		40		24		36		28		58
	50+
		16		60		30		36		32		48		20		66		32		44
	60+
	70+	24		70		24		72		36		40		36		60		24		78
	80+	32		54		40		82		24		64		42		56		40		88
		24		72		44		60		46		72		32		96		42		60
	90+

Свойства функции Эйлера

1.	,	если — простое	число.	В
частности, при имеем		;
2.	,	если и взаимно просты. То есть
Функция Эйлера мультипликативна;
3.		, если и взаимно	просты.	Так
называемая теорема Эйлера;

4.

5.

, если — наименьшее общее кратное, a — наибольший общий делитель.

Асимптотические соотношения

1. где — некоторая константа;

112

2.

3.

4.

Тема 2.2. Симметричные методы криптографии.

1. Виды симметричных криптографических систем.

2.Шифры перестановки

2.1.Шифрующие таблицы

2.2.Применение магических квадратов

3.Шифры подстановки (одноалфавитные и многоалфавитные)

4.Гаммирование.

1. Виды симметричных криптографических систем.

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

Все многообразие существующих симметричных криптографических методов можно свести к следующим классам преобразований:

Подстановки

Гаммирование

Симметричные

криптосистемы

Перестановки

Блочные шифры

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

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

113

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

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

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

Блочные шифры на практике встречаются чаще, чем “чистые” преобразования того или иного класса в силу их более высокой криптостойкости. Российский и американский стандарты шифрования основаны именно на этом классе шифров.

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

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

114

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

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

Σ = {а0, a1, а2, ..., am-1}.

При выполнении криптографических преобразований полезно заменить буквы алфавита целыми числами 0,1,2,3,.... Это позволяет упростить выполнение необходимых алгебраических манипуляций. Например, можно установить взаимно однозначное соответствие между русским алфавитом Σ РУС.= {АБВГДЕ... ЮЯ} и множеством целых

Z32 = {0,1,2,3,..., 31};

между английским алфавитом

ΣАНГЛ. = {ABCDEF... YZ} и множеством целых

Z26 = {0,1.2.3…….. 25}

(см. табл. 2.1 и 2.2).

В дальнейшем будет обычно использоваться алфавит

Zm = {0, 1.2.3, ....m-1},

содержащий m "букв" (в виде чисел}.

Замена букв традиционного алфавита числами позволяет более четко сформулировать основные концепции и приемы криптографических преобразований.

	Таблица 2.1
Соответствие между русским алфавитом и множеством целых
			Z,, = {0,1.2,3 ............................... 31}
Буква		Число		Буква	Число	буква	ЧИСЛО	Буква	Число
А		0		И	8	Р	16	Ш	24
Б		1		Й	9	С	17	Щ	25
В		2		К	10	Т	18	Ь	26
Г		3		Л	11	У	19	Ы	27
Д		4		М	12	Ф	20	Ъ	28
Е		5		Н	13	X	21	Э	29
Ж		6		О	14	Ц	22	Ю	30
3		7		П	15	Ч	23	Я	31

Таблица 2.2
Соответствие между английским алфавитом и множеством целых
Z26 = {0, 1, 2, 3	25}

115

Буква	Число	Буква	Число	Буква	Число
А	0	J	9	S	18
В	1	К	10	т	19
С	2	L	11	и	20
D	3	М	12	V	21
Е	4	N	13	W	22
F	5	О	14	X	23
G	6	Р	15	Y	24
Н	7	Q	16	Z	25
1	8	R	17

Объединяя по определенному правилу буквы из алфавита Z, можно создать новые алфавиты:

• алфавит Σ 2, содержащий т2 биграмм a0a0l a0a1 am_1am_1;

• алфавит Σ 3, содержащий m3 триграмм a0a0a0 a0a0al am_1am_1am_1

В общем случае, объединяя по n букв, получаем алфавит Zn. содержащий mn n-грамм [95].

Например, английский алфавит

ΣАНГЛ. = {ABCDEFGH ... WXYZ}

объемом m =26 букв позволяет сгенерировать посредством операции конкатенации алфавит из 262=676 биграмм

АА, АВ. XZ, ZZ,

алфавит из 263 = 17576 триграмм

ААА.ААВ ZZX.ZZZ и т.д.

Таким образом, текст с n буквами из алфавита Zm можно рассматривать как n-грамму

Х (Хо, X1, Х2, ..., Хn-1),

где Xi є Zm, 0 < i < n, для некоторого целого n =1, 2, 3

Через Zmn будем обозначать множество n-грамм, образованных из букв множества Zm.

Криптографическое преобразование Е представляет собой совокупность

преобразований

Е = {Е(n): 1 < n < оо},

E(n):Zmin→Zm.n. (2.1)

Преобразование Е(n) определяет, как каждая n-грамма открытого текста

х є Zmn заменяется п-граммой шифртекста у, т. е.

у = Е(n)(х), причем x,y є Zmn,

при этом обязательным является требование взаимной однозначности преобразования Е(n) на множестве Zm n.

Криптографическая система может трактоваться как семейство криптографических преобразований

Е = { Е к : К є К },

(2.2)

помеченных параметром К, называемым ключом.

116

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

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

2. Шифры перестановки

При шифровании перестановкой символы шифруемого текста переставляются по определенному правилу в пределах блока этого текста. Шифры перестановки являются самыми простыми и, вероятно, самыми древними шифрами.

Перестановкой набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для того чтобы показать, что целое i перемещено из позиции i в позицию (i), где 0 (i) < n, будем использовать запись

=( (0), (1),..., (N-1)).

Число перестановок из (0,1,...,N-1) равно n!=1*2*...*(N-1)*N. Введем обозначение для взаимно-однозначного отображения (гомоморфизма)

набора S={s0,s1, ...,sN-1}, состоящего из n элементов, на себя.

: S S

: si s (i), 0 i < n

Будем говорить, что в этом смысле является перестановкой элементов S. И, наоборот, автоморфизм S соответствует перестановке целых чисел

(0,1,2,.., n-1).

Криптографическим преобразованием T для алфавита Zm называется

последовательность автоморфизмов: T={T(n):1 n< }

T(n): Zm,n Zm,n, 1 n<

Каждое T(n) является, таким образом, перестановкой n-грамм из Zm,n. Поскольку T(i) и T(j) могут быть определены независимо при i j, число криптографических преобразований исходного текста размерности n равно (mn)!. (Здесь и далее m – объем используемого алфавита). Оно возрастает непропорционально при увеличении m и n: так, при m=33 и n=2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.

Практическая реализация криптографических систем требует, чтобы преобразования {Tk: k K} были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).

117

2.1. Шифрующие таблицы

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

В качестве ключа в шифрующих таблицах используются:

•размер таблицы;

•слово или фраза, задающие перестановку;

•особенности структуры таблицы.

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

ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ

записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рис. 2.1.

Т	Н	П	В	Е	Г	Л
Е	А	Р	А	Д	О	Н
Р	Т	И	Е	Ь	В	О
М	О	Б	Т	М	П	Ч
И	Р	Ы	С	О	О	Ь

Рис. 2.1. Заполнение таблицы из 5 строк и 7 столбцов

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

ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ

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

118

расшифровании действия выполняют в обратном порядке.

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

Применим в качестве ключа, например, слово ПЕЛИКАН,

а текст сообщения возьмем из предыдущего примера. На рис. 2.2 показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблицазаполнению после перестановки.

Рис. 2.2. Таблицы, заполненные ключевым словом и текстом сообщения

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

При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение:

ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ

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

119

расшифровании порядок перестановок должен быть обратным.

Пример выполнения шифрования методом двойной перестановки показан на рис. 2.3. Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее:

ТЮАЕ ООГМ РЛИП ОЬСВ Ключом к шифру двойной перестановки служит последовательность номеров

столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

Рис. 2.3. Пример выполнения шифрования методом двойной перестановки

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:

• для таблицы 3x3 36 вариантов; Ъ для таблицы 4x4 576 вариантов;

• для таблицы 5x5 14400 вариантов.

Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто "взламывается" при любом размере таблицы шифрования.

2.2. Применение магических квадратов

В средние века для шифрования перестановкой применялись и магические квадраты.

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

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

120

Пример магического квадрата и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО показан на рис. 2.4.

Рис. 2.4. Пример магического квадрата 4x4 и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО

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

ОИРМ ЕОСЮ ВТАЬ ЛГОП Число магических квадратов быстро возрастает с увеличением размера

квадрата. Существует только один магический квадрат размером 3x3 (если не учитывать его повороты). Количество магических квадратов 4x4 составляет уже 880, а количество магических квадратов 5x5-около 250000.

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

3. Шифры подстановки.

При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем протяжении текста. Часто шифры простой замены называют шифрами одноалфавитной подстановки.

3.1. Одноалфавитные подстановки.

Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки).