Стохастическая информатика: инновации в информационных системах

М осква
Горячая линия - Телеком
2012

УДК 519.72:621.391 
ББК 32.811+22.18 
     О-74 

 
 
Осмоловский  С. А. 
О-74       Стохастическая информатика: инновации в информационных 
системах. − М.:  Горячая линия–Телеком, 2012. – 320 с.: ил. 
ISBN  978-5-9912-0151-3. 
Рассмотрены инновационные разработки в сфере информационных 
технологий и связи с использованием новых сигнальных конструкций,  
алгоритмов обработки информации и протоколов информационных систем 
(ИС). Разработки основаны на применении кодов восстановления целостности (КВЦ) информации, включающих элементы двоичного помехоустойчивого кодирования и криптографии Шеннона, и обеспечивающих 
комплексность защиты информации от всех видов воздействия на нее  
в рамках единого алгоритма обработки информации при однократном введении избыточности. Протоколы ИС, использующих КВЦ, могут применять принципы адаптивного и робастного управления передачей в системе. 
Использование этих разработок расширяет функциональные возможности и улучшает характеристики информационных (информационнотелекоммуникационных) систем. В частности, системы приобретают свойство повышенной устойчивости к преднамеренным деструктивным воздействиям на систему (устойчивость к кибертерроризму). 
Для руководителей и экспертов инновационных и венчурных компаний, «бизнес-ангелов»; разработчиков и научных работников, специализирующихся в области информационных технологий и систем, теории информации, помехоустойчивого кодирования, криптографии, информатики, 
теории управления; будет полезна студентам и аспирантам соответствующих специальностей. 
 ББК 32.811+22.18 
  
 
 
 
 
Адрес издательства в Интернет WWW.TECHBOOK.RU 

 
Научное издание 

Осмоловский Станислав Антонович 

Стохастическая информатика:  
инновации в информационных системах  

Редактор  Ю. Н. Чернышов 
Компьютерная верстка  Ю. Н. Чернышова 
Обложка художника  В. Г. Ситникова 

Подписано в печать  20.05.2012.  Формат 60×88/16. Уч. изд. л. 20.  Тираж 500 экз. (2-й завод 50 экз.) 
 
ISBN  978-5-9912-0151-3                                          ©  С. А. Осмоловский, 2011, 2012 
   ©  Издательство  НТИ «Горячая линия–Телеком», 2012 

Введение и постановка задачи

В монографии рассматриваются вопросы создания и применения новых информационных технологий на основе оригинальных сигнальных конструкций и алгоритмов их обработки, созданных в России. Эти технологии
основаны на идеях Клода Шеннона [1, 2] использования случайных сигналов
в задачах защиты информации и могут дать в результате своего применения
значительный технико-экономический эффект.
Цель монографии — показать на конкретном примере возможность и
порядок доведения научной идеи до уровня инновационного проекта, способного принести как научные, так и практические результаты [3].
Ранее был проведен комплекс научно-исследовательских и экспериментальных работ [4], достаточных для перехода к промышленному этапу инновационного проекта.
В 2008 году начался финансовый кризис, быстро превратившийся в мировой экономический кризис, беспрецедентный по числу затронутых спадом
производства стран и размеру спада. B период кризиса приходится объединять усилия руководителей всех стран мира и создаются условия для
обновления базисных технологий, влияющих на состояние мировой экономики. Для скорейшего и эффективного применения новых информационных технологий требуются разработка, внедрение стандартов и согласованные действия ведущих мировых компаний при обязательной организующей
роли России, где созданы эти инновационные технологии.
Для России это становится поводом начать выполнение объявленной
программы по приданию экономике России инновационного характера, в
том числе в сфере информационных технологий [5].
В современных информационных технологиях и системах просматривается тенденция применения сразу нескольких видов защиты информации,
каждый из которых существенно необходим для эффективного выполнения функций информационных систем. Эта тенденция отражена в международных стандартах телекоммуникационных сетей, определяющих комплекс функций защиты информации: защита от ошибок в каналах связи с
помощью помехоустойчивых кодов, аутентификация сообщений и контроль
целостности информации (защита от навязывания ложной информации),
рандомизация сигналов, защита от ознакомления с информацией (криптозащита).
В качестве примеров реализации этой тенденции можно привести стандарт 802.16 (WiMax) для широкополосных беспроводных сетей радиосвязи и
европейский стандарт EN 300 744 (Digital Video Broadcasting (DVB); Framing
structure, channel coding and modulation for terrestrial television) передачи
данных для цифрового наземного телевидения.

