Содержание к диссертации
Введение
Глава 1- Кодирование информации на основе динамического хаоса 21
Глава 2. Схема кодирования на основе схемы с нелинейным подмешиванием информационного сигнала в хаотический 64
2.1. Схема с нелинейным подмешиванием 64
2.2. Алгоритм построения системы шифрования на основе схемы с нелинейным подмешиванием 74
2.3. Анализ схемы шифрования 83
2.4. Выводы 97
Глава 3. Хаотические последовательности, содержащие заданную информацию 98
Глава 4. Хаотическая синхронизация в системах с конечным числом состояний 117
4.1. Схемы синхронизации с однонаправленной связью 118
4.2. Информационно-открытые системы 121
4.3. Идентификация состояния и синхронизация для симметричного тент- отображения 124
4.4. Идентификация состояния и синхронизация для несимметричного тент- отображения 130
4.4.1. Модифицированный алгоритм 134
4.4.2. Вероятность установления синхронизации 135
4.5. Выводы 138
Заключение 140
Список литературы 142
- Кодирование информации на основе динамического хаоса
- Алгоритм построения системы шифрования на основе схемы с нелинейным подмешиванием
- Хаотические последовательности, содержащие заданную информацию
- Информационно-открытые системы
Введение к работе
Открытие динамического хаоса [Ы7] и дальнейшее его изучение привели к пересмотру многих привычных представлений в различных областях науки и техники» В середине 80-х годов, после обнаружения явлений хаотической синхронизации [103-108] и хаотического синхронного отклика [109] стало понятно, что нелинейная динамика может найти свое место в теории связи и теории информации [18-20],
В классической теории информации [21-23], где основным является вопрос об условиях надежной передачи сообщений, рассматриваются три типа сигналов:
• информационные, характеризуемые полосой частот, отношением сигнал-шум и/или необходимой скоростью передачи информации в бит/с;
• случайные (как правило это шумы), обладающие бесконечной энтропией (информацией);
• детерминированные (например, синусоидальные несущие сигналы), информационное содержание которых равно нулю.
Шумы ограничивают точность воспроизведения информационных сигналов и тем самым ограничивают пропускную способность каналов связи.
Уже в конце 50-х годов прошлого века начало возникать понимание того, что теория информации не является аксиоматически замкнутой, а допускает н даже требует введения новых элементов, чтобы более полно отражать информационные процессы в естественных и искусственных системах [24]. К началу 80-х годов благодаря фундаментальным открытиям в области нелинейных явлений (самоорганизация и динамический хаос [25-32]) и осознанию возможности обработки информации на квантовом уровне [33-34] созрели предпосылки для дополнения, развития, а в ряде случаев и пересмотра некоторых положений классической теории.
Хаотические колебания представляют собой специфический вид сигналов, информационное содержание которых отлично от нуля. В связи с этнм они могут рассматриваться как носители информации, а детерминированные нелинейные динамические системы, порождающие такие сигналы, как особые источники информации. Важным свойством хаотических колебаний как информационных сигналов является то, что средний объем информации в единицу времени у них строго определен. Отсюда следует, например, что они могут быть переданы без искажений по каналу с ограниченной пропускной способностью. Для других видов аналоговых сигналов, содержащих информацию, например для речевых сигналов или белого шума, это невозможно.
Существует ряд других свойств хаотических сигналов, делающих их потенциально привлекательными для использования в системах передачи информации. К этим свойствам можно отнести:
Возможность получения сложных колебаний с помощью простых по структуре электронных устройств,
К настоящему времени предложено и исследовано значительное количество динамических систем, генерирующих хаотические сигналы. "Минимальные" хаотические генераторы описываются всего тремя обыкновенными дифференциальными уравнениями и, по меньшей мере, часть из них представляют собой генераторы, построенные путем добавления одного или нескольких элементов в стандартные генераторы регулярных колебаний. Другие источники хаоса не так просто связать с традиционными электронными генераторами, однако они также могут быть реализованы с помощью современной элементной базы либо схемотехнически, либо в виде аналоговой интегральной микросхемы, либо на основе цифровых сигнальных процессоров. В качестве примеров источников хаоса с полутора степенями свободы можно привести систему Лоренца [2] систему Ресслера [35], генератор с туннельным диодом [36], цепь Чуа [37-38]. Первые из двух систем первоначально были предложены в областях далеких от электроники, однако как уже говорилось, на базе этих моделей можно реализовать генераторы хаоса, точно также как это делается с генераторами, более
близкими по своему виду к традиционным. Выбор модели и ее реализации определяется конкретной задачей, которая предъявляет (или может предъявить) к источнику хаоса специфические требования. Причем разнообразие моделей источников хаоса, конечно, не исчерпывается только системами с полутора степенями свободы.
• В одном источнике хаоса может быть реализовано большое количество различных хаотических мод»
Траектории хаотических систем чрезвычайно чувствительны к начальным условиям. В то же время сами колебательные режимы источников хаоса демонстрируют богатство разнообразия при изменении параметров системы. Причем, если число существенных параметров в системе несколько, то это, как правило, приводит к увеличению разнообразия динамических режимов. Типичным примером является цепь Чуа [37-37], Разнообразие хаотических режимов может возрастать также с увеличением размерности динамической системы.
Большое количество различных мод представляет интерес для коммуникационных систем, использующих хаос, поскольку потенциально позволяет организовать большое число отдельных каналов связи, определяемых совокупностью значений параметров и тем самым определенной долей приватности. Грубо говоря, для того чтобы пара "посылающий сообщение - принимающий сообщение" могла нормально работать, оба и абонент, посылающий сообщение, и принимающий абонент должны знать этот набор параметров. Другим потенциальным абонентам, не знающим конкретную совокупность параметров (даже если они обладают приемником на основе той же самой по структуре динамической системой) информация пересылаемая упомянутой парой абонентов будет недоступна.
• Управление хаотическими режимами может производиться путем малых изменений параметров системы.
Болыное количество различных колебательных мод в одной и той же системе означает, что изменение режима происходит при малом изменении параметров системы. Этот факт в зависимости от конкретной ситуации может иметь как отрицательное, так и положительное значение для систем передачи информации, использующих хаос. Отрицательное влияние: слишком высокая чувствительность к значениям параметров приводит к жестким требованиям по идентичности параметров, требованиям высокой температурной стабильности и т.д. С другой стороны эти же свойства позволяют управлять хаотическими системами на уровне мощностей намного более низких, чем мощность самого хаотического сигнала, что, несомненно, полезно для достаточно мощных источников хаоса. Это же свойство при прочих равных условиях обеспечивать более высокую скорость модуляции хаотических колебаний по сравнению со скоростью модуляции в классических системах, В целом, за счет возможности управления хаотическими режимами путем малых изменений параметров системы можно ожидать улучшения энергетической эффективности коммуникационных систем с хаосом по сравнению с традиционными системами.
• Хаотические сигналы обладают в среднем постоянной энтропией (информацией) на отсчет (в единицу времени).
Это свойство хаотических систем уже упоминалось выше, К сказанному стоит добавить, что поскольку информационное содержание хаотических сигналов в среднем постоянно, то его можно количественно измерить. Поэтому они могут, например, быть использованы как тестовые сигналы при анализе информационных свойств коммуникационных систем и их компонентов.
• Возможность "вложения" большого количества информации в хаотический сигнал.
По своей природе хаотические сигналы обладают сплошным спектром, простирающимся в широкой полосе частот. Как известно информационное содержание сигналов-сообщений прямо пропорционально занимаемой ими полосе частот. Современные методы модуляции позволяют в принципе обеспечить полосу передаваемого сигнала на высокой частоте до 10-20% по отношению к частоте несущего колебания. Однако это достигается за счет специальных достаточно сложных технических решений. Такие системы относятся к широкополосным системам. Хаотические сигналы являются широкополосными по своей природе. Они могут в принципе даже не иметь выделенных в спектре частот. Это позволяет вводить в них информационные сигналы, с полосой вплоть до полосы самих хаотических сигналов, практически без изменения их полосы и формы спектра. Тем самым появляется возможность достаточно простой реализации не только широкополосных, но и сверхширокополосных систем связи с полосами частот до октавы,
Разнообразие методов ввода информационного сигнала в хаотический.
Введение информации в несущий сигнал осуществляется в классических системах связи путем модуляции амплитуды, фазы или частоты несущих колебаний. Это - те три параметра несущих колебаний, которые являются "свободными" для ввода информации.
Ситуация с хаотическими колебаниями принципиально иная- Они разнообразны по форме и их параметризация не может быть сведена к таким внешним признакам как амплитуда, фаза и частота. Изменение одного или нескольких параметров приводит к изменению структуры колебаЕіий, причем эти изменения, как правило, не сводятся к изменению внешнего вида колебаний, которые могут быть легко зафиксированы "невооруженным взглядом". Структура вида колебаний при небольшом измеїгенин параметра может измениться незначительно, но это будет уже другая хаотическая мода и факт се смены может быть надежно зафиксирован специально разработа иными методами. Если в системе имеется несколько изменяемых параметров, то варьирование каждым из них в отдельности или одновременно будет приводить к изменению типа хаотической моды. Поэтому ввод информации может осуществляться с помощью изменения параметра (параметров). Извлечение же информации в приемнике осуществляется за счет выбора параметров приемника, синхронизующих работу приемника с работой передатчика. Оценки значении этих параметров и будут определять информационный сигнал модулирующий хаотическую систему. Более того, проводились исследования, показавшие, что таким образом можно передавать и извлекать в приемнике не только один сигнал, по и несколько независимых сигналов, модулируя этими сигналами разные параметры хаотической системы.
Таким образом, уже только модуляция параметров хаотической системы дает большое разнообразие возможностей для ввода информации в хаотический сигнал. Однако она далеко не исчерпывает эти возможности. Существует целый ряд других подходов, среди которых: нелинейное подмешивание информационного сигнала к хаотическому, возмущение траекторий хаотической системы малыми отклонениями, использование тонкой структуры аттрактора и другие.
• Увеличение скорости модуляции по отношению к традиционным методам модуляции.
Как уже отмечалось, неустойчивость траекторий хаотических систем делает их чрезвычайно чувствительными к управлению. Например, при необходимости перевести фазовую траекторию из одной точки аттрактора в другую, требуемый результат может быть получен за счет одного или серии малозаметного, незначительного возмущения траектории. Каждое из этих возмущений лишь слегка меняет траекторию системы, но через некоторое время накопление и экспоненциальное усиление малых возмущений приводит к достаточно сильной коррекции траектории и при соответствующем выборе уровня и направления возмущений позволяет решить поставленную задачу. При этом траектория системы остается на хаотическом аттракторе. Таким образом, системы с хаосом демонстрируют одновременно и хорошую управляемость и удивительную пластичность: система чутко реагирует на внешние воздействия, при этом сохраняя тип движения.
Из сказанного следует, что скорость модуляции в хаотических системах при одном и том же уровне коэффициента модуляции может достигать существенно больших значений, чем в системах с регулярной динамикой. При этом в силу отмеченной пластичности будет сохраняться структурная устойчивость динамических режимов,
• Самосинхронизация передатчика и приемника.
Обнаружения явления хаотической синхронизации [39] и хаотического синхронного отклика [40] обусловили возникновение острого интереса к использованию хаоса для передачи информации. Особенно это относится к хаотическому синхронному отклику. Было показано, что для широкого класса систем с хаосом возможно построить некие "сопряженные" к этим системам нелинейные устройства, которые обладают следующими двумя свойствами:
1) при подаче на вход такого устройства хаотического сигнала сопряженной ему хаотической системы, сигнал на выходе этого устройства идентичен сигналу на его входе;
2) для всех других сигналов это свойство не выполняется.
Таким образом, устройство, реализующее хаотический синхронный отклик, представляет собой нелинейный фильтр, позволяющий в частности распознавать сигналы данного источника хаоса среди сигналов, порождаемых другими источниками.
Принцип хаотического синхронного отклика используется в значительной части предложенных к настоящему времени схем связи, использующих хаос.
• Нетрадиционные методы мультиплексирования.
Вопрос о том, как обеспечить одновременное использование каналов связи несколькими или даже многими потребителями является чрезвычайно важным в современных системах связи. Только при его решении возможно построение многопользовательских систем, примерами которых являются: магистральные системы связи (в том числе информационные "highways"), спутниковые системы связи, системы обычной и сотовой телефонии, интернет и др. Совместное использование "пространства - времени" в них обеспечивается различными способами, среди которых наиболее широко распространенными являются: пространственное разделение сигналов (например, обслуживание спутником одновременно нескольких территорий за счет применения многолучевых направленных антенн), частотное разделение каналов (frequency division), разделение каналов по времени (time division), кодовое разделение каналов (code division).
Хаотические сигналы обладают рядом свойств, которые позволяют создать схемы разделения (мультиплексирования) сигналов принципиально отличающиеся от перечисленных, например, на основе хаотической синхронизации и хаотического синхронного отклика. Важно отметить, что подобные схемы разделения невозможно реализовать для других типов сигналов.
• Конфиденциальность при передаче сообщений.
Конфиденциальность передачи информации по эфиру определяется следующими факторами:
- вероятностью перехвата;
- сложностью сигнала, который используется для расширения спектра;
- сложностью шифра, который может быть использован для обычного текстового сообщения.
Из-за малой спектральной плотности мощности, ассоциируемой с передачей в расширенном спектре, что является достаточно типичным для хаотических систем связи, переданный сигнал трудно зафиксировать (принять}. Вероятность приема может быть дополнительно снижена путем использования коротких интервалов передачи.
Повышенная конфиденциальность может. быть получена путем кодирования сообщений перед передачей. Проблема кодирования в практических системах (особенно использования блочных кодов) становится все более тяжелой по мере увеличения скорости передачи потоков данных. Следовательно, потоковые схемы кодирования становятся более привлекательными при высоких скоростях передачи данных, В конечном счете, объем потока данных ограничивается общим количеством шифруемой и кодируемой информации.
Интерес к хаотическим схемам связи в значительной степени определяется тем, что даже простейшие из них обладают определенной степенью конфиденциальности. Речь идет о том, что посторонний наблюдатель должен обладать достаточно подробной информацией об используемой в передатчике хаотической системе, чтобы иметь потенциальную возможность для организации перехвата этой информации.
Исходя из перечисленных свойств хаотических колебаний, можно говорить о целесообразности их выделения в рамках теории информации в отдельную группу сигналов. В соответствие с этим должны появится новые разделы, посвященные взаимодействию таких пар сигналов, как информационный сигнал - хаотический сигнал, хаотический сигнал — шумовой сигнал, хаотический сигнал — регулярный сигнал, а также более сложным видам взаимодействия с участием динамического хаоса.
В настоящей диссертации хаотические сигналы рассматриваются и используются как носители информации, а их свойства применяются для построения и исследования алгоритмов кодирования и передачи данных.
Актуальность работы определяется существующим в настоящее время повышенным интересом со стороны специалистов самых различных научных направлений к динамическому хаосу, а также ролью информационных технологий в жизни современного общества.
Целью настоящей работы является изучение и исследование информационных свойств хаотических сигналов и их применение в задачах кодирования и передачи данных.
Основные задачи, решаемые в работе:
- разработка требований и критериев, которым должны удовлетворять криптографические алгоритмы» основанные на динамическом хаосе;
- построение алгоритма хаотического кодирования информации и исследование его производительности и криптостойкости;
- повышение эффективности использования пропускной способности каналов связи при передаче информации с помощью хаотических носителей;
- синхронизация хаотических систем при наличие шума в канале.
Научная новизна результатов работы заключается в том, что
- исследована взаимосвязь криптографических алгоритмов и хаотических систем; сформулированы требования и критерии по построению алгоритмов кодирования на хаосе;
- на основе разработанных критериев построен алгоритм кодирования информации и исследована его производительность и криптостонкость;
- предложены алгоритмы, позволяюшие управлять динамикой хаотической системы. Это дает возможность вкладывать полезную информацию в хаотический сигнал таким образом, чтобы, во-первых, она содержалась в нем самом, и, во-вторых, ее объем соответствовал объему естественного хаотического сигнала;
- задача синхронизации хаотических систем рассмотрена с точки зрения объема информации, который необходимо передавать от ведущей к ведомой системе, чтобы постоянно поддерживать их в синхронном состоянии. Для класса систем с конечным числом состояний - когда мы имеем дело уже не с хаотическими, а псевдохаотическими системами -предложены алгоритмы, позволяющие организовать синхронизацию между ведущей и ведомой системами без постоянной передачи ведомой системе информации о состоянии ведущей. То есть в пределе (когда t — со) поток передаваемой информации, необходимый для синхронизации, уменьшается до нуля. Достоверность научиых выводов подтверждается соответствием
теоретических результатов с результатами численного моделирования и их
сопоставления с известными в литературе данными.
На защиту выносятся следующие основные положения 1. Требования и критерии по построению и анализу криптографических систем, основанных на динамическом хаосе.
2, Алгоритм хаотического кодирования информации и его исследование на предмет производительности и криптостойкости.
3, Метод ввода информации в хаотический сигнал, позволяющий повысить эффективность использования пропускной способности каналов связи при передаче данных с помощью хаотических носителей.
4. Алгоритм синхронизации хаотических систем, основанный на передаче ведомой системе информации о состоянии ведущей. Научно-практическое значение.
Результаты диссертации могут найти практическое применение при разработке и анализе систем кодирования; в различных задачах, связанных с созданием систем связи, основанных на динамическом хаосе; а также могут использоваться в учебном процессе при чтении соответствующих курсов в Высших учебных заведениях.
Работа выполнялась в рамках исследований, проводимых при поддержке Российского фонда фундаментальных исследований (грант №03-02-16747).
Апробация работы, публикации, внедрение и использование результатов Материалы диссертационной работы докладывались на Международном симпозиуме SCS 2001 (The International Symposium on Signals Circuits and Systems, last» Romania, July 10-11, 2001), на 9-й Международной школе ND&CS 2001 (The 9lh International Workshop & School "Nonlinear Dynamics & Complex Structures", Minsk, Belarus, September 23-26, 2001), на Международной конференции SYNCHRO 2002 (The International Workshop on Synchronization of Chaotic and Stochastic Oscillations. Applications in Physics, Chemistry, Biology and Medicine, SYNCHRO-2002, Саратов, Сентябрь 22-28, 2002), на 11-й Международной конференции NDES 2003 (The 11th Workshop on Nonlinear Dynamics of Electronic Systems, Scuol, May 18-22, 2003), на Всероссийской научной конференции СРСА 2003 (Сверхширокополосные Сигналы в Радиолокации, Связи и Акустике, Муром, Июль 1-3, 2003), на Международном симпозиуме SCS 2003 (The International Symposium on Signals Circuits and Systems, lasi, Romania, July 10-11, 2003) докладывались на научных семинарах в Институте космических исследований РАН, Институте радиотехники и электроники РАН, Московском физико-техническом институте»
По теме диссертации опубликовано 10 печатных работ [46-55].
Структура и объем работы: диссертационная работа состоит из введения, четырех глав, заключения и списка цитированной литературы. Содержит 153 страницы текста, 40 рисунков, две таблицы. Список цитированной литературы содержит 143 наименования.
Краткое содержание диссертационной работы.
Во введении дан обзор свойств хаотических сигналов, делающих их потенциально привлекательными для использования в системах передачи данных. Сформулированы цель и задачи исследований. Обоснована актуальность работы. Изложены положения, выносимые на защиту и краткое содержание работы.
Первая глава посвящена сравнению методов шифрования на основе хаотических систем и традиционных криптографических алгоритмов.
Вначале (раздел 1) излагаются основные положения классической криптографии. К ним относятся: классификация шифров по различным признакам; типы преобразований, осуществляемые с открытым текстом при шифровании; свойства открытых текстов; стойкость шифров и существующие виды криптографических атак; методы анализа алгоритмов блочного и поточного шифрования.
Во втором разделе хаотические системы рассматриваются с точки зрения их приложения к криптографии. Отмечается, что такие свойства как чувствительность к начальным условиям, асимптотическая независимость начального и конечного состояний, возможность самосинхронизации передатчика и приемника, с одной стороны, присущи динамическому хаосу, а с другой - характерны для хороших криптографических алгоритмов. Такое сопоставление позволяет сделать предварительные выводы о том, какие характеристики динамического хаоса и в какой степени являются критическими при создании криптографических алгоритмов на его основе.
Далее проводится анализ некоторых работ, описывающих схемы шифрования на хаосе. Показывается, что большинство предлагаемых методов производят криптографически слабые и медленные алгоритмы. Как выясняется из последующих исследований, одна из причин этого заключается в необоснованном выборе хаотического отображения для схемы шифрования. Дело в том, что двумя основными принципами, которыми необходимо руководствоваться при построении алгоритмов, являются чувствительность к открытому тексту и чувствительность к ключу. Малейшие изменения в одном из них должны значительно изменять результаты шифрования. В хаотических алгоритмах шифрования роль открытого текста могут играть начальные условия, а роль ключа - параметры отображения. Это означает, что если мы хотим использовать в качестве основного элемента схемы некоторое хаотическое отображения, то оно должно обладать чувствительностью не только к начальным условиям, но и к любым возмущениям в пространстве параметров. Однако известно, что большинство хаотических аттракторов структурно неустойчиво по отношению к изменению параметров. Поэтому алгоритмы на их основе могут уметь слабые ключи, В этой связи, необходимо соблюдать большую предосторожность при выборе хаотических отображений- Так, например, устойчивый хаос не может встречаться в гладких системах. С другой стороны, структурно устойчивый хаос может наблюдаться в кусочно-линейных отображениях.
В заключение главы, на основании проведенного анализа, формулируются критерии, которым должен удовлетворять
криптографический алгоритм на основе динамического хаоса.
Во второй главе диссертации описывается разработанная автором процедура создания и анализа схемы шифрования на основе динамического хаоса. В качестве базового модуля алгоритма выбрана схема с нелинейным подмешиванием информационного сигнала в хаотический- Данный выбор продиктован такими свойствами схемы, как точное извлечения информации из смеси с хаотическим сигналом, самосинхронизация передатчика с приемником, простота аппаратной и программной реализации.
В первом разделе схема с нелинейным подмешиванием исследуется на предмет ее эффективности применения в криптографических целях. Руководствуясь критериями, разработанными в главе 1, в роли нелинейного элемента было предложено использовать tent-отображение. Полученная таким образом схема шифрования может использоваться для кодирования любого вида информации. Одним из самых сложных видов сигналов для кодирования является графическая информация. На ее примере и проводятся исследования в работе, В качестве тестового объекта кодирования выбрано черно-белое изображение размером 100x100 пикселов с 256 градациями серого уровня.
Первые тесты по применению этого алгоритма для шифрования информации показали его потенциальную пригодность для криптографического кодирования. Во-первых, в шифрованном изображении не присутствовало никаких струюур, и его спеетр яркости цветов пикселов стал однородным. Во-вторых, предложенная схема чувствительна к малейшим изменениям начальных условий и/или параметров (получаемые при этом шифры абсолютно различны). В-третьих, за счет самосинхронизации, она малочувствительна к ошибкам в шифртексте. Т.е. при расшифровывание искажения в шифртексте сказываются локально, а не распространяются на все изображение.
Однако в схеме был сразу выявлен и существенный недостаток -небольшое число ключей шифрования- Поэтому дальнейшие исследования были направлены на увеличение количества ключей. В результате, путем несложных модификаций схемы с нелинейным подмешиванием, были созданы алгоритмы, которые позволили значительно расширить пространство ключей. Этот процесс модернизации излагается во втором разделе.
В третьем разделе проводится анализ полученной схемы шифрования. Исследуются ее свойства и восприимчивость к различным видам криптографических атак. Показывается, что система является устойчивой против атаки "грубой силы" и атаки с известным открытым текстом- Кроме того» простота структуры и программной реализации схемы позволяют сделать заключение о ее высокой производительности.
Глава 3 посвящена исследованию вопроса о возможности сопоставления динамике произволыюй динамической системы, без нарушения ее структуры, требуемой информационной последовательности. Этот вопрос можно сформулировать несколько иначе; нельзя ли хаотическую систему использовать в качестве кодера, преобразующего информационный сигнап в хаотический? Или другими словами, можно ли заставить хаотическую систему генерировать нужную нам информацию?
В разделе 1 приводятся простые примеры, показывающие, что построение такого кодера вместе с соответствующим ему декодером возможно. В качестве динамических систем используются отображения Бернулли и tent-отображение.
Во втором разделе обсуждается возможность решения поставленных вопросов для систем более сложного вида. Показывается, что методы кодирования информации, применяемые для простых отображений раздела ls в этом случае не применимы- Поэтому в дальнейшем разрабатывается алгоритм, позволяющий представлять информационные сообщения в виде сигнала, структура которого близка к структуре сигнала, генерируемого самой системой.
Стоит отметить, что предлагаемый алгоритм обеспечивает определенную конфиденциальность передачи данных. Кроме того, объем полезной информации, генерируемой такой системой, равен объему информации, содержащемуся в самом хаотическом сигнале. Это означает, что в системах связи с хаотической несущей возможна передача данных без дополнительного увеличения пропускной способности канала.
В четвертой главе изучается вопрос о синхронизации хаотических систем при наличии шума в канале. Изучение проводится посредством анализа информационных свойств хаотических сигналов, когда хаотические колебания рассматриваются как носители информации, а системы их генерирующие, как специфические источники информации,
В первом разделе с позиции количества передаваемой информации необходимой для синхронизации рассматриваются и анализируются некоторые известные схемы синхронизации пары ведущая-ведомая системы,
В разделе 2 даются определения и условия существования информационно-замкнутых (не обменивающихся информацией с внешней средой) и информационно-открытых систем, С этих позиций сами по себе хаотические системы при любом внешнем воздействии являются информационно-открытыми. Однако, как отмечается дальше, при их реализации на системах с конечным числом состояний (например, с помощью обычных компьютеров) они становятся информационно-замкнутыми псевдохаотическими системами. Свойство информационной замкттутости псевдохаотических систем в дальнейшем используется для получения точной синхронизации пары ведущая-ведомая системы. Предложенный алгоритм позволяет значительно сократить, передаваемый от ведущей к ведомой системе, поток информации, необходимой для синхронизации.
В разделах 3 и 4 задача синхронизации систем с конечным числом состояний исследуется на примере tent-отображения, которое выступает в качестве ведущей системы. Для восстановления сигнала в ведомой системе используется отображение, обратное к tent-отображению. Обсуждается вероятность ошибочной синхронизации в зависимости от отношения сигнал шум в канале C/IIL Определяется среднее количество попыток необходимых для точной синхронизации в зависимости от отношения С/Ш.
В заключении суммируются полученные в диссертационной работе результаты и обсуждаются области их применения в задачах кодирования и передачи информации.
Кодирование информации на основе динамического хаоса
В настоящее время существует много алгоритмов кодирования, призванных обеспечить надлежащую защиту для различных видов задач хранения и передачи информации [56-57, 143]- Несмотря на это, задача создания эффективных гибких методов кодирования по-прежнему остается актуальной. Она может стать еще более актуальной в случае создания сверхмощных и сверхскоростных компьютеров, основанных, например, на квантовых вычислениях. При этом большинство существующих на сегодняшний день алгоритмов кодирования, основанных на классической криптографии, окажутся криптографически слабыми и, следовательно, малопригодными для защиты информации. Кроме того, сейчас бурное становление и развитие претерпевают беспроводные системы связи. А это означает, что вероятность перехвата и сканирования информации повышается в десятки раз по сравнению с традиционными системами. И здесь вся ответственность за сохранение конфиденциальности информации ложится на применяемые криптографические алгоритмы.
Осознание этих проблем заставило исследователей обратиться к разработке новых принципов шифрование. Одним из таких направлений является хаотическое шифрование. Привлекательность использования динамического хаоса в криптографии, прежде всего, обусловлена природной чувствительностью хаотических систем к начальным условиям и возможностью самосинхронизации хаотических колебаний. Первое свойство позволяет добиться хорошего перемешивания и рассосредоточения информации в процессе шифрования. Второе - избежать распространения ошибок при восстановлении исходного сообщения. В литературе работы, в которых предлагаются различные алгоритмы шифрования, основанные на хаосе, встречаются довольно часто [75, 77, 79-80, 85-89, 91-93]. Однако, как показывают исследования [58, 76, 78, 84, 85, 91, 92], большинство из них на поверку оказываются довольно медленными и криптографически слабыми схемами. Причина этого заключается в недостаточном понимании принципов построения хаотических криптографических алгоритмов. Дело в том, что в основу хаотических и традиционных алгоритмов изначально положена разная арифметика. Классическая криптография является целочисленной. И само сообщение, и гамма (если идет речь о шифрах гаммирования), с которой оно складывается, являются последовательностями символов из некоторого ограниченного алфавита, например, последовательностями нулей и единиц. Хаотические системы - по своей природе принципиально непрерывны» Поэтому многие методы построения и анализа систем шифрования, существующие в традиционной криптографии не применимы для хаотической. В тоже время сами, принципы и: критерии, которыми сегодня руководствуются при создании шифров на целочисленной арифметике, обязательно должны учитываться и при разработке шифров на хаосе. Отдельная задача, которая здесь возникает - формирование требований и критериев, которым должны удовлетворять уже непосредственно хаотические алгоритмы. Решению этой задачи посвящена первая глава диссертации. В разделе 1 излагаются основные положения классической криптографии. Дана общая классификация шифров по различным признакам и типы преобразований, осуществляемые с открытым текстом при шифровании. Рассмотрены свойства самих открытых текстов. Обсуждена стойкость шифров и существующие виды криптографических атак. Описаны методы анализа алгоритмов блочного и поточного шифрования.
Во втором разделе проводится сопоставление свойств, присущих динамическому хаосу с характеристиками, которым должен удовлетворять хороший криптографический алгоритм. Анализируются некоторые работы по применению хаоса в системах шифрования. На основании проделанного анализа формулируется перечень требований, которым должен соответствовать хаотический криптографический алгоритм.
Алгоритм построения системы шифрования на основе схемы с нелинейным подмешиванием
Как было установлено в предыдущем разделе, рассмотренная схема кодирования с нелинейным подмешиванием имеет существенные ограничения по количеству возможных ключей шифрования. Выясним причину возникновения кластеров большого размера подобных ключей. Из главы 1 известно, что криптографически стойкий алгоритм должен обладать хорошими диффузионными свойствами, как по открытому тексту, так и по ключу. Другими словами, небольшое возмущение в открытом тексте или ключе должно приводить к полному изменению шифртекста. Таким образом, свойство диффузии сильно влияет на количество возможных ключей в схеме шифровании, Рассмотрим проявление диффузионных свойств в описанной схеме.
Схема кодирования с нелинейным подмешиванием обладает хорошим рассеиванием по открытому тексту. Небольшое возмущение в одном пикселе приводит к получению абсолютно нового шифртекста. Данный результат объясняется чувствительностью схемы к начальным условиям. Для tent-отображения показатель Ляпунова X = In 2. Это означает, что если в начальный момент времени размер возмущения был 2" , то через N итераций величина возмущения достигнет 1, т.е. траектории разбегутся на размер аттрактора. Иначе говоря, если мы внесем возмущение в последний бит мантиссы двоичного представления числа, то примерно через 50 - 55 итераций (52 бита в представление числа отводится под мантиссу) степень корреляции между исходной и возмущенной траекториями будет такая же как у двух случайных независимых последовательностей- Таким образом, если длина открытого текста заметно превышает 50 бит, то любое сколь угодно малое возмущение в нем приведет к полному изменению шифртекста»
Рассматриваемая схема является чувствительной не только к изменениям в открытом тексте, но и к изменениям в ключе. Действительно, изменение параметра соответствует изменению наклонов кусочно-линейной функции отображения. Это приводит к возмущению траектории, В свою очередь, как было только что продемонстрировано, любое возмущение траектории влечет за собой появление абсолютно нового шифртекста. Данные рассуждения доказывают наличие хороших диффузионных свойств в схеме с нелинейным подмешиванием.
В чем же тогда причина возникновения больших кластеров подобных ключей? Рассмотрим, что происходит с шифртекстом при его расшифрование. Если на вход декодера пришел сигнал S„ + Xn, то на его выходе мы получим сумму Sn + Ахщ где Ах„ определяется несоответствием параметров кодера и декодера. Поскольку в кодере суммирование (соответственно, вычитание в декодере) информационного и хаотического сигналов происходит при каждой итерации tent-отображения, то размер Ахп можно примерно оценить как 2J//, где А(л - разность значений параметров кодера и декодера. Это означает» что при небольших значениях Дц, Ахп также мало. Графическая информация обладает большой избыточностью, поэтому если Ахп мало, то восстановленное изображение будет поддаваться идентификации- Чтобы избежать этого необходимо построить алгоритм, в котором любое сколь угодно малое изменение в параметрах кодера/декодера приводило бы к сильным изменениям Ахп.
Рассмотрим процессы шифрования и расшифровывания сигнала в схеме кодирования с повторениями. Информационный сигнал 5Л подается в сумматор кодера, где к нему добавляется сигнал хп. Суммарный сигнал Sn + х„ поступает в канал связи, а также на вход нелинейного преобразователя. Пройдя через нелинейный преобразователь с многократным применением ФШ суммарный сигнал преобразуется в сигнал хп+[=/ (5п+хп). Далее происходит единичная задержка сигнала х„ + \ по времени и весь процесс повторяется.
Схема декодера аналогична схеме кодера. Принятый сигнал Sn±xn пройдя по петле разомкнутой связи преобразуется в сигнал /Л(і?„ + д:„) и поступает в вычитатель, где он вычитается из сигнала пришедшего на вход декодера іУл+і+/ (5, +дгя). Полученная разность S п +1 — Sn +1 fN(Sn+xn) является восстановленным информационным сигналом. В случае совпадения значений параметров ФШ в кодере и декодере разность AfN =./ (5 + хп) -f\Sn + хп) = 0 и, восстановленный сигнал в точности равен исходному информационному сигналу 5 „ + ] = S„ +1 - Если значения параметров ФШ кодера и декодера различны, то Af Ф 0 и, соответственно, Sп+1 ФSn+\.
Чем больше Nt т.е. чем больше раз применяется ФШ в нелинейных преобразователях кодера и декодера, тем сильнее разность Af отлична от нуля (при одних и тех же отличиях в параметрах кодера и декодера). Данный результат объясняется чувствительностью траекторий хаотических систем к возмущениям в параметрах (при условии, что область определения параметров соответствует хаотическому режиму). Количество вводимых в схему повторений определяется скоростью разбегания траекторий, характерной для применяемой функции шифрована В случае использования в качестве ФШ tent-отображения количество повторений, необходимых для обеспечения хорошей диффузии по ключу (чувствительности к изменениям последнего бита параметра /.і), как было показано выше, равно 50.
Исследуем работу схемы с повторениями на основе нелинейного подмешивания, в которой отображение (2Л) выступает в роли функции шифрования. Значение параметра (л одинаково для каждого применения отображения (2Л) в нелинейном преобразователе кодера. Аналогично во всей цепочке нелинейного преобразователя декодера // остается постоянным.
В качестве информационного сигнала используем изображение представленное на рис. 2.4. Как и раньше, размер кластеров подобных параметров определяется по степени корреляции между исходным и восстановленным отображениями. При значениях корреляции менее 8% полагается, что восстановленное изображение не поддается визуальной идентификации. Результаты численных экспериментов для разного количества применений ФШ в нелинейных преобразователях кодера и декодера при различных значениях параметра // приведены в табл. 2Л. Прочерки в графе "Размер кластера А" означают, что границы кластера подобных параметров выходят за пределы определения отображения. Этот результат наблюдается при достаточно сильной асимметрии отображения (2.1) и при малом количестве применений ФШ.
Хаотические последовательности, содержащие заданную информацию
Существует ряд подходов к передаче данных с использование хаотических сигналов в качестве носителей (см., например, обзор [18]). В большинстве из них через канал передается комбинация хаотического и полезного сигналов. Как известно информационное содержание самих хаотических сигналов отлично от пуля [102]. Это означает, что кроме пропускной способности канала, необходимой для передачи полезного сигнала, требуется дополнительная пропускная способность, определяемая количеством информации, содержащимся в хаотическом сигнале. Поэтому эффективность использования пропускной способности канала в случае применения хаотических сигналов в качестве носителей оказывается ниже, чем для регулярных сигналов. В этой связи было бы желательно научиться формировать информационный сигнал таким образом, чтобы он по своей структуре был близок сигналу, генерируемому хаотической системой. Переформулируем задачу несколько иначе: научиться управлять динамикой хаотической системы таким образом, чтобы производимый системой сигнал содержал в себе требуемую полезную информацию. Решение этого вопроса позволит уменьшить количество передаваемых в единицу времени данных и, следовательно, повысить эффективность использования канала.
Имеется ряд работ, в которых рассматривалась задача о построении хаотических сигналов, содержащих заданную информацию [41-45]. Например, в статье [41] продемонстрировано, что при помощи малых возмущений можно заставить хаотическую систему типа цепи Чуа следовать заданной символической динамике. Однако в этих работах не рассматривался вопрос о соотношении объемов вкладываемой полезной информации и информации, содержащейся в самом хаотическом сигнале. Следует также отметить, что в указанном методе передача информации осуществлялась в открытом виде, т.е. задача конфиденциальности передачи данных не рассматривалась.
Структура главы следующая. В разделе 1 приводятся простые примеры, показывающие возможность введения полезной информации в хаотический сигнал без нарушения его структуры, В качестве динамических систем в этих примерах используются отображение Бернулли и tent-отображение Далее (раздел 2) рассматриваются системы более сложного вида. Для них также обсуждается возможность ввода информации в хаотический сигнал без изменения его структуры» Показывается, что методы, применяемые для простых отображений, в этом случае не применимы. В связи с этим, на примере несимметричного отображения Бернулли разрабатываются более общие подходы к решению поставленной задачи.
Рассмотрим вопрос о построении хаотических последовательностей, содержащих заданную информацию и обеспечивающих некоторую степень конфиденциальности при ее передаче, на примере динамических систем типа кусочно-линейных одномерных отображений. Динамика таких систем хорошо изучена, что позволяет наряду с компьютерным моделированием провести теоретический анализ задачи. Все полученные результаты могут быть обобщены на весь класс одномерных отображений вида хп+\ = f(xn).
На открытую позицию, как и в случае отображения сдвига Бернулли, вводится информационный бит. Получаемая при итерациях "хаотическая" траектория содержит полезную информацию» но "запутана" по сравнению с траекторией получаемой при итерациях отображения сдвига Бернулли. В каждом "хаотическом" отсчете снова будет содержаться ровно 1 бит полезной информации.
Итак, мы построили хаотический кодер- Как организовать декодер? Рассмотрим сначала вариант, при котором в приемник поступают "хаотические" отсчеты без шума. В этом случае последняя позиция мантиссы каждого отсчета содержит информационный бит в открытом виде. Поэтому задача декодера сводится к простому извлечению этого бита из каждого приходяшего отсчета.
Пусть уровень шума мал по сравнению с уровнем хаотического отсчета, по достаточно велик по сравнению с амплитудой младшего разряда отсчета, При этих условиях мы не можем установить непосредственно какой бит вводится в младший разряд. С другой стороны у нас имеется информация о том, какую из ветвей выбрать при итерировании двузначного отображения, обратного cttent" отображению. Эта информация содержится в ранее принятых отсчетах. Если значение отсчета меньше 1/2, то выбираем ветвь х(у) = у/2, в противном случае — ветвь х(у) = 1 -у/2. Для извлечения информации, заложенной в я-ом отсчете, итерируем обратное отображение М раз, взяв в качестве начального условия уи. При этом элементы последовательности восстанавливаются с предельно возможной точностью, и полученная информация извлекается из последнего двоичного знака.
Информационно-открытые системы
Пусть имеется динамическая система 21, описываемая некоторыми эволюционными уравнениями для переменной хєД где N - размерность фазового пространства системы. Поведение -Г можно изучать, квантуя ее по времени и переменой состояния [139-141].Основная идел заключается в делении множества возможных состояний на конечное число ячеек и нахождении маршрута, определяющего, к какой ячейке относится состояние системы при каждом такте часов. Каждая ячейка описывает информационное состояние системы и ассоциируется с некоторым "символом", и, таким образом, смена информационных состояний системы (информационная эволюция системы) представляется бесконечной последовательностью символов.
Будем называть Еинформационно-открытой системой, если она связана с внешней по отношению к ней средой таким образом, что эта связь приводит к изменению информационных состояний системы в процессе ее эволюции относительно такой же системы, не связанной с внешней средой. В противном случае будем называть систему Еинформационно-замкнутой.
Понятия информационной открытости и замкнутости системы подразумевают наличие порога, при превышении которого внешнее воздействие начинает влиять на эволюцию информационных состояний системы.
Каждая динамическая система, на которую воздействует внешний шум, может рассматриваться по отношению к среде, порождающий этот шум, как кандидат на информационно-открытую для этой среды систему. Она будет информационно открытой в том случае, если уровень внешнего шума таков, что шум способен изменить информационную эволюцию системы.
При малых значениях S система является информационно-замкнутой, поскольку связь с внешней средой, осуществляемая за счет воздействия шума, не меняет информационного состояния системы- Однако при превышении S некоторого порогового значения 4 вероятность перехода в другое состояние становится отличной от нуля. При t% траектория системы время от времени перескакивает через барьер, система "воспринимает" внешнюю информацию, ее информационное состояние меняется при каждом перескоке, и она становится информационно открытой.
В рассмотренном примере существенно наличие порогового значения внешнего шума, ниже которого система является информационно-замкнутой, а выше - информационно-открытой. Пример 2. Хаотические системы по своей природе обладают высокой чувствительностью к возмущениям. В них сколь угодно малое возмущение траектории порождает траекторию, экспоненциально быстро расходящуюся с невозмущенной и, следовательно, с другим информационным содержанием. Эволюция информационных состояний самой возмущенной системы также отличается от информационной эволюции невозмущенной системы. Поэтому хаотические системы являются информационно-открытыми при сколь угодно малых внешних возмущениях, т.е, для них характерно отсутствие порога внешнего шума, при превышении которого информационно-замкнутая система становится информационно-открытой,
В отсутствии внешнего воздействия информационно-замкнутыми системами являются системы с конечным числом состояний. Так как типичные компьютеры представляют системы с конечным числом состояний, они в отсутствии внешнего воздействия являются информационно-замкнутыми системами.
Хаотические системы — это системы с бесконечным числом состояний. Однако при их реализации на обычных процессорах мы имеем дело уже не с хаотическими, а с псевдохаотическими информационно-замкнутыми системами, которые могут рассматриваться как хаотические только на ограниченных временных интервалах, определяемых точностью вычисления процессора (в дальнейшем, с целью упрощения изложения, для псевдохаотических систем будем придерживаться терминологии хаотических систем).
Псевдохаотические системы в силу информационной замкнутости обладают тем свойством, что при многократном запуске системы с одних и тех же начальных условий, ее траектория остается неизменной. Это в частности отличает компьютерное моделирование хаотических систем от физических экспериментов.
Используем свойство замкнутости псевдохаотических систем для синхронизации. Пусть на передающей и приемной сторонах имеются две одинаковые хаотические системы, реализованные на одинаковых процессорах. Каждая система при функционировании производит в процессе своей работы информацию. Для обеспечения синхронизации мы можем передавать информацию от ведущей к ведомой системе- Чтобы осуществить это необходим достаточно высокоскоростной канал. Однако можно поступить и по-другому. По наблюдаемому сигналу от ведущей системы, в силу ограниченности числа состояний процессора, мы можем точно идентифицировать ее информационное состояние и запустить со значением этого состояния ведомую систему. При этом получатель будет принимать с выхода приемной системы тот же сигнал, который он получал бы при непосредственной передачи сигнала с выхода ведущей системы. Но теперь вся эта информация необходимая для воспроизведения сигнала производится в самой ведомой системе. Таким образом, поток информации через коммуникационный канал уменьшается до нуля. При случайной потере синхронизации ее можно восстанавливать путем дополнительных краткосрочных наблюдений за приходящим сигналом.
