Файл: Федеральное агентство Российской Федерации по образованию гоу впо Тульский государственный университет кафедра электронных вычислительных машин.pdf

54
ЛАБОРАТОРНАЯ РАБОТА №10
CRC-АЛГОРИТМЫ ОБНАРУЖЕНИЯ ОШИБОК
1. ЦЕЛЬ РАБОТЫ
Изучить применение циклических избыточных кодов для обнаружения ошибок в передаваемых сообщениях.
2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Циклический избыточный код (Cyclical Redundancy Check — CRC) имеет фиксированную длину и используется для обнаружения ошибок.
Наибольшее распространения получили коды CRC-16 и CRC-32, имеющие длину 16 и 32 бита соответственно. Код CRC строится по исходному сообщению произвольной длины, т.е. этот код не является блочным в строгом смысле этого слова. Но при каждом конкретном применении этот код — блочный, (m, т + 16)-код для CRC-16 или (т, т + 32)-код для CRC-32.
Вычисление значения кода CRC происходит посредством деления многочлена, соответствующего исходному сообщению
(полином- сообщение), на фиксированный многочлен (полином-генератор). Остаток от такого деления и есть код CRC, соответствующий исходному сообщению.
Для кода CRC-16 полином-генератор имеет степень 16, а для CRC-32 — 32.
Полиномы-генераторы подбираются специальным образом и для кодов CRC-
16/32 стандартизированы Международным консультативным комитетом по телеграфной и телефонной связи (CCITT).
Существуют быстрые алгоритмы для расчета CRC-кодов, исполь- зующие специальные таблицы, а не деление многочленов с остатком.
CRC-коды способны обнаруживать одиночную ошибку в любой по- зиции и, кроме того, многочисленные комбинации кратных ошибок, расположенных близко друг от друга. При реальной передаче или хранении информации ошибки обычно группируются на некотором участке, а не распределяются равномерно по всей длине данных. Таким образом, хотя для идеального случая двоичного симметричного канала CRC-коды не имеют никаких теоретических преимуществ по сравнению, например, с простыми контрольными суммами, для реальных систем эти коды являются очень полезными.
Коды CRC используются очень широко: модемами, телекоммуника- ционными программами, программами архивации и проверки целостности данных и многими другими программными и аппаратными компонентами вычислительных систем.
Как уже было указано, основная идея алгоритма CRC состоит в представлении сообщения виде огромного двоичного числа, делении его на другое фиксированное двоичное число и использовании остатка этого деления в качестве контрольной суммы. Получив сообщение, приемник

55 может выполнить аналогичное действие и сравнить полученный остаток с
«контрольной суммой» (переданным остатком). И хотя влияние каждого бита исходного сообщения на частное не столь существенно, остаток во время вычислений может радикально измениться, и чем больше байтов имеется в исходном сообщении (в делимом), тем сильнее меняется каждый раз величина остатка.
Ключевым словом при работе с CRC является слово «полином». Все
CRC-алгоритмы основаны на полиномиальных вычислениях, и для любого алгоритма CRC можно указать, какой полином он использует. Это значит, что вместо представления делителя, делимого (сообщения), частного и остатка в виде положительных целых чисел, можно представить их в виде полиномов с двоичными коэффициентами или в виде строки бит, каждый из которых является коэффициентом полинома. Например, десятичное число 23 в шестнадцатеричной системе счисления имеет вид 17, а в двоичном —
10111, что совпадает с полиномом:
0 1
2 3
4 1
1 1
0 1
x
x
x
x
x
⋅
+
⋅
+
⋅
+
⋅
+
⋅
или, упрощенно:
0 1
2 4
x
x
x
x
+
+
+
И сообщение, и делитель могут быть представлены в виде полиномов, с которыми как и раньше можно выполнять любые арифметические действия.
Все это очень похоже на обычную арифметику, с той лишь разницей, что основание у нас лишь предполагается, а не строго задано.
В полиномиальной арифметике связи между коэффициентами не установлены, и, поэтому, коэффициенты при каждом члене полинома становятся строго типизированными — коэффициент при x
2
имеет иной тип, чем при x
3
Если коэффициенты каждого члена полинома совершенно изолированы друг от друга, то можно работать с любыми видами полиномиальной арифметики, просто меняя правила, по которым коэффициенты работают.
Одна из таких схем — когда коэффициенты складываются по модулю 2 без переноса — то есть коэффициенты могут иметь значения лишь 0 или 1, пе- ренос не учитывается. Это называется «полиномиальная арифметика по модулю 2».
Рассмотрим пример перемножения полиномов по правилам обычной арифметики:
(
) (
)
0 1
2 3
4 5
6 0
1 3
2 3
5 3
4 6
0 1
3 0
2 3
3
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
+
+
+
⋅
+
+
+
=
=
+
+
+
+
+
+
+
+
=
+
+
⋅
+
+
По правилам обычной арифметики, коэффициент члена 3x
3
распределяется по другим членам полинома, используя механизм переноса.
В «полиномиальной арифметике по модулю 2» не известно, чему равен
«X», переносов не существует, а все коэффициенты рассчитываются по модулю 2. В результате получаем:
0 1
2 3
4 5
6
x
x
x
x
x
x
x
+
+
+
+
+
+
=

