Pull to refresh
Comments 8
Мне давно интересно — есть генераторы рандома, которые заполняются даннными, а затем их преобразуют по сложному непредсказуемому алгоритму, а есть хэш-функции, которые работают по тому же принципу.
Вы, как человек, разбирающийся больше меня, может знаете — являются ли они взаимозаменяемыми и, если нет, то почему?
Даже навскидку если прикинуть — 100% взаимозаменяемости точно нет. Ибо «Хеш-функция — это такая функция, которая осуществляет преобразование набора входных данных произвольной длины в битовую последовательность установленной длины».
а ГПСЧ, насколько я понимаю их работу, всё-таки фиксированные N бит имеют и как результат, и их же как входные данные уже для следующей итерации.

Опять же, если немного призадуматься про назначения — хеш-функция, как бы и должна выполнятся быстро, но если речь про криптографию, то какой-то промежуток времени её вычисление должно занимать, для защиты от брут-форса.
У ГСПЧ такого ограничения точно нет, лишь бы выдавал данные похожие на нормальное распределение, а если он это ещё и «мгновенно» сможет сделать, тем лучше.

Хм, только что наткнулс на википедии, что в /dev/random, Microsoft CryptoAPI и Java SecureRandom используют SHA-1 и MD-5.
Но всё равно лично мне непонятно, почему как нельзя использовать.


random = SHA-3(random)
Хоть uacrypto и говорит о «не взаимозаменяемы в общем случае» лично я не считаю последовательность random = SHA-3(random) плохой (она просто в несколько раз медленнее более простых ГПСЧ).
К примеру тут habr.com/ru/post/122711 пишут: «Самый простой объект который может дать хорошую случайность это хеш-функции.»

habr.com/ru/post/151187 — «Подробно о генераторах случайных и псевдослучайных чисел» («В интернете можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.»)
Как минимум, для криптографического ПДСЧ, должно быть сложно по выходным данным понять внутреннее состояние, чтобы предсказать предыдущие/последующие данные. Ваша схема этому критерию не соответствует.
Да, схему, конечно же, можно (нужно) доработать.

r = SHA-3( r )
random = r mod 1000

В этом случае даже зная random не получится предсказать значение внутренней переменной r (и предсказать следующее значение random).

PS. По правде говоря, большинство криптостойких хешей имеют длину более 128 бит, а переменная random почти всегда будет 64 бита или короче, поэтому такое усечение будет делаться всегда.

К хеш функциям и "генераторам рандома" предъявляются различные требования при разработке. Криптографические Хеш функции должны быть устойчивы к коллизиям, нахождению прообраза, нахождению второго прообраза и обеспечивать компрессию строк большой длинны в строку малого размера. Генераторы рандома должны уметь генерировать последовательность бит вычислимо неотличимую от случайной последовательности. Так как эти свойства хеш функций и псевдослучайных генераторов не являются эквивалентными, то соответственно криптопримитивы не взаимозаменяемыми в общем случае.

Only those users with full accounts are able to leave comments. Log in, please.