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

void add_interrupt_randomness(int irq);

void add_keyboard_randomness(unsigned char scancode);

void add_mouse_randomness(__u32 mouse_data);

Функция add_interrupt_randomness()вызывается системой обработки прерываний, когда приходит прерывание, обработчик которого зарегистрирован с флагом SA_SAMPLE_RANDOM. Параметр irq— это номер прерывания. Генератор случайных чисел использует интервалы времени между прерываниями, как источник шума. Следует помнить, что не все устройства для этого подходят. Если устройства генерируют прерывания детерминированным образом (например, прерывания таймера) или на них может воздействовать внешний злоумышленник (например, сетевые устройства), то такие устройства нельзя использовать для ввода информации в пул. Подходящее устройство — жесткий диск, который генерирует прерывания с непредсказуемой частотой.

Функция 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 . Формальное математическое определение имеет следующий вид.