No Image

Что такое псевдослучайные числа

СОДЕРЖАНИЕ
0 просмотров
22 января 2020

Что такое случайные числа?

Представьте себе снег, падающий на землю. Допустим, что мы сфотографировали природу в какой-то момент. Сможем ли мы ответить на такой вопрос: куда точно упадет следующая снежинка? Навряд ли, потому что это зависит от многих причин — от того, какая снежинка ближе к земле, как подует ветер и т.п. Можно сказать, что снежинка упадет в случайное место, то есть в такое место, которое нельзя предсказать заранее.

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

Случайные числа –это такая последовательность чисел, в которой невозможно назвать

следующее число, зная сколько угодно предыдущих.

Получить случайные числа на компьютере достаточно сложно. Иногда для этого применяют различные источники радиошумов. Однако математики придумали более универсальный и удобный способ — псевдослучайные числа.

Псевдослучайные числа– это последовательность чисел, обладающая свойствами, близкими к свойствам случайных чисел, в которой каждое следующее число вычисляется на основе предыдущих по некоторой математической формуле.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9138 – | 7300 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Псевдослучайное число — это особая цифра, создаваемая специальным генератором. Генератор таких чисел (PRNG), также известный как генератор детерминированных случайных битов (DRBG), представляет собой алгоритм для создания последовательности чисел, свойства которой аппроксимируют характеристики последовательностей случайных чисел. Генерируемая PRNG последовательность не является действительно случайной, поскольку она полностью определяется начальным значением, называемым начальным числом PRNG, которое может включать в себя действительно случайные значения. Хотя последовательности, которые ближе к случайным, могут создаваться с использованием аппаратных генераторов случайных чисел, генераторы псевдослучайных чисел на практике важны для скорости генерации чисел и их воспроизводимости.

Применение

PRNG являются центральными в таких приложениях, как моделирование (например, для метода Монте-Карло), электронные игры (например, для процедурной генерации) и криптография. Криптографические приложения требуют, чтобы выходные данные не были предсказуемыми из более ранней информации. Требуются более сложные алгоритмы, которые не наследуют линейность простых PRNG.

Требования и условия

Хорошие статистические свойства являются центральным требованием для получения PRNG. В общем, необходим тщательный математический анализ, чтобы иметь уверенность в том, что ГСЧ генерирует числа, которые достаточно близки к случайным, чтобы соответствовать предполагаемому использованию.

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

Использование

PRNG может быть запущен из произвольного начального состояния. Он всегда будет генерировать одну и ту же последовательность при инициализации с этим состоянием. Период PRNG определяется следующим образом: максимум по всем начальным состояниям длины бесповторного префикса последовательности. Период ограничен числом состояний, обычно измеряемых в битах. Поскольку длина периода потенциально удваивается с каждым добавленным битом «состояния», легко создавать PRNG с периодами, достаточно большими для многих практических применений.

Если внутреннее состояние PRNG содержит n битов, его период может быть не более 2n результатов, он намного короче. Для некоторых PRNG продолжительность может быть рассчитана без обхода всего периода. Регистры сдвига с линейной обратной связью (LFSR) обычно выбираются так, чтобы иметь периоды, ровные 2n − 1.

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

Возможные ошибки

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

Во многих областях исследовательские работы, в которых использовался случайный отбор, моделирование по методу Монте-Карло или другие способы, основанные на ГСЧП, гораздо менее надежны, чем это могло быть в результате использования ГНПГ низкого качества. Даже сегодня иногда требуется осторожность, о чем свидетельствует предупреждение, приведенное в Международной энциклопедии статистической науки (2010).

Пример успешного применения

В качестве иллюстрации рассмотрим широко используемый язык программирования Java. По состоянию на 2017 год, Java все еще полагается на линейный конгруэнтный генератор (LCG) для своего PRNG.

История

Первым PRNG, который избежал серьезных проблем и все еще работал довольно быстро, был Mersenne Twister (обсуждаемый ниже), информацию о котором опубликовали в 1998 году. С тех пор были разработаны другие высококачественные PRNG.

Читайте также:  Телевизор ловит только 1 канал

Но история псевдослучайных чисел этим не исчерпывается. Во второй половине 20-го века стандартный класс алгоритмов, используемых для PRNG, включал линейные конгруэнтные генераторы. Было известно, что качество LCG неадекватно, но лучшие методы были недоступны. Press et al (2007) описал результат следующим образом: «Если бы все научные статьи, результаты которых вызывают сомнения из-за [LCG и связанных с ними] исчезли с библиотечных полок, на каждой полке был бы промежуток размером с ваш кулак».

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

В частности, изобретение 1997 года Мерсена Твистера позволило избежать многих проблем с более ранними генераторами. Mersenne Twister имеет период 219937−1 итераций (≈4,3 × 106001). Доказано, что он равномерно распределен в (до) 623 измерениях (для 32-битных значений), и на момент его внедрения работал быстрее, чем другие статистически обоснованные генераторы, создающие псевдослучайные последовательности чисел.

