Роберт Лав - Разработка ядра Linux

Эти три функции добавляют передаваемые данные в пул энтропии, вычисляют оценку энтропии добавляемых данных и увеличивают оценку энтропии пула на вычисленное значение.

Все эти экспортируемые интерфейсы используют внутреннюю функцию add_timer_randomness()для ввода данных в пул. Эта функция вычисляет интервалы времени между успешными событиями одного типа и добавляет эти значения в пул. Например, интервалы времени между успешными прерываниями жесткого диска достаточно случайны, особенно если измерять достаточно точно. Самые младшие биты — это обычно электрический шум. После того как эта функция вводит данные в пул, она вычисляет количественную характеристику того, насколько эти данные случайны. Это делается путем вычисления отклонения первого, второго и третьего порядка от предыдущего момента времени и изменения этих отклонений первого, второго и третьего порядка. Наибольшее из этих отклонений, округленное до 12 бит, используется в качестве оценки энтропии.

Для получения случайных чисел внутри ядра экспортируется один интерфейс.

void get_random_bytes(void *buf, int nbytes);

Эта функция сохраняет nbytesслучайных байтов в буфере памяти, на который указывает параметр buf. Функция возвращает данные, даже если оценка энтропии равна нулю. Для ядра это не так критично, как для пользовательских криптографических программ. Случайные данные мало используются в ядре, в основном они нужны сетевой подсистеме для генерации стартового номера последовательности сегментов при соединении по протоколу TCP.

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

unsigned long rand;

get_random_bytes(&rand, sizeof(rand));

Для программ, которые выполняются в пространстве пользователя, предоставляется два символьных устройства: /dev/randomи /dev/urandom. Первое устройство, /dev/random, используется, когда необходимы гарантированно случайные данные для криптографических приложений с высоким уровнем безопасности. Это устройство выдает только то количество битов данных, которое соответствует оценке энтропии в ядре. Когда оценка энтропии становится равной нулю, операция чтения устройства /dev/randomблокируется и не возвращает данные, пока значение энтропии не станет существенно положительным. Устройство /dev/urandomне имеет последней возможности, а в остальном работает аналогично. Оба устройства возвращают данные из одного и того же пула.

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

unsigned long get_random(void) {

unsigned long seed = 0;

int fd;

fd = open("/dev/urandom", O_RDONLY);

if (fd == -1) {

perror("open");

return 0;

}

if (read(fd, &seed, sizeof(seed)) < 0) {

perror("read");

seed = 0;

}

if (close(fd))

perror("close");

return seed;

}

Можно также считать $bytesбайтов в файл $file, используя программу dd.

dd if=/dev/urandom of=$file count=1 bs=$bytes

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

Алгоритм — это последовательность действий, возможно, с одним входом или более и, в конечном счете, с одним результатом или выходом. Например, подсчет количества людей в комнате представляет собой алгоритм, для которого люди, находящиеся в комнате, являются входными данными, а количество людей в комнате — выходными данными. Операции замещения страниц в ядре Linux или планирование выполнения процессов — это тоже примеры алгоритмов. Математически алгоритм аналогичен функции (или, по крайней мере, может быть смоделирован с помощью функции). Например, если мы обозначим алгоритм подсчета людей в комнате буквой f, а количество людей, которых необходимо посчитать, буквой x, то функцию подсчета количества людей можно записать следующим образом.