56
Таким образом, полиномиальная арифметика по модулю 2 — это фактически двоичная арифметика по модулю 2 без учета переносов.
Сложение двух чисел в CRC-арифметике полностью аналогично обычному арифметическому действия за исключением отсутствия переносов из разряда в разряд. Это означает, что каждая пара битов определяет результат своего разряда вне зависимости от результатов других пар.
Для каждой пары битов возможны 4 варианта:
0+0=0
0+1=1
1+0=1
1+1=0
(перенос отсутствует)
То же самое справедливо и для вычитания:
0-0=0
0-1=1
(зацикливание)
1-0=1
1-1=0
Фактически, как операция сложения, так и операция вычитания в CRC- арифметике идентичны операции «Исключающее ИЛИ» (eXclusive OR —
XOR), что позволяет заменить 2 операции первого уровня (сложение и вычитание) одним действием, которое, одновременно, оказывается инверсным самому себе.
Сгруппировав сложение и вычитание в одно единое действие, CRC- арифметика исключает из поля своего внимания все величины, лежащие за пределами самого старшего своего бита.
Умножение, как и в обычной арифметике, считается суммой значений первого сомножителя, сдвинутых в соответствии со значением второго сомножителя. Следует обратить внимание, что при суммировании используется CRC-сложение.
Чтобы выполнить вычисление CRC, необходимо выбрать делитель.
Делитель называется генераторным полиномом (generator polynomial), или просто полиномом, и это ключевое слово любого CRC-алгоритма.
Степень полинома W (width — ширина) (позиция самого старшего единичного бита) чрезвычайно важна, так как от нее зависят все остальные расчеты. Обычно выбирается степень 16 ил 32, так как это облегчает реализацию алгоритма на современных компьютерах. Степень полинома — это действительная позиция старшего бита, например, степень полинома
10011 равна 4, а не 5. Единственное, что необходимо сделать до начала работы — дополнить сообщение W нулевыми битами.
Рассмотрим пример:
Исходное сообщение
: 1101011011
Полином
: 10011
Сообщение, дополненное W битами : 11010110110000

57
В результате получаем частное, которое отбрасывается за ненадобностью, и остаток, который и используется в качестве контрольной суммы. Как правило, контрольная сумма добавляется к сообщению и вместе с ним передается по каналам связи. В данном случае будет передано следующее сообщение: 11010110111110.
Таким образом, при вычислении CRC необходимо выполнить следующие действия:
1.
Выбрать степень полинома W и полином G (степени W).
2.
Добавить к сообщению W нулевых битов. Назовем полученную строку M'.
3.
Поделим M' на G с использованием правил CRC-арифметики.
Полученный остаток и будет контрольной суммой.
На другом конце канала приемник может сделать одно из равноценных действий:
1.
Выделить текст собственно сообщения, вычислить для него контрольную сумму (не забыв при этом дополнить сообщение W битами), и сравнить ее с переданной.
2.
Вычислить контрольную сумму для всего переданного сообщения (без добавления нулей), и посмотреть, получится ли в результате нулевой остаток.
Оба эти варианта совершенно равноправны.

