Как правильно генерировать псевдослучайные числа?

Question

[Arti-Jack]

Доброго времени суток.

Из статьи на Хабре можно извлечь одну формулу:


Но вот при использовании данной формулы у меня выходит не совсем то, что нужно.

Поэтому как правильно генерировать каким-либо алгоритмом псевдослучайные числа ? (Как, например в Питоне при random.randint(arg1, arg2) или как в Java при использовании new Random().nextInt(100)

P.S: В метках указан Python и Java, но на самом деле подойдет любой, желательно си-подобный, язык

Answer 1

[Максим Кудрявцев]

Судя по Вашему комментарию к ответу Ivan Sokolov Вы несколько не понимайте суть своего же вопроса.

Любое, повторюсь, абсолютно любое, псевдослучайное число будет находиться в какой-то последовательности, причем сама последовательность будет строиться по какой-то формуле.

Я очень глубоко сомневаюсь что вообще кто-либо когда-либо сможет получить абсолютно случайное число, т.к. любая случайность это непознанная закономерность!

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

Возьмем, например, функцию rand() из любого языка программирования. Она будет генерировать псевдослучайное число основываясь на метки времени в unixtime. На сколько она предсказуема? Хм, думаю не менее чем на 100%. Хорошо, получается что зная приблизительное время запуска функции rand(), скажем, с точностью до 1 минуты, мы можем получить точно такое же псевдослучайное число. Отлично, т.е. вот от этого нужно и копать.

Давайте предположим, что мы вытянули список компаний из ЕГРЮЛ по Москве и взяли их ОРГН. Далее, наша функция генерирует unixtime и из него мы вычитаем этот самый ОГРН, причем последние две цифтры в unixtime и ОГРН должны совпадать(к примеру, условие выбора ОГРН может быть любое). Чего мы добились? Зная время работы функции rand() мы не можем сгенерировать второе точно такое же псевдослучайное число. Вы мне можете сейчас возразить, что давайте возьмем тот же ОГРН и повторим процедуру. На этом месте я хочу задать Вам вопрос: а от кого мы вообще строим защиту? Злоумышленник является создателем системы и знает о ней 100%? Я думаю любая защита в этом случае просто бессмысленна.

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

Будет ли при этом Ваш ряд псевдослучайных числем более или менее случайным? Хм... Большой вопрос... На этом месте опять вспоминаем что такое случайность.
Позволит ли это повысить защищенность системы? Думаю от части может, потому что злоумышленнику неизвестен алгоритм генерации, хотя это в определенной степени и плохо.

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

Comments

[Александр Пожарский]

"Я очень глубоко сомневаюсь что вообще кто-либо когда-либо сможет получить абсолютно случайное число, т.к. любая случайность это непознанная закономерность!" - квантовые процессы же? ЕМНИП, было что-то на тему того, что какой-либо последовательности результаты принадлежать не могут принципиально.

[Александр Пожарский]

Но да, нужно железо :-)

Answer 2

[Rsa97]

Практически все генераторы псевдослучайных чисел генерируют именно последовательности, где, зная начальное число (seed), можно повторить всю последовательность. Для генерации действительно случайных чисел используют аппаратные приспособления или накопление энтропийных событий (задержки между нажатиями на клавиши, движения мыши).
Код, который использует Java, приведён в этой же статье, как и код, восстанавливающий seed по двум подряд идущим результатам nextInt.

Answer 3

[xmoonlight]

Мда....
То ли лыжи не едут, то ли я......
Читаем:

Поэтому как правильно генерировать каким-либо алгоритмом псевдослучайные числа ?

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

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

Критерий выбора параметра: быстро и непредсказуемо изменяющееся значение во времени и не зависящее от алгоритма в коде генератора, недоступное из вне.

Хешируем параметры с timestamp любым алгоритмом и берём каую-то часть из полученного хеша.
ВАЖНО! Параметры для хэширования не должны быть доступны публично: никаких внешних запросов с ИНН, ОГРН и GISMETEO! )

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

Answer 4

[TheTalion]

На с#:
https://msdn.microsoft.com/ru-ru/library/system.ra...
или
https://msdn.microsoft.com/ru-ru/library/system.se...

Comments

[Arti-Jack]

Нет, я говорил именно про алгоритм, а не про готовое решение

Answer 5

[Alexej Simakov]

возьмите последовательность чисел от 0 до n, возьмите за шаг любое простое число p > n/2, и вынимайте из последовательности каждое число за номером p по кругу.
Но и тут последовательности. А вам я так понял нужно чтобы оно "создавалось" а не выбиралось.
Хоря, что плохого в выбирании, ведь карты из неотосортированной колоды тоже выбирают, и ничего, такой выбор считается случайным. A так на основании системного времени. Или белого шума радиочастоты. Или из сервиса на random.org. Если ваш алгоритм будет проходить тест diehard - отпишитесь, всем будет интересно ;)