В 2003 году Джордж Марсаглия представил семейство генераторов ксоршифтов, основанных также на линейном повторении. Такие генераторы чрезвычайно быстры и — в сочетании с нелинейной операцией — они проходят строгие статистические тесты.

В 2006 году было разработано семейство генераторов WELL. Генераторы WELL в некотором смысле улучшают качество Twister Mersenne, который имеет слишком большое пространство состояний и очень медленное восстановление из них, генерируя псевдослучайные числа c большим количеством нулей.

Криптография

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

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

Было показано, что вполне вероятно АНБ вставило асимметричный черный ход в сертифицированный NIST генератор псевдослучайных чисел Dual_EC_DRBG.

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

Большинство алгоритмов PRNG производят последовательности, которые равномерно распределены любым из нескольких тестов. Это открытый вопрос. Он один из центральных в теории и практике криптографии: есть ли способ отличить выход высококачественного PRNG от действительно случайной последовательности? В этой настройке распознаватель знает, что либо использовался известный алгоритм PRNG (но не состояние, с которым он был инициализирован), либо применялся действительно случайный алгоритм. Он должен различать их.

Безопасность большинства криптографических алгоритмов и протоколов, использующих PRNG, основана на предположении, что невозможно отличить применение подходящего PRNG от использования действительно случайной последовательности. Простейшими примерами этой зависимости являются потоковые шифры, которые чаще всего работают, исключая или отправляя открытый текст сообщения с выходом PRNG, создавая зашифрованный текст. Разработка криптографически адекватных PRNG чрезвычайно сложна, поскольку они должны соответствовать дополнительным критериям. Размер его периода является важным фактором криптографической пригодности PRNG, но не единственным.

Ранний компьютерный PRNG, предложенный Джоном фон Нейманом в 1946 году, известен как метод средних квадратов. Алгоритм следующий: возьмите любое число, возведите его в квадрат, удалите средние цифры полученного числа как «случайное число», затем используйте это число в качестве начального для следующей итерации. Например, возведение в квадрат числа 1111 дает 1234321, которое можно записать как 01234321, 8-значное число является квадратом 4-значного. Это дает 2343 как «случайное» число. Результат повторения этой процедуры — 4896 и так далее. Фон Нейман использовал 10-значные числа, но процесс был таким же.

Недостатки «среднего квадрата»

Проблема с методом «среднего квадрата» заключается в том, что все последовательности в конечном итоге повторяются, некоторые — очень быстро, например: 0000. Фон Нейман знал об этом, но он нашел подход, достаточный для своих целей, и беспокоился, что математические «исправления» будут просто скрывать ошибки, а не удалять их.

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

Читайте также:  Смартфон xiaomi mi4 64gb

Метод среднего квадрата с тех пор был вытеснен более сложными генераторами.

Новаторский метод

Недавнее новшество — объединить средний квадрат с последовательностью Вейля. Этот метод обеспечивает высокое качество продукции в течение длительного периода. Он помогает получать лучшие формулы псевдослучайных чисел.

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

Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и в среднем составляет около 2 n/2 , где n — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2 n . Если ГПСЧ может сходиться к слишком коротким циклам, такой ГПСЧ становится предсказуемым и является непригодным.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

  • Слишком короткий период/периоды.
  • Последовательные значения не являются независимыми.
  • Некоторые биты «менее случайны», чем другие.
  • Неравномерное одномерное распределение.
  • Обратимость.

В частности, алгоритм мейнфреймах, оказался очень плохим [1] [2] , что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.

Из современных ГПСЧ широкое распространение получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нишимурой. Его достоинствами являются колоссальный период (2 19937 -1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение от силы в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют сложные алгоритмы, распознающие последовательность, порождаемую с помощью вихря Мерсенна, как неслучайную. Это делает вихрь Мерсенна неподходящим для криптографии.

ГПСЧ с источником энтропии или ГСЧ

Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (ГСЧ — англ. random number generator, RNG ). Так как такие генераторы чаще всего применяются для генерации уникальных симметричных и асимметричных ключей для шифрования, они чаще всего строятся из комбинации криптостойкого ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ).

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

В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. До появления возможности считывать значения счётчика тактов, сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ до сих пор используют традиционные (устаревшие) методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в [3] , или взаимодействия между потоками, как, например, в Java secure random.

Примеры ГСЧ и источников энтропии

Несколько примеров ГСЧ с их источниками энтропии и генераторами:

Источник энтропии ГПСЧ Достоинства Недостатки
/dev/random в Linux Счётчик тактов процессора, однако собирается только во время аппаратных прерываний LFSR, с хешированием выхода через Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom)
Yarrow от Брюса Шнайера [3] Традиционные (устаревшие) методы AES-256 и Гибкий криптостойкий дизайн Долго «нагревается», очень маленькое внутреннее состояние, слишком сильно зависит от криптостойкости выбранных алгоритмов, медленный, применим исключительно для генерации ключей
Генератор Леонида Юрьева [4] Шум звуковой карты ? Скорее всего, хороший и быстрый источник энтропии Нет независимого, заведомо криптостойкого ГПСЧ, доступен исключительно в виде Windows
Microsoft

