Цель лекции: познакомиться с принципами совместного использования шифрования, помехоустойчивого кодирования и сжатия информации для комплексной защиты информации в процессе ее передачи и хранения.
В процессе передачи информации от источника к потребителю на информацию воздействуют различные неблагоприятные факторы. Криптографические методы защищают информацию только от одного вида разрушающих воздействий – от предумышленного разрушения или искажения информации. Однако на практике при передаче информации от абонента к абоненту возможны случайные помехи на линиях связи, ошибки и сбои аппаратуры, частичное разрушение носителей данных и т.д. Таким образом, в реальных системах связи существует проблема защиты информации от случайных воздействий.
В связи с появлением сетей передачи данных высокой пропускной способности и развитием мультимедиа-технологий возникает проблема шифрования больших объемов информации. Если раньше основным типом шифруемых и передаваемых сообщений было текстовое сообщение, то в ХХI веке криптографическая защита все чаще применяется при передаче цифровых видео- и речевых сообщений, карт местности, для организации видеоконференций. Именно поэтому в последнее время возникает проблема шифрования огромных информационных массивов. Для интерактивных систем типа телеконференций, организации аудио- или видеосвязи, такое шифрование должно осуществляться в реальном режиме времени и по возможности быть незаметным для пользователей.
Решение указанных проблем, в том числе и защита от несанкционированного доступа, может быть достигнуто при комплексном использовании достижений теории информации.
В принципе в теории информации выделяют три вида преобразования информации: криптографическое шифрование, помехоустойчивое кодирование и сжатие (или компрессия). В некоторых научных работах ХХ века все три вида преобразования информации называли кодированием: криптографическое кодирование, помехоустойчивое кодирование и эффективное кодирование (сжатие данных). Общим для всех трех видов преобразования является то, что информация каким-либо образом меняет форму представления, но не смысл. Отличия разных видов кодирования связаны с целью проводимых преобразований.
Так, целью криптографического преобразования является, как известно, защита от несанкционированного доступа, аутентификация и защита от преднамеренных изменений. Помехоустойчивое кодирование выполняется с целью защиты информации от случайных помех при передаче и хранении. Эффективное кодирование производится с целью минимизации объема передаваемых или хранимых данных.
На практике эти три вида преобразования информации обычно используются совместно. Так, например, некоторые программные пакеты перед шифрованием архивируют обрабатываемые данные. С другой стороны, реальные системы передачи информации, будь то локальные и глобальные сети передачи данных, или компьютерные носители информации (CD или DVD-диски) всегда имеют в составе системы защиты информации средства контроля и коррекции случайных ошибок.
Таким образом, криптографическое шифрование, помехоустойчивое кодирование и сжатие отчасти дополняют друг друга и их комплексное использование помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
Для того, чтобы более эффективно использовать на практике криптографические методы защиты информации, рассмотрим основные положения теорий помехоустойчивого и эффективного кодирования, используемые в системах защиты информации.
Как уже отмечалось, вопросы криптографического преобразования информации тесно связаны с вопросами помехоустойчивого кодирования сообщений. Это обусловлено, с одной стороны (теоретической), тем, что и при криптографическом шифровании, и при помехоустойчивом кодировании используются одни и те же законы теории информации. С другой стороны (практической) процессы накопления, хранения и передачи информации протекают в условиях воздействия помех, способных исказить хранимые и обрабатываемые данные. Это обуславливает актуальность разработки и использования методов, позволяющих обнаруживать и корректировать подобные ошибки. С математической точки зрения задача сводится к синтезу так называемых помехоустойчивых кодов.
Аналогично понятию шифра в криптографии при обсуждении помехоустойчивого кодирования и вопросов сжатия сообщений вводят понятие кода. Вообще кодом называется совокупность знаков, а также система правил, позволяющая представлять информацию в виде набора таких знаков. Кодовым словом называют любой ряд допустимых знаков. Например, двоичное число 1100 можно считать двоичным 4-разрядным кодовым словом.
Общая идея помехоустойчивого кодирования состоит в том, что из всех возможных кодовых слов считаются допустимыми не все, а лишь некоторые из них. Например, в коде с контролем по четности считаются допустимыми лишь слова с четным числом единиц. Ошибка превращает допустимое слово в недопустимое и поэтому обнаруживается.
Помехоустойчивые коды делятся на блоковые, делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и свёрточные, работающие с данными как с непрерывным потоком.
Блоковые коды характеризуются так называемым минимальным кодовым расстоянием. Вообще, расстоянием по Хэммингу (по имени американского математика Р.У. Хэмминга) между двумя кодовыми словами называется число разрядов, в которых они различны. При этом в качестве минимального кодового расстояния выбирается наименьшее из всех расстояний по Хэммингу для любых пар различных кодовых слов, образующих код.
Например, пусть мы используем только трехразрядные двоичные слова. Всего таких кодовых слов может быть восемь. Те кодовые слова, которые отличаются только на одну единицу, называются соседними. Например, кодовые слова .
(рис 14.1) Трехразрядные двоичные кодовые словаВ случае использования всех трехразрядных двоичных слов для передачи сообщений все они будут считаться допустимыми. Применим контроль по условию четности. Тогда допустимыми будут только выделенные рамками слова с четным числом единиц (см. рис 14.2).
(рис 14.2) Допустимые трехразрядные кодовые слова при контроле по четности Минимальное расстояние между допустимыми словами кода с контролем по четности равно двум (из рис 14.2 видно, что никакие два кодовых слова в рамочках не соединены линиями, то есть не являются соседними). Именно по этой причине одиночная ошибка в кодовом слове превращает это слово в недопустимое.
Платой за помехоустойчивость является необходимость увеличения длины слов по сравнению с обычным кодом. В данном примере только два разряда являются информационными. Это они образуют четыре разных слова. Третий разряд является контрольным и служит только для увеличения расстояния между допустимыми словами. В передаче информации контрольный разряд не участвует, так как является линейно зависимым от информационных. Код с контролем по четности, рассмотренный в качестве примера, позволяет обнаружить одиночные ошибки в блоках данных при передаче данных. Однако он не сможет обнаружить двукратные ошибки потому, что двукратная ошибка переводит кодовое слово через промежуток между допустимыми словами и превращает его в другое допустимое слово.
Таким образом, для того чтобы код приобрел способность к обнаружению и коррекции ошибок, необходимо отказаться от его безызбыточности. Для этого и разделяют всё множество возможных комбинаций двоичных символов на два подмножества: допустимых кодовых слов и недопустимых. Разбиение осуществляется таким образом, чтобы увеличить
Естественно, что введение дополнительных контрольных разрядов увеличивает затраты на хранение или передачу кодированной информации. При этом фактический объем полезной информации остается неизменным. В этом случае можно говорить об избыточности
Мы уже отмечали, что контрольные разряды не передают информацию и в этом смысле бесполезны. Относительное число контрольных разрядов называется избыточностью Q
где n – общее число двоичных разрядов в блоке, а k – число контрольных разрядов.
Например, избыточность рассмотренного трехразрядного кода с контролем по четности составляет:
$$Q=\frac {k}{n}\times 100\%=\frac{1}{3}\times 100\% \approx 33\%$$Избыточность является важной характеристикой кода, причем чрезмерное увеличение избыточности нежелательно. Важной задачей теории информации является синтез кодов с минимальной избыточностью, обеспечивающих заданную обнаруживающую и корректирующую способность.
В качестве иллюстрирующего примера рассмотрим один из простейших кодов, позволяющих обнаруживать и исправлять однократные ошибки – n содержит k информационных и m контрольных разрядов. Коррекция искаженного i-го разряда заключается в сложении (по модулю 2) принятого кодового слова с вектором вида 0…010…0, содержащем единицу в i-ом разряде.
Для n-разрядного кодового слова существует n таких векторов, соответствующих однократным ошибкам, и один нулевой вектор, соответствующий случаю приема слова без ошибок. Таким образом, m контрольных разрядов должны обеспечивать формирование n + 1 вектора ошибки, то есть должно выполняться неравенство $$n \le 2^m -1$$. В результате получается (2m-1, 2m-1-m) код, называемый кодом Хэмминга.
Простейший нетривиальный случай, соответствующий ). При этом нулевому вектору ошибки соответствует нулевой синдром.
a6 | a5 | a4 | a3 | a2 | a1 | a0 | s2 | s1 | s0 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Рассматривая функции si как свертку по модулю 2 разрядов кодовых слов, получим:
Функции si должны обращаться в единицу при наличии ошибки в одном из образующих их разрядов, и в ноль – при отсутствии ошибок. Обеспечение этого требования возможно лишь при условии, что часть разрядов формируется специальным образом. В частности, разряды a0, a1, a2 можно рассматривать как свертку по модулю 2 остальных разрядов, участвующих в соответствующих уравнениях:
Найденные зависимости позволяют генерировать кодовые слова по заданным информационным, а также вычислять синдромы для принятых кодовых слов.
Допустим, исходное информационное слово равно 1101, то есть a6=1, a5=1, a4=1, a3=1. Для преобразования его в допустимое кодовое слово помехоустойчивого (7,4) -
Таким образом, с учетом контрольных разрядов кодовое слово будет равно 1101001.
Если в процессе передачи или хранения слово осталось неискаженным, то его синдром s0…s2 будет соответственно равен: $$s_0 = 1 \oplus 1 \oplus 1 \oplus 1 = 0, s_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0, s_2 = 0 \oplus 1 \oplus 0 \oplus 1 = 0$$,. Синдром, состоящий из одних нулей, указывает на отсутствие ошибки и соответствует нулевому вектору ошибки.
Предположим, что в процессе передачи или хранения в результате воздействия внешних факторов оказался искаженным отдельный разряд кодового слова. Например, вместо слова 1101001 было принято слово 1001001. В этом случае синдром окажется отличным от нуля: s0…s2 будет соответственно равен: $$s_0 = 1 \oplus 1 \oplus 0 \oplus 1 = 1, s_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0, s_2 = 0 \oplus 1 \oplus 0 \oplus 0 = 1$$ Синдром 101 соответствует вектору ошибки 0100000, при этом единица указывает на разряд, в котором эта ошибка произошла. Для ее коррекции достаточно сложить по модулю 2 принятое искаженное кодовое слово с вектором ошибки.
Рассчитаем избыточность (7,4) -
Это очень большое значение. На практике часто применяются существенно более сложные коды, обеспечивающие лучшие характеристики помехоустойчивости при меньшей избыточности.
Как было сказано выше, одной из важных задач предварительной подготовки данных к шифрованию является уменьшение их избыточности и выравнивание статистических закономерностей применяемого языка. Частичное устранение избыточности достигается путём сжатия данных.
Сжатие информации представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения. Алгоритмы, предназначенные для сжатия информации, можно разделить на две большие группы: реализующие сжатие без потерь (обратимое сжатие) и реализующие сжатие с потерями (необратимое сжатие).
Обратимое сжатие подразумевает абсолютно точное восстановление данных после декодирования и может применяться для сжатия любой информации. Оно всегда приводит к снижению объема выходного потока информации без изменения его информативности, то есть без потери информационной структуры. Более того, из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной, а процесс восстановления называется декомпрессией или распаковкой и только после процесса распаковки данные пригодны для обработки в соответствии с их внутренним форматом. Сжатие без потерь применяется для текстов, исполняемых файлов, высококачественного звука и графики.
Необратимое сжатие имеет обычно гораздо более высокую степень сжатия, чем кодирование без потерь, но допускает некоторые отклонения декодированных данных от исходных. На практике существует широкий круг практических задач, в которых соблюдение требования точного восстановления исходной информации после декомпрессии не является обязательным. Это, в частности, относится к сжатию мультимедийной информации: звука, фото- или видеоизображений. Так, например, широко применяются форматы мультимедийной информации JPEG и MPEG, в которых используется необратимое сжатие. Необратимое сжатие обычно не используется совместно с криптографическим шифрованием, так как основным требованием к криптосистеме является идентичность расшифрованных данных исходным. Однако при использовании мультимедиа-технологий данные, представленные в цифровом виде, часто подвергаются необратимой компрессии перед подачей в криптографическую систему для шифрования. После передачи информации потребителю и расшифрования мультимедиа-файлы используются в сжатом виде (то есть не восстанавливаются).
Рассмотрим подробнее некоторые из наиболее распространённых способов обратимого сжатия данных.
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем – это кодирование серий последовательностей (Run
При равномерном кодировании информации на сообщение отводится одно и то же число бит, независимо от вероятности его появления. Вместе с тем логично предположить, что общая длина передаваемых сообщений уменьшится, если часто встречающиеся сообщения кодировать короткими кодовыми словами, а редко встречающиеся – более длинными. Возникающие при этом проблемы связаны с необходимостью использования кодов с переменной длиной кодового слова. Существует множество подходов к построению подобных кодов.
Одними из широко используемых на практике являются словарные методы, к основным представителям которых относятся алгоритмы семейства Зива и Лемпела. Их основная идея заключается в том, что фрагменты входного потока ("фразы") заменяются указателем на то место, где они в тексте уже ранее появлялись. В литературе подобные алгоритмы обозначаются как алгоритмы LZ сжатия.
Подобный метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, так как они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов. Декодирование сжатого текста осуществляется напрямую, – происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа декодера.
Другим подходом к сжатию информации является код Хаффмана, кодер и декодер которого имеют достаточно простую аппаратную реализацию. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды, тогда как реже встречающимся символам – более длинные. За счет этого достигается сокращение средней длины кодового слова и большая эффективность сжатия. Коды Хаффмана имеют уникальный префикс (начало кодового слова), что и позволяет однозначно их декодировать, несмотря на их переменную длину.
Процедура синтеза классического кода Хаффмана предполагает наличие априорной информации о статистических характеристиках источника сообщений. Иначе говоря, разработчику должны быть известны вероятности возникновения тех или иных символов, из которых образуются сообщения. Рассмотрим синтез кода Хаффмана на простом примере.
Пусть источник информации способен генерировать четыре различных символа , а).
Процедура синтеза кода состоит из трех основных этапов. На первом происходит свертка строк таблицы: две строки, соответствующие символам с наименьшими вероятностями возникновения заменяются одной с суммарной вероятностью, после чего таблица вновь переупорядочивается. Свертка продолжается до тех пор, пока в таблице не останется лишь одна строка с суммарной вероятностью, равной единице (рис 14.3, б).
(рис 14.3) Первый этап кодирования ХаффманаНа втором этапе осуществляется построение кодового дерева по свернутой таблице (рис 14.4, а). Дерево строится, начиная с последнего столбца таблицы.
(рис 14.4) Второй этап кодирования ХаффманаКорень дерева образует единица, расположенная в последнем столбце. В рассматриваемом примере эта единица образуется из вероятностей 0,55 и 0,45, изображаемых в виде двух узлов дерева, связанных с корнем. Первый из них соответствует символу S3 и, таким образом, дальнейшее ветвление этого узла не происходит.
Второй узел, маркированный вероятностью 0,45, соединяется с двумя узлами третьего уровня, с вероятностями 0,25 и 0,2. Вероятность 0,2 соответствует символу S1, а вероятность 0,25, в свою очередь, образуется из вероятностей 0,15 появления символа S2 и 0,1 появления символа S4.
Ребра, соединяющие отдельные узлы кодового дерева, нумеруются цифрами , б).
Однако классический алгоритм Хаффмана имеет один существенный недостаток. Для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения.
Другой вариант статического кодирования Хаффмана заключается в просмотре входного потока и построении кодирования на основании собранной статистики. При этом требуется два прохода по файлу – один для просмотра и сбора статистической информации, второй – для кодирования. В статическом кодировании Хаффмана входным символам (цепочкам битов различной длины) ставятся в соответствие цепочки битов также переменной длины – их коды. Длина кода каждого символа берется пропорциональной двоичному логарифму его частоты, взятому с обратным знаком. А общий набор всех встретившихся различных символов составляет алфавит потока.
Существует другой метод – адаптивного или динамического кодирования Хаффмана. Его общий принцип состоит в том, чтобы менять схему кодирования в зависимости от характера изменений входного потока. Такой подход имеет однопроходный алгоритм и не требует сохранения информации об использованном кодировании в явном виде. Адаптивное кодирование может дать большую степень сжатия, по сравнению со статическим, поскольку более полно учитываются изменения частот входного потока. При использовании адаптивного кодирования Хаффмана усложнение алгоритма состоит в необходимости постоянной корректировки дерева и кодов символов основного алфавита в соответствии с изменяющейся статистикой входного потока.
Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество сжатия. Однако кодирование Хаффмана имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит – {0, 1}. Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит.
Совершенно иное решение предлагает арифметическое кодирование. Этот метод основан на идее преобразования входного потока в одно число с плавающей запятой. Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов.
Предполагаемая требуемая последовательность символов при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке.
Рассмотренные методы обеспечивают обратимое сжатие данных. На практике применяются как программные, так и аппаратные их реализации, позволяющие добиваться коэффициентов сжатия порядка 20-40% в зависимости от типа сжимаемой информации.
Таким образом, криптографическое шифрование, помехоустойчивое кодирование и сжатие отчасти дополняют друг друга и их комплексное использование помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
Избыточность – характеристика
Код – совокупность знаков, а также система правил, позволяющая представлять информацию в виде набора таких знаков.
Кодовое слово – любой ряд допустимых знаков в соответствии с используемой системой правил.
Минимальное кодовое расстояние – наименьшее из всех расстояний по Хэммингу для любых пар различных кодовых слов, образующих код.
Помехоустойчивый код – код, позволяющий обнаруживать и корректировать ошибки при хранении и передаче сообщений.
Расстояние по Хэммингу – число разрядов кодовых слов, в которых они различны.
Сжатие информации – процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения.
Соседние кодовые слова – кодовые слова, отличающиеся значением только одного разряда.
В теории информации выделяют три вида преобразования информации: криптографическое шифрование, помехоустойчивое кодирование и сжатие (или эффективное кодирование). Общим для всех трех видов преобразования является то, что информация каким-либо образом меняет форму представления, но не смысл. Отличия разных видов кодирования связаны с целью проводимых преобразований.
Так, целью криптографического преобразования является, как известно, защита от несанкционированного доступа, аутентификация и защита от преднамеренных изменений. Помехоустойчивое кодирование выполняется с целью защиты информации от случайных помех при передаче и хранении. Для этого при записи и передаче в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
Эффективное кодирование (или сжатие информации) представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения. Алгоритмы сжатия информации делятся на две группы: алгоритмы сжатия без потерь (обратимого сжатия) и алгоритмы сжатия с потерями (необратимого сжатия). За счет эффективного кодирования уменьшается избыточность сообщений, что позволяет производить более надежное криптографическое шифрование информации.
Таким образом, криптографическое шифрование, помехоустойчивое кодирование и сжатие отчасти дополняют друг друга и их комплексное использование помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
8 бит. Его избыточность равна 25%. Чему равно число информационных разрядов в нем?S1…S4 с вероятностями возникновения p(S1)=0,1, p(S2)=0,3, p(S3)=0,5, p(S4)=0,1. По этим данным выполните синтез классического кода Хаффмана.В данном курсе были рассмотрены наиболее распространенные в настоящее время методы криптографической защиты информации. Но криптографическая наука, как и любая другая наука, не стоит на месте, а продолжает развиваться. Не прекращаются усилия специалистов по созданию новых методов криптографической защиты информации.
Новая "отрасль" криптографии – асимметричная криптография стала всем уже привычной. Несмотря на то, что открыто уже более десятка алгоритмов шифрования с открытым ключом, продолжается поиск новых методов асимметричного шифрования. Так, например, алгоритмы на эллиптических кривых были предложены учеными только в самом конце ХХ века, а в настоящее время они уже активно используются на практике.
Другая сравнительно молодая ветвь криптографии – исследование криптографических протоколов. Несмотря на то, что первые протоколы появились во второй половине ХХ века, на настоящий момент имеется уже несколько десятков различных типов криптографических протоколов. Криптографические протоколы являются одним из основных объектов исследования теоретической криптографии. Ежегодно специалистами предлагаются новые криптографические протоколы, и задача криптоаналитиков заключается в том, чтобы верно оценить надежность каждого из протоколов.
Одной из относительно новых разработок криптографии является квантовая криптография, основанная на определенных явлениях квантовой физики. Информацию в квантовых системах предлагается передавать по оптоволоконным каналам с помощью квантов света – фотонов, меняющих свое состояние при попытке их перехватить и измерить. Утверждается, что, используя квантовые явления, можно спроектировать и создать такую систему связи, которая всегда сможет обнаруживать подслушивание. Практическая реализация квантовой криптографии пока что находится на самом начальном уровне и встречает множество трудностей.
Таким образом, криптографические методы не прекращают развиваться. Они широко используются и будут использоваться в составе средств комплексной защиты информации.
Цель лекции: познакомиться с принципами совместного использования шифрования, помехоустойчивого кодирования и сжатия информации для комплексной защиты информации в процессе ее передачи и хранения.
В процессе передачи информации от источника к потребителю на информацию воздействуют различные неблагоприятные факторы. Криптографические методы защищают информацию только от одного вида разрушающих воздействий – от предумышленного разрушения или искажения информации. Однако на практике при передаче информации от абонента к абоненту возможны случайные помехи на линиях связи, ошибки и сбои аппаратуры, частичное разрушение носителей данных и т.д. Таким образом, в реальных системах связи существует проблема защиты информации от случайных воздействий.
В связи с появлением сетей передачи данных высокой пропускной способности и развитием мультимедиа-технологий возникает проблема шифрования больших объемов информации. Если раньше основным типом шифруемых и передаваемых сообщений было текстовое сообщение, то в ХХI веке криптографическая защита все чаще применяется при передаче цифровых видео- и речевых сообщений, карт местности, для организации видеоконференций. Именно поэтому в последнее время возникает проблема шифрования огромных информационных массивов. Для интерактивных систем типа телеконференций, организации аудио- или видеосвязи, такое шифрование должно осуществляться в реальном режиме времени и по возможности быть незаметным для пользователей.
Решение указанных проблем, в том числе и защита от несанкционированного доступа, может быть достигнуто при комплексном использовании достижений теории информации.
В принципе в теории информации выделяют три вида преобразования информации: криптографическое шифрование, помехоустойчивое кодирование и сжатие (или компрессия). В некоторых научных работах ХХ века все три вида преобразования информации называли кодированием: криптографическое кодирование, помехоустойчивое кодирование и эффективное кодирование (сжатие данных). Общим для всех трех видов преобразования является то, что информация каким-либо образом меняет форму представления, но не смысл. Отличия разных видов кодирования связаны с целью проводимых преобразований.
Так, целью криптографического преобразования является, как известно, защита от несанкционированного доступа, аутентификация и защита от преднамеренных изменений. Помехоустойчивое кодирование выполняется с целью защиты информации от случайных помех при передаче и хранении. Эффективное кодирование производится с целью минимизации объема передаваемых или хранимых данных.
На практике эти три вида преобразования информации обычно используются совместно. Так, например, некоторые программные пакеты перед шифрованием архивируют обрабатываемые данные. С другой стороны, реальные системы передачи информации, будь то локальные и глобальные сети передачи данных, или компьютерные носители информации (CD или DVD-диски) всегда имеют в составе системы защиты информации средства контроля и коррекции случайных ошибок.
Таким образом, криптографическое шифрование, помехоустойчивое кодирование и сжатие отчасти дополняют друг друга и их комплексное использование помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
Для того, чтобы более эффективно использовать на практике криптографические методы защиты информации, рассмотрим основные положения теорий помехоустойчивого и эффективного кодирования, используемые в системах защиты информации.
Как уже отмечалось, вопросы криптографического преобразования информации тесно связаны с вопросами помехоустойчивого кодирования сообщений. Это обусловлено, с одной стороны (теоретической), тем, что и при криптографическом шифровании, и при помехоустойчивом кодировании используются одни и те же законы теории информации. С другой стороны (практической) процессы накопления, хранения и передачи информации протекают в условиях воздействия помех, способных исказить хранимые и обрабатываемые данные. Это обуславливает актуальность разработки и использования методов, позволяющих обнаруживать и корректировать подобные ошибки. С математической точки зрения задача сводится к синтезу так называемых помехоустойчивых кодов.
Аналогично понятию шифра в криптографии при обсуждении помехоустойчивого кодирования и вопросов сжатия сообщений вводят понятие кода. Вообще кодом называется совокупность знаков, а также система правил, позволяющая представлять информацию в виде набора таких знаков. Кодовым словом называют любой ряд допустимых знаков. Например, двоичное число 1100 можно считать двоичным 4-разрядным кодовым словом.
Общая идея помехоустойчивого кодирования состоит в том, что из всех возможных кодовых слов считаются допустимыми не все, а лишь некоторые из них. Например, в коде с контролем по четности считаются допустимыми лишь слова с четным числом единиц. Ошибка превращает допустимое слово в недопустимое и поэтому обнаруживается.
Помехоустойчивые коды делятся на блоковые, делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и свёрточные, работающие с данными как с непрерывным потоком.
Блоковые коды характеризуются так называемым минимальным кодовым расстоянием. Вообще, расстоянием по Хэммингу (по имени американского математика Р.У. Хэмминга) между двумя кодовыми словами называется число разрядов, в которых они различны. При этом в качестве минимального кодового расстояния выбирается наименьшее из всех расстояний по Хэммингу для любых пар различных кодовых слов, образующих код.
Например, пусть мы используем только трехразрядные двоичные слова. Всего таких кодовых слов может быть восемь. Те кодовые слова, которые отличаются только на одну единицу, называются соседними. Например, кодовые слова .
(рис 14.1) Трехразрядные двоичные кодовые словаВ случае использования всех трехразрядных двоичных слов для передачи сообщений все они будут считаться допустимыми. Применим контроль по условию четности. Тогда допустимыми будут только выделенные рамками слова с четным числом единиц (см. рис 14.2).
(рис 14.2) Допустимые трехразрядные кодовые слова при контроле по четностиМинимальное расстояние между допустимыми словами кода с контролем по четности равно двум (из рис 14.2 видно, что никакие два кодовых слова в рамочках не соединены линиями, то есть не являются соседними). Именно по этой причине одиночная ошибка в кодовом слове превращает это слово в недопустимое.
Платой за помехоустойчивость является необходимость увеличения длины слов по сравнению с обычным кодом. В данном примере только два разряда являются информационными. Это они образуют четыре разных слова. Третий разряд является контрольным и служит только для увеличения расстояния между допустимыми словами. В передаче информации контрольный разряд не участвует, так как является линейно зависимым от информационных. Код с контролем по четности, рассмотренный в качестве примера, позволяет обнаружить одиночные ошибки в блоках данных при передаче данных. Однако он не сможет обнаружить двукратные ошибки потому, что двукратная ошибка переводит кодовое слово через промежуток между допустимыми словами и превращает его в другое допустимое слово.
Таким образом, для того чтобы код приобрел способность к обнаружению и коррекции ошибок, необходимо отказаться от его безызбыточности. Для этого и разделяют всё множество возможных комбинаций двоичных символов на два подмножества: допустимых кодовых слов и недопустимых. Разбиение осуществляется таким образом, чтобы увеличить
Естественно, что введение дополнительных контрольных разрядов увеличивает затраты на хранение или передачу кодированной информации. При этом фактический объем полезной информации остается неизменным. В этом случае можно говорить об избыточности
Мы уже отмечали, что контрольные разряды не передают информацию и в этом смысле бесполезны. Относительное число контрольных разрядов называется избыточностью Q
где n – общее число двоичных разрядов в блоке, а k – число контрольных разрядов.
Например, избыточность рассмотренного трехразрядного кода с контролем по четности составляет:
$$Q=\frac {k}{n}\times 100\%=\frac{1}{3}\times 100\% \approx 33\%$$Избыточность является важной характеристикой кода, причем чрезмерное увеличение избыточности нежелательно. Важной задачей теории информации является синтез кодов с минимальной избыточностью, обеспечивающих заданную обнаруживающую и корректирующую способность.
В качестве иллюстрирующего примера рассмотрим один из простейших кодов, позволяющих обнаруживать и исправлять однократные ошибки – n содержит k информационных и m контрольных разрядов. Коррекция искаженного i-го разряда заключается в сложении (по модулю 2) принятого кодового слова с вектором вида 0…010…0, содержащем единицу в i-ом разряде.
Для n-разрядного кодового слова существует n таких векторов, соответствующих однократным ошибкам, и один нулевой вектор, соответствующий случаю приема слова без ошибок. Таким образом, m контрольных разрядов должны обеспечивать формирование n + 1 вектора ошибки, то есть должно выполняться неравенство $$n \le 2^m -1$$. В результате получается (2m-1, 2m-1-m) код, называемый кодом Хэмминга.
Простейший нетривиальный случай, соответствующий ). При этом нулевому вектору ошибки соответствует нулевой синдром.
a6 | a5 | a4 | a3 | a2 | a1 | a0 | s2 | s1 | s0 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Рассматривая функции si как свертку по модулю 2 разрядов кодовых слов, получим:
Функции si должны обращаться в единицу при наличии ошибки в одном из образующих их разрядов, и в ноль – при отсутствии ошибок. Обеспечение этого требования возможно лишь при условии, что часть разрядов формируется специальным образом. В частности, разряды a0, a1, a2 можно рассматривать как свертку по модулю 2 остальных разрядов, участвующих в соответствующих уравнениях:
Найденные зависимости позволяют генерировать кодовые слова по заданным информационным, а также вычислять синдромы для принятых кодовых слов.
Допустим, исходное информационное слово равно 1101, то есть a6=1, a5=1, a4=1, a3=1. Для преобразования его в допустимое кодовое слово помехоустойчивого (7,4) -
Таким образом, с учетом контрольных разрядов кодовое слово будет равно 1101001.
Если в процессе передачи или хранения слово осталось неискаженным, то его синдром s0…s2 будет соответственно равен: $$s_0 = 1 \oplus 1 \oplus 1 \oplus 1 = 0, s_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0, s_2 = 0 \oplus 1 \oplus 0 \oplus 1 = 0$$,. Синдром, состоящий из одних нулей, указывает на отсутствие ошибки и соответствует нулевому вектору ошибки.
Предположим, что в процессе передачи или хранения в результате воздействия внешних факторов оказался искаженным отдельный разряд кодового слова. Например, вместо слова 1101001 было принято слово 1001001. В этом случае синдром окажется отличным от нуля: s0…s2 будет соответственно равен: $$s_0 = 1 \oplus 1 \oplus 0 \oplus 1 = 1, s_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0, s_2 = 0 \oplus 1 \oplus 0 \oplus 0 = 1$$ Синдром 101 соответствует вектору ошибки 0100000, при этом единица указывает на разряд, в котором эта ошибка произошла. Для ее коррекции достаточно сложить по модулю 2 принятое искаженное кодовое слово с вектором ошибки.
Рассчитаем избыточность (7,4) -
Это очень большое значение. На практике часто применяются существенно более сложные коды, обеспечивающие лучшие характеристики помехоустойчивости при меньшей избыточности.
Как было сказано выше, одной из важных задач предварительной подготовки данных к шифрованию является уменьшение их избыточности и выравнивание статистических закономерностей применяемого языка. Частичное устранение избыточности достигается путём сжатия данных.
Сжатие информации представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения. Алгоритмы, предназначенные для сжатия информации, можно разделить на две большие группы: реализующие сжатие без потерь (обратимое сжатие) и реализующие сжатие с потерями (необратимое сжатие).
Обратимое сжатие подразумевает абсолютно точное восстановление данных после декодирования и может применяться для сжатия любой информации. Оно всегда приводит к снижению объема выходного потока информации без изменения его информативности, то есть без потери информационной структуры. Более того, из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной, а процесс восстановления называется декомпрессией или распаковкой и только после процесса распаковки данные пригодны для обработки в соответствии с их внутренним форматом. Сжатие без потерь применяется для текстов, исполняемых файлов, высококачественного звука и графики.
Необратимое сжатие имеет обычно гораздо более высокую степень сжатия, чем кодирование без потерь, но допускает некоторые отклонения декодированных данных от исходных. На практике существует широкий круг практических задач, в которых соблюдение требования точного восстановления исходной информации после декомпрессии не является обязательным. Это, в частности, относится к сжатию мультимедийной информации: звука, фото- или видеоизображений. Так, например, широко применяются форматы мультимедийной информации JPEG и MPEG, в которых используется необратимое сжатие. Необратимое сжатие обычно не используется совместно с криптографическим шифрованием, так как основным требованием к криптосистеме является идентичность расшифрованных данных исходным. Однако при использовании мультимедиа-технологий данные, представленные в цифровом виде, часто подвергаются необратимой компрессии перед подачей в криптографическую систему для шифрования. После передачи информации потребителю и расшифрования мультимедиа-файлы используются в сжатом виде (то есть не восстанавливаются).
Рассмотрим подробнее некоторые из наиболее распространённых способов обратимого сжатия данных.
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем – это кодирование серий последовательностей (Run
При равномерном кодировании информации на сообщение отводится одно и то же число бит, независимо от вероятности его появления. Вместе с тем логично предположить, что общая длина передаваемых сообщений уменьшится, если часто встречающиеся сообщения кодировать короткими кодовыми словами, а редко встречающиеся – более длинными. Возникающие при этом проблемы связаны с необходимостью использования кодов с переменной длиной кодового слова. Существует множество подходов к построению подобных кодов.
Одними из широко используемых на практике являются словарные методы, к основным представителям которых относятся алгоритмы семейства Зива и Лемпела. Их основная идея заключается в том, что фрагменты входного потока ("фразы") заменяются указателем на то место, где они в тексте уже ранее появлялись. В литературе подобные алгоритмы обозначаются как алгоритмы LZ сжатия.
Подобный метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, так как они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов. Декодирование сжатого текста осуществляется напрямую, – происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа декодера.
Другим подходом к сжатию информации является код Хаффмана, кодер и декодер которого имеют достаточно простую аппаратную реализацию. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды, тогда как реже встречающимся символам – более длинные. За счет этого достигается сокращение средней длины кодового слова и большая эффективность сжатия. Коды Хаффмана имеют уникальный префикс (начало кодового слова), что и позволяет однозначно их декодировать, несмотря на их переменную длину.
Процедура синтеза классического кода Хаффмана предполагает наличие априорной информации о статистических характеристиках источника сообщений. Иначе говоря, разработчику должны быть известны вероятности возникновения тех или иных символов, из которых образуются сообщения. Рассмотрим синтез кода Хаффмана на простом примере.
Пусть источник информации способен генерировать четыре различных символа , а).
Процедура синтеза кода состоит из трех основных этапов. На первом происходит свертка строк таблицы: две строки, соответствующие символам с наименьшими вероятностями возникновения заменяются одной с суммарной вероятностью, после чего таблица вновь переупорядочивается. Свертка продолжается до тех пор, пока в таблице не останется лишь одна строка с суммарной вероятностью, равной единице (рис 14.3, б).
(рис 14.3) Первый этап кодирования ХаффманаНа втором этапе осуществляется построение кодового дерева по свернутой таблице (рис 14.4, а). Дерево строится, начиная с последнего столбца таблицы.
(рис 14.4) Второй этап кодирования ХаффманаКорень дерева образует единица, расположенная в последнем столбце. В рассматриваемом примере эта единица образуется из вероятностей 0,55 и 0,45, изображаемых в виде двух узлов дерева, связанных с корнем. Первый из них соответствует символу S3 и, таким образом, дальнейшее ветвление этого узла не происходит.
Второй узел, маркированный вероятностью 0,45, соединяется с двумя узлами третьего уровня, с вероятностями 0,25 и 0,2. Вероятность 0,2 соответствует символу S1, а вероятность 0,25, в свою очередь, образуется из вероятностей 0,15 появления символа S2 и 0,1 появления символа S4.
Ребра, соединяющие отдельные узлы кодового дерева, нумеруются цифрами , б).
Однако классический алгоритм Хаффмана имеет один существенный недостаток. Для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения.
Другой вариант статического кодирования Хаффмана заключается в просмотре входного потока и построении кодирования на основании собранной статистики. При этом требуется два прохода по файлу – один для просмотра и сбора статистической информации, второй – для кодирования. В статическом кодировании Хаффмана входным символам (цепочкам битов различной длины) ставятся в соответствие цепочки битов также переменной длины – их коды. Длина кода каждого символа берется пропорциональной двоичному логарифму его частоты, взятому с обратным знаком. А общий набор всех встретившихся различных символов составляет алфавит потока.
Существует другой метод – адаптивного или динамического кодирования Хаффмана. Его общий принцип состоит в том, чтобы менять схему кодирования в зависимости от характера изменений входного потока. Такой подход имеет однопроходный алгоритм и не требует сохранения информации об использованном кодировании в явном виде. Адаптивное кодирование может дать большую степень сжатия, по сравнению со статическим, поскольку более полно учитываются изменения частот входного потока. При использовании адаптивного кодирования Хаффмана усложнение алгоритма состоит в необходимости постоянной корректировки дерева и кодов символов основного алфавита в соответствии с изменяющейся статистикой входного потока.
Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество сжатия. Однако кодирование Хаффмана имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит – {0, 1}. Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит.
Совершенно иное решение предлагает арифметическое кодирование. Этот метод основан на идее преобразования входного потока в одно число с плавающей запятой. Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов.
Предполагаемая требуемая последовательность символов при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке.
Рассмотренные методы обеспечивают обратимое сжатие данных. На практике применяются как программные, так и аппаратные их реализации, позволяющие добиваться коэффициентов сжатия порядка 20-40% в зависимости от типа сжимаемой информации.
Таким образом, криптографическое шифрование, помехоустойчивое кодирование и сжатие отчасти дополняют друг друга и их комплексное использование помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
Избыточность – характеристика
Код – совокупность знаков, а также система правил, позволяющая представлять информацию в виде набора таких знаков.
Кодовое слово – любой ряд допустимых знаков в соответствии с используемой системой правил.
Минимальное кодовое расстояние – наименьшее из всех расстояний по Хэммингу для любых пар различных кодовых слов, образующих код.
Помехоустойчивый код – код, позволяющий обнаруживать и корректировать ошибки при хранении и передаче сообщений.
Расстояние по Хэммингу – число разрядов кодовых слов, в которых они различны.
Сжатие информации – процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения.
Соседние кодовые слова – кодовые слова, отличающиеся значением только одного разряда.
В теории информации выделяют три вида преобразования информации: криптографическое шифрование, помехоустойчивое кодирование и сжатие (или эффективное кодирование). Общим для всех трех видов преобразования является то, что информация каким-либо образом меняет форму представления, но не смысл. Отличия разных видов кодирования связаны с целью проводимых преобразований.
Так, целью криптографического преобразования является, как известно, защита от несанкционированного доступа, аутентификация и защита от преднамеренных изменений. Помехоустойчивое кодирование выполняется с целью защиты информации от случайных помех при передаче и хранении. Для этого при записи и передаче в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
Эффективное кодирование (или сжатие информации) представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения. Алгоритмы сжатия информации делятся на две группы: алгоритмы сжатия без потерь (обратимого сжатия) и алгоритмы сжатия с потерями (необратимого сжатия). За счет эффективного кодирования уменьшается избыточность сообщений, что позволяет производить более надежное криптографическое шифрование информации.
Таким образом, криптографическое шифрование, помехоустойчивое кодирование и сжатие отчасти дополняют друг друга и их комплексное использование помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
8 бит. Его избыточность равна 25%. Чему равно число информационных разрядов в нем?S1…S4 с вероятностями возникновения p(S1)=0,1, p(S2)=0,3, p(S3)=0,5, p(S4)=0,1. По этим данным выполните синтез классического кода Хаффмана.В данном курсе были рассмотрены наиболее распространенные в настоящее время методы криптографической защиты информации. Но криптографическая наука, как и любая другая наука, не стоит на месте, а продолжает развиваться. Не прекращаются усилия специалистов по созданию новых методов криптографической защиты информации.
Новая "отрасль" криптографии – асимметричная криптография стала всем уже привычной. Несмотря на то, что открыто уже более десятка алгоритмов шифрования с открытым ключом, продолжается поиск новых методов асимметричного шифрования. Так, например, алгоритмы на эллиптических кривых были предложены учеными только в самом конце ХХ века, а в настоящее время они уже активно используются на практике.
Другая сравнительно молодая ветвь криптографии – исследование криптографических протоколов. Несмотря на то, что первые протоколы появились во второй половине ХХ века, на настоящий момент имеется уже несколько десятков различных типов криптографических протоколов. Криптографические протоколы являются одним из основных объектов исследования теоретической криптографии. Ежегодно специалистами предлагаются новые криптографические протоколы, и задача криптоаналитиков заключается в том, чтобы верно оценить надежность каждого из протоколов.
Одной из относительно новых разработок криптографии является квантовая криптография, основанная на определенных явлениях квантовой физики. Информацию в квантовых системах предлагается передавать по оптоволоконным каналам с помощью квантов света – фотонов, меняющих свое состояние при попытке их перехватить и измерить. Утверждается, что, используя квантовые явления, можно спроектировать и создать такую систему связи, которая всегда сможет обнаруживать подслушивание. Практическая реализация квантовой криптографии пока что находится на самом начальном уровне и встречает множество трудностей.
Таким образом, криптографические методы не прекращают развиваться. Они широко используются и будут использоваться в составе средств комплексной защиты информации.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.