Введение и постановка задачи

В настоящее время при разработке методов кодирования с восстановлением целостности (КВЦ) информации (стохастического кодирования с исправлением ошибок) удалось получить ряд инженерных решений, имеющих
существенное прикладное значение.
В монографии содержится ряд научных разделов, имеющих фундаментальное значение (главы 3–8 и 13), и научных разделов, имеющих прикладное значение (главы 2, 9–12, 14, 15).
B первой группе глав исследуются ансамбли случайных избыточных сигналов, построенных на основе
l-перемежения исходных двоичных (n, k)-кодов с исправлением ошибок, которые вместе с алгоритмом декодирования по принципу максимума точности создают класс (n, k, q)-кодов с восстановлением целостности информации
(ВЦ-кодов, или стохастических кодов с исправлением ошибок). B случае
технической реализации ВЦ-кодов длина перемежения l = 32 достаточна
для достижения верхней границы вероятности ошибки 10−9; такие коды
будем называть нанокодами (нано — одна миллиардная). Эти работы начаты в 1969 году и завершены оформлением патентов [6, 7].
Сформулируем свойства информационной системы, реализация которых позволит говорить про обновление информационных систем.
1. Обеспечение гарантированных характеристик информационной (информационно-телекоммуникационной — ИТ) системы, количественные значения которых произвольно задаются при проектировании путем выбора
необходимых параметров сигналов и алгоритмов их обработки.
2. Робастность систем за счет ослабления зависимости важнейших характеристик системы от наиболее трудно предсказуемых и наименее точно
описываемых параметров внешней среды, какими являются параметры закона распределения ошибок в реальном канале связи.
3. Адаптируемость для достижения наилучших значений характеристик системы в текущих условиях применения и свойствах среды.
4. Универсализация алгоритмов и протоколов информационного обмена средств связи, которые можно единообразно и эффективно применять
в различных (в пределе любых) реальных каналах связи при максимально
простой необходимой замене параметров алгоритмов и протоколов.
5. Устойчивость к деструктивным информационным воздействиям на
систему из каналов связи.
Разработка и исследование информационных систем с подобными
свойствами ведется в рамках научной дисциплины стохастической информатики (или стохастики) как науки о фундаментальных и прикладных
вопросах применения ансамблей случайных избыточных сигналов.
Для достижения указанных свойств информационной системы воспользуемся ансамблями случайных избыточных сигналов (АСИС). Одним из
вариантов построения АСИС является использование в рамках одной сигнальной конструкции элементов, заимствованных из теории двоичных (n, k)кодов и криптографической системы Шеннона [2]. Такую сигнальную конструкцию естественно называть криптокодами, однако в период создания
таких кодов в 70-е — 80-е годы они были названы стохастическими кодами

Введение и постановка задачи
5

