ИнфТехнКомпТехн

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

Рис. 6.1 – Классификация корректирующих кодов Равномерные блочные коды делятся на разделимые и неразделимые. В разделимых

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

Примерами систематических кодов являются коды хемминга и циклические. Последние реализуются наиболее просто, что и привело к их широкому использованию в узо. Для систематического кода применяется обозначение (n,k) – код, где n – число элементов в комбинации; k – число информационных элементов.

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

Код хемминга

Рассмотрим в качестве примера построение систематического кода с кодовым расстоянием d0=3 (кода хемминга). Пусть число сообщений, которое необходимо передать, равно 16. Тогда необходимое число информационных элементов k=log2na=4. Можно выписать все 16 кодовых комбинаций, включая нулевую (0000). Это один из возможных способов задания исходного (простого) кода. Другой способ заключается в выписывании только четырех кодовых комбинаций простого кода в виде матрицы, называемой единичной:

1 0 0 0

0 1 0 0

(6.1)

0 0 1 0

0 0 0 1

151

Суммируя по модулю два в различном сочетании кодовые комбинации, входящие в единичную матрицу, можно получить 15 кодовых комбинаций, 16-я – нулевая. Кодовые комбинации, составляющие матрицу (6.1), линейно независимы. Можно было бы составить матрицу и из других кодовых комбинаций (лишь бы они были линейно независимыми). Ненулевые комбинации a1, a2, a3, a4 линейно независимые, если q1a1 q2a2 q3a3 q4a4≠0, где qi {0,1} при условии, что хотя бы один из коэффициентов qi≠0. Дополним каждую

кодовую комбинацию в (6.1) проверочными элементами так, чтобы обеспечивалось d0=3. Будем иметь в виду также тот факт, что к числу разрешенных комбинаций корректирующего кода принадлежит и комбинация 0000...0, называемая нулевой. Очевидно, что в числе добавляемых проверочных элементов должно быть не менее двух единиц. Тогда общее число единиц в каждой комбинации кода получим не меньше трех и комбинации, полученные нами, будут отличаться от нулевой, по крайней мере, в трех элементах. Добавим по две единицы к каждой строке матрицы (6.1):

	1	0	0	0	1
	0	1	0	0	1	,	(6.2)
	0	0	1	0	1
	0	0	0	1	1

Складывая строки 1 и 2 матрицы (6.2) по модулю два

Видим, что они отличаются только в двух элементах, т.е. Заданное кодовое расстояние не обеспечивается. Дополним каждую строку проверочными элементами так, чтобы d0=3. Тогда матрица примет вид

	1	0	0	0	1	1	1
	0	1	0	0	1	0	1	.	(6.3)
	0	0	1	0	0	1	1
	0	0	0	1	1	1	0

Добавляемые проверочные элементы могут быть записаны и в другом порядке. Необходимо лишь обеспечить d0=3.

Матрицу (6.3) называют производящей, или порождающей, матрицей кода (6,4), содержащего семь элементов, из которых четыре информационных. Обычно матрицу обозначают буквой g с индексом, указывающим, к какому коду она относится (в нашем случае g(7,4)). Производящая матрица состоит из двух матриц - единичной (размерности k·k) и с(r,k), содержащей r столбцов и k строк. Суммируя в различном сочетании строки матрицы (6.3), получаем все (кроме нулевой) комбинации корректирующего кода с d0=3.

Обозначим элементы комбинации полученного семиэлементного кода a1, a2, a3, a4, a5, a6, a7, из которых a1, a2, a3, a4 – информационные и a5, a6, a7 – проверочные. Последние могут быть получены путем суммирования по модулю два определенных информационных элементов. Разумеется, правило формирования проверочного элемента ai для любой кодовой комбинации одинаково.

Найдем правило формирования элемента a5, пользуясь матрицей (6.3). Из первой строки следует, что в суммировании должен обязательно участвовать элемент a1 (только в

152

этом случае a5=1), из второй - что элемент a3 в суммировании не должен участвовать, а из четвертой - что элемент a4 должен участвовать в суммировании. Итак,

a5	a1 a2		a4.	(6.4)
уравнения для a6 и a7 по аналогии записываются в виде:
a6	a1	a3	a4,	(6.5)
a7	a1	a2	a3.	(6.6)
алгоритм			формирования	проверочных элементов a5, a6, a7 может быть задан

