Снова о Случайных Числах или Старый взгляд на новые вещи II.

Введение/Introduction
Продолжим наше путешествие по таинственной дороге RN (Random Numbers - Случайные Числа, далее СЧ).
Автор скромно предполагает, что вы читали первую статью - "Старый взгляд на новые вещи" (на [1]), если же нет, то ... "сложно продолжить путь, так и не начав его" :).
В самом начале вы натолкнётесь на несколько простеньких формул. Есть конечно опасения, что "каждая формула вдвое сокращает круг читателей", но я надеюсь, что Вас это не касается, в противном случае вы можете их просто пропустить (так же могут поступить те, кто сдал курс Теории Вероятностей ;)).

Начало/Beginning
Давайте зададимся простым вопросом: чем одна последовательность СЧ отличается от другой?
Например: чем последовательность СЧ, выдаваемая /dev/random отличается от последовательности СЧ выдаваемой /dev/urandom ?
Ответ, что: "/dev/random создаёт только случайные байты" нужно понять немного глубже.
Статистическая теория даёт нам ряд количественных критериев, по которым проводят проверку качества ГСЧ(Генераторов Случайных Чисел (Random Number Generator) (RNG)) или Генераторов Псевдослучайных Чисел(Pseudorandom Number Generator (PRNG))?
вместо Pseudorandom очень хочется поставить Poor random :-)

Такую проверку проводят по ряду количественных критериев, которые нам даёт статистическая теория.
Ниже приводятся некоторые наиболее распространённые тесты:
1. Критерий "хи-квадрат" (пишется греческая буква хи, возведённая в квадрат)
2. Проверка по моментам распределения.
3. Проверка на равномерность.
4. Проверка независимости элементов последовательности.
5. etc.

Ниже рассмотрена сущность второго и третьего тестов:

Проверка по моментам распределения.

	МОМЕНТ -
	(от лат. momentum - движущая сила, толчок), понятие теории вероятностей;
	характеристика распределения значений случайной величины Х. 
	В простейшем случае, когда Х может принимать лишь конечное число значений
	x1, x2,..., xn
	с вероятностями
	p1, p2,..., pn,
	моментом порядка k величины Х называется выражение:
	
	
	  k     k           k
	x1 p1+x2 p2+ ... +xn pn
	
	Момент 1-го порядка а - математическое ожидание, 
	момент 2-го порядка - дисперсия (если а = 0).
	
	Я конечно рассчитываю, что вам знакомы такие понятия из теории вероятностей, 
	как математическое ожидание и дисперсия, но до кучи :) приведу формулы и для них.
	
	Математическое ожидание:
	Если X принимает значения xi с вероятностями pi
	Тогда математическое ожидание запишется:
	
	
	     n
	    --
	MX= \ (xipi)
	    /
	    --
	     i
	
	Математическое ожидание имеет смысл среднего значения случайной величины.
	Для непрерывной величины сумма заменяется на интеграл.
	Дисперсия:
	
	          2
	DX=M(X-MX)
	
	Дисперсия даёт разброс случайной величины вокруг среднего значения.
	Именно смысл дисперсии имеют величины в принципе неопределённости Гейзенберга.
	

Т.о. проверка по моментам распределения последовательности случайных чисел x1,x2, ... ,xN заключается в подсчёте математического ожидания (сиречь среднего) и дисперсии. Если числа близки к равномерной случайной последовательности [0,1], то при достаточно больших N(число выборок)
Mx~0,5
Dx~1/12
Эти числа получаются, если в интегральные формулы для мат. ожидания и дисперсии подставить функцию плотности распределения, описывающую равномерное распределение в интервале [0,1].

Проверка на равномерность.
Для проверки на равномерность нужно интервал распределения случайной величины (например отрезок [0,1]) разбить на n равных частей. Тогда каждое из чисел xi попадёт в один из интервалов.
Пусть M1 - число чисел, попавших в первый интервал M2 - во второй и т.д. При этом
M1+M2+ ... +Mn=N
Тогда относительные частоты попадания случайных чисел в каждый из n интервалов:
p1=M1/N ,p2=M2/N , ... ,pn=Mn/N ,
Далее строится гистограмма(pi от xi).
Если числа равномерные, то при большом N гистограмма должна приближаться к теоретической прямой 1/n.
Число разбиений обычно берётся 10-20.

