Снова о Случайных Числах.

или

Старый взгляд на новые вещи 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.

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

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

  k     k           k
x1 p1+x2 p2+ ... +xn pn

Математическое ожидание:
Если 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;
}

Из листинга видно, что алгоритм сменился во втором поколении червя. 
Вероятно, была просто поправлена ошибка.

Генерируемый ip-адрес является функцией 3х параметров: 
номер потока (1-100),
текущая секунда (0-59),
текущая миллисекунда (0-999).

Отсюда максимально возможный неповторяющийся набор получаемых адресов равен:
 
100*60*1000 = 6000000 = 6 млн. ip-адресов.
 
Понятно, что все заявления по поводу инфицирования практически всех 
возможных целей не имеют под собой основания. 6 млн. ip-адресов 
это только 0,1 % всех теоретически возможных ip-адресов.

Эту же проблему не обошёл своим вниманием и знаменитый Крис Касперски в статье [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).

Удачи!