Эффективные генераторы псевдослучайных чисел, основанные на двуличных процессах

Размещено на http://www.allbest.ru/

Оглавление

Сокращения

Двуличные (two-faced) процессы

Тесты

Постановка задачи

Построение генератора псевдослучайных чисел на основе двуличных процессов. Описание алгоритма

Результаты

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

Результаты

Выводы на основе первых двух частей

Шифр Вернама. Описание шифра Вернама

Модификация шифра Вернама

Заключение

Список литературы

Приложения

Таблица 1. Тест «хи-квадрат» для ДГ 56+43+99+995

Таблица 2. Тест РСЕ для ДГ 56+43+99+995

Таблица 3. Тест «хи-квадрат» для ВГ

Таблица 4. Тест РСЕ для ВГ

Таблица 5. Тест «хи-квадрат» для файла «Парадокс Глебова»

Таблица 6. Тест РСЕ для файла «Парадокс Глебова»



Сокращения

ДГ - генератор псевдослучайных чисел, основанный на двуличных процессах;

ВГ - встроенный в Microsoft Visual Studio 2005 генератор псевдослучайных чисел;

Тест РСЕ - тест на максимальный размер серии единиц.



Двуличные (two-faced) процессы

Понятие двуличных процессов было взято из статьи B. Ryabko, V. Monarev “Using information theory approach randomness testing”.

Пусть наш алфавит состоит из 0 и 1. Определим случайные процессы

и ,

которые и называются двуличными, индуктивно с помощью матрицы процесса (при этом k называется глубиной процесса, а - параметром процесса):

, . Аналогично

, .

То есть, при подаче на вход данного процесса символов и параметра p на выходе будет вероятность того, что следующий элемент будет единицей или нулем. Если обозначить эти вероятности за

и ,

то формулы двуличных процессов можно переписать следующим образом:

, , , ;



, , , ;

, ;

, .

В вышеназванной статье упоминается следующая теорема.

Теорема 1. s-значная энтропия Шеннона процессов

равна 1 ,

а предел энтропии Шеннона

.

Это значит, что при достаточно больших длинах блоки длины s равновероятны, а энтропия процессов совпадает с энтропией последовательности, в которой единица появляется с вероятностью p, а ноль - с вероятностью 1-p (или наоборот). Однако остается непонятным, какой длины должна быть последовательность, чтобы блоки длины меньше k были в ней равновероятны. Вполне возможно, что длина эта будет слишком большой для того, чтобы признать последовательность случайной.

Тесты

Для проверки случайности полученной последовательности будет использоваться тест «хи-квадрат». Ниже дано краткое описание этого теста.

Пусть у нас есть n элементов, каждый из которых имеет k возможных значений. Мы полагаем, что вероятность того, что элемент будет иметь i-ое значение - , а всего i-ых значений среди n переменных - . Составляем сумму

.

По теореме Пирсона,

.

По таблице распределения находим

.

Запускаем алгоритм, дающий нам n элементов, 100 раз, и смотрим, сколько раз

В нашем случае для каждого запуска алгоритма подсчет будет производиться 10 раз: на длинах от . При этом для каждого n на равномерность будут проверяться блоки длины от 1 до (т.е. будем полагать, что для блока длины s ).

Еще будет использоваться тест РСЕ. Суть его заключается в том, что в сгенерированной последовательности находится максимальное число подряд стоящих единиц. Этот тест будет проходиться 20 раз.



Постановка задачи

Используя формулы двуличных процессов и ВГ (используемый для определения первых элементов процессов и для «подбрасывания монетки» при генерации) создать ДГ. Параметр р задается изначально. Тестировать его вышеперечисленными тестами вместе с ВГ. При этом если ВГ прошел тест «хи-квадрат», то в тесте РСЕ считать его эталонным. В этом случае ДГ пройдет тест РСЕ, если результаты теста будут близки к результатам ВГ. Добиться приемлемых результатов для как можно меньшего значения параметра р.

Убрать «подбрасывание монеты» с помощью ВГ. Использовать вместо этого «подбрасывание монеты» с помощью считывания очередного бита из некоторого файла.

Построение генератора псевдослучайных чисел на основе двуличных процессов. Описание алгоритма

На вход подаются значения - глубин процессов - и p. Для каждого процесса первые бит задаются случайно. Генерация одного процесса происходит следующим образом:

Берем последние бит последовательности;

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

Встроенный генератор выдает случайное число . Если , добавляем к последовательности 1, иначе - 0;

Повторяем шаги 1-3.