Таким образом - не составляет труда написать простенькую программку для тестирования функций ГСЧ.
Исходничек, приведённый ниже предназначен для "тестирования" функции, выдающей случайные числа(rnd(), пример которой приведён в первой статье); вычисляет среднее значение, дисперсию, а так же распределение случайных чисел по пяти интервалам.

	  // for test rnd() function
	
	#ifndef _TESTRND_CPP_
	#define _TESTRND_CPP_
	
	#include <stdio.h>
	#include <math.h>
	#include "utils.h" //for rnd()
	
	// number of intervals
	#define _N_ 5
	#define DEFAULT_MAX_RND 10
	
	const char prog_name[]="testrnd";
	
	int main(int argc,char *argv[])
	{
		float *RndData; // store random numbers
		int NumberOfIterations;
		uint MaxRnd;
		int i; // counter
		float x;
		float average;
		int r1=0,r2=0,r3=0,r4=0,r5=0; 
			// for calculate number of random numbers in various intervals
	
		if(argc<2)
		{
	printf("Usage:\n%s <number of iterations> <random max(divisible on 5)>\n",prog_name);
	return -1;
		}
		NumberOfIterations=atoi(argv[1]);
		if(argc<3)
			MaxRnd=DEFAULT_MAX_RND;
		else
			MaxRnd=atoi(argv[2]);
	
		if(NumberOfIterations==0 || MaxRnd==0)
		{
	printf("Number of iterations and random max must be more than zero!\n");
			return 2;
		}
		// print parameters
	printf("parameters:\nNumber of iterations: %d\nrandom max: %d\n",NumberOfIterations,MaxRnd);
		average=0;
		RndData=new float[NumberOfIterations];
		if(RndData==NULL)
		{
			printf("Cant allocate memory for RndData !\n");
			return 3;
		}
		for(i=0;i<NumberOfIterations;i++)
		{
			//\/\/\/\/\/\/\/\/\//
			x=rnd(MaxRnd+1);
			//\/\/\/\/\/\/\/\/\//
			RndData[i]=x;
			average+=x;
			// calculate number of random numbers in various intervals
			if(x<MaxRnd/5)
				r1++;
			else
			{
				if(x<2*MaxRnd/5)
					r2++;
				else
				{
					if(x<3*MaxRnd/5)
						r3++;
					else
					{
						if(x<4*MaxRnd/5)
							r4++;
						else
						{
							if(x<=MaxRnd)
								r5++;
						}
					}
				}
			}
		}
		average/=NumberOfIterations;
	
		//---------- calculate dispersion  ---------------
		float Dispersion=0,fx=0;
		for(i=0;i<NumberOfIterations;i++)
		{
			fx+=(RndData[i]-average)*(RndData[i]-average);
	//		printf("%1.3f\n",RndData[i]);
		}
		Dispersion=fx/(NumberOfIterations-1);
		Dispersion=sqrt(Dispersion);
		//---------- calculate dispersion end ------------
	
		printf("-------------------\n");
		printf("Average:\t %1.3f\n",average);
		printf("Dispersion:\t %1.3f\n",Dispersion);
		printf("<%d:\t\t %d\n",MaxRnd/5,r1);
		printf("<%d:\t\t %d\n",2*MaxRnd/5,r2);
		printf("<%d:\t\t %d\n",3*MaxRnd/5,r3);
		printf("<%d:\t\t %d\n",4*MaxRnd/5,r4);
		printf("<%d:\t\t %d\n",MaxRnd,r4);
		printf("-------------------\n");
		printf("Number of intervals (n): %d\n",_N_);
		printf("1/n:\t\t %1.3f\n",(float)1/_N_);
		printf("p1:\t\t %1.3f\n",(float)r1/NumberOfIterations);
		printf("p2:\t\t %1.3f\n",(float)r2/NumberOfIterations);
		printf("p3:\t\t %1.3f\n",(float)r3/NumberOfIterations);
		printf("p4:\t\t %1.3f\n",(float)r4/NumberOfIterations);
		printf("p5:\t\t %1.3f\n",(float)r5/NumberOfIterations);
		printf("-------------------\n");
	
		delete []RndData;
		RndData=NULL;
		return 0;
	}
	#endif //#ifndef _TESTRND_CPP_
	  

Этот исходничек - только скромный пример проверки ГСЧ. Для более серьёзной работы рекомендую использовать замечательную утилиту ENT (см. [6])

ГПСЧ в сети и не только ...
Открываю газету, вижу рекламу firewall-а и что же я там читаю...

