close

Вход

Забыли?

вход по аккаунту

?

Alekseev Makarov Sirant Yakovleva issledovanie metodov kodirovaniya i shifrovaniya metod ukazaniya na kursovoe proektirovanie uchebnoe posobie 2018

код для вставкиСкачать
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования (ФГБОУ ВО)
«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ»
Кафедра информатики и вычислительной техники
Алексеев А.П., Макаров М.И., Сирант О.В., Яковлева С.С.
Исследование методов кодирования
и шифрования
Методические указания на курсовое проектирование
Учебное пособие
2018 г.
2
_________________________________________________________________
004.083.73 (075.8)
Рекомендовано к изданию методическим советом ПГУТИ,
протокол № 46 от 26 апреля 2018 г.
Рецензенты:
Проф. д-р инж. Станимир Ст. Станев, Шуменский Университет им.
Епископа Константина Преславского (Болгария);
заведующий кафедрой МСИБ Поволжского государственного университета
телекоммуникаций и информатики (г. Самара)
д.т.н., профессор Карташевский В.Г.
Алексеев А.П., Макаров М.И., Сирант О.В., Яковлева С.С.
Исследование методов кодирования и шифрования.
Под редакцией Алексеева А.П. Учебное пособие по дисциплине «Информатика», для студентов первого курса специальностей 10.03.01 и 10.05.02. –
102 с.
Учебное пособие содержит задание на курсовое проектирование, а
также методические указания для выполнения задания.
Описаны методы сжатия (Хаффмана, RLE, LZW), помехоустойчивого
кодирования (коды Хэмминга и БЧХ), шифрования (аддитивный шифр и
шифр с управляемыми операциями), стеганографического сокрытия информации (скрытая передача информации в графическом файле формата BMP и
в звуковом файле формата WAV), описан порядок моделирования цифровых
устройств (систем шифрования, регистра сдвига и устройства деления полиномов).
Задание содержит большое число различных вариантов, которые
определяются по номеру зачётки. Исходный текст передаваемого сообщения
содержит фамилию и имя студента, поэтому одинаковых работ не может
быть в принципе.
________________________________________________________________________________
3
Содержание
Введение…………………………………………………….............
1. Основные понятия курсового проектирования……………….
2. Методы сжатия информации………………..............................
2.1. Код Шеннона-Фано........................................................
2.2. Метод сжатия RLE..........................................................
2.3. Метод сжатия LZW........................................................
3. Методы помехоустойчивого кодирования.................. .............
3.1. Код Хэмминга........................................................ ........
3.2. Код БЧХ........................................................ ..................
4. Криптографические методы защиты информации ..................
4.1. Области использования криптографии.................. ......
4.2. Шифр гаммирования......................................................
4.3. Шифр с управляемыми операциями.................. ..........
5. Стеганографические методы защиты информации..................
5.1. Основные понятия аналого-цифрового преобразования........................................................ .................................
5.2. Формат звукового файла WAV.....................................
5.3. Модель RGB........................................................ ...........
5.4. Формат графического файла BMP.................. .............
6. Моделирование работы РЭУ.....................................................
6.1. Моделирование работы аддитивной криптосистемы
6.2. Моделирование работы шифратора с управляемыми
операциями........................................................ ....................
6.3. Моделирование работы устройства деления ..............
6.4. Моделирование циклического сдвига..........................
7. Задание на курсовое проектирование.........................................
Список использованной литературы.................. ..................
Заключение........................................................ .....................
Приложения (таблица СР-1251, титульный лист, глоссарий, список аббревиатур, пример оформления списка источников) ........................................................ ........................
Стр.
4
5
8
16
20
22
26
27
29
35
37
39
41
43
46
49
54
57
64
67
69
80
83
85
89
90
91
4
_________________________________________________________________
Введение
Данное учебное пособие содержит задание на проведение курсового
проектирования, теоретический материал и методические указания на выполнение заданий.
Публикация подготовлена коллективом сотрудников кафедры ИВТ
Поволжского государственного университета телекоммуникаций и информатики (г. Самара). Раздел 2.3. «Метод сжатия LZW» написан доцентом,
к.т.н. Макаровым М.И., раздел «Основные понятия курсового проектирования» - старшим преподавателем Сирант О.В., раздел 3.7. «Области использования криптографии» - старшим преподавателем Яковлевой С.С. Разделы
2…7 написаны Алексеевым А.П. Раздел 7, введение и заключение написаны
соавторами совместно. Общее редактирование учебного пособия осуществлял доцент Алексеев А.П.
При работе над учебным пособие авторы стремились создать большое
число различных вариантов заданий, использовать шифры, которые основаны на применении логических операций, изучаемых в информатике, нескольких распространённых способов сжатия и помехоустойчивого кодирования информации. Использование приёмов стеганографического сокрытия
информации позволяет студентам детально ознакомиться с мультимедийными форматами файлов. Проверка основных результатов проектирования
осуществляется путём моделирования работы важнейших узлов кодера и декодера и систем шифрования в среде Multisim.
При выполнении курсового проектирования преподаватели в зависимости от требований рабочей программы и отведённых часов на курсовое
проектирование могут исключать отдельные пункты задания (например, не
делать сжатия исходных данных).
При возникновении вопросов и замечаний, связанных с содержанием
учебного пособия, письма можно направлять Алексееву А.П.
(apa_ivt@rambler.ru).
Авторы выражают благодарность профессору Станеву С.С. и к.т.н.,
доценту Назаренко П.А. за обнаруженные неточности в рукописи и ценные
методические советы.
________________________________________________________________________________
1.
5
Основные понятия курсового
проектирования
Курсовая работа по дисциплине Информатика предусмотрена учебным планом направления подготовки 10.05.02 - Информационная безопасность телекоммуникационных систем и 10.03.01 – Информационная безопасность.
Курсовая работа (КР) – один из видов самостоятельной работы обучающихся, представляющее собой исследование по конкретной теме в письменной форме. Цель выполнения КР – научиться применять полученные знания на практике для решения конкретных задач [8].
Целью курсового проектирования является овладение методикой
или навыками самостоятельного решения конкретных задач на основе ранее
приобретённых знаний, развитие универсальных базовых (ОПК-4 и ОПК-5),
так и профессиональных (ПК-2) компетенций в виде знаний, умений, навыков, способностей и т.д.
- ОПК-4. Способность понимать значение информации в развитии современного общества, применять достижения современных технологий для
поиска и обработки информации.
- ОПК-5. Способность понимать социальную значимость будущей
профессии, обладать высокой мотивацией к выполнению профессиональной
деятельности в области обеспечения информационной безопасности и защиты интересов личности, общества и государства, соблюдать нормы профессиональной этики.
- ПК-2. Способность применять программные средства системного,
прикладного и специального назначения, инструментальные средства, языки
и системы программирования для решения профессиональных задач.
Основными задачами курсового проектирования являются:
- углубление уровня освоения общекультурных и профессиональных
компетенций;
- формирование умений и навыков самостоятельной организации
учебно-исследовательской работы, применение знаний для решения профессиональных задач;
- формирование умения работать с научной и справочной литературой, в том числе нормативными документами и стандартами;
- освоение современных методов поиска, обработки, использования и
анализа информации;
- формирование необходимой культуры выполнения квалификационных работ.
Защита КР должна быть проведена до начала экзаменационной сессии. Работы или проекты допускаются к защите при условии их законченного оформления.
6
_________________________________________________________________
При аттестации студента по итогам его работы над КР оцениваются
следующие показатели:
- качество выполнения КР;
- качество оформление КР;
- степень авторского вклада студента в представленную к защите работу;
- достигнутые уровни компетенций.
Таким образом, на оценку курсовой работы влияет не только глубина
проработки исследуемой темы, но и правильность оформления всей работы.
1.1. Основное содержание курсовой работы
Курсовая работа состоит из:
- титульного листа;
- листа рецензии (оставляется пустым для написания рецензии руководителем);
- оглавления или содержания;
- текста работы, который включает подробное описание выполняемых заданий, с предварительным описанием их, и заключения, содержащего
выводы по работе;
- списка аббревиатур и сокращений (по усмотрению автора);
- перечня литературных и других источников;
- приложений (по усмотрению автора): изображения, графики, таблицы, диаграммы.
Во введении необходимо показать актуальность решаемых задач. В
заключении нужно описать полученные результаты.
Именно в таком порядке структурные элементы выполненной работы
брошюруются.
1.2. Правила оформления текстовой части
Пояснительная записка к курсовой работе выполняется в программе
Microsoft Word в формате document с расширениями .doc или .docx. К текстовой части работы применяются следующие требования:
- допустимо выбирать бумагу размера А4;
- страницы документа должны иметь книжную ориентацию; параметры полей (в мм.): 30 – левое, 15 – правое и по 20 – нижнее и верхнее;
- текст курсовой, включая ссылки, набирается одним шрифтом: Times
New Roman, цвет чёрный, его размер в основном тексте работы должен равняться 14 пт, в автоматических сносках – 12 пт;
________________________________________________________________________________
7
- текст курсовой работы, включая сноски, необходимо располагать по
ширине страницы; обязательным является наличие абзацных отступов по
1,25 см:
- в основном тексте используется полуторный размер интервала, в заголовках, подстрочных ссылках – одинарный;
- печать готовой работы выполняется только в одностороннем формате: сшивается и сдаётся на проверку в одном экземпляре. Одновременно
КР предоставляется в электронном виде. (Работа должна быть сброшюрована с помощью скоросшивателя. Использование прозрачных файлов для
брошюрования работы недопустимо);
- Страницы, таблицы и рисунки должны быть пронумерованы. Формулы вписываются в текстовом или графическом редакторе. Допустимо аккуратно и разборчиво вписывать формулы вручную.
- При исправлении ошибок (по замечаниям руководителя) следует
использовать обратную сторону листов. Листы, содержащие ошибки, заменять нельзя, они должны сохраняться в работе. При исправлении ошибок,
указанных в рецензии, следует дать ответы на все пункты рецензии. Недопустимо удалять рецензию.
1.3.
Оформление заголовков, сносок и источников
Заголовки в курсовой работе набираются полужирным текстом и располагаются по центру строки. Не допускается наличие переносов слов и знаков препинания в конце заголовка. Нумерация страниц должна быть последовательной, она начинается с введения, которому присваивается третий
страничный номер, и заканчивается приложениями, если их наличие предусмотрено логикой курсовой работы. Первый номер на титульном листе не
печатается. Номерной знак страницы может располагаться в нижнем правом
углу или по центру. С новой страницы должна начинаться каждая новая
глава или раздел.
Могут применяться автоматические сноски или сноски в тексте в
квадратных скобках. Обстоятельный разбор вариантов указания постраничных сносок представлен в ГОСТе Р 0.7.5-2008 «Библиографическая ссылка.
Общие требования и правила составления».
Правила составления литературного списка приведены в ГОСТ 7.12003 «Библиографическая запись. Библиографическое описание. Общие требования и правила составления». При написании курсовой работы могут использоваться книги (однотомные и многотомные издания), законодательные
материалы, стандарты, диссертации, статьи в сборниках и журналах, учебники, методические материалы и другая литература (см. Приложение 5).
8
_________________________________________________________________
2. Методы сжатия информации
Несмотря на то, что объёмы внешней памяти ЭВМ постоянно растут,
потребность в архивации не уменьшается. Это объясняется тем, что сжатие
информации необходимо не только для экономии места в памяти, но и для
быстрой передачи информации по сети на другие ЭВМ. Кроме того, возможность отказа магнитных, оптических и электронных носителей информации,
разрушающее действие вирусов заставляют пользователей делать резервное
копирование ценной информации на другие (запасные) носители информации. Очевидно, что разумнее информацию хранить сжатой.
Сжатие информации без потерь (архивация) — это такое преобразование информации, при котором объем файла уменьшается, а количество
информации, содержащейся в архиве, остаётся прежним.
Процесс записи файла в архивный файл называется архивированием
(упаковкой, сжатием), а извлечение файла из архива — разархивированием
(распаковкой, извлечением). Упакованный (сжатый) файл называется архивом.
Степень сжатия информации зависит от содержимого файла и формата файла, а также от выбранного метода архивации. Степень (качество)
сжатия файлов характеризуется коэффициентом сжатия Kc, который определяется как отношение объёма исходного файла Vo к объёму сжатого файла
Vc:
Vo
.
Vc
Чем больше величина Kc, тем выше степень сжатия информации.
Заметим, что в некоторых литературных источниках встречается
определение коэффициента сжатия, обратное приведённому отношению.
Все существующие методы сжатия информации можно разделить на
два класса: сжатие без потерь информации (обратимый алгоритм) и сжатие
с потерей информации (необратимый алгоритм). В первом случае исходную
информацию можно полностью извлечь из архива. Во втором случае распакованное сообщение будет отличаться от исходного сообщения.
Под сжатием (компрессией, упаковкой) с потерями понимается такое
преобразование информации, в результате которого исходный файл уменьшается в объёме, а количество информации в сжатом файле уменьшается на
такую небольшую величину, которой практически можно пренебречь.
Многие приёмы сжатия аудио- и видеоинформации основываются на
«обмане» органов чувств (зрение и слух) человека путём исключения избыточной информации, которую человек (в силу своих психофизических особенностей) не способен воспринять.
Kc 
________________________________________________________________________________
9
Разработано несколько стандартов сжатия видео- и аудиоинформации.
Большее влияние на настоящее и будущее мультимедийных средств
оказывает MPEG (Moving Picture Experts Group) — объединённый комитет
двух организаций: Интернациональной организации по стандартизации
(ISO) и Интернациональной электротехнической комиссии (IEC). Этот комитет разрабатывает стандарты с одноименными названиями. Так стандарт
MPEG-1 был разработан с учётом возможностей двухскоростных проигрывателей лазерных дисков CD-ROM и компьютеров с 486-м процессором.
В январе 1992 г. комитет MPEG опубликовал проект стандарта
MPEG-1, а в декабре 1993 г. проект был принят в качестве стандарта. По
требованиям стандарта скорость передачи информации сжатого видео и
звука должна укладываться в 1,5 Мбайт/с, хотя были предусмотрены режимы вплоть до 4—5 Мбайт/с.
Окончательное утверждение MPEG-2 в качестве международного
стандарта произошло в ноябре 1994 г. В его спецификациях была определена допустимая интенсивность потока данных: от 2 до 10 Мбайт/с.
Стандарт MPEG-2 позволяет записывать на лазерные диски, изготовленные по технологии DVD, полноэкранные фильмы «вещательного» качества. Для телевидения высокой чёткости разрабатывался стандарт MPEG-3,
который впоследствии стал частью стандарта MPEG-2 и отдельно теперь не
упоминается.
Рассмотрим принципы сжатия звуковой информации, а затем — методы сжатия видеоинформации.
Согласно теореме Котельникова [1], чтобы восстановить без искажений аналоговый сигнал после его преобразования в цифровой сигнал,
необходимо, чтобы частота выборки (дискретизации) была хотя бы вдвое
выше верхней граничной частоты исходного сигнала. Для записи звука на
компакт-диски используется частота выборки 44,1 кГц. Эта частота более
чем в 2 раза превышает верхнюю граничную частоту, которую слышит человек.
Второй фактор, влияющий на качество воспроизводимого звука, —
количество двоичных разрядов квантования. Исходный аналоговый сигнал
изменяется непрерывно. В результате цифроаналогового преобразования
восстановленный сигнал неизбежно отличается по форме от исходного сигнала, и это отличие тем больше, чем меньше разрядов использовалось для
квантования сигнала. Искажение формы сигнала при воспроизведении эквивалентно добавлению некоего шума — шума квантования. Чтобы достичь
практически полной неразличимости шумов квантования, при производстве
компакт-дисков используется 16-разрядное квантование, при этом уровень
громкости воспроизводимого звука может принимать одно из 216 = 65 536
значений.
Для записи стереофонического звука с частотой дискретизации
10
_________________________________________________________________
44,1 кГц и 16-ти битном квантовании требуется скорость передачи данных:
44100 16 2 = 1 411 200 бит/c или 172,27 Кбайт/c.
При такой скорости передачи информации сохраняются мельчайшие
детали звуковой картины (в том числе и исходные шумы). Этот способ кодирования информации избыточен, так как многие детали исходной звуковой картины не воспринимается человеком из-за биологических ограничений.
Применение алгоритмов сжатия без потерь для файлов, содержащих
оцифрованный звук в 16-битном формате, не позволяет сжать исходный
файл более чем в 2 раза. Оцифрованный (преобразованный с помощью
АЦП) звуковой сигнал обычно не повторяет сам себя и по этой причине
плохо сжимается с помощью алгоритмов компрессии без потерь.
Адаптивная разностная компрессия (Adaptive Differential Pulse Code
Modulation, ADPCM) используется в основном для сжатия речевых сигналов. Для сжатия музыкальных произведений этот метод не подходит из-за
сильных искажений. Идея компрессии ADPCM заключается в том, что
оцифрованный речевой сигнал представляют не самими отсчётами, а разностями соседних отсчётов, меньших по величине и, следовательно, требующих меньшего числа битов для своего представления.
Рассмотрим основные идеи сжатия аудиоинформации, которые базируются на учёте психофизических ограничений человека.
Основные приёмы, положенные в основу сжатия информации с помощью стандартов MPEG, базируются на объективно существующих психоакустических ограничениях органов чувств человека. Человеческое ухо
способно воспринимать звуковые колебания, лежащие лишь в диапазоне частот 20—20000 Гц, причём с возрастом этот диапазон сужается. Методы
сжатия звуковых данных, основанные на использовании физиологических
особенностей человека, относятся к классу компрессии с потерями. Эти
методы не пытаются достичь абсолютно точного восстановления формы исходных колебаний. Их главная задача — достижение максимального сжатия
звукового сигнала при минимальных слышимых искажениях восстановленного после сжатия сигнала.
Звуковой файл можно сжать с помощью компандирования. Название этого метода происходит от английского термина compander, который
образован от английских слов: compressing — expanding coder — decoder.
Этот метод основан на законе, открытом психологами: если интенсивность
раздражителя меняется в геометрической прогрессии, то интенсивность человеческого восприятия меняется в арифметической прогрессии.
Компандирование заключается в компрессии (сжатии) по амплитуде
исходного звукового сигнала. Затем сжатый сигнал восстанавливается с помощью экспандера (расширителя).
Компрессия — это сжатие динамического диапазона сигнала, когда
11
________________________________________________________________________________
слабые звуки усиливаются сильнее, а сильные — слабее. На слух это воспринимается как уменьшение различия между тихим и громким звучанием
исходного сигнала.
Установлено, что, если повышать громкость звука в 2, 4, 8 и т. д. раз,
то человеческое ухо будет воспринимать этот процесс как линейное увеличение интенсивности звука. Изменение уровня громкости с 1 единицы до 2
единиц столь же заметно для человеческого уха, как и изменение громкости
от 50 до 100 единиц. В то же время изменение громкости от 100 единиц до
101 единицы человеком практически не ощущается. Таким образом, ухо человека логарифмирует громкость слышимых звуков.
При компандировании значение амплитуды звука заменяется логарифмом этого значения. Полученные числа округляются, и для их записи
требуется меньшее число разрядов.
При 16-битном кодировании звука максимальное значение кода не
превышает значение 216. Логарифм этого числа по основанию 2 равен 16.
Последнее число может быть закодировано пятью двоичными разрядами
(1610 = 100002). Таким образом, для представления информации вместо
16 бит можно использовать лишь 5 бит. Этим достигается сжатие информации. Для воспроизведения компрессированного сигнала его подвергают обратному по сравнению с логарифмированием преобразованию — потенцированию.
Ещё один способ сжатия звуковой информации заключается в том, что
исходный звуковой сигнал очищается с помощью фильтров от неслышимых
компонентов (например, убирают низкие басовые шумы). Затем производится более сложный анализ сигнала: удаляются замаскированные частоты,
заглушенные другими мощными сигналами. Таким образом, можно исключить до 70% информации из сигнала, практически не изменив качество его
звучания.
Сжатие сигнала также можно получить за счёт ещё одного приёма.
Если исходный сигнал является стереофоническим, то его можно преобразовать в так называемый совмещённый стереофонический сигнал. Установлено, что слуховой аппарат человека может определить местоположение
источника звука лишь на средних частотах, а высокие и низкие частоты звучат как бы отдельно от источника звука. Таким образом, высокие и низкие
частоты можно представить в виде монофонического сигнала (т. е. без разделения на два стереофонических канала). Это позволяет вдвое уменьшить
объем информации, передаваемой на низких и высоких частотах.
Ещё одна возможность сжатия звукового сигнала связана с наличием
двух потоков информации для левого и правого каналов. Например, если в
правом канале наблюдается какое-то время полная тишина, то это пустующее место используется для повышения качества звучания левого канала
или туда помещают данные, которые не уместились в компрессированный
12
_________________________________________________________________
поток в предыдущие моменты времени.
Одно из свойств человеческого слуха заключается в маскировании
тихого звука, следующего сразу за громким звуком. Так после выстрела
пушки в течение некоторого времени трудно услышать стрекот кузнечиков.
При сжатии звукового сигнала замаскированный, почти неслышимый
звук не сохраняется в памяти ЭВМ и не передаётся через каналы связи.
Например, громкий звук длительностью 0,1 с может замаскировать тихие
последующие звуки, запаздывающие на время до 0,5 с, а значит, их не надо
сохранять. Такая процедура исключения сигнала, следующего за громким
звуком, называется маскированием во временной области.
Для человеческого уха характерно также и явление маскирования в
частотной области, заключающееся в том, что постоянно звучащий громкий
синусоидальный сигнал маскирует («глушит») тихие сигналы, которые
близко лежат на оси частот к громкому сигналу. Когда-то в СССР таким
приёмом «глушили» западные радиостанции, например, «Голос Америки».
Для этого на близкой к рабочей частоте передавали мощный «белый шум»
и принимаемая информация становилась неразборчивой.
При техническом использовании таких физиологических особенностей человеческого слуха уплотняемый сигнал переносят с помощью быстрого преобразования Фурье из временной области в частотную область. Затем удаляют спектральные составляющие, замаскированные громким сигналом, и делают обратное преобразование Фурье.
Ещё одна возможность компрессии основывается на следующей особенности человеческого слуха. Экспериментально установлено, что в диапазонах частот 20—200 Гц и 14—20 кГц чувствительность человеческого
слуха существенно ниже, чем на частотах 0,2—14 кГц. По этой причине допустимо более грубое квантование сигналов в указанных диапазонах частот.
На этих частотах для представления непрерывных сигналов двоичными числами требуется меньшее число уровней, а значит и меньшее число битов.
Так, в среднем диапазоне частот амплитуды кодируются 16 битами, а на частотах, где ухо менее чувствительно — 6 и даже 4 битами.
Биоакустические свойства человеческого слуха не позволяют сжать
звуковой сигнал, если он представляет собой однотонные звуки с постоянным уровнем громкости. В этом случае наряду с рассмотренными приёмами
сжатия дают эффект традиционные методы архивации информации (например, алгоритм Хаффмана или RLE).
Познакомимся с основными показателями, характеризующими качество движущихся изображений.
Частота кадра (Frame Rate). Стандартная скорость воспроизведения
видеосигнала 30 кадров/с (для кино этот показатель составляет 24 кадра/с).
Экспериментально установлено, что иллюзия равномерно движущегося
изображения возникает при частоте смены кадров более 16-ти в секунду. В
13
________________________________________________________________________________
этом случае человек воспринимает быстроменяющиеся картинки в виде динамичного непрерывного изображения. Заметим, что первые фильмы были
сняты с использованием частоты 8 кадров/c (вспомним фильмы Чарли Чаплина).
Глубина цвета (Color Resolution). Этот показатель определяет количество цветов, которые можно одновременно отобразить на экране. Компьютеры обрабатывают цвет в RGB-формате (красный — зелёный — синий).
RGB-формат позволяет путём смешения в разных пропорциях трёх основных цветов получить любой другой цвет или оттенок. Для цветовой модели
RGB обычно характерны следующие режимы глубины цвета: 8 бит/пиксель
(256 цветов), 16 бит/пиксель (65 535 цветов) и 24 бит/пиксель (16,7 миллиона
цветов).
Экранное разрешение (Spatial Resolution) или, другими словами, количество точек, из которых состоит изображение на экране, например, 1920
х 1080 точек (пикселей).
Качество изображения (Image Quality). Это комплексный показатель, который вбирает в себя три предыдущих. Требования к качеству зависят от конкретной задачи.
Расчёты показывают, что 24-битное цветное видео при разрешении
640  480 пикселей и частоте 30 кадров/с требует передачи более 26 Мбайт
данных в секунду. Для наглядности приводим здесь эти расчёты.
640  480  24  30 = 221 184 000 бит/с = 26,37 Мбайт/с.
Для оптимизации процесса кодирования информации необходимо, с
одной стороны, не передавать избыточную информацию, а с другой стороны, не допускать чрезмерной потери качества изображения.
В зависимости от скорости упаковки изображений методы сжатия
подразделяются на две группы. К первой группе относится метод сжатия
неподвижных изображений. Сжатие может выполняться с любой скоростью, так как этот процесс не регламентирован временем (в силу статичности изображения). Вторую группу образуют методы сжатия движущихся
изображений. Сжатие движущихся изображений должно выполняться, как
правило, в режиме реального времени по мере ввода данных.
Стандарт JPEG (Joint Photographic Experts Group), предложенный
Объединённой группой экспертов в области фотографии, позволяет сократить размеры графического файла с неподвижным изображением в 10—20
раз.
Наибольшее распространение для сжатия движущихся изображений
получил стандарт MPEG.
С помощью стандарта MPEG обрабатывается каждый кадр по отдельности, а также анализируется динамика изменения изображения. Этим удаётся уменьшить избыточные данные, так как в большинстве случаев фон
изображения остаётся достаточно стабильным, а изменения происходят в
14
_________________________________________________________________
основном на переднем плане. MPEG начинает сжатие с создания исходного
(ключевого) кадра, называемого Intra (внутренний) кадр. I-кадры играют
роль опорных при восстановлении остального видеоизображения и размещаются последовательно через несколько кадров. I-кадры формируют с помощью методов, разработанных стандартом JPEG для сжатия неподвижных
изображений (например, фотографий).
Фрагменты изображений, которые претерпевают изменения, сохраняются при помощи Predicted (расчетных, предсказываемых) кадров. Pкадры содержат различия текущего изображения с предыдущим кадром. Ркадры формируются с использованием информации, полученной из предыдущих кадров.
Кроме перечисленных кадров, используются B-кадры, название которых происходит от английских слов Bidirectional Interpolated. В переводе с
английского языка этот термин означает «кадры двунаправленной интерполяции (предсказания)». B-кадры содержат усреднённую информацию относительно двух смежных (предыдущего и последующего) I-кадров или P-кадров. Это позволяет предположительно восстанавливать (реконструировать,
интерполировать) отсутствующие кадры.
B-кадры учитывают тот факт, что человек не способен за доли секунды рассмотреть детали движущегося изображения, поэтому можно формировать некоторое приблизительное, усреднённое (промежуточное) изображение, учитывая информацию опорных кадров. Здесь происходит умышленный обман органов чувств человека, за счёт чего происходит сжатие информации. Примерная последовательность кадров выглядит следующим образом: IBBPBBIBBPBBIBB…
Очевидно, что существенный выигрыш в сжатии информации дают
P- и особенно B-кадры, так как для формирования I-кадров необходимо
использовать всю имеющуюся информацию об изображении.
При сжатии изображений (как и при сжатии звуков) используются
физиологические особенности человека. Установлено, что ошибки в изображении заметны глазом (визуально), если они превышают некоторый порог
заметности. Различают пространственную и временную заметность искажений изображений.
Порог заметности пространственных изменений яркости зависит от
многих факторов: яркости деталей изображения, яркости фона, относительного положения деталей различной яркости, условий внешнего освещения.
Что касается временного восприятия цвета, то известно, что вариация
цветности менее заметны, чем вариация яркости. Наиболее заметны изменения зелёного цвета, затем красного. Наименее заметны изменения синего
цвета.
Используя эту особенность зрения человека, можно при упаковке
(сжатии) изображения исключить данные о цвете, скажем, каждой второй
точки изображения (сохранив только её яркость), а при распаковке брать
15
________________________________________________________________________________
вместо исключённого цвета цвет соседней точки. Аналогично для группы
соседних точек брать можно некоторый средний цвет.
За высокое качество сжатия, как правило, приходится платить большими затратами времени на упаковку и распаковку. Алгоритмы, дающие
хорошее качество сжатия, могут оказаться неприменимыми из-за слишком
большого времени, необходимого для распаковки информации. Разработчики новых методов упаковки всегда ищут компромисс между качеством
сжатия и скоростью распаковки.
Как правило, информацию можно «не торопясь» сжать, а при воспроизведении распаковать с большой скоростью. Но бывают случаи, когда информацию нужно упаковать «на лету», т. е. в режиме реального времени.
Такая ситуация возникает, например, при передаче изображения с видеокамеры в Интернет.
Степень сжатия характеризуется коэффициентом сжатия, который
численно равен отношению объёма исходного файла к объёму сжатого
файла.
Выбор коэффициентов сжатия — это компромисс между скоростью
передачи файлов и качеством восстанавливаемого изображения. Чем выше
коэффициент сжатия, тем ниже это качество. При этом следует иметь в виду,
что при очень высокой разрешающей способности и большой степени сжатия можно получить изображение с низкой разрешающей способностью. Что
касается требующегося качества изображения, то оно зависит от конкретной
поставленной задачи. Например, в системах видеоконференций основной
объем необходимой информации содержится в речи (звуке). Качество же
изображения играет второстепенную роль.
При сжатии информации часто используется термин «кодек», который образован путём сокращения слов «кодер» и «декодер». Этим термином обозначается алгоритм, предназначенный для кодирования (сжатия) и
декодирования (распаковки) цифровых сигналов, идущих от системы цифровой аудио- и видеозаписи. Алгоритм может быть реализован программно
и загружен в память компьютера, либо может быть реализован аппаратно с
помощью специальной микросхемы. Симметричные кодеки упаковывают
и распаковывают сигнал в реальном времени.
Некоторые сложные алгоритмы кодирования, например, алгоритм
сжатия видеосигнала MPEG, не могут выполняться в реальном времени (при
записи), поэтому кодек MPEG называется асимметричным.
В настоящее время разработано много методов архивации без потерь.
Рассмотрим три наиболее известные идеи.
16
_________________________________________________________________
2.1.
Код Шеннона-Фано
Первая идея, основанная на учёте частот появления символов в тексте, была разработана Клодом Шенноном и независимо от него Робертом
Фано, а затем в 1952 г. развита Дэвидом Хаффманом - аспирантом Массачусетского технологического института при написании им курсовой работы
[2,3,4]. Идея базируется на том факте, что в обычном тексте частоты появления различных символов неодинаковые. По этой причине для сжатия нужно
использовать кодовые комбинации различной длины.
При кодировании символов в ЭВМ используют кодовые таблицы. При
этом каждый символ кодируется либо одним байтом (CP-1251, КОИ-8), либо
двумя байтами (Unicode). Кодовые таблицы стандартизируют процедуру кодирования. Однако для передачи информации по каналу связи (или для долговременного хранения на вешнем носителе) можно использовать более сложную процедуру кодирования. При данном методе архивации стандартные кодовые таблицы не используются, а создаются собственные. При этом вид кодовой таблицы каждый раз изменяется и зависит от содержания архивируемого документа.
Задачу экономного кодирования сообщений источника, имеющего отличное от равномерного распределения вероятностей появления символов
его алфавита, позволяют решить неравномерные префиксные коды.
Рассмотрим принцип построения кода методом Шеннона-Фано. Построение кода основываются на статистических свойствах источника сообщений. При этом часто встречающимся символам ставят в соответствие короткие кодовые комбинации. Из-за того, что разным символам алфавита соответствуют кодовые комбинации разной длины, такие коды называют неравномерными.
В качестве примера сжатия методом Шеннона-Фано рассмотрим процедуру архивации сообщения «ИНН 637322757237». Данный текст содержит избыточность, которая определяется по формуле:
 H
