Функция add_keyboard_randomness() использует скан-коды и интервалы времени между нажатиями клавиш для ввода энтропии в пул. Интересно, что эта функция достаточно интеллектуальна и игнорирует повторение символов при постоянном нажатии клавиши, потому что повторяющиеся скан-коды и интервалы времени вносят мало энтропии.
Функция add_mouse_randomness() использует позицию указателя мыши и интервалы времени между прерываниями для заполнения пула. Параметр mouse_data — это позиция указателя, которая возвращается аппаратным обеспечением.
Эти три функции добавляют передаваемые данные в пул энтропии, вычисляют оценку энтропии добавляемых данных и увеличивают оценку энтропии пула на вычисленное значение.
Все эти экспортируемые интерфейсы используют внутреннюю функцию 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, то функцию подсчета количества людей можно записать следующим образом.
y=f(x)
В этом выражении буквой y обозначено время подсчета количества людей в комнате.
Множество О
Полезным обозначением асимптотического поведения функции является верхняя граница — функция, значения которой всегда больше значений изучаемой функции. Говорят, что верхняя граница некоторой функции растет быстрее, чем рассматриваемая функция. Специальное обозначение "большого-O" используется для описания этого роста. Это записывается как f(x) ∈ О(g(x)) и читается так: f принадлежит множеству "O-большого" от g. Формальное математическое определение имеет следующий вид.
Если f(x) принадлежит множеству большого O(g(x)) , то ∃c и x', такие что f(x)≤c∙g(x), ∀x>x'
Это означает, что время вычисления функции f(x) всегда меньше времени вычисления функции g(x), умноженного на некоторую константу, и это справедливо всегда, для всех значений x, больших некоторого начального значения х'.
Другими словами, мы ищем функцию, которая ведет себя не лучше, чем наш алгоритм в наихудшей ситуации. Можно посмотреть на результаты того, как ведет себя функция при очень больших значениях входных параметров, и понять, как ведет себя алгоритм.