-1
$\begingroup$

I need a simple PRNG function of type: Integer = PRNG(n, maxval) as I would like to count from 0 to maxval, not in a linear manner, but in a pseudorandom manner where I still use every value, but only once. For example, "0 to maxval=9" might result in "3,8,4,5,1,9,0,2,6,7", and if I asked the function for "Integer = PRNG(3)" in this case it would return the third value which is 4. (For my actual need maxval is always 64bit so 0xFFFFFFFFFFFFFFFF)

Im hoping this can be accomplished without shuffling a pre-filled array? My googling suggests perhaps a "feedback register" of sorts could be what I'm after but ive got no idea which. Thankyou

ps. are there any CPRNG secure versions of this? I dont need that level of security - PRNG is fine, but just wondering!

$\endgroup$
  • $\begingroup$ "without shuffles/arrays" seems like a rather arbitrary requirement. $\;$ $\endgroup$ – user991 Jul 22 '15 at 1:22
  • $\begingroup$ So there's no way of doing this without creating a 64bit array with values 0 to FFFFFFFFFFFFFFFF and shuffling that? seems expensive and inefficient! $\endgroup$ – David Jul 22 '15 at 1:47
  • $\begingroup$ There is a much cheaper and more efficient method; it just only does the $\hspace{1.76 in}$ currently-relevant parts of each shuffle. $\;$ $\endgroup$ – user991 Jul 22 '15 at 5:49
  • 2
    $\begingroup$ Don't get me wrong, but we're not Google. It's not clear to me what your request for a PRNG recommendation has to do with cryptography... maybe you could edit your question and explain the exact scenario, what you've tried, what you've researched, and what exactly you need help with. For more infos on "how to ask", please take a look at our help center. $\endgroup$ – e-sushi Jul 22 '15 at 6:00
  • $\begingroup$ @David No, it is entirely possible to do for 64 bit values in constant space - see my answer. $\endgroup$ – Thomas M. DuBuisson Jul 22 '15 at 16:20
3
$\begingroup$

Just use a small block sized block cipher in counter mode and filter out elements that are out of range.

Given that you are asking for a bigint (64-bits) as output, you don't even need to filter out-of-range values. Simply using 3DES, blowfish, or CAST5 directly, as they have a 64-bit block size.

$\endgroup$
  • $\begingroup$ What block ciphers have blocks smaller than 64 bits? Is there such a thing as a 32-bit or smaller block cipher that would exhibit the correct PRP behavior? $\endgroup$ – rmalayter Aug 20 '15 at 5:01
  • $\begingroup$ Yes. It is also really simple to take the Simon family and make any even number bit sized block cipher you desire. I am tempted to mashes a shall blog post that explains this answer and provides an example. $\endgroup$ – Thomas M. DuBuisson Aug 20 '15 at 6:51
  • $\begingroup$ I should have said explicitly: Simon and Speck both have 32 bit variants. Making a 4, 6, 24, 28, or any other even block sized version is easy. $\endgroup$ – Thomas M. DuBuisson Aug 20 '15 at 15:35
  • $\begingroup$ Skip32 and ipcrypt have 32 bit blocks. $\endgroup$ – CodesInChaos Aug 20 '15 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.