Генераторы псевдослучайных чисел с применением Crypto++ - Стандартная функция C++ rand( )
ОГЛАВЛЕНИЕ
Стандартная функция C++ rand( )
Стандартная функция C++ rand() использует линейный конгруэнтный генератор. Он быстро предоставляет равномерно распределенный поток битов, если параметры m, a, c, и X0 подходяще выбраны. Линейный конгруэнтный генератор не обеспечивает криптостойкость.
X0 называется начальным числом, часто использующим системное время. Генератор получает числа по следующей рекуррентной формуле:
Xn+1 = (aXn + c) mod m
Значения, выбранные для генератора в среде Microsoft Visual C++, показаны ниже. Обратите внимание, что & 0x7FFF выполняет модульное уменьшение.
return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
Интересно прочитать диссертацию Джоан Бойяр, Вывод последовательностей, генерируемых линейным конгруэнтным генератором, лишенных младших битов. Проницательный читатель должен понять, что, вероятно, существует онлайновый игорный сайт, использующий незащищенную систему. Заметьте, что эта атака отличается от Уонгинг (названной в честь Стэнфорда Уонга, бывшего исследователя IBM и профессионального игрока), являющейся системой карточного счета.
Минимальный стандартный генератор
Впервые предложенный Миллером, Левисом и Голдменом в 1969, этот генератор является линейным конгруэнтным генератором с c=0. Уточнение уменьшения константы дало мультипликативный генератор:
Xn+1 = aXn mod m
Пак и Миллер предлагают значения a = 75 = 16807, m = 231-1 = 2147483647. 231-1 дает период 231-2. Другие значения a существуют при использовании 231-1: 48271 и 69627. Нельзя применять никакие другие значения.
Нелинейный конгруэнтный генератор
Есть много быстрых генераторов случайных чисел, заменяющих функции rand() и srand() стандартной библиотеки C/C++. Читателю следует ознакомиться с Генераторы случайных чисел: хорошие трудно найти. Стив Пак предоставляет исходный код генератора Лехмера на своей веб-странице Генератор случайных чисел. Код Пака содержит дополнительные PRNG на основе следующих распределений (эти генераторы называются нелинейными конгруэнтными генераторами):
• Бернулли
• биномиальное
• равномерное
• геометрическое
• Паскаля
• Пуассона
Вихрь Мерсенна, разработанный в 1997 Макото Матсумото и Такуджи Нишимура, тоже входит в эту категорию. Интересный факт о компьютерных вирусах - 30 вирусов используют генератор. Предполагают, что эти вирусы созданы одним автором.
Win32 API CryptGenRandom( )
CryptGenRandom() генерирует запрошенное число байтов для пользователя. GenCryptRandom() – прекрасный источник энтропии в Windows, так как он доступен для всех операционных систем, кроме NT 3.51 и младше и Windows 95 (SR1) и младше.
Последнее начальное значение для CryptGenRandom хранится в реестре Windows Registry под ключом \SOFTWARE\Microsoft\Cryptography\RNG\Seed корневой ветви HKEY_LOCAL_MACHINE. Начальное значение вырабатывается операционными системами с использованием разных параметров системы. К примеру, на устройстве с Windows CE будет использовано следующее:
• Переключатели потока и ядра (CeGetRandomSeed)
• Идентификатор текущего процесса (GetCurrentProcessId)
• Идентификатор текущего потока (GetCurrentThreadId)
• Такты с момента загрузки (GetTickCount)
• Текущее время (GetLocalTime)
• Информация о памяти (GlobalMemoryStatus)
• Статистика хранилища объектов (GetStoreInformation)
После выработки начального значения оно подвергается двум криптографическим преобразованиям: хеш MD4 и шифрование RC4 для дополнительно перемешивания и обрезки.
Пример 1 показывает применение Windows API для получения псевдослучайных значений. Чтобы убрать бремя SDK(пакет разработки программ), программа использует LoadLibrary() и GetProcAddress().