14. Генераторы псп в задачах защиты информации. Требования к генераторам псп.

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

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

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

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

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

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

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

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

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

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

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

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

Примеры:

1. Линейный конгруэнтный метод

Данный алгоритм был предложен Д. Х. Лемером в 1948 году. Рекуррентная формула выглядит следующим образом:

x_n = (ax_n − 1 + c) mod m.

2. Алгоритм Блюма-Блюма-Шуба

x_n = (x0)^{2^n mod (p − 1)(q − 1)} mod pq.

15. Классификация генераторов псп. Принципы построения криптографических генераторов псп.

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

На рис. 1 показана классификация генераторов ПСП. В качестве параметров выбраны:

1. тип используемого нелинейного преобразования;

2. структура генератора;

3. наличие или отсутствие внешних источников случайности.