матрицей, называемой проверочной. Эта матрица содержит r строк и n столбцов. Применительно к сформированному нами коду (6,4) она имеет вид:

	1	1	0	1	1	0	0
B(6,4)	1	0	1	1	0	1	0	.
	1	1	1	0	0	0	1

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

a1 a2 a4 a5.

Процедура обнаружения ошибок основана на использовании проверок (12.4)-(12.6). Очевидно, что проверочные элементы, сформированные из принятых информационных, при отсутствии ошибок должны совпадать с принятыми проверочными.

Пример 6.3 переданная кодовая комбинация имеет вид 1000111 (первая строка

матрицы

(2.3)).

В

результате

действия

помех

на приемном конце имеем

a1

,a2

,a3

,a4

,a5

,a6,a7 1100111. Произведем проверки (12.4)-(12.6):

1 1 0 0 a5 ,

(6.7)

a1

a2

a4

a1 a3 a4 1 0 0 1 a6 ,

(6.8)

1 1 0 0 a7.

(6.9)

a1

a2

a3

1, т.е. a5

В то же время a5

1, a6 1,

a7

a5,

a7 a7, что говорит о наличии ошибок

в принятой кодовой комбинации. При отсутствии в принятой кодовой комбинации ошибок a5 a5 b1 0, a6 a6 b2 0, a7 a7 b3 0.

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

Вид ненулевого синдрома определяется характером ошибок в кодовой комбинации. В нашем случае вид синдрома зависит от местоположения одиночной ошибки. В таблице 6.2 отражено соответствие между местоположением одиночной ошибки для кода, заданного матрицей (6.3), и видом синдрома.

Таблица 6.2 – местоположение ошибки и вид синдрома

	Номер элемента, в котором	1	2	3	4	5	6	7
	произошла ошибка
	Вид синдрома	111	101	110	011	001	010	100

Таким образом, зная вид синдрома, можно определить место, где произошла ошибка, и исправить принятый элемент на противоположный.

153

Пример 6.4 передавалась кодовая комбинация 1000111. Принята кодовая комбинация 0000111. Синдром имеет вид 111. В соответствии с таблицей 6.2 исказился первый элемент (a1). Изменим первый элемент на противоположный:

Полученная в результате исправления ошибки кодовая комбинация совпадает с переданной.

Рассмотренный код (6,4) гарантированно обнаруживает двукратные ошибки, а исправляет только однократные ошибки.

Циклические коды

В теории циклических кодов кодовые комбинации обычно представляются в виде полинома. Так, n-элементная кодовая комбинация записывается в виде

A(x) an 1xn 1 an 2xn 2 ... a1x a0,

Где ai={0,1}, причем ai=0 соответствуют нулевым элементам комбинации, а ai=1 – ненулевым. Например, комбинациям 1101 и 1010 соответствуют многочлены

A1(x) x3 x2 1 и A2 (x) x3 x.

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

A1(x) A2 (x) x3 x2 1 x3 x x2 x 1,

Поскольку x3 x3 x3 1 1 0. рассмотрим операцию деления на следующем примере:

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

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

исправлении ошибок.
Найдем алгоритмы построения циклического кода,		удовлетворяющего
перечисленным выше условиям. Задан полином	P(x) ar 1xr ar 2xr 1 ... 1,

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

Обозначим многочлен, соответствующий комбинации простого кода, q(x). Возьмем произведение q(x)xr и разделим его на р(х). В результате получим многочлен g(х) и остаток r(х)/р(х):

154

Q(x)xr		R(x)
	G(x)		.	(6.10)
P(x)		P(x)

Умножим левую и правую части на p(x), тогда (6.10) перепишется в виде

Q(x)xr G(x)P(x) R(x).	(6.11)
перепишем равенство (6.11) в виде
G(x)P(x) Q(x)xr R(x).	(6.12)

левая часть (2.12) делится без остатка на p(x), значит, без остатка делится и правая часть. Из (6.12) вытекают два способа формирования комбинаций циклического кода: путем умножения многочлена g(x) на p(x) и путем деления q(x)xr на p(x) и приписывания к q(x)xr остатка от деления r(x).

