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

Физический термин энтропия — это мера беспорядка и случайности в любой системе. Энтропия измеряется в единицах энергии на единицу температуры (Джоуль на градус Кельвина). Когда Клод Шеннон (Claude Shennon) [98] Клод Шеннон (30 апреля 1916–24 февраля 2001) работал инженером в компании Bell Labs. В его наиболее известной работе Математическая теории связи, опубликованной в 1948 году, впервые были разработаны основы информационной теории и было введено понятие энтропии Шеннона. Шеннон также любил кататься на одноколесном велосипеде. , создатель информационной теории, искал термин для представления случайности информации, великий математик Джон фон Нейман (John von Neumann) [99] Джон фон Нейман (28 декабря 1903–8 февраля 1957) работал в Институте специальных исследований в Принстоне (Institute for Advanced Study; Princeton). Он внес большой вклад в математические, экономические и компьютерные науки. Среди наиболее значительных его разработок — теория игр, фон-неймановские алгебры и фон-неймановская проблема узких мест. предложил ему использовать термин энтропия, потому что никто толком не понимает, что за этим понятием кроется. Шеннон согласился, и сегодня это звучит как энтропия Шеннона . Некоторые ученые считают, что такое двойное название только вносит путаницу, и когда речь идет об информации, то используют термин неопределенность . Разработчики ядра, наоборот, считают, что "энтропия" — это "круто", и поддерживают использование данного термина.

При рассмотрении генераторов случайных чисел понятие энтропии Шеннона является очень важным. Эта характеристика измеряется в битах на символ. Высокое значение энтропии означает, что в последовательности символов мало полезной (точнее, предсказуемой) информации и много случайного "мусора". Ядро поддерживает пул энтропии, который пополняется данными, возникающими в результате недетерминированных событий, связанных с аппаратными устройствами. В идеале, этот пул содержит полностью случайные данные. Для того чтобы иметь представление о значении энтропии пула, ядро постоянно вычисляет меру неопределенности данных в пуле. По мере того как ядро добавляет данные в пул, оно оценивает меру случайности добавляемых данных. И наоборот, по мере того как данные извлекаются из пула, ядро уменьшает значение оценки энтропии. Соответствующая количественная характеристика называется оценкой энтропии . Если значение оценки энтропии становится равным нулю, то ядро может отказаться выполнять запрос по считыванию данных из пула.

Генератор случайных чисел ядра был предложен в версии 1.3.30 и находится в файле drivers/char/random.c.

Компьютеры — это предсказуемые устройства. Действительно, трудно найти случайное поведение в системе, поведение которой можно практически полностью программировать. Однако окружающая среда, где находится машина, полна различных шумов, которые недетерминированы и которые можно измерить. Источники таких шумов включают моменты времени, в которые возникают события, связанные с аппаратными устройствами, а также события, связанные с взаимодействием пользователей и компьютера. Например, интервалы времени между нажатиями клавиш, перемещения мыши, интервалы времени между некоторыми типами прерываний и время выполнения запроса блочного ввода-вывода являются недетерминированными, и, кроме того, их не может измерить внешний злоумышленник. Случайная информация, которая получается из этих событий, записывается в пул энтропии. Пул растет и заполняется случайными и непредсказуемыми шумовыми данными. По мере добавления данных в пул вычисляется оценка энтропии, и итоговое значение запоминается. Это позволяет всегда иметь информацию о значении энтропии в пуле. На рис. Б. 1 показана диаграмма прохождения потока энтропии в пул и из пула.

Рис. Б.1. Прохождение энтропии через пул энтропии ядра

Для доступа к пулу энтропии, как из пространства ядра, так и из пространства пользователя, ядро предоставляет набор интерфейсов. Когда выполняется обращение к этим интерфейсам, ядро вначале вычисляет хеш-значение SHA данных из пула. Алгоритм SHA (Secure Hash Algorithm, алгоритм вычисления безопасного хеш- значения) — это алгоритм вычисления дайджеста сообщения (профиля сообщения, message digest), который был разработан Агентством национальной безопасности (National Security Agency, NSA) и утвержден в качестве федерального стандарта США Национальным институтом стандартов и технологий (NIST) (федеральный стандарт по обработке информации, FIPS 186). Вычисление дайджеста сообщения выполняется с помощью специального алгоритма, который принимает сообщение переменного размера (большое или маленькое) и выдает на выходе хеш-значение фиксированного размера (обычно размером 128 или 160 байт). Это фиксированное значение и представляет собой дайджест. Входное сообщение не может быть реконструировано по его хеш-значению. Более того, простое изменение входного сообщения (например, изменение одного символа) приведет к радикальному изменению хеш-значения. Алгоритмы вычисления дайджестов сообщений могут использоваться по-разному, включая проверку подлинности данных и дактилоскопию. Другие алгоритмы вычисления дайджестов — это MD4 и MD5. Пользователю возвращается хеш-значение SHA пула, к содержимому пула энтропии непосредственно обращаться нельзя. Считается, что по хеш-значению невозможно получить никакую информацию о состоянии пула. Поэтому если известно несколько значений из пула, то это не дает никакой информации о прошлых и будущих значениях. Ядро может использовать оценку энтропии и отказаться выполнить запрос на считывание данных из пула, если значение энтропии равно нулю. По мере того как из пула считываются данные, оценка энтропии уменьшается. Это реакция на то, что о пуле становится известно больше информации.