Таких процессов может быть несколько(2,3,4). В этом случае сгенерированные элементы складываются по модулю 2, и давая элемент результирующей псевдослучайной последовательности. Она и будет проверяться тестами «хи-квадрат» и РСЕ.

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

Утверждение 1.

;

.

Доказательство: докажем 1. Предположим что

.

Возможны два варианта:

, . Тогда ;

. Тогда

Аналогично рассмотрим случай

Тогда



Тогда

Отсюда следует, что 1 верно, 2 доказывается аналогично.

Пример 1: возьмем два процесса:

и , где .

Пусть начало первого процесса - 1, а второго - 00, а ВГ в генерирует числа b=0.2, 0.95, 0.49, 0.07. Применяем вышеописанный алгоритм:

Берем 1 для первого процесса и 00 для второго;

следующий элемент процесса - 0.

следующий элемент процесса - 0. Значит, первый элемент генерируемой последовательности равен 0+0=0.

Аналогично для второго элемента:

Берем 0 и 00;

следующий элемент - 1.



следующий элемент - 1. Следовательно, второй элемент генерируемой последовательности равен 1+1=0.

Результаты

Один процесс не дает псевдослучайную последовательность на длинах от . Два процесса дают хорошие результаты для . Однако такие большие значения параметра нас не интересуют. Для трех процессов наилучшие результаты получились для комбинации при Для четырех процессов наилучшие результаты получились для и . Результаты тестов «хи-квадрат» и РВЕ для последнего случая и для ВГ представлены в приложении. Из них, очевидно, следует, что ДГ успешно выдержал оба теста.

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

У описанного в первой части генератора есть существенный недостаток - он использует встроенный генератор. Во второй части данной работы будет предложен способ обойтись без него. Для этого достаточно иметь файл с данными размера 512 Кб.

Будем рассматривать файл как последовательность бит. Предположим, что единиц в этой последовательности меньше, чем нулей и

- параметр двуличного процесса (что будет, если это не так - после алгоритма). Для одного процесса последовательность действий выглядит так:

Шаги 1-2 алгоритма из первой части;

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

Повторяем шаги 1-2.

Теперь очевидно, почему допущения о количестве единиц и их частоты возможны. Для частоты важно только одно: , ибо единственное, что надо знать, какая из величин больше: . Поэтому если бы мы положили , ничего бы не изменилось. Если же в исходном файле у нас единиц больше, чем нулей, тогда чаще будут случаться «редкие» события. По сути это означает, что вместо процесса у нас будет процесс , что на случайность практически не влияет.

Пример 2: данные те же самые, что и в примере 1, только вместо b берем файл, начальные биты которого - 1001. Действуем по вышеописанному алгоритму:

Берем 1 и 00.

редкое событие.

Первому процессу соответствует 1, второму - 0. Поэтому первый генерирует 1, а второй - 0. Отсюда элемент результирующей последовательности равен 1+0=1;

То же самое, что и на шаге 1;

Теперь первому процессу соответствует 0, а второму - 1. Следовательно, первый генерирует 0, второй - 1, а в результате получаем 0+1=0. Таким образом, мы сгенерировали результирующую последовательность 11.



Результаты

Воспользуемся генератором из первой части. Он дает приемлемые значения для (почему дальше проверять не нужно - в третьей части). В реальных файлах частоты единиц гораздо выше. У меня, на примере 100 разнообразных файлов, получилось . Как и предполагалось, ДГ давал хорошие результаты для разнотипных файлов. В приложении приведены результаты проверки последовательности, полученной из текстового файла «Парадокс Глебова».

Выводы на основе первых двух частей

Теперь можно по-другому представить ДГ из первой части. Пусть у нас есть некоторая последовательность, в которой 1 встречается значительно реже, чем 0, т.е. последовательность низкоэнтропийная и короткая. Из этой последовательности, используя алгоритм из второй части, можно получить высокоэнтропийную последовательность. Если при этом нам будет слишком мало той последовательности, которая у нас есть, то можно приписать к ней саму себя столько раз, сколько нужно. При этом

.

То есть, последовательность не является случайной (иначе энтропия была бы равна 1), ее можно сжать в 1000 раз, но статистически от случайной она неотличима.

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

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

Шифр Вернама. Описание шифра Вернама

Пусть Алиса хочет передать Бобу сообщение A, K - некоторая последовательность.

Алиса вычисляет В=А+К и отсылает Бобу. Боб вычисляет С=В+К=А. Эта система передачи данных и называется шифром Вернама. При этом K называется ключом.

Ключ должен обладать следующими свойствами:

Он должен быть случайным;

;

Он может применяться только один раз.