с обнаружением [8] и исправлением [9] ошибок, а методы их применения
в информационных системах — стохастическими методами передачи [10] и
защиты [11] информации.
Исходные идеи Клода Шеннона [1, 2] использования случайных сигналов для защиты информации доведены автором до уровня практической реализации в виде: единой сигнальной конструкции, алгоритмов обработки информации, понятий однократной и оптимальной избыточности,
а также соответствующего программного обеспечения.
Поэтому исследуемая научно-техническая задача может рассматриваться как обобщение и
решение задач помехоустойчивости и секретности в постановке Шеннона.
В монографии изложен инновационный проект в сфере информационных технологий и связи, составные части которого основаны на применении
новых методов комплексной защиты информации от всех видов воздействия
на нее в рамках единой сигнальной конструкции и общего для всех видов защиты информации алгоритма обработки при однократном и оптимальном
введении избыточности.
В результате реализации инновационного проекта должны быть разработаны новые информационные технологии в виде алгоритмов обработки
информации и протоколов информационного обмена, проекты стандартов
на эти протоколы, созданы и испытаны на реальных каналах связи макеты
типовых средств связи, изготовлены, испытаны и сертифицированы опытные образцы аппаратуры связи, организовано серийное производство, проведены маркетинговые работы по продвижению этой аппаратуры на рынок.
При проведении инновационного развития российской экономики актуально применение новых технологий, способных обеспечить конкурентоспособность отечественной продукции на мировом рынке наукоемкой продукции.
При постановке задачи разработки обновленных информационных систем сформулируем три основные цели:
1. Создать новый режим восстановления целостности информации.
2. Сократить сложность реализации основных операций защиты информации (помехоустойчивого кодирования и криптографической защиты).
3. Обеспечить комплексность защиты информации в виде единого алгоритма обработки информации.
В монографии сделана попытка совместить доступное и точное изложение новых научных результатов (описание главного в построении и применении кодов с исправлением ошибок в реальных произвольных каналах, построение искусственного q-ичного симметричного канала со свойствами быстрого криптографического средства, понятие и порядок вычисления пропускной способности реального канала) с методами практической реализации
таких алгоритмов, а также с обоснованием достигаемого положительного
эффекта, в том числе в виде обеспечения таких свойств информационным
системам, которые невозможно получить другими известными методами.
Подготовка и издание монографии обусловлено необходимостью решения двух задач.

Введение и постановка задачи

1.
Изложить новые научные результаты о построении и свойствах
ансамблей случайных избыточных сигналов, формирующие основу новой
дисциплины — стохастической информатики, в том числе входящих в нее
разделов других дисциплин: стохастической теории кодирования, стохастической теории информации и стохастической криптографии. При этом
совокупность новых и ранее опубликованных результатов должна дать обоснование для создания новых информационных технологий с улучшенными
по сравнению с ранее достигнутыми характеристиками.
2. Дать необходимую информацию о порядке проведения инновационного проекта, включая научные обоснования, описание необходимых технических решений, алгоритмов функционирования и патентов, что является
частью подготовительного этапа такого проекта, а также показать порядок
перехода к выполнению опытно-конструкторского и маркетингового этапов
работ.
Автор признателен В.Е. Монахову за совместные исследования стохастических кодов в 1969–1975 гг., участие в редактировании рукописи и полезные замечания по содержанию монографии, Г.А. Кабатянскому за доказательство в 1982 г. теоремы об исправляющей способности стохастических
кодов t = d − 2, А.М. Лелюхиной за разработку действующего протокола
канального уровня со стохастическими кодами и первой версии программного обеспечения, М.А. Иванову за возможность компьютерного исследования
статистических свойств методов стохастической криптографии, В.Д. Скворцову за разработку практической реализации стохастических методов с использованием современных технологических решений, а также Л.А. Бассалыго, Н.А. Кузнецову, Ю.В. Прохорову, В.Н. Чубарикову, В.В. Ященко за
полезные обсуждения отдельных результатов, вошедших в монографию.

Г Л А В А
1
Содержание инновационных разработок

1.1. Основные принципы обновления
информационных систем

В этой главе показаны тренд и траектория перехода от основных идей
Шеннона [1, 2] к программному обеспечению, реализующему обновленные
информационные системы.
Полезно сформулировать минимальную совокупность принципов, обеспечивающих создание обновленных информационных систем со свойствами, приведенными во введении. Любопытно также понять, почему другим
исследователям не удалось пройти аналогичным путем.
Рассмотрим эти
принципы.
1. Использование сигнальных конструкций, заимствованных из современной теории помехоустойчивого кодирования для двоичных кодов и
криптографии Шеннона [2].
2. Применение при реализации режима восстановления целостности
информации (исправление ошибок с требуемой точностью) принципа максимума точности, обеспечиващего выделение правильно принятых символов,
контроль точности выделенных символов и исправление невыделенных или
неточных символов.
3. Использование операций преобразования с дважды стохастической
матрицей переходов при длине преобразования больше 1.
4. Использование двоичных операций при максимально возможной
длине операндов с целью упрощения технической реализации.
Информационные системы, реализующие указанные принципы, приобретают новые свойства (вторичные признаки) — они используют все возможные 2n значений сигналов при его длине равной n и ансамбли случайных сигналов (кодов или шифров).
Рассмотрим сущность инноваций в области построения сигнальных
конструкций и алгоритмов их обработки, на основе которых обеспечиваются достижение поставленных задач, а также основные принципы их применения в информационных технологиях и аппаратуре связи.
Серьезная инновационная разработка в научно-технической сфере должна (или может) базироваться:
1) на научной идее, способной осуществиться в виде действующей или
новой научной дисциплины;
2) научной дисциплине, имеющей фундаментальный и прикладной разделы, формулирующей и обосновывающей отличия и полезность инноваций
на фоне известных научно-технических решений;

