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

Question

[Rrooom]

Как программно генерировать ДЕЙСТВИТЕЛЬНО близкие к случайным числа на промежутке?

Я читал, что для этого берут несколько источников случайных чисел - /dev/urandom, железные генераторы, посылают движения мышкой пользователя и смешивают вместе, и на основе этого потока генерят случайные числа.

Но... Я мало что знаю, как их смешивать? Как случайный поток байт превратить в число на отрезке, что бы оно оставалось достаточно случайным?

Можете либо объяснить, либо указать путь для изучения этого вопроса?

Answer 1

[barkalov]

Собираете всю энтропию побитно (паравозиком) в одно сообщение. Берете хеш-функцию с подходящим размером и распределением, например, MD5 и пропускаете сообщение через нее. На выходе получите равномерно распределенное случайное 128-битное число. То есть от 0 до (2^128)-1, если представлять беззнаково. Делите (или берете остаток, если нужны целые), прибавляете - получаете нужный вам диапазон.

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

Comments

[Deerenaros]

MD5 прекрасный вариант для того, чтобы одно случайное число сделать другим случайным числом. Как бы с распределением у него всё впорядке (если не идеально), да и это... Не надо так орать, что всё плохо, если найдёте коллизию второго рода на 256 битный хэш от двухгигабайтового фильма - лично попрошу за Вас премию как решившего задачу P ?= NP.

[jcmvbkbc]

@Deerenaros MD5 -- 128-битный

[Deerenaros]

@jcmvbkbc А два MD5, как не сложно догадаться, 256 бит.

[jcmvbkbc]

> найдёте коллизию второго рода на 256 битный хэш от двухгигабайтового фильма
@Deerenaros поиск сообщения имеющего хэш такой же, как у заданного сообщения -- это поиск коллизии первого рода.

[jcmvbkbc]

> два MD5, как не сложно догадаться, 256 бит
@Deerenaros что хэшировать будем, чтобы получить два MD5?

[barkalov]

@Deerenaros >

Не надо так орать

?

И про размер, и про первый род вам @jcmvbkbc всё верно сказал. Дискутировать с вами нет желания, сорри.

[Deerenaros]

@jcmvbkbc Окей, внимательно думаем, а что же мы вообще хэшируем. О пролетариат! Это же данные - последовательности бит. Вот берём первую половину последовательности, хэшируем, берём вторую - хэшируем. Изи катка. Восклицания о компрометации даже слушать не желаю - когда DES стал плохим из него сделали 3DES.

И да, я знаю разницу между коллизиями первого и второго рода. Бывает ошибаюсь, однако, пожалуйста, вот хэш:
91738e30083612f1132435be3d6d489d
Ну найдите, найдите мне коллизию первого рода. Пожалуйста. Это фильм, если Вам внезапно поможет. Почему-то мне даже кажется, что без браузера Вы не сможете отыскать и пару с одинаковым хешем. И да, это я ещё не колдовал.

Но что самое ужасное. Это полное непонимание поставленной задачи. Нам совершенно никак не требуется что-либо скрывать. Какой вообще смысл скрывать рандом? 128 бит энтропии около 0.8 будут теми же 128 битами с такой же энтропией. Совершенно. Подсчёт хеша здесь максимум что сделает, так это усложнит атаку нестандартным вариантом ГПСЧ. Но хеш - не магия, если что-то известно о хешируемом, также будет известно и о хеше, разве только распределение немного измениться... Если вообще измениться. Вообще, сколько я ни смотрел разных ГПСЧ - ну нет идеала. Да потому что нет случайности, откуда её взять то числодробилке? Взять хеш - это прекрасный вариант попытаться скрыть ужасное распределение. Но будь то sha1, будь то md5, да хоть md4 - вообще без разницы. Как только станет известен алгоритм хеширования, можно сразу предполагать, что хеширования и не было.

Но Вы можете дальше продолжать слепо следовать звону, не зная куда он ведёт. Где-то кто-то сказал, что md5 не использовать, ну значит это кусок говна, который вообще нигде (тем более в коммерции) никак нельзя.

