Генераторы псевдослучайных чисел с применением Crypto++

Written on 06 Ноября 2013.

Загрузки
•    Скачать исходники - пример 1 - Win32 API CryptGenRandom - 4.2 Кб
•    Скачать исходники - пример 2 – Линейный конгруэнтный генератор Crypto++ - 2.9 Кб
•    Скачать исходники - пример 3 - Crypto++ RandomPool - 4.3 Кб
•    Скачать исходники - пример 4 - Crypto++ AutoSeededRandomPool - 4.6 Кб
•    Скачать исходники - пример 5 - Crypto++ AutoSeededX917RNG - 4.5 Кб
•    Скачать документацию - FIPS 140-2 - 801 Кб
•    Скачать документацию – Комплект проверки правильности RNG от NIST - 68 Кб

Случайные числа являются простейшим элементов не только для специалистов по криптографии, но и для специалистов в области теории вычислительных машин и систем и программистов. Требуется метод, быстро генерирующий псевдослучайный поток криптографически стойких чисел. Однако цели прямо противоположны - псевдослучайные последовательности могут генерироваться быстро, либо могут генерироваться стойко; но обычно не быстро со свойствами, не поддающимися криптоанализу.

В статье рассматриваются следующие вопросы:
•    Польза случайных чисел
•    Классы генераторов случайных чисел
•    Типы генераторов
•    Источники случайных чисел
•    Тестирование последовательностей
•    Выбор начального числа
•    Функция выработки ключа
•    Стандартный C++ rand( )
•    Линейный конгруэнтный генератор
•    Минимальный стандартный генератор
•    Нелинейные конгруэнтные генераторы
•    Win32 API CryptGenRandom( )
•    Компиляция и внедрение Crypto++
•    Генераторы случайных чисел Crypto++
•    Таблица применений
•    Дополнительные CSPRNG (криптостойкие генераторы псевдослучайных чисел)
•    Плохие генераторы

Польза случайных чисел

В труде Дональда Кнута «Искусство компьютерного программирования, том II: Получисленные алгоритмы» названы следующие типичные применения случайных чисел:
•    Моделирование
•    Взятие образцов
•    Численный анализ
•    Компьютерное программирование
•    Принятие решений
•    Эстетика
•    Досуг

Моделирование и взятие образцов говорят сами за себя. Численный анализ использует случайные числа для решения сложных задач. Например, модель "хищник - жертва" использует дифференциальные уравнения. Четвертое столь же очевидно: взято из Кнута по пункту пять – «принятие решений»:

Сообщается, что многие руководители принимают решения путем подбрасывания монеты или бросания дротика, и т.д. Также ходят слухи, что некоторые профессора колледжей готовят свои оценки на такой же основе. Иногда важно принять полностью «объективное» решение. Случайность также является неотъемлемой частью оптимальных стратегий в теории матричных игр.

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

Без случайного шума

Случайный шум

Касательно эстетики, Adobe Photoshop использует случайные числа во многих фильтрах, в их числе – размывка, деформация и шум.

Фильтры Adobe Photoshop

Наконец, досуг включает в себя тасование карт или вращение костей.

Классы генераторов случайных чисел

Взято из NIST, FIPS 140-2:

Генераторы случайных чисел относятся к одному из двух классов: детерминированные и недетерминированные. Детерминированный RNG(генератор случайных чисел) состоит из алгоритма, генерирующего последовательность битов исходя из начального значения. Недетерминированный RNG дает вывод, зависящий от некоторого непредсказуемого физического источника, не контролируемого человеком.

Неспециалисты обычно называют недетерминированный генератор «генератором истинно случайных чисел».

Типы генераторов случайных чисел

Существует два типа детерминированных генераторов случайных чисел для программиста на выбор:
• Генераторы псевдослучайных чисел
• Криптографически стойкие генераторы случайных чисел

Генераторы псевдослучайных чисел включают в себя такие генераторы, как линейные конгруэнтные генераторы и вихри Мерсенна. Они быстро дают равномерно распределенный поток по интервалу [0, 1). Они не обеспечивают криптографическую стойкость.

