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

Министерство  образования и науки Украины

Национальный технический университет

«Харьковский  политехнический институт» 
 

Кафедра автоматики и управления в технических системах 
 
 
 
 
 

Реферат

«Псевдослучайные последовательности и их применение для защиты информации» 
 
 
 
 
 

     Выполнил:

cт. гр. АП-15б

     Юраков А.А. 

     Проверил:

     проф. каф. АиУТС

     Ивашко А.В.  
 
 
 

Харьков 2010

     ВВЕДЕНИЕ

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

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

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

 

     1 ОПИСАНИЕ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

     1.1 Основные аспекты  псевдослучайных последовательностей (ПСП)

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

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

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

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

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

     Псевдослучайная двоичная последовательность — частный случай ПСП, в которой элементы принимают два возможных значения 0 и 1 (или -1 и +1 ).

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

     1) Количество "1" в каждом периоде должно отличаться от количества "0" не более, чем на единицу.

     2) В каждом периоде половина серий (из одинаковых символов) должна иметь длину один, одна четверть должна иметь длину два, одна восьмая должна иметь длину три и т.д. Более того, для каждой из этих длин должно быть одинаковое количество серий из "1" и "0".

     3) Предположим, у нас есть две копии одной и той же последовательности периода p, сдвинутые относительно друг друга на некоторое значение d. Тогда для каждого d, 0 <= d <= p-l, мы можем подсчитать количество согласованностей между этими двумя последовательностями Ad, и количество несогласованностей Dd. Коэффициент автокорреляции для каждого d определяется соотношением (Ad - Dd)/p и эта функция автокорреляции принимает различные значения по мере того, как d проходит все допустимые значения. Тогда для любой последовательности, удовлетворяющей правилу 3, автокорреляционная функция (АКФ) должна принимать лишь два значения.

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

     Последовательность, удовлетворяющая правилам 1-3 часто  именуется "ПШ-последователъностъю", где ПШ обозначает "псевдо-шумовая". К анализируемой последовательности применяется широкий спектр различных  статистических тестов для исследования того, насколько хорошо она согласуется с допущением, что для генерации использовался совершенно случайный источник.

     1.2 Разновидности ПСП

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

     1.2.1 М-последовательности

     М-последовательности или последовательности максимальной длины (англ. Maximum length sequence, MLS) — псевдослучайные последовательности, нашедшие широкое применение в широкополосных системах связи. Как правило, используются двоичные М-последовательности, члены которых состоят из чисел 1 и 0.

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

     Теоретически, используя n-разрядный регистр и  соответствующим образом подобранную  логику обратной связи, можно получить последовательность любой длины N в  пределах от 1 до 2ⁿ включительно. Последовательность максимальной длины, или m-последовательность, будет иметь период 2ⁿ-1.

     Такие последовательности обладают следующими свойствами:

1. М-последовательности являются периодическими с периодом N = 2ⁿ − 1;
2. количество символов, принимающих значение единица, на длине одного периода М-последовательности на единицу больше, чем количество символов, принимающих значение нуль;
3. любые комбинации символов длины n на длине одного периода М-последовательности за исключением комбинации из n нулей встречаются не более одного раза. Комбинация из n нулей является запрещённой: на её основе может генерироваться только последовательность из одних нулей;
4. сумма по mod 2 любой М-последовательности с её произвольным циклическим сдвигом также является М-последовательностью;
5. периодическая АКФ любой М-последовательности имеет постоянный уровень боковых лепестков, равный (− 1 / N).

     

     Рисунок 1.1 - Автокорреляционная функция для m-поседовательности: а) апериодическая, б) периодическая

     1.2.2 Последовательности Голда

     Коды  Голда — тип псевдослучайных последовательностей. Значимость этих последовательностей происходит из-за их очень низкой взаимной корреляции. Применяются в CDMA и GPS.

     Оптимальные автокорреляционные свойства могут быть получены и для М-последовательностей, однако, для реализации принципа коллективного доступа необходим большой набор кодов одинаковой длины с хорошими взаимокорреляционными свойствами. Поэтому используется особый класс ПШ-последовательностей, который называют последовательностями Голда. Коды Голда не только позволяют получить большой набор последовательностей, но также и однородные и ограниченные значения взаимокорреляционной функции. Коды Голда хорошо подходят для использования в качестве длинных скремблирующих кодов для беспроводного множественного доступа с кодовым разделением каналов (2¹⁸ − 1 кодов Голда для передачи информации от базовой станции к подвижному объекту, и 2¹⁶ кодов усеченной последовательности для обратного направления).

     В CDMA-системах чаще всего применяются  псевдослучайные последовательности Голда и, обеспечивающие малый уровень  выбросов ВКФ. Коды Голда с периодом 2ⁿ-1 формируются на основе двух m-последовательностей с отбором так называемых «предпочтительных пар» (preferred pairs), имеющих трехзначную функцию автокорреляции (-1,-о?(t), о? (t)-2), где

     

     Последовательности  Голда могут быть сгенерированы  путем суммирования по модулю 2 двух М-последовательностей одинаковой длины. Результирующие Коды Голда имеют  ту же самую длину как и исходные М-последовательности (рис 1.2).

     

     Рисунок 1.2 - Генератор кодов Голда (T – элемент регистра сдвига; & – схема совпадения; + – сумматор по модулю 2)

     В проекте WCDMA специфицированы три  типа кодов Голда: первичный и  вторичный ортогональные коды Голда (оба длиной 256 бит) и длинный код.

     Ортогональные коды Голда создаются на основе m-последовательности длиной 255 бит с добавлением одного избыточного символа. Первичный  синхрокод имеет апериодическую автокорреляционную функцию и используется для первоначального вхождения  в синхронизм. Вторичный синхрокод  представляет собой немодулированный ортогональный код Голда, который  передается параллельно с первичным синхрокодом. Каждый вторичный синхрокод выбирается из 17 различных кодов Голда {C1,...,C17}.

     Длинный код для прямого канала представляет собой фрагменты кода Голда длиной 40 960 чипов. Система связи на базе WCDMA асинхронна, и соседние базовые  станции используют различные коды Голда (всего их 512), повторяемые каждые 10 мс. Асинхронный принцип работы базовых станций делает их независимыми от внешних источников синхронизации. Предполагается применять длинный  код и в обратном канале, однако только в тех сотах, где не задействуется  режим многопользовательского детектирования.

     1.2.3 Последовательности Касами

     Коды  Касами — тип псевдослучайных последовательностей. Применяются в CDMA. Значимость этих последовательностей происходит из-за их очень низкой взаимной корреляции. Код Касами длины N = 2^m − 1, где m — четное целое число, может быть получен, беря периодические выборки из М-последовательности и выполняя суммирование по модулю 2 на циклически сдвигаемых последовательностях. Выборки берутся через каждые s = 2^{m / 2} + 1 элементов М-последовательности, чтобы сформировать периодическую последовательность и затем прибавляя эту последовательность постепенно к первоначальной М-последовательности по модулю 2, чтобы сформировать s = 2^{m / 2} последовательностей Касами. Взаимная корреляционная функция двух последовательностей Касами принимает значения [-1, -s, s-2].