58
3. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1.
Ознакомиться с теоретическими сведениями.
2.
Получить вариант задания у преподавателя.
3.
Выполнить задание.
4.
Продемонстрировать выполнение работы преподавателю.
5.
Оформить отчет.
6.
Защитить лабораторную работу.
4. ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ ОТЧЕТА
Отчет по лабораторной работе должен содержать следующие разделы:
•
титульный лист;
•
цель работы:
•
задание на лабораторную работу;
•
ход работы;
•
ответы на контрольные вопросы;
•
выводы по проделанной работе.
5. ЗАДАНИЕ НА РАБОТУ
В соответствии с номером варианта получить для приведенного в шестнадцатеричном формате в виде четырех пар 4-битовых чисел исходного
32-битного сообщения (таблица 15) циклический избыточный код.
Таблица 15. Варианты заданий на работу
Вариант
Последовательность символов
Полином
1 4F 4E 45 20 1
3 7
+
+
x
x
2 73 61 67 65 1
2 8
+
+
+
x
x
x
3 65 6E 63 65 1
2 3
7 8
+
+
+
+
x
x
x
x
4 61 67 65 73 1
4 5
8
+
+
+
x
x
x
5 6B 69 6E 64 1
2 4
6 7
8
+
+
+
+
+
x
x
x
x
x
6 20 74 68 65 1
4 5
9 10
+
+
+
+
+
x
x
x
x
x
6. КОНТРОЛЬНЫЕ ВОПРОСЫ
1.
Какой логической операции эквивалентны сложение и вычитание в CRC-арифметике?
2.
Чему равна степень полинома 1101111?
3.
Какая арифметическая операция является основной при вычислении циклического избыточного кода?

59 4.
Для каких целей при передаче сообщений по линиям связи к ним добавляется циклический избыточный код, уменьшая тем самым пропускную способность канала?
5.
Назовите главную особенность полиномиальной арифметики по модулю 2.
6.
Необходимо ли на принимающей стороне при проверке сообщения отбрасывать контрольную сумму?
7. ЛИТЕРАТУРА
1. Кнут Д.Е. Искусство программирования. Том 2. Получисленные алгоритмы. 3-е издание. — М.: Вильямс, 2005. — 832 с.
2. Таненбаум Э. Компьютерные сети. — СПб.: Питер, 2006. — 992 с.

60
ЛАБОРАТОРНАЯ РАБОТА №11
БАЗОВЫЕ ТЕХНОЛОГИИ КРИПТОГРАФИИ.
СИММЕТРИЧНОЕ ШИФРОВАНИЕ И ОДНОСТОРОННИЕ ХЭШ-
ФУНКЦИИ
1. ЦЕЛЬ РАБОТЫ
Изучить современные алгоритмы симметричного шифрования и одностороннего хэширования.
Познакомиться с возможностями современных программ шифрования данных.
2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Криптографический
алгоритм, также называемый
шифром, представляет собой математическую функцию, используемую для шифрования и дешифрирования. Под шифрованием понимают процесс преобразования открытых данных в зашифрованные при помощи ключа.
Дешифрование — обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный. Ключ — это информация, необходимая для беспрепятственного шифрования и дешифрования данных.
Ключ может быть любым значением. Обычно он представляет собой после- довательный ряд цифр и букв алфавита.
Множество возможных ключей называют пространством ключей.
Криптосистема представляет собой алгоритм плюс все возможные открытые тексты, шифротексты и ключи.
Существует два основных типа алгоритмов, основанных на ключах: симметричные и с открытым ключом (асимметричные). Симметричные алгоритмы (рис. 24), представляют собой алгоритмы, в которых ключ шифрования может быть рассчитан по ключу дешифрирования и наоборот. В большинстве симметричных алгоритмов ключи шифрования и дешифрирования одни и те же. Эти алгоритмы, также называемые алгоритмами с секретным ключом или алгоритмами с одним ключом, требуют, чтобы отправитель и получатель согласовали используемый ключ перед началом безопасной передачи сообщений. Раскрытие ключа означает, что кто угодно сможет шифровать и дешифрировать сообщения.
Рис. 24. Шифрование и дешифрирование с ключом
Безопасность симметричных алгоритмов полностью основана на ключах, а не на деталях алгоритмов. Это значит, что алгоритм может быть опубликован и проанализирован.