Криптографически стойкие генераторы случайных чисел имеют дополнительные свойства, делающие их подходящими для применения в криптографии. Криптографические применения следующие:
•    Генерация ключей
•    Защитные слова
•    Соли
•    Одноразовые шифры

Защитное слово – число или строка битов, используемая только один раз. Это псевдослучайное число, выданное в протоколе аутентификации, чтобы предотвратить повторное использование старых коммуникаций в атаке путём повтора с использованием перехваченных данных. Для обеспечения однократного использования защитного слова оно должно меняться во времени (включать достаточно детальную метку времени в свое значение) или генерироваться с достаточным количеством случайных битов, чтобы обеспечить ничтожный в вероятностном смысле шанс повторения ранее сгенерированного значения.

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

Источники случайных чисел

Пусть даже NIST(Национальный институт стандартов и технологий) сейчас не признает никаких недетерминированных RNG, можно использовать детерминированный RNG для создания начального числа для криптографически стойкого генератора псевдослучайных чисел. Взято из FIPS 140-2:

До тех пор, пока не появится утвержденный стандарт недетерминированного RNG, недетерминированные RNG, утвержденные для применения в секретных областях применения, могут использоваться для генерации ключей или для создания начальных чисел для утвержденных детерминированных RNG, применяемых при генерации ключей.

NIST предоставляет тесты, позволяющие разработать эвристические правила для определения качества последовательности из рассматриваемого генератора. Для загрузки добавлен комплект проверки правильности NIST, FIPS 140-2, и FIPS 186. Дополнительно читатель может изучить ANSI 9.17, приложение C (Утвержденные генераторы случайных чисел для FIPS 140-2, Требования к безопасности криптографических устройств).

Также представляет интерес NIST SP800-90, Рекомендации по генерации случайных чисел с помощью детерминированных генераторов случайных двоичных последовательностей. Некоторые осторожные специалисты по криптографии не рекомендуют использовать Dual_EC-DRBG (вариант эллиптической кривой), но рекомендуют использовать CTR_DRBG или Hash_DRBG. Статья Шнейера находится здесь: Внедрило ли агентство национальной безопасности скрытую лазейку в новый стандарт шифрования?

Подготовка к тестам

В случайной последовательности, в которой ожидается появление каждой из десяти десятичных цифр примерно 1/10 раз, если основание системы счисления равно 2 (цифры 0 или 1), каждая цифра должна представлять собой примерно 50% последовательности.

Тестирование требует отличать хорошие источники от плохих вариантов. Например, двоичный поток ...1111111110000000000... идеально пройдет простой тест частоты, но не выдержит продвинутые тесты, такие как серии, длиннейшие серии в блоке и накопленные суммы. Представленный двоичный поток парадоксален тем, что является правильной последовательностью случайных чисел. В объективном генераторе появление каждого потока равновероятно.

Тестирование последовательностей

Ниже читатель найдет различные тесты, применяемые при оценке эффективности генератора. Полное описание читателю следует искать в Руководстве по статистическим тестам NIST и в Искусстве компьютерного программирования Кнута.

Кроме того, следует посмотреть SP800-22 NIST, Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических применений. На сайте NIST есть программное обеспечение для тестирования генератора.