Конечно это не самая популярная уязвимость - если просмотреть архив уязвимостей, то уязвимость ГСЧ пренебрежимо(?!) мала, по сравнению с Buffer Overflow и Format String Vulnerability =).
Но, как говорится, на безрыбье и рак - рыба :-)
Тем более эту уязвимость порой достаточно просто эксплуатировать; например, существует такая проблема, как ­конкуренция доступа к каталогу /tmp:
эта проблема возникает, когда программа с правами другого пользователя(например root ;) создаёт в каталоге /tmp временный файл, если файл с таким именем уже есть, то функция open() завершится и вернёт его дескриптор программе. Т.о. злоумышленник может создать символическую ссылку на любой файл в системе и с нужным именем поместить её в каталоге /tmp, что позволяет ему уничтожить системные файлы. Тут главное - кто первым успеет создать временный файл(в этом и состоит конкуренция). Казалось бы, есть простой выход - создавать временные файлы со случайными именами... ,но это решение тоже уязвимо - можно создать много ссылок с "верными" именами и любая верная ссылка сделает свою работу!

А для многих программ надёжность ГСЧ не только один из критериев успеха, но и условие хм... выживания...:
Вот,например, что говорится в статье "История одной уязвимости" (почитать можно на [2]).

 
	     DWORD GetRandomIp(DWORD ThreadCounter)
	{
	 DWORD ResultIP;
	 SYSTEMTIME systime;
	 DWORD temp1, temp2, temp3;
	 DWORD SecMilisec;
	 ResultIP = ThreadCounter*0x50F0668D;
	 GetSystemTime(&systime);
	 memcpy(&SecMilisec, &systime.wSecond, sizeof temp);
	 temp1 = SecMilisec*SecMilisec*0xCD59E3;
	 temp2 = SecMilisec*0x1E1B9;
	 temp3 = ResultIP + temp1;
	#ifdef  CRv1
	 temp2 = temp2 + temp3;
	#else
	 ResultIP = temp2 + temp3;
	#endif
	 ResultIP = ResultIP*0xCF3383 + 0x76BFE53;
	 temp2 = ResultIP & 0xff;
	 if ((temp2 == 127) || (temp2 == 224)) {
	  ResultIP = ResultIP + 0x20DA9;
	 }
	 return ResultIP;
	}
	

Эту же проблему не обошёл своим вниманием и знаменитый Крис Касперски в статье [7].

Как видите - у вирусов и червей ГСЧ вообще является одним из важных органов =).

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

В качестве примера приведён код ГПСЧ нашумевшего вируса mydoom.

	    static DWORD xrand16_seed;
	
	void xrand_init(void)
	{
		xrand16_seed = GetTickCount();
	}
	
	WORD xrand16(void)
	{
		xrand16_seed = 0x015a4e35L * xrand16_seed + 1L;
		return ((WORD)(xrand16_seed >> 16L) & (WORD)0xffff);
	}
	
	DWORD xrand32(void)
	{
		return xrand16() | (xrand16() << 16);
	}
	    

В качестве заключения
Наступает новое время - всё меняется; и вот уже появляются процессоры со встроенными ГСЧ.
Примером является камень от VIA Technologies(www.via.com.tw) с ядром 'Nehemiah'(the First x86 Processor to Market with Embedded Security Features).
А вот, что говорится об этом ядре:

После этого можно было бы начать говорить о "скорой" кончине ГПСЧ, но этот разговор я предоставлю другим (потому что сам так не считаю ;).

СЧ по-прежнему нужны; не только криптографам - даже астрономам требуется их использовать (см. статью "Фотографии кошек помогут изучать галактики" от 15 сентября 2004 на [10]), но стоит понять, что отчасти именно ГПСЧ виновники тех "смертей интернета", которые раз в 5-6 месяцев прогнозируют антивирусные компании.

Продолжение следует...

Дополнительная информация
1. www.bugtraq.ru
2. www.security.nnov.ru
3. www.securitylab.ru
4. www.random.org
5. RFC 1750
6. www.fourmilab.ch/random/
Программу ENT можно скачать по адресу www.fourmilab.ch/random/random.zip
7. Крис Касперски Жизненный цикл червей
статью можно почитать на wasm.ru
8. Брюс Шнайер Прикладная криптография
В in-et-е можно найти электронный вариант книги (к сожалению я не помню :( где скачал эту книгу(в формате .pdf))
9. http://www.cs.berkeley.edu/~daw/rnd/
- большое количество ссылок на ресурсы(eng), посвящённые RN.
10. www.membrana.ru

P.S.
Эта статья является некоторым итогом серии выпусков, рассылки Моделирование Виртуальной Вычислительной Системы. В этой статье автор выражает некоторые суждения, которые могут быть весьма спорными, не претендуя на истину в последней инстанции и глубину своих познаний в данной области автор с благодарностью готов выслушать замечания и дополнения.

P.P.S.
В статье использованы вырезки из различных источников. Авторский текст оставлен без редактирования с моей стороны (т.е. даётся AS IS).

Удачи!

noonv [AT] narod [.] ru

XIII