Г л а в а 1

3) инженерных разработках, имеющих патентную новизну;
4) патентах, позволяющих сформулировать и защитить существенные
технические отличия и решить вопрос об интеллектуальной и промышленной собственности, важной для инвестора при выборе объекта и субъекта
венчурного финансирования разработок;
5) алгоритмах, протоколах и стандартах, обеспечивающих реализацию
научной идеи и патентов в готовой продукции, способной поступить на рынок услуг и обеспечить доход от инвестированных вложений;
6) опытно-конструкторских разработках (ОКР) и организации производства готовой продукции;
7) маркетинговых работах по продвижению на рынок товаров и услуг
инновационной продукции.
Инновационные разработки в сфере информационных технологий и аппаратуры связи могут быть основаны на комплексе научно-исследовательских и экспериментальных работ, основная часть которых уже выполнена,
излагается в монографии и содержит:
• формирование основных научных идей и задач, удовлетворяющих противоречивым требованиям:
◦ решать актуальные задачи, ранее не решаемые или решаемые недостаточно эффективно;
◦ иметь приемлемую по сложности техническую реализацию;
◦ обеспечивать функциональные или количественные преимущества;
◦ максимально вписываться в общие тенденции развития ИТ технологий и стеки протоколов типовых применяемых сетей и аппаратуры связи;
• разработку научных вопросов построения, описания и исследования
характеристик сигнальных конструкций и алгоритмов их обработки;
определение их места, целей и результатов применения относительно
ранее достигнутых научных результатов;
• закрепление отличий новых инженерных результатов в системе защиты промышленной интеллектуальной собственности (патенты, товарные знаки и другие формы защиты собственности);
• разработку вопросов технической реализации в различных типовых
формах (аппаратная реализация, программная реализация на процессорах общего пользования и специализированных, в виде микросхем
различного типа и пр.);
• разработку вопросов и функций применения сигналов и алгоритмов
их обработки для решения типовых задач и различных условий применения;
• исследование эффективности применения инноваций и оценка влияния
этих инноваций на системные (функциональные и количественные) характеристики ИТ технологий и аппаратуру связи.

Содержание инновационных разработок
9

С учетом особенностей предлагаемых сигнальных конструкций на основе помехоустойчивых кодов и стохастического преобразования (рандомизации) как развитие идей Шеннона [1, 2] для исследования предлагается
использовать научные дисциплины, развивающие традиционные методы
помехоустойчивого кодирования, криптографии в части защиты от ознакомления с информацией, защиты от навязывания ложной информации,
аутентификации сообщений и абонентов в направлении перехода от детерминированных кодов и шифров к ансамблям случайных кодов и шифров.
Рассматриваемые в монографии инновационные разработки на основе
ансамблей случайных избыточных сигналов можно разделить на две основные части. Во-первых, это разработки, начатые 40 лет назад и излагаемые
ниже. Во-вторых, это будущие разработки, которые необходимы для достижения заданной цели, и перечень конкретных необходимых организационных, проектных и маркетинговых мероприятий.
Для создания нового поколения информационных, в том числе ИТ систем, необходимо заложить в основу этих разработок научно-технические
решения следующих задач:
1. Обеспечить слабую зависимость основных характеристик ИС от условий их применения, в том числе от параметров используемых каналов
связи, которые могут существенно изменить как достигаемые возможности
и свойства ИС, так и применяемые методы передачи и защиты информации.
В теории управления и измерения такие системы и средства управления
ими носят название робастных [3] («грубых» по степени чувствительности
к точности описания системы и условиям ее применения).
2. За счет подстройки параметров системы к условиям применения ИС,
например к параметрам и качеству каналов, разработать процедуры адаптации, когда на основе анализа текущих параметров, описывающих функционирование системы с целью оптимизации возможностей и достижения
наилучших характеристик, выполняется задача определения оптимальных
параметров системы по выбранному критерию и производится подстройка
параметров системы или ее части.

