Содержание к диссертации
Введение
2. Уплотнение каналов и помехоустойчивое кодирование сигналов на основе мажоритарного преобразования 20
2.1. Мажоритарное уплотнение каналов 20
2.2. Каскадное мажоритарное уплотнение и кодирование при полной загрузке системы 34
2.3. Повышение помехоустойчивости системы с каскадным мажоритарным уплотнением, с постоянным числом каскадов и жесткими решениями 38
2.3.1. Характеристики мажоритарно уплотненных сигналов при отсутствии помех в канале связи 38
2.3.2. Использование дополнительного канала в модуле разделения с жесткими решениями для повышения помехоустойчивости 41
2.3.3. Совместная обработка со стиранием - 44
2.3.4. Исправление ошибок по модифицированному методу Вагнера 45
2.4. Словная синхронизация мажоритарно уплотненных сигналов 50
Выводы по главе 2 54
3. Помехоустойчивость систем с каскадным мажоритарным уплотнением при передаче информации с приоритетами и при неполной загрузке системы 55
3.1. Методы обеспечения приоритета в помехоустойчивости при мажоритарном уплотнении 55
3.2. Сравнительная эффективность приоритетной передачи количественной информации при мажоритарном уплотнении 59
3.3. Анализ многоканальных систем с каскадным мажоритарным уплотнением и кодированием при неполной загрузке 66
3.3.1. Классификация систем с неполной загрузкой 66
3.3.2. Анализ помехоустойчивости каскадного мажоритарного мультиселека в системах с неполной загрузкой 68
3.3.3. Зависимости между помехоустойчивостью, активностью и блоковой длиной канальных сигналов при мажоритарном уплотнении 69
3.3-4. Системы с программируемой загрузкой 79
3.3.5. Системы с адаптивной загрузкой 85
3.4. Помехоустойчивость каскадных мажоритарно уплотненных сигналов при пакетных ошибках в каналах связи 93
3.4.1. Количественные характеристики для типичных параметров каналов с пакетными ошибками 98
Выводы по главе 3 101
4. Аутентификация субъектов доступа в информационных системах с использованием интерактивных алгоритмов и мажоритарного преобразования сигналов 102
4.1. Общие сведения о проблеме аутентификации информации. Криптоалгоритмы шифрования и хэширования 102
4.2. Использование алгоритмов хэширования для аутентификации субъектов доступа 111
4.3. Интерактивный алгоритм аутентификации, использующий мажоритарное преобразование сигналов 113
4.4. Выбор основных параметров и оценка стойкости крштгозамка
4.5. Возможности использования каскадного мажоритарного уплотнения и кодирования для скремблирования и криптографической зашиты цифровой информации 124
Выводы по главе 4 126
5. Экспериментальная часть и внедрение результатов диссертационной работы 127
5.1. Компьютерное моделирование каскадного мажоритарного кодека-мультиселска 127
5.2. Макетирование двухкаскадного мажоритарного кодека-мультиселека 137
2.1. Описание экспериментального макета 137
2.2. Согласование источников сообщений с различной производительностью в экспериментальном макете 140
2.3. Внедрение результатов диссертационной работы 142
Выводы по главе 5 142
6. Заключение 143
6.1. Положения выносимые на защиту 143
6.2. Преимущество полученных результатов по сравнению с аналогами 143
- Каскадное мажоритарное уплотнение и кодирование при полной загрузке системы
- Методы обеспечения приоритета в помехоустойчивости при мажоритарном уплотнении
- Общие сведения о проблеме аутентификации информации. Криптоалгоритмы шифрования и хэширования
- Компьютерное моделирование каскадного мажоритарного кодека-мультиселска
Введение к работе
Во многих областях современных информационных технологий весьма перспективным оказывается мажоритарное преобразование двоичных сигналов. Мажоритарная логическая функция Maj () - это булевская логическая функция, определенная на двоичном наборе своих аргументов (Ьь Ьэ, ..., bm), где Ъ1 є (0,1) і = 1, m [25,26,32]. Это функция абсолютного большинства, если m - нечетное число, т.е. m = 2t + 1, где t = 1,2,... В этом случае она определяется следующим образом
fl, при#т>т/2
Maj(b„b2,...,bm) = ' (1.1)
[0, при # т < т / 2
Здесь #т~ число символов bj = 1 в наборе из т двоичных символов, bje{0,l}.
Если #т = т/2, что может иметь место при m = 2t, t = 1,2,.., т.е. когда m - четное число, то допустимо различное доопределение мажоритарной операции. При #т = т/2 можно полагать, что Maj () = 1, если #т = т/2, а можно полагать, что Maj (-) = 0, если #т = т/2.
Следует придерживаться всегда одного и того же способа доопределения мажоритарной функции для случая m = 2t, t = 1,2,... Надо заметить, что в случае доопределения функции Maj () при m = 2t, строго говоря, она уже не будет мажоритарной, но мы ее по-прежнему будем называть мажоритарной. Более детальные исследования этой функции при ее использовании для преобразования сигналов в информационных радиоэлектронных системах показывают, что нечетная длина входного набора мажоритарной функции, т.е. m = 2t + 1, t = 1,2,..., дает лучший эффект, чем четная длина, когда m = 2t. Поэтому целесообразно использовать нечетную длину входного набора, что мы и будем предполагать в дальнейшем, если не будет соответствующих оговорок.
Если перейти от множества двоичных символов bj є {0,1} к множеству символов а, {±1} с помощью преобразования [26]
а=1-2Ь (1.2)
то тем самым будет осуществлена подстановка
а = -1**Ь=1. а=1<->Ь = 0. (І.З.а)
Операция умножения, заданная на множестве аіє{±1}, определяется таблицей 1.1 [23].
Таблица 1.1
В случае множества bj є {0,1} этой операции умножения будет соответствовать операция сложения по модулю два, определяемая таблицей 1.2 [23].
Таблица 1.2
Из сравнения таблицы 1.1 и таблицы 1.2 можно увидеть, что они эквивалентны с учетом подстановки (І.З.а). Поэтому в дальнейшем будем использовать таблицу умножения (Табл. 1.1) или таблицу сложения по модулю два (Табл. 1.2) в зависимости от того, отображаются ли двоичные сигналы в множество двоичных символов аіЄ{±1} илиЬ,е{0Д}.
Если обрабатываемые двоичные символы - это множество Ь;б{0,1}» то мажоритарная операция определяется соотношением (1.1). Если же двоичные символы представлены на множестве аіє{±1}, то эквивалентной операции (1.1) будет операция Sign () ("сигнум" - знак), которая определяется следующим образом [23]
(а \ Г 1, прих>0
Sign(x) = Sign 5Х = ' Р (1.3)
V w J [-1, при х < 0
Операция сигнум (1.3) является операцией жесткого ограничения (клиппирова-ния) линейной суммы входного набора из m двоичных символов ase{±l}. Она пе-
реводит произвольный непрерывный аналоговый сигнал S в двоичный биполярный сигнал, как это показано, например, нарисі Л.
РисЛЛ. Операция сигнум -операция жесткого ограничения (клиппирования) График функции сигнум, формула (1-3.) представлен нарис.1.2,а)
Sign х
Signx
->х
-1 а)
X]
О -1
6)
->х
Рис 1.2, График функции Sign (х) (а) при х > <0, и Sign (х) б) при х > х2, х < х,
Однако функция сигнум Sign (х), определяемая соотношением (1,3), определена при условии, что ее аргумент х Ф 0. На практике это выполняется во многих случаях, например, когда x(t) - реализация непрерывного случайного процесса. В частности, когда x(t) - реализация случайного гауссовского процесса. Если используется линейное уплотнение m каналов, и m » 1, то в силу центральной предельной теоремы теории вероятностей (теоремы А.М.Ляпунова) линейный уплотненный сигнал будет иметь гауссовское распределение вероятностей, что как раз соответствует указанному выше случаю. Другим примером такого непрерывного аналогового сигнала является речевой сигнал [8]. Как известно, речевые сигналы имеют у-распределение, и при х^Ов этом распределении имеется 5-функция, со-
16 ответствующая паузам речевого сигнала. Но поскольку в паузах речи всегда есть посторонние шумы, например, тепловые, то реальные речевые сигналы являются непрерывными, причем х Ф О, и их распределение часто аппроксимируют суммой двух гауссовскртх распределений, одно из них - распределение согласных фонем (звуков), другое — гласных [17]. Клипированный речевой сигнал сохраняет хорошую разборчивость речи.
Однако в общем случае аргумент х функции сигнум (1.3) может быть х > 0, х < О, х = 0. В таком случае сигнал S(t), подвергнутый клиппированию с учетом доопределения функции сигнум, будет уже не двоичным, как это имело место на рис.1.1, а троичным, как это показано на рисЛ.З, т.е. это будет троичный сигнал хє{1,0-1).
РисЛЗ. Операция Sign(x) прих >х2, х<х|и
График функции Sign (х) для этого случая представлен на рис.1.2, б). Интервал
от xi до X2, на котором переменная х = 0, будем называть зоной стирания. Концы
этого интервала, т.е. значения Xi и х2, могут доопределяться по разному, например
1, при х > х2 Sign(x) = < 0,прих1 < х < х2 (1Аа) -1, прих < Xj
Sign(x) =
1эприх>х2
0,npHxt <х<х2 (1-4.6) -1, прих кх
1, при х > х2,и с вероятностью р / 2, если х = х 2; Sign(x) = * 0, при х} < х < х 2, и с вероятностью 1-р, если Xj = х = х2; (1.4.в) -1, при х < х, 7 и с вероятностью р / 2, если х = х{; где 0 < р < 1
Способ доопределения будет в каждом случае выбираться, исходя из оптимизации определенных характеристик системы, в которой используется операция сигнум.
Мажоритарная операция (1.1) может быть реализована различными способами. В настоящее время в связи с широким распространением быстродействующей цифровой микроэлектронной техники (микроконтроллеров, микропроцессоров) мажоритарную операцию можно реализовать путем непосредственною подсчета веса входного двоичного набора, поступающего на мажоритарный элемент. Вместе с тем5 эта операция может быть реализована и как логическая (булевская) операция на элементах определенного базиса,
В дальнейшем для нас будет особенно важен случай m = 3, т.е. случай трехвхо-дового мажоритарного элемента. Записав таблицу истинности мажоритарной функции для этого случая, легко установить, что она имеет вид
Maj (blf b2, b3) - bib2 + bfa + b2b3 (1.5)
Блок-схема данного мажоритарного элемента представлена на рис. 1.4 [31 ] -
>м
Рис. 1 А Блок-схема мажоритарного элемента при m - 3
Мажоритарная операция (1.1) и эквивалентная ей операция (1.3), (1.4) находят широкое применение в радиоэлектронных системах. Можно, например, указать отмеченное выше клиппирование речевых сигналов, мажоритарное декодирование линейных циклических кодов [9], Однако в настоящей диссертационной работе предлагаются и разрабатываются другие приложения мажоритарной операции и эквивалентной ей операции сигнум в радиоэлектронных системах и информационных технологиях. Центральными в этих системах и технологиях является именно мажоритарное преобразование, что и объединяет их в общий комплекс систем и технологий, которые можно назвать мажоритарными. Их актуальность особенно проявляется в том, что двоичные (троичные) сигналы, формируемые в результате, наиболее удобны при их преобразовании и обработке на элементах современной микроэлектронной техники и компьютерах. В криптографических преобразованиях является важным, что мажоритарная функция (или эквивалентная ей функция сигнум) являются односторонними (однонаправленными функциями)- Функция f(x) является односторонней (однонаправленной), если по значению аргумента х легко вычислить значение функции f(x), но по значению функции f(x) невозможно (или вычислительно невозможно) определить значение ее аргумента [2]. Другими словами, односторонняя функция f(x) не имеет обратной функции i^'(x). Для мажоритарной функции (операции сигнум) это свойство очевидно: бесконечно много значений аргумента х дают значение Цх) = 1 или f(x)=-l для х > х2или х < Xi соответственно.
Можно указать следующие области и типы радиоэлектронных систем и информационных технологий, где мажоритарная функция (функция сигнум) позволяет получить преимущества по сравнению с традиционными методами:
многоканальные системы и сети связи, в которых осуществляется уплотнение каналов - цифровых источников информации. Это могут быть, например, телеметрические системы, многоканальные системы речевой связи и т.п.;
радиорелейные линии, где разнородная цифровая информация уплотняется и ретранслируется;
тропосферные радиолинии, где разнородная цифровая информация уплотняется и передается по каналу связи с замираниями, которые приводят к пакетированию ошибок;
помехоустойчивое кодирование двоичных данных;
преобразование потоков последовательных двоичных данных в параллельные и обратно;
построение генераторов ключевых потоков (генераторов гаммы) для одно-ключевых криптосистем, использующих аддитивные поточные шифры;
создание алгоритмов аутентификации пользователя в информационных системах;
Теоретическое и экспериментальное исследование ряда этих радиоэлектронных систем и информационных технологий проводится в данной диссертационной работе.
Каскадное мажоритарное уплотнение и кодирование при полной загрузке системы
Будем называть информационную радиоэлектронную систему системой с полной заірузкой, если в каждый момент времени любой источник информации в системе при обращении к нему является активным, т.е. на его выходе имеется информационный символ [31]. Если производительность всех источников информации в системе является одинаковой, то для уплотнения (кодирования) таких источников можно использовать каскадный мажоритарный кодек-мул ьтиселек с постоянным числом і каскадов [12, 23, 25]. Будем называть мажоритарный мультиплексор рис.2.3.а) модулем мажоритарного уплотнения, а селектор мажоритарно уплотненного сигнала рис.2 Аа) - модулем разделения. Используя условное изображение этих модулей, рис.2.3.б) и рис,2,4,б) соответственно, принцип каскадного мажоритарного уплотнения и разделения с постоянным числом каскадов можно пояснить рис.2.7.
При каскадном мажоритарном уплотнении с постоянным числом каскадов в системе с полной загрузкой, как следует из рис.2.7, к уплотняемых источников разбиваются на группы. На рис.2.7 число входов (выходов) каждого модуля уплотнения (разделения) одинаково и равно т, так что эта схема с одинаковыми модулями. Такая структура мультиселека наиболее проста и модули являются однотипными. Хотя, очевидно, возможно использование модулей уплотнения (разделения) с различным числом входов (выходов).
Если стоит задача помехоустойчивого кодирования одного источника, то предварительно необходимо преобразовать его выходные символы из последовательной формы в параллельную. Это можно сделать, например, с использованием коммутатора и набора из к двухъячеечных регистров сдвига, как это предлагается в [12, 25]. Однако преобразование сигналов из последовательной формы в параллельную можно осуществить посредством каскадного мажоритарного безызбыточного уплотнения, используя мажоритарно уплотненные сигналы (3,3/ или (7,7) . Для этого сигналы от кодируемого источника, имеющие последовательную форму, следует разбить на блоки длиной З или 7 символов, где і 2: 1 - число каскадов, и подать эти блоки на вход селектора схемы 3,7, где в модулях разделения используется m = 3; 7 выходов и канальные сигналы (2.11) или (2.12) соответственно.
Таким образом, при использовании в случае необходимости преобразователей сигналов из последовательной формы в параллельную задачу мажоритарного уплотнения многих источников и задачу помехоустойчивого кодирования одного источника можно рассматривать как единую задачу, и мультиселек будет одновременно являться кодеком, так что два последних термина мы в дальнейшем будем использовать как синонимы [25,31].
В [23, 25] проведено исследование помехоустойчивости каскадного мажоритарного кодека с постоянным числом каскадов и найдена оптимальная совокупность нежестких решений, определяемых соотношением (1,4-в), при которых обеспечивается максимальная энергетическая эффективность кодека. Ниже будет предложен и исследован другой метод повышения энергетической эффективности каскадного мажоритарного кодека, в котором используются только жесткие решения. Если уплотняемые (кодируемые) источники имеют различную производительность, кратную длине используемых канальных сигналов, то целесообразно использовать каскадное мажоритарное уплотнение с переменным числом каскадов, принцип построения которого иллюстрируется на рис.2.8.
Для уплотнения с переменным числом каскадов разобьем к уплотняемых источников на Р. групп и информационные символы от источников і-ой группы (i = \J) будем подавать непосредственно на входы модулей уплотнения і-го каскада. Если мультиселек составлен из однотипных модулей уплотнения (разделения) с числом входов (выходов), равным т, то, начиная со второго каскада каждый их этих модулей будет иметь їй входов (выходов), на которых имеются непосредственно информационные символы уплотняемых источников. На рис.2,8 схематически представлены две структуры таких мультиселеков для случаев m = 3, т =2 (рис.2.8.а) и m = 3, m = 1 (рис.2.8.6), В [25] проведено исследование каскадного мажоритарного кодека с переменным числом каскадов. Найдена средняя по всем кодируемым информационным символам вероятность ошибки на декодированный бит, и показано, что в таком кодеке асимптотически, при стремлении длины блока кодируемых информационных символов к бесконечности, вероятность ошибки на декодированный бит стремится к нулю, тогда как скорость кода (а, следовательно, и избыточность) стремится к конечной величине. Такие свойства присущи весьма немногим кодам [27].
Ниже мы предложим и исследуем возможности использования каскадного мажоритарного уплотнения и кодирования с переменным числом каскадов для передачи информации с приоритетами по помехоустойчивости, т.е. с неравной защитой информационных символов от помех, действующих в канале связи.
Наконец, в данном разделе будет рассмотрена помехоустойчивость каскадного мажоритарного метода уплотнения и кодирования в системах с неполной загрузкой, т.е. в случаях, когда не все уплотняемые (кодируемые) источники информации являются одновременно активными.
Методы обеспечения приоритета в помехоустойчивости при мажоритарном уплотнении
Во многих многоканальных радиоэлектронных системах информация, поступающая от различных источников, имеет неодинаковую ценность для получателя. В этих системах естественно возникает необходимость обеспечения более высокой помехоустойчивости при передаче более ценной для получателя информации, т.е. обеспечения приоритета в помехоустойчивости различным уплотняемым источникам. Все уплотняемые источники в общем случае могут быть разбиты на l Nn k групп, и источникам каждой их этих групп необходимо обеспечить определенный приоритет в помехоустойчивости передачи.
Аналогично, приоритет в помехоустойчивости передачи целесообразно обеспечить и при передаче от одного источника цифровой количественной информации, представленной в позиционной системе счисления, поскольку ошибки в различных разрядах при передаче такой информации имеют различную цену для получателя. Именно, ошибки в более старших разрядах более "вредны" поскольку вес этих разрядов более высок.
Код, информационные символы которого имеют различные степени защиты, называется кодом с неравной защитой символов (НЗ-кодом) [44-47], Идея построения таких кодов была сформулирована в [44], а в дальнейшем была развита в работах [45-5-47].
В работе [45] был исследован вопрос об оптимальных линейных НЗ-кодах. Исследовались как линейные блоковые, так и итеративные и каскадные линейные НЗ-коды. Как следует из [45], оптимальным блоковым НЗ-кодом является код Хэмминга и его модификации - усеченный и удлиненный код Хэмминга (частный случай кода Боуза-Чоудхури-Хоквингема - БЧХ), а также код с повторениями. Эти коды и будут в дальнейшем использованы для сравнения их эффективности с эффективностью каскадного мажоритарного кода, предлагаемого автором диссертации и рассматриваемым ниже. Каскадный мажоритарный метод уплотнения позволяет легко обеспечить приоритет в помехоустойчивости передачи несколькими способами: посредством использования уплотнения с переменным числом каскадов и одинаковыми модулями (разд.2.2, рис.2-8), уплотнения с постоянным числом каскадов и различными модулями, а также комбинацией этих способов [23].
Структура каскадного мажоритарного мультиселека с переменным числом каскадов и одинаковыми модулями рассмотрена в разд.2.2, где также рассмотрена передача информации при использовании подобного мультиселека. Различный приоритет в помехоустойчивости при этом обеспечивается за счет того, что информационные символы от источников, входящих в ц-ю приоритетную груп-1 ((1 = 1,7 ) подаются на один из каскадов уплотнения. При этом, очевидно, должно выполняться условие Nn і, и чем большее число каскадов мультиселека проходят информационные символы от источников ц-й приоритетной группы, тем выше будет помехоустойчивость их передачи, поскольку каждый каскад мультиселека обеспечивает определенную степень защиты передаваемого сигнала от помех, действующих в групповом тракте. При этом предполагается, что уплотнение на каждом каскаде содержит избыточность.
Структура каскадного мажоритарного мультиселека с постоянным числом каскадов и различными модулями аналогична структуре с постоянным числом каскадов и одинаковыми модулями, приведенной на рис.2,7, за тем исключением, что модули уплотнения (разделения) могут иметь различное число входов (выходов), различную структуру и блоковую длину используемых канальных сигналов, как в пределах каждого каскада уплотнения и разделения, так и на различных каскадах. Пример такой двухкаскадной струїсгурьі для хп\ = 7; т2 = 3, где Ш] и тг - число входов модулей уплотнения на первом и втором каскадах, приведен в [25]. Различный приоритет в помехоустойчивости при этом обеспечивается за счет того, что при канальных сигналах, имеющих минимальную избыточность, помехоустойчивость передачи зависит от числа входов (выходов) модулей уплотнения (разделения) и типа модулей разделения, и от структуры и блоковой длины канальных сигналов. Варьируя указанные параметры, можно обеспечить разнообразие приоритетов в помехоустойчивости передачи. При этом, как показано в [25], финальная вероятность ошибки при разделении символов приоритетной группы зависит также и от порядка следования различных модулей, которые проходит эта группа символов в мультиселеке. Это свойство не имеет место при линейных методах уплотнения и кодирования.
По существу, все перечисленные методы обеспечения приоритета 0 помехоустойчивости передачи тем или иным образом обеспечивают неравномерное распределение по символам различных приоритетных групп избыточности, вносимой при уплотнении, тем самым осуществляя неравномерное деление ресурса помехоустойчивости мультиселека по различным приоритетным группам.
Общие сведения о проблеме аутентификации информации. Криптоалгоритмы шифрования и хэширования
Информация - один из наиболее ценных продуктов деятельности человека. Во всем мире информация, получаемая в процессе научно-технической, коммерческой и других видов деятельности человека, является весьма дорогостоящим товаром. Многие современные ученые полагают, что ведущие развитые страны мира в настоящее время осуществляют переход от индустриальной фазы своего развития к информационной фазе, на которой информация и информационные технологии будут являться главным стратегическим национальным ресурсом. Жизнь современного общества немыслима без повсеместного использования систем обработки данных, связанных с вводом, хранением, обработкой и передачей информации. Всеобщая компьютеризация помимо выгод несет с собой и многочисленные проблемы, наиболее сложной из которых является проблема информационной безопасности или, другими словами, аутентификация информация. При решении задач аутентификации информации широкое применение находят методы криптографии, т.е. использование специальных алгоритмов преобразования данных (криптоалгоритмов), состоящих из процедур шифрования и расшифрования.
Кроме того, во многих информационных системах, например в алгоритмах электронной цифровой подписи, требуется хэширование, т.е одностороннее сжатие данных. Хэшированием, или хэш-функцией у = h(x) называется такое преобразование последовательности х некоторых символов, (для определенности будем считать, что у и х — двоичные последовательности, а длина х произвольна) в последовательность у фиксированной длины [15]- Последовательность у обычно называют результатом хэширования, хэш-кодом, хэш-образом, дайджестом последовательности (message digest)- Обычно хэш-код у существенно короче, чем длина хэшируемой последовательности х, т.е. у « х.
К кэш-функциям предъявляют следующие требования [15, 16]: - Хэш-функция должна быть односторонней (однонаправленной), т.е. для любого значения ее аргумента х значения у = h(x) вычисляется легко, однако по известному значению у невозможно (за приемлемое конечное время вычислений) вычислить обратную функцию х = f _1(у). - Хэш-код h(x) должен зависеть от всех символов хэшируемых данных» а также от их взаимного расположения, т.е. хэш-код должен быть чувствителен к любым изменениям хэшируемых данных, - Хэш-функция h(x) должна быть "свободной от коллизий". Коллизией называется ситуация, когда одно и тоже значение хэш-функции у = h(x) соответствует различным значениям аргумента х, т.е. когда у = h(xi) - h(x2), где Х] х2- Поскольку, как указывалось выше, блоковая длина у обычно значительно меньше, чем длина х, то у всякой хэш-функции есть большое число коллизии, т.е- таких пар Х и Х2, для которых h(xi) = h(x2), xi х2
Хэш-функции, обладающие этими свойствами, называются криптографически стойкими хэш-функциями.
Мажоритарная функция, определяемая (1 Л) выполняет главное условие, предъявляемое к функциям хэширования - она является односторонней. Действительно, бесконечно много значений аргумента х дают значение хэш-функции h(x) = 1 или h(x) = 0, и по значению аргумента х легко вычислить значение у = h(x), тогда как обратное вычисление невозможно- Это свойство однонаправленности мажоритарной функции возможно использовать для криптографической защиты данных при создании алгоритмов шифрования и хэширования.
По существующим мировым стандартам, хэширование осуществляется на основе алгоритмов блочного шифрования, и стойкость получаемой хэш-функции зависит от стойкости криптоалгоритма, используемого при ее вычислении [41]. Соответственно, сложность реализации процедуры хэширования, требуемый объем памяти и потребное быстродействие при программной или аппаратной реализации алгоритма хэширования также зависят от аналогичных параметров используемого криптоалгоритма. Если при вычислении хэш-функции не использовать крипто графическое преобразование хэшируемых данных, то злоумышленнику не составит труда получение коллизий. Например, в качестве хэш-кода можно использовать простую контрольную сумму по некоторому модулю хэшируемых данных [41]. Однако, очевидно, можно легко сформировать большое число различных последовательностей, имеющих одинаковую контрольную сумму, т.е. получить желаемые злоумышленником коллизии. Поэтому стойкие хэш-функции могут быть получены только при использовании криптоалгоритмов,
В настоящее время известны три криптоалгоритма, стандартно используемых для этих целей [41]: американский алгоритм DES (Data Encryption Standard), отечественный алгоритм ГОСТ 28147-89 (стандарт криптозащиты данных - СКЗД) и Европейский стандарт IDEA (International Data Encryption Algorithm), Эти алгоритмы имеют высокую стойкость, особенно отечественный стандарт, но довольно сложны в реализации и имеют низкое быстродействие, что в некоторых случаях является большим препятствием при использовании их для целей аутентификации. Поэтому поиск новых, более перспективных алгоритмов хэширования был одной из целей настоящей диссертационной работы.
За основу разрабатываемого алгоритма хэширования был взят криптоалгоритм "Гамма", использующий мажоритарное преобразование входных данных. Криптоалгоритм "Гамма" официально зарегистрирован в Российском агентстве по правовой охране программ для ЭВМ, баз данных и топологии интегральных схем (Рос АПО) [7], а также запатентован [44]. Сравнение свойств криптоалгоритма "Гамма" с выбранными прототипами показало, что он превосходит их по многим параметрам, из чего следует, что качество получаемой хэш-функции, требуемые вычислительные затраты, объем памяти и быстродействие предлагаемого алгоритма хэширования также будут лучше известных стандартных алгоритмов.
Компьютерное моделирование каскадного мажоритарного кодека-мультиселска
В настоящее время во многих сферах деятельности желательна зашита информации, передаваемой по каналам связи, хранимой в банках данных, обрабатываемой средствами вычислительной техники, от несанкционированного досіупа к этой информации. В случае речевых сигналов такую операцию обычно называют скремблированием [15],
Защиту информации от несанкционированного доступа, и, в частности, скремблирование, можно обеспечить, используя криптографическое преобразование информации - шифрование- В одноключевых криптосистемах обратную операцию расшифрования может легко осуществить лишь санкционированный получатель, которому эта информация предназначена, т.к. только он обладает секрет-ным ключом, необходимым для выполнения этой операции.
Существующие стандарты шифрования (DES в США, ГОСТ 28147-89 в России, IDEA в ЕС), обеспечивая высокую степень защиты, имеют существенные недостатки - они достаточно сложны в реализации и требуют больших вычислительных затрат на выполнение операций шифрования и расшифрования [2,15].
Практическая стойкость того или иного шифра оценивается тем потребным числом стандартных вычислительных операций, которые должен осуществить несанкционированный получатель, не знающий секретного ключа, чтобы дешифровать информацию. Если при этом используется вычислительная техника с известным быстродействием, то обычно принято пересчитывать число операций, затрачиваемых на дешифрование, в потребное время, за которое эта дешифрация может быть осуществлена несанкционированным получателем.
При многих видах коммерческой деятельности, а также при передаче речевых сигналов, высокая степень защиты, когда на дешифрование несанкционированный получатель затрачивает месяцы или годы, обычно не требуется, т.к., как правило, защищаемая информация устаревает, за время, измеряемое часами или единицами суток. Поэтому для защиты этой информации требуются криптоалгоритмы, обеспечивающие именно такую степень защиты, но простые в реализации и свободные от недостатков, указанных выше стандартных алгоритмов шифрования. Желательно, чтобы эти криптоалгоритмы использовали секретный ключ небольшой длины, чтобы легко можно было бы обеспечить фазирование шифратора и дешифратора, чтобы дешифрование криптограммы с ошибками не приводило к неограниченному размножению ошибок в дешифрованных данных, чтобы объем криптограммы значительно не превышал объем шифруемого открытого текста (в идеальном случае эти объемы должны быть равны).
Оказывается, что подобные криптоалгоритмы могут быть реализованы с использованием каскадного мажоритарного кодека-мультиселека. Важное свойство мажоритарной операции и эквивалентной ей функции cp(S) = Sign S состоит в том, что она не имеет обратной функции (p !(S), такой, которая позволила бы по заданному значению функции Sign S однозначно определить ее аргумент S, т.к. определенный знак "+Т1 или "-" имеют бесконечно много возможных значений аргумента S. Поэтому функция cp(S) = Sign S является односторонней (однонаправленной); для заданного S всегда легко определить его знак, т.е. Sign S, тогда как по знаку невозможно единственным образом определить S.
Основываясь на односторонности функции tp(S) = Sign S в ряде работ были предложены нелинейный блочный шифр и нелинейный поточный шифр, которые явились основой для разработки конкретных алгоритмов, способов и устройств шифрования [32]. При поточных криптоалгоритмах каскадный мажоритарный мультиплексор используется как нелинейный генератор ключевого потока. Порождаемый им ключевой поток ("гамма") поразрядно складывается по модулю два с символами открытого текста, в результате чего порождается криптограмма.
Нелинейный блочный шифр, реализуемый на основе каскадного мажоритарного кодека-мультиселека использует перестановки канальных сигналов, задаваемые секретным ключом. Наиболее перспективными при этом являются модули уплотнения (разделения) с числом входов (выходов) равным 3 или 7, поскольку при этом возможно безызбыточное уплотнение, и тогда объем криптограммы оказывается равным объему шифруемого открытого текста [25,31] 1. Предложен алгоритм хэширования двоичных последовательностей, основанный на мажоритарном преобразовании входных данных. 2. Разработан алгоритм аутентификации пользователя в информационных системах, использующий хэширование случайных последовательностей- Разработан протокол пользователя такого алгоритма, рассмотрены возможные реализации основных блоков алгоритма. 3- Рассмотрена возможность использования каскадного мажоритарного уплотнения и кодирования для скремблирования и криптографической защиты цифровой информации.
