ЕЩЕ РАЗ О СЛУЧАЙНЫХ ЧИСЛАХ * Zemsky Fershal //NF (C) 1998-2004

ЕЩЕ РАЗ О СЛУЧАЙНЫХ ЧИСЛАХ
by DrMAD

Введение
1. "Настоящие" и "ненастоящие" случайные числа
2. Использование системного таймера
3. Что такое "хорошо" и что такое "плохо"
3.1. "Случайное" поведение
3.2. Равномерное распределение
3.3. Циклы
4. Линейные конгруэнтные датчики
5. Прочие датчики
5.1. Датчики Фибоначчи
5.2. Примитивные датчики
5.3. Датчики случайных битов
6. Некоторые полезные применения
6.1. Имитационное моделирование
6.2. Генерация паролей
6.3. Случайное перемешивание
Литература
Постскриптум

Сразу предупреждаю - эта маленькая статьюшка будет неинтересна тем,
кто мечтает взять готовый рецепт, не задумываясь использовать его и
побыстрей о нем забыть. Хотя я постараюсь всю математику описать в
стиле "ути-пуси для детей младшего ясельного возраста". И готовые
рецепты в статье тоже будут...

ВВЕДЕНИЕ

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

1. "НАСТОЯЩИЕ" И "НЕНАСТОЯЩИЕ" СЛУЧАЙНЫЕ ЧИСЛА

"Настоящие" случайные числа можно получить только в объектах и
процессах реального мира.
Обычно их получают:
1) либо выбирая их из специальных, заранее заготовленных таблиц;
2) либо аппаратно - оцифровывая какой-нибудь слабо коррелированный
случайный процесс (например, электрический сигнал на выходе "шумящего"
диода), на мамках с чипсетами от Intel, начиная с i810, есть такой
девайс - RNG.
Поведение последовательности таких чисел абсолютно непредсказуемо.
Повторить такую последовательность (например, для того, чтобы повторить
моделирование и получить те же самые результаты) невозможно.

"Ненастоящие" случайные числа генерируются по определенному
алгоритму F примерно так:
1) выбирается самое первое число X(0);
2) все остальные числа получаются как X(i)=F(X(i-1)), i=1,2,3...

Любой желающий, зная самое первое число X(0) (так называемую
"затравку" или по-буржуйски "seed") и алгоритм генерации F, может
сколько угодно раз воспроизвести всю цепочку таких чисел, т.е. они все-
таки не случайны. Но выглядят они очень похоже на случайные, определить
закономерность их создания очень трудно, поэтому их называют
"псевдослучайными" числами.

2. ИСПОЛЬЗОВАНИЕ СИСТЕМНОГО ТАЙМЕРА

Можно попытаться получать "настоящие" случайные числа при помощи
системного таймера. Этот метод рекомендуется даже в книжке /1/ и часто
применяется в полиморфиках. Но делается это не всегда правильно.
Вот типичный пример процедуры генерации случайных чисел, взятый из
вируса Arch.903:

@1: mov al, ah
in al, 40h
cmp al, ah
jnc @1
xchg ah, al
ret

Порт 40h - это буферный порт обмена данными с нулевым каналом
системного таймера. У таймера имеются еще два независимо работающих
канала: первый с буферным портом 41h и второй с буферным портом 42h.
Поэтому, кстати, команды in al,41h и in al,42h в этом отношении ничем
не хуже.
По умолчанию через этот порт доступны значения 16-битового
таймерного счетчика, который уменьшает свое значение на 2 с частотой
1.19 МГц (т.е. каждые 0.00000083 сек.), а по достижении нуля вновь
перезагружает исходную константу. При загрузке компьютера BIOS
инициализирует для нулевого канала эту константу значением 65535. Т.к.
какой-нибудь софт мог эту константу изменить, то по хорошему, перед
использованием таймера надо принудительно повторить эту операцию:

mov al, 00111110h
out 43h, al
mov al, 0FFh
out 43h, al
out 43h, al

По умолчанию этот порт работает следующим образом: каждое нечетное
чтение из него возвращает младший байт 16-битового счетчика (который
изменяется быстро), а каждое четное - старший байт (который изменяется
медленно). Таким образом, обращаясь в цикле (т.е. в неслучайные моменты
времени!) к процедуре, взятой из вируса Arch.903, можно получить числа
типа

... 12 34 10 34 8 34 ... 2 34 0 34 65534 33 65532 33 ...