Пример 6.5 задан полином g(x)=x3+x, соответствующий комбинации простого кода. Сформировать комбинацию циклического кода (7,4) с производящим полиномом р(х)=х3+х2+1. Можно получить комбинацию циклического кода в виде g(x)p(x)=(x3+x)(x3+x2+1)=x6+x5+x4+x. Однако в полученной комбинации нельзя отделить информационные элементы от проверочных, и код получается неразделимым.

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

1)		G(x)xr=(x3+x)x3=x6+x4;
2)

3) (x6+x4+1) – комбинация циклического кода, полученная методом деления на производящий полином. Она может быть переписана в виде 1010001. Первые четыре элемента – информационные, последние три - проверочные, т.е. Полученный код – разделимый.

Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях также сделать вывод о характере ошибки и исправить ее.

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

v.41 в системах пд с ос рекомендуется применять код с производящим полиномом p(x)=x16+x12+x5+1.

Эффективность применения корректирующих кодов

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

155

Pош(n) 1 1 pош k ,

Где pош – вероятность неправильного приема единичного элемента; k – число элементов в комбинации простого кода. При применении систематических корректирующих кодов к исходной кодовой комбинации добавляются проверочные элементы, позволяющие исправлять или обнаруживать ошибки. Так, если код используется в режиме исправления ошибок и кратность исправляемых ошибок tи.ош, то вероятность неправильного приема кодовой комбинации

	n
Pош(и)	Cnt pош 1 pош n t .

ttи.ош 1

Врезультате применения корректирующего кода в режиме исправления ошибок

P(n)

вероятность ошибки уменьшается в kи раз: Kи ош 1. однако это достигается за счет

Pош(и)

увеличения затрат на реализацию системы и снижения скорости передачи информации. Если в системе с простым кодом скорость равна сп, то в системе с корректирующим кодом скорость ск=сп·γ1, где γ1=k/n – коэффициент, характеризующий потери скорости вследствие введенной в код избыточности. Чем больше избыточность (меньше γ1), тем меньше скорость передачи информации, т.е. Тем меньше в единицу времени передается полезной информации.

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

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

Контрольные вопросы и задания

1.Какие методы защиты от ошибок вам известны?

2.Каково необходимое условие для того, чтобы код был способен обнаруживать ошибки?

3.В чем отличие понятий расстояние хемминга и кодовое расстояние?

4.Какова связь между кратностью обнаруживаемых и исправляемых ошибок и кодовым расстоянием?

5.Постройте производящую матрицу для кода, у которого d0=3, k=5.

6.Запишите синдром для кода (7,4), для которого a5=a1+a2, a6=a1+a3, a7=a1+a2+a3, при появлении ошибки в a3.

7.Запишите кодовую комбинацию циклического кода, у которого р(х)=х3+х+1, а исходная кодовая комбинация имеет вид 1111.

8.Определите содержит или нет принятая кодовая комбинация циклического кода

1111000 ошибки, если р(х)=х3+х2+1.

9.Выполните задания п.5-8 в соответствии с данными, полученными от преподавателя.

156

Лабораторная работа № 7. Защита информации

Введение

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

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

Исследование основных методов криптографической зашиты информации.

Краткие сведения из теории

Криптография – обеспечивает сокрытие смысла сообщения с помощью шифрования и открытия его расшифрованием, которые выполняются по специальным алгоритмам с помощью ключей.

Ключ – конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования данных, обеспечивающее выбор только одного варианта из всех возможных для данного алгоритма.

Криптоанализ – занимается вскрытием шифра без знания ключа (проверка устойчивости шифра).

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

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

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

Вкриптографии используются следующие основные алгоритмы шифрования:

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

Алгоритм перестановки – символы шифруемого текста переставляются по определенному правилу в пределах некоторого блока этого текста;

Гаммирование – символы шифруемого текста складываются с символами некоторой случайной последовательности;

Аналитическое преобразование – преобразование шифруемого текста по некоторому аналитическому правилу (формуле).

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

157

Симметричные криптосистемы Шифры перестановки

В шифрах средних веков часто использовались таблицы, с помощью которых выполнялись простые процедуры шифрования, основанные на перестановке букв в сообщении. Ключом в данном случае является размеры таблицы. Например, сообщение “неясное становится еще более непонятным” записывается в таблицу из 5 строк и 7 столбцов по столбцам.

