Генераторы псевдослучайных чисел с применением Crypto++ - Польза случайных чисел
ОГЛАВЛЕНИЕ
Польза случайных чисел
В труде Дональда Кнута «Искусство компьютерного программирования, том 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... идеально пройдет простой тест частоты, но не выдержит продвинутые тесты, такие как серии, длиннейшие серии в блоке и накопленные суммы. Представленный двоичный поток парадоксален тем, что является правильной последовательностью случайных чисел. В объективном генераторе появление каждого потока равновероятно.