и т.д., которые "случайными" можно назвать только с дикого бодуна.
(На самом деле, на медленных компьютерах последовательность будет
выглядеть более привлекательно, но не намного).
Это был простейший пример. Во многих полиморфных движках (типа SPE,
RTFM, TCE и т.п.) число, полученное из порта, "ксорится" с чем-нибудь,
сдвигается влево-вправо, инвертируется и т.п. Нетрудно догадаться, что
последовательность чисел от этого намного более случайной не станет.
Если уж совсем влом использовать арифметику и хочется обойтись
одним таймером, можно рекомендовать попробовать метод Z0mbIE
(использование комбинации значений из разных каналов):

...
in al,40h
xor bl,al
in al,40h
add bh,al
in al,41h
sub bl,al
in al,41h
xor bh,al
in al,42h
add bl,al
in al,42h
sub bh,al
mov rndword[ebp] bx
...

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

3. ЧТО ТАКОЕ "ХОРОШО" И ЧТО ТАКОЕ "ПЛОХО"

Датчики псевдослучайных чисел (ДПСЧ) бывают хорошими и плохими.
Признаками хорошего ДПСЧ является:
1) способность генерировать числа, ведущие себя "похоже" на
случайные;
2) способность генерировать распределение чисел, близкое к
равномерному;
3) большая длина "цикла".

3.1. "СЛУЧАЙНОЕ" ПОВЕДЕНИЕ

Это свойство проще всего пояснить наглядно:

1 2 3 4 5 6 7 8... явно неслучайная последовательность;
6 1 5 1 4 1 3 1... тоже случайностью не слишком пахнет;
1 2 1 3 4 2 1 5... нарисуйте график, и увидите тенденцию;
1 3 2 6 1 4 4 2... только эти числа похожи на случайные.

Формально "случайность" можно определить, например, рассчитав для
последовательности этих чисел автокорреляционную функцию (АКФ). Если
эти числа "скачут" независимо друг от друга, то это - некоррелированный
случайный процесс (так называемый "белый шум"), и его АКФ - это просто
дельта-функция ("палка") в нуле.

АКФ какого-то коррелированного процесса (плохо):

Ш
ШШ
ШШШ ШШ
_ШШШШ____ШШШШ_Ш_______________
0 ШШШШ Ш
ШШ

АКФ "белого шума" (хорошо):

Ш
Ш
Ш
_Ш______________________________
0

3.2. РАВНОМЕРНОЕ РАСПРЕДЕЛЕНИЕ

Это означает, что любое возможное значение на выходе у датчика -
примерно равновероятно.
Пример "хорошего" датчика с равномерным распределением -
нефальшивая монета, которая, как известно, при падении может лечь орлом
или решкой с равной вероятностью. Уронив монету 100 раз и подсчитав
количество падений той или иной стороной, можно получить отношение,
близкое к "фифти-фифти". Ну пусть 48/52 или даже 55/45, это достаточно
мелкие отклонения.
А вот если отношение сильно несимметричное (например, 20/80), то
это значит, что вы роняли не монету, а... бутерброд, который, как
известно, почти всегда падает маслом вниз. J Бутерброд - пример
"плохого" датчика.
Кстати, при необходимости из равномерного распределения можно
получить любое другое, но не наоборот.
Формально "равномерность" можно определить, построив для
последовательности полученных чисел гистограмму (оценку плотности
вероятности) и применив какой-нибудь известный математический критерий
(например, "хи-квадрат"), но можно и просто оценить на глаз.

Гистограмма какого-то очень неравномерного распределения (плохо).

Ш
Ш Ш Ш
Ш Ш Ш Ш
_ШШШШШШ_ШШ_
a a

Гистограмма равномерного на интервале [a,b] распределения (хорошо).

ШШШШШШШШ
_ШШШШШШШШ_
a b

3.3. ЦИКЛЫ

Монета потенциально дает всего два возможных значения, а реальные
датчики столько, сколько различных чисел возможно поместить в ячейке
памяти. Очевидно, что возможно получить не более 65535 различных
значений 16-битового целого числа. А после этого одно из чисел
неминуемо повторится, и повторится вся слудующая за ним
последовательность чисел (ведь она считается по жесткому алгоритму!).
Это и есть "цикл" датчика. Кстати, для 16-битового датчика получить
длину цикла в 65 тысяч - это очень и очень хороший результат. Если не
предпринимать специальных мер, зацикливание происходит много раньше.

Формально обнаружить цикл можно при помощи метода Флойда,
упомянутого в /2/. Идея метода в том, чтобы параллельно из одной и той
же затравки X(0)=Y(0) одним и тем же алгоритмом F генерировать
случайные числа

X(i)=F(X(i-1)) и Y(i)=F(F(Y(i-1))).

Поскольку вторая последовательность "бежит" в 2 раза быстрей, то
рано или поздно возникнет ситуация X(i)=Y(i)=X(2*i), а это и означает
наличие цикла.