Н	О	Н	С	Б	Н		Я
Е	Е	О	Я	О	Е		Т
Я	С	В	Е	Л	П		Н
С	Т	И	Щ	Е	О		Ы
Н	А	Т	Е	Е	Н		М
			Рис. 7.1 – шифр перестановки

Для получения шифрованного сообщения текст считывается по строкам и группируется по 5 букв:

Нонсб няеео яоетя свелп нстищ еоына теенм

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

Л

У

Н

А

Т

И

К

А

И

К

Л

Н

Т

У

4

7

5

1

6

2

3

1

2

3

4

5

6

7

Н

О

Н

С

Б

Н

Я

С

Н

Я

Н

Н

Б

О

Е

Е

О

Я

О

Е

Т

Я

Е

Т

Е

О

О

Е

Я

С

В

Е

Л

П

Н

Е

П

Н

Я

В

Л

С

С

Т

И

Щ

Е

О

Ы

Щ

О

Ы

С

И

Е

Т

Н

А

Т

Е

Е

Н

М

Е

Н

М

Н

Т

Е

А

до перестановки

после перестановки

Рис. 7.2 – метод одиночной перестановки

158

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

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

2

4

1

3

1

2

3

4

1

2

3

4

4

П

Р

И

Е

4

И

П

Е

Р

1

А

З

Ю

Ж

1

З

Ж

А

Ю

1

А

3

Ю

Ж

2

Е

_

С

Ш

2

_

Ш

Е

С

2

.

_

С

Ш

3

Г

Т

О

О

3

Т

О

Г

О

3

Г

Т

О

О

4

И

П

Е

Р

Рис. 7.3 – двойная перестановка столбцов и строк

Врезультате перестановки получена шифровка азюже_сшгтооипер. Ключом к шифру служат номера столбцов 2413 и номера строк 4123 исходной таблицы.

Число вариантов двойной перестановки достаточно быстро возрастает с увеличением размера таблицы: для таблицы 3х3 их 36, для 4х4 их 576, а для 5x5 их 14400.

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

16	3	2	13			О	И	Р		Т
5	10	11	8			З	Ш	Е		Ю
9	6	7	12			_	Ж	А		С
4	15	14	1			Е	Г	О		П
									159

П	Р	И	Е	З	Ж	А	Ю	_	Ш	Е	С	Т	О	Г	О
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

Рис. 7.4 – магические квадраты Число магических квадратов очень резко возрастает с увеличением размера его

сторон: для таблицы 3х3 таких квадратов - 1; для таблицы 4х4 - 880; а для таблицы 5х5 - 250000.

Шифры простой замены Система шифрования цезаря - частный случай шифра простой замены. Метод основан

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

Известная фраза юлия цезаря veni vini vici – пришел, увидел, победил, зашифрованная с помощью данного метода, преобразуется в sbkf sfaf sfzf (при смещении на 4 символа).

Греческим писателем полибием за 100 лет до н.э. Был изобретен так называемый полибианский квадрат размером 5х5, заполненный алфавитом в случайном порядке. Греческий алфавит имеет 24 буквы, а 25-м символом является пробел. Для шифрования на квадрате находили букву текста и записывали в шифротекст букву, расположенную ниже ее в том же столбце. Если буква оказывалась в нижней строке таблицы, то брали верхнюю букву из того же столбца.

Шифры сложной замены

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

Пусть в качестве ключа используется группа из трех цифр – 314, тогда Сообщение совершенно секретно Ключ 3143143143143143143

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

сообщения применяется свой шифр простой замены (свой алфавит).

	Абвгдеёжзиклмнопрстуфхчшщъыьэюя_
А	Абвгдеёжзиклмнопрстуфхчшщъыьэюя_
Б	_абвгдеёжзиклмнопрстуфхчшщъыьэюя
В	Я_абвгдеёжзиклмнопрстуфхчшщъыьэю
Г	Юя_абвгдеёжзиклмнопрстуфхчшщъыьэ
.	…………
Я	Вгдеёжзиклмнопрстуфхчшщъыьэюя_аб
_	Бвгдеёжзиклмнопрстуфхчшщъыьэюя_а
		замены
	Рис. 7.5 – шифр многоалфавитной
	160