@barkalov ну да пожалуйста

[jcmvbkbc]

> берём первую половину последовательности, хэшируем, берём вторую - хэшируем. Изи катка. Восклицания о компрометации даже слушать не желаю - когда DES стал плохим из него сделали 3DES.

@Deerenaros как вы нам изящно намекнули, что что такое 3DES вы тоже не знаете.

> Но что самое ужасное. Это полное непонимание поставленной задачи.

Я очень живо представляю, как вам эту фразу говорит препод. Ну, хоть что-то вы усвоили на лекциях.

[Deerenaros]

@jcmvbkbc Собственно, не помню, чтобы преподаватель какой-либо что-либо такое говорил при мне, хотя возможно просто забыл. Но задача действительно другая, и на мой скромный взгляд таки скорость в данном контексте чуть-чуть приоритетней чем списки коллизий.

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

Answer 2

[Deerenaros]

Ой, какие сложности. А отстаток брать не учили? А потом добавляем нижнюю границу.

Смешивать можно как угодно. Можно побайтово xor'ить, можно складывать, можно умножать. К слову, побайтовый xor - наверное, лучший способ перемешать. Только он побайтовый и даёт едва ли не лучшее распределение.

Ну, а числа хранятся в своеборазном пуле байт. Из этого пула можно попросить один (char), два (short) или четыре (int) байта и он будет в собственных пределах. Как случайное число превести к числу в нужном диапозоне смотрим ниже:

Number RandomBeetwen(Number min, Number max):
    return min + Random() % (max - min);

Comments

[jcmvbkbc]

> А отстаток брать не учили?
@Deerenaros а вот хрен-то там, это неправильное решение. Попробуйте проверить распределение сгенерированнх так случайных целых чисел на отрезке 0..3000000000, когда Number это unsigned int.

[Deerenaros]

@jcmvbkbc Лолшто, ясное дело распределение испортится, только задача стояла получить случайное число, читай - случайную величину, про её распределение ничего не было сказано. Да и если размер диапозона - корень какой-то степени от диапозона генератора, то и распределение ни разу не изменится - банальная компрессия, даже лучше будет.

Вообще, если диапозоны не совпадают, то при любом сжатии (деление, вычитания, остатки, логарифмы - не важно) распределение так же портится. Хотя бы потому, что случайные велечины внезапно другие становятся.

[jcmvbkbc]

> задача стояла получить случайное число, читай - случайную величину, про её распределение ничего не было сказано
Ну так надо было посоветовать return 4;, чо уж.

> Вообще, если диапозоны не совпадают, то при любом сжатии (деление, вычитания, остатки, логарифмы - не важно) распределение так же портится.
Опять мимо. И, кстати, давно ли вычитание стало сжатием?

[Deerenaros]

@jcmvbkbc да вычитайте что угодно, это не то, я про тот момент, когда у нас есть целочисленный генератор, дающий числа от [a, b), а нам нужно от [c, d), где a - b != c - d. Что не делай, если a - b не делит или не делится c - d - переход будет неравномерным. Простейшая логика. Впрочем, с вычитанием похоже пролетел...

По поводу return 4 - отличный пример. Прекрасный вариант случайных целых чисел на отрезке [4, 5).

[jcmvbkbc]

> Что не делай, если a - b не делит или не делится c - d - переход будет неравномерным.
Если распределение на исходном отрезке равномерно, то для получения равномерного распределения на новом отрезке достаточно получать новые случайные числа и выкидывать те из них, которые не попадают в новый отрезок.

[Deerenaros]

@jcmvbkbc ну.. если оно равномерно... Правда как-то я не понимаю, что значит "выкидывать"? Заново рандомить? Как-то грустно и медленно. Хотя в общем и целом, это довольно криптостойко...

Ну и потом, для начала надо бы спросить зачем вообще нужен отрезок. Боюсь, криптография здесь вообще мало причём.

