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

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

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

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

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

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

@Deerenaros >

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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