Теорема 2 (свойство шифра Вернама).

Пусть Алиса передала Бобу сообщение A. Пусть - некоторый случайный ключ. Тогда

.

Это свойство называется абсолютной криптографической стойкостью.

Однако у шифра Вернама есть один большой недостаток: для того, чтобы Боб мог расшифровать сообщение, Алиса должна ему передать ключ.

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

Модификация шифра Вернама

У Алисы и Боба есть ДГ, первые бит каждого процесса заданы одинаково;

Алиса берет небольшое число k, тайно передает его Бобу, переводит его в двоичную систему, получает последовательность битов ;

Алиса получает , n выбирается так, чтобы

,

где А - сообщение, которое Алиса хочет передать Бобу;

Используя ДГ из второй части (), Алиса получает псевдослучайную последовательность, по длине равную А. Это и будет ключ K;

Алиса вычисляет и посылает B Бобу;

Боб переводит число k в двоичную систему и повторяет 3-й и 4-й шаги Алисы (только на 4-м шаге длина псевдослучайной последовательности должна равняться В);

Боб вычисляет , расшифровывая сообщение Алисы.

В первый раз число k можно передать по сверхнадежному каналу (устно, объявление и пр., но не через системы с меньшей, чем шифр Вернама, надежностью!), в последующие разы его можно указывать в тексте передаваемого сообщения. Как было замечено выше, система будет работать даже если k=0. Также надо следить, чтобы среди использованных битовых последовательностей

.



Заключение

генератор псевдослучайное число двуличный процесс

Подведем итоги. Фактически в работе была решена следующая задача: пусть у нас есть некая произвольная, сколь угодно низкоэнтропийная последовательность. С ее помощью, используя ДГ, мы получаем псевдослучайную последовательность, для которой, однако, , т.е. ее можно сжать в 1000 раз. Также этот ДГ был применен для модификации шифра Вернама, суть которой заключается в том, что ключи не передаются, а генерируются на местах. В целом я считаю, что данная работа рассказала об актуальных на сегодняшний день задачах, связанных со случайными последовательностями.



Список литературы

Ryabko B.Y., Monarev V.A. Using information theory approach randomness testing // Journal of statistical planning and inference, №133, 2005;

Боровков А.А. Математическая статистика, Новосибирск: Наука, 1997;

Нагаев С.В. Математическая статистика: Курс лекций для студентов мат. фак., Новосибирск: НГУ, 1973.

Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации, М: Горячая линия - Телеком, 2005;



Приложения

Таблица 1. Тест «хи-квадрат» для ДГ 56+43+99+995

	11	12	13	14	15	16	17	18	19	20
S =1
0.5	40	45	43	43	52	48	47	49	46	57
0.1	6	7	6	11	8	11	13	14	9	13
0.01	0	0	1	0	2	2	1	4	3	3
S=2
0.5	45	40	49	52	50	51	53	47	41	43
0.1	7	6	4	10	7	9	12	16	9	9
0.01	0	0	0	0	1	0	3	2	2	2
S=3
0.5	46	44	57	51	51	52	51	54	42	45
0.1	9	11	11	13	9	9	12	16	15	14
0.01	1	1	2	2	1	1	0	2	3	4
S=4
0.5	53	46	53	40	47	52	53	56	38	43
0.1	10	11	11	14	10	10	13	14	12	14
0.01	3	3	2	1	0	1	1	1	3	4
S=5
0.5	59	55	61	53	54	43	50	55	48	52
0.1	14	10	11	11	11	12	9	7	14	11
0.01	1	0	1	0	2	1	2	2	0	4
S=6
0.5	-	62	60	58	53	54	54	61	43	47
0.1	-	13	14	13	9	14	15	14	16	16
0.01	-	2	3	1	0	1	2	1	3	3
S=7
0.5	-	-	-	54	62	49	51	53	50	56
0.1	-	-	-	15	13	9	16	14	10	13
0.01	-	-	-	3	3	2	0	0	0	1
S=8
0.5	-	-	-	-	-	54	52	49	59	56
0.1	-	-	-	-	-	8	13	7	7	11
0.01	-	-	-	-	-	1	1	1	0	4
S=9
0.5	-	-	-	-	-	-	-	59	54	52
0.1	-	-	-	-	-	-	-	14	15	15
0.01	-	-	-	-	-	-	-	3	1	3
S=10
0.5	-	-	-	-	-	-	-	-	-	51
0.1	-	-	-	-	-	-	-	-	-	6
0.01	-	-	-	-	-	-	-	-	-	1

