Содержание к диссертации
Введение
Глава 1. Анализ методов передачи конфиденциальных сообщений по открытым каналам 5
1.1. Требования к конфиденциальной связи 5
1.2. Модели каналов связи с перехватом 9
1.3. Двоичное вероятностное кодирование 20
1.4. Декодирование в синдромном канале 28
1.5. Оценки неопределенности у перехватчика 45
Глава 2. Анализ методов декодирования в каналах с шумом 56
2.1. Свойства конечных полей 56
2.2. Представление кодов БЧХ 60
2.3. Коды Рида-Соломона 66
2.4. Синдромное декодирование кодов Рида-Соломона 69
2-5. Методы исправления ошибок и стираний в кодах Рида-Соломона 82
2.6. "Мягкое" декодирование кодов Рида-Соломона 86
Глава 3. Метод защищенной передачи информации на основе кодового зашумления 93
3.1. Метод кодового зашумления на базе кодов Рида-Соломона 93
3 2 Восстановление информационных символов в синдромном канале
Глава 4. Оценка качества передачи информации в каналах с перехватом
4.1. Основные параметры системы
4.2. Оценка вероятности успешного перехвата
Заключение 146
Список литературы 147
- Модели каналов связи с перехватом
- Синдромное декодирование кодов Рида-Соломона
- Восстановление информационных символов в синдромном канале
- Оценка вероятности успешного перехвата
Введение к работе
В настоящее время средства вычислительной техники и сети связи получили столь широкое распространение и столь нужны во всех сферах народного хозяйства, что отказаться от их использования оказывается совершенно невозможно, хотя более 80 % компаний и агентств несут убытки из-за различных нарушений целостности данных. Поэтому проблема защиты информации практически во всех вычислительных системах и системах связи стала весьма актуальна. Само понятие защиты информации является весьма многогранным. Оно включает в себя по крайней мере три аспекта: защиту от получения информации противником» защиту от изменения информации и защиту от разрушения информации незаконным пользователем, В этой диссертации рассматриваются некоторые аспекты защиты от перехвата информации противником.
Дело в том, что работа средств вычислительной техники и связи сопровождается электромагнитными излучениями и наводками на различные радиотехнические цепи. Перехват сигналов наводок и излучений открывает противнику доступ к информации, циркулирующей в информационно-вычислительных сетях. Каналы утечки информации такого вида составляют основу математических моделей каналов с перехватом, исследуемых в этой работе.
Для защиты информации от утечки по каналам наводок и электромагнитных излучений используются различные способы. Среди них полная изоляция всех технических средств от возможного перехвата территориально и с помощью специальных экранов и фильтров, использование методов шифрования, использование зашумления электромагнитных излучений специальными генераторами сопровождающего шума и т.п. Все эти способы требуют дополнительных и значительных затрат различных ресурсов, что обходится примерно в 4-5 раз дороже, чем установка и эксплуатация вычислительных средств без специальных средств защиты.
Однако имеется другой подход к этой проблеме, основанный на достижениях современной теории информации и кодирования, позволяющий переда-
4 вать конфиденциальные сообщения по открытым каналам без опасности их
компрометации. Этот подход был предложен А. Вайнером и развит во многих исследованиях. В нашей стране большой вклад в решение этой проблемы внесли известные ученые Коржик В.И., Яковлев В.А. и другие.
При рассматриваемом подходе защита информации обеспечивается не за счет воздействия на параметры каналов утечки, а за счет вероятностного преобразования информации перед передачей по каналу связи. Невозможность восстановления информации противником основана на том свойстве, что канал утечки имеет меньшую пропускную способность, чем канал законного пользователя. Способ кодирования выбирается так, чтобы в канале утечки количество возникающих ошибок сильно возрастало, обеспечивая эффект зашумления передаваемого сигнала, в то время как в основном канале обеспечивалась надежная связь.
Таким образом, в настоящее время задача передачи конфиденциальных сообщений по открытым системам и сетям связи, не использующая каких-либо методов шифрования, для которых необходима служба генерации и распределения ключей между законными пользователями, является актуальной и перспективной для исследователей.
Модели каналов связи с перехватом
Прежде перехода к рассмотрению модели канала с перехватом рассмотрим основные теоретико-информационные понятия об измерении секретности. В нашей ситуации легитимный передатчик хочет передать некоторое сообщение Л/ легитимному приемнику. Противник подслушивает передачу по каналу и таким образом получает некоторое измерение или наблюдаемую величину К Предполагается, что противнику известны только частичные сведения о связи между М и К. Чтобы формализовать эти знания, сообщение М и наблюдение Y рассматриваются как случайные переменные, принимающие значения из некоторых множеств Миї, соответственно. Эти случайные переменные связаны условным распределением Ру\м(У\&0- Здесь предполагается, что условное распределение Р імЛ М находится под частичным контролем легитимных пользователей. Их цель заключается в том чтобы задача вычисления оценки сообщения Миз переменной-наблюдения Убыла трудной.
Теоретически замечательный способ обеспечения секретности заключается в таком проектировании системы передачи, чтобы при любом Y имелось много различных сообщений М таких, что вероятности РМ\ч (М\ У) при выбранном Убыли достаточно велики. С точки зрения перехватчика это означает, что многие сообщения оказываются высоковероятными, так как достаточно велики их апостериорные вероятности. Как следствие, перехватчик не может выбрать одну оценку сообщения с высокой вероятностью, то есть не может указать точное сообщение.
Теоретическое обоснование рассмотренного способа построения крипто-системы было выполнено К-Шенноном [4] в терминах теории информации. Это обоснование совершенно надежной системы определяется условием
Это условие означает, что у совершенно надежной криптосистемы апостериорное и априорное распределения вероятностей на множестве сообщений М просто совпадают. Другими словами, противник может выбрать вариант сообщения хоть до получения криптограммы, хоть после получения ее, ничего не выигрывая от наблюдения переменной У. В качестве меры неопределенности Шеннон использовал энтропию, которая для случая переменной М (сообщений) определяется формулой где логарифм взят по основанию два. Условная энтропия (оставшаяся неопределенность) относительно М после получения противником наблюдения Уесть
Хорошо известное свойство условной энтропии Н(М Т) заключается в том, что условная энтропия всегда меньше безусловной и может быть равна безусловной Н(М) тогда и только тогда, когда случайные величины М и У являются статистически независимыми. Но условие (1,2.1) и есть формальное определение статистической независимости случайных переменных М и У Отсюда получаем, что равенство является необходимым и достаточным условием, чтобы криптографическая система была совершенно надежной. словная энтропия II(M F) может быть использована для вычисления нижней границы вероятности ошибки при оценке любого сообщения, которое перехватчик может выполнить. Предположим, что отображение g: У— М используется для того, чтобы находить оценку сообщения M = q(Y) по принятому наблюдению У. Тогда вероятность ошибки Р[е) = Р(М МJ, то есть вероят ность того, что оценка сообщения М перехватчиком не совпадает с переданным сообщением М, удовлетворяет известному неравенству Фано [12]
Отметим еще раз, что использование условной энтропии как меры секретности означает, что секретность рассматривается как одновременное существование многих обоснованных возможностей декодирования (то есть многих правдоподобных сообщений) при заданном наблюдении Y. Таким образом, секретность может быть увеличена за счет использования кодирования, при котором число существующих одновременно обоснованных возможностей для сообщений возрастает.
Для упрощения дальнейшего рассмотрения сосредоточим свое внимание на случае двоичного канала с перехватом. Такой канал показан на рис, 2,1. На этом рисунке предполагается, что источник информации и каналы заданы, а проектировщик может выбирать любые кодирующие и декодирующие устройства, которые позволяют решить рассматриваемую задачу.
Синдромное декодирование кодов Рида-Соломона
Как хорошо известно, что проектирование любой технической системы, в том числе и системы связи, заключается в том, чтобы обеспечить требования будущих пользователей системы. Обычно пользователи системы связи требуют, чтобы скорость передачи, измеряемая в двоичных единицах в секунду (или килобитах в секунду), была достаточно большой для решения задач пользователя. Вторым требованием является надежность передачи. Надежность передачи информации обычно измеряется вероятностью ошибки на один передаваемый символ или на блок символов, составляющих кодовое слово. Требуемая вероятность ошибки обычно весьма мала и составляет величину порядка 10-10 на передаваемый символ. На третьем месте обычно стоит стоимость системы связи. В настоящее время требования к системам связи продолжают ужесточаться, причем часто основным требованием является требование обеспечение секретности передачи. Другими словами, помимо высокой скорости передачи и высокой надежности требуется обеспечить получение информации только легитимными приемниками. Нелегитимные приемники рассматриваются как подслушивающие приемники или приемники-перехватчики. Эти приемники, при любой их технической оснащенности, не должны иметь возможности получить полезную информацию о передаваемых сообщениях между легитимными передатчиком и приемником.
В двухточечной схеме, когда передатчик и приемник связаны физическим каналом, имеется несколько вариантов защиты информации от приемников-перехватчиков. Наиболее надежный вариант, но и наиболее дорогой, заключается в полной изоляции физического канала от внешнего мира, то есть таким образом, чтобы приемники-перехватчики не имели возможности получить какую-либо информацию о передаваемых сообщениях. Более слабый уровень защиты физического канала предполагает, что приемники-перехватчики имеют некоторый частичный доступ к физическому каналу легитимных абонентов, но они всегда получают искаженную версию сигналов или только частичную информацию о сигналах» передаваемых по этому каналу. Наконец, можно предположить ситуацию, ко гда физический канала полностью открыт и любой приемник может иметь полный доступ к передаваемым сообщениям. В этой и предыдущей ситуациях защищать информацию приходиться криптографическими методами.
Еще более сложное положение пользователей, работающих в некоторой общей сети связи. В этом случае предположение о том, что между какими-то двумя пользователями можно образовать защищенный канал кажется вообще нереалистичным. Поэтому в сетях передачи информации можно получить защищенную передачу сообщения между двумя пользователями только криптографическими методами. Для защиты информации в перечисленных ситуациях и во многих других используются криптографические системы. Основной задачей такой криптографической системы является преобразование исходного сообщения в криптотекст. который и передается по каналу связи. На приемной стороне выполняется инверсия этого преобразования для получения из крипто-текста исходного сообщения. Чтобы перехватчик не мог подслушать и восстановить сообщение даже при получении криптотекста необходимо держать операцию дешифрации в большом секрете.
Фактически имеется большое семейство шифрующих и дешифрующих отображений, каждое из которых определяется одним параметром, называемым ключом шифрации-дешифрации. Секретность криптосистемы основана на секретности ключа, а также не предположении, что не существует эффективной процедуры для определения переданного сообщения без знания этого секретного ключа. В традиционных симметричных системах ключи для шифрования и дешифрования являются одинаковыми. Это делает необходимым доставлять ключи каждой паре пользователей некоторым надежным способом, например с помощью доверенного курьера. Кроме того, для каждой пары пользователей должен быть свой общий секретный ключ. Генерация, доставка и хранение большого количества секретных ключей представляет довольно сложную проблему, которая называется проблемой управления ключами. Эта проблема требует значительных затрат различных ресурсов для своего решения и поэтому находит практическое применение только в особо важных случаях.
В качестве альтернативы можно использовать криптографические системы с открытым ключом. В этом случае у каждого пользователя имеется два разных ключа — шифрующий и дешифрующий. Шифрующий ключ является несекретным и известен всем пользователям сети и любому перехватчику. Однако, для дешифрации криптотекста необходим дешифрующий ключ, который является секретным. Вычисление этого ключа является весьма сложной задачей, которая, конечно, может быть решена при наличии у перехватчика достаточных вычислительных ресурсов и времени- Следует отметить, что современное развитие теории алгоритмов и методов криптографии с открытым ключом не позволяют количественно оценить вычислительную сложность задачи вычисления шифрующего ключа, а значит и надежность такого способа криптографической защиты.
Совсем другой подход к проблеме обеспечения секретности при передачи сообщений по незащищенному каналу был предложен Вайнером [1] и развит в дальнейших работах [2]. В своей работе Вайнер считал, что перехватчик всегда имеет доступ только к деградированной версии сигнала, передаваемого по основному каналу между легитимными пользователями. Это предположение дает легальным пользователям некоторое информационное преимущество, которое может быть использовано, чтобы обеспечить необходимую секретность передачи вместо использования любых секретных ключей,
В модели канала с перехватом мы имеем единственного отправителя и многих получателей- Модель канала с шумом для этой ситуации была ранее описана, как модель широковещательного канала [1]. В этой модели цель заключалась в передаче информации ко всем приемникам с максимально возможными скоростями передачи. В модели канала с перехватом, введенной Вайнером, ситуация аналогична, но цель системы полностью отличается- Здесь необходимо достичь высокой скорости передачи от отправителя к легитимному получателю, в то время как другие приемники могут получать передаваемую информацию с очень незначительной скоростью передачи.
Восстановление информационных символов в синдромном канале
Как было отмечено ранее, цель кодирования сообщений для канала с перехватчиком заключается в том, чтобы перехватчик получил как можно меньше информации о передаваемых сообщениях. По предположению канал перехватчика хуже, чем основной канал, который предполагается свободным от каких-либо искажений. Поэтому кодирование должно обеспечить эффективное использование тех искажений, которые имеют место в канале перехватчика. Как уже указывалось, канал перехватчика является двоичным симметричным каналом, у которого переходная вероятность для ошибочной передачи равна є. Это означает, что при использовании кодовых слов длины п в среднем около пг символов в кодовом слове будут ошибочны. Другими словами, перехватчик получив некоторую последовательность v символов длины п из своего канала может быть уверен с большой вероятностью, что переданная по основному каналу кодовое слово находится в сфере радиуса n-z с центром в принятой последовательности V Исходя из этой модели канала с перехватом можно рассмотреть несколько возможных сценариев кодирования с тем, чтобы представить наиболее подходящее требования к используемому блоковому коду.
Если предположить, что используются методы помехоустойчивого кодирования, при которых все возможные кодовые слова разнесены друг от друга на значительное расстояние Хэмминга, то в сферу радиуса л-є вокруг принятой последовательности v попадет незначительное число возможных кодовых слов.
Перехватчик проанализирует каждое из них и тем самым получит значительную информацию о передаваемых сообщениях по основному каналу.
Возможен сценарий, при котором все используемые кодовые слова отличаются друг от друга незначительно в смысле расстояния Хэмминга. В результате в указанную сферу радиуса пв попадет много возможных кодовых слов. Перехватчик должен проанализировать каждое из полученных кодовых слов и выбрать подходящее. В этом сценарии положение перехватчика много хуже, чем в первом случае, так как подходящих для выбора возможностей намного больше. Однако, и в этом случае перехватчик получает много полезной информации, так как все те кодовые слова, которые не попали в сферу указанного радиуса могут быть сброшены перехватчиком и исключены из рассмотрения.
Таким образом, наилучшая стратегия борьбы с перехватом информации заключается в том, чтобы в сфере радиуса wz вокруг принятой последовательности v были представлены все возможные сообщения основного канала, В этом случае перехватчику необходимо выбрать одно из них, что представляется малореальным делом, если сообщений много, а длина сообщений п достаточно велика. Последний сценарий может быть реализован при условии, что каждое сообщение будет представлено многими кодовыми словами, а операция кодирования будет носить стохастический характер. Другими словами, каждому сообщению будет сопоставляться довольно большое множество кодовых слов, а для передачи по каналу связи будет выбираться из этого множества одно какое-либо кодовое слово случайным образом. Именно эту стратегию кодирования предпочитают во многих работах [].
Сформулируем основные требования к сценарию блокового кодирования в соответствии с предыдущим рассмотрением. Эти требования включают следущее. 1. Перехватчик должен иметь очень большое количество возможных выборов сообщений, то есть длина передаваемых сообщений п должна быть столь большой, чтобы сфера радиуса п-в вокруг принятой приемником последовательности содержала все возможные кодовые слова. 2. Кодовая скорость передачи информации должна быть достаточно низкой, чтобы предотвратить утечку информации от легальных пользователей к перехватчику. 3. Все точки сферы радиуса п-г вокруг любой полученной перехватчиком последовательности должны включать всевозможные передаваемые сообщения. Это может быть достигнуто представлением каждого сообщения многими кодовыми словами и использованием стохастического кодирования. Перейдем к рассмотрению указанного способа блокового кодирования. Обозначим через F конечное поле с двумя элементами GF(2). Блок двоичных символов длины п будем рассматривать как векторы из арифметического пространства F1 [], Любой линейный код (п, к)-код С является Л-мерным подпространством пространства F . Проверочная матрица такого кода имеет вид где r = n-k дает число линейно независимых строк матрицы Н. Любой вектор из линейного кода С удовлетворяет равенству X Н = 0, где символ Тобозначает транспортирование матрицы Н, а О-вектор из всех нулей. Таким образом, линейный код {п7 &)-код С есть множество векторов, удовлетворяющих условию Если х произвольный вектор из F 1 (необязательно кодовое слово), то произве дение хН называется синдромом вектора х. Указанное произведение сопоставляет каждому вектору х из F" свой r-разрядный синдром. Если код С является хорошим корректирующим кодом, то есть кодом имеющим большое минимальное расстояние Хэмминга между каждой парой кодовых слов, то векторы из Р 9 являющиеся близким друг к другу в смысле расстояния Хэмминга, отображаются в различные синдромы. Это свойство хорошо корректирующих кодов показывает, что целесообразным способом кодирования сигналов для каналов с перехватом является использование синдромов передаваемых векторов как носителей информации.
Теперь предположим, что сообщениями являются блоки двоичных символов длины г, которые можно рассматривать как элементы векторного пространства F . Тогда каждое такое сообщение т можно представить любым вектором из смежного класса Ст разложения векторного пространства Г" по линейному коду С, который имеет синдром т, то есть где Н — проверочная матрица используемого линейного кода С. Кодирующее устройство, имеющее на входе сообщение ш, случайным образом выбирает вектор из смежного класса Ст и передает его по основному каналу связи- Распределение вероятностей на элементах смежного класса Ст предполагается равномерным. Другими словами, стохастическое кодирующее устройство имеет при передаче сообщений т распределение вероятностей на выходе Здесь через к обозначено число информационных символов кода С. В частности, смежный класс Со, соответствующий сообщению из г нулевых символов, является самим кодом С Можно отметить, что при таком способе кодирования вес векторы из множества F1 являются кодовыми словами с равномерным распределением вероятностей, если распределение вероятностей на множестве сообщений является равномерным, то есть Рм(т) = 2- Действительно, Стохастический кодер, таким образом, можно представить как некоторое устройство, которое по передаваемому сообщению т генерирует случайный век тор из смежного класса Ст, входящего в разложение всего векторного пространства F по линейному коду С.
Оценка вероятности успешного перехвата
В этом разделе ограничимся рассмотрением методов исправления ошибок в принятом кодовом слове кода Рида-Соломона, основанных на вычислении синдрома. Предположим, что некоторое кодовое слово с{х) кода Рида-Соломона с параметрами (я, к) передано по каналу с шумом. Принятый на приемной стороне полином может быть представлен как где полином {X) = "_7Q X представляет полином ошибок. Коэффициенты еіч і = 0, 1, „., п - 1, являются элементами поля GF(2m) и обозначают величину ошибки на /-той позиции, если et Ф 0. Предположим, что в принятом полиноме h(x) имеется / ошибок, где 0 2t (n-k\ на позициях ij9j—l, I, „., L Полином ошибок е(х) имеет только t ненулевых коэффициентов и может быть записан как Задачей декодера кода Рида-Соломона является определение числа ошибок, нахождение ошибочных позиций в кодовом слове ij и вычисление значения ошибки на ошибочной ПОЗИЦИИ в; . Вычислим значения принятого полинома Ь{х) в тех точках, в которых переменная х принимает значения, равные корням генераторного полинома фс\ то есть при і = 0, 1, .,., (п-к— 1). Эти (п — к) величин принято называть синдромами (признаками ошибок) и обозначать символами s\+h где (=0, 1, ,.,, (п-к— 1).
Используя соотношения (2.4.1) и (2.4.2) синдромы можно представить как где і пробегает значения 0, 1, „., (п-к-\). Для удобства принято обозначать величину ошибки eh через Yj и локатор ошибки (расположение ошибки в кодовом слове) a через X/ для всех у = 1, 2,...? t. Тогда синдромы могут быть записаны в терминах величин и локаторов ошибок В качестве примера рассмотрим случай п — к = 2. Этот код способен корректировать одну ошибку. Двумя синдромами являются величины S\ и s2. Если оба синдрома равны нулю, то утверждается, что ошибок в канале при передаче слова с(х) не произошло и принятая последовательность является безошибочным кодовым словом- Если оба синдрома s\ и j2 не нули, то предпо лагается, что произошла одиночная ошибка и уравнения для синдромов имеют вид si = Y\X\ HS2= Y\X\2. Решая эти уравнения, можно получить значение локатора ошибки Х\ = S2/S] и значение величины ошибки Y\ =S\IX\. Отметим, что синдромные уравнения представляют нелинейные соотношения между S\+h Yj, Xj. При {n-k) 2 решение этой системы нелинейных уравнений является трудной задачей и ее лучше избежать. Действительно, возможно ттреобразовать нелинейные синдромные уравнения в линейные уравнения, введя полином локаторов А(У), как показано в ряде работ[26]. Локаторный полином А(х) определяется как полином степени t, который имеет в качестве корней обратные значения локаторов ошибок Xj,j = 1, 2, ..., /, то есть Умножив обе части равенства (2А4) на множитель YjXf для I uj t и О / {п — к— (- 1), можно получить равенства Теперь подставим x + Xf] в обе части равенств (2.4.5), где Х[х — корни локаторного полинома А(х). В результате получим следующую систему уравнений где параметры j и і пробегают следующие значения lujut и 0 i (n-k - 1). Зафиксируем некоторое значение / из заданного диапазона и просуммируем эти уравнения по переменной j. Тогда получим Сравнивая суммы по переменной у в выражении (2,4.7) и определение синдромов (2.4.3), получаем
Система уравнений (2.4.8) является совместной системой линейных уравнений с / неизвестными коэффициентами локаторного полинома Л, и (п -к) известными значениями синдромов Si. Если число / действительно произошедших ошибок известно, то достаточно составить подмножество t линейных уравнений, представленных в следующей матричной форме t, могут быть найдены обращением квадратной матрицы, составленой из синдромов, К сожалению, количество ошибок в принятом полиноме Ь(х) неизвестно и, следовательно, размер системы линейных уравнений (2.4.9) не известен. Поэтому предварительно надо вычислить число действительно искаженных символов в принятой последовательности. И эти вычисления являются частью процесса декодирования, В работе [22] дан так называемый прямой метод декодирования. В соответствии с этим методом сначала предполагается, что в принятом полиноме произошло максимально возможное число ошибок. Затем вычисляется детерминант матрицы, составленной из синдромов. Если детерминант не равен нулю, то инвертируя матрицу в системе уравнений (2.4.9) находим все коэффициенты локаторного полинома. Если же детерминант равен нулю, то выбираем квадратную подматрицу в левом верхнем углу, размер которой меньше предыдущей матрицы на единицу.
Вычисляем детерминант этой подматрицы- Если он также равен нулю, то снова уменьшаем размер квадратной подматрицы на единицу. Продолжаем этот процесс до тех пор, пока детерминант квадратной подматрицы в левом верхнем углу исходной матрицы не будет отличен от нуля. В этом случае размер подматрицы с ненулевым детерминантом дает количество ошибок, действительно произошедших в канале связи при передаче рассматриваемого кодового слова. Это число ошибок обозначено выше через t. Теперь, используя (2,4.9), получим коэффициенты локаторного полинома Л,, 1=1,2, ..., Л В качестве примера рассмотрим код Рида-Соломона с параметрами (7,3) над полем QF{2 ). Этот код имеет минимальное кодовое расстояние d= 5» то есть исправляет любые две ошибки. Предположим, что передавалось кодовое слово из всех нулей, а принятая последовательность Ь(х) = сед: , Значения синдромов вычисляются следующим образом
