Порядок выполнения практического занятия

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

Задачи для решения

6.1. Сформируйте ЦИК символов А, В и СASCIIпри условии использования образующего полиномаx⁴+x+ 1.

6.2. Найдите разрешенные комбинации ЦИК при n= 5 и образующем полиномеx³+x+ 1.

6.3. Вычислите коды синдромов ЦИК, характеристики которого приведены в условии задачи 6.2.

6.4. Определите, какие из следующих кодовых комбинаций ЦИК с образующим полиномом x⁴+x+ 1 содержат ошибки:

100000000001, 110001100011, 100001011011, 111111110100, 100010000101.

6.5. Сформируйте ЦИК БЧХ символовA,BиCASCII, позволяющие обнаруживать и корректировать до 2-х ошибок в блоке. Информационное поле ЦИК представлять 7-ю битами.

6.6. Для ЦИК БЧХ, обеспечивающего коррекцию до 2-х ошибок в 15-битовом блоке, вычислите коды синдрома, соответствующие искажению:

- бита i₂;

- бита c₅;

- битов i₂иc₅одновременно.

6.7. Определите, какие из следующих кодовых комбинаций ЦИК БЧХ с образующим полиномомx⁸+x⁷+x⁶ +x⁴+ 1 содержат ошибки:

000011101000100, 100000010000000, 010110101011001, 000111010001000.

6.8. Сформируйте ЦИК БЧХ символа А ASCII, обеспечивающий обнаружение и коррекцию до 3-х ошибок.

Практическое занятие №7 Изучение примеров криптографического кодирования

Цель занятия: практическое исследование примеров криптографических кодов.

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

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

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

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

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

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

- перестановке (транспозиции) символов шифруемого сообщения между собой по определенному алгоритму;

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

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

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

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

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

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

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

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

2. Символы ключа ранжируются аналогично тому, как это было выполнено при шифровании.

3. Зашифрованное сообщение делится на фрагменты по kсимволов в каждом, гдеk– число строк в восстанавливаемой таблице. После этого осуществляется собственно ее восстановление, в соответствии со следующим правилом: в качествеi-го столбца таблицы выступаетj-й фрагмент зашифрованного сообщения, гдеj– рангi-го символа ключа.

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

Пусть необходимо зашифровать методом постолбцовой транспозиции сообщение «ПИАНИСТКА НА СВЯЗЬ НЕ ВЫШЛА».В качестве ключа используется слово«ЮСТАС».Пробелы между словами игнорируются.

Решение. Ранжируем символы ключа по их порядковым номерам в алфавите. Буквам ключа с первой по пятую присваиваем ранги 5, 2, 4, 1 и 3 соответственно.

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

Таблица 7.1 – Пример шифровальной таблицы метода постолбцовой транспозиции

Номер столбца, соответствующая ему буква ключа и присвоенный ей ранг
1(Ю; 5)	2 (С; 2)	3 (Т; 4)	4 (А; 1)	5 (С; 3)
П С А Ь Ш	И Т С Н Л	А К В Е А	Н А Я В А	И Н З Ы Б

На базе таблицы 4.1 составляем шифрованное сообщение, выписывая ее столбцы в порядке возрастания рангов соответствующих им букв ключа, т.е. в следующем: 4-й, 2-й, 5-й, 3-й, 1-й. В итоге получаем результирующую последовательность символов: НАЯВАИТСНЛИНЗЫБАКВЕАПСАЬШ.

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

Среди других методов шифрования, основанных на принципе перестановки, сравнительно широко известен также шифр, называемый решеткой Кардано [5].

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

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

В качестве ключа в рассматриваемых методах может использоваться:

- некоторое заранее выбранное слово (лозунг);

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

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

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

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

Таблица 7.2 – Таблица Виженера для латинского алфавита

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

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

i_J+k_J - 1, еслиi_J+k_Jm+ 1,

c_J= (7.1)

i_J+k_J-m- 1, еслиi_J+k_J>m+ 1,

где i_J,k_Jиc_J- порядковые номера по алфавитуj-го символа соответственно шифруемого сообщения, ключевой последовательности и зашифрованного сообщения;

m– общее число символов в используемом алфавите.

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

c_J-k_J + 1, если с_Jk_J,