Таблица 2. Тест РСЕ для ДГ 56+43+99+995

19	18	18	17	17
17	19	17	26	18
20	20	23	21	19
18	19	21	18	19

Таблица 3. Тест «хи-квадрат» для ВГ

	11	12	13	14	15	16	17	18	19	20
S =1
0.5	51	49	58	64	58	52	55	48	41	48
0.1	12	16	12	13	16	14	9	9	9	13
0.01	1	3	0	2	2	0	1	1	2	2
S=2
0.5	47	45	41	48	53	58	48	52	44	51
0.1	9	12	10	12	14	10	9	11	9	7
0.01	0	0	0	1	2	1	0	0	0	0
S=3
0.5	46	45	44	48	48	58	50	47	40	42
0.1	9	9	1	7	11	14	12	9	11	9
0.01	0	0	0	1	2	3	3	1	0	1
S=4
0.5	44	49	44	55	54	56	55	47	49	52
0.1	11	11	5	8	11	10	9	10	13	8
0.01	0	2	0	1	1	1	1	1	3	1
S=5
0.5	61	51	52	48	58	58	56	58	51	52
0.1	17	11	14	14	15	19	19	15	11	9
0.01	3	2	2	1	2	6	3	1	3	1
S=6
0.5	-	68	52	56	45	56	59	53	52	54
0.1	-	18	7	10	10	13	18	9	8	10
0.01	-	5	0	1	3	1	2	0	1	0
S=7
0.5	-	-	-	59	58	46	46	42	45	52
0.1	-	-	-	13	8	9	11	9	4	7
0.01	-	-	-	1	1	3	2	2	1	0
S=8
0.5	-	-	-	-	-	56	53	55	46	53
0.1	-	-	-	-	-	10	14	10	7	9
0.01	-	-	-	-	-	1	0	1	1	0
S=9
0.5	-	-	-	-	-	-	-	67	64	49
0.1	-	-	-	-	-	-	-	19	15	10
0.01	-	-	-	-	-	-	-	2	1	1
S=10
0.5	-	-	-	-	-	-	-	-	-	57
0.1	-	-	-	-	-	-	-	-	-	14
0.01	-	-	-	-	-	-	-	-	-	2

Таблица 4. Тест РСЕ для ВГ

22	18	16	19	17
25	18	19	22	20
17	22	17	18	19
21	18	20	18	20

Таблица 5. Тест «хи-квадрат» для файла «Парадокс Глебова»

	11	12	13	14	15	16	17	18	19	20
S =1
0.5	56	51	46	52	42	49	54	45	46	51
0.1	8	8	11	10	9	14	9	9	9	16
0.01	1	0	1	0	1	2	0	3	2	3
S=2
0.5	48	53	48	46	46	41	52	49	50	45
0.1	11	10	8	8	6	9	10	10	12	10
0.01	1	2	0	1	2	2	0	1	1	0
S=3
0.5	51	41	46	55	50	59	53	57	52	50
0.1	9	8	14	12	12	15	7	8	14	13
0.01	0	2	1	3	1	1	0	0	2	1
S=4
0.5	50	45	52	44	44	43	49	54	53	49
0.1	9	8	9	8	11	13	7	9	12	16
0.01	0	1	0	0	1	0	0	0	2	3
S=5
0.5	60	54	59	51	54	54	50	42	42	41
0.1	14	12	10	11	12	13	12	11	9	13
0.01	1	1	0	0	1	3	0	0	2	2
S=6
0.5	-	62	56	59	55	56	51	54	51	48
0.1	-	17	13	15	14	14	10	12	12	14
0.01	-	4	2	2	1	2	2	3	1	3
S=7
0.5	-	-	-	49	51	51	59	52	46	47
0.1	-	-	-	14	16	13	13	13	10	11
0.01	-	-	-	4	3	1	0	2	1	3
S=8
0.5	-	-	-	-	-	59	54	51	54	46
0.1	-	-	-	-	-	12	15	13	15	16
0.01	-	-	-	-	-	3	2	2	2	2
S=9
0.5	-	-	-	-	-	-	-	62	59	55
0.1	-	-	-	-	-	-	-	16	13	11
0.01	-	-	-	-	-	-	-	3	1	1
S=10
0.5	-	-	-	-	-	-	-	-	-	50
0.1	-	-	-	-	-	-	-	-	-	16
0.01	-	-	-	-	-	-	-	-	-	3

Таблица 6. Тест РСЕ для файла «Парадокс Глебова»

19	21	17	18	22
16	20	21	19	21
24	18	17	19	18
23	18	20	22	19

Размещено на Allbest.ru