NIST требует, чтобы PRNG прошел 16 статистических тестов. Тесты перечислены ниже с кратким описанием.
•    Частота – соотношение нулей и единиц для всей последовательности.
•    Частота внутри блока – определяет, равна ли частота единиц в M-битовом блоке примерно M/2.
•    Серии – общее число серий нулей и единиц во всей последовательности, где серия – непрерывная последовательность одинаковых битов.
•    Длиннейшая серия единиц в блоке – определяет, соответствует ли длина длиннейшей серии единиц в тестируемой последовательности длине длиннейшей серии единиц, ожидаемой в случайной последовательности.
•    Ранг случайной двоичной матрицы – проверяет на линейную зависимость между подстроками фиксированной длины из исходной последовательности.
•    Дискретное преобразование Фурье (спектральное) – выявляет периодические свойства.
•    Сравнение с неперекрывающимся (непериодическим) шаблоном – число вхождений предопределенных целевых подстрок.
•    Сравнение с перекрывающимся (периодическим) шаблоном - число вхождений предопределенных целевых подстрок.
•    Универсальный статистический тест Маурера – число битов между совпадающими комбинациями. Задача теста – выяснить, можно ли существенно сжать последовательность без потери информации.
•    Сложность Лемпела-Зива – до какой степени можно сжать тестируемую последовательность. Последовательность считается неслучайной, если ее можно существенно сжать.
•    Линейная сложность – длина генерации регистра с обратной связью.
•    Серийность – частота всех без исключения перекрывающихся m-битовых комбинаций по всей последовательности.
•    Приблизительная энтропия - частота всех без исключения перекрывающихся m-битовых комбинаций.
•    Накопленная сумма – определяет, является ли накопленная сумма частичных последовательностей, входящих в тестируемую последовательность, слишком большой или слишком маленькой по сравнению с ожидаемым поведением накопленной суммы для случайных последовательностей.
•    Случайные отклонения – определяет, не превышает ли число появлений состояния в течение случайного блуждания ожидаемое число для случайной последовательности.
•    Разновидность случайных отклонений – обнаруживает отклонения от ожидаемого числа появлений разных состояний в течение случайного блуждания.

Кнут утверждает, что случайная последовательность должна пройти 13 статистических тестов. Тесты, не входящие в требования NIST, перечислены ниже.
•    Хи-квадрат – классическое определение
•    Колмогоров-Смирнов – расширяет критерий хи-квадрат до набора действительных чисел
•    Интервал – обнаруживает интервалы между числами по диапазону чисел в последовательности
•    Покер (разбиение) - n групп из пяти последовательных целых чисел из потока, соблюдающих итоговую схему. Одна пара - aabcd, три карты одного достоинства и две другого- aaabb, и т.д.
•    Сборщик купонов – Проверяет длину последовательности, требуемую для наблюдения всех чисел в наборе от 0 до d-1.
•    Перестановка – число порядков разбиения последовательности на части
•    Столкновение – используется, если критерий хи-квадрат превышает определенное число столкновений
•    Интервал между днями рождения – похож на парадокс дней рождения при выборе двух целых чисел в последовательности

Выбор начального числа

Криптографически стойкие RNG делят слабое место с другими генераторами псевдослучайных чисел – и те, и другие требуют начальное число на входе. Если секретное начальное число скомпрометировано, злоумышленник сможет мгновенно сгенерировать всю выходную последовательность, используя такой же алгоритм.

В 1995г. Дэвид Вагнер, тогда аспирант в Беркли, и его бывший однокурсник Ян Голдберг взломали генератор случайных чисел, используемый веб-браузером Netscape для защиты онлайновых транзакций. Они определили, что Netscape создавал свои начальные числа с помощью легко предсказываемых чисел, таких как время суток.

Функции выработки ключа

Функции выработки ключа используются (среди прочего) для выработки ключей на основе секретных паролей или парольных фраз. Для справки смотрите RFC 2898, Спецификация криптографии на базе паролей. Кроме того, платформа .NET предоставляет Rfc2898DeriveBytes, входящий в состав System.Security.Cryptography.

Функции выработки ключа часто используются вместе с несекретными параметрами для выработки ключей на основе общего секретного значения. Также может применяться KDF для обеспечения того, чтобы выработанные ключи обладали другими желательными свойствами, к примеру, исключение слабых ключей в некоторых специальных системах шифрования.

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

Такое применение можно выразить через Dk = KDF(ключ, соль, повторения), где Dk – выработанный ключ, KDF - функция выработки ключа, ключ – исходный ключ или пароль, соль – случайное число, играющее роль криптографической соли, а повторения относятся к числу повторений подфункции. Выработанный ключ используется вместо исходного ключа или пароля в качестве ключа для системы. Значения соли и числа повторений (если оно не фиксированное) хранятся вместе с хешированным паролем или отправляются в виде простого текста с помощью зашифрованного сообщения.

Стандартная функция 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().

Компиляция и внедрение 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 Блам Блам Шаб ? вырабатывает последовательность битов на основе квадратичных вычетов. Генератор останется криптостойким, пока целочисленная факторизация остается трудной. Еще не определено, где целочисленная факторизация находится в теории сложности.

форум c++