L   1   100% ,
n

где H - энтропия сообщения;
n - длина кодовой комбинации при использованном кодировании.
Энтропия сообщения вычисляется по формуле:
N
H   pi log2 pi ,
i 1
где N - число символов в алфавите источника;
pi - относительная частота (вероятность) появления символа в сообщении.
17
________________________________________________________________________________
Относительная частота pi встречаемости символа определяется как
отношение абсолютной частоты появления символа в сообщении к общей
длине сообщения (числу символов в сообщении):
pi 
i
,
m
где i - абсолютная частота (частость) встречаемости i-ого символа
алфавита источника; m – число символов в сообщении.
В данном случае энтропия сообщения равна:
4
3
3 2
2
1
1
4
H    log2  2  log2  log2  4  log2   2,781 бит/сим16
16
16 16
16
16
16 
 16
вол,
4 1
 - относительная частота появления символа «7»;
16 4
3
- относительная частота появления символов «2» и «3»;
p2  p3 
16
2 1
p4 
 - относительная частота появления символа «Н»;
16 8
1
- относительная частота появления символов
p5  p6  p7  p8 
16
где p1 
«5», «6», «И», Пробел.
При использовании равномерного кода (например, СР-1251) длина
кодовой комбинации для кодирования одного символа определяется так:
n  log2 N  ,
 x  - функция округления аргумента до ближайшего целого значения, не меньшего, чем x .
В данном примере n  log2 256  8 бит.
Избыточность сообщения при кодировании равномерным кодом
равна:
 2,781 
L  1 
 100%  65,23% .
8 

На первом этапе построения кода Шеннона-Фано формируется таблица абсолютных частот символов.
Абсолютная частота
СимАбсолютная частота  i
Символ
i
вол
7
4
5
1
2
3
6
1
3
3
И
1
Н
2
Пробел
1
18
_________________________________________________________________
Для получения кодовых комбинаций строится кодовое дерево. При
формировании кода Шеннона-Фано дерево строится от корня к листьям (в
отличие от настоящего дерева здесь корень располагается вверху, а листья –
внизу). В качестве корня используется множество всех символов алфавита
сообщения, упорядоченное (ранжированное) по частоте встречаемости символов. Число сверху таблицы указывает на количество символов в исходном
сообщении (см. следующий рисунок).
Затем множество символов делят на два подмножества так, чтобы новые подмножества имели равные (насколько это возможно) суммарные частоты встречаемости входящих в них символов. Например, вес 11 желательно разделить на два подмножества 5 и 6, деление на подмножества 4 и 7
будет ошибочным. Два новых подмножества соединяются с корнем дерева
ветвями, становясь потомками. Левая ветвь дерева обозначается символом
1, а правая ветвь – символом 0.
Полученные подмножества рекурсивно делятся до тех пор, пока не
будут сформированы листья дерева – отдельные символы сообщения.
19
________________________________________________________________________________
Кодовые комбинации (на предыдущем рисунке они указаны в кавычках под соответствующими листьями) получаются при движении от корня
дерева к кодируемому символу-листу путём объединения (конкатенации)
бит, присвоенных пройденным ветвям дерева. Запись кодовой комбинации
ведут в направлении от старших разрядов к младшим. Например, при кодировании символа «3» сначала следует пройти по правой ветви к множеству
{3, Н, 5, 6, И, Пробел}. При этом в кодовую комбинацию нужно записать бит
0. Затем нужно пройти по левой ветви к множеству {3, Н} (к кодовой комбинации добавляется бит 1). Наконец, нужно пройти по левой ветви, чтобы
достичь листа «3». Таким образом, получена кодовая комбинация «011».
При декодировании биты считываются из входного потока и используются, как указатели направления движения по кодовому дереву от корня к
искомому листу. При достижении листа найденный символ записывается в
выходной поток, а движение по кодовому дереву снова начинают от корня.
Например, декодирование комбинации «010» происходит следующим образом. Из потока данных считывается бит 0, следовательно, нужно пройти по
правой ветви от корня дерева к узлу {3, Н, 5, 6, И, Пробел}. Следующий бит
единичный, что требует пройти по левой ветви к множеству {3, Н}. Наконец,
следующий бит 0 приводит декодер по правой ветви к листу «Н».
В следующей таблице приведены все разрешённые комбинации полученного кода Шеннона-Фано. Это так называемый словарь сообщения. Он
передаётся на приёмную сторону вместе с архивом.
Символ
7
2
3
Н
Кодовая комбинация
11
10
011
010
Символ
5
6
И
Пробел
Кодовая комбинация
0011
0010
0001
0000
Закодированное сообщение будет иметь вид:
000101001000000010011110111010110011111001111
Общая длина закодированного сообщения составляет 45 бит.
Средняя длина кодовой комбинации равна (напомним, что число символов в сообщении – 16):
45
n
 2,813 бит/символ.
16
Избыточность сообщения после применения кода Шеннона-Фано
снизилась до значения:
20
_________________________________________________________________
 2, 781 
L  1 
 100%  1,13% .
 2,813 
Несложно убедиться, что применение кода Шеннона-Фано позволило
существенно уменьшить избыточность сообщения. При равномерном кодировании рассмотренного сообщения с помощью кодовой таблицы CP-1251
пришлось бы передать не 45 бит, а 128 бит.
При архивации рассмотренным методом был сформирован префиксный код. Префиксным кодом называется множество таких двоичных последовательностей, что ни одна последовательность в этом множестве не является началом (префиксом) другой последовательности.
2.2. Метод сжатия RLE
Вторая идея архивации состоит в учёте того факта, что в файлах часто
встречаются несколько подряд идущих одинаковых байтов, а некоторые последовательности байтов повторяются многократно. При архивации такие
места файла можно заменить командами вида «повторить данный байт n
раз» или «взять часть данных длиной k байтов, которая встречалась m байтов
назад». Такой алгоритм архивации носит имя RLE (Run Length Encoding —
кодирование путём учёта повторений).
Понять идею этого метода упаковки позволяет следующий пример
[5].
Пусть имеется следующее изображение звёздного неба: на чёрном
фоне видны редкие белые звезды. При растровом представлении неба информация в ЭВМ будет храниться в таком виде: черное-черное-черное-черное-черное-белое-черное-черное-черное-черное-черное и т. д.
Естественно, что значительно компактнее хранить информацию, указав, сколько раз подряд идут черные
пиксели, сколько раз белые и т. д.
Среди известных художественных произведений наибольшему сжатию методом RLE можно подвергнуть
«Чёрный квадрат» Малевича К.С.
Рассмотрим детально основную
идею метода архивации RLE.
Упакованная методом RLE последовательность состоит из управляющих байтов, за которыми следуют один или несколько байтов данных.
При этом если старший бит управляющего байта равен 1, то следующий за
ним байт данных нужно повторить при распаковке столько раз, сколько указано в оставшихся 7 битах управляющего байта.
Например, управляющий байт 10001001 говорит, что следующий за
ним байт нужно повторить 9 раз, так как 10012 = 910.
21
________________________________________________________________________________
Если старший бит управляющего байта равен 0, то при распаковке архива нужно взять несколько следующих байтов без изменений. Число байтов, которые берутся без изменений, указывается в оставшихся семи битах.
Например, управляющий байт 00000011 говорит, что следующие за ним 3
байта нужно взять без изменений.
Рассмотрим пример архивации методом RLE.
Выполним сжатие сообщения «ИНН 22223133333» методом RLE.
Текст
И
Н
Н
Пробел
2
2
2
2
3
1
3
3
3
3
3
Десятичный код
(таблица CP-1251)
200
205
205
32
50
50
50
50
51
49
51
51
51
51
51
Двоичный код
Архив
11001000
11001101
11001101
00100000
00110010
00110010
00110010
00110010
00110011
00110001
00110011
00110011
00110011
00110011
00110011
00000001
11001000
10000010
11001101
00000001
00100000
10000100
00110010
00000010
00110011
00110001
10000101
00110011
Таким образом, пятнадцать байт исходного текста сжаты до тринадцати байт. Коэффициент сжатия в данном случае составил:
Kc 
15
 1,154.
