Ищете PRNG, который можно посеять с любым числом байтов - PullRequest
Новая
       44

Ищете PRNG, который можно посеять с любым числом байтов

0 голосов
/ 29 января 2010

Я ищу PRNG (псевдослучайность), который вы изначально заполняете произвольным массивом байтов.

Слышал ли кто-нибудь?

Ответы [ 2 ]

3 голосов
/ 01 февраля 2010

Хэширование вашего начального числа произвольной длины (вместо использования XOR, как предложено paxdiablo) гарантирует, что коллизии крайне маловероятны, т. Е. Равны вероятности коллизии хэшей, с чем-то вроде SHA1 / 2 это практически невозможно.

Затем вы можете использовать свое хешированное семя в качестве входного сигнала для приличного PRNG, такого как мой любимый, Mersenne Twister.

UPDATE

Доступная здесь реализация Mersenne Twister, похоже, уже принимает ключ произвольной длины: http://code.msdn.microsoft.com/MersenneTwister/Release/ProjectReleases.aspx?ReleaseId=529

ОБНОВЛЕНИЕ 2

Для анализа того, насколько маловероятно столкновение SHA2, посмотрите, как тяжело кому-то придется работать, чтобы найти его, цитируя http://en.wikipedia.org/wiki/SHA_hash_functions#SHA-2:

Существуют две атаки прообраза «посередине» против SHA-2 с уменьшенным количеством раундов. Первый атакует 41-раундовый SHA-256 из 64 раундов со сложностью времени 2 ^ 253,5 и пространственной сложностью 2 ^ 16, и 46-раундовый SHA-512 из 80 раундов со временем 2 ^ 511,5 и пробелом 2 ^ 3 , Второй атакует 42-раундовый SHA-256 с временной сложностью 2 ^ 251,7 и пространственной сложностью 2 ^ 12, и 42-раундовый SHA-512 с временем 2 ^ 502 и пробелом 2 ^ 22.

2 голосов
/ 29 января 2010

Почему бы вам просто не XOR вашей произвольной последовательности в тип правильной длины (добавив его при необходимости к части)? Например, если вы хотите, чтобы начальное число "paxdiablo" и ваш PRNG имел четырехбайтовое начальное число: 

paxd    0x70617864
iabl    0x6961626c
opax    0x6f706178
        ----------
        0x76707b70 or 0x707b7076 (Intel-endian).

Я знаю, что семя выглядит искусственным (и это потому, что ключ выбран из буквенных символов). Если вы действительно хотите, чтобы фраза отличалась от того, где фраза может быть похожего диапазона, снова сделайте XOR с помощью дифференциатора, например 0xdeadbeef или 0xa55a1248: 

paxd    0x70617864    0x70617864
iabl    0x6961626c    0x6961626c
opax    0x6f706178    0x6f706178
        0xdeadbeef    0xa55a1248
        ----------    ----------
        0xa8ddc59f    0xd32a6938

Я предпочитаю второй, поскольку он с большей готовностью перемещает подобные байты в разрозненные диапазоны (старшие разряды байтов в дифференциаторе разнородны).

...