Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

Реферат

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

Выполнил:

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.

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

М-последовательности являются периодическими с периодом N = 2ⁿ − 1;
количество символов, принимающих значение единица, на длине одного периода М-последовательности на единицу больше, чем количество символов, принимающих значение нуль;
любые комбинации символов длины n на длине одного периода М-последовательности за исключением комбинации из n нулей встречаются не более одного раза. Комбинация из n нулей является запрещённой: на её основе может генерироваться только последовательность из одних нулей;
сумма по mod 2 любой М-последовательности с её произвольным циклическим сдвигом также является М-последовательностью;
периодическая АКФ любой М-последовательности имеет постоянный уровень боковых лепестков, равный (− 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].

Семейство кодов Касами содержит 2^к последовательностей с периодом 2^n-1. Они считаются оптимальными в том смысле, что для любой «предпочтительной» пары обеспечивается максимальное значение автокорреляционной функции, равное (1+2^к).

Кодовые последовательности Касами реализуются с помощью трех последовательно включенных регистров сдвига (u, v и w) с различными обратными связями (рис. 1.3), каждый из которых формирует свою m-последовательность. Чтобы получить кодовые последовательности Касами с заданными свойствами, последовательности v и w должны иметь различные сдвиги.

Коды Касами длиной 256 бит используются в качестве коротких последовательностей в обратном канале (проект WCDMA) в тех сотах, в которых применяется многопользовательское детектирование.

Рисунок 1.2 - Генератор кодов Касами типа kas (6, m, k), где m и k – циклические сдвиги v- и w-кодов соответственно (см. условные обозначения

к рис. 1.2)

1.2.4 Последовательности Баркера

Последовательность Баркера — это числовая последовательность a₁, a₂, …, a_N, где каждый элемент равен +1 или -1, причём,, для всех .

Последовательности Баркера имеют минимальный уровень боковых лепестков автокорреляционной функции 1/N.

Последовательность Баркера с 11 членами используется в цифровых системах передачи данных.

Псевдослучайные последовательности с малым значением апериодической АКФ способны обеспечить синхронизацию передаваемых и принимаемых сигналов за достаточно короткий промежуток времени, обычно равный длине самой последовательности. Наибольшую известность получили такие последовательности Баркера (табл. 1.1).

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

Таблица 1.1. – Структура последовательности Баркера (N = 7, 11, 13)

Длина	Вид последовательности	Показатель качества
7	+1 +1 +1 −1 −1 +1 −1	9,85
11	+1 +1 +1 −1 −1 −1 +1 −1 −1 +1 −1	12.1
13	+1 +1 +1 +1 +1 −1 −1 +1 +1 −1 +1 −1 +1	14.08

2 ИСПОЛЬЗОВАНИЕ ГЕНЕРАТОРОВ ПСП ДЛЯ ЗАЩИТЫ ИНФОРМАЦИИ

2.1 Функции генераторов ПСП в системах защиты информации

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

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

Генераторы псевдослучайных последовательностей являются неотъемлемыми элементами любой системы защиты, они используются для решения следующих задач:

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

- хеширования информации;

- построения самосинхронизирующихся поточных шифров;

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

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

- внесения неопределенности в работу защищаемых аппаратно-программных средств;

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

Степень защищенности компьютерной системы можно повысить даже за счет всего лишь простой замены N-разрядных счетчиков команд и адреса на генераторы ПСП с числом состояний 2^N.

2.2 Использование генераторов ПСП в шифровании информации

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

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

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

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

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

• нелинейное преобразование F_k , зависящее от секретной информации (ключа k), используемое для построения генератора (рис. 2.3), обладает свойством «размножения» искажений - все выходные (преобразованные) вектора е' возможны и равновероятны независимо от исходного вектора е;

• при инициализации случайными значениями генератор порождает статистически независимые ПСП.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСТОЧНИКОВ ИНФОРМАЦИИ

Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей / М.: КУДИЦ-ОБРАЗ, 2003, 204с.
Ковтун В.Ю. Генераторы случайных и псевдослучайных последовательностей. Статистические тесты. Криптографически безопасные генераторы псевдослучайных последовательностей. Курс лекций. 27.09.2009 – Версия 0.1
Лифшиц Ю. Псевдослучайные генераторы - лекция 9.
Сухинин Б.М. - Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов. Статья. 2010.
http://ru.wikipedia.org/wiki/Псевдослучайная_последовательность.
http://ru.wikipedia.org/wiki/Псевдослучайная_двоичная_последовательность.
http://www.osp.ru/text/print/302/141475.html.
http://cryptolog.ru/?Psevdosluchainye_posledovatelmznosti.

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