13
22
_________________________________________________________________
2.3.
Метод сжатия LZW
Алгоритм Лемпеля-Зива-Велча (LZW) является одним из широко используемых алгоритмов сжатия данных без потерь. Этот алгоритм применяется для сжатия данных популярных мультимедийных файлов формата: GIF,
TIFF, PDF.
При рассмотрении данного материала будут использованы термины:
сообщение, архив, словарь.
Сообщение – документ (текст, изображение, видео или звуковой
файл), который подвергается сжатию.
Архив – сообщение, подвергнутое обработке, в результате которого
размер файла уменьшается, а объём информации остаётся прежним.
Словарь – набор сочетаний символов (фраз), входящих в сообщение,
которым поставлены в соответствии коды.
В алгоритме LZW (а отличии от алгоритмов Хаффмана, ШеннонаФано) не требуется в архиве сохранять таблицу кодировки (словарь).
Во время выполнения сжатия информации по алгоритму LZW отдельные символы кодируются с помощью стандартных кодовых таблиц, например, CP-1251. Коме того, создаётся дополнительная кодовая таблица
(словарь) для встретившихся в сообщении сочетаний букв. Если в дальнейшем в сообщении встретится имеющееся в словаре сочетание символов
(фраза), то в архив помещается код этого сочетания символов.
Во время распаковки архива словарь поэтапно восстанавливается.
Для распаковки информации необходимо знать использованную кодовую
таблицу (для кодирования отдельных символов) и выбранную для архивации
длину фраз в словаре (например, 9 бит).
Пример сжатия.
Дано сообщение, которое необходимо сжать методом LZW:
абаабабаба.
Шаг 1. Считываем первый символ сообщения – символ “а”, и ищем
его в таблице СР-1251. В начале работы алгоритма словарь пуст, поэтому
код берётся из таблицы. Десятичный код символа “а” имеет значение 224. В
это же время формируется словарь. Для кода 256 записывается первый символ фразы “а” и ожидается следующий символ из сжимаемого сообщения (в
таблице, представленной ниже, ожидание символа отмечается знаком “?”).
Код в архиве
224
Символ в архиве
Код в словаре
256
Фраза в словаре
а?
23
________________________________________________________________________________
Шаг 2. Считываем следующий символ сообщения – символ “б”.
Ищем в словаре сочетание “аб”, такого сочетания нет, поэтому записываем
в архив число 224 (код символа “а”). В таблице коду 256 ставится в соответствие фраза “аб”, а для значения 257 - “б” с ожиданием следующего символа
сообщения.
Код в архиве
224
Символ в архиве
а
Код в словаре
256
257
Фраза в словаре
аб
б?
Шаг 3. Считываем следующий символ – символ “а”. Ищем в словаре
сочетание “ба”, такого сочетания нет, поэтому записываем в архив число 225
(код “б”). В словаре коду 257 ставится в соответствие фраза “ба”, а для значения 258 - “а” с ожиданием следующего символа сообщения.
Код в архиве
224
225
Символ в архиве
а
б
Код в словаре
256
257
258
Фраза в словаре
аб
ба
а?
Шаг 4. Считываем следующий символ – символ “а”. Ищем в словаре
сочетание “аа”, такого сочетания нет, поэтому записываем в архив число 224
(код “а”). В таблице коду 258 ставится в соответствие фраза “аа”, а для значения 259 - “а” с ожиданием следующего символа сообщения.
Код в архиве
224
225
224
Символ в архиве
а
б
а
Код в словаре
256
257
258
259
Фраза в словаре
аб
ба
аа
а?
Шаг 5. Считываем следующий символ – символ “б”. Ищем в словаре сочетание “аб”, такая фраза есть (256). В словаре код 259 ставится в
соответствие фразе “аб” с ожиданием следующего символа.
Код в архиве
224
225
224
Символ в архиве
а
б
а
Код в словаре
256
257
258
259
Фраза в словаре
аб
ба
аа
аб?
24
_________________________________________________________________
Шаг 6. Считываем следующий символ – символ “а”. Ищем в словаре
сочетание “аба”, такого сочетания нет, поэтому записываем в архив число
256 (код “аб”). В таблице коду 259 ставится в соответствие фраза “аба”, а для
значения 260 - “а?” с ожиданием следующего символа сообщения.
Код в архиве
224
225
224
256
Символ в архиве
а
б
а
аб
Код в словаре
256
257
258
259
260
Фраза в словаре
аб
ба
аа
аба
а?
Шаг 7. Считываем следующий символ – символ “б”. Ищем в словаре
фразу “аб”, такое сочетание есть (256 в таблице). В словаре коду 260 ставится в соответствие фраза “аб” с ожиданием следующего символа.
Код в архиве
224
225
224
256
Символ в архиве
а
б
а
аб
Код в словаре
256
257
258
259
260
Фраза в словаре
аб
ба
аа
аба
аб?
Шаг 8. Считываем следующий символ – символ “а”. Ищем в словаре
сочетание “аба”, такое сочетание есть (259). Коду 260 ставится в соответствие сочетание “аба” с ожиданием следующего символа.
Код в архиве
224
225
224
256
Символ в архиве
а
б
а
аб
Код в словаре
256
257
258
259
260
Фраза в словаре
аб
ба
аа
аба
аба?
Шаг 9. Считываем следующий символ сообщения – символ “б”.
Ищем в словаре фразу “абаб”. Такой фразы нет, поэтому записываем в архив
число 259 (код фразы “аба”). В словаре код 261 ставится в соответствие “б,”
с ожиданием следующего символа.
25
________________________________________________________________________________
Код в архиве
224
225
224
256
259
Символ в архиве
а
б
а
аб
аба
Код в словаре
256
257
258
259
260
261
Фраза в словаре
аб
ба
аа
аба
абаб
б?
Шаг 10. Считываем следующий символ – символ “а”. Ищем в словаре сочетание “ба”, такое сочетание есть 257 (код “ба”), так как это последний символ то записываем в архив.
Таким образом итоговая таблица имеет следующий вид:
Код в архиве
224
225
224
256
259
257
Символ в архиве
а
б
а
аб
аба
ба
Код в словаре
256
257
258
259
260
Фраза в словаре
аб
ба
аа
аба
абаб
Таким образом, текст абаабабаба закодирован десятичными числами:
224 225 224 256 259 257. Десять символов представлены шестью десятичными числами. При переводе десятичные числа следует заменить девятибитными двоичными числами.
В двоичном виде архив будет выглядеть так:
011100000 011100001 011100000 100000000 100000011 100000001
В предыдущей строке между символами для наглядности поставлены
пробелы. Фактически их в архиве нет.
26
_________________________________________________________________
3. Помехоустойчивое кодирование
При работе устройств вычислительной техники и телекоммуникационной аппаратуры возможно появление ошибок в обрабатываемых цифровых данных. Причинами сбоев могут быть мощные электромагнитные помехи, малый уровень принимаемого сигнала (например, от космического аппарата, находящегося на комете), резкое изменение напряжения питания,
старение радиоэлементов, ненадёжный контакт разъёмов, радиоактивное излучение естественных и искусственных источников и т.п. Сбои проявляются
в виде случайного изменения одного или нескольких битов машинного слова
(вместо единицы в отдельных разрядах передаётся ноль или наоборот).
Автоматическое обнаружение и исправление ошибок сопровождается
введением избыточности в передаваемые или хранимые данные. Для этих
целей разработаны специальные коды, в которые помимо информационных
битов b1b2 ...bn дополнительно вводят контрольные (проверочные) биты
k1k 2 ...k m . Контрольные биты позволяют проверять целостность (неискажённость) информационных битов машинного слова, а наиболее сложные коды
могут не только обнаружить, но и исправить неверно принятые биты.
Разработанные помехоустойчивые коды позволяют решать разные задачи: обнаружить одиночную ошибку, обнаружить и исправить единственную ошибку, обнаружить и исправить несколько ошибок. Первые коды
называются обнаруживающими, а вторые – корректирующими кодами.
Простейший код, предназначенный для обнаружения одной ошибки
(точнее – для обнаружения нечётного числа ошибок), основан на добавлении
к информационным битам одного контрольного бита. При этом контрольный бит должен быть таким, чтобы суммарное число единиц в образованном
машинном слове было чётным. Добавляемый бит называется битом паритета.
Проверочный бит k для n-битного двоичного слова b1b2 ...bn вычисля-
ется по формуле:
1, если b1  b2  ...  bn  1
k  
 0, если b1  b2  ...  bn  0
В результате такого преобразования формируется (n+1) – битное
слово b1b2 ...bn k , число единиц в котором будет чётное.
Рассмотрим пример.
Пусть дан байт 10111100. Число информационных единиц в этом
байте нечётное, поэтому бит паритета нужно установить равным единице. В
результате этого получается машинное слово 101111001.
27
________________________________________________________________________________
Идею обнаружения и определения неверно принятого бита можно
проиллюстрировать с помощью кода Хэмминга. Для иллюстрации принципа
кодирования можно воспользоваться диаграммами Вена [6]. Пусть передаётся сообщение 1010.
Окружности A, B и C дают
семь сегментов. В четыре
внутренних сегмента помещаются информационные биты
числа 1010 (см. рис. a). Оставшиеся три сегмента дополняются контрольными битами
(рис. b).
Правило формирования
контрольных битов такое: в
каждой окружности должно
быть чётное число единиц. В
данном случае в каждой
окружности получилось по две
единицы. Пусть в процессе передачи информации один информационный бит будет искажён (рис. с). На приёмной
стороне осуществляется анализ принятой информации. Легко заметить, что
в окружности С число единиц осталось чётным, а окружностях А и В число
единиц стало нечётным. Это говорит о том, что искажённый бит находится
в сегменте, который принадлежит окружностям А и В, но не принадлежит
окружности С (рис. d).
3.1. Код Хэмминга
Рассмотрим пример нахождения искажённого бита с помощью кода
Хэмминга. Места расположения информационных битов (ИБ) и контрольных битов (КБ) в передаваемых данных указаны в следующей таблице. В
верхней строке таблицы записан порядковый номер каждого бита в машинном слове.
№
12 11 10
9
8
7
6
5
4
3
2
1
раз
.
ИБ
b
b
b
b
b
b
b
b
8
КБ
7
6
5
4
k8
3
1
2
k4
k2
k1
28
_________________________________________________________________
Форма записи машинного слова, приведённая в предыдущей таблице,
выбрана такой с целью повышения наглядности (из методических соображений). Фактически данные представляют единым двенадцатибитным машинным словом: b8b7b6b5 k8b4b3b2 k4b1k2 k1 .
Предположим, что в процессе передачи некоторых данных произошло искажение одного информационного бита и на приёме получены указанные в следующей таблице данные. Требуется найти и исправить искажённый информационный бит.
Разряд
Слов
о
ИБ
КБ
12
11
10
9
8
7
6
5
4
3
2
1
b8
b7
b6
b5
k8
b4
b3
b2
k4
b1
k2
k1
1
0
0
0
1
1
0
0
0
0
1
1
Вычислим значения контрольных битов на приёме. Будем обозначать проверочные биты на приёме со штрихом (чтобы отличить их от контрольных битов, сформированных на передающей стороне). Расчёт производится по формулам [6]:
k1`  b1  b2  b4  b5  b7 ;
k 2`  b1  b3  b4  b6  b7 ;
k4`  b2  b3  b4  b8 ;
k8`  b5  b6  b7  b8 .
Используя предыдущие формулы и исходные данные, получим значения контрольных битов на приёме:
k1`  1  0  1  0  0  0;
k2`  1  1  1  0  0  1;
k 4`  0  1  1  1  1;
k8`  0  0  0  1  1.
Расчёты показывают, что контрольные биты, сформированные на передающей и приёмной сторонах, различаются:
k1`  k1 ; k 2`  k 2 ; k 4`  k 4 ; k8`  k8 .
Различие контрольных битов, сформированных на передающей и
приёмной сторонах, говорит о том, что в процессе передачи произошло искажение машинного слова. Теперь необходимо определить, какой именно
бит был принят неверно.
29
________________________________________________________________________________
Для определения неверно принятого бита требуется вычислить так
называемый синдром S  s8 s 4 s 2 s1 , где
s1  k1`  k1 ; s 2  k 2`  k 2 ; s4  k 4`  k 4 ; s8  k8`  k8 .
Используя результаты расчётов и исходные данные, можно определить
четыре бита синдрома:
s1  0  0  0; s 2  1  0  1; s 4  1  1  0; s8  1  0  1.
Перевод синдрома S = 10102 из двоичной системы счисления в десятичную СС даёт значение S = 1010. Десятичное число 10 говорит о том, что
десятый разряд принятых данных (b6) искажён, и этот бит нужно исправить
(проинвертировать). Таким образом, после корректировки принятые данные
будут иметь вид, показанный в следующей таблице. Напомним, что счёт разрядов ведётся справа налево.
Разряд
Слов
о
ИБ
КБ
12
11
10
9
8
7
6
5
4
3
2
1
b8
b7
b6
b5
k8
b4
b3
b2
k4
b1
k2
k1
1
0
1
0
1
1
0
0
0
0
1
1
3.2. Код БЧХ
Устранить две ошибки (и более) в принятых данных позволяют циклические коды Боуза-Чоудхури-Хоквингема (БЧХ).
Циклический код БЧХ v(x) на передающей стороне формируется следующим образом [7]:
(1)
v( x)  x nk u ( x)  ( x nk u ( x) mod(g ( x))) ,
где x – фиктивная переменная; u(x) - кодируемая последовательность
данных (информационные биты, сообщение); n – число бит в передаваемых
данных (суммарное число информационных и контрольных бит); k - число
информационных бит в машинном слове; mod - операция вычисления
остатка от деления; + - операция конкатенации (соединения, склеивания) информационных и контрольных битов; g(x) – порождающий полином.
В приведённом выше выражении первое слагаемое описывает информационные биты, сдвинутые влево на
x n  k разрядов. Этим умножением ин-
формационные биты были смещены влево на число разрядов, равное числу
30
_________________________________________________________________
контрольных битов. Второе слагаемое в выражении (1) описывает контрольные биты.
Выберем одну из разновидностей БЧХ с кодовой последовательностью длиной n = 15. Данный код формируется с помощью порождающего
полинома восьмой степени (r = 8):
g ( x)  x 8  x 7  x 6  x 4  1 .
Число информационных разрядов в таком коде k = n – r = 15 – 8 = 7.
Код позволяет исправить две ошибки (s = 2).
Рассмотрим порядок построения циклического кода БЧХ на передающей стороне.
Дано 7 информационных бит 1011011. Запишем указанные информационные биты в виде полинома:
(2)
u ( x)  x 6  x 4  x 3  x  1 .
Порядок построения полинома u(x) иллюстрирует следующая таблица:
Номера
разрядов
Слагаемые
7
6
x6
x5
5
4
3
2
1
x3
x2
x
1
x4
Таблицу нужно трактовать следующим образом: если в соответствующем разряде данных информационный бит равен единице, то в полином
нужно включить нижерасположенный член ряда. Этим объясняется отсутствие в полиноме (2) слагаемых x 2 и x5 .
Для нахождения первого слагаемого в выражении (1) нужно полином
8
(2) умножить на x (число контрольных битов n  k  15  7  8 ):
(3)
x nk  u (x)  x8  ( x6  x 4  x3  x  1)  x14  x12  x11  x9  x8 .
Смысл предыдущей операции очень прост: информационные разряды
за счёт умножения на x8 смещаются влево на восемь позиций (в сторону
старших разрядов). Это сделано для того, чтобы разделить в машинном
слове информационные и контрольные биты (информационные разряды будут располагаться в передаваемых данных слева, а контрольные биты –
справа).
Для нахождения контрольных битов нужно найти остаток от деления
полинома (3) на порождающий полином g(x):
( x14  x12  x11  x9  x8 ) mod(x8  x7  x 6  x 4  1) 
 x 6  x5  x3  x 2  1 .
(4)
Именно контрольные биты (4) позволяют на приёмной стороне опре-
31
________________________________________________________________________________
делить, есть ли искажения и при необходимости восстановить неверно принятые биты. Сформированный в соответствии с (1) помехоустойчивый код
БЧХ описывается полиномом:
(5)
v( x)  x14  x12  x11  x 9  x 8  x 6  x 5  x 3  x 2  1 .
Чтобы проверить верно ли сформирован полином (5), достаточно его
разделить на порождающий полином g(x). Если остаток от деления равен
нулю, то код сформирован правильно. В соответствии с полиномом (5) в линию нужно передать двоичный код:
101101101101101.
(6)
Несложно заметить, что первые семь бит сформированного кода полностью совпадают с информационными битами (с сообщением). Следующие
восемь бит в коде (6) являются контрольными. Соотношение между числом
информационных и контрольных битов наглядно показывает, почему такие
коды называют избыточными.
В процесс передачи по каналу связи (или записи в память цифрового
устройства) сформированный код БЧХ v(x) может быть искажён и на приём
поступит код f (x) . Декодирование полученных данных f (x) происходит в
соответствии со следующим алгоритмом:
1) выполняется деление принятой последовательности f (x) на порождающий полином g (x) ;
2) вычисляется вес остатка w (количество единиц в остатке);
3) если w  s , где s – число ошибок, исправляемых данным кодом,
то производится циклический сдвиг влево на один разряд принятой последовательности f (x ) и вновь выполняется шаг 1. Математически операция
сдвига влево эквивалентна операции умножения полинома на х. Если получается фиктивная переменная х в степени 15, то в младшем разряде полинома нужно записать 1;
4) если w  s , то производится суммирование полученной последовательности с остатком;
5) производится циклический сдвиг полученной последовательности
вправо на количество разрядов, равное числу сдвигов влево, выполненное в
процессе декодирования принятой последовательности (в процессе деления).
32
_________________________________________________________________
При описании алгоритма декодирования использован термин «циклический сдвиг». Сдвиг – это изменение позиций битов в машинном слове на одну и ту
же величину. Следующий рисунок иллюстрирует порядок перемещения битов при
циклических сдвигах влево и вправо.
На рисунке приняты обозначения:
LSB – младший значащий разряд; MSB –
старший значащий разряд.
Рассмотрим процесс декодирования
на примере кода, сформированного ранее.
Предположим, что в данных (6) произошло искажение разрядов 13 и 11. В результате на приём поступило двоичное число
111001101101101. Следует обратить внимание, что счёт разрядов начинается с нуля.
Запишем это число в виде полинома:
f ( x)  x14  x13  x12  x 9  x 8  x 6  x 5  x 3  x 2  1 .
Выполним декодирование. Результаты расчётов на каждой итерации
поместим в таблицу. Так как данный код позволяет исправлять две ошибки
(s = 2), расчёты следует вести до тех пор, пока не будет выполнено условие
w ≤ 2.
В таблице использованы такие обозначения:
C i (x) - частное от деления f i (x) на порождающий полином g (x) на
i – той итерации; P i (x) - остаток от деления f i (x) на порождающий полином
g(x) на i – той итерации.
На пятой итерации вес остатка достиг значения, при котором следует
прекратить дальнейшие расчёты (w = 2). За пять проведённых итераций было
выполнено четыре циклических сдвига влево.
Выполненные операции позволяют наглядно понять, почему этот код
называю циклическим. При выполнении сдвига влево крайний левый разряд
считался соседним с крайним правым разрядом. По этой причине на итерациях 2, 3, 4 последними слагаемыми полиномов f i (x) являются единицы.
Это объясняется тем, что в этих случаях x14  1 и единица переходит в младший разряд последовательности. На пятой итерации полином f 5 ( x) не содержит слагаемого, равного 1. Это происходит потому, что на предыдущей
итерации x14  0 .
33
________________________________________________________________________________
Ит.
1
2
3
4
5
Полиномы
f 1 ( x)
x14  x13  x12  x 9  x 8  x 6  x 5  x 3  x 2  1
C 1 ( x)
x6  x2
P 1 ( x)
x6  x5  x3  1
f 2 ( x)
x14  x13  x10  x 9  x 7  x 6  x 4  x 3  x  1
C 2 ( x)
x6  x4  x3  1
P 2 ( x)
x7  x6  x4  x
f 3 ( x)
x14  x11  x10  x 8  x 7  x 5  x 4  x 2  x  1
C 3 ( x)
x6  x5  x
P 3 ( x)
x6  x5  x4  x2  1
f 4 ( x)
x12  x11  x 9  x 8  x 6  x 5  x 3  x 2  x  1
C 4 ( x)
x4  x2 1
P 4 ( x)
x7  x6  x5  x3  x
f 5 ( x)
x13  x12  x10  x 9  x 7  x 6  x 4  x 3  x 2  x
C 5 ( x)
x5  x3  x  1
P 5 ( x)
x2 1
Вес
w
4
4
5
5
2
В соответствии с алгоритмом декодирования теперь следует перейти
к шагу 4 и найти сумму полинома и остатка на последней итерации:
R( x )  f 5 ( x )  P 5 ( x ) 
 x13  x12  x10  x 9  x 7  x 6  x 4  x 3  x 2  x  x 2  1 
(7)
 x13  x12  x10  x 9  x 7  x 6  x 4  x 3  x  1.