Встроен в Windows, не «застревает» Маленькое внутреннее состояние, легко предсказуем
Взаимодействие между потоками В Java другого выбора пока нет, большое внутреннее состояние Медленный сбор энтропии
Chaos от Ruptor [5] Счётчик тактов процессора, собирается непрерывно Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора Пока самый быстрый из всех, большое внутреннее состояние, не «застревает»
RRAND от Ruptor [6] Счётчик тактов процессора Зашифровывание внутреннего состояния поточным шифром Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает»

ГПСЧ в криптографии

Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а так же различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или семенем (англ. seed ), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

Читайте также:  Элементы окна графического редактора paint

Хотя многие криптостойкие ГПСЧ или поточные шифры предлагают гораздо более «случайные» числа, такие генераторы гораздо медленнее обычных арифметических и могут быть непригодны во всякого рода исследованиях, требующих, чтобы процессор был свободен для более полезных вычислений.

В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба, а так же счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.

Аппаратные ГПСЧ

Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы и также держатся в секрете. Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA- или

Из-за недостатка хороших аппаратных ГПСЧ производители вынуждены применять имеющиеся под рукой гораздо более медленные, но широко известные блочные шифры (

Примечания

  1. Дональд Кнут. Глава 3.3. Спектральный критерий // Искусство программирования. Указ. соч. — С. 129—130.
  2. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. — 2nd ed. — Cambridge University Press, 1992. — P. 277. — ISBN 0-521-43108-5
  3. 12http://www.schneier.com/yarrow.html
  4. http://leo.yuriev.ru/random
  5. http://cryptolib.com/crypto/chaos/
  6. http://cryptolib.com/crypto/rrand/

См. также

  • NIST STS — пакет статистического тестирования
  • CryptX — пакет статистического тестирования
  • Тесты DIEHARD
  • Метод Монте-Карло
  • Случайное простое число
  • Линейный конгруэнтный метод

Ссылки

  • Андрей Зубинский. В поисках случайности Компьютерное обозрение № 29 (2003)
  • Юрий Лифшиц. Курс «Современные задачи криптографии» Лекция 9: Псевдослучайные генераторы
  • Л. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел
  • noonv. Старый взгляд на новые вещи
  • Жельников Владимир. Псевдослучайные последовательности чисел // Криптография от папируса до компьютера М.: ABF, 1996.
  • random.org (англ.) — онлайновый сервис для генерации случайных чисел
  • Cryptographic Random Numbers (англ.)
  • Theory and Practice of Random Number Generation (англ.)
  • Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analysis of the Linux Random Number Generator (англ.)
  • A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (англ.) NIST SP 800-22

Литература

  • Дональд Кнут. Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: «Вильямс», 2007. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 5-8459-0081-6 (русс.) ISBN 0-201-89684-2 (англ.)

Wikimedia Foundation . 2010 .

Смотреть что такое "Псевдослучайные числа" в других словарях:

псевдослучайные числа — — [http://www.iks media.ru/glossary/index.html?gloss >Справочник технического переводчика

Псевдослучайные числа — [pse­udo random numbers], псевдослучайные величины вырабатываемая алгоритмически последовательность чисел, обладающих свойствами случайных чисел и используемых взамен последних при решении на ЭВМ ряда классов задач (см., например, Метод Мон­те… … Экономико-математический словарь

ПСЕВДОСЛУЧАЙНЫЕ ЧИСЛА — см. Случайные и псевдослучайные числа … Математическая энциклопедия

СЛУЧАЙНЫЕ И ПСЕВДОСЛУЧАЙНЫЕ ЧИСЛА — числа (или цифры ), последовательность появления к рых обладает теми или иными статистич. закономерностями (см. Вероятностей теория). Различают случайные числа (с. ч.), генерируемые каким либо стохастич. устройством, и псевдослучайные числа (п. ч … Математическая энциклопедия

Случайные и псевдослучайные числа — числа, которые могут рассматриваться в качестве реализации некоторой случайной величины (См. Случайная величина). Как правило, имеются в виду реализации случайной величины, равномерно распределенной на промежутке (0,1), или приближения к… … Большая советская энциклопедия

Алгоритмы уничтожения информации — Алгоритмы уничтожения информации последовательность операций, предназначенных для осуществления программными и/или аппаратными средствами необратимого удаления данных, в том числе остаточной информации. Как правило, данные алгоритмы… … Википедия

Генератор псевдослучайных чисел — (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному). Современная информатика… … Википедия

Датчик случайных чисел — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… … Википедия

Криптостойкий генератор псевдослучайных чисел — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… … Википедия

Псевдослучайное число — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… … Википедия

Комментировать
0 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock detector