Второе издание
 Скачать 3.09 Mb.
|
|
Принцип работы и реализация Компьютеры— это предсказуемые устройства. Действительно, трудно найти слу- чайное поведение в системе, поведение которой можно практически полностью программировать. Однако окружающая среда, где находится машина, полна различ- ных шумов, которые недетерминированы и которые можно измерить. Источники таких шумов включают моменты времени, в которые возникают события, связанные с аппаратными устройствами, а также события, связанные с взаимодействием поль- зователей и компьютера. Например, интервалы времени между нажатиями клавиш, перемещения мыши, интервалы времени между некоторыми типами прерываний и время выполнения запроса блочного ввода-вывода являются недетерминированны- ми, и, кроме того, их не может измерить внешний злоумышленник. Случайная ин- формация, которая получается из этих событий, записывается в пул энтропии. Пул растет и заполняется случайными и непредсказуемыми шумовыми данными. По мере добавления данных в пул вычисляется оценка энтропии, и итоговое значение запо- минается. Это позволяет всегда иметь информацию о значении энтропии в пуле. На рис. Б.1 показана диаграмма прохождения потока энтропии в пул и из пула. 2 Джон фон Нейман (28 декабря 1903-8 февраля 1957) работал в Институте специальных исследо- ваний в Принстоне (Institute for Advanced Study; Princeton). Он внес большой вклад в математиче- ские, экономические и компьютерные науки. Среди наиболее значительных его разработок- тео- рия игр, фон-неймановские алгебры и фон-неймановская проблема узких мест. 424 Приложение Б Для доступа к пулу энтропии, как из пространства ядра, так и из пространства пользователя, ядро предоставляет набор интерфейсов. Когда выполняется обра- щение к этим интерфейсам, ядро вначале вычисляет хеш-значение SHA данных из пула. Алгоритм SHA (Secure Hash Algorithm, алгоритм вычисления безопасного хеш- значения) — это алгоритм вычисления дайджеста сообщения (профиля сообщения, message digest), который был разработан Агентством национальной безопасности (National Security Agency, NSA) и утвержден в качестве федерального стандарта США Национальным институтом стандартов и технологий (NIST) (федеральный стандарт по обработке информации, FIPS 186). Вычисление дайджеста сообщения выполняет- ся с помощью специального алгоритма, который принимает сообщение переменно- го размера (большое или маленькое) и выдает на выходе хеш-значение фиксирован- ного размера (обычно размером 128 или 160 байт). Это фиксированное значение и представляет собой дайджест. Входное сообщение не может быть реконструировано по его хеш-значению. Более того, простое изменение входного сообщения (напри- мер, изменение одного символа) приведет к радикальному изменению хеш-значения. Алгоритмы вычисления дайджестов сообщений могут использоваться по-разному, включая проверку подлинности данных и дактилоскопию. Другие алгоритмы вычис- ления дайджестов — это MD4 и MD5. Пользователю возвращается хеш-значение SHA пула, к содержимому пула энтропии непосредственно обращаться нельзя. Считается, что по хеш-значению невозможно получить никакую информацию о состоянии пула. Поэтому если известно несколько значений из пула, то это не дает никакой информа- ции о прошлых и будущих значениях. Ядро может использовать оценку энтропии и отказаться выполнить запрос на считывание данных из пула, если значение энтропии равно нулю. По мере того как из пула считываются данные, оценка энтропии умень- шается. Это реакция на то, что о пуле становится известно больше информации. <- Пространство ядра 10110001- Ядро использует значения интервалов времени между успешными прерываниями для заполнения пула энтропии с помощью функции add_keyboard_random ness() 1111010000-> 11100101100000110101 01111010101110100010 00100010110101011000 Пул энтропии Пространство пользователя -> Приложения считывают информацию из пула через специальные файлы /dev/random и /dev/urandom Рис. Б.1. Прохождение энтропии через пул энтропии ядра Когда значение оценки энтропии достигает нуля, то ядро все равно может воз- вращать случайные числа. Однако в этом случае теоретически появляется возмож- ность того, что злоумышленник сможет предугадать результат вывода. Для этого тре- буются все результаты вывода из пула энтропии, а также чтобы злоумышленник смог Генератор случайных чисел ядра 425 При нажатии клавиш генерируются прерывания выполнить криптографический анализ алгоритма SHA. Так как алгоритм SHA счи- тается безопасным, то это невозможно. Для высоконадежной криптографии оценка энтропии позволяет гарантировать устойчивость случайных чисел. Для большинства пользователей такая дополнительная гарантия не нужна. Почему это реализовано в ядре? Критерием того, что какую-либо возможность необходимо реализовать в ядре, является слож- ность реализации этой возможности в пространстве пользователя. Недопустимо вводить что-либо в ядро только потому, что мы это можем сделать. Может показаться, что генерато- ру случайных чисел и пулу энтропии не место в ядре. Однако существует, по крайней мере, три причины, по которым они должны быть в ядре. Во первых, генератору необходим доступ к системным событиям, таким как прерывания и ввод данных пользователями. Для обеспечения доступа к информации об этих событиях из пространства пользователя необходимо экспорти- ровать специальные интерфейсы, чтобы информировать пространство пользователя о том, что эти события произошли. Даже если эти данные будут экспортироваться, то доступ к ним будет не простым и не быстрым. Во-вторых, генератор случайных чисел должен быть безопасным. Хотя такая система и может выполняться с правами пользователя root, тем не менее ядро явля- ется значительно более безопасным местом для пула энтропии. И наконец, самому ядру также необходимы случайные числа. Получать информацию о случайных числах, которая необходима ядру, из пространства пользователя — это не практично. В связи с этим генератор случайных чисел работает в ядре. Проблема с загрузкой системы Когда ядро загружается, оно выполняет последовательность действий, которые гарантированно можно предугадать. Следовательно, злоумышленник может предска- зать состояние пула энтропии на этапе загрузки. Еще хуже то, что каждая загрузка очень похожа на все остальные и пул инициализируется при каждой загрузке в очень близкие значения. Это уменьшает точность оценки энтропии, потому что нет ника- кого способа обеспечить, чтобы энтропия, которая добавляется на этапе загрузки, была менее предсказуема, чем энтропия, которая добавляется при такой же загрузке в другое время. Для решения проблемы большинство Linux-систем сохраняет на диске содер- жимое части пула энтропии между перегрузками системы. При старте системы со- храненные данные считываются и записываются в пул энтропии. Загрузка предыду- щего содержимого пула в текущий пул позволяет обойтись без увеличения оценки энтропии. Таким образом, злоумышленник не может предугадать состояние пула энтропии, не зная одновременно предыдущего и текущего состояний системы. Интерфейсы для ввода энтропии Ядро экспортирует следующее семейство интерфейсов, которые могут использо- ваться драйверами и системами для ввода данных в пул энтропии. void add_interrupt_randomness(int irq) void add_keyboard_randomness (unsigned char scancode) void add_mouse_randomness(__u32 mouse_data) 426 Приложение Б Функция add_interrupt_randomness () вызывается системой обработки преры- ваний, когда приходит прерывание, обработчик которого зарегистрирован с флагом SA_SAMPLE_RANDOM. Параметр i r q — это номер прерывания. Генератор случайных чисел использует интервалы времени между прерываниями, как источник шума. Следует помнить, что не все устройства для этого подходят. Если устройства гене- рируют прерывания детерминированным образом (например, прерывания тайме- ра) или на них может воздействовать внешний злоумышленник (например, сетевые устройства), то такие устройства нельзя использовать для ввода информации в пул. Подходящее устройство — жесткий диск, который генерирует прерывания с непред- сказуемой частотой. Функция add_keyboard_randomness () использует скан-коды и интервалы вре- мени между нажатиями клавиш для ввода энтропии в пул. Интересно, что эта функ- ция достаточно интеллектуальна и игнорирует повторение символов при постоян- ном нажатии клавиши, потому что повторяющиеся скан-коды и интервалы времени вносят мало энтропии. Функция add_mouse_randoraness () использует позицию указателя мыши и интер- валы времени между прерываниями для заполнения пула. Параметр mouse_data — это позиция указателя, которая возвращается аппаратным обеспечением. Эти три функции добавляют передаваемые данные в пул энтропии, вычисляют оценку энтропии добавляемых данных и увеличивают оценку энтропии пула на вы- численное значение. Все эти экспортируемые интерфейсы используют внутреннюю функцию add_timer_randomness () для ввода данных в пул. Эта функция вычисляет интер- валы времени между успешными событиями одного типа и добавляет эти значения в пул. Например, интервалы времени между успешными прерываниями жесткого дис- ка достаточно случайны, особенно если измерять достаточно точно. Самые младшие биты — это обычно электрический шум. После того как эта функция вводит данные в пул, она вычисляет количественную характеристику того, насколько эти данные случайны. Это делается путем вычисления отклонения первого, второго и третье- го порядка от предыдущего момента времени и изменения этих отклонений перво- го, второго и третьего порядка. Наибольшее из этих отклонений, округленное до 12 бит, используется в качестве оценки энтропии. Интерфейсы для вывода энтропии Для получения случайных чисел внутри ядра экспортируется один интерфейс. void get_random_bytes(void *buf, int nbytes) Эта функция сохраняет nbytes случайных байтов в буфере памяти, на который указывает параметр buf. Функция возвращает данные, даже если оценка энтропии равна нулю. Для ядра это не так критично, как для пользовательских криптографи- ческих программ. Случайные данные мало используются в ядре, в основном они нужны сетевой подсистеме для генерации стартового номера последовательности сегментов при соединении по протоколу TCP. Код ядра может выполнить следующий код для получения случайных данных раз- мером в одно машинное слово. Генератор случайных чисел ядра 427 unsigned long rand; get_random_bytes(&rand, sizeof(rand)); Для программ, которые выполняются в пространстве пользователя, предоставля- ется два символьных устройства: /dev/random и /dev/urandom. Первое устройство, /dev/random, используется, когда необходимы гарантированно случайные данные для криптографических приложений с высоким уровнем безопасности. Это устрой- ство выдает только то количество битов данных, которое соответствует оценке эн- тропии в ядре. Когда оценка энтропии становится равной нулю, операция чтения устройства /dev/random блокируется и не возвращает данные, пока значение эн- тропии не станет существенно положительным. Устройство /dev/urandom не имеет последней возможности, а в остальном работает аналогично. Оба устройства возвра- щают данные из одного и того же пула. Чтение из обоих файлов выполняется очень просто. Ниже показана функция пользовательской программы, которая служит для считывания одного машинного слова случайных данных. , i 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, используя программу del. dd if=/dev/urandom of=$file count=l bs=$bytes 428 Приложение Б в Сложность алгоритмов В компьютерных и связанных с ними дисциплинах полезно выражать сложность, или масштабируемость, алгоритмов с помощью количественных значащих ха- рактеристик (в отличие от менее наглядных характеристик, таких как быстрый или медленный). Существуют различные методы представления масштабируемости. Один из наиболее часто используемых подходов — это исследование асимптотиче- ского поведения алгоритмов. Асимптотическое поведение — это поведение алгоритма при достаточно больших значениях входных параметров или, другими словами, при стремлении входных параметров к бесконечности. Асимптотическое поведение пока- зывает, как масштабируется алгоритм, когда его входные параметры принимают все большие и большие значения. Исследование масштабируемости алгоритмов, т.е. из- учение свойств алгоритма при больших значениях входных параметров, позволяет смоделировать поведение алгоритма по отношению к тестовым задачам и лучше по- нять особенности этого поведения. Алгоритмы Алгоритм — это последовательность действий, возможно, с одним входом или более и, в конечном счете, с одним результатом или выходом. Например, подсчет количества людей в комнате представляет собой алгоритм, для которого люди, на- ходящиеся в комнате, являются входными данными, а количество людей в комнате — выходными данными. Операции замещения страниц в ядре Linux или планирование выполнения процессов — это тоже примеры алгоритмов. Математически алгоритм аналогичен функции (или, по крайней мере, может быть смоделирован с помощью функции). Например, если мы обозначим алгоритм подсчета людей в комнате бук- вой f, а количество людей, которых необходимо посчитать, буквой х, то функцию подсчета количества людей можно записать следующим образом. y=f(х) В этом выражении буквой у обозначено время подсчета количества людей в ком- нате. Множество О Это означает, что время вычисления функции f ( x ) всегда меньше времени вы- числения функции g (х), умноженного на некоторую константу, и это справедливо всегда, для всех значений х, больших некоторого начального значения х'. Другими словами, мы ищем функцию, которая ведет себя не лучше, чем наш алго- ритм в наихудшей ситуации. Можно посмотреть на результаты того, как ведет себя функция при очень больших значениях входных параметров, и понять, как ведет себя алгоритм. Множество большого-тета Когда говорят об обозначении большого-О, то чаще всего имеют в виду то, что Дональд Кнут (Donald Knulh) описывал с помощью обозначения "большого-тета". Обозначение "болыпого-О" соответствует верхней границе. Например, число 7 — это верхняя граница числа 6, кроме того, числа 9, 12 и 65— это тоже верхние границы числа 6. Когда рассматривают рост функции, то обычно наиболее интересна наимень- шая верхняя граница или функция, которая моделирует как верхнюю, так и нижнюю границу'. Профессор Кнут описывает это с помощью обозначения большого-тета следующим образом. Если f (х) принадлежит множеству большого-тета от g (x), то g(х) является одновременно и верхней и нижней границей f(х) Можно также сказать, что функция f (x) порядка функции g (х). Порядок, или множество "большого-тета" алгоритма, — один из наиболее важных математических инструментов изучения алгоритмов. Следовательно, когда говорят об обозначении большого-О, то чаще всего имеют в виду наименьший возможный вариант "большого-О" — "болыное-тета". Об этом не нужно особо волноваться, если, конечно, нет желания доставить удовольствие про- фессору Кнуту. 1 Если интересно, то нижняя граница описывается с помощью обозначения большого-омега. Определение аналогично определению множества большого-О, за исключением того, что значе- ния функции g ( s ) должны быть меньше значений функции f (х) или равны им. 430 Приложение В Полезным обозначением асимптотического поведения функции является верхняя граница — функция, значения которой всегда больше значений изучаемой функции. Говорят, что верхняя граница некоторой функции растет быстрее, чем рассматрива- емая функция. Специальное обозначение "большого-О" используется для описания этого роста. Это записывается как f (х) О (g (х} ) и читается так: f принадлежит множеству "О-болыпого" от g. Формальное математическое определение имеет сле- дующий вид. Е с л и f ( x ) п р и н а д л е ж и т м н о ж е с т в у б о л ь ш о г о O ( g ( х ) ) , т о Объединяем все вместе Опасность, связанная со сложностью алгоритмов Очевидно, что будет разумным избегать алгоритмов, которые масштабируются, как О ( n ! ) или О(2 n ) . Более того, замена алгоритма, который масштабируется, как О(n), алгоритмом, который масштабируется, как O(1), — это обычно серьезное улуч- шение. Тем не менее это не всегда так, и нельзя принимать решение вслепую, бази- руясь только на описании "болыпого-О". Вспомните, что в определении множества О ( g ( х ) ) фигурирует константа, на которую умножается значение функции g(х). Поэтому есть возможность, что алгоритм, который масштабируется, как O(1), будет выполняться в течение 3 часов. Следовательно, он будет выполняться всегда в те- чение 3 часов, независимо от количества входных данных, но это может оказаться дольше, по сравнению с алгоритмом, который масштабируется, как О ( n ) , при не- большом количестве входных данных. При сравнении алгоритмов необходимо всег- да принимать во внимание количество входных данных. Не стоит слепо оптимизи- ровать для некоторого случайно выбранного варианта. Сложность алгоритмов 431 Вернемся снова к подсчету количества людей в комнате. Допустим, что можно считать по одному человеку за секунду. Следовательно, если в комнате находится 7 человек, то подсчет займет 7 секунд. Очевидно, что если будет n человек, то подсчет всех займет n секунд. Поэтому можно сказать, что этот алгоритм масштабируется, как О(n). Что если задача будет состоять в том, чтобы станцевать перед всеми, кто находится в комнате? Поскольку, независимо от того, сколько человек будет в комна- те, это займет одно и то же время, значит, этот алгоритм масштабируется, как O(1). В табл. В.1 показаны другие часто встречающиеся характеристики сложности. Таблица В.1. Значения масштабируемости алгоритмов во времени O(g(x)) Название 1 log(n) n n 2 n 3 2 n n! Как масштабируется алгоритм представления всех людей в комнате друг другу? Какая функция может промоделировать этот алгоритм? Для представления одного человека необходимо 30 секунд, сколько времени займет представление 10 человек друг другу? Что будет в случае 100 человек? Постоянная (отличная масштабируемость) Логарифмическая Линейная Квадратичная Кубическая Показательная, или экспоненциальная (плохо) Факториал (очень плохо) |