4. ЛИНЕЙНЫЕ КОНГРУЭНТНЫЕ ДАТЧИКИ

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

Get_Rand:
push cx
push dx
mov ax, cs:[rand_seed+bp]
mov cx, 0DEADh
mul cx
xor ax, 0DADAh
ror ax, 1
mov cs: [rand_seed+bp], ax
pop dx
pop cx
ret

Распределение чисел близко к равномерному, но при _любой_ затравке
этот алгоритм дает цикл длиной всего 532.
На футбольном языке это называется "перекрутил мяч". J Реально
хороший датчик вполне можно было получить, выкинув их этого текста ряд
лишних и все портящих строк и чуть-чуть скорректирова константы.
Дело в том, что общепризнанным "хорошим" рецептом является
"линейный конгруэнтный" метод:

X(i) := (A*X(i-1) + B) mod C.

Рекомендации Д. Кнута из книги /2/ по выбору констант А, B, и C:

С - обычно для 16-битовых ДПСЧ это 2^16=65536, а для 32-битовых
2^32;
A = 8t+5, где t - какое-то целое число, причем C/100 < A < C-SQRT(C);
B - нечетное и не кратное 5 число.

Стандарт ANSI-C требует для любого компилятора с языка С/С++
наличия в нем двух функций:

#define RAND_MAX 32767

static unsigned long next_rand = 1;

/* Линейный конгруэнтный ДПСЧ */
int rand(void) {
next_rand = next_rand * 1103515245 + 12345;
return (unsigned int)(next_rand/65536)%32768;
}

/* Формирователь желаемой затравки */
void srand( unsigned int seed ){
next_rand = seed;
}

Очевидно, что этот датчик 32-битовый, хотя выдает 15-битовые
результаты.
В Watcom C/C++ и TopSpeed C/C++ реализован именно он (a =
1103515245, b = 12345), а фирма Borland для своих компиляторов слегка
модифицировала константы (a = 22695477, b=1). Но и в том и в другом
случае гарантированно получаются достаточно хорошие по всем параметрам
псевдослучайные последовательности.
Вот компактный пример 16-битового линейного конгруэнтного датчика
на ассемблере:

A dw 32005
B dw 1
SEED dw 12345
...
Rand:
mov ax, SEED
mul A
add ax, B
mov SEED, ax
ret

В статье /3/ можно найти дизассемблированные датчики из Borland
Pascal и Turbo C.

5. ПРОЧИЕ ДАТЧИКИ

5.1. ДАТЧИКИ ФИБОНАЧЧИ

Линейные конгруэнтные ДПСЧ неплохо изучены теоретически и дают
довольно хорошие для большинства приложений последовательности
псевдослучайных чисел. Но и у них есть недостатки: 1) длина цикла не
может превышать константу С; 2) при использовании ряда очень
навороченных статистических тестов все-таки можно обнаружить
закономерности в сгенерированных числовых последовательностях, т.е. они
недостаточно "случайны".
Использование "Фибоначчиевых ДПСЧ" - путь к улучшению качества
псевдослучайных последовательностей.
Примеры таких датчиков (на мой взгляд, они не все Фибоначчиевы, но
там, где я их взял, они называются именно так) :

1) датчик, упомянутый в /2/:

X(i) = (X(i-1)+X(i-N)) mod C, N>15;

2) датчик, упомянутый в /5/:

Y1=X(i-N), Y2=X(i-M), N <> M
X(i) = Y1-Y2>0?Y1-Y2:Y2-Y1

Полной теории Фибоначчиевых датчиков пока не существет, поэтому
использовать их можно только на собственный страх и риск.

5.2. ПРИМИТИВНЫЕ ДАТЧКИ

Иногда можно воспользоваться не слишком хорошими, но крайне
простыми в реализации датчиками из книжки /4/:
1) X(i)={A*X(i-1)}, где {.} означает выделение дробной части, а
константа A выбирается как 8*t+3 или 8*t-3, а t - любое целое число;
2) X(i)={11*X(i-1)+3.1415926}, обозначения те же.

По крайней мере несколько десятков (а то и сотен) неплохих
псевдослучайных чисел в интервале [0..1] они обеспечивают.

5.3. ДАТЧИКИ СЛУЧАЙНЫХ БИТОВ

Все описанные выше датчики ориентированы на генерацию случайных
чисел. Но в этих числах разные части (группы битов) иногда имеют разные
вероятности появления, поэтому их не всегда можно использовать в таких
ответственных задачах, как, например, криптография.
Для этих целей разработаны другие методы. Вот, например, упомянутый
в /7/ генератор М-последовательностей. Идея проста: пусть уже
сгенерировано N битов, тогда берется K<N последних битов b(K-1),
b(K-2),...b(0), а новый N+1-ый бит генерируется как