[jcmvbkbc]

> Заново рандомить?
@Deerenaros да, заново.

> Как-то грустно и медленно.
Не более чем в два раза медленнее, чем в исходном генераторе. Выкидывать можно только один бит, а все остальные использовать повторно.

[Deerenaros]

@jcmvbkbc а вот и нет. Из теорвера Вам наверняка известно, что есть ненулевая вероятность бесконечного цикла по причине того, что число почему-то постоянно не подходит. Нет, оно конечно очень маловероятно, что придётся вечность числа придумывать, однако вполне возможно (особенно, если ГПСЧ используется часто), что на какое-то число уйдёт втрое, а то и вчетверо больше времени, чем обычно. Раз из тысячи, но таки да.

[jcmvbkbc]

> на какое-то число уйдёт втрое, а то и вчетверо больше времени, чем обычно
@Deerenaros конечно, будут флуктуации, но в среднем -- не более чем вдвое.

[Deerenaros]

@jcmvbkbc ладно, ладно. Остановимся на "среднем", здесь же математики собрались. Какое нам дело до непонятных утечек вследствии того, что конвейр почему-то переполняет буфер, раз в пару дней, но таки переполняет, а грёбанную проверку кто-то не сделал, ибо понадеялись на "в среднем" (если что, буфер использовался очень и очень часто, думали даже о хардварном варианте в виде платы PCI-Express; с простыми числами никак не связано).

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

Answer 3

[jcmvbkbc]

Я читал, что для этого берут несколько источников случайных чисел - /dev/urandom, железные генераторы, посылают движения мышкой пользователя и смешивают вместе... Я мало что знаю, как их смешивать?

Если у вас есть /dev/urandom то всё уже смешано как надо, берите случайные биты оттуда.

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

Зависит от того, нужны ли вам целые числа на вашем отрезке или плавающие.

С целыми числами нужно взять столько случайных бит, сколько покрывает нужный вам отрезок, значения которые не вписываются в отрезок выкинуть и сместить полученное значение к началу отрезка. Для плавающих чисел ещё проще: нужно взять единицу вашего плавающего типа, заменить биты мантиссы (23 для float, 52 для double) случайными битами и отнять 1. Получится случайное число в диапазоне [0, 1), умножить его на длину отрезка и сместить к его началу.

В частном случае, если криптостойкость не нужна, то для получения раномерно распределённых на отрезке [a, b) плавающих чисел проще всего взять drand48: r = drand48() * (b - a) + a.

Comments

[Deerenaros]

@jcmvbkbc ну не совсем всё смешано как надо. В хардовом ИБ рекомендуют всё делать как минимум нестандартно. От размещения ssh порта на 3947ом порте, до дополнительного перемешивания байтов из /dev/urandom. Почему? Потому что любой может посмотреть что там в urandom и как числа от туда получаются, а этого совсем не надо. Это всё хорошо, что система теоретически устойчива к полному исследованию, но чем больше вставить палок в колёса врагам, тем лучше. Чем меньше он знает, тем сложнее (читай, дороже) ему будет пробраться в систему.

Я к тому, что совет о дополнительной энтропии из других источников весьма и весьма не плох.

[jcmvbkbc]

> В хардовом ИБ рекомендуют всё делать как минимум нестандартно.
@Deerenaros чтобы делать что-то нестандартно, нужно очень хорошо понимать, что делаешь. Автор вопроса явно говорит, что это не тот случай.

[Deerenaros]

@jcmvbkbc Поэтому я и советую. Тем более, что чтобы испортить /dev/urandom надо сильно постараться. Случайность тема весьма интересная, и даже очень хреновый ГПСЧ может оказаться чрезвычайно криптоустойчивым банально потому, что вообще никакой информации о нём у атакующего нет. А такая информация... Её как бы легко скрывать - заинкапсулировать куда-нибудь очень глубоко-глубоко едва ли не в железе и пролетариат с ней, остальные лишь используют это как обычный ГПСЧ не думая о реализации.