Полученный полином (7) преобразуем в двоичное число:
R(x) = 011011011011011.
(8)
В соответствии с шагом 5 алгоритма декодированную последовательность (8) нужно циклически сдвинуть вправо на четыре разряда. Этапы
сдвига показаны в таблице.
34
_________________________________________________________________
Номера сдвигов
R(x)
1 сдвиг
2 сдвиг
3 сдвиг
4 сдвиг
Числа
011011011011011
101101101101101
110110110110110
011011011011011
101101101101101
Первые семь битов двоичного числа, полученного после четвёртого
циклического сдвига вправо, являются информационными битами, в которых были исправлены две ошибки.
Таким образом, в результате декодирования получено число 1011011,
которое точно совпадает с переданным числом.
Этот пример наглядно демонстрирует возможность автоматического
исправления возникших ошибок.
Заметим, что операцию циклического сдвига вправо можно осуществить с помощью полиномов путём деления на х.
35
________________________________________________________________________________
4.
Криптографические методы защиты информации
Рассмотрим основные идеи шифрования.
Обозначим открытый текст символом М (от англ. Message, сообщение). Сообщение М в процессе шифрования на передающей стороне преобразуют таким образом, чтобы сделать его недоступным для прочтения противником. Для преобразования открытого текста используют шифратор, который может быть построен аппаратным или программным путём. Алгоритм работы шифратора описывается функцией шифрования E (Encrypting).
Зашифрованный текст (криптограмму) обозначим символом С
(Cryptogram). Шифратор преобразует открытое сообщение М, создавая нечитаемую криптограмму С:
Е(М) = С.
Очевидно, что вид криптограммы зависит как от исходного сообщения, так и от алгоритма работы шифратора.
На приёмной стороне дешифратор D, работа которого описывается
функцией дешифрования D (Decrypting), восстанавливает открытое сообщение М:
D(С) = М.
Понятно, что функции шифрования и дешифрования должны быть
обратимыми (симметричными), и на приёмной стороне должно быть принято сообщение, совпадающее с отправленным:
D(Е(М)) = М.
Если криптостойкость зашифрованного сообщения основана лишь на
сохранении в тайне самого алгоритма шифрования, то такой алгоритм в соответствии с правилом Керкгоффса использовать недопустимо. Такие алгоритмы представляют только исторический и учебный интерес.
Криптостойкость современных шифров основывается на секретном
ключе К (Key). Каждый ключ определяет, какой конкретный вид преобразований используется в данном случае (при неизменном и известном алгоритме шифрования). Результаты шифрования и дешифрования зависят от
используемого ключа. При шифровании:
ЕК(М) = С,
где ЕК – функция шифрования на ключе К.
При дешифровании:
DК(С) = М,
где DК – функция дешифрования на ключе К.
Естественно, что при всех преобразованиях, производимых в процессе передачи сообщения, должно выполняться соотношение:
DК(ЕК(М)) = М.
Последние соотношения выполняются в симметричных шифрах, у
36
_________________________________________________________________
которых ключи на предающей и приёмной сторонах одинаковые (или связаны между собой очевидным способом). Перечислим наиболее известные
современные симметричные шифры: ГОСТ 28147-89, AES, CAST5, IDEA,
Blowfish, Twofish.
При использовании асимметричных шифров (шифры с открытым
ключом) на передающей и приёмной сторонах используются разные ключи
К1 и К2:
При шифровании выполняется соотношение:
EK1(M) = C,
где EK1 – функция шифрования на ключе К1.
Ключ К1 не секретный, он публикуются в доступных источниках.
При дешифровании криптограммы на приёмной стороне используется ключ К2:
DK2(C) = M,
где DK2 – функция дешифрования на ключе K2.
Ключ К2 секретный, он известен только на приёмной стороне. Ключ
К2 функционально связан с ключом К1. Однако установить эту связь с помощью современной вычислительной техники сложно.
Весь процесс передачи шифрованного сообщения по схеме с двумя
ключами описывается соотношением:
DK2(EK1(M)) = M.
Криптостойкость рассмотренных алгоритмов базируется на секретных ключах, а не на секретном алгоритме (способе) шифрования. Секретным является ключ, а алгоритм шифрования (шифр), как правило подвергается детальному публичному анализу.
Симметричные и асимметричные алгоритмы используются по-отдельности, но разработана криптографическая система, которая сочетает
сильные стороны этих алгоритмов.
Гибридная криптосистема — это система шифрования, совмещающая достоинства симметричной и асимметричной криптосистем.
Достоинствами симметричной криптосистемы является высокая скорость шифрования и относительно кроткие ключи. Её недостаток – необходимость передачи ключей по секретному каналу связи. Асимметричная
криптосистема позволяет передавать ключи по открытому каналу связи, однако скорости шифрования и расшифрования низкие.
В гибридной криптосистеме симметричный алгоритм используется
для шифрования открытого текста, а асимметричный алгоритм - для шифрования симметричного ключа.
В курсовой работе будут использованы два симметричных шифра:
аддитивный шифр (гаммирования) и шифр с управляемыми
операциями.
37
________________________________________________________________________________
4.1.
Области использования криптографии
Криптография используется не только для защиты передаваемой информации. Результаты, полученные при разработке асимметричных шифров, методы вычисления хэш-функции применяются при эмиссии (создании)
криптовалюты (цифровых денег) и выполнении транзакций (перечисления
финансовых средств).
В настоящее время в мире существует более 1000 видов цифровых денег. Кроме широкоизвестных биткоинов получили распространение: Альткоины, Peercoin, Namecoin, Feathercoin, Freicoin, Ethereum, Ripple, Litecoin,
Primecoin, Dash, Nem и др.
Каждая новая монета криптовалюты создаётся путём затраты большого времени работы ЭВМ и ресурсов (электроэнергии). Физически криптовалюты не существуют, это виртуальные деньги. Нет ассигнаций или монет в виде биткоинов. Есть только специальные реестры, в которых ведётся
учёт, сколько у кого биткоинов и кто куда их переводит [14].
Эти реестры (журналы) называются блокчейнами. Гарантией надёжности криптовалюты являются распределённо хранимые блокчейны и сложные математические соотношения, с помощью которых заверяются финансовые операции, заносимые в реестры.
Все реестры (блокчейны) у всех пользователей (владельцев биткоинов) идентичны. Изменения в бокчейнах происходит на всех компьютерах
одновременно, синхронно.
Использование криптовалюты имеет сходство с безналичными платежами. Когда происходит оплата картой в магазине, покупатель физически не
передаёт продавцу деньги или золото. Просто где-то в банковском реестре
прописывается сделанная операция (транзакция).
Биткоины отличаются от обычной валюты тем, что реестры хранятся
не централизованно в банках и платёжных системах, а одновременно на многих компьютерах.
Реестры защищены криптографически. Подделать их одновременно
на всех компьютерах, где хранятся реестры нельзя. Биткоин в этом смысле
надёжно защищён. Правда, уже существует атака, которая позволяет дважды
рассчитаться одними и теми же биткоинами. Сказать, что биткоин абсолютно безопасен, нельзя.
Обычную валюту выпускает государство. Очень опосредованно
объём валюты связан с запасами золота государства. Фактически, сколько
государству нужно, столько оно и печатает денежных знаков.
Эмиссия биткоинов не происходит в одном каком-то государстве. Эта
валюта интернациональна. Новые единицы биткоина появляются в процессе
того, как компьютеры в этой платёжной сети обслуживают нужды этой же
38
_________________________________________________________________
самой сети.
Например, если в какой-то стране человек заплатил биткоинами за некоторую продукцию, то эту операция будет записана в реестры на всех компьютерах, которые подключены к биткоиновой сети. Чтобы записать операцию в реестр, нужно заверить её цифровой подписью. Цифровая подпись
формируется с помощью ЭВМ. Это достаточно сложная вычислительная задача.
Предположим, что у некоторого пользователя установлен компьютер,
который обслуживает биткоиновую сеть, и на этом компьютере была вычислена криптографическая подпись. В знак благодарности (оплаты за работу)
владелец этого компьютера получает вознаграждение в виде некоторого
числа биткоинов (так происходит эмиссия).
Для пользователя, который установил компьютер в режим вычисления криптографических подписей, это выглядит так: его компьютер производит вычисления, а ему на счёт в качестве вознаграждения поступают биткоины. Компьютер как будто добывает биткоины, хотя на самом деле он
просто шифрует и подписывает чужие финансовые операции. Это процесс
называется майнингом.
Биткоины — это вознаграждение за некоторые сделанные на ЭВМ
вычисления. Ценность биткоина держится исключительно на сложном процессе создания каждой новой единицы виртуальных денег.
Майнинг — способ эмиссии криптовалюты, основанный на выполнении математических операций с помощью ЭВМ.
Работа майнеров (специалисты, занимающиеся майнингом) заключается в подборе правильного хэша, который подойдёт ко всем транзакциям,
находящимся в сети, и обеспечит получение секретного ключа. Возможных
комбинаций – миллионы, поэтому процесс, как правило, занимает много
времени и требует наличия мощного оборудования.
Транзакция - запись о том, с какого кошелька на какой кошелёк, какая сумма переводятся, а также, время и дата операции. Эта запись (её хэш)
подписывается закрытым ключом отправителя и рассылается всем в ожидании подтверждения.
39
________________________________________________________________________________
4.2.
Шифр гаммирования
При шифровании аддитивным методом вначале открытый текст
шифруют методом замены, преобразуя каждую букву в число. Затем к каждому числу прибавляют секретную гамму (псевдослучайную числовую последовательность). Технически добавление гаммы к открытому тексту в
криптографических системах осуществляется поразрядно (поточный шифр).
Процедуру добавления гаммы удобно реализовать с помощью двоичных чисел. При этом на каждый бит открытого текста накладывается бит секретной
гаммы.
Генератор гаммы выдаёт последовательность битов: 1, 2, 3,…, n.
Этот поток битов и поток битов открытого текста p1, p2, p3,…, pn подвергаются поразрядно логической операции Исключающее ИЛИ. В результате получается поток битов криптограммы:
ci = pi  i.
При дешифровании на приёмной стороне операция Исключающее
ИЛИ выполняется над битами поступившей криптограммы и тем же самым
потоком гаммы:
pi = ci  i .
Благодаря особенностям логической операции Исключающее ИЛИ на
приёмной стороне операция вычитания заменяется данной логической операцией. Сказанное иллюстрируется примером.
Предположим, что открытый текст Р = 10011001, а гамма G =
11001110. В результате шифрования криптограмма С будет иметь следующий вид:
Р
G
C
1
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
1
0
1
1
1
0
1
На приёмной стороне повторно выполняется логическая операция Исключающее ИЛИ:
C
G
Р
0
1
1
1
1
0
0
0
0
1
0
1
0
1
1
1
1
0
1
1
0
1
0
1
Из этих таблиц видно, что переданный и принятый байты одинаковые.
В ЭВМ преобразование открытого текста в числа происходит естественным путём, так как каждый символ кодируется двоичным числом. Вид
40
_________________________________________________________________
этого преобразования зависит от используемой операционной системы. Для
определённости будем считать, что сообщение в ЭВМ кодируется с помощью кодовой таблицы CP-1251. Итак, будем считать, что секретная гамма
добавляется к открытому тексту по правилу сложения по модулю два без
переносов в старшие разряды (логическая операция Исключающее ИЛИ).
Результаты всех преобразований поместим в таблицу.
Открытый текст
Г
Д
Е
А
Б
Б
А
Десятичное число
195
196
197
192
193
193
192
11000011 11000100 11000101 11000000 11000001 11000001 11000000
Двоичное число
Гамма (десятич.)
32
18
36
11
61
23
3
00100000 00010010 00100100 00001011 00111101 00010111 00000011
Гамма (двоич.)
Криптогр. (двоич.) 11100011 11010110 11100001 11001011 11111100 11010110 11000011
Криптогр. (десят.)
227
214
225
203
252
214
195
Криптограмма
г
Ц
б
Л
ь
Ц
Г
Для наглядности результат шифрования (шифрограмма) переведён с
помощью таблицы CP-1251 в буквы. Из таблицы видно, что открытый текст
был записан прописными буквами, а криптограмма содержит как прописные, так и строчные буквы.
Естественно, что при реальном (а не учебном) шифровании набор
символов в шифрограмме будет ещё богаче. Кроме русских букв будут присутствовать латинские буквы, знаки препинания, управляющие символы.
41
________________________________________________________________________________
4.3.
Шифр с управляемыми операциями
Напомним, что основная идея шифра гаммирования заключается в замене символов открытого текста на числа и суммировании их с псевдослучайными числами, которые называются «гаммой». При этом состав гаммы
известен только доверенным лицам на передающей и приёмной сторонах.
Известны методы взлома этого шифра. Скомпрометировать шифр
можно в случаях нештатного использования гаммы (некачественный состав
гаммы, малая длина или повторное использование одной и той же гаммы для
шифрования разных сообщений).
Источником уязвимости аддитивного шифра является логическая
операция Исключающее ИЛИ, которая используется для зашифрования и
расшифрования.
Известно интересное свойство этой логической операции:
M GG  M .
Соотношение говорит о том, что наличие чётного числа одинаковых
слагаемых, участвующих в операции Исключающее ИЛИ, уничтожает эти
слагаемые. Таким образом, если определить период циклически повторяющейся гаммы и выполнить логическую операцию Исключающее ИЛИ над
символами криптограммы с одинаковыми значениями гаммы (с одинаковыми фазами), то можно уничтожить гамму. В результате такого преобразования получаются данные, представляющие собой результат выполнения логической операции Исключающее ИЛИ над символами открытого текста:
R  Ci  Ci T  M i  Gi  M i T  Gi T  M i  M i T
Это объясняется тем, что Gi  Gi T , то есть элементы гаммы повторяются с периодом Т и поэтому они одинаковые. Если гамма дважды использована для шифрования двух разных текстов, то задача криптоанализа становится ещё проще: достаточно выполнить операцию Исключающее ИЛИ
над двумя криптограммами. Известен пример неверного использования метода гаммирования в операционной системе Windows 95. Одна и та же гамма
применялась несколько раз для шифрования данных в файлах PWL (эти
файлы хранят логины и пароли).
Величину R можно назвать разностью открытых текстов (сообщений). Разность R может быть подвержена успешному криптоанализу путём
учёта статистических закономерностей открытых текстов или использования известных из других источников их особенностей.
Часто структура нескольких разных криптограмм бывает одинаковой.
Например, начинаться словами «Совершенно секретно». Это даёт зацепку
для криптоаналитиков.
42
_________________________________________________________________
Таким образом, в аддитивном методе шифрования из-за симметричности (обратимости) логической операции Исключающее ИЛИ и нештатного использования гаммы существует возможность произвести криптоанализ и восстановить открытый текст даже без знания гаммы.
Повысить криптостойкость аддитивного шифра можно за счёт использования управляемых операций шифрования [9]. Основная идея данной
криптосистемы состоит в использовании в течение одного сеанса связи не
одной, а нескольких различных шифрующих операций. В этой криптосистеме вместе с изменением значения гаммы варьируются операции преобразования, выполняемые над открытым текстом (на передаче) и над криптограммой (на приёме). Причём на передаче и приёме операции зашифрования
и расшифрования должны синхронно чередоваться. Например, если на передаче осуществляется арифметическое сложение символа открытого текста с
элементом гаммы, то на приёме нужно вычесть гамму из полученной криптограммы. Синхронизация выполняемых операций должна осуществляться
под управлением гаммы, которая одновременно определяет и вид выполняемой операции, и сама участвует в этих операциях.
В курсовой работе предполагается использовать четыре различных
операций: две логические операции (равнозначность и неравнозначность) и
две арифметические операции (сложение и вычитание).
При этом если при шифровании используется логическая операция
Равнозначность, то при расшифровании – эта же операция. Понятно, что при
использовании на передающей стороне операции Неравнозначность принимающая сторона для расшифрования должна использовать эту же операцию.
При использовании логических операций шифрование одного символа даст четыре бита, а при использовании арифметических операций –
пять битов (необходимо учитывать значение переноса в старший разряд).
Очевидно, что при шифровании с помощью арифметического сложения расшифрование должно производиться арифметического вычитания и
наоборот.
43
________________________________________________________________________________
5.
Стеганографические методы защиты информации
Стеганография — это наука, изучающая такие методы организации
передачи (и хранения) секретных сообщений, которые скрывают сам факт
передачи информации [12].
Криптография превращает открытый текст в нечитаемый набор символов (шифрограмму). Шифрограмма передаётся по открытому каналу
связи, и криптостойкость держится на сложности подбора секретного
ключа. Факт передачи криптограммы не скрывается от противника.
Стеганография нацелена на сокрытие факта передачи информации.
Сообщение (его называют вложением) помещают (внедряют) в контейнер,
вид которого практически не изменяется от сделанного внедрения.
Скрываемое сообщение помещается внутри безобидного на вид контейнера таким образом, чтобы постороннему наблюдателю было бы сложно
заметить наличие встроенного тайного послания. Контейнерами могут быть
чемодан с двойным дном, монета с отворачивающейся крышкой, почтовая
марка с микроплёнкой, письмо, написанное симпатическими чернилами.
В данной разделе рассматриваются электронные контейнеры
(файлы), которые хранят (содержат) текстовую, графическую, звуковую, видео и другую информацию. Перечисленные виды контейнеров можно
назвать мультимедийными, хотя для скрытой передачи информации могут
быть использованы файлы любых форматов.
Все контейнеры можно разделить на контейнеры-оригиналы и контейнеры-результаты. Контейнер-оригинал (или «пустой» контейнер) — это
контейнер, который не содержит скрытой информации. Контейнер-результат (или «заполненный» контейнер, стего) — это контейнер, который содержит скрытую информацию. Под ключом понимается секретный элемент, который определяет порядок занесения (внедрения) сообщения в контейнер
Другими словами: ключ – это информация которая определяет порядок выбора адресов в мультимедийных файлах, использованные разряды семплов
звукового файла, номера отсчётов звукового файла, кадров в видеоклипе,
TCP/IP пакетов, нот в Midi-файлах и т.п.
Все контейнеры могут быть разделены на два типа: статические и динамические. Статические контейнеры могут быть использованы как для
скрытого хранения информации, так и для её скрытой передачи. Примером
может служить цифровая фотография. Динамические контейнеры могут
быть использованы только для скрытой передачи информации. В качестве
примера можно назвать пакеты, передаваемые по протоколу TCP/IP.
Число разнообразных контейнеров и методов внедрения вложений
44
_________________________________________________________________
велико. Многие приёмы сокрытия информации основываются на «обмане»
органов чувств человека. При сокрытии информации в графических и видео
файлах изменения кадров столь незначительны, что глаз человека не регистрирует эти изменения.
При сокрытии информации в текстовых документах умышленно выбирают цвета символов и бумаги одинаковыми (скажем, зелёные). В электронных документах используют невидимые (непечатаемые) символы (пробел, табуляцию).
В звуковых Midi-файлах незначительно изменяют длительности звучания нот и за счёт этого скрывают передаваемое сообщение. При вложении
информации в аудио файлы изменения контейнера не должны регистрироваться слухом человека.
Однако такие требования к степени сокрытия информации могут использоваться лишь в простейших случаях. При передаче ценной конфиденциальной информации сделанные вложения не должны обнаруживаться
даже с помощью специальных программно-аппаратных средств и профессиональных алгоритмов стегоанализа (например, с помощью статистического
анализа контейнеров, спектрального анализа и т.п.).
При сокрытии сообщений методами компьютерной стеганографии
часто используют информацию, скрытую в последнем (наименьшем) значащем бите LSB (Last Significant Bits). В отечественных публикациях для его
обозначения используют аббревиатуру НЗБ (наименьший значащий бит).
При цифровом представлении графики и звука последний бит контейнера
является малозначимым, часто изменяющимся по случайному закону.
Шумы, возникающие при аналого-цифровом преобразовании звука и изображения (шумы квантования), случайным образом изменяют последний бит
каждого отсчёта.
Рассмотрим простейший учебный пример.
Предположим, что имеется последовательность двоичных чисел (8
байт), отображающих в цифровом виде какой-то графический образ в формате BMP, либо восемь восьми битных семплов файла WAV формата:
10100001-10101110-11010110-1100111011000111-11001010-11010110-11101101
В данном примере каждое число контейнера представлено восьмью
битами информации. Во многих случаях последний бит может быть безболезненно изменён, и пользователь не заметит произошедшей подмены.
Например, при вариации младшего бита невозможно визуально заметить отличия в цветной графической картине, где каждый пиксель представлен двадцатью четырьмя битами. Также нельзя на слух уловить изменения, происходящие в звуковом файле с 16-ти битным квантованием по уровню.
45
________________________________________________________________________________
Предположим, что в приведённый выше фрагмент контейнера необходимо «запрятать» русскую букву «А», представленную с помощью кодовой таблицы CP-1251. Десятичное представление буквы «А» имеет вид
192D, а двоичное — 11000000B.
Модифицируя имеющийся блок двоичных чисел (контейнер), поместим в контейнер двоичное число 11000000В. При этом 8 бит файла-сообщения записываются в 8 чисел файла-контейнера:
10100000-10101110-11010110-11001110-11000110-11001010-1101011111101101
Эта же процедура внедрения скрытой информации иллюстрируется
следующей таблицей. Заметим, что здесь буква «А» записана, начиная с
младших битов.
Следующая таблица наглядно показывает порядок внедрения битов.
46
_________________________________________________________________
5.1.
Основные понятия аналого-цифрового
преобразования
Различают две формы представления информации — непрерывную
(аналоговую) и прерывистую (цифровую, дискретную). Непрерывная форма
характеризует процесс, который не имеет перерывов и теоретически может
изменяться в любой момент времени и на любую величину (например, речь
человека, музыкальное произведение). Цифровой сигнал может изменяться
лишь в определённые моменты времени и принимать лишь заранее обусловленные значения (например, только значения напряжений 0 и 3,5 В). Моменты возможного изменения уровня цифрового сигнала задаёт тактовый
генератор конкретного цифрового устройства.
Для преобразования аналогового сигнала в цифровой сигнал требуется провести дискретизацию непрерывного сигнала во времени, квантование по уровню, а затем кодирование отобранных значений.
Дискретизация — замена непрерывного (аналогового) сигнала последовательностью отдельных во времени отсчётов (семплов) этого сигнала
[10].
На рисунке схематично показан процесс преобразования аналогового
сигнала в цифровой сигнал. Цифровой сигнал в данном случае может принимать лишь пять различных уровней. Естественно, что качество такого преобразования невысокое. Из рисунка видно, что изменение цифрового сигнала возможно лишь в некоторые моменты времени (в данном случае этих
моментов одиннадцать).
После такого преобразования непрерывный сигнал представляют последовательностью чисел. Показанный на рисунке непрерывный сигнал заменяется числами 2-3-4-4-4-3-2-2-3-4-4. Десятичная система счисления в
рассматриваемом примере использована лишь для большей наглядности.
47
________________________________________________________________________________
Фактически аналоговый сигнал преобразуют в последовательность единиц
и нулей. Результаты данного преобразования можно представить таблицей:
Время
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
t11
Десятичные
числа
2
3
4
4
4
3
2
2
3
4
4
Двоичные
числа
0010
0011
0100
0100
0100
0011
0010
0010
0011
0100
0100
Здесь цифровые сигналы представлены четырьмя разрядами двоичных чисел. Очевидно, что, чем больше разрядов у двоичных чисел (то есть
чем больше число уровней квантования) и чем чаще во времени осуществляются отсчёты (выборки), тем точнее будет преобразован непрерывный
сигнал в цифровой.
Образное представление о качестве оцифрованного сигнала дают кинофильмы, снятые с разной скоростью. Первые немые фильмы были сняты
с частотой 16 кадров в секунду. Из-за низкой частоты съёмки некоторые
фазы движения объектов терялись, и перемещение персонажей на экране
становилось комичным, дёрганным. Переход на частоту 24 кадров в секунду
сняло эту проблему, движение стало плавным.
Предыдущий рисунок показывает, как влияет частота дискретизации
аналого-цифрового преобразования на качество оцифрованного сигнала. В
нижней части диаграмм показан исходный аналоговый сигнал (синусоида
частотой 1 кГц). В верхней части рисунков изображён сигнал после двойного
48
_________________________________________________________________
преобразования при разных значениях частоты дискретизации. В данном
случае аналоговый сигнал был вначале преобразован в цифровой, а затем
цифровой сигнал обратно конвертирован в аналоговый. Рисунки отличаются
использованной частотой дискретизации. В первом случае частота дискретизации составляла 8 кГц, во втором – 32 кГц. Из рисунка видно, что с ростом частоты дискретизации качество преобразования улучшается. На качество цифрового сигнала сильно влияет также его разрядность.
При цифровой аудиозаписи используется процесс выборки, заключающийся в периодическом измерении уровня (громкости, амплитуды) аналогового звукового сигнала (например, поступающего с выхода микрофона) и
превращении полученного значения в последовательность двоичных чисел.
Для преобразования аналогового сигнала в цифровой используется специальный конвертор, называемый аналогово-цифровой преобразователь
(АЦП). Сигнал на выходе АЦП представляет собой последовательность двоичных чисел, которая может быть обработана компьютером. Обратная конверсия цифрового сигнала в непрерывный сигнал осуществляется с помощью цифроаналогового преобразователя (ЦАП).
Качество аналогово-цифрового преобразования характеризует параметр, называемый разрешением. Разрешение — это количество уровней
квантования, используемых для замены непрерывного аналогового сигнала
цифровым сигналом. Восьмиразрядная выборка позволяет получить только
256 различных уровней квантования цифрового сигнала, а шестнадцатиразрядная выборка — 65 536 уровней.
Ещё один показатель качества трансформации непрерывного сигнала
в цифровой сигнал — это частота дискретизации — количество преобразований аналог-цифра (выборок), производимое устройством в одну секунду.
Этот показатель измеряют килогерцами (килогерц — тысяча выборок в секунду). Типичное значение частоты дискретизации— 44,1 кГц.
49
________________________________________________________________________________
5.2.
Структура звукового файла формата WAV
На рисунке показан дамп памяти некоторого звукового файла формата WAV. Этот дамп получен с помощью звукового редактора Audacity. С
помощью этого приложения сформирован монофонический звуковой сигнал
с частотой дискретизации 8 кГц и глубиной звука 16 бит.
Рассмотрим некоторые понятия, которые потребуются при изучении
последующего материала.
Семпл (отсчёт) – группа бит, полученная в результате аналого-цифрового преобразования, которая описывает уровень звуковой волны в короткий момент выполнения одного (отдельного) АЦП преобразования (за один
период частоты дискретизации).
Фрейм – группа семплов, находящихся в разных каналах и описывающая уровень звуковой волны за один период частоты дискретизации. Для
монофонического сигнала фрейм состоит из единственного семпла. Стереофонический фрейм состоит из двух семплов и т.д.
В самом начале дампа размещается информация об основных характеристиках звукового файла (ячейки памяти с адресами 00Н…2BH). Начиная с адреса 2СН и далее находятся данные, полученные в процессе аналогоцифрового преобразования исходного сигнала. Эта область обозначена на
рисунке цифрой 9.
В первых четырёх байтах дампа памяти размещены символы «RIFF»
(они обозначены цифрой 1). Буквы представлены в шестнадцатеричной системе счисления в соответствии с кодовой таблицей CP-1251.
С помощью аббревиатуры RIFF (англ. Resource Interchange File
50
_________________________________________________________________
Format) обозначен один из форматов файлов-контейнеров, который предназначен для хранения потоковых мультимедиа-данных (видео, аудио). Наиболее известными контейнерами, использующими RIFF формат, являются:
AVI (видео), WAV (аудио), RMI (MIDI-треки).
Формат RIFF использует такой порядок байтов, при котором младший байт располагается в памяти первым (ittle-endian).
В ячейках 04…07 указывается размер файла в байтах (значение
уменьшено на 8 байт).
В ячейках памяти 08…0В конкретизируется вид мультимедийного
контейнера - звуковой файл формата WAVE. Символы записаны в шестнадцатеричной системе счисления. Эта область отмечена на рисунке цифрой 2.
В следующих трёх ячейках памяти записаны латинские буквы «fmt».
Информация, помещённая в ячейках 00…0ЕН, как бы говорит воспроизводящему устройству: «В данном файле располагается звуковой файл
формата WAV». Далее в заголовке размещаются сведения, которые позволяют уточнить характеристики звукового файла: частота дискретизации,
глубина звука (число бит в семпле), число каналов (моно или стерео) и т.п.
В ячейках 14…15Н указывается есть сжатие файла или нет. Наличие
единицы говорит об отсутствии сжатия (звуковой файл несжатый, порой говорят «сырой»). Это поле данных на рисунке обозначено цифрой 3.
Байты по адресам 16…17Н говорят о том, что данный звуковой файл
монофонический. Единица свидетельствует о том, что используется один канал (см. рисунок, цифра 4). Стереофонический файл маркируется цифрой 2
и т.д.
В ячейках 18Н…19Н (область обозначена на рисунке цифрой 5) указана частота дискретизации, выраженная в герцах. Напомним, что потоковая
технология RIFF использует обратный порядок размещения данных: вначале
идут младшие байты, а затем – старшие. В указанных ячейках размещено
шестнадцатеричное число 1F40H. При переводе в десятичную систему счисления это число даёт значение 8000, то есть 8 кГц.
В ячейках 1СН…1ЕН указывается количество байт, передаваемых за
одну секунду воспроизведения. В рассматриваемом случае здесь указано
шестнадцатеричное число 3Е80Н. Перевод в десятичную СС даёт значение
16000 байт/c. Это значение вполне предсказуемо. Так как частота дискретизации выбрана равной 8 кГц, а каждый отсчёт состоит из двух байт, то это и
даёт указанное значение битрейта (скорости воспроизведения данных).
В ячейках 20Н и 21Н говорится, какое число байт используется для
представления одного семпла. В данном случае каждый семпл представлен
двумя байтами (область обозначена цифрой 6).
Информация в ячейках памяти 22Н и 23Н говорит о том, что для АЦП
преобразования использовано шестнадцати битное кодирование (65535
уровней квантования). Указанная область отмечена на рисунке цифрой 7.
В четырёх ячейках памяти 24Н…27Н содержатся шестнадцатеричные
51
________________________________________________________________________________
коды латинского слова «data» (область отмечена цифрой 8). Эта информация
как бы предупреждает воспроизводящее устройство, что скоро поступят
оцифрованные данные.
В ячейках 28Н…2BH запоминается, какое количество байт содержится в области данных.
Начиная с ячейки 2СН в файле размещаются непосредственно отсчёты (звуковые данные, которые воспроизводятся соответствующим
устройством). Эта область отмечена на рисунке цифрой 9. Под каждый
семпл отводится две ячейки памяти. Первый отсчёт занимает ячейки 2СН и
2DH. В этих ячейках записано число 0074Н. Следующий семпл 002BН занимает ячейки 2E и 2F и т.д.
Именно в области 9 удобно скрытно передавать дополнительную информацию, например, путём изменения значений младших битов (метод
LSB). Очевидно, что при таком сокрытии в каждом семпле размещается
один бит скрываемой информации. Число семплов о оцифрованном сигнале
зависит от выбранной частоты дискретизации и времени звучания файла.
На следующем рисунке показан заголовок звукового файла формата
WAV, Файл сформирован в звуковом редакторе Sound Forge с частотой дискретизации 8 кГц (область 5), каждый семпл занимает одну ячейку памяти
(область 6), при АЦП преобразовании использовано восьми битное кодирование (область 7).
Звуковой редактор Sound Forge формирует файлы со структурой, несколько отличающийся от структуры, описанной выше. Особенностью этих
файлов является то, что в заголовке располагается дополнительная служебная информация с описанием музыкального произведения. Однако место
расположения воспроизводимых данных также отмечено четырьмя символами «data». На следующем рисунке область размещения этих символов отмечена цифрой 8. В ячейках памяти 1FCH…1FFH указано количество байт,
содержащихся в звуковых данных. Как видно из рисунка данные в файле
размещаются, начиная с адреса 200Н.
52
_________________________________________________________________
Предположим, что имеется звуковой файл, дамп которого показан на
рисунке. Файл является монофоническим (ячейки 16Н и 17Н), в нём использовано 16-ти битное кодирование (ячейки 22Н и 23Н), частота дискретизации составила 44,1 кГц (ячейки 18Н…19Н содержат число AC44H). Для записи каждого семпла требуется две ячейки памяти. Об этом свидетельствует
информация, размещённая в ячейках 20Н и 21Н. Требуется в этот файл внедрить (скрыть в данных) латинскую букву S. Десятичный код этой буквы в
соответствии с кодовой таблицей CP-1251 составляет 53, а двоичный
01010011.
Внедрение будет осуществляться методом LSB. В соответствии с методом LSB в каждый семпл внедряется один бит буквы S. Причём внедрение
должно вестись в младший бит семпла. Условимся внедрение вести, начиная
со старшего разряда внедряемого символа (в данном случае, начиная с 0).
Таким образом для сокрытия буквы S придётся использовать 8 семплов, то есть 16 ячеек памяти.
53
________________________________________________________________________________
Область данных начинается с ячейки 2СН. Так как внедрение должно
осуществляться в младшие биты семплов, то сокрытие информации должно
идти в ячейках 2СН, 2ЕН, 30Н, 32Н, 34Н, 36Н, 38Н и 3АН.
В этих ячейках памяти находятся шестнадцатеричные числа соответственно 3А, 2Е, 43, 35, 71, 60, 26 и 2С. Двоичное число 01010011нужно поразрядно записать в эти восемь шестнадцатеричных чисел, путём замены последнего бита.
Первый символ 0 нужно внедрить в число 3А. В двоичной системе
счисления число 3АН выглядит так: 00111010. После замены последнего
бита нулём данное число не изменит свой первоначальный вид.
Следующий бит символа S внедряется в число 2ЕН, в результате чего
оно превращается в число 2FH.
Проведя аналогичные замены получим новую последовательность
шестнадцатеричных чисел: 3А, 2F, 42, 35, 70, 60, 27 и 2D. Полученные числа
нужно разместить по указанным адресам. Как видно из примера, изменить
пришлось пять чисел из восьми. Для трёх значений чисел последние биты
семплов случайно совпали со значениями внедряемых чисел.
Метод LSB не является единственным методом, который определяет
порядок записи информации в WAV-файл. В патенте [11] описан способ
скрытой передачи информации, при котором используются не все отсчёты,
а внедрение информации происходит не только в младшие разряды семплов,
но и в старшие. При этом используемые отсчёты и номера разрядов определяются секретным ключом.
54
_________________________________________________________________
5.3. Модель RGB
По принципам формирования изображения все объекты компьютерной графики можно разделить на три вида: растровые, векторные и фрактальные.
Растровые изображения строятся с помощью маленьких, равных по
величине квадратиков (точек, пикселей). Хорошей метафорой для объяснения принципа формирования растрового изображения может служить вышивка «крестиком». Растровую графику можно представлять себе также как
мозаику или витраж. Растровое изображение хранится в памяти в виде двоичных чисел, которые указывают координаты и цвет отображаемых точек.
На векторных картинках форма изображаемой линии определяется
начальными точками и формулой, описывающей эту линию. Этот вид графики можно сравнить с вышивкой «гладью». Однако лучше представлять
векторную графику, как изображение, образованное из фрагментов разноцветных графиков различных математических функций. Сложное векторное
изображение состоит из нескольких объектов (узлы, линии, четырёхугольники, многоугольники, фигуры). Объекты могут размещаться в разных
слоях, накладываться друг на друга.
Векторное изображение хранится в памяти ЭВМ в виде чисел, которые характеризуют координаты опорных точек, форму, толщину и цвет линий.
Фрактальное изображение формируется из одинаковых (подобных)
частей (элементов).
Термин «фрактал» произошёл от латинского слова fractus, которое в
переводе означает дроблёный. Фрактал — это математическое множество,
обладающее свойством самоподобия. Простейшим фрактальным элементом
является треугольник. Достоинством фрактальной картинки является малый
размер файла, а недостатком — ограниченный набор изображаемых объектов. С помощью фракталов могут быть реалистично изображены: облака, деревья, водоросли, кораллы, морские раковины, снежинки, морозные узоры
на окне, кровеносная система и др.
Фрактальное изображение хранится в памяти ЭВМ в виде системы
уравнений.
Заметим, что все виды графики (растровая, векторная, фрактальная)
технически отображаются разноцветными точками на матричном дисплее.
Дадим более подробную характеристику каждому виду графики.
Растровая графика (РГ) получается в результате съёмки с помощью
цифрового фотоаппарата, цифровой видеокамеры или сканирования фотографий, иллюстраций. Растровый рисунок можно создать вручную с помощью растрового графического редактора.
55
________________________________________________________________________________
Основным элементом РГ является точка (её положение в матрице, яркость, цвет). Матричная структура изображений формируется в момент создания растрового изображения. Фотоаппараты, видеокамеры, сканеры содержат электронные светочувствительные матрицы,
которые преобразуют исходную картину в дискретное (точечное) изображение.
Растровое изображение формируется из множества отдельных точек (пикселей), расположенных на
пересечении столбцов и строк. Рисунок с изображением буквы «Ж» иллюстрирует принцип формирования изображения с помощью растровой графики.
Термину «растровая графика» в английском
языке соответствует термин «Bitmap — графика». В переводе это означает
графику, основанную на карте (плане) расположения битов в таблице. Приведённый рисунок с изображением буквы подтверждает справедливость
такого названия.
Формирование цветовых оттенков цветного изображения происходит
путём слияния (сложения, смешивания) трёх основных цветов в разных пропорциях. Основными цветами являются: красный (англ. Rot), зелёный
(Green) и синий (Blue). Аддитивная модель смешения основных цветов обозначается аббревиатурой RGB. Она основана на психофизических свойствах
человеческого зрения.
Максимальные значения интенсивности трёх основных цветов в модели RGB приводят к формированию белого цвета. Малые значения цветовых составляющих формируют чёрный цвет или темно-серые оттенки. Смешивая основные цвета в различных пропорциях можно получить любой цветовой оттенок. Например, слияние красного и зелёного цветов даст жёлтый
цвет. Отображение цветных картин происходит на дисплеях, конструкция
которых позволяет смешивать практически в одной точке основные цвета
разной интенсивности. При типографической печати цветных изображений
используется цветоразностная (субтрактивная) модель CMYK. Модель
CMYK использует голубой, пурпурный, жёлтый и чёрный цвета.
Наглядное представление о цветовой модели RGB можно получить,
56
_________________________________________________________________
рассматривая содержимое памяти, в которой хранится какой–либо рисунок.
Пусть это будет изображение чёрного прямоугольника (10х4 пикселя), на
котором нарисована серая точка. Для формирования серого цвета выберем
следующие цветовые составляющие: красный 128 десятичных единиц, зелёный – 129, синий – 130. Указанные составляющие выбраны отличающимися
друг от друга, что позволяет их различать в памяти
ЭВМ.
Дамп памяти, который содержит рисунок, получим с помощью редактора памяти HEdit32. Из рисунка видно, что цветовые составляющие размещаются по адресам: 65, 66 и 67. В этих ячейках памяти размещены шестнадцатеричные числа 82, 81 и 80. Цвета расположены в памяти в таком порядке:
синий (адрес 65), зелёный (адрес 66), красный (адрес 67). Перевод составляющих из шестнадцатеричной системы счисления в десятичную СС даёт такие значения: 130, 129, 128. В остальных ячейках содержатся нули (так как
прямоугольник чёрный), за исключением служебной информации, указанной в младших адресах. Например, по адресу 12Н указана ширина рисунка,
измеренная в пикселях (шестнадцатеричное число 0АН говорит о том, что
число пикселей равно 10). В ячейке 16Н указана высота рисунка (4 пикселя).
Качество растрового изображения характеризует разрешающая способность (разрешение), которая измеряется числом точек на единицу
длины, например, на дюйм (dots per inch — dpi). Полиграфическое качество
печати требует разрешения порядка 250 dpi.
Фотоснимок размером 10  12 см при полиграфическом разрешении
250 dpi будет содержать примерно 1000  1200 пикселей. Если для кодирования цвета каждого пикселя использовать 24 бита (это даёт более 16 миллионов цветовых оттенков), то для хранения всей информации о такой небольшой фотографии потребуется более 3,4 Мбайт. Приведённое число говорит о том, что для запоминания растрового изображения требуется значительный объем памяти.
57
________________________________________________________________________________
5.4.
Формат графического файла BMP
Существует большое число способов скрытой передачи информации
в графических файлах. Рассмотрим возможность использования для этого
особенности формата BMP. Дамп памяти для рисунка размером 5х3 пикселя
показан ниже.
В рассматриваемом типе графического файла использована модель
RGB. Согласно этой модели, любой пиксель изображения описывается
тремя байтами (по одному байту на каждую цветовую составляющую).
Два байта 42H и 4DH, представленные в шестнадцатеричной системе
счисления, указывают на то, что формат данного файла BMP. В соответствии с кодовой таблицей CP-1251 эти числа после декодирования дают латинские буквы BM (то есть, графический формат Bit Map).
Шестнадцатеричное число 66Н, расположенное по адресу 02Н, говорит
о том, что размер данного файла равен 102 байта. Это значение получено
путём перевода шестнадцатеричного числа 66Н в десятичную систему счисления. Число 36Н, записанное по адресу 0AH, указывает, с какого адреса
начинается запись картинки (это смещение от начала файла, длина заголовка). По адресу 12H указана ширина рисунка, выраженная в пикселях. В
данном случае число пикселей равно 5. Высота рисунка указывается в
ячейке 16Н (для рассматриваемого рисунка высота - 3 пикселя). В ячейке
1AH указано число плоскостей. По адресу 1СН указана глубина цвета. В
данном случае число 18Н говорит о том, что для формирования цветовых
оттенков этого рисунка используется 24 бита (по 8 бит на каждую цветовую
58
_________________________________________________________________
составляющую). В ячейке 22Н указывается объем памяти (в байтах), необходимый для запоминания битовой карты
(объем рисунка без служебной информации).
Изображённый выше дамп памяти
описывает рисунок, показанный слева.
Рисунок состоит из 15-ти пикселей
(прямоугольник 5х3). Из них одиннадцать пикселей - белые, пиксель в левом верхнем углу прямоугольника - чёрный (1), в левом нижнем углу - красный (2), в правом нижнем – зелёный (3) и в верхнем правом – синий (4).
Запись битовой карты в память начинается с левого нижнего угла рисунка, ведётся построчно слева – направо, снизу - вверх. Красный пиксель
(2) описывается составляющими R=255, G=0, B=0. Запись информации в памяти (при увеличении адреса ячейки) ведётся в обратном порядке B-G-R
(синий – зелёный – красный). Таким образом, в самую первую ячейку битовой карты (адрес 36Н) заносится синяя составляющая B=00. В ячейку 37Н
записывается зелёная составляющая красного пикселя G=00, а в ячейку 38Н
красная составляющая R=FF (см. следующий рисунок). На рисунке составляющие красного пикселя обозначены цифрой 2.
Следующие три пикселя в нижней строке рисунка - белые. Поэтому
очередные девять байт имеют максимальное значение FFH (255D). В ячейках 42Н, 43Н и 44Н размещаются три байта зелёного пикселя (цифра 3).
В ячейке 45Н размещён байт 00 – это дополнение, предназначенное для
выравнивания строк дампа памяти. Содержимое этой ячейки избыточно, оно
не несёт никакой полезной информации. Однако содержимое этой ячейки
передаётся в файле вместе с рисунком.
59
________________________________________________________________________________
Следующие пять пикселей рисунка (вторая строка) – белые. Эти пиксели описываются с помощью пятнадцати байт FFH, которые размещены в
ячейках памяти 46Н…54Н. В ячейке памяти 55Н помещается выравнивающий байт 00.
В ячейках 56Н, 57Н и 58Н размещаются байты 00 – это цветовые компоненты чёрного пикселя. Далее на рисунке размещены 3 белых пикселя
верхней строки. Им соответствуют девять байт FFH.
В ячейках 62Н, 63Н и 64Н размещаются цветовые составляющие синего пикселя. Ячейка 65Н используется для выравнивания. Три дополнительных байта обозначены цифрой 5.
Дополнительные ячейки появляются в тех случаях, когда число пикселей в строке рисунка не кратно четырём. Именно дополнительные байты в
графическом файле, предназначенные для выравнивания строк, могут быть
использованы для скрытой передачи информации в графическом файле с помощью метода форматной стеганографии.
Рассмотрим несколько примеров анализа дампов памяти для картинок
разного размера и разного содержания. При внедрении информации с помощью метода LSB можно использовать любые ячейки памяти (в том числе и
предназначенные для выравнивания строк).
Ниже показан рисунок размером 4х3 пикселя, который содержит белые и цветные пиксели.
На следующем рисунке показан дамп памяти для указанного рисунка.
В таблице выделены области памяти, в которых содержится описание цветовых составляющих пикселей.
Заголовок файла занимает в памяти 54 байта (ячейки с адреса 00Н до
36Н). Сам рисунок занимает 36 байт (информация о размере рисунка содержится в ячейке 22Н). Файл занимает 90 байт (см. ячейку 02Н, где содержится
шестнадцатеричное число 5АН).
60
_________________________________________________________________
Проверим указанные данные с помощью простейших вычислений.
Рисунок содержит 12 пикселей с глубиной цвета 24 бита. Перемножение
этих чисел и перевод результата в байты даёт число 36, и оно совпадает с
числом, указанным в заголовке. Суммирование объёма заголовка и объёма
рисунка даёт значение 90 байт, что также совпадает с числом, указанным в
заголовке.
Рассмотрим рисунок 8х3 пикселей, содержащий жёлтый, красный и
синий пиксели, расположенные на белом фоне.
Из заголовка видно, что рисунок содержит 8 столбцов и 3 строки
(ячейки 12Н и 16Н).
В ячейке 22Н указан объём памяти (в байтах), необходимый для сохранения рисунка (без служебной информации). Перевод шестнадцатеричного числа 48Н в десятичную СС даёт десятичное число 72 байта.
Выполним элементарную проверку указанной информации. Рисунок
содержит 8 х 3 = 24 пикселей. Для описания одного пикселя требуется 24
бит, а для описания всех пикселей рисунка необходимо 576 бит (или 72
байта). Результаты расчёта совпали с данными в заголовке файла.
Объём файла указан в ячейке 02Н. По этому адресу сохранено десятичное число 126. Суммирование объёма рисунка с объёмом заголовка даёт
такое же число: 72 + 54 = 126. Объём заголовка определяется путём непосредственного подсчёта числа занимаемых ячеек, либо эту информацию
можно считать в ячейке 0АН.
Ниже показан рисунок размером 3х3 пикселя, который содержит белые и цветные пиксели.
61
________________________________________________________________________________
На изображении дампа памяти выделены области, где записана информация о цветных пикселях.
Заголовок занимает в памяти 54 байта, а непосредственно рисунок 36
байт. Весь файл занимает 90 байт.
Описание красного пикселя содержится в ячейках 36Н, 37Н и 38Н
(цветовые составляющие с увеличением адреса располагаются в таком порядке: синий – зелёный – красный). Описание зелёного пикселя находится в
ячейках 3СН, 3DH и 3EH. Информация о цветовых составляющих синего
пикселя приведены в ячейках 54Н, 55Н, 56Н.
Рисунок содержит 9 пикселей и для его описания требуется 27 байт.
Однако по адресу 22Н указано десятичное число 36 (на 9 байт больше). Это
говорит о том, что в файле имеется девять ячеек памяти, в которых не переносится никакая информация и их содержимое не отображается на экране
монитора. Эти ячейки на предыдущем рисунке закрашены серым цветом.
Очевидно, что указанные ячейки памяти могут быть использованы для скрытой передачи дополнительной информации внутри этого рисунка с помощью
метода форматной стеганографии. При этом потребительские свойства рисунка не изменятся, он будет занимать прежний объём памяти, а само изображение не изменится.
Внедрим в этот контейнер слово «Аллегория» методом форматной
стеганографии. В шестнадцатеричной системе счисления это слово будет
выглядеть так:
C0 EB EB E5 E3 EE F0 E8 FF.
Внедрение слова выполним в соответствии со следующей таблицей:
Адрес
Байты
3F
C0
40
EB
41
EB
4B
E5
4C
E3
4D
EE
57
F0
58
E8
59
FF
В результате внедрения информации дамп памяти будет выглядеть
62
_________________________________________________________________
так.
Закономерность появления дополнительных байтов в графическом
файле формата BMP иллюстрируется с помощью следующей таблицы.
Число пикселей
в строке (ширина рисунка)
4
5
6
7
8
9
Число байт, необходимых для
описания
строки
12
15
18
21
24
27
Ближайшее неменьшее целое
число, кратное
4
12
16
20
24
24
28
Число выравнивающих байтов
0
1
2
3
0
1
Таблицу следует трактовать следующим образом.
Если ширина рисунка, выраженная в пикселях, кратна четырём
(например, 4, 8, 12), то в файле не будет дополнительных (выравнивающих)
байтов. Если ширина рисунка, например, пять пикселей, то сначала располагаются 15 байтов строки, а затем один выравнивающий байт, так как ближайшее большее целое число, кратное четырём, равно 16. Если ширина рисунка 6 пикселей, то потребуется 18 ячеек для их размещения и две выравнивающие ячейки. Объясняется это тем, что ближайшее число, кратное четырём, это 20.
Самое большое возможное число дополнительных байтов для каждой
строки рисунка 3 будет, если ширина рисунка равна 7 +4n пикселям, где n =
0, 1, 2, 3 и т.д. (натуральные числа, начиная с нуля).
С увеличением ширины рисунка на один пиксель число дополнительных байтов для каждой строки будет циклически изменяться по закону: 0-12-3-0-1-2-3….
Рассмотренная закономерность хорошо прослеживается на белом
прямоугольнике шириной 6 пикселей, а высотой 2. Четыре дополнительных
байта заполнены нулями.
63
________________________________________________________________________________
Рассмотрим пример внедрения информации в цветовые составляющие графического файла формата BMP с помощью метода LSB. Заметим,
что при внедрении информации в 24-х битный рисунок формата BMP методом LSB можно внедрить 3 бита на каждый пиксель изображения.
Предположим, что требуется скрыть латинскую букву N (двоичный
код 01001110). Внедрение будем производить, начиная с младшего разряда.
После замены последних бит дамп памяти этого файла будет выглядеть так:
64
_________________________________________________________________
6. Моделирование работы РЭУ
Рассмотрим основные понятия, которые используются при моделировании радиоэлектронных устройств (РЭУ).
Модель — материальный объект либо образ, которые упрощённо
отображают самые существенные свойства объекта исследования. Под образом понимаются: формула, изображение, словесное описание, схема, граф,
чертёж, план, карта, блок-схема алгоритма, ноты и т.п.
Моделирование — метод научного исследования явлений, процессов, объектов, устройств или систем (обобщённо – объектов исследований), основанный на построении и изучении свойств моделей с целью получения новых знаний, совершенствования характеристик объектов исследований или управления ими.
Любая модель всегда отличается от реального объекта и отображает
лишь часть его самых существенных черт, основные элементы и связи. По
этой причине для одного объекта исследования существует множество различных моделей. Вид модели зависит от выбранной цели моделирования и
мастерства исследователя. Если попросить философа, биолога, психолога,
физика и скульптора создать модель человека, то результаты будут различны
[5].
Исторически первыми моделями, которые замещали реальные объекты, вероятно, были языковые знаки. Они возникли в ходе развития человечества и постепенно превратились в разговорный язык.
Возможно, что первыми моделями на нашей планете были жесты
наших предков. Однако документальных подтверждений этому факту нет.
Первые документально зарегистрированные наскальные рисунки
(петроглифы) были графическими моделями, которые изображали картины
быта, животных и эпизоды охоты. Возраст этих рисунков оценивается величиной 200 тысяч лет.
Следующим этапом развития моделирования можно считать возникновение числовых знаков. Сведения о результатах счета первоначально сохранялись в виде зарубок. Постепенное совершенствование этого метода
привело к возникновению цифр как системы знаков. Можно предположить,
что именно зарубки были прототипом римских цифр.
Потребность в создании и использовании моделей связана с тем, что
экспериментально исследовать многие реальные явления и объекты сложно
или дорого, а порой вовсе невозможно. Например, безумно экспериментально изучать, к чему приведёт мировая термоядерная война. Опасны эксперименты с реальными реакторами на атомных электростанциях. Неразумны опыты с радиоаппаратурой при предельных значениях напряжения
питания и окружающей температуры.
При изучении сложных явлений, процессов, объектов не удаётся
65
________________________________________________________________________________
учесть полную совокупность всех элементов и связей. По этой причине модель всегда проще исследуемого объекта.
При создании модели нет необходимости учитывать все элементы и
связи, существующие в объекте исследования. Нужно лишь выделить наиболее характерные составляющие, которые с достаточной степенью определяют
основные свойства объекта исследования. В результате объект исследования
заменяется некоторым упрощённым подобием, но обладающим главными
свойствами, аналогичными свойствам объекта исследования.
Появившийся вследствие проведённой подмены новый объект (или
абстракция) принято называть моделью объекта исследования.
Системы моделирования радиоэлектронных устройств (РЭУ) позволяют резко уменьшить объем экспериментальных исследований, для проведения которых требуется приобретение дорогостоящих измерительных приборов, радиодеталей, трудоёмкая сборка и длительная настройка макетов.
Применение программ моделирования РЭУ позволяет всесторонне
исследовать разрабатываемые устройства в различных режимах работы
(например, в предельно допустимых режимах), что сложно выполнить экспериментальными методами. Результаты макетирования дают ограниченный объем информации о характеристиках разрабатываемой аппаратуры.
Экспериментальные исследования отражают характеристики лишь конкретных единичных макетов. Они не позволяют оценить влияние статистического разброса параметров полупроводниковых и других элементов РЭУ, и
поэтому трудно делать обобщающие выводы по результатам макетирования.
Экспериментально сложно определить, какие последствия вызовет наихудшее сочетание параметров радиоэлементов, и что произойдёт при отказе отдельных радиоэлементов. Опытным путём не просто исследовать влияние
дестабилизирующих факторов, например, внешней температуры. Перечисленные проблемы, возникающие при экспериментальных исследованиях,
легко преодолеваются путём моделирования работы РЭУ.
Моделирование широко используется при проведении научно-исследовательских и опытно-конструкторских работ.
Одной из первых удачных программ моделирования РЭУ была программа схемотехнического моделирования SPICE (Simulation Program with
Integrated Circuit Emphasis), разработанная в начале 70-х годов ХХ столетия
в Калифорнийском университете для больших ЭВМ, а в конце 80-х годов эта
программа была адаптирована (приспособлена) для ПЭВМ и получила
название PSpice. Эта программа оказала сильное влияние на последующие
подобные разработки.
Наиболее легка в освоении программа Electronics Workbench (фирма
Interactive Image Technologies). Она построена интуитивно понятно, и работа
с этой программой напоминает экспериментальную деятельность радиоинженера. В программе имеются виртуальные приборы (вольтметры, ампер-
66
_________________________________________________________________
метры, генераторы, осциллограф, измеритель амплитудно-частотной характеристики и т. п.).
В версию MultiSIM & Electronics Workbench добавлены измеритель
мощности, анализатор спектра и анализатор сети. Программа имеет большую библиотеку аналоговых и цифровых радиодеталей. В библиотеке содержатся сведения о транзисторах, диодах, резисторах, конденсаторах, триггерах, счётчиках, индикаторах и т. п.
Испытуемая схема «монтируется» на виртуальном столе, и затем делаются необходимые измерения. При этом настройка виртуальных измерительных приборов осуществляется практически так же, как и настройка реальных приборов. Создаётся полная иллюзия работы с конкретными действующими конструкциями.
Программа допускает возможность вносить изменения в схему прямо
в процессе моделирования (например, с помощью переменных резисторов
или коммутируемых клавишами переключателей). Это существенно повышает наглядность моделирования. Изменение параметров измерительных
приборов (например, осциллографа) даёт возможность исследовать сигналы
в разных масштабах непосредственно в процессе моделирования. Это
наиболее существенное отличие данной системы (другие работают в пакетном режиме моделирования и не допускают изменения параметров устройства в процессе его моделирования).
«Собранную» схему легко редактировать. Элементы перемещаются
на «резиновых нитях», т. е. провода при перемещении не обрываются, а изменяют свою конфигурацию.
67
________________________________________________________________________________
6.1. Моделирование работы аддитивной криптосистемы
Выполнить моделирование криптосистемы, которая имитирует работу шифра гаммирования, позволяет схема, показанная на рисунке (приложение Multisim 11.0.2).
Устройство содержит два четырёхразрядных арифметико-логических
устройства (АЛУ U1 и АЛУ U2), генератор слов (Word Generator) и четыре
индикатора для отображения значений открытого текста, гаммы, криптограммы и принятого текста.
АЛУ U1 имитирует работу передающей стороны (работу шифратора),
АЛУ U2 – работу приёмной стороны (дешифратора). Гамма одновременно
подаётся на передающую и приёмную сторону (входы B0…B3 АЛУ). Открытый текст подаётся на входы A0…A3 АЛУ U1, а криптограмма - на
входы A0…A3 АЛУ U2.
С помощью управляющих сигналов:
S0  0, S1  1, S2  1, S3  0, M  1
оба АЛУ жёстко устанавливаются в режим выполнения логической операции Исключающее ИЛИ.
Числа открытого текста и гаммы формируются с помощью Генератора слов (Word Generator XWG1). Настройки Генератора слов, показанные
на следующем рисунке, позволяют моделировать работу криптосистемы с
68
_________________________________________________________________
пятью значениями гаммы и открытого текста (2С, 30, BD, 67, 00). Изменяется объём буфера (число машинных слов) с помощью списка Buffer size,
который находится в диалоговом окне Settings.
Моделирование криптосистемы ведётся в пошаговом режиме (за счёт
многократных щелчков по кнопке Step…).
Содержимое Генератора слов (Word Generator XWG1), показанное на
первом рисунке, соответствует открытому тексту CН и значению гаммы 2Н.
Очевидно, что поразрядное сложение по правилу Исключающее ИЛИ двоичных чисел 1100В = СН и 0010В = 2Н даст значение 1110В. В шестнадцатеричной системе счисления результат даёт значение ЕН. На индикаторах
просматриваются именно эти значения открытого текста, гаммы и криптограммы. На приёмной стороне получено такое же число, как и отправленное
с передающей стороны.
69
________________________________________________________________________________
6.2. Моделирование работы шифратора с управляемыми
операциями
Имитация работы передающей и приёмной сторон криптосистемы
осуществляется с помощью двух арифметико-логических устройств. Четыре
разряда открытого текста M подаётся на вход А первого арифметико-логического устройства (АЛУ). Четырёхбитная гамма G подаётся на входы В
каждого АЛУ. Вид выполняемой операции на передающей стороне задаётся
с помощью преобразователя кода ПК1. Управляющие сигналы S на приёмной стороне формируются с помощью преобразователя кода ПК2. Сигналы
с выходов преобразователей кодов подаются на управляющие шины АЛУ и
шину входного переноса CN. Именно эти сигналы определяют вид выполняемых АЛУ операций.
Криптограмма K формируется на выходе F первого АЛУ. Расшифрование криптограммы происходит на приёмной стороне с помощью второго
АЛУ. Выполняемые операции синхронно изменяются под управлением
гаммы. Принятый открытый текст M` появляется на выходе F второго АЛУ.
В качестве шифрующих преобразований можно использовать различные логические и арифметические операции, а также математические функции и их комбинации [9]. Некоторые из них перечислены в таблице 6.2.1, в
которой приняты такие обозначения:
M - открытый текст (сообщение); G - гамма; K - криптограмма;  логическая операция Исключающее ИЛИ (неравнозначность);  - логическая операция равнозначность; «+» - арифметическая операция сложение;
«– » - арифметическая операция вычитание; черта над переменными обозначает операцию инверсии.
70
_________________________________________________________________
Первые 10 операций в таблице 6.2.1 предполагают работу ЭВМ с целыми числами. Остальные операции предназначены для работы с вещественными числами.
Таблица 6.2.1
Операции
Операции
на передающей стороне
на приёмной стороне
1.
Неравнозначность
Неравнозначность
K  M G
2.
Равнозначность
K  M G  M  G
3.
4.
5.
Сложение
M ` K  G
Равнозначность
M ` K  G  K  G
Вычитание
K  M G
M ` K  G
Вычитание
Сложение
K  M G
Вычитание
M ` K  G
Вычитание
K GM
M ` G  K
Инверсия от суммы
Комбинированная разность
K  M G
M ` K  G
7.
Инверсия от разности
Комбинированная сумма
K  M G
M ` K  G
8.
Инверсия от разности
Комбинированная разность
K GM
M ` G  K
Комбинированная сумма
Комбинированная разность
6.
9.
10.
11.
12.
13.
14.
15.
K  M G
M ` K  G
Комбинированная разность
Комбинированная сумма
K  M G
M ` K  G
Умножение
Деление
K  M G
M  K /G
Деление
Умножение
Деление
Деление
K  M /G
M  K G
K G/M
M G/K
Функциональные
Функциональные
K  f (M , G)
M f
1
( K , G)
Алгебраические
Алгебраические
K  M nG s
M  n K  Gs
71
________________________________________________________________________________
Задачей преобразователей кодов ПК1 и ПК2 является синхронное изменение управляющих сигналов на передающей и приёмной сторонах. Естественно, что конструкции преобразователей кодов ПК1 и ПК2 должны быть
разными, так как при одинаковых входных воздействиях (гамма G) преобразователи кодов должны формировать разные выходные (управляющие) сигналы S, S` и сигналы переносов CN.
Преобразователи кодов можно синтезировать различными способами: графически (с помощью карт Карно и диаграмм Вейча), аналитически
(методы Квайна, Мак-Класки, неопределённых коэффициентов) и с помощью графических символов, интерпретирующих булевы функции.
Перечисленные способы синтеза комбинационных цифровых
устройств трудоёмки и имеют ограничения на их использование при числе
переменных более 5…6. При разработке модели данной криптосистемы преобразователи кодов целесообразно синтезировать с помощью блока Logic
Converter (логический конвертор), который входит в систему моделирования
радиоэлектронных устройств Multisim.
Логический конвертор позволяет создавать преобразователи кодов с
числом аргументов n ≤ 8. Для получения логических выражений, описывающих работу ПК, достаточно в конвертор ввести таблицу истинности, которая
описывает работу преобразователя кода. Полученные математические выражения затем можно использовать для построения принципиальной схемы
ПК.
Рассмотрим подробнее порядок выбора логических и арифметических операций, которые можно использовать в криптосистеме.
Безусловно, для шифрования нужно использовать многократно проверенную на практике операцию Исключающее ИЛИ. Аналогичными положительными свойствами обладает операция “Равнозначность”, которая является инверсной по отношению к операции Исключающее ИЛИ.
В виду того, что логические операции M  G  M  G эквивалентны операции неравнозначности M  G , использовать все три операции
при шифровании не имеет смысла, так как криптограммы при шифровании
будут одинаковыми. Аналогично операции M  G  M  G сводятся к
операции равнозначности M  G . Таким образом, из рассмотренных шести
операций следует использовать только две: равнозначность и неравнозначность.
Для арифметических операций в дополнительном коде справедливы
соотношения:
M G  G  M  M G
M G  G M  M G
G  M  M G  M G
72
_________________________________________________________________
G  M  M G  M G
M G  G  M
Использование операций, перечисленных в одной строке, даст одинаковые значения криптограммы при одинаковых значениях гаммы и открытого текста. Из четырнадцати указанных операций целесообразно оставить
только шесть, например,
M  G , M  G , M  G , M  G, M  G и G  M .
Криптосистема должна работать с использованием четырёх операций:
Исключающее ИЛИ, равнозначность, сложение и вычитание (текст минус
гамма). Эти операции должны сменять друг друга в зависимости от значений
гаммы. Для реализации этого при составлении принципиальной схемы криптосистемы следует использовать разработанные преобразователи кода.
Именно преобразователи кодов выполняют управление работой АЛУ (изменение шифрующих и дешифрующих операций).
Открытый текст, гамма, криптограмма в криптосистеме с управляемыми операциями представлены четырёхразрядными двоичными операндами (тетрадами), а управляющие сигналы формируются с помощью пяти
двоичных разрядов. Ещё один разряд потребуется для формирования сигнала переноса. Таким образом, преобразователь кода должен содержать четыре входа (на них подаётся гамма) и шесть выходов.
Рассмотрим пример синтеза преобразователя кода на передающей
стороне. Исходные данные приведены в таблице 6.2.2.
Таблица 6.2.2
№
п/п
Гамма
Управляющие
B3B2B1B0
Операция
сигналы
Мod
CN
(ABCD)
S3S2S1S0
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
M G
M G
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
x
1
x
73
________________________________________________________________________________
8
9
10
11
12
13
14
15
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
M G
M G
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
1
В колонке «Гамма» одновременно указаны разряды АЛУ (B3B2B1B0),
на которые подаётся гамма, и обозначения этих же разрядов в конверторе
Logic Converter (ABCD).
Дадим комментарии к предыдущей таблице.
В колонке «Операция» указываются математические и логические
операции, которые должно выполнять АЛУ при значениях гаммы, указанных в столбце «Гамма».
Так для значений гаммы, равной значениям «0», «1», «2», «3», должна
выполнятся операция M  G , поэтому в строках 0-3 четырежды указана
данная операция. Другие строки таблицы заполняются аналогично
Колонка «Управляющие сигналы» заполняется с учётом информации,
содержащейся в колонке «Операция». Соответствие управляющих сигналов
S3S2S1S0 и выполняемых АЛУ операций следующее:
 G » – «0 1 1 0», « M  G » – «1 0 0 1»,
