id: Гость   вход   регистрация
текущее время 13:20 28/03/2024
создать
просмотр
редакции
ссылки

Случайные числа

Применение случайных чисел


Многие компьютерные программы нуждаются в случайно выбранных числах. У компьютеров вообще большая проблема с получением подобных чисел, ведь электроника делается так, чтобы всякая инструкция давала предсказуемый результат. Поэтому для генерации потока со сложной и оттого труднопредсказуемой структурой применяются такие же сложные, но тщательно разработанные формулы, и подобные генераторы псевдо-случайных чисел (ГПСЧ) вполне подходят для большинства приложений. Однако, для криптографических задач применимы случайные числа только самого лучшего "качества": истинно случайные числа. Согласно 5 главе [13], генератор случайных битов — это устройство, производящее последовательность независимых и равномерно распределённых двоичных чисел.


Компонент PGP, ответственный за выдачу таких чисел, называется генератором (истинно) случайных чисел (ГСЧ), в противовес так называемым ГПСЧ, алгоритмам, генерирующим детерминированный поток, похожий на случайные данные. ГСЧ использует гибридный подход: он обращается к внешним источникам для обеспечения непредсказуемости и использует функцию хэширования, чтобы сгладить отклонения.


PGP держит пул с 5120 битами данных. Пул размещается в памяти и сохраняется на диск с завершением работы PGP, дабы он не был пуст при следующем запуске программы. Вход пула состоит из временных задержек между пользовательскими событиями, такими, как перемещения мыши и нажатия клавиш. Также поддерживается счётчик, фиксирующий приблизительную энтропию пула случайных чисел. Используя такое средство управления ГСЧ может принудительно набрать дополнительную случайность при недостатке текущей энтропии. Контроль очень точен, вплоть до учёта долей битов.


Энтропия — это мера неопределённости, она измеряется в битах. Если вам ничего неизвестно о 8-битовом числе, кроме того, что его длина 8 бит, значит, оно содержит 8 бит энтропии. Если вы знаете, что оно равно количеству детей некоего человека, тогда вам известно, что малые значения более вероятны, чем большие, следовательно, число содержит меньше 8 бит энтропии.

Вывод буфера случайности


Если PGP нуждается в случайных байтах, пул зашифровывается в режиме CBC, и содержимое регистра R помещается в буфер вывода пула случайных чисел (пул замещается собственным шифртекстом). Вместо блочного шифра процедура зашифрования использует функцию сжатия алгоритма SHA из-за её свойства однонаправленности, которым не обладают блочные шифры. После этого буфер вывода может считываться небольшими порциями. Если в ходе считывания в буфер вывода производится запись, буфер сбрасывается. Процедура вывода крайне консервативна. Каждый бит вывода зависит от каждого бита пула, кроме того, знание вывода не в силах помочь вам в реконструировании пула (исходя из допущения, что SHA — действительно однонаправленная функция). Когда пул случайных чисел содержит хотя бы 80 бит энтропии, его вывод становится практически непредсказуем.


В дополнение существует операция взбалтывания, подающая байты вывода обратно в пул, перемешивая его содержимое. Методы программы могут взбалтывать пул, если необходимо, чтобы случайные байты до и после перемешивания были "сверхнекоррелированы". Как таковая, операция взбалтывания не очень нужна, учитывая количество хэширований, уже применяющихся к пулу, но PGP выполняет её сразу после генерации ключа на случай, если взломщик получит состояние пула непосредственно в этот момент, чтобы это не могло ему помочь в воссоздании сгенерированного ключа.

Ввод буфера случайности


Все входные данные прежде всего помещаются в ключевой буфер. Если этот буфер становится достаточно заполнен (содержит 80 бит энтропии или 32 байта данных), его содержимое объединяется операцией XOR с подлежащими замене байтами пула, затем пул CBC-хэшируется с ключевым буфером и результат операции замещает одно слово пула (под "словом" понимается блок данных, имеющий длину выхода алгоритма хэширования). Операция XOR гарантирует, что не будет утеряна ни малейшая доля энтропии: мера непредсказуемости в перезаписываемом блоке данных по-прежнему сохраняется в выводе XOR'а.


Хэширование разрушает любую структурированность ввода. Случайные данные, собираемые из различных источников случайных событий, обычно не имеют равномерного распределения: одни значения в них более вероятны, чем другие. Хэширование этих данных не повышает и не понижает количество их энтропии, 1 зато маскирует все отклонения и возвращает равномерно распределённые биты.


Наиболее важный вопрос, ещё не рассмотренный нами, — это откуда на вход ГСЧ поступают случайные данные. Существует несколько способов для сбора энтропии в обычном ПК. PGP получает её из временных интервалов между нажатиями клавиш, задержек в движениях мыши, значений нажимаемых клавиш и из различных параметров под общим названием "данные ОС". Что представляют собой эти "данные ОС", зависит от конкретной операционной системы. В Windows в них входят статистические сведения о запущенных процессах, которые можно обнаружить в реестре. Обычно PGP накапливает энтропию в фоновом режиме, но если вдруг возникает потребность в большом объёме случайности, к примеру, при генерации ключевых пар, он отображает диалоговое окно с предложением к пользователю выполнять какие-либо произвольные действия.


