maxcoolmakarov Dec 20 2020 at 22:52

Хеш-функции на основе клеточных автоматов

3 min

4.9K

Cryptography*

From sandbox

+13

Comments 8

tetelevm Dec 21 2020 at 10:24

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

UFO just landed and posted this here

tetelevm Dec 21 2020 at 11:19

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

random = SHA-3(random)

imageman Dec 21 2020 at 14:07

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

habr.com/ru/post/151187 — «Подробно о генераторах случайных и псевдослучайных чисел» («В интернете можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.»)

tetelevm Dec 22 2020 at 15:42

Спасибо, интересные статьи.

TheDaemon Dec 21 2020 at 20:06

Как минимум, для криптографического ПДСЧ, должно быть сложно по выходным данным понять внутреннее состояние, чтобы предсказать предыдущие/последующие данные. Ваша схема этому критерию не соответствует.

imageman Dec 23 2020 at 16:41

Да, схему, конечно же, можно (нужно) доработать.

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

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

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

uacrypto Dec 21 2020 at 11:40

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

Show the best of all time