« M  G » – «0 1 1 0», « M  G » – «1 0 0 1»
«M
Входы S3S2S1S0 и Mod предназначены для формирования управляющих сигналов, которые позволяют выбрать одну из тридцати двух возможных операций АЛУ.
Столбец «Mod» определяет, какую операцию выполняет АЛУ: логическую (значение равно 1) или арифметическую (значение равно 0). Сигнал
CN определяет величину переноса. Для логических операций безразлично,
какое значение принимает CN, поэтому сигнал обозначен символом «Х». Для
арифметического вычитания сигнал CN равен «0», а для арифметического
сложения – «1».
На основании данных из таблицы 6.2.2 следует сформировать логические выражения, которые будут использованы для синтеза преобразователя
кода. Составить логические выражения проще всего с помощью Logic
Converter (логический конвертор).
74
_________________________________________________________________
XLC1
AB
Для получения математических выражений, описывающих работу
ПК, достаточно в конвертор ввести данные из таблицы истинности преобразователя кода. В качестве примера получим выражение для S3 (табл. 6.2.2).
Логические выражения формируются при нажатии кнопки SIMP, находящейся в поле Conversions.
Как видно из приведённого рисунка, вся введённая в конвертор таблица истинности описывается одним символом В. Анализируя таблицу 6.2.2,
несложно заметить, что сигналы на шинах S3 и S0 должны совпадать, поэтому
эти два входа АЛУ должны быть соединены между собой.
Учитывая последовательность ввода операндов и принятые обозначения (см. табл. 6.2.2), можно записать: S3 = S0 = B2.
Фрагмент схемы ПК, который реализует полученное выражение показан на рисунке.
75
________________________________________________________________________________
Напомним, что символ А в окне Logic Converter соответствует разряду
гаммы В3, символ В – В2, С – В1, D – В0.
Описанные действия по определению сигнала на одном выходе ПК
следует повторить для всех выходов ПК. В результате должно быть получено шесть логических выражений, часть из которых могут быть одинаковыми.
Например, анализируя таблицу 6.2.2, легко заметить, что сигналы
S 2  S1 . Это означает, что эти шины должны быть соединены между собой.
Ниже приведены результаты формирования логических выражений
для остальных четырёх выходных сигналов первого ПК:
S 2  S1  B 2 , M  B 3 , C N  B2 .
Эти выражения следует использовать для построения схемы преобразователя кода на передаче. Вся схема будет состоять из двух инверторов для
сигналов В1 и В3. Ещё один выходной сигнал ПК берётся непосредственно с
шины В2. На рисунке показана шифрующая часть криптосистемы (передающая часть).
76
_________________________________________________________________
Затем следует выполнить синтез ПК на приёмной стороне. Для этого,
используя данные таблицы 6.2.2, нужно составить новую таблицу истинности. Следует помнить, что логические операции на приёме и передаче
должны синхронно совпадать, а арифметические операции на приёме
должны поменяться на противоположные, то есть, если на передаче использовалось арифметическое сложение, то на приёме нужно использовать арифметическое вычитание, и наоборот. В итоге таблица истинности примет следующий вид:
Таблица 6.2.3
№
п/п
Гамма
Управляющие
B3B2B1B0
Операция
сигналы
Мod
CN
(ABCD)
S3S2S1S0
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
M G
M G
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
x
1
x
77
________________________________________________________________________________
8
9
10
11
12
13
14
15
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
M G
M G
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
0
0
Используя логический конвертор и данные из таблицы, несложно получить выражения, которые описывают ПК на приёмной стороне:
S3  S0  ( B 3  B2 )  ( B3  B 2 ) ,
S2  S1  ( B3  B2 )  ( B3  B2 ) ,
M  B 3 , CN  B 2 .
На основе этих выражений формируется схема ПК на приёмной стороне. Следующий рисунок показывает схему второго ПК.
Полная принципиальная схема криптосистемы имеет вид:
78
_________________________________________________________________
Четырёхбитный открытый текст подаётся на вход А первого арифметико-логического устройства (U1). Гамма подаётся на вход В. Вид выполняемой операции задаётся с помощью преобразователя кода (U3, U4). Криптограмма формируется на выходе F первого АЛУ (U1). Дешифрация криптограммы осуществляться на приёмной стороне с помощью второго АЛУ (U2).
Вид выполняемой операции синхронно изменяется под управлением гаммы.
Принятый открытый текст появлялся на выходе F второго АЛУ (U2).
Исходный текст, принятый текст, гамма и криптограмма отображаются с помощью четырёх индикаторов соответственно U15, U13, U16, U14.
Значения гаммы и передаваемый текст формируются с помощью генератора
слов XWG1 (Word Generator). На рисунке показан генератор слов, в буфере
которого содержатся некоторые значения открытого текста и гаммы.
79
________________________________________________________________________________
Как видно из рисунка, выполняется 6-я по счету операция. В соответствии с таблицей 6.2.2 в этот момент времени выполняется шифрующая операция «Равнозначность». Операция выполняется над числами 5 и 7 и результат равен шестнадцатеричному числу D. На приёмной стороне число подвергается расшифрованию и в результате получается число 7 (открытый
текст). Именно эти числа показаны на принципиальной схеме криптосистемы.
На последнем этапе выполнения моделирования следует проверить
правильность работы созданной криптосистемы. Для этого в окне свойств
генератора слов XWG1 нужно выставить заданные значения гаммы и открытого текста, как показано на рисунке, и нажатием на клавишу Step, проверить все операции. Для удобства флажок таблицы исчисления должен стоять
на отметке Hex.
В рассмотренном примере синтеза криптосистемы принципиальные
схемы преобразователей кодов достаточно просты. При существенном
усложнении конструкции возникает проблема из-за высокой плотности размещения микросхем на отведённой площади листа. Увеличить пространство
рабочего стола можно с помощью диалогового окна, показанного на следующем рисунке. Вызывается диалоговое окно с помощью контекстного меню
и выбора опции Properties (Свойства).
Как и всякая имитация, рассмотренная модель не полностью соответствует реальной криптографической системе. Например, при моделирова-
80
_________________________________________________________________
нии предполагается, что соединение между передающей и приёмной сторонами происходит по четырём проводам. В реальной криптосистеме связь
должна осуществляться по двухпроводной линии.
Кроме того, при моделировании считается, что операнды, циркулирующие в криптосистеме, являются четырёхразрядными целыми числами.
Диапазоны изменения чисел составляли 0  M  15 и 0  G  15 . Заметим,
что в реальной криптосистеме при формировании криптограммы возможно
использование не только целых, но и вещественных чисел.
6.3.
Моделирование работы устройства деления
С помощью моделирования процесса деления одного полинома на
другой можно проверить правильность выполнения ручных расчётов, сделанных при формировании кода БЧХ. При этом делимое вводится в устройство, а конфигурация самого устройства формируется в соответствии с видом делителя. Другими словами, структура схемы зависит от вида порождающего полинома.
На следующем рисунке показана схема, предназначенная для деления
двоичных чисел на порождающий полином g ( x )  x 3  x 2  1 . Напомним,
что в результате такого деления формируются контрольные биты кода БЧХ.
Схема состоит из трёх D-триггеров. Число триггеров в схемах деления
соответствует максимальной степени порождающего полинома. Кроме Dтриггеров в схеме используется две двухвходовые схемы Исключающее
ИЛИ. Входы схем Исключающее ИЛИ подключают к выходам тех триггеров, которые соответствуют членам полинома с ненулевыми коэффициентами. В данном случае в полиноме отсутствует слагаемое х, поэтому выход
триггера DD1 напрямую соединён со входом триггера DD2 (не через схему
Исключающее ИЛИ).
81
________________________________________________________________________________
Формирование обрабатываемых данных (информационных битов)
производят с помощью ключа, обозначенного тремя символами [2]. Ввод
начинают со старших битов. Например, для числа 101101100000000 ввод
начинается с единицы.
Ввод каждого информационного бита подтверждается с помощью
ключа [1]. Напомним, что синхронные D-триггеры срабатывают только при
поступлении тактового сигнала на вход С триггера. Переключение триггера
происходит по переднему фронту синхроимпульса (когда ключ [1] переходит из нижнего положения в верхнее, тактовый импульс переходит из 0 в 1).
Результат моделирования показан на следующем рисунке. Старший
триггер DD3 находится в состоянии «0» (светодиод H3 не горит). Триггеры
DD1 и DD2 находятся в состоянии «1» (светодиоды Н1 и Н2 горят). В результате моделирования получено число 011. Необходимо обратить внимание на то, что при записи двоичного результата старший бит находится
слева, а в схеме – справа.
Для порождающего полинома g ( x )  x  x  1 схема деления показана на следующем рисунке. Схема содержит только два триггера, так как
это полином второй степени. Наличие двух схем Исключающее ИЛИ говорит о том, что в полиноме нет неиспользуемых слагаемых (нет нулевых коэффициентов).
2
82
_________________________________________________________________
Если
для
кодирования используется порождающий
g ( x )  x  x  1 , то схема нахождения остатка выглядит так:
полином
3
Ниже показана схема нахождения остатка для порождающего полинома g ( x)  x  x  x  x  1 .
8
7
6
4
83
________________________________________________________________________________
6.4.
Моделирование циклического сдвига
При декодировании принятых данных с помощью кода БЧХ требуется выполнить циклические сдвиги чисел вправо. На рисунке показан регистр сдвига, построенный на шести D-триггерах (приложение Multisim).
Входы триггеров обозначены символами 1D…6D, выходы – 1Q…6Q.
Триггеры имеют общий вход синхронизации CLK. Выходы предыдущих
триггеров соединены со входами последующих триггеров, за исключением
шестого (последнего) триггера. Срабатывание триггеров происходит по переднему фронту синхроимпульса CLK. В штатном режиме на вход CLR
(очистка) должна быть подана логическая единица.
Светодиоды Х1…Х6 используются для индикации состояний триггеров в процессе моделирования работы регистра.
Ключ S1 служит для формирования синхроимпульсов. Ключ S2 предназначен для формирования исходных данных, последовательно вводимых
в регистр. Ключ S3 служит для изменения режима работы регистра сдвига.
В верхнем положении ключа S3 осуществляется ввод исходных данных в
регистр. В нижнем положении ключа осуществляется моделирование операции циклического сдвига. В этом положении ключа выход последнего триггера 6Q через переключатель S3 соединяется со входом первого триггера 1D
(формируется замкнутый цикл, кольцо).
Если необходимо выполнить моделирование сдвига многоразрядных
машинных слов, то следует использовать несколько указанных микросхем.
Для моделирования сдвига пятнадцатиразрядных чисел потребуется три
микросхемы, причём, последние три триггера не используются.
Предположим, что требуется выполнить четыре сдвига числа 011011.
Ввод числа начинают с младших разрядов. На рисунке показана фаза
84
_________________________________________________________________
ввода, на которой введены четыре младших бита числа 1011.
Процесс всех сдвигов описан в таблице. Окончательный результат
сдвигов отображён на последнем рисунке
Номера сдвигов
R(x)
1 сдвиг
2 сдвиг
3 сдвиг
4 сдвиг
.
Числа
011011
101101
110110
011011
101101
85
________________________________________________________________________________
7.
Задание на курсовую работу «Исследование методов
кодирования и шифрования»
1. С помощью одного из трёх методов (1 - Шеннона-Фано, 2 - RLE, 3
- LZW) сжать фамилию, имя, отчество, год, день и месяц рождения. Получить последовательность двоичных чисел d1. Полученную последовательность ограничить величиной 128 бит. Метод сжатия определяется последней
цифрой зачётки (см. таблицу 7.1).
Табл.7.1. Выбор метода сжатия
Последняя цифра 0, 1, 2
3, 4, 5, 6
7, 8, 9
зачётки
Метод сжатия
Шеннона-Фано RLE
LZW
2. Зашифровать последовательность d1 методом гаммирования или
шифром с управляемыми операциями. Шифр выбрать по предпоследней
цифре зачётки (см. табл.7.2).
Табл.7.2. Выбор шифра
Предпоследняя цифра за- 0, 1, 2, 8, 3
4, 5, 6, 7, 9
чётки
Шифр
Гаммирования С управляемыми операциями
Гамма выбирается с помощью таблицы 7.3. Управляемые операции
определяются таблицей 7.4.
Табл.7.3. Выбор гаммы
М
Гамма десятичная
М
Гамма десятичная
1
50, 60, 70, 110, 120, 130, 140
33 33, 44, 55, 66, 77, 88, 99
2
51, 61, 71, 111, 121, 131, 141
34 34, 45, 56, 67, 78, 89, 90
3
52, 62, 72, 112, 122, 132, 142
35 35, 46, 57, 68, 79, 80, 91
4
53, 63, 73, 113, 123, 133, 143
36 36, 47, 58, 69, 70, 81, 92
5
54, 64, 74, 114, 124, 134, 144
37 37, 48, 59, 60, 71, 82, 93
6
55, 65, 75, 115, 125, 135, 145
38 38, 49, 50, 61, 72, 83, 94
7
56, 66, 76, 116, 126, 136, 146
39 39, 40, 51, 62, 73, 84, 95
8
57, 67, 77, 117, 127, 137, 147
40 30, 41, 52, 63, 74, 85, 96
9
58, 68, 78, 118, 128, 138, 148
41 30, 160, 10, 170, 41, 51, 231
10 59, 69, 79, 119, 129, 139, 149
42 31, 161, 11, 171, 42, 52, 232
11 240, 20, 150, 30, 160, 10, 170
43 32, 162, 12, 172, 43, 53, 233
12 241, 21, 151, 31, 161, 11, 171
44 33, 163, 13, 173, 44, 54, 234
13 242, 22, 152, 32, 162, 12, 172
45 34, 164, 14, 174, 45, 55, 235
14 243, 23, 153, 33, 163, 13, 173
46 35, 165, 15, 175, 46, 56, 236
86
_________________________________________________________________
15 244, 24, 154, 34, 164, 14, 174
47 36, 166, 16, 176, 47, 57, 237
16 245, 25, 155, 35, 165, 15, 175
48 37, 167, 17, 177, 48, 58, 238
17 246, 26, 156, 36, 166, 16, 176
49 38, 168, 18, 178, 49, 59, 239
18 247, 27, 157, 37, 167, 17, 177
50 39, 169, 19, 179, 40, 50, 230
19 248, 28, 158, 38, 168, 18, 178
51 170, 41, 51, 231, 151, 15, 77
20 249, 29, 159, 39, 169, 19, 179
52 171, 42, 52, 232, 151, 15, 77
21 110, 120, 130, 140, 20, 30, 40
53 172, 43, 53, 233, 151, 15, 77
22 111, 121, 131, 141, 19, 29, 39
54 173, 44, 54, 234, 151, 15, 77
23 112, 122, 132, 142, 18, 28, 38
55 174, 45, 55, 235, 151, 15, 77
24 113, 123, 133, 143, 17, 27, 37
56 175, 46, 56, 236, 151, 15, 77
25 114, 124, 134, 144, 16, 26, 36
57 176, 47, 57, 237, 151, 15, 77
26 115, 125, 135, 145, 15, 25, 35
58 177, 48, 58, 238, 151, 15, 77
27 116, 126, 136, 146, 14, 24, 34
59 178, 49, 59, 239, 151, 15, 77
28 117, 127, 137, 147, 13, 23, 33
60 179, 40, 50, 230, 151, 15, 77
29 118, 128, 138, 148, 12, 22, 32
61 114, 12, 134, 144, 116, 26, 36
30 119, 129, 139, 149, 11, 21, 31
62 115, 12, 135, 145, 115, 25, 35
31 31, 42, 53, 64, 75, 86, 97
63 116, 12, 136, 146, 114, 24, 34
32 32, 43, 54, 65, 76, 87, 98
64 117, 12, 137, 147, 113, 23, 33
Номер варианта М вычисляется по двум последним цифрам номера
зачётки N по формуле:
M = N(mod 64) +1.
3. Гамму для аддитивного шифра следует взять из табл.7.3. Каждое
число гаммы должно быть представлено восьмиразрядным двоичным числом. Гамму необходимо циклически повторить несколько раз так, чтобы
криптограмма составила 128 бит. Получить последовательность двоичных
чисел (криптограмму) d2. Процесс формирования криптограммы нужно описать с помощью таблицы.
Табл. 7.4. Выбор шифрующей операций
Значения гаммы G
Варианты
M G
M G
M G
M G
1
2
3
4
5
6
7
8
9
0,5,6,7
2,3,7,11
0,1,4,5
0,13,14,15
1,5,9,13
0,5,10,15
0,4,8,12
2,6,10,14
3,7,11,15
1,3,11
8,12,14,15
2,3,12,14,15
4,6,8,10,12
3,7,11,15
3,6,9,12
1,5,9,13
0,4,8,12
2,6,10,14
2,8,12,15
0,1,5,9,13
6,8,10
1,3,5
2,6,10,14
4,8,7,11
2,6,10,14
3,7,11,15
1,5,9,13
4,9,10,13,14
4,6,10
7,9,11,13
2,7,9,11
0,4,8,12
1,2,13,14
3,7,11,15
1,5,9,13
0,4,8,12
87
________________________________________________________________________________
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
4,5,8,9,
13,15,3,7
2,3,6,7
2,6,8,12
5,7,10,13
0,4,9,13
3,7,8,12
0,1,2,3
5,7,10,13
2,6,11,15
4,8,7,11
0,4,11,15
7,9,11,13
0,1,3,13
8,10,12,14
4,5,7,9
5,7,9,11
1,7,8,10
0,4,8,12
2,5,10,14
2,6,10,14
0,4,8,12
6,9,10,12
2,3,12,13
2,6,9,12
10,11,14,15
3,7,11,15
4,6,12,15
1,5,8,12
0,4,10,14
4,5,6,7
6,1,2,14
0,4,9,13
3,6,9,12
1,5,10,14
0,1,4,5
2,5,10,14
1,3,5,7
3,6,8,10
10,12,14,15
2,3,11,15
2,6,10,14
4,6,7,15
1,5,9,13
3,7,11,15
1,4,8,13
0,1,6,7
0,4,8,11
4,5,8,9
0,4,10,14
0,2,8,11
3,7,10,14
2,6,11,15
8,9,10,11
3,4,8,9
1,3,5,7,
1,2,5,10
2,6,9,13
2,3,6,8
4,6,7,15
0,2,4,6
0,1,2,11
1,2,4,13
0,4,5,14
1,3,5,15
1,3,12,13
0,3,4,7
1,2,5,14
2,3,5,7
10,11,14,15
1,5,10,14
0,1,12,13
1,5,9,13
1,3,9,14
2,6,11,15
1,5,9,13
12,13,14,15
0,11,12,15
8,10,12,14
0,13,14,15
3,7,8,12
10,12,14,15
8,9,11,12
9,11,13,15
12,13,14,15
0,3,6,8
6,9,12,13
7,9,11,13
0,8,9,11
8,11,12,15
6,9,10,13
0,11,14,15
Номер варианта М вычисляется по двум последним цифрам номера
зачётки N по формуле:
M = N(mod 32) +1.
4. Используя данные таблицы 4 выполнить шифрование с помощью
управляемых операций. Для этого шифра задано только шестнадцать значений гаммы (от 0 до 15). Необходимые значения гаммы для остальных символов следует получить путём циклического повторения гаммы. Гамма и
шифруемый текст должны быть представлены четырёхразрядными числами.
Криптограмма формируется по следующему правилу: при выполнении логических операций результат будет четырёхразрядным, при выполнении
арифметических операций криптограмма записывается с помощью пяти разрядов. Длину криптограммы следует ограничить величиной 128 бит. В результате шифрования последовательности d1 будет получена криптограмма
d2.
5. Разбить последовательность d2 на группы данных по 7 бит. Последнюю группу дополнить пятою нулями до числа, кратного семи битам. Получить последовательность d3, состоящую из 19-ти семибитных чисел.
88
_________________________________________________________________
6. Последовательность d3 закодировать помехоустойчивым кодом
БЧХ. При кодировании использовать порождающий полином
g ( x)  x 8  x 7  x 6  x 4  1 . Получить последовательность d4, состоящую
из 285-ти бит.
7. Стеганографически внедрить (методом LSB или форматной стеганографии) первые 15 бит последовательности d4 в графический файл формата BMP или звуковой файл формата WAV. Тип контейнера выбирается по
предпоследней цифре зачётки. Если предпоследняя цифра зачётки нечётная,
то следует использовать графический контейнер. Метод форматной стеганографии используется если последняя цифра зачётки нечётная.
8. Выполнить декодирование (код БЧХ) первых пятнадцати бит принятой последовательности. Перед выполнением декодирования исказить
первый и седьмой биты последовательности d4 (счёт разрядов ведётся
слева). Полученный результат сравнить с первыми семью битами последовательности d3.
9. Выполнить моделирование работы криптосистемы (шифр гаммирования или шифр с управляемыми операциями в зависимости от варианта).
10.
Выполнить моделирование операции деления на полином.
11.
Выполнить моделирование операции циклического сдвига.
89
________________________________________________________________________________
Список использованной литературы
1. Котельников В. А. О пропускной способности эфира и проволоки в
электросвязи — Всесоюзный энергетический комитет. // Материалы к I Всесоюзному съезду по вопросам технической реконструкции дела связи и развития слаботочной промышленности, 1933. Репринт статьи в журнале УФН,
176:7 (2006), 762—770.
2. Shannon C. E. A Mathematical Theory of Communication // Bell System
Technical Journal. — 1948. — Т. 27. — pp. 379 — 656.
3. Huffman D. A. A method for the construction of minimum-redundancy
codes, Proc. Inst. Radio Engineers, vol. 40, no. 9, pp. 1098-1101, Sep. 1952.
4. Алексеев, А. П. Методы сжатия информации [Текст]: метод. указания к
провед. лаб. работ по дисц." Информатика " для студ. спец. 090302 "Информационная безопасность телекоммуникационных систем", 200700 "Фотоника и
оптоинформатика", 210400 "Радиотехника" / Алексеев, А. П., Орлов, В. В.;
ПГУТИ, Каф. ИВТ. - Самара: ПГУТИ, 2013. - 20 с.
5. Алексеев А.П. Информатика 2015: учебное пособие/ Алексеев А.П.
– М: СОЛОН-Пресс, 2015. – 400 с. ISBN 978-5-91359-158-6.
6. Цилькер, Б.Я. Организация ЭВМ и систем [Текст]: учеб. для вузов /
Б. Я. Цилькер, С. А. Орлов, - СПб: Питер, 2011. - 687 с.
7. Авдеев, В. А. Периферийные устройства: интерфейсы, схемотехника, программирование [Текст]: учеб. пособие для вузов / Авдеев, В. А. М.: ДМК Пресс, 2009. – 848 c.
8. Организация и проведение курсового проектирования. Положение
[Текст]: РД ПГУТИ 2.11.7 – 2017 – Отдел менеджмента качества ПГУТИ.
9. Алексеев А. П., Моделирование криптосистемы с управляемыми
операциями с помощью MULTISIM/ Алексеев А. П., Жеренов Ю.В., Орлов
В. В. // Инфокоммуникационные технологии, том 7, № 4, 2009. Стр. 78-82.
10. Кловский, Д. Д. Теория электрической связи [Текст]: [учебник для вузов связи] / Д. Д. Кловский. - М.: Радиотехника, 2009. - 648 с.
11. Авдеев В.А. Периферийные устройства: интерфейсы, схемотехника,
программирование. – М.: ДМК Пресс, 2009. – 848 с.
12. Алексеев А.П. Способ стеганографического внедрения дополнительной информации в семплы цифровых звуковых сигналов. Патент №
2618379. Дата государственной регистрации в Государственном реестре
изобретений РФ 3 мая 2017.
13. Алексеев А.П. Многоуровневая защита информации. Монография.
Самара: ПГУТИ-ИУНЛ, 2017. – 128 с. ISBN 978-5-904029-72-2. Заказ №
1007962.
14. https://journal.tinkoff.ru/bitcoin/
90
_________________________________________________________________
Заключение
Информатика очень динамичная наука, изменения в которой происходят каждый день. Наибольший прогресс в развитии этой науки происходит в областях использования мультимедийных приложений, кодирования и
защиты информации. Авторы уделили наибольшее внимание в этой публикации именно этим направлениям.
Учебное пособие позволяет преподавателям гибко использовать
предложенный авторами материал. В зависимости от рабочей программы и
часов, отводимых на курсовое проектирование, можно корректировать содержание курсовой работы.
Выполненные студентами задания позволяют им прочно закрепить
полученные навыки в переводе чисел из одной системы счисления в другую,
закрепить знания таблиц истинности логических операций, научиться выполнить арифметические операции в дополнительном коде, познакомиться
с форматами мультимедийных файлов, научиться работать инструментальными средствами (редактор памяти, система моделирования), сделать первый шаг в приобретении навыков решения сложных технических задач.
В процессе выполнения КР у студентов формируется понимание того,
что кодирование позволяет получить те или иные новые свойства данных
(помехоустойчивость, компактность, нечитаемость, скрытость).
Составленные задания позволяют понять отличие кодирования и
шифрования: кодирование и декодирование производятся по известным алгоритмам, поэтому декодирование может быть выполнено любым специалистом. Шифрование и расшифрование осуществляют также по многократно
проверенным алгоритмам, но при этом имеется некоторый секретный параметр, который позволяет выполнить расшифрование только лицу, владеющему ключом.
Достаточно новым материалом, с которым знакомятся студенты, являются задания, связанные со стеганографией. Выбор популярных мультимедийных форматов для скрытой передачи информации позволяет обучаемым ознакомиться со структурой звуковых и графических файлов.
В процессе курсового проектирования закрепляется материал, относящийся к аналого-цифровому преобразованию. Закрепляются важные понятия (частота дискретизации, разрядность семпла). Использование графического контейнера заставляет студентов внимательно отнестись к изучению цветовой модели RGB.
Курсовая работа побуждает студентов к поиску новых способов преобразования информации и к нацеливает их на разработку новых методов
криптоанализа.
91
________________________________________________________________________________
Приложение 1
Образец титульного листа
Государственное бюджетное образовательное учреждение высшего
профессионального образования «Поволжский государственный университет телекоммуникаций и информатики»
Кафедра
«ИНФОРМАТИКИ И
ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ»
Сдана на проверку
___________________
Допустить к защите
________________________
"_____"_____ 20___ г.
"_____"___________ 20__ г
Защищена с оценкой
_______________________
"_____"___________20__ г.
КУРСОВАЯ РАБОТА
ПО ИНФОРМАТИКЕ
«Исследование методов кодирования и
шифрования»
Студент (ка) группы __________________________.
(подпись)
Фамилия И. О.
Номер зачётки________________________________
Руководитель
_______________________________
(подпись)
Самара, 20___г.
92
_________________________________________________________________
Приложение 2.
Таблица СР-1251
Десятичная
СС
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Двоичная
СС
00000000
00000001
00000010
00000011
00000100
00000101
00000110
00000111
00001000
00001001
00001010
00001011
00001100
00001101
00001110
00001111
00010000
00010001
00010010
00010011
00010100
00010101
00010110
00010111
00011000
00011001
00011010
00011011
00011100
00011101
00011110
00011111
00100000
Шестнадцатеричная СС
00
01
02
03
04
05
06
07
08
09
0A
0B
0C
0D
0E
0F
10
11
12
13
14
15
16
17
18
19
1A
1B
1C
1D
1E
1F
20
Символ, команда
Ноль
Начало заголовка
Начало текста
Конец текста
Конец передачи
Запрос
Подтверждение приёма
Звуковой сигнал
Забой (Back Space)
Горизонтальная табуляция
Перевод строки
Вертикальная табуляция
Перевод страницы
Возврат каретки
Верхний регистр
Нижний регистр
Отключение от линии
Управление 1
Управление 2
Управление 3
Управление 4
Нет подтверждения
Синхронизация
Конец передающего блока
Отмена
Конец носителя
Замена
Прерывание
Разделитель файлов
Разделитель групп
Разделитель записей
Разделитель элементов
Пробел
93
________________________________________________________________________________
Дес.
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
Двоичная
00100001
00100010
00100011
00100100
00100101
00100110
00100111
00101000
00101001
00101010
00101011
00101100
00101101
00101110
00101111
00110000
00110001
00110010
00110011
00110100
00110101
00110110
00110111
00111000
00111001
00111010
00111011
00111100
00111101
00111110
00111111
01000000
01000001
01000010
01000011
01000100
Шестнадц.
21
22
23
24
25
26
27
28
29
2A
2B
2C
2D
2E
2F
30
31
32
33
34
35
36
37
38
39
3A
3B
3C
3D
3E
3F
40
41
42
43
44
Символ
!
“
#
$
%
&
‘
(
)
*
+
,
.
/
0
1
2
3
4
5
6
7
8
9
:
;
<
=
>
?
@
A
B
C
D
94
_________________________________________________________________
Дес.
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
Двоичная
01000101
01000110
01000111
01001000
01001001
01001010
01001011
01001100
01001101
01001110
01001111
01010000
01010001
01010010
01010011
01010100
01010101
01010110
01010111
01011000
01011001
01011010
01011011
01011100
01011101
01011110
01011111
01100000
01100001
01100010
01100011
01100100
01100101
01100110
01100111
01101000
Шестнадц.
45
46
47
48
49
4A
4B
4C
4D
4E
4F
50
51
52
53
54
55
56
57
58
59
5A
5B
5C
5D
5E
5F
60
61
62
63
64
65
66
67
68
Символ
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
e
f
g
h
95
________________________________________________________________________________
Дес.
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
Двоичная
01101001
01101010
01101011
01101100
01101101
01101110
01101111
01110000
01110001
01110010
01110011
01110100
01110101
01110110
01110111
01111000
01111001
01111010
01111011
01111100
01111101
01111110
01111111
10000000
10000001
10000010
10000011
10000100
10000101
10000110
10000111
10001000
10001001
10001010
10001011
10001100
Шестнадц.
69
6A
6B
6C
6D
6E
6F
70
71
72
73
74
75
76
77
78
79
7A
7B
7C
7D
7E
7F
80
81
82
83
84
85
86
87
88
89
8A
8B
8C
Символ
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
{
|
}
~
Удаление (DEL)
Ђ
Ѓ
Нижний апостроф ‚
ѓ
Двойные нижние кавычки „
…
†
‡
€
Знак промилле ‰
Љ
<
Њ
96
_________________________________________________________________
Дес.
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
Двоичная
10001101
10001110
10001111
10010000
10010001
10010010
10010011
10010100
10010101
10010110
10010111
10011000
10011001
10011010
10011011
10011100
10011101
10011110
10011111
10100000
10100001
10100010
10100011
10100100
10100101
10100110
10100111
10101000
10101001
10101010
10101011
10101100
10101101
10101110
10101111
10110000
Шестнадц.
8D
8E
8F
90
91
92
93
94
95
96
97
98
99
9A
9B
9C
9D
9E
9F
A0
A1
A2
A3
A4
A5
A6
A7
A8
A9
AA
AB
AC
AD
AE
AF
B0
Символ
Ќ
Ћ
Џ
ђ
‘
’
“
”
•
Короткое тире –
Длинное тире —
Не определён
Торговая марка ™
љ
>
њ
ќ
ћ
џ
Неразрывный пробел
Ў
ў
Ј
¤
Ґ
¦
§
Ё
©
Є
«
¬
­Ї
®
Ї
Градус °
97
________________________________________________________________________________
Дес.
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
Двоичная
10110001
10110010
10110011
10110100
10110101
10110110
10110111
10111000
10111001
10111010
10111011
10111100
10111101
10111110
10111111
11000000
11000001
11000010
11000011
11000100
11000101
11000110
11000111
11001000
11001001
11001010
11001011
11001100
11001101
11001110
11001111
11010000
11010001
11010010
11010011
11010100
Шестнадц.
B1
B2
B3
B4
B5
B6
B7
B8
B9
BA
BB
BC
BD
BE
BF
C0
C1
C2
C3
C4
C5
C6
C7
C8
C9
CA
CB
CC
CD
CE
CF
D0
D1
D2
D3
D4
Символ
±
І
i
ґ
µ
¶
Срединная точка ·
ё
№
є
»
ј
Ѕ
ѕ
ї
А
Б
В
Г
Д
Е
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
98
_________________________________________________________________
Дес.
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
Двоичная
11010101
11010110
11010111
11011000
11011001
11011010
11011011
11011100
11011101
11011110
11011111
11100000
11100001
11100010
11100011
11100100
11100101
11100110
11100111
11101000
11101001
11101010
11101011
11101100
11101101
11101110
11101111
11110000
11110001
11110010
11110011
11110100
11110101
11110110
11110111
11111000
Шестнадц.
D5
D6
D7
D8
D9
DA
DB
DC
DD
DE
DF
E0
E1
E2
E3
E4
E5
E6
E7
E8
E9
EA
EB
EC
ED
EE
EF
F0
F1
F2
F3
F4
F5
F6
F7
F8
Символ
Х
Ц
Ч
Ш
Щ
Ъ
Ы
Ь
Э
Ю
Я
а
б
в
г
д
е
ж
з
и
й
к
л
м
н
о
п
р
с
т
у
ф
х
ц
ч
ш
99
________________________________________________________________________________
Дес.
249
250
251
252
253
254
255
Двоичная
11111001
11111010
11111011
11111100
11111101
11111110
11111111
Шестнадц.
F9
FA
FB
FC
FD
FE
FF
Символ
щ
ъ
ы
ь
э
ю
я
Приложение 3.
Список аббревиатур
АЦП (аналого- цифровой преобразователь) — устройство, которое
превращает аналоговый (непрерывный) сигнал в цифровые данные.
БЧХ-коды – коды Боуза — Чоудхури — Хоквингхема — в теории кодирования это широкий класс циклических кодов, применяемых для защиты
информации от ошибок.
КР – курсовая работа.
РЭУ – радиоэлектронное устройство.
ЦАП (цифроаналоговый преобразователь) — устройство, которое
превращает цифровой сигнал в аналоговый.
LZW — метод сжатия информации, названный в честь Ле́мпеля —
Зи́ва — Ве́лча (Lempel-Ziv-Welch).
RLE — (run-length encoding) метод сжатия информации, основанный
на учёте имеющихся повторений в сжимаемых данных.
LSB — (Least Significant Bit, наименьший значащий бит) стеганографический метод скрытой передачи информации, основанный на замене
младших значащих битов в мультимедийном контейнере на скрываемые
данные.
100
_________________________________________________________________
Приложение 4.
Глоссарий
Архив – сообщение, подвергнутое обработке, в результате которого
размер файла уменьшается, а объём информации остаётся прежним.
Атака — действия, предпринимаемые криптоаналитиком с целью
раскрытия секретного ключа.
Битрейт — скорость передачи информации, измеряемая в битах за
секунду.
Дамп памяти — текстовое представление файла (оперативной или
постоянной памяти) с указанием адресов ячеек памяти и их содержимым.
Кодек (сокращение от слов кодер – декодер) — устройства или программы, предназначенные для кодирования информации на передающей
стороне и декодирования информации на приёмной стороне системы связи.
Криптография (Cryptography) — наука, занимающаяся разработкой
методов шифрования — преобразований, которые делают текст нечитаемым
(непонятным) и трудно раскрываемым без знания секретных ключей.
Майнинг — способ эмиссии крптовалюты, основанный на выполнении математических операций с помощью ЭВМ.
Модель — материальный объект либо образ, которые упрощённо
отображают самые существенные свойства объекта исследования. Под образом понимаются: формула, изображение, словесное описание, схема, граф,
чертёж, план, карта, блок-схема алгоритма, ноты и т.п.
Пиксель (иногда — пиксел) — элементарная точка изображения на
экране дисплея, которой может быть независимо от других точек присвоены
свои цвет и интенсивность. Экран дисплея представляет собой матрицу (таблицу, решётку) пикселей, а изображение — совокупность пикселей различного цвета.
Протокол — правила (соглашения, стандарт) передачи информации
в сети.
Расшифрование — обратный зашифрованию процесс. При расшифровании зашифрованный текст (криптограмма, шифрограмма, шифровка)
преобразуется в исходный открытый текст. В отличии от дешифрования расшифрование происходит при известном ключе.
Разрешение (глубина звука)— это количество уровней квантования,
используемых для замены непрерывного аналогового сигнала цифровым
сигналом (разрядность семпла).
Семпл (отсчёт) – группа бит, полученная в результате аналого-цифрового преобразования, которая описывает уровень звуковой волны в короткий момент выполнения одного (отдельного) АЦП преобразования (за один
период частоты дискретизации).
101
________________________________________________________________________________
Словарь – набор сочетаний символов (фраз), входящих в сообщение,
которым поставлены в соответствии коды (метод LZW).
Сжатие информации без потерь (архивация) — это такое преобразование информации, при котором объем файла уменьшается, а количество
информации, содержащейся в архиве, остаётся прежним.
Стеганография (Steganography) — наука, изучающая такие методы
организации передачи секретных сообщений, которые скрывают сам факт
передачи информации.
ASCII (American Standard Code for Information Interchange — американский стандартный код для обмена информацией) — схема кодирования
букв, цифр, знаков пунктуации, управляющих и других символов с помощью
восьмибитного кода, позволяющего получить 256 различных кодовых комбинаций, которые записываются в виде кодовой таблицы. Первая половина
таблицы используется для кодировки латинских букв, а вторая — для кодировки символов национальных алфавитов.
dpi (dot per inch) — число точек на дюйм. Единица измерения разрешающей способности различных устройств (принтеров, сканеров, ручных
манипуляторов и т. д.).
Файл — это набор взаимосвязанных данных, воспринимаемых компьютером как единое целое, имеющих общее имя, находящихся на магнитном или оптическом дисках, в оперативной памяти, Flash-памяти или на другом носителе информации.
Фрейм – группа семплов, находящихся в разных каналах и описывающая уровень звуковой волны за один период частоты дискретизации. Для
монофонического сигнала фрейм состоит из единственного семпла. Стереофонический фрейм состоит из двух семплов и т.д.
Шифрование — такое преобразование информации, которое делает
исходный текст нечитаемым и трудно раскрываемым без знания специальной секретной информации — ключа.
102
_________________________________________________________________
Приложение 5
Примеры оформления источников курсовой работы
Нормативно-правовые источники
1. Издания. Международная стандартная нумерация книг [Текст]:
ГОСТ 7.53–2001.
2. Информационная технология (ИТ). Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи [Текст]: ГОСТ Р 34.10-2012.
Описание книги одного автора
3. Бауэр, Ф. Расшифрованные секреты. Методы и принципы криптологии [Текст] / Ф. Бауэр, – М.: Мир, 2007. 550 c.
4. Быховский, М. А. Развитие телекоммуникаций. На пути к информационному обществу. Развитие спутниковых телекоммуникационных систем
[Текст]: учеб. пособие для вузов / М. А. Быховский. - М.: Горячая линияТелеком, 2014. - 439 с. - (История электросвязи и радиотехники).
5. Мао, B. Современная криптография. Теория и практика. [Текст] /
B.Мао, – М.: Вильямс, 2005. 763 с
6. Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. [Текст] / Б. Шнайер, – М.: Триумф, 2003. 806 с
Описание книги двух авторов
7. Балашов, А. И. Правоведение [Текст]: учебник для вуза / А. И. Балашов, Г. П. Рудаков. - 5-е изд. [доп. и перераб.]. – СПб: Питер,2014. - 462 с.
- (Учебник для вузов).
8. Игумнов, Д. В. Основы полупроводниковой электроники [Текст] :
учеб. пособие для вузов / Д. В. Игумнов, Г. П. Костюнина. - 2-е изд., доп. М.: Горячая линия-Телеком, 2014. - 393 с.: рис., табл., ил. - (Учебное пособие).
9. Мендез, А. Справочник по специализированным оптическим волокнам [Текст]: справочник / А. Мендез, Т. Ф. Морзе; ред. К. А. Пестрецова;
пер. Н. Л. Бирюков. - М.: Техносфера, 2012. - 728 с.
Описание электронного ресурса удалённого доступа (Internet)
10. Габец, А.П., Гончаров Д.И. 1С: Предприятие 8.1. Простые примеры разработки. [Текст]/ А.П. Габец, Д.И Гончаров – Москва: ПИТЕР и 1С–
Паблишин, 2009.
11. Встроенный язык программирования 1С: Предприятие. [Электронный ресурс] Режим доступа http://ru.wikipedia.org/wiki, свободный. –
Загл.с экрана.
Документ
Категория
Без категории
Просмотров
27
Размер файла
2 503 Кб
Теги
sirant, kursovoy, yakovlev, makarov, shifrovanija, metod, 2018, proektirovanie, issledovanie, posobie, kodirovanie, uchebnoy, ukazaniya, metodos, alekseevne
1/--страниц
Пожаловаться на содержимое документа