Генераторы псевдослучайных чисел с применением Crypto++ - Компиляция и внедрение Crypto++
ОГЛАВЛЕНИЕ
Компиляция и внедрение Crypto++
Смотрите соответствующую статью – Компиляция и внедрение Crypto++ в среду Microsoft Visual C++. Данная статья основана на исходных допущениях, представленных в вышеуказанной статье. Она также рассматривает большинство проблем, встречающихся в проектах – от командной строки до MFC (Ошибки C1083, C1189, LNK1104, LNK2001 и LNK2005). Кроме того, в ней приведены советы и тонкости использования библиотеки Crypto++.
LC_RNG
LC_RNG – линейный конгруэнтный RNG. Хотя этот генератор лишен криптографической ценности, он позволяет воспроизводить результаты при отладке программы. К тому же, он быстро генерирует блок байтов (или поток). При начальном значении 0x00 для LCG(линейный конгруэнтный генератор случайных чисел) устойчивый поток 0x80 является результатом. Это начальное значение дает период 1. Другие начальные значения работают как надо. Можно использовать пример 1 для сравнения результатов разных начальных значений линейных конгруэнтных генераторов.
RandomPool
RandomPool работает аналогично LCG – в том смысле, что одно и то же начальное значение дает одни и те же результаты. Но, в отличие от LC_RNG, в основе RandomPool сейчас лежит шифр MD5<SHA>. randpoool.cpp предоставляет typedef MDC<SHA>RandomPoolCipher. Затем RandomPool инициализируется и используется следующим образом (как показано в примере 3):
// Должно быть равно минимум 16 для RandomPool
const unsigned int SEEDSIZE = 16;
byte pcbSeed[ SEEDSIZE ];
// Рабочая область
const unsigned int BLOCKSIZE = 16 * 8;
byte pcbScratch[ BLOCKSIZE ];
...
// Инициализация случайной группы
CryptoPP::RandomPool rng( SEEDSIZE );
rng.Put( pcbSeed, SEEDSIZE );
// Использование
rng.GenerateBlock( pcbScratch, BLOCKSIZE );
AutoSeededRandomPool
Случайная группа с автоматическим заданием начального значения была предложена Леонардом Джанке, которую Вэй Дай позже встроил в Crypto++. AutoSeededRandomPool использует конструкцию RandPool из PGP(вполне хорошая секретность). Он подходит для всех криптографических целей, включая генерацию ключей и IV. В зависимости от операционной системы, начальное значение генератора задается с помощью следующего:
• CryptGenRandom()посредством поставщика служб шифрования
• /dev/urand
• /dev/rand
Пример 4 показывает применение AutoSeedeRandomPool.
// Рабочая область
const unsigned int BLOCKSIZE = 16 * 8;
byte pcbScratch[ BLOCKSIZE ];
// Создание
AutoSeededRandomPool rng;
// Случайный блок
rng.GenerateBlock( pcbScratch, BLOCKSIZE );
AutoSeededX917RNG
В отличие от LG_RNG и RandomPool, AutoSeededX917RNG не требует задания начального значения. Но надо указать утвержденный блочный шифр в качестве параметра шаблона. Два утвержденных шифра ANSI 9.17 - шифр DES с трёхкратным шифрованием и 3 ключами и SHA1. Пример 5 показывает использование вместе с SHA1.
// Рабочая область
const unsigned int BLOCKSIZE = 16 * 8;
byte pcbScratch[ BLOCKSIZE ];
// Создание
AutoSeededX917RNG< DES_EDE3 > rng;
// Случайный блок
rng.GenerateBlock( pcbScratch, BLOCKSIZE );
Таблица применений
Следующая таблица должна применяться при выборе генераторов случайных чисел на практике.
|
Требуется |
Использовать |
Комментарий |
|
Быстрая генерация |
LCG, не-LCG |
Слабый. быстрый |
|
Моделировать вращение костей |
LCG, не-LCG |
Слабый, быстрый |
|
Моделировать клиентов, входящих в очередь |
LCG, не-LCG |
Слабый, быстрый |
|
Соль |
Win32 API RandomPool AutoSeededRandomPool |
Мощный |
|
Начальное значение |
Win32 API RandomPool AutoSeededRandomPool |
Мощный |
|
Моделировать тасование для онлайн-казино |
AutoSeededX917RNG |
Криптостойкий |
|
Одноразовый шифр |
AutoSeededX917RNG |
Криптостойкий |
|
Генерировать симметричные или асимметричные ключи |
AutoSeededX917RNG |
Криптостойкий |
Дополнительные CSPRNG
Помимо вышеуказанных, разные стандарты FIPS признают другие криптостойкие генераторы. Криптостойкий генератор псевдослучайных чисел обертывает детерминированный генератор в трудную задачу. FIPS 186-3 утверждает алгоритм цифровой подписи (DSA) и Elliptic Curve DSA эллиптической кривой (ECDSA) в качестве CSPRNG.
Плохие генераторы
Метод среднего квадрата
Метод среднего квадрата для генерации был предложен Джоном фон Нейманом. Генератор использовался с 1946г. до середины 1950гг. Учтите, что в 1946г. компьютеру был 1 год. Недостатком генератора было слишком быстрое схождение к последовательности нулей; и, оказавшись в 0, он прицеплялся к 0.
RANDU мейнфрейма IBM
RANDU был конгруэнтным генератором, поставляемым IBM для применения на его компьютерах-мейнфреймах. Выбор a=65539 и m=231 оказался плохим. Когда авторы Численных рецептов на C сгенерировали пример и начертили плоскости, существовали только 11 плоскостей (а должно было быть порядка m1/k, где k – число случайных чисел, выбранных для задания в трехмерном пространстве). Генератор страдал от корреляции в каонном пространстве. Представитель IBM заявил:
«Мы гарантируем, что каждое число случайно по отдельности, но не гарантируем, что больше одного из них случайное».
Вычитание с займом
В 1992г. физики выяснили, что даже "качественные" генераторы случайных чисел могут давать неправильные результаты при определенных обстоятельствах. При подготовке к моделированию трехмерной модели Изинга исследователи испытали пакет на двумерной версии, имеющей известный ответ. Результат был неправильным.
Вывод
Данная статья представила читателю разные варианты генераторов псевдослучайных чисел на основе предметной области. Если нужен источник для моделирования или взятия образцов – выбирайте LCG. Если нужна мощность - выбирайте Win32 API, AutoSeededRandomPool или AutoSeededX917RNG. Если нужна криптостойкость – выбирайте AutoSeededX917. Наконец, если нужна энтропия – используйте Win32 API или AutoSeededRandomPool.
Кроме того, существуют другие генераторы (Crypto++ предоставляет некоторые из них). Например, CSPRNG Блам Блам Шаб ? вырабатывает последовательность битов на основе квадратичных вычетов. Генератор останется криптостойким, пока целочисленная факторизация остается трудной. Еще не определено, где целочисленная факторизация находится в теории сложности.