Applications of two-faced processes to pseudorandom number generation.pdf Генераторы случайных и псевдослучайных чисел (ГСЧ и ГПСЧ) находят широкое применение в системах защиты информации, причём используемые в таких системах генераторы должны удовлетворять целому ряду требований, одно из которых - статистическая неотличимость порождаемых генератором последовательностей от бернуллиевских с p(0) = p(1) = 1/2 [1]. С другой стороны, ГПСЧ по своему построению существенно отличаются от бернуллиевских процессов: энтропия (на символ) у выходной последовательности значительно меньше одного бита, тогда как у полностью случайной - один (см. описание схемы ГПСЧ, например, в [2, 3]). Напомним определение энтропии стационарного процесса условная энтропия порядка m, m = 1,и (предельная) энтропия даются равенствами hm = - Y, Mu) Y, Mv/u)logMv/u), hж = lim hm [4]. «€{0,1}™-! ve{o,i} В работе описываются процессы, для которых с вероятностью 1 в порождаемой последовательности x1x2 • • • для каждого двоичного слова u выполняется равенство lim vt(u)/(t - |u|) = 2-|u|, где vt(u) -число встреч слов u в последовательности x1 •••Х|«|, x2 • • • X|«|+1 ,•••, xt-|«|+1 •••xt, что должно выполняться для полностью случайных последовательностей. Однако энтропия процесса может быть много меньше единицы, что обычно выполняется для ГПСЧ. Сначала определим два семейства процессов Tk,n и Tk,n, где k =1, 2, • • • и п G (0,1) - параметры. Оба процесса - марковские цепи связности, или памяти k, которые генерируют буквы из алфавита {0,1}. Определим их матрицы переходов по индукции: матрица для Т1п определяется равенствами PTl п (0/0) = п, PTl п (0/1) = 1 - п (очевидно, PTl п(1/0) = 1 - п, PTl п(1/1) = п). Процесс определяется равенствами Pt1 п(0/0) = 1 - п, Pt1 п(0/1) = п. Предположим теперь, что Tk,n и Tk,n определены. Тогда Tk+1,n и Tk+1,n определяются так: PTfc+i (0/0u) = PTfc (0/u), PTfc+i (1/0u) = Pr(fc,n)(1/u), PT(fc+1,n)(0/1u) = PT(fc,n) (0/u) , PT(fc+1,n)(1/1u) = PT(fc,n) (1/u) , и наоборот, PT(fc+1,n) (0/0u) = PT'(fc)n) (0/u) , PT(fc+1,n) (1/0u) = PT(fc,n) (1/u) , PT(fc+1,n) (0/1u) = PT(fc,^0^ PT(fc+1,n) (1/1u) = PT(k,n)(1/u) для каждого u е {0,1}k (здесь vu - конкатенация слов v и u). Например, PT(2,n)(0/00) = п, Pt (2,п) (0/01) = 1 - п, Pt (2,п) (0/10) = 1 - п, Pt (2,п) (0/11) = п. Будем считать, что начальное распределение равномерное на {0,1}k, т. е. P{x1... = = u} = 2-k для u е {0,1}k. Теорема 1. Пусть последовательность x1x2 ... порождается процессом Т (^п) (или Т^п)), k ^ 1 и u - двоичное слово длины k. Тогда i) имеет место P (Xj+1 ...Xj+k = u) = 2-|u|; (1) ii) для каждого п е (0,1) энтропия hk процессов T(k,п) и Т^п) равна 1 бит, тогда как предельная энтропия h^ равна - (п log2 п + (1 - п) log2(1 - п)). Определение 1. Назовём случайный процесс двуликим k-го порядка, если для него выполняются свойства i и ii. Поясним название «двуликие». Если мы рассматриваем слова длины, не превосходящей k, то они все равновероятны (энтропия равна 1), т.е. такие, какие должны быть у полностью случайного процесса. С другой стороны, если длина слова больше k, то энтропия меньше единицы, распределение вероятностей слов отличается от равномерного и процесс явно не «полностью случайный». Рассмотрим на простом примере свойства этих процессов. Возьмём возможные типичные последовательности для Т(1, п) и Т(1, п) для п = 1/5. Пусть последовательности такие: 010101101010100101... и 000011111000111111000 ... Каждая последовательность содержит примерно половину единиц и нулей и поэтому энтропия первого порядка равна 1, что должно выполняться для полностью случайной последовательности. С другой стороны, последовательности не выглядят как случайные, так как они содержат слишком длинные подпоследовательности вида 101010 ... или 000 ... 11111... Поэтому энтропия второго и высших порядков меньше 1. Другими словами, данные последовательности имитируют полностью случайные, если учитываются только слова длины 1; при большей длине это не выполняется. Следующая теорема показывает, что, в некотором смысле, двуликих процессов довольно много. Теорема 2. Пусть X = x1x2 ... и Y = y1 y2 ... - случайные процессы и процесс Z = z1z2 ... задаётся равенствами z1 = x1 фy1, z2 = x2фy2,... Тогда если X - двуликий процесс k-го порядка (k ^ 1), то Z тоже двуликий k-го порядка. Двуликие процессы k-го порядка имитируют полностью случайные только при длине слова, не превосходящей k. Оказывается, существуют процессы, для которых это свойство выполняется для слов любой длины. Теорема 3. Существуют процессы, для которых (1) выполняется для слов любой длины. В работе показано, как на основе двуликих процессов могут быть построены ГСЧ и ГПСЧ с доказанными статистическими свойствами.

Скачать электронную версию публикации