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

На правах рукописи

САВЕЛЬЕВ Максим Феликсович

»

МЕТОД ЗАЩИЩЕННОЙ ПЕРЕДАЧИ ИНФОРМАЦИИ НА ОСНОВЕ КОДОВОГО ЗАШУМЛЕНИЯ

Специальность: 05.13.19 - «Методы и системы защиты информации, информационная безопасность»

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2003 г.

Работа выполнена на кафедре «Информационная безопасность компьютерных систем» Санкт-Петербургского государственного политехнического университета.

Научный руководитель:

Доктор технических наук, профессор, Зегжда Петр Дмитриевич

Официальные оппоненты:

Доктор технических наук, профессор Мирончиков Евгений Тимофеевич

Кандидат технических наук, с.н.с. Егоров Владимир Викторович

Ведущая организация:

Санкт-Петербургский государственный университет телекоммуникаций (СПбГУТ).

Защита состоится июня 2003 г. в

часов на заседании

диссертационного совета Д212.229.27 в Санкт-Петербургском государственном политехническом университете по адресу: 195251, Политехническая ул., д.29, Главное здание, ауд. 118.

С диссертационной работой можно ознакомиться в Фундаментальной библиотеке Санкт-Петербургского государственного политехнического университета

Автореферат разослан мая 2003 г.

Ученый секретарь диссертационного совета

Платонов В. В.

Общая характеристика работы

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

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

Диссертационная работа базируется на трудах Яковлева В А, Мирончикова Е.Т.,

Коржика В И. и других и посвящена задаче разработки метода передачи

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

Принципиальным преимуществом метода кодового зашумления является совершенная

секретность в теоретико-информационном смысле, что позволяет использовать данный

г~ - ------- :

метод при любых предположениях о вычисщ ехватчика.

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

л

при передаче по открытым каналам.

Для достижения поставленной цели в работе решались следующие задачи:

1. Построение и исследование математической модели системы передачи конфиденциальных сообщений по незащищенным каналам связи с перехватом

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

3. Разработка алгоритмов вероятностного кодирования и декодирования, включая быстрые алгоритмы восстановления сообщений из принятых синдромов-сообщений.

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

5. Разработка рекомендаций по применению предложенного метода кодового зашумления.

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

Научная новизна диссертационной работы состоит в следующем:

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

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

3. Разработана система передачи конфиденциальных сообщений по открытому каналу с шумом при наличии перехватчика.

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

Практическая ценность работы подтверждается возможностью использования полученных результатов для систем передачи конфиденциальных сообщений и актами о внедрении полученных результатов в части передачи конфиденциальных сообщений по открытым каналам с кодовым зашумлением от ЦНИИ РТК и Московского Федерального

государственного предприятия Аттестационный центр "Желдоринформзащита МПС РФ", в учебном процессе СПбГУТ. На основе результатов диссертационной работы были разработаны учебно-методические материалы, используемые для подготовки специалистов на кафедре «Информационная безопасность компьютерных систем» СПбГПУ.

Основные положения, выносимые на защиту:

1. Метод кодового зашумления на основе использования кодов Рида-Соломона для вычислительных и телекоммуникационных систем и сетей связи, в которых все используемые каналы, включая каналы перехватчика, являются каналами с шумом.

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

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

4. .Методика расчета оценки вероятности успешного перехвата правильного сообщения противником и оценки достоверности доведения сообщения получателю по основному каналу..

Публикации. По теме диссертации опубликовано 9 научных статей и докладов.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка использованной литературы из 65 наименований.

Содержание работы

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

Рис. 1. Модель канала с перехватом.

Источник информации генерирует последовательность символов из двоичного алфавита Б = \{0,1\}. Сообщениями являются блоки двоичных символов М-(тяь тг, .., ту) е ЕР = М. Эти сообщения являются случайными величинами с равномерным распределением вероятностей

Ри(М) = 2*, М е Ок.

Оба канала (основной и перехватчика) имеют двоичные входные алфавиты и двоичные выходные алфавиты, причем входные алфавиты обоих каналов совпадают и обозначаются буквой П= {0, 1}, а выходной алфавит перехватчика буквой Ч* = {0, 1}. Кодирующее устройство отображает каждое сообщение т = = ..., тк) в некоторое

кодовое слово х = (*!, х2,..., х„), принадлежащее множеству Г2", гдек<п.

Декодер основного канала (легальный приемник) осуществляет отображение /о' П" —> вычисляя оценку /Й = /р (л:) соответствующего блока источника

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

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

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

