Comments 22
причём появление того или иного значения этой величины до её измерения нельзя точно предсказать
Имелось в виду, что нельзя предсказать с вероятностью 1.
На самом деле, понятие «случайная последовательность» — довольно нетривиально. С точки зрения тервера все бесконечные последовательности нулей и единиц равноправны. Так что в computer science обычно используется определение либо через колмогоровскую сложность, либо через тесты разных классов.
Ну да, конечно. Корреляция.
Сейчас перечитал и заметил, что даны X0, X1, X2, X3. До этого подумал что даны только X1, X2, X3 — придумал небольшую хитрость для вычисления a, c, m по трем выходам:
Допустим даны
X0
X1 = X0 * a + c (mod m),
X2 = X1 * a + c (mod m).
(X2 — X1) — (X1 — X0) = a * (X1 — X0) — (X1 — X0) (mod m)
X2 + X0 — 2*X1 = (a — 1) * (X1 — X0) + k*m
Если при выборе a, c, m для максимизации периода следовали условиям (в частности, (a — 1) делит все простые делители m), то (a — 1) ** n = s*m для некоторых n > n_0 и s=s(n). При этом n_0 не больше максимальной степени простого числа в разложении m.
Обозначим Q = (X2 — X1) — (X1 — X0). Тогда Q**n == z * m. Если взять достаточно большое n, можно вычислить z * m и высчитать c' и a' по этому модулю. Если выходное число X_i' не совпадает с соответствующим известным выходом X_i,
то можно уменьшить модуль с помощью НОД: new_mod = gcd(mod, X_i' — X_i) и пересчитать a' и c'. Опять же, если получить 4й, 5й,… выходы, то очень быстро можно восстановить реальный m, а следовательно, a и c. Есть еще куча способов быстрее восстановить m (например в в z может быть много небольших простых делителей, на которые можно поделить с помощью небольшого перебора). Кроме того, перед возведением в степерь Q можно умножить на специальным образом сформированное число, чтобы необходимое n было не слишком велико для вычислений.
Проверил на нескольких случайных a, c, m с m до 1024 — бит — восстанавливается достаточно быстро.
Каждый раз разные псевдослучайные биты в initial и в seed заливаются разными потоками асинхронно всяким мусором, как то — длинна интервала (ticks) между последними heartbeat потока, каждое n-ное время ожидания (ticks) мутекса, размер некоторого пула в n-ный момент времени, xor на handle передающийся в какой-нибудь асинхронный callback, пара случайных битов из md5 какой-нибудь user credential, и т.д. и т.п. Биты строятся в seed примерно как в sha-512, причем напомню асинхронно, т.е. теоретически параллельно сразу M потоками.
Кто в теме, представляет себе на какой порядок это все отличается от того же отслеживания движений мыши пользователя…
И хоть все это и псевдослучайно, и алгоритм расчета известен, но вероятность просчитать конечный результат стремится к нулю. Что, после моей просьбы оценить эту вероятность, мой оппонент скрипя зубами и подтвердил.
А статья супер — однозначно в закладки…
Некоторые разработчики считают, что если они скроют используемый ими метод генерации или придумают свой, то этого достаточно для защиты. Это очень распространённое заблуждение. Следует помнить, что есть специальные методы и приемы для поиска зависимостей в последовательности чисел.При достаточно высоком уровне энтропии — невозможно найти какие-нибудь зависимости — их просто нет. И абсолютно неважно при этом скрыт ли алгоритм.
Буду очень признателен за любую помощь в этом направлении.
Посмотрите эту задачу code.google.com/codejam/contest/639102/dashboard#s=p0
Примерно там же есть и разбор.
Работали они более менее нормально и если кому интересно, то могу скинуть.
Но надеюсь, что для кого-нибудь окажется полезной.
Все проще!
У нас есть seed и rand и они зависимы между собой. Связь однозначная.
Если же значения ранда модулированные, то есть mt_rand(0,N), то надо больше rand, но поверьте — 624 — это ПРОСТО ДОФИГА :)
См. www.slideshare.net/d0znpp/dcg7812-cryptographyinwebapps-14052863 слайды с 18го
Простите, что отвечаю спустя 10 лет после выхода статьи. Но вдруг тут еще остался кто-то, интересующийся псевдослучайными числами и разбирающийся в методах их генерации в разных библиотеках?
История длинная (прямо хоть статью пиши... но в статье должен быть ответ, а у меня пока только вопрос.).
Так вот. Я занимаюсь научными расчетами, и внезапно обнаружил очень странный эффект. Если вызывать интеловский (встроенный в Intel Fortran) генератор равномерно распределенных случайных чисел (0,1) много раз подряд, то на некоторых компах (пока таких 4 из 5 протестированных) примерно через A=50 млн вызовов (точная цифра меняется, см.под спойлером) он начинает квазипериодически, с периодом около B=10 млн вызовов, возвращать NaN.
Подробности
Причем, значение параметра A сильно варьирует от запуска к запуску тестовой программы. На своем компьютере я получал первый NaN через 30-80 млн. вызовов функции RANDOM. А вот значение B очень стабильно: интервал между повторными NaN обычно меняется не более, чем на 10%.
На двух других протестированных компах значения параметров A и B примерно такие же, как у меня, а на третьем - вдвое меньше. Еще на одном компьютере NaN-ов нет вовсе. Все компьютеры 64-битные, процессоры - AMD и один Intel (не глючит один из AMD).
Сам тест тривиальный: генератор инициализируется некоторым числом, собранным из даты и времени (функция SEED), а потом много раз вызывается функция RANDOM. После теста результаты выводятся на график, типичный пример которого лежит вот здесь: FORTRAN_URAND_BUG.doc. Это файл Word, в котором кроме графиков с результатами приведена информация о результатах тестов на разных компах, а также тестовая программа (включая дизассемблер генератора случайных чисел). Там же написано, как скачать и запустить эту тестовую программу в виде exe-шника. Прошу прощения, но я пока не стал оформлять это все в более адекватном виде, так как не уверен, что мое сообщение здесь, в комментариях к статье 10-летней давности, вообще кто-то прочтет. Но если Вы вдруг сюда все-таки заглянули и заинтересовались - то пишите, оформлю по-человечески.
Будет ли аналогичный эффект наблюдаться в других языках/компиляторах, я проверить не могу - не располагаю компилятором/навыком. Но подозреваю, что у фортрана и Си базовые математические библиотеки часто общие. А другие языки могут что-то таскать из Си-шных библиотек. В общем, если этот вопрос тут кого-то заинтересует, я был бы благодарен за информацию о результатах ваших тестов и/или тестовые программы.
Для себя я пока решил вопрос так: сделал для встроенного генератора случайных чисел "обертку" (точнее, она и так там была, чтобы не думать в прикладных функциях про инициализацию генератора) и в случае isNan(Random) вызываю генератор повторно. Но внутренний дискомфорт остался. Я конечно понимаю, что баги могут быть даже в самых хорошо отлаженных и многократно протестированных функциях, но
НЕ В ФОРТРАНЕ ЖЕ ;-)))
Это конечно, шутка, но как известно, в каждой шутке есть доля шутки. А если немного серьезнее, то я, как фортранщик, всегда верил, что более дубовый и стабильный язык программирования надо еще поискать (КОБОЛ просьба не предлагать ;-). А уж базовому генератору случайных чисел и вовсе скоро 40 лет в обед стукнет, т.е. все должно быть отлажено, как часы. Однако же вот...
Ну и последний нюанс. Если собирать программу c выключенной оптимизацией, то все работает без NaN-ов. Меня это, мягко говоря, удивило, так как генератор случайных чисел, по идее, должен в обоих случаях вызываться один и тот же. Поскольку исходный текст функции RANDOM к моему компилятору не прилагается - вероятно, она цепляется их какой-то стандартной библиотеки - я полез в дизассемблер, чтобы понять разницу между двумя версиями генератора случайных чисел (сборка с оптимизацией и без нее). Сам генератор, как и следовало ожидать, действительно в обоих случаях одинаковый. Но внутри этой функции есть
.
один внешний вызов
Для начала предупреждаю, что в ассемблере я ни бум-бум, и пишу только на фортране! Поэтому все написанное под этим спойлером может оказаться полным бредом и воспаленным воображением. Я всего лишь хотел попытаться, насколько сумею, собрать хоть какую-то информацию про обнаруженный баг для тех, кто проявит интерес к ситуации, но не имеет возможности открыть интел-фортран и проделать все это лично.
Итак, я дизассемблировал две версии своей тестовой программы: с ключом оптимизации /Od (оптимизация запрещена) и /O2 (оптимизация скорости). Более подробная информация о компиляторе и ключах сборки есть в том же самом файле FORTRAN_URAND_BUG.doc, который упоминался выше. Оказалась, что сама функция-генератор случайных чисел в двух версиях идентична (с точностью до ее расположения в памяти, но это понятно).
Однако, внутри этой функции есть один внешний вызов:
005C052B call _for__acquire_semaphore_threaded (596C80h)
Внутри которого (после череды других call) происходит что-то уже совсем-совсем для меня непонятное:
75C34043 call 75C443C5
(...)
75C443C5 jmp dword ptr ds:[75BA007Ch]
Для непосвященного это напоминает call по адресу, хранящемуся в ячейке памяти (указатель на функцию?). Как такое дебажить, особенно если нештатное срабатывание может первый раз произойти через 50 млн вызовов, я себе представляю плохо. Точнее, не представляю вообще: это вопрос совершенно не моего уровня компетенций :-((
Но на всякий случай добавлю, что программа у меня однопоточная и, по идее, ничего согласовывать с другими потоками не должна. С другой стороны, в языке есть массивные операции, которые могут распараллеливаться автоматически, и, теоретически, генератор случайных чисел может в этом случае как-то донастраиваться для параллельных вычислений. В справке я об этом ничего не нашел, но это может быть не проблемой справки, а моей личной проблемой (справка написана по-английски, а я не знаю никаких языков, кроме русского, фортана и совсем немного фарси).
Вдогонку.
Благодаря временному просветлению от старческого маразма, я сообразил задать вопрос про генераторы случайных чисел вот тут, благодаря чему Сообщество его уже почти раскрутило!
А благодаря временному просветлению от старческого склероза - вспомнил, что хорошо бы дополнить сделанный выше комментарий ссылкой на указанное обсуждение.
Что и спешу исполнить, пока вышеназванные состояния не вернулись ;-)
Здравствуйте. У меня появилась интересная идея: использовать для генерации случайныэ чисел очень точный таймер как источник энтропии. Для надёжности, можно использовать какую-то умную математическую формулу. Ведь чаще всего число генерируется тогда, когда этого требует генерирующий, а у человека довольно медленная реакция. Кроме того что генерировать псевдослучайные числа таким образом может только человек, есть ли у алгоритма какие-то уязвимости?
Подробно о генераторах случайных и псевдослучайных чисел