61
Симметричные алгоритмы делятся на две категории. Одни алгоритмы обрабатывают открытый текст побитно (иногда побайтно), они называются потоковыми алгоритмами или потоковыми шифрами. Другие работают с группами битов открытого текста. Группы битов называются блоками, а алгоритмы — блочными алгоритмами или блочными шифрами.
При поточном шифровании шифруется поток битов (рис. 25а). Такие шифры работают в два этапа. На первом этапе алгоритм использует секретный ключ для генерации потока случайных битов. На втором этапе, алгоритм шифрует биты данных, объединяя их по одному с потоком случайных битов, используя операцию «Исключающее ИЛИ». Если изменить один бит в открытом тексте, то это повлияет только на тот же бит в шифрованном тексте.
Характерная особенность этого способа шифрования — высокая производительность. Примерами таких шифров являются Enigma и RC4.
При шифровании по блокам кодирование данных выполняется после разбиения их на блоки фиксированной длинны, каждый из которых шифруется отдельно с помощью одного и того же ключа (рис. 25б). Если размер исходной информации не кратен размеру блока, то последний блок дополняется символами-заполнителями, которые при расшифровании отбрасываются. Примерами блочных шифров могут служить DES, ГОСТ
28147-89, RC5, AES.
а) Алгоритм поточного шифрования
б) Алгоритм блочного шифрования
Рис. 25. Категории алгоритмов симметричного шифрования
Хэширующая функция — это многозначная функция H, ставящая в соответствие своему аргументу M произвольной длины значение h=H(M) фиксированной длины. Хэш-функции используемые в криптографических приложениях обладают следующими свойствами:
Для любого M легко вычислить его хэш-значение h=H(M);
•
По известному значению хэш-функции практически невозможно определить сообщение M.
•
Для сообщения M практически невозможно найти сообщение M' такое, чтобы значения хэш-функций этих сообщений были одинаковы.

62
•
Практически невозможно найти два случайных сообщения M и M' таких, чтобы значения хэш-функций этих сообщений были одинаковы (свойство сильной устойчивости к коллизиям).
Хэш-значение сообщения может использоваться в качестве его уникального идентификатора. Если сообщение изменить, то изменится и хэш-значение. Найти другое сообщение с точно таким же хэш-значением практически невозможно. Благодаря этому свойству хэш-функции можно использовать для проверки целостности документов и для цифровой подписи. Очевидно, что наиболее важным параметром хэш-функции является длина возвращаемого ею значения. Если эта длина n бит, то для того, чтобы найти сообщение M', имеющее такое же хэш-значение, как и M, придётся перебрать в среднем 2n-1 различных сообщений.
Примерами хэш-функций могут служить MD2, MD4, MD5, SHA.
TrueCrypt — это криптографическое приложение для создания зашифрованных файл-контейнеров и шифрования разделов дисков, а так же съемных устройств хранения и дискет.
Возможности TrueCrypt:
•
Запись и чтение зашифрованных дисков.
•
Создание обычных зашифрованных дисков.
•
Создание скрытых зашифрованных дисков.
•
Монтирование зашифрованных физических дисков.
•
Возможность устанавливать (помимо пароля) ключевые файлы.
•
Набор алгоритмов (на выбор пользователя) шифрования.
•
Версии TrueCrypt доступны под Windows и Linux (возможность использовать один и тот же том, как по сети, так и из различных операционных систем).
TrueCrypt (рис. 26) позволяет зашифровывать и расшифровывать данные
«на лету».
Это означает, что данные автоматически зашифровываются или расшифровываются прежде, чем они будут загружены или сохранены, без любого пользовательского вмешательства.
Расшифрование происходит в оперативной памяти при считывании файлов с монтированного тома, при этом TrueCrypt никогда не сохраняет никаких временных расшифрованных данных на диск — все операции происходят в оперативной памяти. Точно так же происходит и шифрование. Данные, хранящиеся на зашифрованном томе, не могут быть расшифрованы без правильного секретного ключа. Программа полностью шифрует файловую систему тома (имена файлов, название папок и их содержание, свободное пространство и т.д.). Для хранения пользовательских паролей в TrueCrypt используется хэширование.
Для создания тома TrueCrypt следует нажать кнопку «Создать том» в главном окне программы. В появившемся окне можно выбрать тип создаваемого тома: обычный (внешний) том или скрытый том внутри обычного. Последний вариант позволит скрывать особо важные данные.