ееС,

гдеw(e) — вес Хемминга векторае, е- вероятность ошибки в основном канале, С - код, s - синдром, п- длина кода.

Смежные классы характеризуются своими спектрами (количеством последовательностей с заданным весом Хемминга). Каждому смежному классу сопоставляется единственное сообщение и для его передачи используется любая последовательность из этого класса. Если перехватчик получает эту последовательность из канала без единой ошибки, то он прочитает сообщение, так как сможет определить номер смежного класса. Вероятность таких событий называется вероятностью успешного перехвата. В работе найдено соотношение, связывающее вероятность успешного перехвата со спектральными свойствами используемых кодов. Разработана методика выбора параметров используемого кода таким образом, чтобы вероятность успешного перехвата была сделана сколь угодно малой.

В работе рассмотрены методы вычисления вероятностей смежных классов для используемого вероятностного кодирования в канале с перехватом и некоторые схемы оптимального декодирования сообщений перехватчиком Показано, что вероятность успешного перехвата совпадает с вероятностью самого линейного кода. Эту вероятность обозначим через Р(С, в), где С - множество кодовых слов, а е - вероятность ошибки в канале. Показано, что вероятность успешного перехвата складывается из вероятности безошибочной передачи по каналу перехвата и суммы вероятностей того, что набор ошибок в этом канале совпадет с некоторым кодовым словом из кода С. Другими словами, вероятность успешного перехвата определяется выражением

Р(С,е) = (\-е)п+Р(ееС\0), где п - длина слов используемого кода.

Благодаря тому, что для величины Рш1(С,е) = Р(ееС\0) определено множество границ, в работе выведены формулы для оценки вероятности успешного перехвата.

Рассмотрены оценки меры неопределенности (нормированной условной энтропии), которую имеет перехватчик при использовании в основном канале вероятностного кодирования. Показано, что вычисление условной энтропии сообщений сводится к вычислению энтропии на множестве синдромов. Но так как распределение весов Хемминга в используемом коде, как правило, неизвестно, то приходится для этой энтропии использовать различные оценки сверху и снизу.

H(S)Z-logP(C,e)

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

Во второй главе проведен анализ выбора кодов для реализации общего метода передачи информации на основе кодового зашумления. В результате исследования функциональных зависимостей основных параметров показано, что для конструктивного метода кодового зашумления необходимо использовать достаточно "технологичные" коды, то есть такие коды, которые могут быть построены для любых значений параметров (длины кода, скорости передачи и минимального кодового расстояния Хемминга) и для которых существуют простые способы вычисления спектров. Этим условиям удовлетворяют коды Рида-Соломона, задаваемые над достаточно большими конечными полями. Поэтому для разработки метода кодового зашумления в работе использованы коды Рида-Соломона.

В работе предложено использовать код Рида-Соломона над полем СР(2т) длины л, 0 < п <= 2т - 1, с к информационными символами и минимальным кодовым расстоянием Ы = п-к+ Данные коды имеют эффективные алгоритмы исправления ошибок Построим для используемого кода порождающую и проверочную матрицы, которые обозначим через й и Н, соответственно. Порождающая матрица имеет размер к х п, а проверочная матрица имеет размер (п-к)х п.

Для построения системы передачи проведем предварительные преобразования, позволяющие представить порождающую матрицу в следующем виде:

0(р(х)) =

1 - />(*)' ... 1 ...... 1

где все элементы на главной диагонали равны единице, а в правом верхнем углу расположен полином, который имеет минимальную степень среди всех полиномов, которые могут быть получены элементарными преобразованиями матрицы. Результат таких преобразований позволяет разбить матрицу й на две части, которые будем называть ступенями кода. Тогда определим порождающую и поверочную матрицу для каждой из полученных ступеней. Для кода первой ступени порождающую матрицу обозначим через б] (она имеет размер кХл, где к\<к). Для этой порождающей матрицы находим проверочную матрицу, обозначаемую Н\. Порождающую матрицу кода второй ступени обозначим через Сз. Для этой порождающей матрицы проверочной будет проверочная матрица исходного кода Причем проверочная матрица для порождающей матрицы Сг может быть получена из матрицы Я вычеркиванием первых М столбцов. Тогда каждое сообщение от отправителя А к получателю В является линейной комбинацией строк матрицы йг, а коэффициенты этой линейной комбинации представляют собой передаваемые информационные символы.

