Уязвимость в генераторе случайных чисел в ОС FreeBSD

> Что свидетельствует, что с koi8-r жопа настает намного раньше.

Вы просто неудачники. У мну жопа не настает ни дверандому ни девурандому ни в утф ни в кои ни на 2.6.18 ни на 2.6.22. :p

>Внутри записанной на диске последовательности бит сложно найти какие-либо закономерности, поэтому она и называется случайной.

Настоящая случайная последовательность фиксированной длины может содержать любые закономерности, может даже оказаться полным текстом «Войны и мира». На то она и случайная. А если в некоторой последовательности заведомо исключено подобное - она уже не случайная.

>Просто этот титанический труд кажется немного забавным. Случайность нельзя вогнать в рамки детерминированности, чем является, например, единичный CDROM ;)

надо же. а вот раньше таблицы использовали случайных чисел. и ничего ;)

Раньше и таблицы логарифмов использовали :)

> Настоящая случайная последовательность фиксированной длины может содержать любые закономерности, может даже оказаться полным текстом «Войны и мира».

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

Вряд ли вы, или кто-нибудь еще дождется Войны и мира в выводе rng, хотя теоретически это и возможно в случае идеального rng с бесконечным периодом, но вот если через каждые десять байт будет проскакивать слово 'Наташа', то извините, говно генератор.

Случайные числа всегда определяются от противного, такова их сущность. Если мы не видим закономерностей -- это не значит, что их нет, но если мы их видим -- генератор точно плохой. Например, батарея тестов diehard проверяет качество rng попыткой применить к выводу rng набора из нескольких десятков моделей. Если одна или больше моделей каким-то образом коррелируют, генератор плохой. Если нет, то, возможно, он не так плох.

Если говорить о prng, то есть об rng с фиксированным периодом, вероятность появления Войны и мира внутри периода легко посчитать, и она будет очень и очень маленькой. Вряд ли сейчас существует алгоритм prng, в выводе которого присутствует Война и мир, хотя и тут мы можем говорить лишь о вероятностях подобного события. Иными словами, есть много плохих rng, и из них надо выбирать наименее плохой. Идеальных не бывает (потому что этого не докажешь), но бывают достаточно хорошие, как минимум для той или иной задачи. Это уже чисто практический вывод по теме.

> На самом деле, мне эта тема очень итересна, о она напрямую связана с моими профессиональными занятиями - софт для имитационного моделирования. Пока мы обходимся двумя генераторами: простой (1) и на основе криптографии (2). Все сделано на основе стандартных библиотек и при минимальном вмешательстве с нашей стороны.

Как правило, для большинства задач, даже для Монте-Карло, вполне достаточным оказывается стандартный библиотечный генератор :) Но задачи конечно бывают разными, и чем сложнее симуляция, тем лучше генератору стоило бы быть. В общем, в этой теме конечно бесконечное количество непаханых полей, тем она и интересна.