b(N+1) = a(K-1)*b(K-1) xor a(K-2)*b(K-2) xor... a(0)*b(0),

где a(K-1), a(K-2)... a(0) - коэффициенты некоего битового полинома
K-го порядка. Можно в качестве этого полинома взять какое-нибудь
K-разрядное случайное число с равномерно распределенными битами.
Период (цикл) М-последовательности невелик и равен 2^K-1, поэтому
обычно в необходимый момент просто изменяют полином "a".

6. НЕКОТОРЫЕ ПОЛЕЗНЫЕ ПРИМЕНЕНИЯ

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

6.1. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ.

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

ШШШШШ
ШШШШШШШ
ШШШШШШШШШ
ШШШШШШШШШШШШШ
_ШШШШШШШШШШШШШШШШШШШ_
-oo M +oo

Последовательность нормально распределенных случайных чисел
характеризуется двумя параметрами:
1) M - математическим ожиданием (это положение "центра тяжести");
2) D - среднеквадратическим отклонением (это скорость
"рассасывания").

Моделируются такие случайные числа на основе равномерно
распределенного на интервале [0..1] датчика. Алгоритм:

Y(i) = M + D*( (X(i-N)+X(i-N+1)+...+X(i)) - N/2),

где обычно принимают N=12, хотя неплохо получается уже при N=4.

6.2. ГЕНЕРАЦИЯ ПАРОЛЕЙ

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

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

#define NPAS 10
#define NSYM 8

char s[]=
{"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
~!@#$%^&(){}[]"};

main()
{
int i j; struct time t;
gettime(&t); srand(t.ti_sec*100+t.ti_hund); // Всего 6000 затравок
for (j=0;j<NPAS;j++)
{
for (i=0;i<NSYM;i++) cout << s[rand()|(RAND_MAX|(sizeof(s)-1))];
cout << endl;
}
}

Мне эта утилита выдала пароли: Z1TuA0Lp, MeXin(Xj, ruXv[esv и т.д.

6.3. СЛУЧАЙНОЕ ПЕРЕМЕШИВАНИЕ

Иногда требуется выполнить случайное перемешивание каких-нибудь
объектов (например, карт в пасьянсе "Свободная ячейка" или IP-адресов в
определенном диапазоне).
Первый подход заключается в том, чтобы генерировать пары случайных
индексов в перемешиваемом массиве и менять их местами. Дешево и
сердито, но нет никакой гарантии, что один и тот же индекс (или даже
пара индексов) не выпадет несколько раз.
Я предпочитаю другой метод, основанный на "линейном конгруэнтном"
датчике и описанный в книжке /6/. Пусть имеется массив из N элементов.
Выбираем:
1) число 0.66*N<M<0.9*N, взаимно-простое с N;
2) произвольный (можно случайный) начальный индекс K<N.
Ну а дальше получаем новые индексы: K(i) = (K(i-1)+M) mod N.

ЛИТЕРАТУРА

1. Фролов А., Фролов Г. Аппаратное обеспечение IBM PC. Часть 2. -
М: Далог-МИФИ, 1992. - 208 с.
2. Кнут Д. Искусство программирования для ЭВМ. Получисленные
алгоритмы. -М.: Мир, 1977.-724 с.
3. Генераторы случайных чисел // MoonBug #5.
4. Дьяконов В.П. Справочник по расчетам на микрокалькуляторах. -
М.: Наука, 1986.- 224 с.
5. Michael Machin aka Ltwood. Добавление: о датчиках случайных
чисел.// http://ltwood.hotbox.ru.
6. Этюды о персональных компьютерах. - М.: Знание, 1988. - 160 с.
7. Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной
криптографии / М: Горячая Линия-Телеком, 2002. - 175 с.

Постскриптум. Уже после написания статьи мне попалась на глаза
статья "Analysis of Common RNGs" от Feathered Serpents из журанала
"Natural selection #1", в которой рассматривается три десятка ДПСЧ из
разных вирусов. Датчики сравнивались по вероятности появления отдельных
битов в случайных числах, так же исследовалось их распределение по
критерию "хи-квадрат" и выполнялись некоторые другие статистические
тесты. Как и следовало ожидать, датчики, которые использовали линейный
конгруэнтный алгоритм, показывали хорошие результаты, а те, кто тупо
сканировали таймер или ориентировались на какую-нибудь заумную
арифметику, никуда не годились. Хорошая статья, рекомендую!
DrMAD