Кодовые слова, порожденные матрицей С\, предназначены для кодового зашумления передаваемых сообщений по основному каналу связи от отправителя А к получателю В. Таким образом, к передаваемому сообщению необходимо добавлять кодовое слово кода первой ступени, выбранное в соответствии с равномерным распределением на множестве всех кодовых слов кода первой ступени. Генераторный полином кода первой ступени имеет степень (п-к\). Корни генераторного полинома

имеют вид а!1, аА +. ., ^ *, где а— примитивный элемент поля СР(2т) Этот код

имеет минимальное кодовое расстояние (1=п-к\~\. Таким образом, преобразования исходной матрицы заключаются в том, чтобы выбрать порождающую подматрицу б], генерирующую кодовые слова с минимальным расстоянием Хемминга с!-п-к\ + 1 и выше.

Если в основном канале в процессе передачи ошибок не произошло, то для того, чтобы снять кодовое зашумление, достаточно умножить принятую последовательность на проверочную матрицу Я\ кода первой ступени. Тогда сообщениями, передаваемыми по основному каналу, являются кодовые слова, принадлежащие коду второй ступени. Число

возможных различных сообщений равно Все возможные сообщения, а также

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

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

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

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

Для решения задачи выделения информационных символов вычисляется аналог псевдообратной матрицы для матрицы В, составленной из базисных векторов слова-синдрома. Чтобы преодолеть трудности вычислений псевдообратных матриц в конечных полях большой размерности, в матрице В базисных векторов размера (Ъ х с) все элементы представляются как полиномы от переменной х с коэффициентами из поля GF(2).

A,i(*) Lj(2(*) - к,Лх)

¿2,1 (*) ¿2.2 (*) - h ,ЛХ)

4,1 (*) Ьь,г{х) ••• ььАх).

Полученную матрицу обозначим Lk(x). Матрицу Lt(x) можно представить в следующей форме

Lt(x) = A(x)F(x)B(x), где А(х) и В(х) матрицы размеров (bxb) и (с х с) соответственно с единичными детерминантами, а матрица Fix) - диагональная матрица размера (Ьхс). Элементами диагональной матрицы F{x) являются полиномы. Используя это разложение, можно

найти псевдообратную матрицу Lf, = В Переходя к элементам

используемого конечного поля, из матрицы Ьк'^(х) получаем псевдообратную матрицу

В . Таким образом, операция восстановления информационных символов из принятого слова-синдрома сводится к умножению сообщения- синдрома на псевдообратную матрицу

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

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

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