Дополнительный источник случайности — это аппаратный генератор случайных чисел. Он представляет собой замеряющую шум электронную схему, которая бывает включена, к примеру, в процессор. В период 1999 года компания Intel планировала оснастить ими современную линейку процессоров, но затем отказалась от этой идеи. Вместо этого, устройство можно найти на некоторых материнских платах (с определёнными чипсетами Intel). Исходный код PGP готов к применению подобных устройств. В поставке исходников соответствующий флаг отключен (он определён в pgpSDKbuildflags.h), но в скомпилированном дистрибутиве включен. Аппаратные ГСЧ очень быстры и, вероятно, столь же надёжны, как и другие источники случайных событий. Обратитесь к [9] для подробного описания устройства.


PGP тщательно оценивает количество энтропии в каждом поступающем образце. Он не считает, что в значении нажимаемой клавиши имеется какая-либо энтропия, если та же клавиша присутствовала среди последних четырёх нажатий. Он также рассчитывает энтропию, исходя из ранее полученных образцов, по формуле 2E = abs(X-A), где E — мера энтропии в образце X с ожидаемым значением A. Эта формула подходит не для всякого потока данных, но вполне безопасна для оценок временных интервалов случайных событий. PGP вычисляет результат, используя A, основанное на предыдущем образце, затем используя A как производное первого порядка от двух последних образцов, затем используя A как производное второго порядка от трёх последних образцов, и т.д., обращаясь к стольким предыдущим шагам, к скольким нужно. Для событий, получаемых от мыши, рассматриваются только два последних образца, зато для нажатий клавиш ведётся история последних трёх событий. Из всех полученных E учитывается наименьшее из значений.


Что сильно затрудняет чтение исходных текстов PGP, так это то, что программа использует дробные значения энтропии, не прибегая к числам с плавающей точкой (не всякий процессор имеет такие инструкции, прежде всего 8088, под который был написан PGP 1.0, а также процессоры нынешних встраиваемых устройств). Для учёта количества энтропии используются два целых числа: первое содержит количество целых бит, floor(E) для математиков и программистов, а другое — (2E-floor(E)) ∗ 232. Значение умножается на 232, чтобы сделать его целочисленным. 2E может быть рассчитано непосредственно по формуле, приведённой выше, а самая важная проверка, что E>1, выполняется, если 2E>2.

Ложный пул


Несмотря на внимательное проектирование, разработчики PGP посчитали не слишком разумной идею использовать ГСЧ для выработки публичных параметров, скажем, ключей Elgamal: они решили, что нельзя давать внешнему миру узнать слишком много о внутреннем состоянии пула. Поэтому они сделали второй пул, который выдаёт одни нули: ложный пул. Он аналогичен настоящему ГСЧ, просто не генерирует никаких случайных чисел. Согласно комментарию в коде, вы не должны использовать это не слишком полезное устройство, "если не уверены в том, что вы делаете".


Ложный пул позволяет создать криптографически стойкий генератор псевдослучайных чисел (ГПСЧ, детерминированную функцию, производящую непредсказуемо выглядящий поток данных), но для этого вам понадобится настоящий пул случайных чисел. Если просто воспользоваться ложным пулом, он, разумеется, не будет должным образом инициализирован, поэтому его внутреннее состояние должно быть заполнено выводом из реального пула, после чего генератор начнёт выдавать необходимые случайные числа. Эта процедура снижает нагрузку на пул случайных чисел и считается безопасной. Кроме того, она являет собой отличный пример "не очень хорошего программирования": один автор устанавливает требование на надлежащую инициализацию ГПСЧ с помощью пула случайных чисел (обязательного для создания генератора); другой автор обходит эту меру безопасности, придумывая ложный пул.


Исследованные нами файлы:


  • pgpRndWin32.h
  • pgprandompool.h
  • pgpRndWin32.c
  • pgprandompool.c

Исторический экскурс: PGP 1.0


В порядке небольшого отступления, представляющего исторический интерес, я бы хотел процитировать комментарий из файла random.c, входившего в дистрибутив первоначального PGP 1.0:


Данный код генерирует истинно случайные числа. Они извлекаются из счётчика, который непрерывно возрастает, пока клавиатура сканируется на предмет пользовательского ввода. Каждый раз, когда пользователь нажимает на клавишу, наименее значащие биты счётчика помещаются в стек. Впоследствии этот запас случайных чисел может быть выведен из стека в программу, нуждающуюся в стохастических числах. Криптографические приложения используют именно такой тип случайности.

Это выглядит надёжным (правда, перед использованием этих байтов следовало бы применять хэширование) и куда более простым, ведь данный код был рассчитан на конкретную операционную систему и процессор: MS-DOS, однозадачную ОС, программы в которой имели непосредственный доступ к аппаратной части компьютера. На другой системе этот код не будет работать, как должен, поскольку ОС может обрабатывать нажатия клавиш через фиксированные предсказуемые интервалы.


Назад | Дальше



1 Если только ввод не содержал больше бит энтропии, чем имеет длина выхода хэш-функции.


 
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3