d_J= (7.2)

m– (k_J-c_J) + 1, если с_J<k_J,

где d_J- порядковый номер по алфавитуj-го символа расшифрованного сообщения.

Поясним шифрование по таблице Виженера конкретным примером. Пусть необходимо зашифровать сообщение«MEET ME TOMORROW»с помощью таблицы 7.2, используя в качестве ключа слово«COMPUTER».Пробелы в шифруемом сообщении опустить.

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

Таблица 7.3 – Пояснения к процессу шифрования по таблице Виженера

Текущий символ ключа	Текущий символ шифруемого сообщения	Текущий символ зашифрованного сообщения
C	M	O
O	E	S
M	E	Q
P	T	I
U	M	G
Т	Е	Х
E	T	X
R	O	F
C	M	O
O	O	C
M	R	D
P	R	G
U	O	I
T	W	P

Таким образом, получаем следующее шифрованное сообщение:

OSQIGXXFOCDGIP.

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

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

i_J+k_J, еслиi_J+k_Jm,

c_J= (7.3)

i_J+k_J -m, еслиi_J+k_J>m,

где i_J,k_Jиc_J- порядковые номера по алфавитуj-го символа соответственно шифруемого сообщения, ключевой последовательности и зашифрованного сообщения;

m– общее число символов в используемом алфавите.

Декодирование сообщения, зашифрованного данным методом, осуществляется следующим образом:

c_J-k_J, еслиc_J>k_J,

d_J= (7.4)

m– (k_J-c_J), еслиc_Jk_J,

где d_J– порядковый номер по алфавитуj-го символа расшифрованного сообщения.

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

Решение. Так как шифруемое сообщение содержит 23 символа, а ключ – 5, ключевую последовательность формируем путем пятикратного повторения ключа. Собственно шифрование осуществляем в соответствии с выражением (7.3). Процесс шифрования поясняется таблицей 7.3.

Таблица 7.3 – Пояснения к процессу шифрования методом суммирования

Текущий символ ключа и его номер по алфавиту	Текущий символ шифруемого сообщения и его номер по алфавиту	Номер по алфавиту текущего символа шифрованного сообщения	Текущий символ шифрованного сообщения
1	2	3	4
Ю ( 32 )	П ( 17 )	32 + 17 – 33 = 16	О
С ( 19 )	И ( 10 )	19 + 10 = 29	Ы
Т ( 20 )	А ( 1 )	20 + 1 = 21	У

Окончание таблицы 7.3

1	2	3		4
А ( 1 )	Н ( 15 )	1 + 15 = 16		О
С ( 19 )	И ( 10 )	19 + 10 = 29		Ы
Ю ( 32 )	С ( 19 )	32 + 19 –33 = 18		Р
С ( 19 )	Т ( 20 )	19 + 20 – 33 = 6		Е
Т ( 20 )	К ( 12 )	20 + 12 = 32		Ю
А ( 1 )	А ( 1 )	1 + 1 = 2		Б
С ( 19 )	Н ( 15 )	19 + 15 – 33 = 1		А
Ю ( 32 )	А ( 1 )		32 + 1 = 33	Я
С ( 19 )	С ( 19 )		19 + 19 – 33 = 5	Д
Т ( 20 )	В ( 3 )		20 + 3 = 23	Х
А ( 1 )	Я ( 33 )		1 + 33 – 33 = 1	А
С ( 19 )	З ( 9 )		19 + 9 = 28	Ъ
Ю ( 32 )	Ь ( 30 )		32 + 30 – 33 = 29	Ы
С ( 19 )	Н ( 15 )		19 + 15 – 33 = 1	А
Т ( 20 )	Е ( 6 )		20 + 6 = 26	Ш
А ( 1 )	В ( 3 )		1 + 3 = 4	Г
С ( 19 )	Ы ( 29 )		19 + 29 – 33 = 15	Н
Ю ( 32 )	Ш ( 26 )		32 + 26 – 33 = 25	Ч
С ( 19 )	Л ( 13 )		19 + 13 = 32	Ю
Т ( 20 )	А ( 1 )		20 + 1 = 21	У

В результате получаем следующее шифрованное сообщение:

ОЫУОЫРЕЮБАЯДХАЪЫАШГНЧЮУ.

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