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

     Семейство кодов Касами содержит 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     ЗАКЛЮЧЕНИЕ

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

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

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

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