1.2. Существо и порядок разработки инноваций,
положенных в основу проекта

В 1971 г. была предложена новая криптографическая двухпараметрическая операция на случайной таблице [13], очень близкая к принципу шифровании с абсолютной стойкостью, предложенному Шенноном [2]. В соответствии с [13] берется таблица с 2n−1 ненулевыми случайными значениями
длины n, полученными от датчика случайных чисел. Для криптографического преобразования на такой таблице используется параметр преобразования (гамма, или «ключ» по Шеннону [2]). Преобразование исходного значения u в результат v состоит в следующем: находим в этой таблице u, затем
от найденной строки таблицы отступаем на число строк, совпадающее на
двоичную интерпретацию значения гаммы, из которой считывается v.

Г л а в а 1

Однако такой подход делает недостаточно точным расчет вероятностей исходов преобразования или декодирования кода, использующего такое
преобразование для перехода от исходного кода к ансамблю случайных кодов. Поэтому было предложено [14] обобщение задачи преобразования на
случайной таблице использованием не 2n − 1 ненулевых значений, а всех
2n комбинаций в таблице и исходов преобразования. Отметим, что такой
переход означает, что искаженное в канале кодовое слово (или q-ичный символ) может с вероятностью 2−n оказаться верным («самоисправиться»), что
не является критичным для применения такого преобразования. Это преобразование имеет дважды стохастическую матрицу переходов размером
(n − 1) × (n − 1) и выполняется под управлением «случайного» преобразования длиной n, что полностью совпадает с постановкой Шеннона [2].
На основе операций на случайной таблице строятся две группы функций:
преобразования блоков (q-ичных символов) произвольной длины [15] и генерации параметров преобразования (гаммы) [16], которые создают основу
для стохастической криптографии, описанной в главе 8.
В 1974 г. была опубликована статья [9] с описанием (n, k)-кода с обнаружением ошибок на основе стохастического преобразования кодового блока
длины n под воздействием случайной последовательности такой же длины.
Это преобразование описывается дважды стохастической матрицей переходов, откуда и название кода. Этот код гарантирует в произвольном канале
вероятность необнаруженной ошибки, верхняя граница которой зависит только от числа избыточных символов r = n − k, благодаря чему код назван
универсальным. Такое свойство уместно назвать робастным в соответствии
со стандартом [8], регламентирующем методы обеспечения точности.
На основе естественной идеи перенести принцип произвольно задаваемой верхней границы вероятности ошибки на режим исправления ошибок
в 1980 г. были предложены конструкция и алгоритм декодирования кода
[10, 17–19], гарантирующий вероятность ошибки в декодированной информации, не превышающей значение q−1 в произвольном канале, в том числе с
преднамеренными ошибками. Алгоритм декодирования такого кода содержит функцию отказа от декодирования при кратности ошибки, превышающей исправляющую способность кода, что принципиально необходимо для
обеспечения гарантированной верхней границы вероятности ошибки после
декодирования. Учитывая часто требуемое на практике значение вероятности декодирования с ошибкой равное 10−9, код с алгоритмом декодирования,
обеспечивающим наличие такой верхней границы в произвольном канале,
назван в [4] нанокодом.
Конструкция и алгоритм декодирования нанокода преобразования с
дважды стохастической матрицей переходов обеспечивают условия для комплексной защиты информации при однократном введении избыточности.
Отметим, что такие средства защиты обладают научной новизной в классе
задач помехоустойчивого кодирования, что подтверждается как результатами проведения гранта РФФИ [19], так и патентной новизной, в частности
патентами России [6, 14–16, 52–55] и заявкой РСТ [7], успешно прошедшей