Поскольку система базируется на кодах Рида-Соломона, то символы, которыми оперируют все участники рассматриваемой модели, являются элементами конечного поля ОР{2г). Поэтому для оценки вероятности успешного перехвата наибольший интерес представляет вопрос о безошибочности символов. Сама величина ошибки интереса не представляет, так как любое значение неисправленной ошибки приводит к безуспешному перехвату. Поэтому в работе рассматривается случай, когда сигнал передается без ошибок и передача происходит в основном канале с вероятностью (1 - б)г, а в канале перехвата с вероятностью (1 - Р)г, где вир соответственно вероятности ошибки на двоичный символ в основном канале и канале перехвата. Тогда вероятности того, что символы кода Рида-Соломона будут искажены, равны 1 - (1 - е/ и 1 - (1 - р)г для каждого из рассматриваемых каналов соответственно. Таким образом, несмотря на то, что значения символов кода Рида-Соломона берутся из поля СР(2"), качество передачи основного канала и возможности перехватчика определяются только двумя величинами —

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

Для увеличения различия между вероятностями ошибки на символ в основном канале и канале перехватчика законные пользователи перед посылкой сообщения должны провести дополнительные операции В соответствии с этими операциями отправитель получает от получателя случайную последовательность по основному каналу, а затем отправляет получателю поразрядную сумму передаваемого сообщения и принятой случайной последовательности по безошибочному каналу. В качестве безошибочного канала можно использовать тот же основной канал в сочетании с некоторым избыточным кодированием, которое, конечно, считается известным перехватчику. Пересылки всех сигналов контролируются перехватчиком, но в результате даже при оптимальной обработке сигналов перехватчик получит сообщение с набором возможных ошибок, вероятности появления которых соответствуют каскадному соединению основного канала и канала перехватчика Таким образом, канал перехватчика всегда будет иметь вероятность ошибки р=е(\-8) + 5(1-£), где е и 8 переходные вероятности ошибки в основном канале и канале перехватчика. В этом случае состояние перехватчика отличается тем, что он получает свое сообщение по каналу, в котором вероятность ошибки на символ больше, чем вероятность ошибки на символ в канале законного пользователя. Это различие в дальнейшем усиливается за счет кодового зашумления с увеличением общей длины кодового слова используемого кода и ограничением числа исправляемых ошибок.

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

С(е, 8) = И(е + 8 - 2 • в ■ 8)-А(г), где ей. 8 вероятности ошибки в основном канале и канале перехвата, а - функция двоичной энтропии.

В работе рассмотрены зависимости между параметрами каналов, секретной пропускной способностью и параметрами кодов Рида-Соломона. Результаты расчетов представлены в табл.1, где е - вероятность ошибки на символ в основном канале, 8 -вероятность ошибки на символ в канале перехватчика, С(е,8)-секретная пропускная способность канала с открытым обсуждением общей информации, 2Г -мощность конечного поля, п- длина кода Рида -Соломона и Я- скорость используемого кода.

Таблица 1

в 8 С (е,8) 2Г п Я

0.000001 0.000001 0.0000194 21Ь 65533 0.0000153

0.00001 0.00001 0.000161 2й 8191 0.000122

0.0001 0.0001 0.001273 2й 8191 0.00122

0.0001 0.0002 0.00247 2й 8191 0 00244

0 0001 0 0003 0.003618 2ш 1023 0.00293

0.001 0.0001 0.000987 21и 1023 0.000978

0.001 0.0002 0.001962 2* 511 0.001957

0.001 0.0003 0.002934 2Ш 1023 0.00293

0.01 0.0001 0.000649 2й 2047 0.000489

0.01 0.0002 0.001297 2и . 4095 0.00122

Для создания системы передачи с параметрами, указанными в табл.1, достаточно выбрать неприводимый полином над полем СР(2) подходящей степени, а все остальное -конструкция вероятностного кодирования, алгоритмы исправления ошибок и восстановления информационных символов могут быть выполнены программными средствами в соответствии с разработанными рекомендациями. Реальными затратами в процессе эксплуатации являются только затраты времени на передачу информации в обоих направлениях по основному каналу. Эти затраты времени зависят от объемов передаваемой открытой и конфиденциальной информации и могут составлять от долей секунд до нескольких минут.

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

трудно, но в данной задаче возможность использования границы Чернова является следствием особенностей алгебраической структуры кодов Рида-Соломона, которая позволяет легко вычислить спектры используемого кода.

Для оценки вероятности успешного перехвата (и вероятности ошибки в основном канале) в работе использовалась граница Чернова, применение которой позволяет оценить вероятность успешного перехвата сообщения противником и вероятности правильного приема в основном канале

(р г (1 -р)

и, )

1-й?

1 п

и»=0

1 п

•/=о

, 1 >с1>р, , 0<й<р.

Расчетные значения параметров биномиальных распределений представлены в табл 2, где /? - вероятность ошибки на символ каскадного соединения двух каналов, а Р0 и Р - вероятности ошибки для символов кода Рида-Соломона в основном канале и канале перехвата соответственно.

Таблица 2.

£ 3 р = е + д- 2-е-д 2Г Р0=1-(1-*)' Р=1-(1-Я'

0.00001 0.00001 1.99998 10"5 2м 0.0002 0.0004

0.00001 0.00002 2.99996 10"3 220 0.0002 0.0006

0.00001 0.00003 3.99994 10° 2'2и 0.0002 0.0008

0.0001 0.0001 0 00019998 2м 0.001998 0 003992

0.0001 0.0001 0.00019998 2й 0.001699 0.003394

0 0001 0.0002 0.00029996 2й 0.001699 0.005087

0.0001 0.0003 0.00039994 2й 0.001699 0.006777

0.001 0.001 0 001998 2Ь 0.014895 0.029554

0.001 0.002 0.002996 2Ь 0.014895 0.04401

0.001 0.003 0.003994 2В 0.014895 0.057826

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

Итоговые результаты представлены в табл.3.

Таблица 3.

р Ро X п пХ X

0.0004 0 0002 0.0003 5.9475 10"6 10485575 6.2 314

0.0006 0.0002 0.0004 1.6423 10° 10485575 17.2 419

0.0008 0.0002 0.0005 2.8231 10"3 10485575 29.6 524

0.003992 0.001998 0.002995 5.9445 10"3 10485575 62.3 3140

0.003394 0.001699 0.002546 5.0532 10'3 131071 6.6 333

0.005087 0.001699 0.003393 0.0001396 131071 18.2 444

0.006777 0 001699 0.004238 0.00024011 131071 31.4 555

0.029554 0.014895 0.022225 0 0004441 32767 14.5 728

0.057826 0.014895 0.03658 0.0021299 32767 69.7 143

В этой таблице символ 6 обозначает долю исправляемых ошибок от длины кодового слова кода Рида-Соломона, Х-значение показателя границы Чернова, показатель экспоненты в границе Чернова равен произведению пХ (оценка вероятности успешного перехвата имеет вид 10-Хп), а I- число исправляемых ошибок.

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

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

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

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

к

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

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

1

4. Предложенный метод реализован в виде двухступенчатой схемы вероятностного кодирования и декодирования кодами Рида-Соломона и схемы снятия зашумления,

которая включает алгоритм быстрого восстановления информационных символов из |

принятого синдромиого сообщения.

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

I

Основные результаты диссертации изложены в 9 печатных работах.

1. Курицын К.А., Савельев М.Ф., Открытое обсуждение при согласовании секретного |

I

ключа //Сб.тезисов конференции «Методы и технические средства обеспечения |

безопасности информации», СПбГТУ, 200! г., С.93-94

2. Курицын К.А., Савельев М.Ф., Согласование секретного ключа через открытый канал //Проблемы информационной безопасности. Компьютерные системы, № 3,

2001 г., С.39-43. |

3. Савельев М.Ф. Линейные коды в каналах с перехватом //Проблемы 1 информационной безопасности. Компьютерные системы, №2, 2002 г., С.47-51.

г •

4. Савельев М.Ф., Дешифрация сообщений по базисным элементам // Сб.тезисов 1 конференции «Методы и технические средства обеспечения безопасности 1 информации», СПбГТУ, 2002 г., С.104-107. |

I

5. Савельев М.Ф. Восстановление сообщений по базисным элементам //Сб тезисов

I

конференции «Информационная Безопасность Регионов России-2002», СПб, 2002 I

г., С.39-43. {

6. Савельев М.Ф. Анализ сообщений по базисным элементам //Сб тезисов конференции "Проблемы информационной безопасности в системе Высшей школы", МИФИ, 2003 г., 105 с.

7. Савельев М.Ф. Защищенная передача сообщений по открытому каналу //Проблемы информационной безопасности. Компьютерные системы, №2, 2003 г., С 92-96.

8. Савельев М.Ф. Оценка вероятности успешного перехвата в каналах с кодовым зашумлением //Проблемы информационной безопасности. Компьютерные системы, №2, 2003 г., С.97-102.

9. Савельев М.Ф. О скорости передачи информации в системе радиорелейной связи с кодовым зашумлением //Проблемы информационной безопасности. Компьютерные системы, №2, 2003 г., С.101-105.

Лицензия ЛР №020593 от 07.08.97.

Подписано в печать -/6, Объем в п.л. уГ

Тираж /00, ' Заказ

Отпечатано с готового оригинал-макета, предоставленного автором, в типографии Издательства СП6ГГ1У 195251, Санкт-Петербург, Политехническая ул., 29.

Отпечатано на ризографе £.N-2000 ЕР Поставщик оборудования — фирма "Р-ПРИНТ" Телефон: (812) 110-65-09 Факс: (812) 325-23-04

№

*

4

У 89 9

¿op

ВВЕДЕНИЕ.

ГЛАВА 1. Анализ методов передачи конфиденциальных сообщений по открытым

Ф каналам.

1.1. Требования к конфиденциальной связи.

1.2. Модели каналов связи с перехватом.

1.3. Двоичное вероятностное кодирование.

1.4. Декодирование в синдромном канале.

1.5. Оценки неопределенности у перехватчика.

ГЛАВА 2. Анализ методов декодирования в каналах с шумом.

2.1. Свойства конечных полей.

2.2. Представление кодов БЧХ.

2.3. Коды Рида-Соломона.

2.4. Синдромное декодирование кодов Рида-Соломона.

2.5. Методы исправления ошибок и стираний в кодах Рида-Соломона.

2.6. "Мягкое" декодирование кодов Рида-Соломона.

ГЛАВА 3. Метод защищенной передачи информации на основе

4 кодового зашумления.

3.1. Метод кодового зашумления на базе кодов Рида-Соломона.

3.2 Восстановление информационных символов в синдромном канале. .1(&

ГЛАВА 4. Оценка качества передачи информации в каналах с перехватом.1ЦР

4.1. Основные параметры системы.12JD

4.2. Оценка вероятности успешного перехвата.

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

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

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

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

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

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

3. Выводы

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

1. В первом разделе показано, что хорошо изученные коды Рида»

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

2. Во втором разделе показано, что, благодаря особой структуре кодов Рида-Соломона, удается использовать для оценки вероятности успешного перехвата границу Чернова. Результаты вычислений показывают, что практически при любых характеристиках используемых каналов связи с перехватом можно обеспечить достаточную защиту передаваемых секретных сообщений по открытым каналам связи.

Заключение

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

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

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

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

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

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

1. Витерби А.Д., Омура Дж.К. Принципы цифровой связи и кодирования. М.: Радио и связь, 1982.

2. Гантмахер Ф. Теория матриц. М.: Наука. Главная редакция физико-математической литературы, 1988.

3. Герасименко В.А., Размахнин М.К. Защита информации в вычислительных, информационных и управляющих системах и сетях. Зарубежная радиоэлектроника. 1985. № 85. С. 41-60.

4. Гниденко Б.В. Курс теории вероятностей. М.: Изд-во "Наука", 1965.

5. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах связи. М.: Радио и связь, 1987.

6. Колесник В.Д., Мирончиков Е.Т. Декодирование циклических кодов. М.: Связь, 1968.

7. Коржик В.И. Помехоустойчивое кодирование "уникальных" сообщений. Проблемы передачи информации. Изд. РАН СССР. Т. 22. № 4. С. 26-31.

8. Коржик В.И., Яковлев В.А. Защита информации от утечки по каналам электромагнитных излучений на основе способа кодирования. Региональная информатика. РИ-93. Тезисы докладов. СПб., 1993. Часть 1. С. 91.

9. Коржик В.И., Яковлев В.А. Пропускная способность канала связи с внутренним случайным кодированием. Проблемы передачи информации. Т. 28. № 4. С. 24-34. 1992.

10. Коржик В.И., Борисенко Н.Н. Вычисление секторов смежных классов производных БЧХ-кодов. Известия Вузов. Радиоэлектроника, Т. 26. № 4. С. 14-19. 1983.

11. Коржик В.И., Яковлев В.А. Неасиптотические оценки эффективности кодового зашумления одного канала. Проблемы передачи информации. Изд-во РАН СССР. Т. 17. №4. С. 11-18. 1981ю

12. Курицын К.А., Савельев М.Ф., Открытое обсуждение при согласовании секретного ключа, Сб.тезисов конференции «Информационная Безопасность Регионов России-2001», 2001 г., 0.1 усл.печ.л.

13. Курицын К.А., Савельев М.Ф., Согласование секретного ключа через открытый канал, Журнал «Проблемы информационной безопасности. Компьютерные системы» № 3, 2001 г., 0.2 усл.печ.л.

14. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: "Связь", 1979.

15. Маркин А.В. Безопасность излучений и наводок от средств электронно-вычислительной техники: домыслы и реальность. Зарубежная радиоэлектроника. 1989. № 12. С. 102-109.

16. МессиДж. Л. Введение в современную криптологию. ТИИЭР. 1988. Т. 76. №5. С. 24-42.

17. Мирончиков Е.Т., Федоренко С.В. Об алгебраическом декодировании циклических кодов. Проблемы передачи информации. Изд. РАН. Т. 35. Вып. 1. 1999. С. 44-48.

18. Муттер В.М. Основы помехоустойчивой телепередачи информации. Л.: Энергоатомиздат, 1990.

19. Питерсон У. Коды, исправляющие ошибки / Пер. с англ. под ред. Добрушина Р.Л. М.: Мир, 1964.

20. Прохоров Ю.В. Асимптотическое поведение биоминального распределения. УМН. Т. 8. Вып. 3. 1953. С. 136-142.

21. Розенкродт Дж., Джекобе И. Теоретические основы техники связи. М.: Мир, 1969ю

22. Савельев М.Ф. Анализ сообщений по базисным элементам, Сб.тезисов конференции «Информационная Безопасность Регионов России-2002», 2002 г., 0.2 усл.печ.л.

23. Савельев М.Ф. Анализ сообщений по базисным элементам, Сб.тезисов конференции "Проблемы информационной безопасности в системе Высшей школы", МИФИ, 2003 г., 0.2 усл.печ.л.

24. Савельев М.Ф. Защищенная передача сообщений по открытому каналу, Журнал «Проблемы информационной безопасности. Компьютерные системы», №2, 2003 г., усл.печ.л. 0.2.

25. Савельев М.Ф. Линейные коды в каналах с перехватом, Журнал «Проблемы информационной безопасности. Компьютерные системы», №2, 2002 г., 0.3. усл.печ.л.

26. Савельев М.Ф., Дешифрация сообщений по базисным элементам, СПб, СПбГПУ, СЦЗИ, Сб.тезисов конференции «Методы и технические обеспечения безопасности информации», 2002 г., 0.2 усл.печ.л.

27. Савельев М.Ф. Оценка вероятности успешного перехвата в каналах с кодовым зашумлением, Журнал «Проблемы информационной безопасности. Компьютерные системы», №2, 2003 г., усл.печ.л. 0.2.

28. Савельев М.Ф. О скорости передачи информации в системе радиорелейной связи с кодовым зашумлением, Журнал «Проблемы информационной безопасности. Компьютерные системы», №2, 2003 г., усл.печ.л. 0.2.

29. Соломон Г., МаттсонГ.Ф. Новая трактовка кодов Боуза-Чаудхури. Сб. "Теория кодирования". Изд-во "Мир", 1964. С. 7-29.

30. Сосуков Б.В. Основы теории и практики экранирования РЭС. Л. ВАКС. 1990.

31. Федоров Р.Ф., Яковлев В.В., ДобрисГ.В. Стохастические преобразователи информации. Л.: Машиностроение. Ленинградское отделение, 1978.

32. Феллер В. Введение в теорию вероятностей и ее приложения. М.: Изд-во "Мир", 1964.

33. Финк Л.М. Теория передачи дискретных сообщений. М.: Соврадио, 1970.

34. Форни Д. Каскадные коды / Пер. с англ. под ред. Самойлина С.И. М.: Мир. 1970.

35. Чиссар И., Кернер Я. Теория информации: Теоремы кодирования для дискретных систем без памяти / Пер. с англ. М.: Мир, 1985.

36. Яковлев В.А. Защита информации на основе кодового зашумления. Часть 1. Теория кодового зашумления. Спб.,ВКАС, 1993.

37. Яковлев В.А., Бондаренко А.Г. Оценка неопределенности источников в суммирующем канале при случайном кодировании. 46-я научно-техническая конференция Электротехнического института связи им. М.А. Бонч-Бруевича. Тезисы докладов. СПб., 1993. С. 12-13.

38. Яковлев В.А., Жупников В.Г. Оценка помехоустойчивости системы передачи информации со случайными сигналами. Доклады 12-го научно-технического семинара: Статистический синтез и анализ информационных систем. Москва-Черкасы, 1992. С. 93-95.

39. Berlekamp E.R. Algebraic Coding Theory. New York: Mc. Graw-Hill, 1968.

40. Blahut R.E. A universal Reed-Solomon decoder. ШМ J. Res. Develop. Vol. 28. P. 150158. 1984.

41. Blahut R.E. Theory and Practice of Error Control Codes. Reading, Mass.: Addison-Wesley, 1983.

42. Bose R.C. and Ray D.K. -Chaudhuri. On aclass of error-correcting binary group codes. Inform. Contr., Vol. 3. P. 68-79.

43. ChernoffH.A. A Measure or Asymptotic Efficienty for test of a Hypothesis Based on a Sum of Observatious. Ann. Math. Stat. Vol. 23. P. 493-507. 1952.

44. Chien R.T. Cyclic decoding procedure for Bose-Chandhuri-Hocquenghem codes. IEEE Trans. Inform. Theory. Vol. IT-10. P. 357-363. Oct. 1964.

45. Csissar I., Korrner I. Broad cast Channels with Confidential Messages. IEEE Trans. Inform. Theory. Vol. IT-24. № 3. 1978. P. 339-348.

46. Einersson G. and Sundberg C.E. A note on soft decision decoding with successive erasures. IEEE Trans. Inform. Theory, Vol. IT-22. P. 86-96. San. 1976.

47. Forney D.G. Jr. On decoding BCH codes. IEEE Trans. Inform. Theory. Vol. IT-11. P. 549-557. Oct. 1965.

48. Forney D.G., Jr., Generalized minimum distance decoding. IEEE Trans. Inform. Theory. Vol. IT-12. P. 125-131. Apr. 1966.

49. Gorenstein D.C. and Zierler N. A class of cyclic linear error-correcting codes in pm symbols. S. Soc. Ind. Appl. Math., Vol. 9. P. 207-214, June 1961.

50. HellmanM.E., CarleialA.B. A note an Wynef s wire-tap channel. IEEE Trans. Inform. Theory. Vol. IT-23. № 3. P. 387-390.

51. Hocquengem A. Codes correteurs d'erreurs. chiffers. Vol. 2. P. 147-156, 1959.

52. HuguetLl. Coding Scheme for a Wire-tap Channel Using Regular Codes. Discrete Mathematics. 1985. Vol. 56. № 2,3. P. 191-201.

53. Jamali S.H. and Tho Le-N doc. Coded— modulation techriques for fading channels. Kluwer Academic Publishens. 1996.

54. Massey J.L. Shift-register synthesis and BCH decoding. IEEE Trans. Inform. Theory. Vol. IT-15. P. 122-127. San. 1969.

55. Massey J.L. A. Simplitied Treatment of Wyner s Wire-tap channel. Proc. 21-st. Allerton Conference on Communication, Control and Computing. Monticello. IL. Oct. 5-7. 1983. P. 268-275.

56. MaurerU.M. Secret Key Agreement by Public Discussion from Common Information IEEE Trans. Inform. Theory. Vol. IT-39. № 3. May, 1993. P. 733-742.

57. Peterson W.W. and Weldon E.S., Jr., Error-Correcting Codes. Cambridge. Mass.:MIT Press, 1972.

58. Peterson W.W. Encoding and error-correction procedures for the Bose-Chandhuri codes. IEEE Trans. Inform. Theory. Vol. IT-6. P. 459-470, 1960.

59. Peterson W.W. Error-correcting Codes. Cambridge. Mass. :MIT Press, 1961.

60. PiretPh. Wire-tapping of a Binary Symmetric Channel. Philips J. Res. 1980. Vol.35. P. 251-258.

61. Reed I.S. and Solomon G. Polynomial codes over certain finite fields. J. Soc. Ind. /-^pl. Math. Vol. 8. P. 300-304, June 1960.

62. Wolf J.K. Efficient maximum like lihoad decoding of linear block codes using a trellis. IEEE Trans. Inform. Theory. Vol. IT-24. P. 76-81. 1978.

63. Wolf J.K. Adding tow information symbols to certain nonbinary BCH codes. Bell. Syst. Tech. S. Vol. 48. P. 2405-2409, 1969.

64. Yamamoto H. Cading Theorem for Secret Sharing Communication System with tow Noisy Channels. IEEE Trans. Inform. Theory. Vol. IT-35. P. 572-578. 1989.

65. ГОСУДАРСТВЕННЫЙ НАУЧНЫЙ ЦЕНТР РОССИИ1. ОТ .

66. ЦЕНТРАЛЬНЫЙ НАУЧНО ИССЛЕДОВАТЕЛЬСКИЙ И ОПЫТНО - КОНСТРУКТОРСКИЙ ИНСТИТУТ РОБОТОТЕХНИКИ И ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ

67. Тихорецкий пр., 21, Санкт-Петербург, 194064 Россия1. СС. лсоз №1. На №.от

68. УТВЕРЖДАЮ Директор-глдв^ый^онструктор1. В.А.Лопота1. АКТоб использовании результатов диссертационной работы1. М.Ф.Савельева

69. А.Я.Городецкий, д.т.н., профессор Ю.Е.Подгурский, к.т.н., завлабораторией С.А.Захаров, начальник отдела

70. Телефон: (812)552-0110, 552-0130 Факс:(812)556-3692 Телетайп-122433APC e-mail: info@neva.ru http://www.rtc.neva.ru1. УТВЕРЖДАЮ

71. Вице-презид/нт ГОУ «СПбГПУ» по научной. ,,, "\'АЛ^БашкареЕ1. Www13 г.$/ -Апестационн! о / цантр 70>| Министерства путем о\ сообщения1. Л Российской1. Федерации А?1. УТВЕРЖДАЮ

72. Директор <рГП АЦ «Желдоринформзащита ПС России»1. М.М. Петров2003 г* МОСКвЧ"1. АКТоб использовании результатов диссертационной работы Савельева М.Ф. на тему "Метод защищенной передачи информации на основе кодового зашумления"

73. Заместитель директора кандидат технических наук1. Начальник отдела

74. Зав. кафедрой ИБКС СПбГПУ проф., д.т.н.

75. И.А. Сидоров В.А. Девятаев1. П.Д. Зегжда1. УТВЕРЖДАЮ1. УТВЕРЖДАЮ1. АКТоб использовании результатов диссертационной работы аспиранта ГОУ «СПбГПУ» Савельева Максима Феликсовича

76. Зам. директора СЦЗИ СПбГПУ1. С.А.Монин